Как стать автором
Обновить

Некоторые идеи написания искуственного интелекта для шахмат

Время на прочтение 7 мин
Количество просмотров 19K
К сожалению, для шахмат пока нет лучших алгоритмов, чем перебор очень многих позиций. Правда, перебор порядком (и не одним) оптимизированный, но все же это большой перебор. Для поиска ответного хода строится дерево с исходным ходом в корне, ребрами — ходами-ответами и узлами — новыми позициями.

image

Как в элементарных алгоритмах выбирается следующий ход объяснить просто. На своем ходе вы выбираете такой ход (по вашему мнению), который принесет наибольшую пользу (максимизирует вашу выгоду), а противник на очередном своем ходе старается выбрать ход, который принесет ему больше всего пользы (максимизирует его выгоду и минимизирует вашу). Алгоритм с таким принципом называется минимакс. На каждом этапе вы присваиваете каждому узлу в дереве оценку позиции (об этом потом) и на своем ходе ее максимизируете, а на ходе противника — минимизируете. Алгоритм во время работы должен пройти по всем узлам дерева (то есть по всем возможный игровым позициям в игре), то есть совсем непригоден по времени.
Следующее его усовершенствование — альфа-бета отсечение (метод веток и границ).

Из названия следует, что в алгоритме проводится отсекание по каким-то двум параметрам — альфа и бета. Главная идея отсечения в том, что теперь мы будем держать интервал отсечений (нижняя и верхняя границы — альфа и бета соответственно — ваш К.О.) и оценки всех узлов, какие не попадают в интервал снизу мы рассматривать не будем (так как они не влияют на результат — это просто худшие ходы, чем уже найденный), а сам интервал будем сужать по мере нахождения лучших ходов. Хотя и альфа-бета отсечение намного лучше минимикса, все же время его работы тоже очень большое. Если принять, что в середине партии в одной стороны есть приблизительно 40 разных ходов, то время алгоритма можно оценить как O(40^P), где P — глубина дерева ходов. Конечно, при минимаксе может быть такая последовательность рассмотрения ходов, когда мы не будем делать никаких отсечений, тогда альфа-бета отсечение просто превратится в минимакс. В лучшем случае с помощью альфа-бета отсечения можно избежать проверки корня из числа всех ходов в минимаксе. Для того, чтоб избежать долгого времени работы (при такой О-большое сложности алгоритма), перебор в дереве делают на какую-то фиксированную величину и там проводят оценку узла. Вот эта оценка есть очень великое приближение к реальной оценке узла (то есть, перебора до конца дерева, а там результат — «выиграл, проиграл, ничья»). Насчет оценки узла есть просто кипа различных методик (можно прочесть в линках в конце статьи). Если кратко — то, естественно, подсчитываю материал игрока (согласно одной системе — целыми числами пешка — 100, конь и слон — 300, ладья — 500, ферзь — 900; согласно другой системе — действительными в частях от единицы) + позиция на доске данного игрока. Насчет позиции — то здесь начинается один из кошмаров написания шахмат, так как скорость работы проги будет в основном зависеть от оценочной функции и, если точнее, то от оценки позиции. Тут уже кто во что горазд. За спаренных тур игроку +, за прикрытость короля своими пешками +, за пешку возле другого конца доски + и т.д., а минусуют позицию висячие фигуры, открытый король и т.д. и т.п. — факторов можно написать кучу. Вот для оценки позиции в игре строится оценка позиции игрока, что делает ход, и от нее отнимается оценка соответствующей позиции противника. Как говорят, одна фотография иногда лучше тысячи слов, и, может, кусок кода на псевдо C# тоже будет лучше объяснений:

enum CurentPlayer {Me, Opponent};

public int AlphaBetaPruning (int alpha, int beta, int depth, CurrentPlayer currentPlayer)
{
    // value of current node
    int value;

    // count current node
    ++nodesSearched;

    // get opposite to currentPlayer
    CurrentPlayer opponentPlayer = GetOppositePlayerTo(currentPlayer);

    // generates all moves for player, which turn is to make move
    / /moves, generated by this method, are free of moves
    // after making which current player would be in check
    List<Move> moves = GenerateAllMovesForPlayer(currentPlayer);

    // loop through the moves
    foreach move in moves
    {        
        MakeMove(move);
        ++ply;

        // If depth is still, continue to search deeper
        if (depth > 1)
            value = -AlphaBetaPruning (-beta, -alpha, depth - 1, opponentPlayer);
        else 
            // If no depth left (leaf node), evalute that position
            value = EvaluatePlayerPosition(currentPlayer) - EvaluatePlayerPosition(opponentPlayer); 

        RollBackLastMove();
        --ply;

        if (value > alpha) 
        {
            // This move is so good that caused a cutoff of rest tree
            if (value >= beta)
                return beta;
            alpha = value;
        }
    }

    if (moves.Count == 0) 
    {
        // if no moves, than position is checkmate or
        if (IsInCheck(currentPlayer))
            return (-MateValue + ply);
        else
            return 0;
    }

    return alpha;
}


Думаю, не будут излишними некоторые объяснения насчет кода:
  • GetOppositePlayerTo() просто меняет CurrentPlayer.Me на CurrentPlayer.Opponent і наоборот
  • MakeMove() делает следующий ход из списка ходов
  • ply — глобальная переменная (часть класса), которая держит в себе количество полуходов, сделанных на данной глубине

