Мы приступаем к созданию шахматного "искуственного интеллекта" (ИИ). На самом деле это конечно не имеет ничего общего с тем ИИ, который сейчас "в тренде", наш - не про нейросети, не про машинное обучение.
В этой части мы реализуем простейшую оценочную функцию, простой "грубый перебор" ходов, и заодно исправим один забавный баг, который я обнаружил при тестировании.
Общая концепция, алгоритм NegaMax
Как работает грубый перебор ходов? У нас есть какая-то позиция, мы хотим найти "наилучший" ход в этой позиции. Мы берём все возможные ходы для нашей позиции. Для каждой из получившихся позиций мы берём все возможные ходы нашего соперника. Ведь в получившихся позициях уже его очередь хода. Далее, для каждой из получившихся позиций после хода нашего соперника мы берём всевозможные наши ходы, ... и так далее. Данный процесс можно представить в виде дерева вариантов позиций:
На картинке конечно показаны не все варианты ходов, обычно их не 2 - 4 из каждой позиции как на картинке, а несколько десятков. И в идеале конечно дерево не ограничивается четвёртым уровнем вложенности. В идеале мы продолжаем строить дерево до "конечных" позиций, где одной из сторон объявлен мат, или достигнуто состояние ничьи.
Представим, что мы построили дерево игры. Как узнать, какой ход выбрать из нашей начальной позиции, т.е. из вершины дерева?
Оценка листьев дерева
Лист дерева - узел, у которого нет дочерних узлов.
Спустимся по веткам дерева в самый низ, т.е. до какого-то листа дерева. Представим что на нашей картинке мы спустились по самым левым ветвям до уровня 4. На этом уровне у нас ход чёрных. Надо оценить полученную позицию. Т.е. дать ей какую-то числовую характеристику, которая показывает насколько у чёрных тут "хороши дела". Чем лучше позиция для чёрных, тем выше должна быть оценка.
В идеальном случае, когда мы построили полное дерево игры, в рассматриваемой позиции кому-то поставили мат, или достигнута ничья. Если бы это было не так, то из рассматриваемой позиции были бы возможны ещё ходы, т.е. из неё ещё бы шли ветви вариантов, а мы по условию спустились в самый низ. Итак, у нас или мат, или ничья. Напомню, что сейчас мы рассматриваем позицию со стороны чёрных. Если нам, т.е. чёрным, поставлен мат, то такую позицию надо оценить максимально низко, например минус миллион. Если мы поставили мат, т.е. мат белым - то оценим позицию максимально высоко, например миллион. Если ничья, то можно поставить такой позиции оценку ноль.
В реальных условиях, мы не можем построить полное дерево игры. Оно слишком большое, число вариантов позиций растёт экспотенциально, и даже современные компьютеры, с оптимизированными алгоритмами и структурами данных, вряд-ли просчитают полное дерево вариантов даже на 8 полуходов за приемлемое время. Глубину просчёта / дерева придётся ограничивать.
Итак, мы в неполном дереве, рассматриваем позицию в "листе" дерева, и хотим её оценить, но у нас нет мата и нет ничьи. Как сделать оценку позиции? А примерно так-же, как это делают шахматисты в реальной игре. Они учитывают "материальное преимущество", т.е соотношение фигур на доске, занимаемое ими положение, насколько далеко "простреливают" доску дальнобойные фигуры, есть-ли спаренные пешки, проходные пешки, наколько они далеки от последней горизонтали, насколько хорошо защищён король, захвачен ли центр в начальных стадиях игры, ... Функцию, которая в играх оценивает "положение дел" в какой-то позиции, называют оценочной функцией.
В шахматах, в самом простом случае, оценочная функция считает только материальное положение, т.е. преимущество в фигурах (с учётом их ценности). В этой статье мы реализуем как раз такой самый простой вариант.
Движимся по дереву к корню
Итак, у нас в дереве игры теперь оценены "листовые" (конечные) узлы. Как пример, часть дерева игры:
На картинке оценены две листовые позиции для чёрных. Левой позиции присвоена оценка "100", правой "150". Поднимемся от этих узлов к родительскому узлу, т.е. к самой левой на рисунке позиции на уровне 3. Представьте что вы находитесь в этой позиции. В этой позиции - ход белых. У вас есть всего два возможных хода. Какой выбрать?
Если пойдём по самой левой ветке, попадём в позицию которую чёрные оценивают в 100 едениц. Пойдём по правой - у чёрных будет позиция с оценкой 150. Т.е. для чёрных правая позиция выгоднее - у неё выше оценка. И чёрные хотели бы чтобы белые пошли по правому варианту. Но мы-то сейчас выбираем ход за белых. А чем лучше позиция для чёрных, тем она хуже для белых. И наоборот. Поэтому выбрать надо ход, ведущий в позицию с минимальной оценкой - это левый ход.
Итак, мы выбрали левый ход, ведущий в позицию с оценкой 100 для чёрных. И мы можем эту оценку присвоить "текущей" позиции, из которой мы выбираем ходы. Но это оценка "с точки зрения чёрных". А в нашей "текущей" позиции - ход белых. Шахматы - игра двух оппонентов, чем лучше дела у одного, тем хуже у другого. И раз для чёрных позиция оценивается в 100 едениц, то можно считать что для белых оценка позиции - минус 100. И на рисунке, вместо знаков вопроса мы можем вписать оценку позиции для белых - "-100"
Таким образом мы оцениваем все позиции на уровне 3. Т.е. берём минимум из оценок позиций на уровне 4, и записываем противоположное число.
Потом поднимаемся на уровень выше - уровень 2. Там ход чёрных. Они хотят выбрать ход, ведущий в позицию с максимальной для себя оценкой, т.е. в позицию с минимальной оценкой для белых. Берём минимальную оценку на уровне 3 и записываем её с противоположным знаком. Далее - аналогично: оцениваем все позиции на уровне 2, поднимаемся на уровень 1.
В итоге получим дерево игры с оцененными узлами. Как иллюстрация:
На картинке я не стал показывать оценки для веток справа, принцип и так достаточно проиллюстрирован. На всякий случай повторюсь: на картинке указаны оценки для того игрока, чья очередь хода. Т.е. если оценка позиции для чёрных равна "плюс 100", то для белых эта-же позиция оценивается в "минус 100".
Ещё раз. При оценке узла дерева мы хотим взять максимум из "оценок для себя" родительских узлов (позиций). Т.е. минимум из "оценок для противника", взятый с противоположным знаком.
При оценке самой левой позиции на уровне 3 (см. картинку), мы берём оценки дочерних узлов: 100 и 150, берём минимум: 100, и записываем с противоположным знаком.
При оценке самой левой позиции на уровне 2, берём оценки дочерних узлов: -100, -20, 40, -10. Берём минимум: -100. Записываем с противоположным знаком.
При оценке корневой позиции (на уровне 1), берём оценки дочерних узлов: 100, -30, 0. Берём минимум: -30. Записываем с противоположным знаком: 30. И вот мы находимся в корневой позиции. Какой ход нам выбрать? Тот, который ведёт в узел с наибольшей для нас оценкой, т.е. с наименьшей для противника. Этот ход (ветка) выделен на рисунке красным цветом.
Описанный алгоритм называется NegaMax. Этот алгоритм можно считать упрощённым, более "компактном" вариантом алгоритма MiniMax.
Рефакторинг, перенос методов, забавный баг
Нам придётся делать ходы, из получившейся позиции опять делать ходы, и т.д. Вероятно будем делать рекурсивные вызовы методов, передавая в них состояние игры. И хорошо-бы тогда перенести некоторые методы из класса игры, в класс состояния: методы проверки ничьи, проверки атакован ли король, да и метод совершения хода тоже очень завязан на состоянии игры. Итак, открываем файл engine/game_state.php с кодом класса состояния игры.
Добавляем метод определения под атакой ли король, и метод определения ничьи. Просто копируем эти методы из класса ChessGame. Конечно вместо $this->game_state пишем просто $this->, мы же теперь внутри класса GameState. И в метод "под атакой ли король" не нужно передавать цвет текущего игрока, мы и так его знаем внутри класса состояния. Итак, добавляем два метода:
engine/game_state.phppublic function isKingUnderAttack() {
$board_position = new BoardPosition();
$board_position->setPosition($this->position);
return $board_position->isKingUnderAttack($this->current_player_color);
}
// Проверка ничьи по правилам 50-и ходов и троекратного повторения позиции
public function checkDraw() {
if ($this->non_action_semimove_counter >= 100) {
$this->text_state = 'Ничья. Компьютер потребовал ничью по правилу 50 ходов';
return true;
}
if ($this->positionRepeatCount() >= 3) {
$this->text_state = 'Ничья. Компьютер потребовал ничью по правилу троекратного повторения позиции';
return true;
}
return false;
}
Идём теперь в класс игры (в файле engine/chess_game.php), делаем соответствующие изменения:
- Удаляем методы isKingUnderAttack, checkDraw
- Заменяем в двух местах строку if ($this->checkDraw()) { на if ($this->game_state->checkDraw()) {
- Заменяем в двух местах строку
if ($this->isKingUnderAttack($this->game_state->current_player_color)) {
на
if ($this->game_state->isKingUnderAttack()) {
Метод makeMove
В классе игры (ChessGame) есть метод makeMove. В нем создаётся экземпляр класса конкрентной фигуры, и вызывается метод makeMove класса фигуры.
Для удобства перебора позиций, давате сделаем метод makeMove в классе GameState. Там и будем создавать экземпляр класса фигры. А в классе ChessGame делаем изменения:
-
Удаляем строки:
$figure_factory = new FigureFactory(); $figure = $figure_factory->create($this->game_state, $cell_index_from); - Строку if ($figure->makeMove($cell_index_to, $validate_move, $to_figure)) {
заменяем на строку:
if ($this->game_state->makeMove($cell_index_from, $cell_index_to, $validate_move, $to_figure)) {
Теперь идём в класс состояния игры, добавляем там метод makeMove и переносим то, что выкорчевали только что из класса игры:
engine/game_state.phppublic function makeMove($cell_index_from, $cell_index_to, $validate_move=true, $to_figure=FG_QUEEN) {
$figure_factory = new FigureFactory();
$figure = $figure_factory->create($this, $cell_index_from);
if (!$figure->makeMove($cell_index_to, $validate_move, $to_figure)) {
return false;
}
return true;
}
Забавный баг
Немного забегу вперёд. Когда я тестировал уже написанный код, то наткнулся на забавный баг, который не связан с новым кодом. Т.е. этот баг есть и в нескольких предыдущих статьях. Сейчас мы его исправим. Итак, я играю белыми, возникает такая позиция с ходом белых:
В этой позиции я слоном взял ладью (ход Сg7:h8). И знаете как ответили чёрные? Они сделали короткую рокировку!!! Т.е. мой слон изчезает, король двигается на поле g8, и рядом, на поле f8 материализуется ладья, которую я только что съел
Всё оказалось просто и логично. При генерации ходов, когда доходит дело до короля, рассматриваются и возможности сделать рокировку (не забываем - рокировка считается ходом короля). И все условия для рокировки выполняются! Король не под атакой, два поля справа от него свободны, и тоже не под атакой, и, главное - выставлен флаг возможности короткой рокировки (поле enable_castling_black_king в классе состояния игры)!
Когда мы сбрасываем флаг возможности рокировки? Когда король делает любой ход, сбрасываем два флага - для длинной и короткой рокировки. И когда ладья уходит с "начального для неё места" сбрасываем один соответствующий флаг. А в нашей позиции всё было норм - король ещё не двигался, и ладья тоже. А то, что ладьи уже нет, ну это такая мелочь, ну что вы на это вообще обращаете внимание
В итоге, среди ходов-кандидатов оказалась короткая рокировка. Компьютер выбрал этот ход. Помните, как у нас реализована рокировка? Король двигается на два поля в нужном направлении. Соответствующее поле "начальной ладейной позиции" очищается. А рядом с королём ставится ладья. Что и произошло.
Исправить этот баг очень легко. Открываем общий класс фигуры, и в метод makeMove добавляем в самый конец, но перед строкой return true; такой код:
engine/figure.php// если пошли на начальное поле какой-либо ладьи ("съели" например), то надо снять флаг возможности соответствующей рокировки
switch ($to_cell_index) {
case Rook::WHITE_KING_ROOK_INIT_POSITION:
$this->game_state->enable_castling_white_king = false;
break;
case Rook::WHITE_QUEEN_ROOK_INIT_POSITION:
$this->game_state->enable_castling_white_queen = false;
break;
case Rook::BLACK_KING_ROOK_INIT_POSITION:
$this->game_state->enable_castling_black_king = false;
break;
case Rook::BLACK_QUEEN_ROOK_INIT_POSITION:
$this->game_state->enable_castling_black_queen = false;
break;
}
Всё просто: если ход делается на "начальное поле" какой-то из ладей, то снимаем соответствующий флаг возможности рокировки.
Подготовка: "плоский" массив ходов
Вспомним как у нас выглядит результат генератора допустимых ходов. Это ассоциативный массив, где ключи - индексы полей откуда можно совершить ходы. А значения - массивы с индексами полей, куда можно пойти с соответствующего поля. Как пример, допустимые ходы чёрных коней в начальной позиции (вспомните как кодируюся поля доски):
array(
1 => array(16, 18),
6 => array(21, 23)
)Перебирать ходы в таком виде неудобно. Здесь представлены 4 хода, а элемента массива два. Два хода у одного коня, и два у другого. Было бы проще, если бы ходы были в виде "плоского массива". Как пример, для тех-же коней в начальной позиции:
array(
array(1, 16),
array(1, 18),
array(6, 21),
array(6, 23)
)Добавим в генератор ходов метод, который будет возвращать допустимые ходы именно в таком виде:
engine/move_generator.phppublic function generateAllMovesFlat() {
$moves = $this->generateAllMoves();
if (count($moves) === 0) {
return $moves;
}
$flat_moves = array();
foreach($moves as $index_from => $indexes_to) {
foreach($indexes_to as $index_to) {
$flat_moves[] = array($index_from, $index_to);
}
}
return $flat_moves;
}
Тут всё просто - получаем допустимые ходы уже существующим методом, потом проходим по ним вложенным циклом, и просто перекладываем данные в нужном нам виде.
Простейшая оценочная функция
В этой статье напишем самую простую оценочную функцию, которая будет учитывать только "материальную ценность" фигур. Функция оценивает позицию, поэтому думаю, будет логично разместить её в классе состояния игры.
Давайте зададим ценность фигур. Пешка - самая слабая фигура, дадим ей оценку в 10 единиц. Конь и слон обычно оцениваются как три пешки, но коня считают чуть-чуть слабее слона. Дадим слону оценку 30 едениц, коню - 27.
Ладья - 5 пешек, ферзь - 9 пешек, королю дадим оценку в один миллион.
В начало класса GameState, там, где константы, добавим новую константу - массив с ценностю фигур:
engine/game_state.phpconst FIGURE_VALUES = array(
FG_KING => 1000000,
FG_QUEEN => 90,
FG_ROOK => 50,
FG_BISHOP => 30,
FG_KNIGHT => 27,
FG_PAWN => 10
);
Оценочной функции достаточно иметь только саму позицию для её оценки. Но сначала ей надо определить - есть ли сейчас ситуация мата или пата. Для этого надо определить - есть ли допустимые ходы из позиции. Но мы будем вызывать оценочную функцию из места, где уже есть список допустимых ходов (это я уже постфактум говорю, вначале я писал сам перебор ходов). Поэтому давайте будем передавать в оценочную функцию аргумент - факт отсутствия допустимых ходов (назовём аргумент $no_available_moves)
Итак, в класс состояния игры добавляем метод - оценочную функцию:
engine/game_state.phppublic function calcStaticScore($no_available_moves) {
if ($no_available_moves) {
if ($this->isKingUnderAttack()) {
return PHP_INT_MIN;
} else {
return 0;
}
}
// Проверяем ничью по повторам и неактивности
if ($this->checkDraw()) {
return 0;
}
$score = 0;
for($i = 0; $i < BOARD_SIZE*BOARD_SIZE; $i++) {
$figure_code = $this->position[$i];
if ($figure_code !== FG_NONE) {
$figure = Functions::figureType($figure_code);
$color = Functions::color($figure_code);
if ($color == $this->current_player_color) {
$score += self::FIGURE_VALUES[$figure];
} else {
$score -= self::FIGURE_VALUES[$figure];
}
}
}
return $score;
}
В строках 2 - 8 обрабатывается случай, когда нет допустимых ходов. Если наш король под атакой (строка 3), значит ситуация максимально плоха, возвращаем PHP_INT_MIN - минимальное возможное число. Иначе, т.е. король не под атакой, т.е. у нас пат, ничья, возвращаем ноль.
Под словом "наш" здесь имеется ввиду тот цвет, чья очередь хода сейчас в текущей позиции. Оценочная функция будет вызываться и для белых, и для чёрных, её задача - дать оценку позиции для "текущего игрока".
В строке 10 проверяем, не возникла ли ситуация ничьей, и если возникла, возвращаем ноль.
В строке 14 заводим переменную $score, в которой будем накапливать оценку позиции,записываем туда ноль.
Далее, проходим в цикле по всем клеткам доски. Для каждой клетки получаем код фигуры (строка 16). Если клетка не пустая, то выделяем из кода фигуры саму фигуру (вид фигуры), и её цвет (строки 18, 19)
По виду фигуры (пешка, конь, ... король) мы можем получить её ценность из константы-массива FIGURE_VALUES. Если фигура "нашего" цвета, т.е. цвета текущего игрока (строка 20), то мы прибавляем ценность фигуры к нашей оценке позиции (строка 21), иначе - берём её со знаком минус, т.е. отнимаем (строка 23)
Всё! Прошли по доске, сложили ценности фигур, полученную оценку возвращаем в строке 27
Новый класс шахматного ИИ
Как работал старый ИИ
Вспомним, как мы получали ход компьютера. В классе ChessGame есть метод makeComputerMove. В нём мы создавали экземпляр класса "компьютерного искуственного интеллекта" - ComputerAI. В конструктор класса мы передавали состояние игры - переменную, экземпляр класса GameState. И вызывали метод getGeneratedMove:
engine/chess_game.php$ai = new ComputerAI($this->game_state);
$move = $ai->getGenerateMove();
Можно оставить тут всё как есть, пойти в класс ComputerAI и уже там изменять логику. А сейчас там, напомню, генерируются все возможные ходы, и из них случайно выбирается один. Но я решил оставить этот "случайный ИИ" нетронутым, и рядом завести ещё один. Может позже на странице сделаем "переключалку", чтобы можно было выбрать с каким ИИ сразиться. Кстати, со случайным ИИ довольно просто тестировать разные ситуации. Легко заставить противника сделать то, что тебе надо, например провести его пешку в ферзи, или заставить его поставить тебе мат.
Итак, будем создавать ещё один класс шахматного ИИ, "AI версия 1". Сразу сделаем всё необходимое в классе игры, чтобы сюда не возвращаться. Итак, в начале класса ChessGame, там, где подключаются разные файлы, добавим ещё одно подключение:
engine/chess_game.phprequire_once('computer_ai_v1.php');
Да, такого файла ещё нет, но мы его скоро создадим. И в вышеупомянутой строке
engine/chess_game.php$ai = new ComputerAI($this->game_state);
заменяем имя класса, просто добавляем "V1":
engine/chess_game.php$ai = new ComputerAIV1($this->game_state);
Пишем новый ИИ
Итак, создаём новый файлик engine/computer_ai_v1.php. Я сразу напишу его полный текст:
engine/computer_ai_v1.php<?php
class ComputerAIV1 {
protected $search_depth = 0;
protected GameState $game_state;
private $position_counter = 0;
public function __construct(GameState $game_state, $search_depth = 3) {
$this->game_state = $game_state;
$this->search_depth = max($search_depth, 1);
}
public function getGenerateMove() {
$search_best_move_result = $this->searchBestMove($this->game_state, $this->search_depth);
// error_log('Оценено позиций: '.$this->position_counter.' Score='.$search_best_move_result['score']."\r\n", 3, 'log.txt');
$move = $search_best_move_result['best_move'];
if (!$move) {
return false;
}
return array('from' => $move[0], 'to' => $move[1]);
}
/**
* Метод ищет "лучший ход" и возвращает оценку позиции
* $game_state - позиция, для которой ищется лучший ход
* $depth - глубина, на которую надо делать перебор позиций
* Возвращается массив с двумя ключами:
* score - оценка позиции
* best_move - найденный "лучший ход" (массив с двумя элементами - индексы полей "откуда" и "куда") или null
*/
private function searchBestMove(GameState $game_state, $depth) {
$move_generator = new MoveGenerator($game_state);
$available_moves = $move_generator->generateAllMovesFlat();
$no_available_moves = (count($available_moves) === 0);
if ($depth === 0 || $no_available_moves) {
$this->position_counter += 1;
return array('score' => $game_state->calcStaticScore($no_available_moves), 'best_move' => null);
}
$score = PHP_INT_MIN;
$best_move = reset($available_moves);
foreach ($available_moves as $move) {
$cell_from = $move[0];
$cell_to = $move[1];
$next_game_state = clone $game_state;
$next_game_state->makeMove($cell_from, $cell_to, false);
$search_best_move_result = $this->searchBestMove($next_game_state, $depth-1);
$tmp_score = - $search_best_move_result['score'];
if ($tmp_score > $score) {
$score = $tmp_score;
$best_move = $move;
}
}
return array('score' => $score, 'best_move' => $best_move);
}
}
В начале класса объявляем три поля. $search_depth - здесь будет глубина просмотра дерева, на сколько уровней вниз будем спускаться при переборе позиций. Т.е., на сколько полуходов "вперёд" будем смотреть.
$game_state - здесь будет состояние игры, т.е. экземпляр класса GameState
$position_counter - счётчик оцененных позиций. Это ненужное для функционирования поле, я его ввёл "из интереса", чтобы при отладке знать, сколько позиций оценено, чтобы можно было посчитать примерную скорость перебора позиций. Учитываться тут будут только позиции в листьях дерева, т.е. только те, для которых вызывается оценочная функция.
Конструктор
Конструктор класса (строки 8 - 11) принимает два параметра - состояние игры, для которого надо найти "лучший" ход, и глубину просмотра. Глубина просмотра ($search_depth) - необязательный параметр, по умолчанию равен трём. Т.е. по умолчанию компьютер "смотрит" вперёд всего на полтора хода (3 полухода). Переданные параметры присваиваются полям класса. Для глубины просмотра берётся максимум от единицы и переданного значения. Такая простенькая защита от случайной передачи отрицательного или нулевого значения.
getGenerateMove
Метод getGenerateMove вызывается "внешним" кодом, и, как и метод предыдущего "случайного ИИ", он должен возвращать ассоциативный массив с ключами "from" и "to" - индексы полей "откуда" пошли, и "куда". А если ход нельзя найти (мат или пат), то возвращается false.
В строке 14 вызывается основной метод класса - searchBestMove. Он принимает состояние игры, и глубину просмотра, на которую надо строить дерево игры. Возвращать метод должен ассоциативный массив с двумя ключами - оценка позиции, и "лучший ход". На примере:
array(
'score' => 25, // оценка позиции
'best_move' => [57, 42] // найденный "лучший" ход - индексы полей "откуда", "куда", или null
)Как метод это будет делать - чуть ниже. Итак, мы вызвали этот волшебный метод в строке 14 и записали результат в переменную $search_best_move_result. Строка 15 в коде закомментирована, она писала в файл количество оцененных позиций, и полученную оценку исходной позиции. Можете раскомментировать строку, посмотреть какие оценки получают позиции во время игры.
В строке 16 записываем "лучший ход" в отдельную переменную, и дальше просто возвращаем данные в нужном формате - false, если хода нет, или ассоциативный массив с ключами from, to - индексы полей "откуда", "куда"
searchBestMove
Мы добрались до "сердца" нашего ИИ, или, наверное логичнее было бы сказать "головы". Что делает метод searchBestMove уже писал чуть выше, да и в коде это написано - в комментарии в строках 23 - 30. Теперь опишу, как он это делает.
В строках 32, 33 создаём как обычно экземпляр класса генератора ходов, и получаем все допустимые ходы в виде "плоского" массива. Напомню вид этого массива на примере:
array(
array(1, 16),
array(1, 18),
array(6, 21),
array(6, 23)
)В строке 34 в переменную $no_available_moves записывем флаг отсутствия допустимых ходов. Т.е. если в массиве допустимых ходов ноль элементов, то в $no_available_moves запишется true, иначе - false.
Что делать дальше? Если допустимых ходов нет, то уже ничего не поделать, надо оценить позицию, и возвращать из метода результат. Если глубина перебора равна нулю, т.е. если в метод передали $depth = 0, то получается нам "сказали": "перебирать варианты вообще не нужно". В этом случае тоже надо просто оценить позицию и вернуть результат.
Эти проверки мы делаем в строке 35 - "если требуемая глубина просмотра равна нулю, или нет допустимых ходов". В строке 36 мы увеличиваем счётчик оцененных позиций, это необязательная строка, для функционирования ИИ она не нужна. И в строке 37 возвращаем результат в ожидаемом виде. Т.е. в виде ассоциативного массива с двумя ключами:
-
score - оценка позиции. Чтобы её получить, мы вызываем нашу "оценочную функцию":
$game_state->calcStaticScore($no_available_moves) - best_move - найденный лучший ход. Поскольку в данной ветке кода у нас или вообще нет допустимых ходов или нас просили не перебирать позиции ($depth === 0), т.е. не искать этот "лучший ход", то здесь мы пишем null
Итак, мы дошли до строки 40. Здесь мы заводим переменную $score, в ней будем хранить текущую оценку позиции. Сразу пишем туда PHP_INT_MIN - минимально возможное в текущей версии PHP целое число. Наша задача - найти позицию с максимальной оценкой. В процессе перебора, как только найдём оценку больше $score, будем обновлять эту переменную.
В строке 41 заводим переменную $best_move. Сюда будем писать найденный лучший ход. Пока пишем сюда первый элемент из массива допустимых ходов.
Мы уже далеко ушли от самого кода, давайте я здесь повторю его часть, внутренность метода searchBestMove, начиная с объявления переменой $score:
engine/computer_ai_v1.php$score = PHP_INT_MIN;
$best_move = reset($available_moves);
foreach ($available_moves as $move) {
$cell_from = $move[0];
$cell_to = $move[1];
$next_game_state = clone $game_state;
$next_game_state->makeMove($cell_from, $cell_to, false);
$search_best_move_result = $this->searchBestMove($next_game_state, $depth-1);
$tmp_score = - $search_best_move_result['score'];
if ($tmp_score > $score) {
$score = $tmp_score;
$best_move = $move;
}
}
return array('score' => $score, 'best_move' => $best_move);
Здесь строка 1 - это строка 40 из предыдущего полного кода. Далше при описании буду пользоваться "новой нумерацией"
Итак, мы дошли до строки 3. В ней делаем цикл - проходим по всем допустимым ходам из текущей позиции.
В строках 4, 5 раскладываем компоненты хода по переменным $cell_from, $cell_to (индексам полей "откуда" делается ход, и "куда")
Далее, нам надо "сделать" этот ход. Но текущее состояние игры надо сохранить, чтобы потом из него делать другие ходы. В строке 6 мы клонируем текущее состояние игры в переменную $next_game_state, и в следующей строке делаем ход в новом состоянии игры, не затрагивая исходное:
$next_game_state->makeMove($cell_from, $cell_to, false);Третий параметр в методе makeMove - флаг $validate_move - проверять ли допустимость хода. Так как мы получили ход из нашего собственного генератора, не из "внешнего мира", то мы "доверяем" ему, и проверки нам не требуется, поэтому передаём false
Итак, мы сделали ход в игре $next_game_state, теперь нам надо оценить возникшую там позицию. Как? А у нас-же есть метод для оценки состояния игры! Это метод searchBestMove, который мы сейчас и рассматриваем. Можно из метода вызвать самого себя, старая добрая рекурсия. Делаем такой рекурсивный вызов в строке 8, передавая туда новое состояние игры, с уже сделанным ходом, и уменьшая требуемую глубину перебора на единицу:
$search_best_move_result = $this->searchBestMove($next_game_state, $depth-1);К примеру, мы вызвали метод searchBestMove с глубиной перебора 4 полухода. В нём мы делаем ходы, и полученные позиции надо просмотреть уже не на 4 полухода, а на три. Мы вызывем опять этот-же метод, говорим ему - сделай перебор позиций на глубину 3 полухода. В методе делаются ходы, получаются позиции, которые надо просмотреть уже на два полухода, и так далее. Когда мы вызываем метод с требуемой глубиной, равной нулю, то из переданной позиции уже не делаются ходы, а вызывается оценочная функция, и возвращается результат, рекурсия прерывается.
Итак, в строке 8 мы сделали рекурсивный вызов, и записали результат в переменную $search_best_move_result. Напомню на примере, как выглядит результат:
array(
'score' => 25, // оценка позиции
'best_move' => [57, 42] // найденный "лучший" ход - индексы полей "откуда", "куда", или null
)В строке 9 берём из этого результата оценку позиции с противоположным знаком, и сохраняем в переменную $tmp_score. Почему с противоположным знаком? Мы в методе ищем оценку позиции в состоянии $game_state для того игрока, который является "текущем" в этом состоянии. А после того, как мы сделали ход, мы вызываем метод для оценки позиции в состоянии $next_game_state, в котором очередь хода уже другого игрока. И в строке 8 мы получаем результат (оценку позиции и "лучший ход") уже для другого игрока. А значит оценка позиции для "нас" в состоянии $game_state будет противоположной.
Итак, в строке 9 мы записали в переменную $tmp_score нашу оценку позиции, возникшей после хода $move. Если эта оценка больше, чем $score ("текущая лучшая оценка"), значит мы нашли ход, который лучше $best_move (текущий "лучший ход"). В этом случае в переменную $score записываем новое найденное лучшее значение оценки позиции, и в переменную $best_move - ход, ведущий в позицию с этой новой "лучшей оценкой". Это всё происходит в строках 10-13
Всё, цикл закончен, мы прошли сделали все возможные ходы из текущей позиции, и оценили рекурсивно все возникающие после этого хода позиции. На строке 15 возвращаем ассоциативный массив с найденными лучшей оценкой и лучшим ходом.
Немного статистики
Уже можно играть! Теперь компьютер не зевает фигуры, избегает простых угроз, и иногда находит довольно неожиданно сильные ходы. Ну это на мой взгляд "сильные", я не так уж хорошо играю в шахматы.
Компьютер сейчас просматривает дерево игры всего на 3 полухода вглубь, т.е. всего на полтора хода. Можно конечно запрашивать просмотр на глубину 4 полухода, простым указанием параметра $search_depth при поздании экземпляра класса "компьютерного ИИ":
engine/chess_game.php$ai = new ComputerAIV1($this->game_state, 4);
Или на глубину 5, 6, 7, 10 полуходов... Но уже при глубине 4 время ответа слишком велико. Вы не заходите играть с таким "тормознутым" ИИ. Поэтому я поставил глубину 3 как значение по умолчанию. С такой глубиной вполне можно играть.
Скорость перебора у меня была примерно 2000 оцененных позиций в секунду. В начальной стадии игры компьютру требовалось около 10 секунд на ответ, при этом рассматривалось около 20 тыс. позиций. В средних стадиях, когда фигур ещё много, оценивается около 40-50 тысяч позиций.
Потом мне попалась позиция, когда компьютер не смог ответить за 30 секунд - время отведённое по умолчанию на работу php-скрипта. Пришлось увеличить допустимое время. Идём в файл make_computer_move.php и, например после строки с загрузкой игры, увеличиваем лимит времени до 45 секунд:
make_computer_move.phpset_time_limit(45);
После этого я смог получить ответ и в той "проблемной" позиции. В ней было оценено более 60 тысяч позиций.
Итоги
Теперь компьютер отвечает не мгновенно, зато играть с ним становится интереснее. Он уже "огрызается", не зевает, и способен заставить задуматься неопытных игроков. В следующих частях мы улучшим ИИ. А сейчас можно попробовать поиграть: Демо №14 игры
исходные коды проекта на github.
P.S. На сайте ИИ, по ощущениям, отвечает быстрее, чем на локально на моём компьютере.