Пишем простой ИИ для шахмат на Javascript
...с условием, что данный AI будет играть получше, чем вот это, хотя насчёт этого не уверен :)
1. Генерация ходов и отрисовка доски
Эти рутинные задачи способны съесть значительную часть времени разработки.
К счастью, в последние годы появились прекрасные готовые библиотеки для шахмат на JS:
- генерацию ходов и проверку всех правил шахмат может сделать chess.js, с её помощью мы рассчитаем все возможные из текущей позиции ходы;
- с визуализацией доски поможет chessboard.js, мы её выкачаем и единственное, что изменим - настроим путь по умолчанию к картинкам (установкой свойства
cfg.pieceTheme), чтобы не зависить от внешнего сервера.
Сами картинки с шахматными фигурами легко найти где угодно.
Для работы понадобится также общепринятая сегодня Javascript-библиотека JQuery, можно скачать и её, но мы просто подключим её извне.
В программе нам останется сделать что-то вроде:
var game = new Chess();
var board = ChessBoard('board', cfg);
Таким образом, рутина выполнена, а предстоит лишь реализовать алгоритм выбора лучшего хода из тех, что предложит библиотека.
Начнём с функции, которая выберет случайный ход из всех возможных, она не слишком интеллектуальна, но отправной точкой может служить, своего рода Monkey Chess:
var calculateBestMove = function(game) {
//Генерация всех ходов для данной позиции
var newGameMoves = game.ugly_moves();
return newGameMoves[Math.floor(Math.random() * newGameMoves.length)];
};
2. Оценка позиции
Попробуем вычислить, какая из сторон сильнее в некоторой заданной позиции. Для этого нам понадобится таблица относительной силы фигур. Существуют разные версии этих таблиц, мы остановимся на следующей:
пешка: 10 конь и слон: по 30 ладья: 50 ферзь: 90 король: 900
Сила короля так велика потому, что его надо защищать от шаха ("взятия"). Для чёрных фигур значения силы будут браться с отрицательным знаком, чтобы оценку позиции можно было выразить одним числом, как в реальных "движках", где знак "+" в числе оценки означает перевес белых, а "-" - чёрных.
Теперь имеет смысл изменить метод calculateBestMove так, чтобы он выбирал ход с наивысшей (или с "наинизшей", если для чёрных) оценкой:
var calculateBestMove = function (game) {
var newGameMoves = game.ugly_moves();
var bestMove = null;
//для инициализации переменной используем заведомо малое отрицательное число:
var bestValue = -9999;
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;
};
Предполагается, что метод evaluateBoard возвращает оценку переданной ему позиции, а остальные методы уже есть в подключённых библиотеках.
Единственное преимущество, которого мы пока что достигли - теперь алгоритм съест фигуру, если это возможно.
3. Дерево поиска и минимакс
Оценка позиции зависит не только от того, что сейчас на доске, но и от того, каких преимуществ можно добиться ближайшими ходами или каких опасностей нужно ими избежать.
Для пошаговых игр с нулевой суммой, к которым относятся и шахматы, изобретать велосипед не нужно, ведь давно придуман алгоритм минимакс. Его суть в том, что рекурсивное дерево всех возможных ходов игры исследуется до заданной глубины, а позиция оценивается на "листьях" этого дерева.
После этого функция возвращает либо наименьшее, либо наибольшее значение потомка в родительский узел, в зависимости от того, чей просчитывается ход, то есть, мы стараемся минимизировать или максимизировать результат на каждом уровне.
Для простых игр, вроде крестиков-ноликов, существует полное дерево игры, следовательно, можно реализовать "непобедимый" алгоритм, для шахмат построение такого дерева нереально, но с небольшой глубиной расчета depth в 2-3 хода Javascript вполне справится:
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. Улучшение функции оценки
Первоначальная функция оценки позиции очень примитивна, она просто подсчитывает суммарный вес материала на доске. Чтобы улучшить оценку, нужно учесть положение фигур. Например, конь сильнее в центре доски, чем на её краю, а слон в углу контролирует меньше полей, чем на другом поле.
Для учёта этого позиционного фактора имеются квадратные таблицы (Piece-Square Tables), описанные в Chess Programming Wiki. Скорректировав или подобрав нужные веса, добавим в программу массивы размерностью 8x8 для каждого из типов фигур -
pawnEvalWhite, pawnEvalBlack, bishopEvalWhite и т.д. Функция getPieceValue, возвращающая "силу" фигуры, будет учитывать
её положение как "плюс" или "минус" к базовой силе фигуры:
var getPieceValue = function (piece, x, y) {
if (piece === null) {
return 0;
}
var getAbsoluteValue = function (piece, isWhite, x ,y) {
if (piece.type === 'p') {
return 10 + ( isWhite ? pawnEvalWhite[y][x] : pawnEvalBlack[y][x] );
} else if (piece.type === 'r') {
return 50 + ( isWhite ? rookEvalWhite[y][x] : rookEvalBlack[y][x] );
} else if (piece.type === 'n') {
return 30 + knightEval[y][x];
} else if (piece.type === 'b') {
return 30 + ( isWhite ? bishopEvalWhite[y][x] : bishopEvalBlack[y][x] );
} else if (piece.type === 'q') {
return 90 + evalQueen[y][x];
} else if (piece.type === 'k') {
return 900 + ( isWhite ? kingEvalWhite[y][x] : kingEvalBlack[y][x] );
}
throw "Unknown piece type: " + piece.type;
};
var absoluteValue = getAbsoluteValue(piece, piece.color === 'w', x ,y);
return piece.color === 'w' ? absoluteValue : -absoluteValue;
};
Применив это улучшение, мы получаем код, который играет в шахматы уже чуть сильнее условной "обезьяны", по крайней мере, зевать в один ход не должен. Хотя стратегического видения ситуации, разумеется, алгоритму недостаёт.
Внимательный анализ файла js/script.js из прилагаемого листинга поможет вам понять детали, а нам остаётся написать служебные методы для настройки параметров игры и разметку HTML, которая всё подключит и запустит (файл index.html):
<!DOCTYPE html> <html> <head> <meta charset="windows-1251"> <title>Простой ИИ для шахмат на Javascript</title> <link rel='stylesheet' type="text/css" href='css/style.css'/> </head> <body> <div class="info">Простой ИИ для шахмат. Ваши фигуры - белые<br> </div> <div id="board" class="board"></div> <div class="info"> Глубина поиска: <select id="search-depth"> <option value="1">1</option> <option value="2">2</option> <option value="3" selected>3</option> <option value="4">4</option> <option value="5">5</option> </select> <br> <span>Проверено позиций: <span id="position-count"></span></span> <br> <span>Время: <span id="time"></span></span> <br> <span>Позиций в секунду: <span id="positions-per-s"></span></span> <br> <div id="move-history" class="move-history"></div> <div id="fen" class="fen"></div> </div> <script src="https://code.jquery.com/jquery-1.12.4.min.js"></script> <script src='js/chess.js'></script> <script src='js/chessboard.js'></script> <script src='js/script.js'></script> <noscript>Извините, Javascript отключён или недоступен в вашем браузере</noscript> </body></html>
Увы, Javascript - медленный язык и при глубине расчёта выше 3 скрипт может довольно заметно "тормозить".
Дальнейшие направления развития "движка" могут быть следующими:
- более гибкий выбор ходов - например, при нескольких ходах с близкой оценкой можно брать любой из них;
- улучшение генерации ходов;
- упорядочивание ходов;
- оценка эндшпиля.
Данная статья является вольным переводом и дополнением вот этого первоисточника, там можно почитать несколько меньший текст на английском и посмотреть больше картинок :)
Поиграть с шахматным ИИ на Javascript онлайн
Скачать все исходники скрипта в архиве .zip, папка внутри архива уже создана (53 Кб)
05.10.2017, 14:32 [7928 просмотров]