Создаем несложный шахматный ИИ: 5 простых этапов



    Перевели для вас статью Лори Хартикка (Lauri Hartikka) о создании простейшего ИИ для шахмат. Она написана еще в 2017 году, но базовые принципы остались теми же. Все файлы, которые использовал Лори, тоже доступны.

    Простой искусственный интеллект, который умеет играть в шахматы, можно создать на базе четырех концепций:

    1. 1. Перемещение;
    2. 2. Оценка доски;
    3. 3. Минимакс;
    4. 4. Альфа-бета-отсечение. На каждом этапе работы с алгоритмом будет использоваться одна из них, это позволит постепенно совершенствовать игровые способности ИИ.

    Skillbox рекомендует: Прикладной онлайн-курс «Аналитик данных Python».

    Напоминаем: для всех читателей «Хабра» — скидка 10 000 рублей при записи на любой курс Skillbox по промокоду «Хабр».

    Готовый исходный код можно найти на GitHub.


    Этап 1. Визуализация шахматной доски с генерацией ходов


    На этом этапе мы будем использовать библиотеки chess.js для генерации ходов и chessboard.js для визуализации доски. Библиотека, которая отвечает за генерацию ходов, позволяет применять все шахматные правила, так что мы можем рассчитывать каждое действие для конкретного расположения фигур.


    При клике на картинке она откроется в полном разрешении.

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

    var calculateBestMove =function(game) {
        //generate all the moves for a given position
        var newGameMoves = game.ugly_moves();
        return newGameMoves[Math.floor(Math.random() * newGameMoves.length)];
    };

    Несмотря на то, что алгоритм не является идеальным игроком в шахматы, для большинства игроков его уровня этого будет вполне достаточно.


    Черные ходят случайным образом. (исходники и игра онлайн)

    Этап 2. Оценка позиции


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



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

    var calculateBestMove = function (game) {
     
        var newGameMoves = game.ugly_moves();
        var bestMove = null;
        //use any negative large number
        var bestValue = -9999;
     
        for (var i = 0; i < newGameMoves.length; i++) {
            var newGameMove = newGameMoves[i];
            game.ugly_move(newGameMove);
     
            //take the negative as AI plays as black
            var boardValue = -evaluateBoard(game.board())
            game.undo();
            if (boardValue > bestValue) {
                bestValue = boardValue;
                bestMove = newGameMove
            }
        }
     
        return bestMove;
     
    };

    В принципе, уровень прежний, но алгоритм уже может взять чужую фигуру, когда такая возможность есть.


    Черные получили возможность брать белые фигуры. (Исходники и игра здесь).

    Этап 3. Дерево поиска с минимакс


    После этого мы создаем дерево поиска. Теперь программа может выбрать из него лучший ход. Это делается при помощи минимакс-алгоритма.

    Здесь рекурсивное дерево с отображением всех возможных ходов анализируется до заданной глубины. Позиция же оценивается по листьям нашего дерева.

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


    Здесь лучшим ходом для белых является b2-c3, поскольку он гарантирует, что игрок доберется до позиции с оценкой -50.

    var minimax = function (depth, game, isMaximisingPlayer) {
        if (depth === 0) {
            return -evaluateBoard(game.board());
        }
        var newGameMoves = game.ugly_moves();
        if (isMaximisingPlayer) {
            var bestMove = -9999;
            for (var i = 0; i < newGameMoves.length; i++) {
                game.ugly_move(newGameMoves[i]);
                bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
                game.undo();
            }
            return bestMove;
        } else {
            var bestMove = 9999;
            for (var i = 0; i < newGameMoves.length; i++) {
                game.ugly_move(newGameMoves[i]);
                bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
                game.undo();
            }
            return bestMove;
        }
    };

    С минимакс-алгоритмом наш ИИ уже стал понимать базовую тактику шахмат.

    Минимакс с глубиной 2 (Исходники и игра здесь)

    Стоит отметить, что эффективность минимакс-алгоритма увеличивается с глубиной поиска. За это отвечает следующий этап.

    Этап 4. Альфа-бета-отсечения


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

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

    На результат минимакса оптимизация не влияет, но все начинает работать быстрее.

    Этот алгоритм гораздо более эффективен в том случае, если сначала проверить пути, ведущие к хорошим ходам.


    Изображение демонстрирует ходы, которые становятся ненужными в процессе использования альфа-бета-отсечения.

    Как видите, с альфа-бета-отсечением минимакс оптимизируется, и весьма значительно.


    Количество позиций, которые требуется оценить в случае поиска с глубиной 4 и начальной позицией, которая изображена выше. (исходники и игра доступны здесь)

    Этап 5. Улучшенная функция оценки


    Изначальная функция оценки достаточно простая, поскольку она просто считает очки фигур, находящихся на доске. Для ее оптимизации можно учитывать положение фигур. К примеру, если разместить коня в центре доски, то он становится дороже — спектр доступных ходов для этой фигуры расширится.

    На этом этапе мы будем работать с несколько видоизмененной версией квадратных таблиц, изначально описанной в вики Chess Programming.



    И теперь наш алгоритм играет уже весьма неплохо, конечно, по сравнению со средним игроком.


    Исходники и игра доступны здесь

    Заключение


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

    Реализация нашего алгоритма выполнена всего в 200 строк кода, так что базовые принципы достаточно просты. Финальную версию программы можно <a href=«github.com/lhartikk/simple-chess-ai'>видеть на GitHub.

    В алгоритм можно добавить и другие модули, включая:



    Больше о шахматных алгоритмах можно узнать на Chess Programming Wiki.

    Skillbox рекомендует:

    • +35
    • 7,1k
    • 6
    Skillbox
    325,00
    Онлайн-университет профессий будущего
    Поделиться публикацией

    Комментарии 6

      +4
      Как видите, с альфа-бета-отсечением минимакс оптимизируется, и весьма значительно.


      Тем не менее, этого мало для быстрой и сильной игры.
      Вам ещё нужны будут:
      Late Move Reduction
      Продление взятий
      Продление шахов
      Эвристика убийцы
      Итеративное углубление
      Сортировка фигур MVV/LVA
      Нулевой ход
      Futility pruning
      Razoring
      Хэш таблица
      Эвристика истории

      Я, кстати, тут всё это описывал.
      А ещё крайне желательно делать генератор ходов на битовых матрицах — это ещё больше ускорит работу программы.
        –1
        Вот зачем называть некий алгоритм даже если это нейросеть называть его ИИ? Он что себя осознает? Или соответствует ещё каким то критериям ИИ? Это всего лишь алгоритмы, ИИ тут и близко нет.
          +1

          Тоже баловался написанием шахмат на разных языках

            +1
            А ничего, что эта статья уже была переведена,
            причем перевод был несколько ближе к оригиналу?

            Поправьте, могу ошибаться: это не против политики Хабра?

            Не следует:
            Заниматься плагиатом
            Не следует копировать на «Хабр» тексты, опубликованные другими людьми на других ресурсах, но можно копировать собственные тексты, если они не нарушают правила ресурса.
              0
              Вот пример неточности перевода:

              Оригинал:
              Although this algorithm isn’t a very solid chess player, it’s a good starting point, as we can actually play against it:

              Ваш перевод:
              Несмотря на то, что алгоритм не является идеальным игроком в шахматы, для большинства игроков его уровня этого будет вполне достаточно.

              (примечание: алгоритма, который выбирает случайный ход без всякой оценки, «достаточно для большинства игроков его уровня?» То есть, уровня «обезьянки за печатной машинкой»? Это вроде как тавтология. Т.е., игрока 0-го уровня, очевидно, достаточно для игрока 0-го уровня).

              Перевод с TProger:
              Хотя этот алгоритм не очень солидный шахматист, но это хорошая отправная точка, поскольку его уровня достаточно, чтобы сыграть с нами:

              Да, «солидный» как-то не литературно, но логика сохранена.
                0
                емнип что-то подобное приведено в качестве примера в книге Вирта про паскаль более 25 лет назад… но это надо уточнить на книжной полке.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое