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

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

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

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

  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) } 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.

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


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

Заключение

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

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

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

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

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Ложные срабатывания в PVS-Studio: как глубока кроличья нора

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

Онлайн контест по решению задачи из теории игр

Привет, Хабр! На факультативе по теории игр мы решаем различные интересные задачи, и я хотел бы поделиться с вами одной из таких. Меня зовут Миша, и я студент. Описание игры «Я люблю вархаммер, поэтому решил адаптировать условие» Играют двое. 1. ...