Оптимизируем, поле 16*16, взятия до конца

Что дальше?

Сейчас базовая глубина перебора - всего два полухода. Хотя есть выборочные продления, но всё-же хочется более глубокого "гарантированного просмотра". Будем пробовать ускорить (оптимизировать) нашу программу. И возможно будем ещё пробовать какие-то игровые эвристики.

Про оптимизацию

Когда мы хотим ускорить какую-то систему, сначала ищем конкретные места, которые "тормозят", т.е. работают значительно медленне чем всё остальное, или на на выполнение которых тратится в сумме больше времени чем на остальные части системы. После того, как выделили "тормознутые части", надо решить - что с ними делать. И тут я бы выделил два основных вида случаев, которые встречаются. В первом случае есть достаточно простой способ сильно ускорить проблемную часть, немного поменяв алгоритм обработки. Пример - "проблема N+1 запроса".

Проблема "N+1 запроса" возникает когда приложение выполняет множество однотипных запросов к базе данных. Например у нас есть база данных , где хранятся пользователи (users) и их заказы (orders). И например мы получили неким запросом какую-то выборку (множество) пользователей. И нам надо получить все их заказы. Можно пройтись циклом по всем выбранным пользователям, и для каждого запросить его заказы. Если выбранных пользователей - 10000 человек, то для этого понадобится 10000 запросов к базе данных. А можно запросить сразу все заказы для всех выбранных пользователей одним запросом, передав в него идентификаторы выбранных пользователей.

Но такие простые случаи не всегда встречаются, и часто они просто следствие неопытности или лени разработчика. Второй вид случаев - когда алгоритм "некуда" существенно ускорять. Тут приходится иногда кардинально менять организацию данных или архитектуру системы.

Как может выглядеть эволюция какого-нибудь проекта? Сначала его реализуют простым способом, более-менее соблюдая "общепринятие" принципы написания "хорошего кода". Читаемость кода, DRY, KISS, SOLID, исключение "магических чисел", … И проект прекрасно работает. Потом растёт число пользователей и развивается функциональность. Проект начинает тормозить, и люди жалуются на зависания. Проект "закидывают ресурсами", увеличивают количество процессоров, памяти, увеличивают количество серверов (реплик инстансов). Если проект простой, это помогает (на какое-то время).

И вот тут иногда оказывается что нельзя одновременно и выполнить критерии "идеального кода", и сделать быструю систему. Простой и понятный алгоритм, прекрасно работавший с небольшим количеством данных, оказывается совершенно непригодным для большого объёма. А сложный и запутанный алгоритм, справляющийся с большим объёмом, никак не представить "читабельным кодом". Внешние ключи (foreign keys), поддерживающие целостность данных, вдруг становятся причинами жутких тормозов.

Ну это я ушёл "в сторону", отвлёкся. К чему это? К тому, что у нас тут второй случай. Нельзя как-то хитро исправить одно место, и алгоритм вдруг начнёт просматривать дерево игры глубже за приемлемое время.

Что работает дольше всего?

С помощью профилировщика (xDebug + PHP Profiler) я нашёл места кода, которые суммарно выполняются дольше всего. Как и предполагал, это генерация ходов и расширенная оценочная функция - calcStaticScoreEx. Если углубиться, то самыми затратными оказываются методы класса BoardPosition: underAttackByShifts (находится ли поле под атакой по направлениям) и weighedCountAttackByShifts (расчёт взвешенного количества атак по направлениям).

Эти методы не содержат чего-то "тяжёлого", просто выполняются очень много раз. Что можно придумать? Там много раз происходит проверка - "вышли ли мы за пределы доски?" Что если избавиться от этих проверок? Тут надо сделать предупреждение.

Универсальность против скорости

Предупреждение для любителей "сказочных", необычных шахмат. До сих пор наша программа не была "узко заточена" только под классические шахматы. Довольно простыми изменениями можно было сделать доску произвольного размера, добавлять новые виды фигур со своими особенностями ходов и взятий. Но сейчас мы будем пытаться ускорять алгоритм, при этом будем использовать особенности классических шахмат, в частности размер доски 8*8 клеток. Это известная дилемма "универсальность vs скорость". Вы пишите или гибкий, многоцеловой код, который легко адаптировать под разные задачи, или код, оптимизированный под узкую задачу, зато максимально производительный. Универсальность облегчает развитие и поддержку, но иногда критически важна скорость. Как говорится: "амфибия - плохой катер, и хреновый автомобиль".

Поле 16*16

Итак, как можно избавиться от проверок выхода за границы доски? Можно окружить доску "нерабочими клетками". Помните, что цвет поля у нас задаётся двумя битами? Т.е. в каждой клетке записано какое-то значение, которое показывает, что находися в этой клетке. И два младших разряда этого значения показывают цвет фигуры, расположенной в этой клетке:

двоичный вид	десятичный вид	что означает
00	0	в клетке нет фигуры
01	1	в клетке - белая фигура
10	2	в клетке - чёрная фигура

У нас осталось незадействованным ещё одно значение - 0b11. Используем его чтобы отметить клетки, находящиеся "за доской", т.е. за "рабочей областью" доски:

двоичный вид	десятичный вид	что означает
11	3	клетка - за доской

Добавим к нашим константам в файле engine/constants.php ещё две:

define('COLOR_NONE', 0);
define('COLOR_OVER', 0b11); // 3 - флаг выхода за доску

"Рабочую доску" надо окружить минимум двумя рядами клеток с каждой стороны, чтобы при генерации ходов коня не "выскочить" за пределы нового представления доски. Т.е. поле должно быть размером минимум 12 на 12 клеток. Удобнее сделать размер поля кратным степени двойки, т.е. нам подойдёт размер 16 на 16 клеток, при этом "рабочую доску" расположим посередине большого поля. При таком представлении, различные преобразования с клетками можно делать с помощью битовых операций. Итак, будем представлять доску в таком виде:

Представление доски полем 16 на 16 - содержимое полей в начальной позиции

На рисунке показано содержимое массива 16x16 для представления начальной позиции, только вместо кодов фигур показаны картинки этих фигур.

Преобразования представления досок

Поле 16*16 будем представлять в виде одномерного массива с инлексами от 0 до 255. Представление доски в виде поля 16*16 нужно нам только для "внутреннего использования" нашим "движком". Для интерфейса никаких изменений не нужно. Поэтому нам понадобятся преобразование для представления "доски 8*8" в виде "доски 16*16", и обратное преобразование. Надо изменить методы получения индекса столбца из индекса позиции (positionToCol), и индекса строки из индекса позиции (positionToRow). Надо изменить метод получения индекса позиции по индексам строки и столбца (colRowToPositionIndex). Эти методы сейчас у нас находятся в классе Functions. И ещё понадобится преобразование индекса позиции на доске 8*8 в индекс позиции на доске 16*16, и обратно. Понадобится также преобразование представления хода из "16x-представления" в "8x-представление".

Для наглядности вот картинка, где показаны индексы поля 16*16 и внутри "рабочей части" - индексы 8*8:

Представление доски полем 16 на 16 - индексы полей

Итак, открываем файл engine/functions.php, будем делать там изменения. Часто в нашей программе делается проход в цикле по всем полям доски, и используется индекс позиции. Раньше он изменялся от 0 до 63. Теперь понадобятся преобразования. Чтобы не делать вычисления каждый раз в этой частой ситуации, можно просто завести массив преобразования индексов. Добавим его в начало класса, как статическое поле класса:

engine/functions.phpstatic public $pos8To16convert = array(
    68,   69,  70,  71, 72,  73,   74,  75,  
    84,   85,  86,  87, 88,  89,   90,  91,  
    100, 101, 102, 103, 104, 105, 106, 107,  
    116, 117, 118, 119, 120, 121, 122, 123,  
    132, 133, 134, 135, 136, 137, 138, 139,  
    148, 149, 150, 151, 152, 153, 154, 155,  
    164, 165, 166, 167, 168, 169, 170, 171,  
    180, 181, 182, 183, 184, 185, 186, 187
);

Изменяем методы получения индексов колонок и строк из индекса позиции, и получение индекса позиции по индексам колонки и строки:

engine/functions.phpstatic public function positionToCol(int $position_index) {
    return ($position_index & 0b1111) - 4;
}

static public function positionToRow(int $position_index) {
    return ($position_index >> 4) - 4;
}

static public function colRowToPositionIndex($col, $row) {
    return (($row + 4) << 4) + $col + 4;
}

Нужно-ли подробно объяснять эти преобразования? Наверное если Вы добрались до этого места, таких пояснений уже не требуется. Если будут запросы, могу отдельно разобрать эту простую битовую арифметику. Это касается и следующих, новых методов преобразований. Добавим их:

engine/functions.php// Преобразование "индекс поля на доске 16*16" -> "индекс поля на доске 8*8"
static public function pos16ToPos8($pos16) {
    $row = ($pos16 >> 4) - 4;
    $col = ($pos16 & 0b1111) - 4;
    return ($row << 3) + $col;
}

// Преобразование "индекс поля на доске 8*8" -> "индекс поля на доске 16*16"
static public function pos8ToPos16($pos8) {
    return self::$pos8To16convert[$pos8];
}

// Преобразование позиции на доске 16*16 в позицию на доске 8*8
static public function convertPosition16To8($position16) {
    $result = array();
    for ($row = 0; $row < 8; $row++) {
        $i = (($row + 4) << 4) + 4;
        $result[] = $position16[$i];
        $result[] = $position16[$i+1];
        $result[] = $position16[$i+2];
        $result[] = $position16[$i+3];
        $result[] = $position16[$i+4];
        $result[] = $position16[$i+5];
        $result[] = $position16[$i+6];
        $result[] = $position16[$i+7];
    }
    return $result;
}

// Преобразование позиции на доске 8*8 в позицию на доске 16*16
static public function convertPosition8To16($position8) {
    $result = array_fill(0, 256, FG_NONE + COLOR_OVER);
    foreach(self::$pos8To16convert as $index8 => $index16) {
        $result[$index16] = $position8[$index8];
    }
    return $result;
}

// Преобразование структуры допустимых ходов из формата с индексами полей на доске 16*16 в формат с индексами полей на доске 8*8 
static public function convertMoves16To8($moves) {
    $result = array();
    foreach ($moves as $pos_from_16 => $moves_16) {
        $pos_from_8 = self::pos16ToPos8($pos_from_16);
        $result[$pos_from_8] = array();
        foreach($moves_16 as $to_16) {
            $result[$pos_from_8][] = self::pos16ToPos8($to_16);
        }
    }
    return $result;
}

Изменения для работы с полем 16*16

Пройдёмся коротко по изменениям, связанным с новым представлением поля.

Контроллер обработки хода человека

Скрипт make_move.php обрабатывает ходы человека. Он принимает индексы клеток "откуда" и "куда" в поле 8*8, а наш движок теперь будет работать с полем 16*16. Тут потребуется всего лишь добавить преобразование "pos8ToPos16" в двух строках, которые принимают post-параметры:

make_move.php$cell_index_from = Functions::pos8ToPos16( intval($_POST['cell_index_from']) );
$cell_index_to = Functions::pos8ToPos16( intval($_POST['cell_index_to']) );

Генератор ходов

В генераторе ходов (в файле engine/move_generator.php) в методе generateAllMovesFlat в основном цикле, мы проходим по всем полям доски. Вот так начинался цикл:

engine/move_generator.phpfor($i = 0; $i < BOARD_SIZE * BOARD_SIZE; $i++) {

Теперь нам так же надо пройти по всей доске, но индекс поля будет изменяться не от 0 до 63. Теперь работаем в поле 16*16, а пройти надо только по "рабочей части" поля. Индексы рабочей части поля мы уже собрали в массиве $pos8To16convert. Теперь начало цикла будет выглядеть так:

engine/move_generator.phpforeach (Functions::$pos8To16convert as $i) {

Эта одна строка - это всё, что нужно изменить в генераторе ходов. Далее, в нём вызываются методы генерации ходов (getAvailableMoves) классов конкретных фигур. Вот ими и займёмся.

Классы фигур

Классы коня, слона, ферзя и ладьи

У нас каждые допустимые смещения фигур представлялись в виде массива - отдельно указывались смещения для горизонтали и вертикали. Теперь нам не нужно контролировать выход за границы доски, и каждое допустимое смещение для фигур можно представить одним числом - на сколько изменяется индекс поля. Например, смещение "вправо" увеличивает индекс поля на единицу, "влево" - уменьшает на единицу. Смещение "вниз" - увеличивает на 16, а "вверх" - уменьшает на 16.

У коня, слона, ферзя и ладьи простая логика перемещений. В их классах надо просто изменить константы допустимых смещений. Так эта константа будет выглядеть у коня:

engine/figures/knight.phpconst SHIFTS = array(-33, -31, -18, -14, 14, 18, 31, 33);

Получилось даже гораздо компактнее чем было! Для слона:

engine/figures/bishop.phpconst SHIFTS = array(-17, -15, 15, 17);

Для ферзя:

engine/figures/queen.phpconst SHIFTS = array(-17, -16, -15, -1, 1, 15, 16, 17);

Для ладьи, кроме допустимых смещений, надо изменить ещё индексы начальных позиций всех четырёх ладей. Индексы удобно можно посмотреть чуть выше, на картинке индексы полей на доске 16*16. Вот такие будут изменённые строки в классе ладьи:

engine/figures/rook.phpconst WHITE_KING_ROOK_INIT_POSITION = 187;
const WHITE_QUEEN_ROOK_INIT_POSITION = 180;
const BLACK_KING_ROOK_INIT_POSITION = 75;
const BLACK_QUEEN_ROOK_INIT_POSITION = 68;
const SHIFTS = array(-16, -1, 1, 16);

Класс короля

Открываем файл с классом короля: engine/figures/king.php. Своих допустимых смещений тут нет, мы используем смещения ферзя. Изменяем индексы полей, по которым проходят оба короля при рокировках (опять для преобразований индексов пользуемся картинкой):

engine/figures/king.php// индексы полей между королём и ладьёй. Порядок важен! От короля - до ладьи
const FIELDS_CASTLING_WHITE_KING = array(185, 186);
const FIELDS_CASTLING_WHITE_QUEEN = array(183, 182, 181);
const FIELDS_CASTLING_BLACK_KING = array(73, 74);
const FIELDS_CASTLING_BLACK_QUEEN = array(71, 70, 69);

Ещё изменяем индексы начальных позиций короля:

engine/figures/king.phpconst FIELD_INIT_WHITE = 184; // начальная позиция белого короля
const FIELD_INIT_BLACK = 72; // начальная позиция чёрного короля

Дальше - микроулучшение в методе getAvailableMoves. В конце цикла где проверяются "обычные перемещения", есть такая строка:

$moves[] = array($this->position_index, $to_index, $king_figure_weight, $beat_figure_weight);

В ней используется переменная $king_figure_weight. Но можно использовать поле класса figure_weight, оно-же заполняется в общем конструкторе класса Figure, а мы как раз и находимся в классе короля, чей "вес" нам и нужен. Так что теперь строка будет выглядеть так:

$moves[] = array($this->position_index, $to_index, $this->figure_weight, $beat_figure_weight);

А эту строку (выше строк на 15) теперь можно удалить:

$king_figure_weight = self::FIGURE_WEIGHTS[FG_KING];

Последнее, что надо исправить в классе короля - метод makeMove. В начале метода удаляем строку:

$col = $this->col;

И приведу кусок кода из конца метода, где красным выделены удалённые строки, и зелёным - добавленные:

engine/figures/king.php$to_col = Functions::positionToCol($to_cell_index);
if (abs($col - $to_col) == 2) {
if (abs($this->position_index - $to_cell_index) == 2) {
    // вертикаль изменилась на 2, значит это рокировка, надо передвинуть ладью
    if ($to_col == self::TO_COLUMN_CASTLING_KING) {
        // короткая рокировка (на королевский фланг)
        $rook_from_position = Functions::colRowToPositionIndex(BOARD_SIZE-1, $this->row);
        $rook_from_position = $this->position_index + 3;
        $rook_to_position = $to_cell_index - 1;
    } else {
        // длинная рокировка (на ферзевый фланг)
        $rook_from_position = Functions::colRowToPositionIndex(0, $this->row);
        $rook_from_position = $this->position_index - 4;
        $rook_to_position = $to_cell_index + 1;
    }
    $this->game_state->position[$rook_from_position] = FG_NONE;
    $this->game_state->position[$rook_to_position] = FG_ROOK + $this->color;
}
return true;

Класс пешки

Самая "сложная" фигура - пешка. Да, я знаю, что часть шахматного мира не считает пешку фигурой, но в рамках сайта, я отношу пешку тоже к фигурам. Открываем файл engine/figures/pawn.php с классом пешки. Забегу чуть вперёд - в общем классе фигур мы уберём в конструкторе класса заполнение поля $row с индексом горизонтали. Этот индекс был нужен всем фигурам для проверки выхода за границы доски. Теперь это не нужно. Но для пешек по прежнему важна горизонталь, на которой они расположены. Так что добавим индекс горизонтали, и его заполнение в класс пешки. В начале класса пишем:

engine/figures/pawn.phpprotected int $row; // индекс строки положения пешки

public function __construct(GameState $game_state, int $position_index) {
    parent::__construct($game_state, $position_index);
    $this->row = Functions::positionToRow($position_index);
}

Изменим метод getCandidateMoves. Недалеко от начала метода, удалим следующие строки:

$last_row = 0;

$last_row = 7;

if ($this->row === $last_row) {
    throw new Exception('Pawn in last row');
}

Дальше делаем такие замены в коде, где проверяется возможность хода пешки (красные строки - то что удаляем, зелёные - то что пишем вместо красных):

// проверим поле перед пешкой
$row = $this->row + $direction;
$to_index = Functions::colRowToPositionIndex($this->col, $row);
$to_index = $this->position_index + $direction * 16;

// пешка находится на начальной позиции, проверим ещё одно поле "вперёд"
$row = $this->row + $direction;
$to_index = Functions::colRowToPositionIndex($this->col, $row);
$to_index += $direction * 16;

И, далее - замены в коде, где проверяются возможности взятия:

engine/figures/pawn.php, getCandidateMoves// теперь проверим возможность взятий
$row = $this->row + $direction;
$col = $this->col - 1;
if ($col >= 0) {
    $to_index = Functions::colRowToPositionIndex($col, $row);
    $to_figure = $this->game_state->position[$to_index];
    if (Functions::color($to_figure) === $this->enemy_color || $to_index === $this->game_state->crossed_field) {
        $moves[] = $to_index;
    }
}
// теперь проверим возможность взятий, сначала - влево
$to_index = $this->position_index + $direction * 16 - 1;
$to_figure = $this->game_state->position[$to_index];
if (Functions::color($to_figure) === $this->enemy_color || $to_index === $this->game_state->crossed_field) {
    $moves[] = $to_index;
}
$col = $this->col + 1;
if ($col < BOARD_SIZE) {
    $to_index = Functions::colRowToPositionIndex($col, $row);
    $to_figure = $this->game_state->position[$to_index];
    if (Functions::color($to_figure) === $this->enemy_color || $to_index === $this->game_state->crossed_field) {
        $moves[] = $to_index;
        }
}
// теперь взятие вправо
$to_index = $this->position_index + $direction * 16 + 1;
$to_figure = $this->game_state->position[$to_index];
if (Functions::color($to_figure) === $this->enemy_color || $to_index === $this->game_state->crossed_field) {
    $moves[] = $to_index;
}
return $moves;

Ну и последнее мелкое изменение в классе пешки - в методе makeMove. В начале метода стоит присвоение:

$row = $this->row;

Я его перенёс ниже, поставил перед строкой $this->game_state->non_action_semimove_counter = 0;, т.к. выше эта переменная не нужна. А в начале метода я запомнил исходную позицию пешки:

$from_cell_index = $this->position_index;

И в части кода, где пешка идёт на два поля вперёд, там где мы запоминаем пересечённое поле, такие изменения:

// пешка перескочила поле, пометим его как проходное, т.е. доступное для взятия пешкой оппонента
$this->game_state->crossed_field = Functions::colRowToPositionIndex($this->col, $row + $direction);
$this->game_state->crossed_field = $from_cell_index + $direction * 16;

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

Общий класс фигур

Открываем файл engine/figure.php с общим классом фигур. Раньше нам надо было знать, на какой горизонтали и вертикали расположена фигура, чтобы при генерации ходов проверять выход за пределы доски. Теперь это не нужно, и смещения задаются не парой чисел "смещение по горизонтали, смещение по вертикали", а одним числом - "изменение индекса позиции". Так что индексы горизонтали и вертикали стали не нужны. Удаляем поля класса:

protected int $col; // индекс колонки положения фигуры
protected int $row; // индекс строки положения фигуры

В конструкторе удаляем заполнение этих полей:

$this->col = Functions::positionToCol($position_index);
$this->row = Functions::positionToRow($position_index);

Изменяем метод getLongRangeCandidateMoves поиска возможных "длинных" ходов по направлениям:

engine/figure.phppublic function getLongRangeCandidateMoves(array $shifts) {
    $moves = array();
    foreach ($shifts as $shift) {
        list($shift_col, $shift_row) = $shift;
        $continue_shift = true;
        $col = $this->col;
        $row = $this->row;
        $to_index = $this->position_index;
        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;
            }
            $to_index = Functions::colRowToPositionIndex($col, $row);
            $to_index += $shift;
            $to_figure = $this->game_state->position[$to_index];
            if ($to_figure === FG_NONE) {
                $moves[] = $to_index;
                continue;
            }
            $to_figure_color = Functions::color($to_figure);
            if ($to_figure_color == $this->enemy_color) {
                $moves[] = $to_index;
            }
            $continue_shift = false;
        }
    }
    return $moves;
}

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

Ну и похожие изменения делаем в методе поиска "коротких ходов" по направлениям. Приведу готовый код метода, без подсвечивания новых и удалённых строк:

engine/figure.phppublic function getShortRangeCandidateMoves(array $shifts) {
    $moves = array();
    foreach($shifts as $shift) {
        $to_index = $this->position_index + $shift;
        $to_color = Functions::color($this->game_state->position[$to_index]);
        if ($to_color == COLOR_NONE || $to_color == $this->enemy_color) {
            $moves[] = $to_index;
        }
    }
    return $moves;
}

Класс состояния игры

Теперь изменим класс состояния игры (в файле engine/game_state.php). Что мы хотим? Хотим "внутри программы" оперировать представлением доски на поле 16*16, но при этом хотим оставить без изменения формат представления состояния игры в хранилище (в сессии). Для этого надо каждый раз при записи в хранилище, и при чтении из хранилища делать соответствующие преобразования представлений доски и ходов.

Для порядка, изменим комментарий к полю класса $position:

public $position = null; // массив из 256 элементов (64 "полезных") - положение фигур на доске

Изменим теперь метод serializeState. Он представляет состояние игры вместе с историей в виде json-строки. До изменений он выглядит так:

engine/game_state.phppublic function serializeState() {
    $data = array(
        'state' => $this->getHash(),
        'history' => $this->state_history
    );
    return json_encode($data, JSON_UNESCAPED_UNICODE);
}

Теперь нам надо преобразовать позиции, в том числе те, которые находятся в "истории" из представления 16*16 в представление 8*8. Также надо сделать это преобразование для полей предыдущего хода - "откуда" и "куда", и для пересечённого пешкой поля. Вот так теперь будет выглядеть метод:

engine/game_state.phppublic function serializeState() {
    $state = $this->getHash();
    $state['position'] = Functions::convertPosition16To8($state['position']);
    $fields_to_convert = array('crossed_field', 'prev_move_from', 'prev_move_to');
    foreach($fields_to_convert as $field) {
        if (!is_null($state[$field])) {
            $state[$field] = Functions::pos16ToPos8($state[$field]);
        }
    }

    $state_history = $this->state_history;
    foreach($state_history as $i => $history) {
        $state_history[$i]['position'] = Functions::convertPosition16To8($history['position']);
        foreach($fields_to_convert as $field) {
            if (!is_null($state_history[$i][$field])) {
                $state_history[$i][$field] = Functions::pos16ToPos8($state_history[$i][$field]);
            }
        }
    }
    $data = array(
        'state' => $state,
        'history' => $state_history
    );
    return json_encode($data, JSON_UNESCAPED_UNICODE);
}

Далее, переписываем метод unserializeState. Это обратный по функционалности метод. Он принимает json-строку, и заполняет состояние игры. Там нужны обратные преобразования - из представления 8*8 в представление 16*16:

engine/game_state.phppublic function unserializeState(string $serialized_state) {
    $fields_to_convert = array('crossed_field', 'prev_move_from', 'prev_move_to');
    try {
        $data = json_decode($serialized_state, true);
        $this->state_history = $data['history'];
        foreach($this->state_history as $i => $history) {
            $this->state_history[$i]['position'] = Functions::convertPosition8To16($history['position']);
            foreach($fields_to_convert as $field) {
                if (!is_null($this->state_history[$i][$field])) {
                    $this->state_history[$i][$field] = Functions::pos8ToPos16($this->state_history[$i][$field]);
                }
            }
        }
        foreach (self::PROPERTY_NAMES as $key) {
            $this->$key = $data['state'][$key];
        }
        $this->position = Functions::convertPosition8To16($this->position);
        foreach($fields_to_convert as $field) {
            if (!is_null($this->$field)) {
                $this->$field = Functions::pos8ToPos16($this->$field);
            }
        }
        $this->recalculatePositionHashes();
        return true;
    } catch(Exception $e) {
        return false;
    }
}

Далее, в паре методов у нас есть такая строка:

for($i = 0; $i < BOARD_SIZE*BOARD_SIZE; $i++) {

Это объявление цикла перебора клеток доски. Теперь эти строки надо заменить на перебор только рабочих клеток поля 16*16, вот так:

foreach(Functions::$pos8To16convert as $i) {

Оценочная функция, ускорение мата

Сейчас изменим оценочную "расширенную" функцию calcStaticScoreEx. В процессе тестирования, я заметил забавный момент. Компьютер получил подавляющее преимущество, у меня остался король и несколько заблокированных пешек. В логах видно что программа оценивает свою позицию максимальным числом. Это значит, что моё поражение неминуемо. Я и сам уже вижу мат в один ход. …

Но компьютер ходит ладьёй "где-то там", далеко от моего короля, мат не ставит. Я хожу королём. Комьютер опять ходит ладьёй, возвращает её на место, где она была ход назад. "Так!", думаю, "Какой-то баг". Возвращаю короля. Ладья опять повторяет ход. И я повторяю ход короля. Третий раз ладья ход не повторила. Это привело бы к ничьей по правилу троекратного повтора. А зачем компьютеру ничью с нулевой оценкой если у него есть оценка - "максимальное целое число в php". Поэтому он ход не повторил, он пошёл ладьёй через поле, потом возвратил назад, потом опять повторил, потом пошёл ещё через одно поле, … Так мы скакали много ходов, пока наконец компьютер не поставил мне мат. Хотя мог бы сделать это гораздо раньше.

Объяснение такого поведения очень простое. Вспомним, как компьютер выбирает ход. Он берёт упорядоченный список всех возможных ходов, перебирает их, и когда какой-то ход улучшает оценку позиции, этот ход помечается как лучший. В нашем случае, он взял первый ход (ладьёй) из списка, оценил позицию после этого хода, она оказалась максимально возможной. "Ага, запоминаем это ход как лучший" - подумал комп, и стал перебирать остальные ходы. Остальные ходы не улучшили оценку, потому что "ну а куда уж выше масимальной!". В итоге был выбран не тот ход, после которого сразу получался мат, а первый попавшийся, после которого мат тоже был неизбежен, но не сразу, ~~а семь веков спустя~~.

Как это исправить? Можно учитывать глубину просмотра при оценке позиции. Вычитать эту глубину из максимального числа если нашли мат. Таким образом получим что позиция с матом через один ход будет оценена выше чем позиция с матом через два хода. Итак, в метод оценки позиции добавляем необязательный параметр $deep, с нулевым значением по умолчанию:

public function calcStaticScoreEx($no_available_moves, $deep=0) {

И через две строчки ниже, где оказывается что в позиции объявлен мат текущему игроку, возвращаем минимальное целое число, добавив к нему глубину:

return PHP_INT_MIN + $deep;

Дальше, массив с ценностью продвижения пешек, расширяем до 256 элементов. С помощью отступов я сделал наглядное представление, удобное для чтения:

engine/game_state.php// ценность продвижения пешек
$pawn_position_weigths = array(
    0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0,
    0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0,
    0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0,
    0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0,

    0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0,
    0, 0, 0, 0,   65,70,70,70,70,70,70,65,    0, 0, 0, 0,
    0, 0, 0, 0,   50,55,60,65,65,60,55,50,    0, 0, 0, 0,
    0, 0, 0, 0,   36,40,48,50,50,48,40,36,    0, 0, 0, 0,
    0, 0, 0, 0,   18,20,24,36,36,24,20,18,    0, 0, 0, 0,
    0, 0, 0, 0,   10,10,10,10,10,10,10,10,    0, 0, 0, 0,
    0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0,
    0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0,

    0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0,
    0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0,
    0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0,
    0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0
);

Дальше, изменим блок метода под комментарием // Наши фигуры (белые) хотим расположить ближе к королю противника. Там есть несколько вызовов Functions::positionToRow и Functions::positionToCol. Мы пытаемся ускорить часто выполняющиеся части кода, поэтому вместо этих вызовов я подставил прямые вычисления битовыми операциями. Причём номера горизонталей и вертикалей не стал приводить в доске 8*8, оставил их в координатах 16*16. Например поле A8 в координатах 8*8 имеет нулевую горизонталь и нулевую вертикаль, а в координатах 16*16 индексы горизонтали и вертикали равны 4. Эти числа потом используются только при вычислении разности координат, поэтому не нужно тратить лишнее действие, приводя их к координатам 8*8.

Точно такие-же изменения будут в блоке ниже, под комментарием // А нашего (белого) короля хотим расположить подальше от фигур противника. В итоге получатся такие изменения:

engine/game_state.php// Наши фигуры (белые) хотим расположить ближе к королю противника
$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);
$black_king_row_norm = $black_king_position >> 4;
$black_king_col_norm = $black_king_position & 0b1111;
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); // минус - т.к. чем больше дистанция, тем нам (белым) хуже
        $row_norm = $position >> 4;
        $col_norm = $position & 0b1111;
        $square_distance -= pow($black_king_row_norm - $row_norm, 2) + pow($black_king_col_norm - $col_norm, 2); // минус - т.к. чем больше дистанция, тем нам (белым) хуже
    }
}

// А нашего (белого) короля хотим расположить подальше от фигур противника
$white_king_position = $this->getKingPosition(COLOR_WHITE);
$white_king_row = Functions::positionToRow($white_king_position);
$white_king_col = Functions::positionToCol($white_king_position);
$white_king_row_norm = $white_king_position >> 4;
$white_king_col_norm = $white_king_position & 0b1111;
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); // чем больше дистанция тем нам (белым) лучше
        $row_norm = $position >> 4;
        $col_norm = $position & 0b1111;
        $square_distance += pow($white_king_row_norm - $row_norm, 2) + pow($white_king_col_norm - $col_norm, 2); // чем больше дистанция тем нам (белым) лучше
    }
}

Класс игры

Открываем файл engine/chess_game.php. Изменим метод, отдающий начальное заполение поля, он теперь будет выглядеть так:

engine/chess_game.phpprivate function getInitPosition() {
    # FG_NONE+COLOR_OVER = 3 - поле за доской
    # FG_PAWN+COLOR_BLACK = 24 + 2 = 26 - чёрная пешка
    # FG_PAWN+COLOR_WHITE = 24 + 1 = 25 - белая пешка
    # Аналогично FG_ROOK = 12 - ладья без цвета, к ней прибавляется цвет: 1 - белый, 2 - чёрный
    # FG_KNIGHT = 20 - конь, FG_BISHOP = 16 - слон, FG_QUEEN = 8 - ферзь, FG_KING = 4 - король
    return array(
        3, 3, 3, 3,     3,  3,  3,  3,  3,  3,  3,  3,    3, 3, 3, 3,
        3, 3, 3, 3,     3,  3,  3,  3,  3,  3,  3,  3,    3, 3, 3, 3,
        3, 3, 3, 3,     3,  3,  3,  3,  3,  3,  3,  3,    3, 3, 3, 3,
        3, 3, 3, 3,     3,  3,  3,  3,  3,  3,  3,  3,    3, 3, 3, 3,

        3, 3, 3, 3,    14, 22, 18, 10,  6, 18, 22, 14,    3, 3, 3, 3,
        3, 3, 3, 3,    26, 26, 26, 26, 26, 26, 26, 26,    3, 3, 3, 3,
        3, 3, 3, 3,     0,  0,  0,  0,  0,  0,  0,  0,    3, 3, 3, 3,
        3, 3, 3, 3,     0,  0,  0,  0,  0,  0,  0,  0,    3, 3, 3, 3,
        3, 3, 3, 3,     0,  0,  0,  0,  0,  0,  0,  0,    3, 3, 3, 3,
        3, 3, 3, 3,     0,  0,  0,  0,  0,  0,  0,  0,    3, 3, 3, 3,
        3, 3, 3, 3,    25, 25, 25, 25, 25, 25, 25, 25,    3, 3, 3, 3,
        3, 3, 3, 3,    13, 21, 17,  9,  5, 17, 21, 13,    3, 3, 3, 3,

        3, 3, 3, 3,     3,  3,  3,  3,  3,  3,  3,  3,    3, 3, 3, 3,
        3, 3, 3, 3,     3,  3,  3,  3,  3,  3,  3,  3,    3, 3, 3, 3,
        3, 3, 3, 3,     3,  3,  3,  3,  3,  3,  3,  3,    3, 3, 3, 3,
        3, 3, 3, 3,     3,  3,  3,  3,  3,  3,  3,  3,    3, 3, 3, 3
    );
}