Пример использования метода:

{
      ply = 0;
      nodesSearched = 0;
      int score = AlphaBetaPruning (-MateValue, MateValue, max_depth, CurrentPlayer.Me);
} 

где MateValue — достаточно большое число.
Параметр max_depth — максимальная глубина, на которую опустится алгоритм в дереве. Следует иметь в виду, что псевдокод чисто демонстративный, но вполне рабочий.

Вместо того, чтоб придумать новый алгоримт, люди, продвигающие альфа-бета отсечение, придумали много различных эвристик. Эвристика — просто небольшой хак, который иногда делает очень большой выигрыш в скорости. Эвристик для шахмат есть очень много, всех не пересчитаешь. Я приведу лишь основные, остальные можно найти в линках в конце статьи.

Во-первых, применяется очень известная эвристика «нулевой ход». В спокойной позиции противнику дают сделать два хода вместо одного и после этого рассматривают дерево на глубину (depth-2), а не (depth-1). Если после оценки такого поддерева окажется, что у текущего игрока все равно есть преимущество, то нет смысла рассматривать поддерево далее, так как после своего следующего хода игрок только сделает свою позицию лучше. Так как перебор полиномиальный, то выигрыш в скорости ощутимый. Иногда бывает так, что противник выровняет свое преимущество, тогда надо рассматривать все поддерево до конца. Пустой ход надо делать не всегда (например, когда один из королей под шахом, в цугцванге или в ендшпиле).

Далее, используется идея сначала сделать ход, в котором будет взятие фигуры противника, которая сделала последний ход. Так как почти все ходы во время перебора тупые не очень разумные, то такая идея сильно сузит окно поиска еще в начале, тем самым отсекая много ненужных ходов.

Также известна эвристика истории или служба лучших ходов. Во время перебора сохраняются лучшие ходы на данном уровне дерева, и при рассмотрении позиции сначала можно попробовать сделать такой ход для данной глубины (базируется на идее, что на равных глубинах в дереве очень часто делают одинаковые лучшие ходы).
Известно, что такое своеобразное кеширование ходов улучшило производительность советской проги Каисса в 10 раз.

Также есть некоторые идеи насчет генерации ходов. Сначала рассматривают выигрышные взятия, то есть такие взятия, когда фигура с меньшой оценкой бьет фигуру с большей оценкой. Потом рассматривают promotions (когда пешку на другом конце доски можно заменить на более сильную фигуру), затем равные взятия и затем ходы с кеша эвристики истории. Остальные ходы можно отсортировать за контролем над доской или каким-то другим критерием.

Все было бы хорошо, если бы альфа-бета отсечение гарантировано давало бы лучший ответ. Даже учитывая долгое время на перебор. Но не тут то было. Проблема в том, что после перебора на фиксированную величину проводится оценка позиции и все, а, как оказалось, в некоторых игровых позициях нельзя прекращать перебор. После многих попыток выяснилось, что перебор можно прекращать только в спокойных позициях. Поэтому в основном переборе дописали дополнительный перебор, в котором рассматриваются только взятия, promotions и шахи (называется форсированный перебор). Также заметили, что некоторый позиции с разменом в середине также надо рассматривать поглубже. Так появились идеи насчет extensions і reductions, то есть углублений и укорачиваний дерева перебора. Для углублений найболее подходящие позиции типа ендшпиля с пешками, ухода от шаха, размен фигуры в середине перебора и т.д. Для укорачиваний подходят «абсолютно спокойные» позиции. В советской программе Каисса форсированный перебор был немного особенным — там после взятия во время перебора сразу начинался форсированный и его глубина не ограничивалась (так как за некоторое время он сам себя исчерпает в спокойной позиции).

Как говорил Энтони Хоар: "Premature optimization is the root of all evil in programming." (примечание: для тех, кто считает, что данная цитата принадлежит Кнуту, есть интересные дискусии тут и тут). В шахматном переборе, где будет относительно большая глубина рекурсии думать об оптимизациях надо, но очень осторожно.
Тут тоже есть несколько общих идей:
  • библиотека дебютов (дебютная теория в шахматах очень продвинутая — Wiki + Database)
  • библиотека эндшпилей (аналогично есть много баз данных с готовыми эндшпилями)
  • итеративные углубления+кеширование: идея в том, чтоб делать перебор сначала на глубину 1, потом 2, 3 и так далее. При этом сохранять данную позицию, ее наилучший ход, глубину или еще что-то в какой-то хеш-таблице. Вся суть итеративных углублений в том, что результатом незаконченного перебора пользоваться нельзя (тогда лучше провести неполный перебор на меньшую глубину) и при переборе на большую глубину можно использовать результаты перебора на меньшую глубину. Даже выходит так, что перебор на глубину от 1 до 6 выполняется быстрее, чем перебор сразу на глубину 6.


В статье была использована информация с некоторых ресурсов:


P.S. Вся теория была мной использована на практике и некоторое время существовал несложный rest-вебсервис на PHP для шахмат онлайн + программа на C# (использовался .NET Remoting для сетевой игры), но теперь сайт не рабочий и когда будет время, хочу перенести на RubyOnRails.

P.P.S. Кому интересно — проект теперь живет на гуглокоде и апгрейдится, когда у меня есть время. Кто захочет код предыдущей версии — могу выслать.
Теги:
Хабы:
+42
Комментарии 26
Комментарии Комментарии 26

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн