Продолжаем писать "шахматный ИИ". В этой части мы сильно сократим количество оцениваемых позиций, что позволит за приемлемое время просмативать деверо игры на бОльшую глубину, чем ранее.
Объяснение алгоритма альфа-бета отсечения на примере
Алгоритм альфа-бета отсечения - основной алгоритм оптимизации перебора в играх. Его суть в том, что для получения оценки позиции такой же точности, как и при полном переборе, не обязательно просматривать все варианты.
Давайте рассмотрим идею этого алгоритма на примере. Рассмотрим такое дерево игры:
Здесь мы уже спустились по левым веткам до позиции №3, оценили позиции №4 и №5 (-10 и +25 для чёрных, т.е. +10 и -25 для белых). В позиции №3 белые максимизируют свою оценку, т.е. позиция №3 получет оценку +10.
Теперь рассматриваем следующий ход, ведущий из позиции №2 в позицию №6. Из позиции №6 рассматриваем ход в позицию №7, и например мы получили для позиции №7 оценку -50 для чёрных, т.е. +50 для белых.
Т.е. белые, находясь в позиции №6, могут выбрать ход, ведущий в позицию №7, у которой оценка +50. Какие-бы оценки не получили другие позиции, полученные ходом из позиции №6, у белых есть "гарантированный минимум" оценки - +50. А белые хотят максимизировать оценку. Т.е. оценка позиции №6 будет +50 или выше.
Теперь посмотрим на позицию №2. В ней чёрные масимизируют свою оценку, или, по другому - минимизируют оценку для белых. Из позиции №2 есть два хода. Выбрав ход ведущий в позицию №3, чёрные получат позицию с оценкой +10 для белых. А выбрав ход, ведущий в позицию №6, они получат позицию с оценкой для белых "+50 или выше". А чёрным надо минимизировать оценку для белых. Т.е. они точно не пойдут в позицию №6.
Значит можно даже не рассматривать другие ходы из позиции №6. На картинке красным крестом перечёркнуты позиции, которые не нужно рассматривать. Мы "отсекли" их гарантированным минимумум для чёрных. Таким образом, позиции №6 можно присвоить оценку 50 без ущерба для игры. А позиция №2 получает оценку -10.
Немного повторюсь… В позиции №2, после оценки левой ветки, у чёрных есть гарантированный минимум оценки: -10. На более низкую оценку они уже не согласятся, они всегда могут выбрать ход, ведущий в позицию №3, у которой оценка -10 (+10 для белых). В свою очередь, у белых в позиции №1 есть гарантированный минимум оценки: 10. Они могут пойти в позицию №2, и получить позицию с оценкой 10. Оценка хода, ведущего из позиции №1 направо, может только улучшить оценку для белых.
Теперь пойдём из позиции №1 направо, спустимся по левым веткам, и, например, мы получим такие оценки:
Т.е., оценочкая функция дала оценки 20 и 25 для чёрных в позициях №10 и №11. Значит позиция №9 получит оценку -20 (минимум из оценок 20 и 25 для чёрных, взятый с противоположным знаком).
Посмотрим на позицию №8. Здесь ход чёрных. Они могут выбрать ход, ведущий в позицию №9 и получить оценку +20 для себя (-20 для белых). Рассмотрение остальных ходов, ведущих из позиции №8 может только улучшить оценку для чёрных, они уже не согласятся делать ход в позицию с оценкой меньше чем 20.
Это значит, что для белых оценка позиции №8 будет или -20, или ещё меньше (хуже). Но тогда зачем белым делать ход из позиции №1 в позицию №8 с оценкой "-20 или хуже", если они могут сделать ход в позицию №2 с оценкой -10? У них уже гарантирован этот минимум: -10, и они не пойдут в позицию №8, так как там дела для них будут хуже.
Таким образом, получается что остальные ходы из позиции №8 можно не рассматривать. На рисунке перечёркнуты позиции, которые были "отсечены", которые не пришлось рассматривать.
Ещё раз, идея алгоритма альфа-бета отсечения
При оценке позиции, просматривая варианты, мы теперь заведём две переменные - "гарантированный минимум" для белых и для чёрных. В самом начале, обе эти величины будут равны минимально возможным значениям: PHP_INT_MIN (ну ладно, не обязательно конечно именно столько, можно взять минус миллион для нашей игры).
При оценке позиций мы будем увеличивать этот "гарантированный минимум" для обеих сторон. Если в какой-то позиции игрок получил гарантированный минимум, равный например 10, то для его оппонента "минус 10" будет максимумом его оценки. В свою очередь, гарантированный минимум оппонента, взятый с противоположным знаком будет нашим возможным максимумом. Наш гарантированный минимум обозначают греческой буквой "альфа" α, наш возможный максимум - буквой "бета" β. Если, в процессе перебора вариантов, альфа сравняется с бетой, то перебор можно прекращать.
Наша альфа равна минус бета оппонента. И наша бета равна минус альфа оппонента.
Важность порядка ходов
Алгоритм альфа-бета очень чувствителен к порядку рассмотрения ходов. В самом худшем случае, когда не будет отсечений, он просмотрит столько-же позиций, как и при полном переборе. При хорошем порядке ходов, альфа-бета построит значительно меньшее дерево. Можно считать, что будет рассмотрено количество позиций, равное примерно крадратному корню из количества позиций при полном переборе. Т.е., например если при полном переборе рассматривается 10 000 позиций, то при альфа-бета отсечении, при "хорошем" порядке рассмотрения ходов, будет рассмотрено всего примерно 100 позиций.
Чем раньше мы рассмотрим ход, дающий улучшение оценки позиции, тем больше веток дерева сможем отсечь. А какие ходы сильнее влияют на оценку позиции? В нашей оценочной функции сейчас учитывается только материальная ценность фигур. Значит сильнее всего на оценку влияют ходы-взятия. Сегодня, помимо реализации алгоритма альфа-бета отсечения, мы сделаем сортировку ходов. Но начнём, как обычно, с исправления замеченных багов.
Компьютер не видит ничьи при повторах: исправляем
Когда я тестировал программу с уже добавленным альфа-бета отсечением, и глубиной просмотра 4 полухода, заметил такую странность… Компьютер получил значительное преимущество - у меня остался один король, у компьютера - ладья, конь и пешка. Компьютер стал ходить ладьёй "туда-сюда", повторять ходы. Я тоже стал повторять ходы королем. И после третьего повторения компьютер объявил ничью!
То, что ладья ходила "туда-сюда", "просто так", это объяснимо: сейчас при оценке позиции, (когда не мат и не состояние ничьи), учитывается только материальная ценность фигур. Такая у нас сейчас оценочная функция. На глубине своего просмотра (4 полухода) алгоримт мат не нашёл. Значит любой ход, после которого мой король не съест фигуру компьютера, будет одинаковым для результата с точки зрения алгоритма. С этим всё понятно.
Но почему компьютер не избегает повторения позиции? Ведь после трёх повторов будет ничья. Оценочная функция для ничьи вернёт оценку - ноль. А зачем компьютеру ноль, если у него преимущество в фигурах? Любая позиция без ничьи даёт для компьютера положительную оценку (сумма стоимостей ладьи, коня и пешки), это больше нуля. Т.е. компьютер должен избегать троекратного повтора позиций. А он стабильно повторял ходы, и давал мне дойти до ничьи.
Разгада оказалась, как обычно, проста. Где у нас обновлялся счётчик повторов позиций? В методе savePositionHash класса GameState. А где у нас вызывался этот метод? В классе ChessGame в методе makeMove после успешного вызова метода makeMove объекта состояния игры.
Наш "искуственный интеллект" не пользуется классом ChessGame. Он делает ходы, вызывая метод makeMove на состоянии игры. Так что при "просчёте ходов" нашим ИИ, счётчик повторов просто не обновлялся. Вот и вся разгадка.
Обновление счётчика повторов само просится перенестись в метод makeMove класса состояния игры. Итак, открываем класс ChessGame (файл engine/chess_game.php), удаляем там строку:
$this->game_state->savePositionHash();Открываем файл engine/game_state.php с классом состояния игры, ищем там метод makeMove, и в самом конце, перед return true; добавляем:
$this->savePositionHash();Всё! После этого компьютер стал избегать троекратных повторов. Мат одинокому королю с центра доски компьютер пока ставить умеет, это сейчас за пределами его "горизонта событий". Этим мы займёмся позже.
Чуть-чуть рефакторинга
Пока у нас открыт файл engine/game_state.php, заодно сразу добавим метод, который понадобится, чтобы не повторять один и тот-же кусок кода. А именно - добавим метод, определяющий позицию короля, по его цвету. Добавляем метод:
engine/game_state.phppublic function getKingPosition($color) {
$king_positions = $this->figures[FG_KING + $color];
if (count($king_positions) === 0) {
throw new Exception('Not found king');
}
return $king_positions[0];
}
И ещё одна мелкая правка. В контроллере make_move.php мы получаем индексы полей "откуда" и "куда" делается ход. Индексы полей - числа, а мы берём значения из POST-параметров, это строки. Пока это не мешало нам. Но в этой части, при тестировании, выявился баг из за этого. Для исправления достаточно явно привести полученные данные к числу, например функцией intval. Т.е. строки
$cell_index_from = $_POST['cell_index_from'];
$cell_index_to = $_POST['cell_index_to'];изменить так:
$cell_index_from = intval($_POST['cell_index_from']);
$cell_index_to = intval($_POST['cell_index_to']);Изменяем структуру информации о ходе
Займёмся сортировкой ходов.
Сейчас информация о ходе у нас представляет собой числовой массив из двух элементов - индексы полей "откуда" и "куда". Чтобы удобно сортировать ходы, дополним эту "структуру" ещё двумя числами:
- "вес" фигуры, которая ходит
- "вес" фигуры, которую берут
Идея с "весами" такая: чем более ценную фигуру мы берём, тем потенциально более лучшую позицию мы получим. Взять ферзя обычно лучше, чем взять пешку, верно? Поэтому лучше сначала рассмотреть взятия более "тяжёлых" фигур.
Если ход не является взятием, то аналогично, ход более тяжёлой фигурой обычно приводит к более сильному улучшению ценности позиции (пусть и не сразу). В начальной стадии партии это конечно не так, но пока опустим эту деталь.
Общий класс фигуры
Итак, нам надо добавить дполнительную информацию при генерации ходов. Открываем общий класс фигуры (файл engine/figure.php), и в самое начало класса добавляем "веса" фигур:
const FIGURE_WEIGHTS = array(
FG_KING => 2,
FG_QUEEN => 6,
FG_ROOK => 5,
FG_BISHOP => 4,
FG_KNIGHT => 3,
FG_PAWN => 1,
FG_NONE => 0
);Тут мы указываем, что хотим рассматривать ходы сначала ферзя, потом ладьи, слона, коня, затем - короля, и за ним - пешки.
Добавляем поле класса:
protected int $figure_weight; // "вес" фигуры, для которой создан экземпляр классаИ добавляем в конструктор строку, заполняющую это новое поле класса:
$this->figure_weight = self::FIGURE_WEIGHTS[ Functions::figureType($this->figure) ];Теперь идём в метод getAvailableMoves. Приведу полный код метода, потом напишу что там поменялось:
engine/figure.phppublic function getAvailableMoves() {
/**
* допустимые ходы - числовой массив, элементы которого - числовые массивы с такой структурой (индекс - информация):
* 0 - индекс поля "откуда"
* 1 - индекс поля "куда"
* 2 - вес фигуры, которая ходит
* 3 - вес фигуры, которую берут
*/
$moves = array();
$board_position = new BoardPosition();
$our_king_position = $this->game_state->getKingPosition($this->color);
$candidate_moves = $this->getCandidateMoves();
foreach($candidate_moves as $to_index) {
$to_position = $this->game_state->position; // копируем позицию
$to_position[$this->position_index] = FG_NONE; // убираем фигуру из текущей позиции
$beat_figure = $to_position[$to_index];
$beat_figure_weight = self::FIGURE_WEIGHTS[ Functions::figureType($beat_figure) ];
$to_position[$to_index] = $this->figure; // перемещаем фигуру на выбранное поле. Если на том поле что-то стояло - оно "убирается"
$board_position->setPosition($to_position);
if ($board_position->isFieldUnderAttack($our_king_position, $this->enemy_color)) {
// ход недопустим, т.к. после него наш король оказывается под атакой
continue;
}
$moves[] = array($this->position_index, $to_index, $this->figure_weight, $beat_figure_weight);
}
return $moves;
}
Во первых, в начало метода я добавил комментарий - описание структуры результата метода. Во вторых, строка 11 заменила собой 6 строк старого кода, где определялась позиция нашего короля. Теперь мы просто вызываем метод getKingPosition состояния игры. Этот метод мы добавили чуть выше, под заголовком "Чуть-чуть рефакторинга".
Строки 17, 18 - новые. Там мы определяем фигуру, которая стоит на поле "куда", т.е. фигуру, которая бьётся. И определяем её "вес".
И изменена строка 25, в которой мы добавляем ход "в новом формате" в результирующий массив с ходами.
И, раз у нас изменился формат представления хода, надо изменить все места, где эти ходы обрабатываются.
В этом-же классе (общий класс фигуры), у нас есть метод makeMove, в начале которого проверяется допустимость хода, который этот метод должен совершить:
if ($validate_move) {
$available_moves = $this->getAvailableMoves();
if (!in_array($to_cell_index, $available_moves)) {
$this->game_state->text_state = 'Недопустимый ход. Сделайте корректный ход';
return false;
}
}Тут мы берём допустимые ходы фигуры, и проверяем - находится-ли индекс поля куда надо пойти, в массиве допустимых ходов. Но мы изменили структуру хода, и теперь этот код заменим на такой:
if ($validate_move && !$this->isValidMove($to_cell_index)) {
$this->game_state->text_state = 'Недопустимый ход. Сделайте корректный ход';
return false;
}Т.е. мы тут заменили всю "логику" на вызов нового метода isValidMove. Добавим этот метод:
protected function isValidMove($to_cell_index) {
$available_moves = $this->getAvailableMoves();
foreach($available_moves as $move) {
if ($to_cell_index === $move[1]) {
return true;
}
}
return false;
}Здесь мы получаем возможные ходы фигуры, проходим по ним в цикле, и как только встретим в них проверемый индекс поля "куда", возвращаем true. Т.е. ход фигурой на это поле действительно возможен. Если цикл полностью пройден, значит мы не встретили в "возможных ходах" фигуры проверяемое поле. Возвращаем false.
Класс короля
Вспомните - помимо общего класса фигуры, у нас есть классы конкретных фигур, где перекрываются некоторые методы из за особенностей хода конкретной фигуры. Запись возвращаемых ходов у нас перекрывается только у короля и у пешки.
Начнём с класса короля, который описан в файле engine/figures/king.php. Нужно изменить метод getAvailableMoves. Приведу его полностью:
engine/figures/king.phppublic function getAvailableMoves() {
$moves = array();
$this->board_position = new BoardPosition();
$king_figure_weight = self::FIGURE_WEIGHTS[FG_KING];
// проверим "обычные" перемещения
$candidate_moves = $this->getCandidateMoves();
foreach($candidate_moves as $to_index) {
$to_position = $this->game_state->position; // копируем позицию
$beat_figure = $to_position[$to_index];
$to_position[$this->position_index] = FG_NONE; // убираем фигуру из текущей позиции
$to_position[$to_index] = $this->figure;
$this->board_position->setPosition($to_position);
if ($this->board_position->isFieldUnderAttack($to_index, $this->enemy_color)) {
// ход недопустим, т.к. после него наш король оказывается под атакой
continue;
}
$moves[] = $to_index;
$beat_figure_weight = self::FIGURE_WEIGHTS[ Functions::figureType($beat_figure) ];
$moves[] = array($this->position_index, $to_index, $king_figure_weight, $beat_figure_weight);
}
// теперь проверим возможность рокировок
$none_figure_weight = self::FIGURE_WEIGHTS[FG_NONE];
$castling_weight = self::FIGURE_WEIGHTS[FG_KING] + self::FIGURE_WEIGHTS[FG_ROOK];
$this->board_position->setPosition($this->game_state->position);
if ($this->color == COLOR_WHITE) {
if ($this->game_state->enable_castling_white_king && $this->checkCastlingConditions(self::FIELD_INIT_WHITE, self::FIELDS_CASTLING_WHITE_KING)) {
$moves[] = array($this->position_index, self::FIELDS_CASTLING_WHITE_KING[1], $castling_weight, $none_figure_weight);
}
if ($this->game_state->enable_castling_white_queen && $this->checkCastlingConditions(self::FIELD_INIT_WHITE, self::FIELDS_CASTLING_WHITE_QUEEN)) {
$moves[] = array($this->position_index, self::FIELDS_CASTLING_WHITE_QUEEN[1], $castling_weight, $none_figure_weight);
}
} else {
if ($this->game_state->enable_castling_black_king && $this->checkCastlingConditions(self::FIELD_INIT_BLACK, self::FIELDS_CASTLING_BLACK_KING)) {
$moves[] = array($this->position_index, self::FIELDS_CASTLING_BLACK_KING[1], $castling_weight, $none_figure_weight);
}
if ($this->game_state->enable_castling_black_queen && $this->checkCastlingConditions(self::FIELD_INIT_BLACK, self::FIELDS_CASTLING_BLACK_QUEEN)) {
$moves[] = array($this->position_index, self::FIELDS_CASTLING_BLACK_QUEEN[1], $castling_weight, $none_figure_weight);
}
}
return $moves;
}
Зелёным фоном подсвечены новые или изменённые строки. Красным - удалённые. Т.е. строки номер 18 в коде быть не должно.
В строке 4 в отдельную переменную запоминаем "вес" короля, чтобы каждый раз не обращаться к массиву.
В строке 10 записываем в переменную $beat_figure код фигуры, которая бьётся (в частности может быть пустое поле - FG_NONE). В строке 19 записываем в переменую вес фигуры, которая бьётся.
И в строке 20 (которая заменила строку 18) записываем ход в новом формате в результирующий массив ходов. Мы закончили с "простыми перемещениями" короля, далее идёт бработка рокировок.
В строке 24 записываем в переменную вес "пустой фигуры/поля", это значение нам понадобится при записи хода как "вес фигуры которую берут". И нам ещё нужен вес фигуры, которая ходит. Я решил поднять "вес рокировки", и в строке 25 записал в переменную $castling_weight сумму весов короля и ладьи. Значение этой переменной будем подставлять как в ход, как "вес фигуры, которая ходит". Таким образом мы будем рассматривать оценивать рокировки даже раньше, чем ход ферзём. (Вес ферзя - 6, вес короля + вес ладьи = 2 + 5 = 7)
В строках 29, 32, 36, 39 записываем ход-рокировку в результирующий массив ходов. Эти строки различаются только вторым элементом массива (с индексом 1) - индексом поля "куда". Остальные элемента массива записываются одинаково:
0: индекс поля "откуда" - начальная позиция короля = $this->position_index
2: "вес рокировки" = $castling_weight
3: вес фигуры, которую взяли = $none_figure_weight (при рокировке никакую фигуру не берём)Класс пешки
В классе пешки тоже надо изменить метод getAvailableMoves, чтобы он возвращал ходы в новом формате. Приведу этот метод полностью, цветом подсвечивая удалённые, новые, и изменённые строки:
engine/figures/pawn.phppublic function getAvailableMoves() {
$moves = array();
$board_position = new BoardPosition();
$our_king_positions = $this->game_state->figures[FG_KING + $this->color];
if (count($our_king_positions) === 0) {
return $moves;
}
$our_king_position = $our_king_positions[0];
$our_king_position = $this->game_state->getKingPosition($this->color);
$candidate_moves = $this->getCandidateMoves();
$pawn_figure_weight = self::FIGURE_WEIGHTS[FG_PAWN];
foreach($candidate_moves as $to_index) {
$to_position = $this->game_state->position; // копируем позицию
$to_position[$this->position_index] = FG_NONE; // убираем фигуру из текущей позиции
$to_position[$to_index] = $this->figure; // перемещаем фигуру на выбранное поле. Если на том поле что-то стояло - оно "убирается"
if ($to_index === $this->game_state->crossed_field) {
// это "взятие на проходе". Надо убрать с позиции проскочившую пешку.
$beat_col = Functions::positionToCol($to_index);
$beat_cell_index = Functions::colRowToPositionIndex($beat_col, $this->row);
$to_position[$beat_cell_index] = FG_NONE;
$beat_figure_weight = $pawn_figure_weight;
} else {
$beat_figure_type = Functions::figureType($to_position[$to_index]);
$beat_figure_weight = self::FIGURE_WEIGHTS[$beat_figure_type];
}
$to_position[$this->position_index] = FG_NONE; // убираем фигуру из текущей позиции
$to_position[$to_index] = $this->figure; // перемещаем фигуру на выбранное поле. Если на том поле что-то стояло - оно "убирается"
$board_position->setPosition($to_position);
if ($board_position->isFieldUnderAttack($our_king_position, $this->enemy_color)) {
// ход недопустим, т.к. после него наш король оказывается под атакой
continue;
}
$moves[] = array($this->position_index, $to_index, $pawn_figure_weight, $beat_figure_weight);
}
return $moves;
}
Строки 4-8 заменены одной строкой 9, не зря-же мы добавили метод поиска короля в состояние игры.
В строке 11 в отдельную переменную записали "вес пешки" для удобства, чтобы потом просто записать имя переменной, не обращаясь к массиву.
Строки 14, 15 переехали ниже, они стали строками № 26, 27. Причина? В этих строках мы "переставляем" пешку на поле, куда она ходит, убирая фигуру, которую она съедает, но нам-то теперь надо знать, что это за фигура, чтобы узнать её "вес". Поэтому мы унесли сам ход ниже.
А сам вес фигуры, которая съедается, мы определяем в строках 23, 24 для "обычного хода", а для взятия на проходе - в строке 21
Ну и в строке 33 добавляем инфрмацию о ходе в новом формате в результирующий массив ходов пешки.
Генератор ходов
Итак, классы фигур теперь возвращают ходы в новом формате. Но общий генератор ходов (класс MoveGenerator) пока работает со старым форматом. Напомню, что у нас сейчас есть в генераторе ходов.
А у нас там сейчас два метода (кроме конструктора). Первый - generateAllMoves. Он в цикле проходит по всем клеткам доски, и если в клетке встречается фигура "нашего" цвета, то с помощью "фабричного метоа" создаёт экземпляр класса соответствующей фигуры, вызывает метод генерации ходов этой фигуры, и добавляет её ходы в результирующий массив ходов в старом формате. Напомню этот формат. Ключами выступают индексы полей "откуда". Значения - массив индексов полей "куда". Именно в таком виде и нужны данные для пользовательской javascript-части приложения.
Но для перебора ходов удобнее "плоский" массив. Для получения ходов в "плоском виде" у нас есть второй метод - generateAllMovesFlat. Он вызывает первый метод (generateAllMoves), проходит по результату, и просто перекладывает данные в нужном виде.
В "плоском виде" ходы используются шахматным ИИ при переборе вариантов, т.е. - часто. А представление хода для пользовательской части нужно очень редко. Поэтому лучше генерировать ходы сразу в плоском виде, а для пользовательской части использовать преобразование из плоского вида. У на сейчас обратная картина "по истоическим причинам", просто мы начинали с пользовательской части, и не утруждались планированием всей системы.
Изменим эту схему. Теперь в методе generateAllMovesFlat будем проходить по всем полям, и вызывать методы генерации ходов на экземплярах классов фигур. А в методе generateAllMoves будем вызывать generateAllMovesFlat, и перекладывать данные в нужном для клиентской части виде.
Итак, открываем файл engine/move_generator.php и переписываем два метода:
engine/move_generator.phppublic function generateAllMoves() {
$moves = array();
$flat_moves = $this->generateAllMovesFlat();
foreach($flat_moves as $move) {
$field_from = $move[0];
if (!isset($moves[$field_from])) {
$moves[$field_from] = array($move[1]);
} else {
$moves[$field_from][] = $move[1];
}
}
return $moves;
}
protected function generateAllMovesFlat() {
$moves = array();
$color = $this->game_state->current_player_color;
for($i = 0; $i < BOARD_SIZE * BOARD_SIZE; $i++) {
$figure_code = $this->game_state->position[$i];
if ($figure_code === FG_NONE || Functions::color($figure_code) != $color) {
continue;
}
$figure_factory = new FigureFactory();
$figure = $figure_factory->create($this->game_state, $i);
$figure_moves = $figure->getAvailableMoves();
$moves = array_merge($moves, $figure_moves);
}
return $moves;
}
В методе generateAllMoves используются $move[0], $move[1]. Напомню, что ходы генерируются классами фигур уже в новом формате, и напомню его структуру:
ходы - массив, элементы которого - массивы с такой структурой (индекс - информация):
0 - индекс поля "откуда"
1 - индекс поля "куда"
2 - вес фигуры, которая ходит
3 - вес фигуры, которую берут
Сортировка ходов
Для чего мы заморачивались с новым форматом хода? Для чего добавили туда веса фигур? Чтобы делать сортировку ходов по этим параметрам. От порядка перебора ходов зависит насколько много вариантов мы сможем отсечь альфа-бета алгоритмом. Добавим в класс генератора ходов метод, который будет возвращать отсортированные ходы:
engine/move_generator.phppublic function generateSortedMoves() {
$moves = $this->generateAllMovesFlat();
if (count($moves) === 0) {
return $moves;
}
usort($moves, [$this, 'cmpMoves']);
return $moves;
}
Тут всё просто: вызывается метод генерации всех ходов, потом, если массив ходов не пустой, в строке 6 делается пользовательская сортировка методом cmpMoves класса. В нём весь "секрет". Добавим этот метод:
engine/move_generator.phpprivate function cmpMoves($a, $b) {
/* Структура сравниваемых переменных (индекс - смысл):
* 0 - поле "откуда"
* 1 - поле "куда"
* 2 - вес фигуры, которая ходит
* 3 - вес фигуры, которую берут
*/
$taken_figure_weigth_a = $a[3];
$taken_figure_weigth_b = $b[3];
if ($taken_figure_weigth_a === $taken_figure_weigth_b) {
if ($taken_figure_weigth_a === Figure::FIGURE_WEIGHTS[FG_NONE]) {
// Оба сравниваемых хода - не взятия фигур.
// Лучший ход будет фигурой с бОльшим весом
return $b[2] <=> $a[2];
} else {
// Оба сравниваемых хода берут фигуру с одинаковым весом (одинаково ценные фигуры)
// Лучший ход будет более лёгкой фигурой (рискует менее ценная фигура)
return $a[2] <=> $b[2];
}
}
// Оба сравниваемых хода - взятия фигур с разным весом. Лучший будет тот, в котором берётся более ценная фигура
return $taken_figure_weigth_b <=> $taken_figure_weigth_a;
}
Если не сталкивались с функцией пользовательсокой сортировки, посмотрите документацию по usort
Метод cmpMoves вызывается "из внутренностей" функции usort. Он принимает на вход две переменных, $a и $b (это сравниваемые ходы), и должен вернуть результат сравнения - целое число, которое меньше, равно или больше нуля, если $a является соответственно меньшим, равным или большим, чем $b.
В строке 8 мы запоминаем в переменную $taken_figure_weigth_a вес фигуры, которая берётся в ходе $a, а в строке 9 - вес фигуры, которая берётся в ходе $b.
В строке 10 мы сравниваем веса фигур, которые бьются в сравниваемых ходах. В ветке кода в строках 11-19 мы рассматриваем вариант, когда веса бьющихся фигур равны.
В строке 11 сравниваем вес взятой фигуры в ходе $a с весом пустого поля. Если эти веса равны, значит в ходе $a нет взятия, значит нет взятия и в ходе $b (мы находимся в ветке кода, где веса взятых фигур равны).
Итак, к строке 12 мы выяснили, что оба сравниваемых хода - не взятия. Какой из ходов мы хотим рассматривать в первую очередь в этом случае? Я решил что хочу сначала рассмотреть ход более тяжёлой фигурой. Т.е. надо чтобы ход с более тяжёлой фигурой был расположен в отсортированном массиве раньше хода с более лёгкой фигурой. Т.е. ход более тяжёлой фигурой должен быть "меньше" хода с более лёгкой фигурой. В строке 14 мы возвращаем результат сравнения "веса фигуры в ходе $b" слева от "веса фигуры в ходе $a".
Пояснение для тех, кто не встречал оператор "<=>". Этот оператор появился в PHP7, он называется "space ship" (космический корабль). Запись
$x <=> $y
эквивалентна такому коду:
if ($x > $y) {
return 1;
} elseif ($x < $y)
return -1;
} else {
return 0;
}
Конечно, последний else можно отбросить, просто возвращать 0. В таком виде я записал для наглядности логики. Если у вас не поддерживается оператор "<=>", можете заменить его на такой код.
В ветку else (строки 16-18) мы попадаем когда в обоих сравниваемых ходах мы берём фигуры с одинаковым весом. Я решил что в этом случае лучше сначала рассмотреть ход, где мы берём фигуру противника более лёгкой фигурой, точнее фигурой с меньшим весом. Например мы атакуем коня своими слоном и ферзём, и этот конь как-то защищён. Конечно лучше сначала рассмотреть ход, когда мы берём этого коня слоном, а не ферзём.
Т.е. в случае взятия фигур, мы, в отличии от ходов - "не-взятий", хотим сначала рассмотреть ход более лёгкой фигурой. В строке 18 мы возвращаем результат сравнения "веса фигуры в ходе $a" слева от "веса фигуры в ходе $b". Сравните строки 18 и 16, в них, можно сказать, "противоположные сравнения".
Ну и в строку 22 мы попадаем, когда в сравниваемых ходах разный вес "берущихся" фигур, в том числе, в качестве "фигуры" может быть и "пустое поле". В этом случае, мы хотим раньше рассмотреть ход, в котором у съедаемой фигуры бОльший вес. Т.е. "больше вес" значит "надо чтобы в отсортированном массиве располагался раньше" значит "при сравнении должен быть меньше", возвращаем результат сравнения: $taken_figure_weigth_b <=> $taken_figure_weigth_a
Добавляем альфа-бета отсечение в компьютерный ИИ
Открываем файл engine/computer_ai_v1.php с нашим ИИ. Метод getGenerateMove исправим, чтобы он выглядел так:
engine/computer_ai_v1.phppublic function getGenerateMove() {
//$t1 = microtime(true);
$search_best_move_result = $this->searchBestMove($this->game_state, $this->search_depth, PHP_INT_MIN, PHP_INT_MAX);
//$t2 = microtime(true);
//$delta = round($t2 - $t1, 1);
//$speed = $t2>$t1 ? round($this->position_counter / ($t2 - $t1)) : 1000000;
//error_log('Оценено позиций: '.$this->position_counter.' Score='.$search_best_move_result['score']." Time=$delta sec. Speed = $speed\r\n", 3, 'log.txt');
$move = $search_best_move_result['best_move'];
if (!$move) {
return false;
}
return array('from' => $move[0], 'to' => $move[1]);
}
Сразу бросается в глаза большое количество закомментаренных строчек. Они нужны были только для логирования количества оцененных позиций и времени выполнения. Основная работа делается в строке 3 - мы вызываем метод searchBestMove. Как и раньше, передаём в него состояние игры и требуемую глубину просмотра дерева. Но теперь добавляем туда ещё два параметра - PHP_INT_MIN, PHP_INT_MAX. Это наши начальные границы отсечения - альфа и бета. При первом вызове метода мы передаём туда минимальное возможное целое число и максимально возможное целое число, т.е. делаем поиск с максимально возможным "окном".
Теперь посмотрим, как будет выглядеть сам метод поиска хода:
engine/computer_ai_v1.php/**
* Метод ищет "лучший ход" и возвращает оценку позиции
* $game_state - позиция, для которой ищется лучший ход
* $depth - глубина, на которую надо делать перебор позиций
* $alpha, $beta - альфа, бета границы отсечения
* Возвращается массив с двумя ключами:
* score - оценка позиции
* best_move - найденный "лучший ход" (массив с двумя элементами - индексы полей "откуда" и "куда") или null
*/
private function searchBestMove(GameState $game_state, $depth, $alpha, $beta) {
if ($game_state->checkDraw()) {
return array('score' => 0, 'best_move' => null);
}
$move_generator = new MoveGenerator($game_state);
$available_moves = $move_generator->generateSortedMoves();
$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);
}
$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, -$beta, -$alpha);
$tmp_score = - $search_best_move_result['score'];
if ($tmp_score > $alpha) {
$alpha = $tmp_score;
$best_move = $move;
}
if ($alpha >= $beta) {
break;
}
}
return array('score' => $alpha, 'best_move' => $best_move);
}
Что тут изменилось? Во первых, добавилось два параметра метода - альфа и бета границы отсечения. Во вторых, сразу в начале метода я добавил проверку на состояние ничьи (строки 10-12). И убрал эту проверку из оценочной функции в классе состояния игры. Посчитал что так код выглядит проще. Откройте файл engine/game_state.php и в методе calcStaticScore удалите такой код:
// Проверяем ничью по повторам и неактивности
if ($this->checkDraw()) {
return 0;
}Возвращаемся к изменениям в searchBestMove. Далее, в строке 14 вместо метода generateAllMovesFlat вызываем метод generateSortedMoves чтобы получить отсортированные перемещения.
Следующее изменённое место - рекурсивный вызов описываемого метода на строке 27. Мы добавили два новых параметра в метод searchBestMove - альфа и бета, так что добавляем их и в вызов метода. В качестве параметра альфа мы передаём "минус бета", а в качестве бета - "минус альфа". Помните, выше я писал, что наш гарантированный минимум - это возможный максимум оппонента, и гарантированный минимум оппонента - это наш возможный максимум.
Полученная оценка позиции ($tmp_score) сравнивается с альфой (строка 29). Если оценка выше альфы, значит удалось улучшить наш гарантированный минимум, и в строках 30, 31 мы обновляем альфу, и записываем ход, который улучшил оценку, как новый "лучший ход".
Ну и само отсечение - в строках 33 - 35. Если альфа сравнялось с бетой, дальше нет смысла рассматривать ходы из текущего варианта, т.к. оппонент не выберет этот вариант. Прерываем цикл, выходим из него. В качестве оценки позиции берём значение альфы ($alpha).
Смотрим что получилось. Итоги
Пробую играть с этим алгоритмом - ответ мгновенный. Увеличиваю глубину перебора с трёх до четырёх полуходов. Компьютер отвечает в среднем за две секунды. Увеличиваю глубину до пяти. Компьютер стал отвечать примерно за 10-20, иногда больше секунд, т.е. столько-же сколько и при полном переборе на три полухода. Это очень существенное ускорение. Давайте для глубины перебора сделаем значение по умолчанию, равное четырём. Компьютер так будет играть слабее, чем при глубине, равной пяти, зато ждать его не нужно будет.
Идём в файл engine/computer_ai_v1.php, и в параметрах конструктора изменяем "$search_depth = 3" на "$search_depth = 4". Всё. Можно играть.
А давайте примерно оценим, насколько сильно сократилось число оцениваемых позиций. Сделал в предыдущей версии скриптов (где грубый перебор) глубину просмотра 4 полухода. Это была долгая игра. Ответа компьютера приходилось ждать и 10 минут, и иногда больше. Вот лог:
"Грубый перебор" на глубину 4 полухода
Оценено позиций: 405385 Score=-10
Оценено позиций: 368870 Score=-7
Оценено позиций: 247667 Score=3
Оценено позиций: 464620 Score=-7
Оценено позиций: 606772 Score=-7
Оценено позиций: 619224 Score=-17
Оценено позиций: 931767 Score=-17
Оценено позиций: 593493 Score=-20
Оценено позиций: 90449 Score=-30
Оценено позиций: 334843 Score=-20
Оценено позиций: 715329 Score=-20
Оценено позиций: 569063 Score=-20
Оценено позиций: 902827 Score=-20
Оценено позиций: 749868 Score=-20
Оценено позиций: 605440 Score=-20
Оценено позиций: 908245 Score=-20
Оценено позиций: 770202 Score=-30
Оценено позиций: 1377141 Score=-30
Оценено позиций: 821363 Score=-30
Оценено позиций: 429788 Score=-40
Оценено позиций: 28175 Score=-9223372036854775808
Оценено позиций: 334819 Score=-9223372036854775808
Оценено позиций: 21897 Score=-9223372036854775808
Оценено позиций: 1 Score=-9223372036854775808Отбросим те строки, где число позиций меньше 100 тысяч, там были "вынужденные ходы" (шахи), тогда получится, что в среднем алгоритм оценивал около 650 тысяч позиций чтобы сделать ход.
А вот лог одной из партий с той-же глубиной просмотра, но с альфа-бета отсечением:
Альфа-бета отсечение, глубина 4 полухода
Оценено позиций: 3348 Score=-10 Time=1.4 sec. Speed = 2328
Оценено позиций: 4233 Score=-10 Time=1.8 sec. Speed = 2400
Оценено позиций: 5966 Score=-10 Time=2.3 sec. Speed = 2637
Оценено позиций: 5156 Score=-10 Time=2.1 sec. Speed = 2427
Оценено позиций: 4794 Score=-10 Time=1.9 sec. Speed = 2475
Оценено позиций: 4335 Score=-10 Time=1.9 sec. Speed = 2275
Оценено позиций: 7128 Score=0 Time=3.7 sec. Speed = 1940
Оценено позиций: 4593 Score=-27 Time=2.7 sec. Speed = 1729
Оценено позиций: 1008 Score=-10 Time=0.5 sec. Speed = 2118
Оценено позиций: 2385 Score=20 Time=1.3 sec. Speed = 1832
Оценено позиций: 3605 Score=-27 Time=2 sec. Speed = 1844
Оценено позиций: 3760 Score=-27 Time=1.9 sec. Speed = 2015
Оценено позиций: 2043 Score=-7 Time=1.3 sec. Speed = 1611
Оценено позиций: 4982 Score=-7 Time=2.4 sec. Speed = 2051
Оценено позиций: 783 Score=-7 Time=0.4 sec. Speed = 2133
Оценено позиций: 3566 Score=3 Time=1.5 sec. Speed = 2315
Оценено позиций: 2216 Score=3 Time=0.9 sec. Speed = 2383
Оценено позиций: 1278 Score=-7 Time=0.6 sec. Speed = 2035
Оценено позиций: 1821 Score=-7 Time=0.8 sec. Speed = 2428
Оценено позиций: 2821 Score=-47 Time=1 sec. Speed = 2920
Оценено позиций: 2680 Score=-47 Time=0.9 sec. Speed = 3001
Оценено позиций: 600 Score=-9223372036854775808 Time=0.2 sec. Speed = 3261
Оценено позиций: 4127 Score=-57 Time=1.6 sec. Speed = 2579 Здесь я пропустил мат, мог бы раньше закончить партию
Оценено позиций: 4147 Score=-67 Time=1.6 sec. Speed = 2615
Оценено позиций: 7262 Score=-117 Time=2.1 sec. Speed = 3401
Оценено позиций: 1495 Score=-90 Time=0.5 sec. Speed = 2805
Оценено позиций: 3575 Score=-77 Time=1.4 sec. Speed = 2477
Оценено позиций: 4706 Score=-87 Time=1.6 sec. Speed = 2980
Оценено позиций: 3213 Score=-77 Time=1 sec. Speed = 3249
Оценено позиций: 1487 Score=-87 Time=0.5 sec. Speed = 2882
Оценено позиций: 1925 Score=-87 Time=0.7 sec. Speed = 2886
Оценено позиций: 2170 Score=-87 Time=0.7 sec. Speed = 3104
Оценено позиций: 3973 Score=-77 Time=1.4 sec. Speed = 2776
Оценено позиций: 1287 Score=-77 Time=0.5 sec. Speed = 2762
Оценено позиций: 2135 Score=-9223372036854775808 Time=0.7 sec. Speed = 3011
Оценено позиций: 514 Score=-9223372036854775808 Time=0.2 sec. Speed = 2663
Оценено позиций: 1 Score=-9223372036854775808 Time=0 sec. Speed = 1000Видите, насколько мощное сокращение числа вариантов даёт альфа-бета отсечение! Максимальное число позиций, рассмотренных в этой партии было всего 7128, и компьютер ответил за 3,7 секунды. Это максимум. Сравните эти максимальные 7 тысяч со средним числом 650 тысяч в полном переборе. "Speed" в логе - это скорость перебора, "оцененных позиций в секунду".
И в конце, как обычно: исходные коды этого варианта на github.
И демо игры: Демо №15 игры, альфа-бета отсечение