ИИ шахматы на 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 с алгоритмом, который может продемонстрировать неплохую игру.

РУБРИКИ В СТАТЬЕ

МЕРОПРИЯТИЯ

Искать мидлов или растить джунов?
26 февраля Онлайн Бесплатно
Kubernetes® Meetup
05 марта Москва Бесплатно

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

ВАКАНСИИ

Front-end developer
от 140000 RUB до 200000 RUB
Go developer
от 140000 RUB до 200000 RUB
Release Manager
Хилверсюм, по итогам собеседования
Unity 3D Developer
по итогам собеседования

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

BUG