Я тут написал числа, вместо использования констант. Посчитал, что это будет совсем не читабельно - 256 сумм констант.

В методе makeMove, в 4-ой строке тела метода, упростим условие:

if ($figure_code === FG_NONE || Functions::color($figure_code) != $color) {
if (Functions::color($figure_code) != $color) {

Метод getClientJsonGameState отдаёт состояние игры для фронтового javascript-приложения, для которого формат данных должен остаться прежним. Поэтому делаем в методе такие изменения:

engine/chess_game.phpreturn array(
    'position' =>$this->game_state->position,
    'position' => Functions::convertPosition16To8($this->game_state->position),
    'is_human_move' => $is_human_move,
    'human_color' => ($this->game_state->human_color == COLOR_BLACK ? 'b' : 'w'),
    'move_number' => $this->game_state->move_number,
    'prev_move_from' => $this->game_state->prev_move_from,
    'prev_move_to' => $this->game_state->prev_move_to,
    'prev_move_from' => is_null($this->game_state->prev_move_from) ? null : Functions::pos16ToPos8($this->game_state->prev_move_from),
    'prev_move_to' => is_null($this->game_state->prev_move_to) ? null : Functions::pos16ToPos8($this->game_state->prev_move_to),
    'text_state' => $this->game_state->text_state,
    'available_moves' => $is_human_move ? $this->generateAvailableMoves() : array()
    'available_moves' => $is_human_move ? Functions::convertMoves16To8($this->generateAvailableMoves()) : array()
);

Класс BoardPosition

В классе BoardPosition большой объём изменений, хотя эти изменения простые и однотипные. Я не буду приводить их здесь. Можно просто забрать готовый код из github-а, или самому сделать изменения. Эти изменения связаны с методами, определяющими, находитсяли поле под атакой, под атакой коня, пешки, под линейной атакой, с методами, вычисляющими фактор атаки, "взвешенные количества атак".

Изменения там однотипны: замена пары "горизонталь и вертикаль" на переменную "индекс поля 16*16", и удаление проверок на выход за границы доски.

Итоги оптимизации полем 16*16

После описанных изменений, скорость перебора возросла в среднем примерно на 500 позиций в секунду. Да, ускорение есть. Но этого всё равно недостаточно для увеличения глубины перебора, чтобы компьютер отвечал за комфортное для игры время.

Продления взятий до конца

Попробуем улучшить игру просматривая все взятия до конца. Поясню … Мы ищем "лучший" ход рекурсивным методом searchBestMove (в классе ComputerAIV1). Когда мы доходим до максимальной глубины просмотра, мы оцениваем позицию с помощью оценочной функции calcStaticScoreEx класса состояния игры. Идея состоит в том, чтобы оценку позиции проводить другим, новым методом. Назовём его getForceScore. Он также, как и searchBestMove будет рекурсивно вызывать себя, использовать альфа-бета отсечение, но будет рассматривать не все ходы, а только взятия, причём без ограничения глубины. И только дойдя до позиции, где нет взятий, будем возвращать оценку этой позиции всё той-же оценочной функцией calcStaticScoreEx. И этой-же оценочной функцией будем получать начальную оценку позиции.

Также напомню, что мы ввели новый необязательный параметр в оценочной функции - $deep для предотвращения затягивания мата. Приведу полный код метода searchBestMove с отмеченными изменениями:

engine/computer_ai_v1.phpprivate function searchBestMove(GameState $game_state, $depth, $alpha, $beta, $current_depth=0) {
    if ($game_state->checkDraw()) {
        return array('score' => 0, 'best_move' => null);
    }
    if ($depth < 0) {
        return array('score' => $this->getForceScore($game_state, $alpha, $beta, $current_depth+1), '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) {
    if ($no_available_moves) {
        $this->position_counter += 1;
        return array('score' => $game_state->calcStaticScoreEx($no_available_moves, $current_depth), '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);
        $next_game_state->makeMove($move[0], $move[1], false);

        if ($next_game_state->isKingUnderAttack()) {
            $new_depth = $depth - min(0.2, $delta_depth);
            $new_depth = $depth - min(0.3, $delta_depth);
        } elseif ($move[3] >= Figure::FIGURE_WEIGHTS[FG_ROOK]) {
            $new_depth = $depth - min(0.24, $delta_depth);
            $new_depth = $depth - min(0.35, $delta_depth);
        } elseif($move[3] > FG_NONE) {
            $new_depth = $depth - min(0.34, $delta_depth);
            $new_depth = $depth - min(0.45, $delta_depth);
        } else {
            $new_depth = $depth - $delta_depth;
        }
        $search_best_move_result = $this->searchBestMove($next_game_state, $new_depth, -$beta, -$alpha, $current_depth+1);
        $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);
}

В определение метода searchBestMove, и в его вызов (на строке 54) добавили параметр - "текущую глубину просмотра". Также добавили эту текущую глубину в вызов оценочной функции в строке 15

В строках 43-50 я немного изменил значения на сколько уменьшать оставшуюся глубину. Эти знначения подобрал экспериментально, как компромис между качеством игры и скоростью ответа.

Ну и главное изменение - в начале метода, в строке 6. Если мы "выбрали" всю допустимую глубину просмотра, то возвращаем оценку позиции. А оцениваем её вызовом нового метода getForceScore, который сейчас напишем.

Ещё в начале метода getGenerateMove я увеличил лимит времени на ответ c 50 до 90 секунд:

set_time_limit(90);

Ну и в вызов метода searchBestMove добавил ноль в качестве последнего параметра (текущая глубина, нужная для не-затягивания мата).

Добавим теперь новый метод оценки позиции с форсированными взятиями:

engine/computer_ai_v1.php/**
* Метод оценивает позицию делая только ходы - взятия без ограничения глубины
*/
private function getForceScore(GameState $game_state, $alpha, $beta, $current_depth) {
    $move_generator = new MoveGenerator($game_state);
    $available_moves = $move_generator->generateSortedMoves();
    $no_available_moves = (count($available_moves) === 0);

    $this->position_counter += 1;
    $score = $game_state->calcStaticScoreEx($no_available_moves, $current_depth);
    if ($no_available_moves) {
        return $score;
    }

    if ($score > $alpha) {
        $alpha = $score;
    }
    if ($alpha > $beta) {
        return $alpha;
    }
    foreach ($available_moves as $move) {
        if ($move[3] == 0) {
            continue;
        }
        $next_game_state = clone $game_state;
        $next_game_state->makeMove($move[0], $move[1], false);
        $tmp_score = - $this->getForceScore($next_game_state, -$beta, -$alpha, $current_depth+1);
        if ($tmp_score > $alpha) {
            $alpha = $tmp_score;
        }
        if ($alpha >= $beta) {
            return $alpha;
        }
    }
    return $alpha;
}

Структура метода такая-же, как у searchBestMove. Сначала получаем все возможные ходы из текущей позиции. В строке 10 получаем оценку $score текущей позиции с помощью оценочной функции calcStaticScoreEx.

Если возможных ходов нет, то сразу возвращаем оценку $score (строка 12). Если $score больше альфа-границы, то $score становится новым значением альфы (строка 16). Если альфа превысила бету, то дальше нет смысла искать, возвращаем альфу (строка 19).

В строке (строка 21) начинаем цикл по возможным ходам. В строке 22 проверяем вес взятой фигуры. Если он нулевой, т.е. этот ход - не взятие, то идём на следующую итерацию цикла, нам тут надо рассматривать только взятия.

Делаем ход на склонированном состоянии игры, и получаем оценку полученной позиции рекурсивным вызовом метода getForceScore, который сейчас и рассматриваем. Далее, если полученная оценка выше альфа, то альфу меняем на значение этой оценки. И если альфа превысила бету, делаем отсечку, возвращаем альфу. И в конце метода, если добрались до него, возвращаем альфу.

Итоги

Мы попробовали оптимизировать методы, работающие с доской. Скорость перебора позиций удалось увеличить. Примерно на 500 оцененных позиций в секунду. Этого недостаточно для увеличения глубины перебора без увеличения времени на ответ. Ну что-ж, не все опыты "одинаково успешны".

Еще мы стали оценивать позиции при переборе просматривая все взятия до конца. И, "по ощущениям", это немного увеличило эффективность альфа-бета отсечения, которая сильно просела после введения расширенной оценочной функции на предыдущем шаге (в 16-ой версии).

Я пробовал играть другой, сторонней программой на разных уровнях с нашим алгоритмом. Наш алгоритм уверенно выигрывает у сторонней программы на уровне 6, который соответствует примерно ELO=1435. Но проигрывает на уровне 7, который соответствует ELO=1526.

Вот здесь можно сразиться с алгоритмом, Демо №17 игры

А здесь - исходные коды варианта №17 на github.