Игровые эвристики
Как усилить игру нашей программы? Можно увеличивать "глубину просмотра" дерева игры. Но при этом резко растёт затраченное время. Нам не нужна программа, ответа которой надо долго ждать. Даже 5 минут для нас - слишком долго. Можно пытаться оптимизировать, ускорить алгоритм генерации ходов и других операций на доске. Может позже мы это попробуем сделать. Но существенно увеличить глубину просмотра дерева игры не получится. Что же делать?
Когда точное решение / оптимальное действие невозможно найти, или когда такой поиск занимает недопустимо много времени, можно применить значительно более быстрый неточный алгоритм. Такой алгоритм может и не найдёт точное решение / лучшее действие, но он достаточно быстро даст приемлемый результат в большинстве случаев. Такие алгоритмы называют эвристическими (от греческого слова "отыскиваю", "открываю").
Тут открывается большое поле для экспериментов. Можно придумывать, пробовать и комбинировать разные идеи и подходы. Загуглите к примеру: "эвристика пустого хода", "эвристика убийцы", "эвристика истории", "нулевого окна", …
В этой статье опишу уже готовый результат недолгих моих экспериментов. Все перечисленные приёмы я конечно не использовал. Ограничился небольшим усложнением оценочной функции, и "дробной глубиной просмотра" с выборочными продлениями. Пробуйте, экпериментируйте! Добавляйте свои критерии оценки позиции. Например у меня "сдвоенные" пешки не оказывают негативного влияния на позиционную оценку. Так-же, как и "висячие" пешки. Есть ещё большое простанство для улучшений.
Усложняем оценочную функцию
Напомню - оценочная функция берёт позицию, и вычисляет её "оценку". Т.е. одним числом характеризует, насколько хорошо в этой позиции обстоят дела. Для одной и той-же позиции, "оценка для белых" равна "минус оценка для чёрных". Сейчас при оценке позиции учитывается только материальная ценность фигур. Если в двух разных позициях набор фигур на доске одинаковый, то и оценка этих позиций одинаковая, независимо от того, где находятся эти фигуры.
Именно поэтому сейчас компьютер "в спокойной позиции" может ходить одной фигурой туда-сюда. На своём "горизонте событий" (глубине просмотра дерева игры) он не видит ходов, улучшающих оценку. Не видит, как съесть безнаказанно чужую фигуру. А про "развитие фигур", захват центра доски, прочие какие-то абстакции - нет, не слышал, "да что это вы такое придумываете?"
Все знакомые позиционные факторы я учитывать не стал. Что будем учитывать в позиционной оценке в новой версии:
- Конечно материальная оценка фигур, этот фактор остаётся самым значимым
- Ценность продвижения пешек
- Близость наших фигур к королю противника, и удалённость нашего короля от фигур противника
- "Фактор атаки". Здесь будем учитывать сумму "взвешенных количеств атак" наших фигур, и атак на наши фигуры. Что это такое, опишу ниже.
Полный код новой оценочной функции
Ценность фигур у нас была указана в константе FIGURE_VALUES класса GameState. У пешки оценка равна 10. Сейчас мы будем добавлять разные факторы позиционной оценки, и надо чтобы ценность фигур превышала эти новые факторы. Не хочется ради позиционного перевеса с призрачной перспективой жертвовать фигурами. Так что повысим ценность фигур, припишем всем (кроме короля) по два нолика. У короля и так заоблачная ценность - миллион. Новый массив с ценами фигур будет выглядеть так:
engine/game_state.phpconst FIGURE_VALUES = array(
FG_KING => 1000000,
FG_QUEEN => 9000,
FG_ROOK => 5000,
FG_BISHOP => 3000,
FG_KNIGHT => 2800,
FG_PAWN => 1000
);
Оценочная функция у нас - это метод calcStaticScore класса GameState. Во время экспериментов, я решил её не трогать, а завести рядом новый метод calcStaticScoreEx для новой оценочной функции. ("Ex" - это сокращение от "extended", т.е. "расширенный"). Сразу приведу её полный код:
engine/game_state.phppublic function calcStaticScoreEx($no_available_moves) {
if ($no_available_moves) {
if ($this->isKingUnderAttack()) {
return PHP_INT_MIN;
} else {
return 0;
}
}
// Будем строить оценку позиции для белых. Если нужна оценка для чёрных (т.е. если сейчас их ход), то возвратим противоположное число.
// заполняем массив фигур. Формат: array[figure_code][] - массив номеров полей
$this->setFigures();
// считаем материальную ценность фигур
$figure_types = array(FG_QUEEN, FG_ROOK, FG_BISHOP, FG_KNIGHT, FG_PAWN);
$score = 0;
foreach ($figure_types as $figure_type) {
$score += self::FIGURE_VALUES[$figure_type] * (count($this->figures[$figure_type + COLOR_WHITE]) - count($this->figures[$figure_type + COLOR_BLACK]));
}
// ценность продвижения пешек
$pawn_position_weigths = array(
0, 0, 0, 0, 0, 0, 0, 0,
65, 70, 70, 70, 70, 70, 70, 65,
50, 55, 60, 65, 65, 60, 55, 50,
36, 40, 48, 50, 50, 48, 40, 36,
18, 20, 24, 36, 36, 24, 20, 18,
10, 10, 10, 10, 10, 10, 10, 10,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0
);
// считаем ценность продвижения для белых пешек
foreach ($this->figures[FG_PAWN + COLOR_WHITE] as $field_idx) {
$score += $pawn_position_weigths[$field_idx];
}
// считаем ценность продвижения для чёрных пешек
$pawn_position_weigths = array_reverse($pawn_position_weigths);
foreach ($this->figures[FG_PAWN + COLOR_BLACK] as $field_idx) {
$score -= $pawn_position_weigths[$field_idx];
}
// Наши фигуры (белые) хотим расположить ближе к королю противника
$square_distance = 0;
$figure_types_without_pawn = array(FG_QUEEN, FG_ROOK, FG_BISHOP, FG_KNIGHT);
$black_king_position = $this->getKingPosition(COLOR_BLACK);
$black_king_row = Functions::positionToRow($black_king_position);
$black_king_col = Functions::positionToCol($black_king_position);
foreach ($figure_types_without_pawn as $figure_type) {
foreach ($this->figures[$figure_type + COLOR_WHITE] as $position) {
$row = Functions::positionToRow($position);
$col = Functions::positionToCol($position);
$square_distance -= pow($black_king_row - $row, 2) + pow($black_king_col - $col, 2); // минус - т.к. чем больше дистанция, тем нам (белым) хуже
}
}
// А нашего (белого) короля хотим расположить подальше от фигур противника
$white_king_position = $this->getKingPosition(COLOR_WHITE);
$white_king_row = Functions::positionToRow($white_king_position);
$white_king_col = Functions::positionToCol($white_king_position);
foreach ($figure_types_without_pawn as $figure_type) {
foreach ($this->figures[$figure_type + COLOR_BLACK] as $position) {
$row = Functions::positionToRow($position);
$col = Functions::positionToCol($position);
$square_distance += pow($white_king_row - $row, 2) + pow($white_king_col - $col, 2); // чем больше дистанция тем нам (белым) лучше
}
}
$score += $this->move_number * 0.2 * $square_distance;
// учитывем "фактор атак"
$score += $this->getAttackFactor() / 100;
if ($this->current_player_color == COLOR_BLACK) {
$score = -$score;
}
return $score;
}
Начало такое-же, как в старой версии метода. Т.е. если нет допустимых ходов, то у нас или мат (и тогда возвращаем минимально возможное в php целое число), или пат (и тогда возвращает ноль).
Материальная оценка фигур
Материальную ценность фигур на доске считаем в строках 14 - 19. В предыдущей версии мы проходили по всем полям доски, и если поле было не пустое, учитывали ценость фигуры, стоящей в этом поле. В новой версии мы сначала собираем информацию о положении всех фигур на доске (вызовом метода setFigures в строке 12). Потом, в строке 15 заполняем массив с типом фигур, ценность которых будем учитывать. Почему там нет короля? Потому что в любой момент игры и у белых и у чёрных на доске всегда есть король, и только один. Их ценности компенсируют друг друга (в сумме дают ноль).
Почему я изменил способ подсчёта? Ведь для того, чтобы пройтись циклом по типам фигур, перед этим надо всё равно пройти по всем полям доски и собрать информацию о положении фигур в поле класса $this->figures. Просто этот массив с положением фигур ещё понадобится в текущем методе оценки позиции.
В переменной $score будем "накапливать" оценку позиции, и возвратим её в конце метода.
В строках 17 - 19 проходим циклом по типам фигур. К оценке $score прибавляем стоимость типа фигуры, умноженную на разность количеств фигур этого типа у белых и у чёрных.
Ценность продвижения пешек
В строках 22 - 31 я завёл массив с 64 элементами, каждый из которых соответствует одной клетке доски. И в коде они расположены визуально соответствующими клеткам. Этот массив показывет, какие числа добавлять к оценке позиции, если в соответствующих полях расположены белые пешки. "Нижние" два ряда заполнены нулями, потому что на этих полях белые пешки не могут оказаться. И "верхий ряд" тоже состоит из нулей, потому что белые пешки, добавшись до последней горизонтали, перестают быть пешками, превращаются в другие фигуры, имеющие более высокую оценку.
К примеру, в поле e2 стоит число 10. В поле e4 - число 50. Т.е. сделав ход e2-e4, пешка увеличит оценку позиции на 50 - 10 = 40 едениц за счёт своего перемещения.
Оценки для пешек я расположил так, что чем ближе к последней горизонтали, тем выше оценка. И продвижение центральных пешек оценил выше, чем продвижение боковых.
В строках 33 - 35 проходим циклом по положениям всех белых пешек и добавляем к оценке позиции "стоимость" их положения.
В строке 37 переворачиваем массив $pawn_position_weigths со "стоимостями" положения пешек, таким образом получаем "стоимости расположения" для чёрных пешек. (Здесь мы пользуемся тем, что числа "расположены" симметрично относительно "вертикальной центральной линии"). Затем, в строках 37 - 40, так-же проходим по положениям всех чёрных пешек, но уже не прибавляем, а вычитаем "стоимости" их положения. Напоминаю, что мы строим оценку позиции для белых фигур. А уже в самом конце метода, если оценка нужна для чёрных фигур, просто меняем знак полученной оценки. (см. строки 74 - 74).
Близость фигур к королю противника
Я решил попробовать эвристику "близости фигур к королю". И вроде работает неплохо. Суть - чем дальше находится наш король от фигур противника, тем лучше, безопаснее. И, симметрично - чем ближе наши фигуры к королю противника, тем лучше для нас. Учёт расстояний реализован в строках 42 - 70 кода, приведённого выше.
Как это работает? Заводим переменную $square_distance, в которой будем накапливать сумму квадратов расстояний до короля. Заводим массив (строка 44) $figure_types_without_pawn, в котором укажем типы фигур, для которых будем считать расстояния до короля - ферзь, ладья, слон, конь. От пешек не будем бегать. И пешки не будем приближать к королю, им и так есть куда стремиться - к последней горизонтали.
Сначала обработаем расстояния от наших фигур (белых) до короля противника (чёрного короля). Напомню, что мы считаем оценку позиции для белых. И только в конце метода, если нужна оценка для чёрных, инвертируем оценку (менянем знак). В строках 45 - 47 получаем индекс позиции чёрного короля, и получаем из неё отдельные "координаты" чёрного короля - индекс горизонтали и индекс вертикали.
В строке 48 начинаем цикл по типам фигур, для которых решили считать расстояния. Внутри - ещё один цикл - проходим по позициям белых фигур текущего типа. Т.е. сначала будет цикл по позициям всех белых ферзей, потом - по позициям всех белых ладей, потом слонов, коней. Для каждой позиции вычисляем отдельные координаты - горизонталь и вертикаль. В итоге, у нас есть координаты чёрного короля, и координаты текущй (белой) фигуры. В строке 52 считаем квадрат расстояния между текущей фигурой и чёрным королём (вспоминаем школьную геометрию) как сумму квадратов разности координат. И этот квадрат расстояния мы добавляем к $square_distance со знаком "минус". Потому что, чем больше расстояние от наших (белых) фигур до чёрного короля, тем уже, мы хотим минимизировать это расстояние.
В строках 56 - 66 код аналогичный только что описанному. Только мы берём уже позицию нашего (белого) короля, проходим циклом по чёрным фигурам, и крадраты расстояний плюсуем к $square_distance, т.к. мы хотим располагать нашего короля подальше от фигур противника. (Не забывайте, что мы сейчас рассуждаем со стороны белых, для которых строится оценка позиции).
В строке 67 окончательно учитываем вклад расстояний в оценку позиции:
$score += $this->move_number * 0.2 * $square_distance;Я хотел, чтобы фактор расстояния действовал слабее в начальной стадии игры, поэтому умножил $square_distance на номер хода. А чтобы полученное значение не перекрыло стоимость пешки (материальная ценность фигур превыше всего в статической оценке позиции), умножил это всё ещё на 0.2. Просто экспериментально подобрал такой коэффициент.
Фактор атаки
Давайте учитывать, сколько на доске суммарно атак на наши фигуры, и сколько фигур противника атакуют наши фигуры. Причём, учитывать будем "рентгеновские атаки". Т.е. если про проверке например вертикали, обнаружили, что фигуру противника атакует наша ладья, мы продолжаем смещаться по выбранной вертикали, ведь там может стоять другая наша ладья, а за ней - может быть ещё и ферзь. Конечно, если на фигуру нападает король, то фигуры за ним рассматривать не будем. Смысл "рентгеновских атак" в серии разменов. Т.е. к примеру: "я съедаю эту пешку слоном, он съедает его своим слоном, я съедаю слона ферзём". А какая серия разменов после короля? Его съедать нельзя. Какой смысл что за ним стоит ладья, если королём всё равно нельзя съесть защищённую фигуру?
Кроме этого, будем учитывать ценность фигуры, которую атакуют, и ценность атакующей фигуры. Чем ценнее фигура, на которую напали, тем лучше для нападающей стороны. И чем более слабая фигура нападает, тем тоже лучше нападающей стороне. Т.е. если пешка напала на ферзя - хорошо. Если ферзь напал на пешку - не так хорошо. Пешка может быть защищена, и мы не хотим отдавать ферзя за пешку. А вот пешку за ферзя - запросто.
Т.е. при подсчёте количеств нападений, будем учитывать и "вес" атакуемой фигуры, и "вес" нападающей фигуры. Сумму таких "взвешенных" количеств нападений будем называть фактором атаки.
Учёт "фактора атаки" в итоговой оценке позиции - в строках 69 - 70:
// учитывем "фактор атак"
$score += $this->getAttackFactor() / 100;Т.е. я вынес вычисление этого фактора в новый отдельный метод (который сейчас напишем), и разделил "фактор атаки" на 100. Это тоже экспериментально подобранный коэффициент, нужный чтобы вклад фактора атаки в оценку позиции не превысил материальную стоимость пешки. Добавляем новый метод в класс состояния игры:
engine/game_state.phppublic function getAttackFactor() {
// Вычисляем "фактор атаки" для белых: сумму "взвешенных количеств атак" на чёрные фигуры минус сумма взвешенных количеств атак на белые фигуры.
// Вес определяется достоинствами атакуемой и атакующей фигур
$board_position = new BoardPosition();
$board_position->setPosition($this->position);
return $board_position->getAttackFactor();
}
И снова перенос реального вычисления фактора атаки - в класс BoardPosition. Почему туда? В том классе есть метод, определяющий, находится-ли поле под атакой. При подсчёте числа атак будем использовать похожий код.
На этом заканчиваем рассмотрение метода calcStaticScoreEx класса GameState
Вычисление фактора атаки
Открываем код класса BoardPosition. В начало класса добавим две константы - массива, в которых укажем веса атакующих фигур, и отдельно - атакуемых:
engine/board_position.php// чем более ценную фигуру атакуем, тем лучше
const FIGURE_ATTACK_FACTOR = array(
FG_KING => 80,
FG_QUEEN => 60,
FG_ROOK => 35,
FG_BISHOP => 22,
FG_KNIGHT => 20,
FG_PAWN => 10
);
// чем менее ценной фигрой атакуем, тем лучше
const FIGURE_FROM_ATTACK_FACTOR = array(
FG_KING => 20,
FG_QUEEN => 40,
FG_ROOK => 65,
FG_BISHOP => 78,
FG_KNIGHT => 80,
FG_PAWN => 90
);
Добавляем теперь сам метод вычисления фактора атаки:
engine/board_position.php/**
* "Фактор атаки" - сумма взвешенных количеств атак на фигры с учётом цвета. Вычисляется для белых.
* Учитываются "рентгеновские" атаки, когда атакующие фигуры стоят друг за другом
*/
public function getAttackFactor() {
$attacks_factor = 0;
for($i = 0; $i < BOARD_SIZE*BOARD_SIZE; $i++) {
$figure_code = $this->position[$i];
if ($figure_code == FG_NONE) {
continue;
}
// нашли поле с фигурой
$figure_type = Functions::figureType($figure_code);
$figure_color = Functions::color($figure_code);
if ($figure_color == COLOR_WHITE) {
$opponent_color = COLOR_BLACK;
$multiplier = -1;
} else {
$opponent_color = COLOR_WHITE;
$multiplier = 1;
}
$attacks_factor += $multiplier * self::FIGURE_ATTACK_FACTOR[$figure_type] * $this->getWeighedAttackCountToField($i, $opponent_color);
}
return $attacks_factor;
}
Здесь мы проходим по всем клеткам доски, если поле пустое - пропускаем. Если поле не пустое, определяем (строки 13, 14) какая фигура в нём стоит, и какого цвета. Потом определяем цвет фигур оппонента ($opponent_color), т.е. цвет фигур, чьи атаки по рассматриваемому полю будем считать. И определяем множитель ($multiplier "1" или "-1"), на который будем умножать "взвешенное количество атак" при добавлении в результирующую переменную $attacks_factor.
Т.е., например, если в цикле в текущем поле стоит белая (т.е. "наша") фигура (строки 16, 17), то будем считать атаки со стороны чёрных фигур. И, т.к.
это будут атаки на нашу (белую) фигуру, то взвешенную сумму количеств атак надо вычесть из результирующего фактора атаки, т.е. установить
$multiplier = -1;
В строке 22 множитель ("1" или "-1") умножаем на вес атакуемой фигуры, и умножаем на взвешенную сумму количеств атак на текущее поле. Эта "взвешенная сумма" вычисляется вызовом ещё одного нового, не написанного пока метода - getWeighedAttackCountToField. Передаём этому методу индекс текущего поля, и цвет фигур, атаки которых на указанное поле нас интересуют.
Взвешенное количество атак на поле
Добавляем новый метод:
engine/board_position.php/**
* Метод возвращает взвешенное количество атак на поле с индексом $field_idx со стороны фигур цвета $attack_color
*/
private function getWeighedAttackCountToField($field_idx, $attack_color) {
$figure_col = Functions::positionToCol($field_idx);
$figure_row = Functions::positionToRow($field_idx);
return $this->weighedCountKnightAttack($figure_col, $figure_row, $attack_color) + $this->weighedCountLinearAttack($figure_col, $figure_row, $attack_color);
}
Т.е. здесь мы разделили задачу на две части, и считаем результат как сумму "взвешенных количеств конских атак", и "взвешенных линейных атак". Обе части суммы реализованы вызовами новых, пока не написанных методов.
Атаки со стороны коней
Добавляем метод, считающий взвешенное количество атак со стороны коней:
engine/board_position.phpprivate function weighedCountKnightAttack($figure_col, $figure_row, $attack_color) {
$attack_count = 0;
foreach(Knight::SHIFTS as $shift) {
$col = $figure_col + $shift[0];
if ($col < 0 || $col >= BOARD_SIZE) {
continue;
}
$row = $figure_row + $shift[1];
if ($row < 0 || $row >= BOARD_SIZE) {
continue;
}
$to_index = Functions::colRowToPositionIndex($col, $row);
$to_figure = $this->position[$to_index];
if (FG_KNIGHT + $attack_color == $to_figure) {
$attack_count++;
}
}
return $attack_count * (self::FIGURE_FROM_ATTACK_FACTOR[FG_KNIGHT]);
}
Очень похоже на метод underKnightAttack. Почти "копи-паст". В том методе определялось - находится ли поле с переданными координатами под атакой коня переданного цвета. В новом методе тот-же самый алгоритм, но нам нужно посчитать количество всех атак, а не факт наличия хотя-бы одной атаки. Поэтому при нахождении чужого коня на очередном рассматриваемом поле (строка 14, 15), мы не прекращаем перебор направлений, а просто увеличиваем счётчик найденных атак.
В конце метода возвращаем количество найденных атак, умноженное на "атакующий вес" коня (на self::FIGURE_FROM_ATTACK_FACTOR[FG_KNIGHT])
Линейные атаки
Добавляем метод, считающий взвешенное количество "линейных атак":
engine/board_position.phpprivate function weighedCountLinearAttack($figure_col, $figure_row, $attack_color) {
$attack_count = $this->weighedCountAttackByShifts($figure_col, $figure_row, $attack_color, Rook::SHIFTS, array(FG_ROOK, FG_QUEEN));
$attack_count += $this->weighedCountAttackByShifts($figure_col, $figure_row, $attack_color, Bishop::SHIFTS, array(FG_BISHOP, FG_QUEEN));
$attack_count += $this->weighedCountAttackByPawn($figure_col, $figure_row, $attack_color);
return $attack_count;
}
Здесь используются два новых метода. Метод weighedCountAttackByShifts вычисляет взвешенное количество атак "по смещениям", а метод weighedCountAttackByPawn - взвешенное количество "пешечных атак" (тоже с "рентгеном" - за пешкой могут стоять слон и ферзь).
Атаки "по смещению"
Метод weighedCountAttackByShifts принимает такие аргументы:
- координаты (индексы вертикали и горизонтали) поля, атаки на которое мы ищем
- цвет фигур, атаки со стороны которых мы ищем
- массив смещений координат, указывающих направление линий, по которым ищем атакуюие фигуры
- массив типов фигур, которые представляют угрозу на рассматриваемых направлениях
engine/board_position.phpprivate function weighedCountAttackByShifts($figure_col, $figure_row, $attack_color, $shifts, $dangerous_figures) {
$weighted_count = 0;
foreach($shifts as $shift) {
list($shift_col, $shift_row) = $shift;
$continue_shift = true;
$col = $figure_col;
$row = $figure_row;
$distance = 0; // расстояние, на сколько мы отошли от рассматриваемой клетки - нужно для атак короля
while ($continue_shift) {
$col = $col + $shift_col;
if ($col < 0 || $col >= BOARD_SIZE) {
$continue_shift = false;
continue;
}
$row = $row + $shift_row;
if ($row < 0 || $row >= BOARD_SIZE) {
$continue_shift = false;
continue;
}
$distance++;
$to_index = Functions::colRowToPositionIndex($col, $row);
$figure = $this->position[$to_index];
if ($figure == FG_NONE) {
// поле пустое, можно дальше двигаться вдоль текущего направления
continue;
}
// наткнулись на какую-то фигуру
$to_figure_color = Functions::color($figure);
if ($to_figure_color != $attack_color) {
// наткнулись на свою фигуру, дальше направление можно не рассматривать
$continue_shift = false;
continue;
}
// наткнулись на чужую фигуру, надо узнать, представляет ли она опасность
$figure_type = Functions::figureType($figure);
if (in_array($figure_type, $dangerous_figures)) {
$weighted_count += self::FIGURE_FROM_ATTACK_FACTOR[$figure_type];
// не останавливаемся, продолжим двигаться по направлению - учитываем "рентгеновкое" нападение
} elseif ($distance == 1 && $figure_type == FG_KING) {
$weighted_count += self::FIGURE_FROM_ATTACK_FACTOR[FG_KING];
$continue_shift = false; // после короля двигаться по направлению не будем
}
}
}
return $weighted_count;
}
Подробно этот кусок кода комментировать не буду, он очень похож на метод underAttackByShifts, где искался факт хотя-бы одной "линейной атаки". А здесь нам надо найти все линейные атаки, да ещё и не останавливаться на "опасной фигуре", а идти дальше вдоль направления, чтобы обнаружить "рентгеновские атаки". В самом коде есть комментарии, да и вы, если дошли до этой части, достаточно легко разберётесь этом коде.
Пешечные атаки с рентгеном
Добавляем метод для подсчёта пешечных атак:
engine/board_position.phpprivate function weighedCountAttackByPawn($figure_col, $figure_row, $attack_color) {
$weighted_count = 0;
$direction = ($attack_color == COLOR_WHITE ? 1 : -1);
$row = $figure_row+ $direction;
if ($row < 0 || $row >= BOARD_SIZE) {
return $weighted_count;
}
// сначала рассмотрим луч влево от пешки
$col = $figure_col - 1;
if ($col >= 0) {
$position_index = Functions::colRowToPositionIndex($col, $row);
if ($this->position[$position_index] == FG_PAWN + $attack_color) {
$weighted_count += self::FIGURE_FROM_ATTACK_FACTOR[FG_PAWN];
// продолжим двигаться по лучу влево, возможно там "рентгеновская" атака от слона или ферзя
$continue_shift = true;
while ($continue_shift) {
$row += $direction;
if ($row < 0 || $row >= BOARD_SIZE) {
break;
}
$col -= 1;
if ($col < 0) {
break;
}
$to_index = Functions::colRowToPositionIndex($col, $row);
$figure = $this->position[$to_index];
if ($figure == FG_NONE) {
continue;
}
$to_figure_color = Functions::color($figure);
if ($to_figure_color != $attack_color) {
break;
}
$figure_type = Functions::figureType($figure);
if ($figure_type == FG_BISHOP || $figure_type == FG_QUEEN) {
$weighted_count += self::FIGURE_FROM_ATTACK_FACTOR[$figure_type];
}
}
}
}
// тепeрь рассмотрим луч вправо от пешки
$row = $figure_row+ $direction;
$col = $figure_col + 1;
if ($col < BOARD_SIZE) {
$position_index = Functions::colRowToPositionIndex($col, $row);
if ($this->position[$position_index] == FG_PAWN + $attack_color) {
$weighted_count += self::FIGURE_FROM_ATTACK_FACTOR[FG_PAWN];
// продолжим двигаться по лучу вправо, возможно там "рентгеновская" атака от слона или ферзя
$continue_shift = true;
while ($continue_shift) {
$row += $direction;
if ($row < 0 || $row >= BOARD_SIZE) {
break;
}
$col += 1;
if ($col >= BOARD_SIZE) {
break;
}
$to_index = Functions::colRowToPositionIndex($col, $row);
$figure = $this->position[$to_index];
if ($figure == FG_NONE) {
continue;
}
$to_figure_color = Functions::color($figure);
if ($to_figure_color != $attack_color) {
break;
}
$figure_type = Functions::figureType($figure);
if ($figure_type == FG_BISHOP || $figure_type == FG_QUEEN) {
$weighted_count += self::FIGURE_FROM_ATTACK_FACTOR[$figure_type];
}
}
}
}
return $weighted_count;
}
Тут тоже не буду построчно описывать код, он достаточно лёгок для понимания. Определяем направление ("вверх" или "вниз") откуда нам могут угрожать пешки цвета $attack_color. Потом по очереди рассматриваем в этом направлении лучи "влево" и "вправо" от поля, атаки на которое мы ищем. В каждом направлении смотрим - если пешка стоит рядом, т.е. она нападает на рассматриваемое поле, то продолжаем идти по лучу дальше, суммируя факторы атак от встреченных слнов и ферзей цвета $attack_color. Идём, пока не уйдём за доску, или не наткнёмся на "не угрожающую фигуру".
Выборочные продления
Итак, мы усложнили оценочную функцию. Из за этого оценка позиции теперь вычисляется значительно дольше. Т.е. скорость перебора снизилась, и теперь в среднем на моём компьютере примерно равна 1200-1300 оцененных позиций в секунду. Мало того что скорость снизилась, теперь оценки позиций стали "разнообразнее", и эффективность альфа-бета отсечения снизилась. Что-же делать?
А как играет человек? Его скорость "перебора позиций" явно же ниже чем 1200 позиций в секунду. А человек не рассматривает одинаково глубоко все варианты ходов. Какие-то ходы он вообще не рассматривает, "интуитивно понимая" что после этого хода ничего интересного не произойдёт (иногда это ошибочно, но "человеку свойственно ошибаться"). Какие варианты он пытается просмотреть как можно глубже. Например серию разменов. Вряд-ли кто-то размышляет - "вот я возьму этого коня, а дальше разберёмся потом".
Зато именно так работает наша программа. Это называется "эффект горизонта". Программе например задали глубину просмотра 4 полухода, она нашла вариант где съела ферзя, получив сильное материальное преимущество, и выбрала этот ход, т.к. он ведёт к позиции с максимальной оценкой. А то что после того как съела ферзя, на пятом полуходе получит мат - ну извините, она только на 4 полухода видит.
Итак, чтобы теперь не ждать долго хода компьютера, придётся сильно снизить глубину перебора. Но теперь мы не будем каждый раз уменьшать "оставшуюся глубину" на единицу при каждом углублении в дерево игры. Например, если в какой-то позиции у игрока всего один вариант хода, мы вообще не будем уменьшать глубину, и это не увеличит время рассчёта. Если вариантов хода всего два - уменьшим глубину, но не на еденицу, а например на 0,4. Можно ввести другие "приращения глубины" для позиций где всего 3 варианта хода, 4 варианта, …
Кроме количества возможных ходов, будем учитывать после хода - находится ли король под шахом, взята ли какая-то фигура? В этих вариантах тоже будем "продлять" дерево игры, т.е. уменьшать оставшуюся глубину просмотра меньше чем на единицу.
Итак, открываем код класса ComputerAIV1. К полям класса добавляем:
private $init_search_depth = 0;Для чего я ввёл это поле класса? При тестировании, в какой-то из позиций, я заметил что компьютер "не очень быстро" сделал ход, хотя у него был всего один вариант хода. Если он всего один, его и надо делать, над чем тут думать? Но если вариант с одним ходом встретился при просмотре дерева на какой-то глубине, тут нельзя сразу возвращать этот ход как "лучший", надо идти дальше и получить оценку позиции на той глубине до которой доберёмся. У нас ведь есть другие варианты ходов из корня дерева, кроме того, в ветке которого встретилась позиция с одним возможным ходом.
Поэтому я и ввёл поле класса ComputerAIV1. При поиске лучшего хода, если и з позиции возможен только один ход, и мы находимся в корне дерева игры (т.е. если ($depth == $this->init_search_depth), то можно сразу возвращать этот единственный ход, всё равно выбирать не из чего.
В конструктор класса, в самый конец добавляем заполнение нового поля класса:
$this->init_search_depth = $this->search_depth;И в аргументах конструктора уменьшаем значение по умолчанию для аргумента $search_depth с "4" до "2". Да, теперь быстродействие снизилось настолько, что приемлемое время ответа будет только для двух полуходов. Конечно в выборочных продлениях компьютер может углубиться и на 4, и на 6, и на 10 полуходов, где-то он найдёт "гениальную комбинацию", но где-то пропустит простейшую ловушку, лежащую за пределами взятий и двух полуходов.
В методе getGenerateMove первой строчкой увеличим лимит времени на ответ php до 50 секунд:
set_time_limit(50);Метод searchBestMove
И, наконец, изменим сам метод, ищущий лучший код. Хотя там изменений немного, я приведу его полный код:
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->calcStaticScoreEx($no_available_moves), 'best_move' => null);
}
$delta_depth = 1;
$moves_qty= count($available_moves);
if ($moves_qty == 1) {
if ($depth == $this->init_search_depth) {
$best_move = reset($available_moves);
return array('score' => 0, 'best_move' => $best_move);
}
$delta_depth = 0;
} elseif ($moves_qty == 2) {
$delta_depth = 0.4;
} elseif ($moves_qty == 3) {
$delta_depth = 0.55;
} elseif ($moves_qty == 4) {
$delta_depth = 0.8;
}
$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);
if ($next_game_state->isKingUnderAttack()) {
$new_depth = $depth - min(0.2, $delta_depth);
} elseif ($move[3] >= Figure::FIGURE_WEIGHTS[FG_ROOK]) {
$new_depth = $depth - min(0.24, $delta_depth);
} elseif($move[3] > FG_NONE) {
$new_depth = $depth - min(0.34, $delta_depth);
} else {
$new_depth = $depth - $delta_depth;
}
$search_best_move_result = $this->searchBestMove($next_game_state, $new_depth, -$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);
}
Что тут нового? В строке 17 мы сравниваем оставшуюся глубину просмотра$depth не с нулём отношением равенства, а проверяем что эта глубина меньше или равна нулю. Теперь у нас будет "дробная глубина" просмотра, и при очередном изменении глубины, мы можем получить отрицательное число.
В строке 19 мы вызываем новый метод статической оценки позиции: calcStaticScoreEx вместо старого calcStaticScore.
В строке 22 заводим переменную $delta_depth и присваиваем ей значение "1". Здесь будем хранить значение - на сколько будем уменьшать текущую глубину просмотра. У нас сейчас указывается начальная глубина, равная двум. Если $delta_depth = 1, то мы постоим дерево игры на глубину два полухода. А если к примеру $delta_depth = 0.4, т.е. начальное значение "2" будет каждый раз уменьшаться на "0.4", то мы построим дерево игры уже на глубину 5 полуходов.
В строках 23 - 36 мы настраиваем это значение $delta_depth в зависимоси от количества допустимых ходов из текущей позиции. Если есть всего один допустимый ход (строки 24 - 29), проверяем - если текущая (оставшаяся) глубина равна начальной, то просто возвращаем единственный возможный ход как лучший. При этом ставим нулевую оценку позиции, она ни на что не повлияет, т.к. используется только при поиске лучшего хода, а тут мы находимся в самой вершине дерева игры, есть всего один ход, искать нечего. Если мы не в вершине дерева, то обнуляем значение $delta_depth (строка 29), т.е. не уменьшаем глубину просмотра.
Далее, если количество возможных ходов равно "2", то глубину будем уменьшать на "0.4". Если 3 хода, то на "0.55", если 4 - на "0.8". Эти значения я подбирал экспериментально, "от балды", балансируя между скоростью ответа и силой игры алгоритма.
Итак, мы определили минимум, на сколько будем уменьшать текущую глубину просмотра. Но при переборе допустимых ходов могут встречаться разные позиции, и я решил при переборе ещё уточнять на сколько уменьшать глубину просмотра. Это реализовано внутри цикла перебора ходов, в строках 45 - 53. Здесь, уже после совершения очередного хода, окончательно уточняем, какую новую глубину ($new_depth) передадим в следующий рекурсивный вызов метода поиска хода.
Если в результате очередного хода король оказался под атакой (условие в строке 45), то для получения новой текущей глубины, вычитаем из текущей глубины минимум из чисел "0.2" и предыдущей оценкой уменьшения глубины: $new_depth = $depth - min(0.2, $delta_depth);
Поясню. Если король под атакой, мы хотим рассмотреть дерево из этой позиции глубже обычного. Например минимум в пять раз. И вычитать хотим из текущей глубины не единицу, а "0.2". Но что если перед начало цикла перебора ходов у нас был единственный возможный ход? Помните, мы тогда вообще обнуляли сокращение глубины? Т.е. вообще не хотели сокращать перебор. Поэтому из текущей глубины и вычитаем минимум из "0.2" и ранее полученным "сокращением".
Дальше, если король у нас не под шахом, смотрим какая фигура у нас взята в результате хода. Напомню, что в 4-ом элементе хода (индекс 3), т.е. в $move[3] у нас находится "вес" взятой фигуры. В строке 47 условие - "если вес взятой фигуры больше или равен весу ладьи". В этом случае мы тоже хотим глубже обычного рассмотреть дерево игры. И глубину уменьшаем на минимум из числа 0.24 и предыдущего "сокращения".
И далее, аналогично, если король не под шахом, и вес взятой фигуры не достигает веса ладьи, проверяем - если вес взятой фигуры больше "пустой фигуры" (FG_NONE), т.е. если вообще было взятие, то уменьшаем глубину на минимум из "0.34" и $delta_depth. Т.е. если взята лёгкая фигура или пешка, то мы тоже хотим углубить просмотр дерева, хотя и не так сильно, как при взятии тяжёлой фигуры.
Эти числа я тоже подбирал экспериментально, так чтобы и алгоритм играл не слишком слабо, и ответа не приходилось долго ждать.
Ну и последнее изменение - в рекурсивный вызов метода searchBestMove вторым параметром (глубину просмотра) передаём теперь не $depth-1 как раньше, а $new_depth.
Итоги
Играть с алгоритмом стало интереснее, он теперь действует более "агрессивно", если можно так выразиться. Но в общем слабовато. Какие-то варианты он просчитывает глубоко, в других, в случае с "тихими ходами", не видит ловушек. Пробуйте, подбирайте другие коэффициенты, попробуйте реализовать разные эвристики. Хотя-бы даже просто усложнением оценочной функции.
Как обычно, в конце ссылка на исходные коды варианта №16 на github.
И демо игры: Демо №16 игры, выборочные продления, эвристики