ИИ шахматы на JavaScript в 5 этапов

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

Интересуетесь искусственным интеллектом? Тогда познакомьтесь с созданием шахмат :)

1. Визуализация доски и перебор ходов

Для реализации мы воспользуемся библиотеками JavaScript: chessboard.js позволит визуализировать доску, а chess.js – сгенерировать возможные перемещения.

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

var calculateBestMove = function(game) {
    //генерируем все движения для заданной позиции
    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;
    //используем отрицательное число
    var bestValue = -9999;

    //создаем цикл for
    for (var i = 0; i < newGameMoves.length; i++) {
        var newGameMove = newGameMoves[i];
        game.ugly_move(newGameMove);

        //используем отрицательные значения, если у ИИ черные фигуры
        var boardValue = -evaluateBoard(game.board())
        game.undo();
        if (boardValue > bestValue) {
            bestValue = boardValue;
            bestMove = newGameMove
        }
    }
    return bestMove;
};

3. Правило принятия решений

Создаем дерево поиска, с помощью которого выбирается лучший ход. Для этого используется алгоритм минимакс. Рекурсивное дерево всех возможных перемещений исследуется до заданной глубины, а сама позиция – это «листья». После анализа возвращается или наименьшее, или наибольшее значение, в зависимости от того, какой цвет шахмат задействован.

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;
    }
};

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

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

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

5. Улучшенная оценка

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

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