Шахматы на php и javascript: Битовые доски

Попробуем по другому

В предыдущей статье мы пытались ускорить работу "шахматного ИИ", экономя на проверках выхода за пределы доски. Для этого стали представлять доску полем 16*16 клеток, расположив "рабочую область" доски посередине этого поля. Программа стала оценивать на 500 позиций в секунду больше. Но для нашей задачи это совсем незначительная величина. Ещё мы добавили просмотр взятий до конца, и это увеличило немного силу игры программы.

Что делать дальше? До этого мы постоянно развивали предыдущую версию программы. Но теперь, думаю, надо отбросить вариант с полем 16*16, и попробовать другое представление доски.

Идея битовых досок

На шахматной доске 64 клетки. И в современных компьютерах используется 64-битное представление числа. Какое удобное совпадение! Это позволяет использовать битовые доски (bitboards) - такое представление доски, когда каждому полю соответствует один бит. Вся позиция кодируется с помощью нескольких 64-битных (8-байтных) чисел. Каждое число (каждый bitboard) будет соответствовать своему набору фигур (например всем белым пешкам). Схема проста - если в поле есть фигура - в соответствующем бите хранится единица, нет фигуры - ноль.

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

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

На этот раз я не буду показывать здесь и комментировать каждую добавленую или изменённую строчку кода. Их слишком много. Исходники кода есть, ссылку, как обычно, укажу в конце статьи. Раз Вы дошли этого места, наверное уже умеете разбираться в чужом коде (а это - важный навык в программировании). И вообще, на этом уровне не так важен исходный код, как понимание идеи, структур данных.

Итак, положение на доске каждого вида фигур, каждого цвета, будем хранить в одном числе. Т.е. все чёрные пешки - одно число. Все белые пешки - другое число. Все чёрные ладьи - ещё одно число, и т.д. Т.е. вся позиция будет представлена в виде 12 чисел.

На рисунке ниже - пример битовой доски для чёрных ладей в начальном положении. Самый младший (правый) бит числа соответствует полю h1, а самый старший - полю a8.

Ниже схематично изображены все 12 битовых досок с фигурами в начальном положении. Эту схему я взял с википедии. На ней очень наглядно показана идея представления позиции с помощью двенадцати чисел (битовых досок).

Обозначения, преобразование позиции в битовые доски

Здесь - исходные коды шахмат, использующие bitboards. Для понимания кода Вам надо хорошо ориентироваться в двоичной логике, в простых битовых операциях (И, ИЛИ, НЕ).

Откройте класс состояния игры (в файле engine/game_state.php). Битовые доски там определены как поля класса:

engine/game_state.php// bitboard для всех типов фигур для обоих цветов
public $m_w_pawn = null;
public $m_b_pawn = null;
public $m_w_king = null;
public $m_b_king = null;
public $m_w_queen = null;
public $m_b_queen = null;
public $m_w_knight = null;
public $m_b_knight = null;
public $m_w_bishop = null;
public $m_b_bishop = null;
public $m_w_rook = null;
public $m_b_rook = null;

public $m_all_white_figures = null;
public $m_all_black_figures = null;
public $all_figures_mask = null;
public $m_crossed_field = 0;

Здесь, и далее, в других местах кода, начальная буква "m" в имени переменной обозначает "mask", т.е. в этой переменной хранится какая-то битовая маска.

Далее, после подчёркивания, буквы "w" или "b" в имени переменной обозначают цвет - белый (white) или чёрный (black). Далее идёт тип фигуры. Например в поле с именем $m_b_bishop будем хранить битовую маску с положением всех чёрных слонов.

Также, как видите в строках 15 - 18, иногда будем использовать маски, в которых будут сразу все белые фигуры, все чёрные фигуры, вообще все фигуры, и будет маска для "пересечённого поля" при ходе пешки на два поля вперёд.

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

На картинке ниже - пример битовой маски для поля d1, изображённой прямо на полях доски:

Загрузка позиции

В хранилище состояние игры по прежнему хранится в старом виде. Позиция там представляется массивом, где индекс меняется от нуля (A8), до 63 (H1). При загрузке игры, надо взять этот старый формат и заполнить битовые доски. Такое заполнение делается методом setPosition класса состояния игры:

engine/game_state.phppublic function setPosition($position) {
    $this->m_w_pawn = 0;
    $this->m_b_pawn = 0;
    $this->m_w_king = 0;
    $this->m_b_king = 0;
    $this->m_w_queen = 0;
    $this->m_b_queen = 0;
    $this->m_w_knight = 0;
    $this->m_b_knight = 0;
    $this->m_w_bishop = 0;
    $this->m_b_bishop = 0;
    $this->m_w_rook = 0;
    $this->m_b_rook = 0;
    $this->position = $position;
    $position_bit = 0b1;
    for($i = 63; $i >= 0; $i--) {
        switch ($position[$i]) {
            case FG_NONE:
                break;
            case FG_PAWN + COLOR_WHITE:
                $this->m_w_pawn |= $position_bit; break;
            case FG_PAWN + COLOR_BLACK:
                $this->m_b_pawn |= $position_bit; break;
            case FG_KING + COLOR_WHITE:
                $this->m_w_king |= $position_bit; break;
            case FG_KING + COLOR_BLACK:
                $this->m_b_king |=  $position_bit; break;
            case FG_QUEEN + COLOR_WHITE:
                $this->m_w_queen |= $position_bit; break;
            case FG_QUEEN + COLOR_BLACK:
                $this->m_b_queen |= $position_bit; break;
            case FG_ROOK + COLOR_WHITE:
                $this->m_w_rook |= $position_bit; break;
            case FG_ROOK + COLOR_BLACK:
                $this->m_b_rook |= $position_bit; break;
            case FG_BISHOP + COLOR_WHITE:
                $this->m_w_bishop |= $position_bit; break;
            case FG_BISHOP + COLOR_BLACK:
                $this->m_b_bishop |= $position_bit; break;
            case FG_KNIGHT + COLOR_WHITE:
                $this->m_w_knight |= $position_bit; break;
            case FG_KNIGHT + COLOR_BLACK:
                $this->m_b_knight |= $position_bit; break;
        }
        $position_bit = $position_bit << 1;
    }
    $this->m_all_white_figures = $this->m_w_pawn | $this->m_w_king | $this->m_w_queen | $this->m_w_rook | $this->m_w_bishop | $this->m_w_knight;
    $this->m_all_black_figures = $this->m_b_pawn | $this->m_b_king | $this->m_b_queen | $this->m_b_rook | $this->m_b_bishop | $this->m_b_knight;
}

В этом методе сначала обнуляются 12 битовых досок. В строке 15 в переменную $position_bit записываем единицу. В этой переменной будем хранить битовую маску для одного поля, и значение "1" соответствует полю H1. А индекс этого поля в массиве $position - 63.

Далее организуем цикл, где переменная цикла уменьшается от 63 до нуля включительно. Эта переменная цикла соответствует индексу поля, т.е. мы проходим по полям от H1 до A8. В конце тела цикла, в строке 45 в переменной $position_bit мы делаем битовый сдвиг влево на одну позицию. Таким образом, в теле цикла у нас оказываются связанными две переменые: $i и $position_bit. Обе указывают на одно поле (которое меняется в цикле от H8 до A1). Но $i - это индекс этого поля, а $position_bit - битовая маска, выделяющая это поле.

В теле цикла мы смотрим, какая фигура стоит в текущем поле ($position[$i]), и в зависимости от этого, устанавливаем (битовой операцией ИЛИ) в нужную битовую доску единицу в разряд, соответсвующий текущему полю.

После цикла заполняем маски, представляющие все белые фигуры, и все чёрные фигуры - просто делаем логическое сложение (ИЛИ) масок пешек, королей, ферзей, ладей, слонов и коней.

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

Один ход мы будем представлять почти так-же, как и раньше - в виде массива. Но поля "откуда" и "куда" будут представлены уже не индексами позиции (не номером поля), а 64-битным числом - маской. Один ход будет массивом с тремя элементами: "откуда", "куда", и тип хода. Тип хода может быть комбинацией нескольких флагов (масок) типа хода, определённых в файле engine/constants.php:

engine/constants.phpdefine('MOVE_TYPE_SIMPLE',         0b0000000);
define('MOVE_TYPE_BEAT',           0b0000001); // маска типа хода - взятие
define('MOVE_TYPE_PAWN',           0b0000010); // маска типа хода - ход пешки
define('MOVE_TYPE_PAWN2',          0b0000100); // маска типа хода - ход пешки на два поля вперёд
define('MOVE_TYPE_CROSS_BEAT',     0b0001000); // маска типа хода - взятие на проходе
define('MOVE_TYPE_KING',           0b0010000); // маска типа хода - ход короля
define('MOVE_TYPE_KING_CASTLING',  0b0100000); // маска типа хода - короткая рокировка
define('MOVE_TYPE_QUEEN_CASTLING', 0b1000000); // маска типа хода - длинная рокировка

Например, тип хода 0b1010000 является логическим сложением двух масок - "ход короля", и "длинная рокировка". Эти маски я ввёл для упрощения (и ускорения) процедуры выполнения хода. Например, при ходе короля, надо в состоянии игры отметить невозможность рокировки. При ходе пешки надо обнулить счётчик неактивных полуходов ($non_action_semimove_counter). И при любом взятии этот счётчик нужно обнулить. Проверить "особенности" хода легко, когда для каждой из этих "особенностей" есть свой выделенный бит в типе хода.

Генерация ходов происходит, кто-бы мог подумать, в классе MoveGenerator. На верхнем уровне, это делается в следующем методе:

engine/move_generator.phppublic function generateAllMovesMasks() {
    $this->beat_pawns = array();
    $this->beat_knights = array();
    $this->beat_bishops = array();
    $this->beat_rooks = array();
    $this->beat_queens = array();
    $this->beat_king = array();
    $this->move_pawns = array();
    $this->move_knights = array();
    $this->move_bishops = array();
    $this->move_rooks = array();
    $this->move_queens = array();
    $this->move_king = array();
    $this->all_figures_mask = (int)($this->game_state->m_all_white_figures | $this->game_state->m_all_black_figures);
    if ($this->game_state->current_player_color == COLOR_WHITE) {
        $this->generateWhiteMoves();
    } else {
        $this->generateBlackMoves();
    }
}

Как видите, в генераторе ходов мы завели 12 полей для хранения ходов. Для каждого из шести типов фигур (пешка, конь, слон, ладья, ферзь, король), есть по два поля - для взятий, и для "простых" ходов. Например для ладьи: beat_rooks - все ходы-взятия всех ладей "текущего цвета", move_rooks - все "простые" ходы всех ладей "текущего цвета".

В методе generateAllMovesMasks сначала записывается пустой массив во все 12 полей с ходами. Потом, в зависимости от текущего цвета, вызывается один из методов - generateWhiteMoves или generateBlackMoves.

Да, я сделал разные методы для генерации ходов белых и чёрных! Да, так получится много очень похожих, почти одинаковых кусков кода. Зачем я так сделал?

Если делать "универсальные методы", то в коде будет много проверок различных условий. Попробуйте сами! Одни только ходы пешек с их разными направлениями чего стоят. Мелочи конечно, но при игре выполняться эти проверки будут очень много раз, буквально миллионы раз. Именно генерация ходов у нас - одно из узких мест проиводительности.

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

А вот метод, который вызывается "шахматным ИИ" для получения всех возможных ходов:

engine/move_generator.phppublic function generateAllMovesFlat() {
    $this->generateAllMovesMasks();
    return array_merge(
        $this->beat_pawns, $this->beat_knights, $this->beat_bishops, $this->beat_rooks, $this->beat_queens, $this->beat_king,
        $this->move_queens, $this->move_rooks, $this->move_bishops, $this->move_knights, $this->move_pawns, $this->move_king
    );
}

Сначала вызываем вышеописанный метод генерации масок всех ходов. Потом объединяем в один массив в нужном порядке - сначала взятия, от взятий пешками до взятий королём, потом - простые ходы, от ходов ферзём до ходов королём. Даже сортировка ходов не нужна! На этом тоже съэкономили.

А что скрывается за методами generateWhiteMoves, generateBlackMoves, упомянутыми чуть выше? Там тоже всё просто. Вот они:

engine/move_generator.phpprivate function generateWhiteMoves() {
    $this->addWhiteQueenMoves();
    $this->addWhiteRookMoves();
    $this->addWhiteBishopMoves();
    $this->addWhiteKhightMoves();
    $this->addWhitePawnMoves();
    $this->addWhiteKingMoves();
}

private function generateBlackMoves() {
    $this->addBlackQueenMoves();
    $this->addBlackRookMoves();
    $this->addBlackBishopMoves();
    $this->addBlackKhightMoves();
    $this->addBlackPawnMoves();
    $this->addBlackKingMoves();
}

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

Ходы конём

На примере генерации ходов белых коней, покажу некоторые "шаблоны кода", которые массово применяются в новой версии шахмат.

Как пройти по всем единичным битам

Нам надо взять всех белых коней, и для каждого сделать некоторые действия. Это делается так:

engine/move_generator.phpprivate function addWhiteKhightMoves() {
    $m_knights_set = (int)$this->game_state->m_w_knight;
    while ($m_knights_set) {
        $m_knight = $m_knights_set & (int)-$m_knights_set;
        
        Какие-то действия с $m_knight

        $m_knights_set &= ~$m_knight;
    }
}

Такой шаблон часто встречается. Есть число - маска с несколькими выставленными битами, (в нашем примере это $m_knights_set - набор белых коней). Надо для каждого выставленного бита (для каждого белого коня) сделать какие-то действия. Для выделения одного бита из числа x у нас используется выражение вида: x & -x

Операция -x инвертирует все биты числа x и прибавляет 1. Благодаря этому, в результате выполнения x & -x сохраняется только самый младший единичный бит. Проиллюстрируем на примере:

Итак, операцией $m_knight = $m_knights_set & (int)-$m_knights_set мы получили маску, соответствующую одному коню. Делаем какие-то действия, а потом убираем этого коня из маски со всеми конями: $m_knights_set &= ~$m_knight;. Т.е инвертируем маску с одним конём (при этом получаем ноль в разряде, где находится конь, и единицы - во всех остальных разрядах), и делаем логическое умножение (операцией И) с маской всех коней.

И всё это делаем в цикле, пока в маске со всеми конями не останутся одни нули.

Ещё раз, шаблон кода, когда мы хотим пройти по всем выставленным (единичным) битам в каком-то числе $x_set:

while ($x_set) {
    $x = $x_set & (int)-$x_set;
    Какие-то действия с $x
    $x_set &= ~$x;
}

Готовые маски для ходов

Ещё одно ускорение - во время игры можно не рассчитывать куда можно пойти конём с какого-то поля. Можно заранее это посчитать и для каждого поля доски записать маску всех возможных ходов с этого поля. На картинке показан пример для ходов коня с поля g1:

Из картинки видно, что для поля g1 (поля с индексом 62), маска в 16-ричном представлении выглядит так: 50800. Такие маски можно заранее посчитать для всех полей и записать в массив. Конечно я не вручную считал эти маски. Сделал скрипт, он для каждого поля посчитал маски ходов коня, и выдал мне готовый массив.

Маски ходов коня, (и другие маски) я поместил в файл engine/constants.php. Добавил там класс Masks, и записывал маски как публичные константы класса. Вот, как пример, маски ходов коня:

engine/constants.phppublic const KHIGHT_MASK = array(
    0x0020400000000000, 0x0010a00000000000, 0x0088500000000000, 0x0044280000000000, 0x0022140000000000, 0x00110a0000000000, 0x008050000000000, 0x004020000000000,
    0x2000204000000000, 0x100010a000000000, 0x8800885000000000, 0x4400442800000000, 0x2200221400000000, 0x1100110a00000000, 0x800080500000000, 0x400040200000000,
    0x4020002040000000, 0xa0100010a0000000, 0x5088008850000000, 0x2844004428000000, 0x1422002214000000, 0x0a1100110a000000, 0x508000805000000, 0x204000402000000,
    0x0040200020400000, 0x00a0100010a00000, 0x0050880088500000, 0x0028440044280000, 0x0014220022140000, 0x000a1100110a0000, 0x005080008050000, 0x002040004020000,
    0x0000402000204000, 0x0000a0100010a000, 0x0000508800885000, 0x0000284400442800, 0x0000142200221400, 0x00000a1100110a00, 0x000050800080500, 0x000020400040200,
    0x0000004020002040, 0x000000a0100010a0, 0x0000005088008850, 0x0000002844004428, 0x0000001422002214, 0x0000000a1100110a, 0x000000508000805, 0x000000204000402,
    0x0000000040200020, 0x00000000a0100010, 0x0000000050880088, 0x0000000028440044, 0x0000000014220022, 0x000000000a110011, 0x000000005080008, 0x000000002040004,
    0x0000000000402000, 0x0000000000a01000, 0x0000000000508800, 0x0000000000284400, 0x0000000000142200, 0x00000000000a1100, 0x000000000050800, 0x000000000020400
);

Маски представлены в шестнадцетиричном коде, выровнены по длине, и расположены в 8 рядов по 8 масок в строке. Это всё просто для удобства чтения. В таком виде расположение масок соответствует визуально полям шахматной доски, которые эти маски представляют.

Но вернёмся к генерации ходов для белых коней

Весь метод генерации ходов коня

engine/move_generator.phpprivate function addWhiteKhightMoves() {
    $m_knights_set = (int)$this->game_state->m_w_knight;
    while ($m_knights_set) {
        $m_knight = $m_knights_set & (int)-$m_knights_set;
        $pos_from = (int)(63 - log($m_knight, 2));
        $moves_mask = (int)Masks::KHIGHT_MASK[$pos_from];
        // взятия конём
        $m_beat_figures = $moves_mask & $this->game_state->m_all_black_figures;
        while ($m_beat_figures) {
            $m_beat = $m_beat_figures & (int)-$m_beat_figures;
            if ($this->game_state->checkWhiteKnightBeat($m_knight, $m_beat)) {
                $this->beat_knights[] = array($m_knight, $m_beat, MOVE_TYPE_BEAT);
            }
            $m_beat_figures &= ~$m_beat;    
        }

        // простые перемещения конём
        $m_moves_fields = $moves_mask & ~($this->game_state->m_all_black_figures | $this->game_state->m_all_white_figures);
        while ($m_moves_fields) {
            $m_move = $m_moves_fields & (int)-$m_moves_fields;
            if ($this->game_state->checkWhiteKnightMove($m_knight, $m_move)) {
                $this->move_knights[] = array($m_knight, $m_move, MOVE_TYPE_SIMPLE);
            }
            $m_moves_fields &= ~$m_move;    
        }

        $m_knights_set &= ~$m_knight;
    }
}

В строке 2 получаем из состояния игры положение всех белых коней. Потом в цикле проходим по всем белым коням. Как это делается я описал подробнее чуть выше: "Как пройти по всем единичным битам". Внутри цикла положение одного коня, для которого генерируем ходы, храним в маске $m_knight.

В строке 5 из маски-положения коня, получаем индекс поля, на котором находится конь:

$pos_from = (int)(63 - log($m_knight, 2));

Двоичный логарифм от маски коня по определению означает степень в которую надо возвести двойку, чтобы получить маску коня. Т.е. сколько раз надо умножить два на два. А что означает умножение на двойку в двоичной системе? Это смещение бита на один разряд влево. (Так же как в десятичной системе: умножение на 10 приводит к смещению "единицы" влево на один разряд в десятичном представлении) Т.е. наш логарифм покажет - на сколько разрядов влево надо сдвинуть единицу из самого младшего разряда, чтобы "попасть" в бит коня. Но у нас нумерация позиций идёт с поля A8 по H1. Т.е. полю H1 соответствует позиция 63. А самый младший разряд, (представленный двойкой в нулевой степени) соответствует как раз полю H1. Поэтому, чтобы получить номер позиции, мы вычитаем полученный логарифм из числа 63.

Операция двоичного логарифма оптимизирована в современных процессорах, и именно такое получение номера позиции из маски, выполнялось быстрее других способов, которые я тестировал

Итак, мы получили индекс поля, на котором находится конь. В строке 6 для этого поля берём из массива Masks::KHIGHT_MASK маску со всеми ходами коня - $moves_mask.

В строке 8 делаем логическое умножение (операция И) маски всех ходов нашего (белого) коня и маски всех чёрных фигур. В итоге получаем маску со всеми взятиями коня - $m_beat_figures. Далее, в строках 9-15 по знакомой уже схеме проходим по всем единичным битам маски взятий (т.е. перебираем все взятия коня).

В строке 11 проверяем допустимость взятия белым конём с позиции, представленной маской $m_knight в позицию представленной маской $m_beat. Делаем это вызовом метода checkWhiteKnightBeat состояния игры, который опишу позже. Допустимость хода проверяет, не останется белый король под угрозой при выполнении рассматриваемого хода. Если метод нам "сказал" что ход допустим, то в строке 12 добавляем рассматриваемый ход в массив взятий коня $this->beat_knights.

К данному моменту мы записали все взятия рассмативаемого коня. Теперь, по такой-же схеме, запишем все простые ходы этого коня. В строке 18 получаем маску со всеми простыми перемещениями коня. Как это делается? Делаем операцию логического сложения (ИЛИ) маски всех чёрных фигур и маски всех белых фигур. Получилась маска со всеми фигурами. Инвертируем её (операция НЕ), получаем маску со всеми свободными полями. И делаем логическое умножение (И) маски со всеми ходами коня и маски со всеми свободными полями. Дальше - почти такие-же действия, как и при рассмотрении взятий: проходим по всем простым перемещениям, проверяем допустимость хода (checkWhiteKnightMove), и если он допустим, то добавляем ход в массив ходов коней ($this->move_knights).

Ходы пешек

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

Взятия влево

Чтобы получить маску поля, которому угрожает белая пешка влево, можно бит, соответствующей пешке, переместить на 9 полей влево. Т.е. сделать битовый сдвиг влево на 9. Причём можем сделать такой сдвиг сразу всех пешек, одной операций. Но пешка, стоящая на вертикали A в результате такого сдвига попадёт на вертикаль H. Например поле A2, при сдвиге на 9 позиций влево, попадёт на поле H4. Поэтому из результата сдвига надо исключить вертикаль H. Так мы получим маску полей под "левой угрозой" белых пешек. И, чтобы получить взятия, эту маску логически умножаем на маску во всеми чёрными фигурами. Вот код, иллюстрирующий описанное:

engine/move_generator.php$m_pawns_set = (int)$this->game_state->m_w_pawn; // это все белые пешки
// проверим взятия влево (без взятия на проходе)
$m_beats = (int)($m_pawns_set << 9) & ~COL_H;
$m_beat_figs = $m_beats & $this->game_state->m_all_black_figures;

Здесь COL_H - константа - число, где единичные биты выставлены в позициях, соответствующих вертикали H. Эта константа определена в файле engine/constants.php

Чтобы получить взятия влево для чёрных пешек, их позиции (биты) можно сдвинуть на 7 позиций вправо. Вот кусок кода, показывающий добавление взятий чёрных пешек влево:

engine/move_generator.php// проверим взятия влево (без взятия на проходе)
$m_beats = ($m_pawns_set >> 7) & ~COL_H;
$m_beat_figs = $m_beats & $this->game_state->m_all_white_figures;
while ($m_beat_figs) {
    $m_beat = $m_beat_figs & (int)-$m_beat_figs;
    $m_from = $m_beat << 7;
    if ($this->game_state->checkBlackPawnBeat($m_from, $m_beat)) {
        $this->beat_pawns[] = array($m_from, $m_beat, MOVE_TYPE_BEAT | MOVE_TYPE_PAWN);
    }
    $m_beat_figs &= ~$m_beat;
}

Взятия вправо

Для взятий вправо всё аналогично, как для взятий влево. Чтобы получить взятия влево для белых пешек, можно битовую маску белых пешек сдвинуть на 7 разрядов влево. Для чёрных пешек - сдвинуть их битовую маску на 9 разрядов вправо. И в обоих вариантах надо исключить вертикаль A.

Взятия на проходе

Вот отрывок из генератора ходов, показывающий генерацию ходов - взятий на проходе для белых пешек:

engine/move_generator.php// проверим взятие на проходе
if (($m_beat = (int)$this->game_state->m_crossed_field) != 0) {
    // получу маску с пешками, которые бьют проходное поле
    $m_pawnscross = $this->game_state->m_w_pawn & ( (($m_beat >> 7) & ~COL_H) | (($m_beat >> 9) & NOT_COL_A) );
    while ($m_pawnscross) {
        $m_pawn = $m_pawnscross & (int)-$m_pawnscross;
        if ($this->game_state->checkWhitePawnCrossBeat($m_pawn, $m_beat)) {
            $this->beat_pawns[] = array($m_pawn, $m_beat, MOVE_TYPE_CROSS_BEAT | MOVE_TYPE_PAWN | MOVE_TYPE_BEAT);
        }
        $m_pawnscross &= ~$m_pawn;
    }
}

Сначала, в строке 2, проверем, есть ли вообще "пересечённое поле". В переменную $m_beat записываем "пересечённое поле" из состояния игры, приведённое к типу int, и сравниваем с нулём.

В строке 4 получаем маску с белыми пешками, которые бьют "пересечённое поле":

• (($m_beat >> 7) & ~COL_H) - "пересечённое поле" свигаем на 7 разрядов вправо и исключаем вертикаль H. Так мы получаем позицию "внизу слева" от пересечённого поля. Если там стоит белая пешка, то она может "взять на проходе", переместившись на пересечённое поле "вправо вверх".
• (($m_beat >> 9) & NOT_COL_A - аналогично, "пересечённое поле" сдвигаем на 9 разрядов вправо, и исключаем вертикаль A. Получаем позицию "внизу справа".
• Два полученных выше поля объединяем (складываем) операцией ИЛИ
• $this->game_state->m_w_pawn & (…) - делаем пересечение (логическое умножение) полученных выше полей с маской всех белых пешек.

В итоге, в переменной $m_pawnscross будет маска для всех белых пешек, которые бьют "пересечённое поле". Далее, по обычной схеме, в цикле (строки 5-11) обрабатываем все единичные биты, т.е. все белые пешки, бьющие проходное поле.

В строке 7 проверяем "валидность" взятия на проходе (т.е. то, что после такого взятия белый король не окажется под атакой). И в случае успеха, в строке 8 добавляем ход в массив взятий пешек ($this->beat_pawns). Причём в типе хода указываем сразу три флага (единичных бита): MOVE_TYPE_CROSS_BEAT | MOVE_TYPE_PAWN | MOVE_TYPE_BEAT Т.е. говорим что этот ход - "взятие на проходе", это ход пешкой, и это взятие.

Простые ходы вперёд на одну и две клетки

Вот так можно получить маски всех ходов белых пешек вперёд:

engine/move_generator.php$m_to_step1 = ((int)$this->game_state->m_w_pawn << 8) & ~$this->all_figures_mask; // маска - куда могут пойти пешки на одну клетку
$m_to_step2 = (int)(($m_to_step1 & HOR_3) << 8) & ~$this->all_figures_mask; // маска - куда могут пойти пешки на две клетки

Берём маску всех белых пешек ($this->game_state->m_w_pawn). Сдвигаем её на 8 разрядов влево, получаем маску полей перед белыми пешками. И умножаем (логическое И) с инвертированной маской всех фигур. Если инвертировать (логическое НЕ) маску всех фигур (и белых и чёрных), то получим маску всех свободных полей. Таким образом мы получили все свободные поля перед белыми пешками. Это и есть те поля, куда могут ходить пешки на одно поле вперёд.

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

Ходы дальнобойных фигур

Ходы ферзя можно представить как сумму ходов ладьи и слона. Ходы ладей строятся по лучам "налево", "направо", "вверх" и "вниз". Ходы слонов - по лучам "влево-вверх", "вправо-вверх", "влево-вниз" и "вправо-вниз". Битовые маски для всех этих лучей для каждого поля доски заранее вычислены и хранятся в классе Masks (в файле engine/constants.php) в константах.

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

Если бы на доске не было других фигур, то эта маска уже описывала бы все возможные ходы (т.е. их конечно ещё надо проверить на допустимость позиции, которая получится после совершения этих ходов). Но на доске есть другие фигуры. Делаем логическое умножение маски луча на маску всех фигур на доске. Берём "ближайший" к нашему полю единичный бит полученного числа. Это будет положение фигуры, которую мы атакуем на рассматриваемом луче. Если это чужая фигура, то мы можем её взять, и добавим этот ход в рассматриваемые хода.

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

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

Луч влево

Рассмотрим луч влево с поля E1, и, для примера, такое расположение фигур:

Видим, что "ближайшая" атакуемая фигура для луча влево представляется младшим битом пересечения "луча влево" с маской всех фигур. А младший бит находить мы уже умеем: m_ray_end = x & -x (здесь x - это маска луча "влево").

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

Получили готовую маску для всех простых ходов влево.

Луч вправо

Теперь рассмотрим луч вправо на таком примере:

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

Как найти старший бит числа?

Тут есть два способа. Первый:

(int)(1 << (int)log($num, 2))

Здесь $num - число, у которого бы хотим взять старший единичный бит. Берём логарифм по основанию 2 от нашего числа. Что значит этот логарифм? Это значит - "в какую степень надо возвести двойку, чтобы получить число $num". Т.е. "сколько раз надо 2 умножить на 2 чтобы получить наше число". А что значит "умножить на 2" в битовой арифметике? Значит "сделать поразрядный сдвиг влево". Т.е., грубо говоря, с учётом округления, "на сколько разрядов надо сдвинуть единицу, чтобы получить наше число". Потом берём единицу, и делаем поразрядный сдвиг влево именно на это число. Получаем число, в котором один единичный бит, и он стоит на нужной позиции, т.е. технически представляет максимальное число с одним выставленным битом, меньшее, чем заданное.

Второй способ, в виде функции:

function getHighestBit($num) {
    $num |= ($num >> 1);
    $num |= ($num >> 2);
    $num |= ($num >> 4);
    $num |= ($num >> 8);
    $num |= ($num >> 16);
    $num |= ($num >> 32);
    return ($num ^ ($num >> 1));
}

Этот приём сдвигает число вправо и объединяет его с самим собой через побитовое OR, благодаря чему все биты справа от старшего становятся единицами. Повторяя такие операции с разным сдвигом, мы "заполняем" все младшие биты единицами. Затем операция XOR с числом, сдвинутым вправо на 1, оставляет только самый старший установленный бит.

Какой вариант быстрее? Сначала я думал что вариант с логарифмом медленнее. Но при тестировании оказалось что разница между ними незначительна даже при многих миллионах вызовов в процессе поиска хода. Видимо современные сопроцессоры хорошо оптимизированы для таких вычислений со степенями двойки.

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

Проверки допустимости кода

При генерации ходов мы получаем маски полей, куда фигура может ходить по правилам её хода. Но в результате такого хода может получиться что король оказался (или остался) под атакой. Такой ход недопустим. Поэтому при генерации ходов каждый раз вызываются методы проверки допустимости хода. В примере выше, с генерацией ходов белого коня, я показывал вызовы одного из таких методов - checkWhiteKnightMove. Ещё выше упоминались методы checkBlackPawnBeat - проверка допустимости взятия чёрной пешкой, и checkWhitePawnCrossBeat - проверка допустимости взятия белой пешкой на проходе.

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

Все эти методы размещены в классе состояния игры. Для примера покажу метод проверки хода-взятия белым конём:

engine/game_state.php/**
 * Проверка - будет ли белый король под атакой при взятии белым конём фигуры, стоящей в поле, определённом маской $mask_to
 */
public function checkWhiteKnightBeat($mask_from, $mask_to) {
    $to_state = clone $this;
    // перемещаем белого коня
    $to_state->m_w_knight = ($to_state->m_w_knight & ~$mask_from) | $mask_to;
    $to_state->m_all_white_figures = ($to_state->m_all_white_figures & ~$mask_from) | $mask_to;
    $to_state->removeBlackFigureByMask(~$mask_to);
    return !$to_state->isWhiteKingUnderAttack();
}

Входные параметры этого метода (и других аналогичных) - маски полей "откуда" и "куда" делается ход. В строке 5 делаем клон состояния игры, записываем его в переменную $to_state. Именно в этой копии состоянии игры будем делать перемещения, не затрагивая исходное состояние.

В строке 7 изменяем маску белых коней. Сначала делаем логическое И с отрицанием маски поля "откуда". Этим самым мы убираем единичный бит "с поля" откуда делаем ход белый конь. Потом делаем логическое ИЛИ с маской поля "куда". Т.е. устанавливаем единицу в разряд, соответствующий этому полю.

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

Т.к. мы рассматриваем метод для хода-взятия, то надо убрать единицы из масок, описывающих чёрные фигуры. Для этого в строке 9 вызываем метод removeBlackFigureByMask, текст которого чуть ниже.

Ну и в строке 10 вызываем метод isWhiteKingUnderAttack на объекте итогового состояния игры (т.е. состояния после совершения проверяемого хода). Метод возвращает True если белый король в этом состоянии игры находится под атакой. И возвращаем отрицание этого результата. Т.е. если король под атакой, то ход недопустим, и надо вернуть False. Если король не под атакой, то надо вернуть True.

Метод removeBlackFigureByMask

Метод removeBlackFigureByMask делает удаление чёрной фигуры (фигур) по маске. Вот его код:

engine/game_state.php/**
 * Удаление чёрной фигуры (фигур) из битовых досок по маске
 */
public function removeBlackFigureByMask($remmask) {
    $this->m_all_black_figures &= $remmask;
    $this->m_b_pawn &= $remmask;
    $this->m_b_knight &= $remmask;
    $this->m_b_bishop &= $remmask;
    $this->m_b_rook &= $remmask;
    $this->m_b_queen &= $remmask;
}

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

Поле под атакой?

Ранее, чуть выше, ещё упоминался метод isWhiteKingUnderAttack, который проверяет - находится ли белый король под атакой? Его код очень прост:

engine/game_state.php/**
 * Проверка - находится ли белый король под атакой?
 */
public function isWhiteKingUnderAttack() {
    return $this->isAttackedByBlack($this->m_w_king);
}

Здесь просто вызывается метод, определяющий, находится ли поле под атакой чёрных фигур. В качестве параметра передаётся маска поля с белым королём. Этот метод нужен и при определении возможности рокировок (поля, проходимые королём, не должны быть под атакой). Вот код этого метода:

engine/game_state.php/**
 * Проверка - находится ли поле под атакой чёрными фигурами?
 */
public function isAttackedByBlack($field_mask) {
    // поле атаковано конями?
    $pos_from = (int)(63 - log($field_mask , 2));
    if ($this->m_b_knight & (int)Masks::KHIGHT_MASK[$pos_from]) {
        return true;
    }
    // поле атаковано пешками?
    if ( ((($this->m_b_pawn >> 7) & ~COL_H) | (($this->m_b_pawn >> 9) & NOT_COL_A)) & $field_mask ) {
        return true;
    }
    $m_b_queen_rook = $this->m_b_queen | $this->m_b_rook;
    $m_b_queen_bishop = $this->m_b_queen | $this->m_b_bishop;
    // поле атаковано с соседних полей (по вертикалям, горизонталям, диагоналям)? (не пешками, с ними мы разобрались ранее)
    if (
        ((int)Masks::KING_HV_MASK[$pos_from] & ($this->m_b_king | $m_b_queen_rook))
        ||
        ((int)Masks::KING_DIAG_MASK[$pos_from] & ($this->m_b_king | $m_b_queen_bishop))
    ) {
        return true;
    }
    
    $all_figures_mask = $this->m_all_white_figures | $this->m_all_black_figures;
    
    // проверим луч влево
    $cross_mask = (int)Masks::HOR_LEFT_MASK[$pos_from] & $all_figures_mask;
    // выделение самого младшего (правого) бита: $cross_mask & (int)-$cross_mask
    if ( ($cross_mask & (int)-$cross_mask) & $m_b_queen_rook ) {
        return true;
    }

    // проверим луч вправо
    $cross_mask = Masks::HOR_RIGHT_MASK[$pos_from] & $all_figures_mask;
    if ( $cross_mask && $m_b_queen_rook && ($m_b_queen_rook & Functions::getHighestBit($cross_mask)) ) {
        return true;
    }

    // луч вверх
    $cross_mask = (int)Masks::VERT_UP_MASK[$pos_from] & $all_figures_mask;
    if ( ($cross_mask & (int)-$cross_mask) & $m_b_queen_rook ) {
        return true;
    }
    
    // луч вниз
    $cross_mask = Masks::VERT_DOWN_MASK[$pos_from] & $all_figures_mask;
    if ( $cross_mask && $m_b_queen_rook && ($m_b_queen_rook & Functions::getHighestBit($cross_mask)) ) {
        return true;
    }

    // луч вверх влево
    $cross_mask = (int)Masks::DIAG_UP_LEFT[$pos_from] & $all_figures_mask;
    if ( ($cross_mask & (int)-$cross_mask) & $m_b_queen_bishop ) {
        return true;
    }

    // луч вверх вправо
    $cross_mask = Masks::DIAG_UP_RIGHT[$pos_from] & $all_figures_mask;
    if ( ($cross_mask & (int)-$cross_mask) & $m_b_queen_bishop ) {
        return true;
    }

    // луч вниз влево
    $cross_mask = Masks::DIAG_DOWN_LEFT[$pos_from] & $all_figures_mask;
    if ( $cross_mask && $m_b_queen_bishop && ($m_b_queen_bishop & Functions::getHighestBit($cross_mask)) ) {
        return true;
    }

    // луч вниз вправо
    $cross_mask = Masks::DIAG_DOWN_RIGHT[$pos_from] & $all_figures_mask;
    if ( $cross_mask && $m_b_queen_bishop && ($m_b_queen_bishop & Functions::getHighestBit($cross_mask)) ) {
        return true;
    }

    // угроз не обнаружили, возвращаем false
    return false;
}

Сначала, в строке 6 по маске поля определяем индекс этого поля на доске. Это выражение уже описано выше, когда рассматривался код генерации хода коня. По этому индексу поля будем получать маски лучей и ходов коня.

В строке 7 проверем, не атаковано ли рассматриваемое поле чёрными конями. Берём маску всех возможных ходов коня из этого поля И пересекаем (делаем логическое И) с маской всех чёрных коней. Здесь используется свойство изотропности ходов коня - если из нашего поля можно ходом коня попасть на поле с конём, то этот конь может попасть на наше поле. Если полученное пересечение не пусто, значит поле находится под атакой чёрных коней, и можно сразу возвращать результат из метода - true, т.е. поле под атакой. Вот такая проверка в одну строчку.

В строке 11 проверяем - атаковано ли поле чёрными пешками. Тоже получилась проверка в одну строку. Получили все поля, которые атакуют чёрные пешки, и пересекли с маской проверяемого поля.

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

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

Дальше идут однотипные проверки угроз для восьми лучей. Для каждого луча берём маску полей этого луча. Пересекаем с маской всех фигур (и белых и чёрных). У полученного пересечения берём "ближайший" к проверяемому полю единичный бит (т.е. берём ближайшее поле с фигурой). И полученную маску ближайшей фигуры пересекаем с маской фигур, бьющих по рассматриваемому лучу.

Здесь, как и ранее, при генерации ходов, в зависимости от направления луча, встречаются два случая: когда "ближайшее поле" представляется младшим битом маски, и старшим битом маски. Рассмотрим оба случая на примерах - на лучах "влево" и "вправо".

Луч влево

// проверим луч влево
$cross_mask = (int)Masks::HOR_LEFT_MASK[$pos_from] & $all_figures_mask;
// выделение самого младшего (правого) бита: $cross_mask & (int)-$cross_mask
if ( ($cross_mask & (int)-$cross_mask) & $m_b_queen_rook ) {
    return true;
}

Всё очень просто. Маску луча Masks::HOR_LEFT_MASK[$pos_from] пересекаем с маской всех фигур $all_figures_mask, получаем маску пересечения $cross_mask

Выделяем младший бит (уже знакомый приём): $cross_mask & (int)-$cross_mask. Пересекаем с маской чёрных фигур, которые бьют по горизонталям-вертикалям $m_b_queen_rook. Если пересечение не пустое, значит поле под атакой, возвращаем true из метода.

Луч вправо

// проверим луч вправо
$cross_mask = Masks::HOR_RIGHT_MASK[$pos_from] & $all_figures_mask;
if ( $cross_mask && $m_b_queen_rook && ($m_b_queen_rook & Functions::getHighestBit($cross_mask)) ) {
    return true;
}

Всё тот-же алгоритм, что и для луча влево, только конечно маска луча другая, и брать надо не младший, а старший бит. Для получения старшего бита у нас есть метод Functions::getHighestBit. Но почему тут у нас так много условий?

Тут достаточно было написать "взять старший бит маски пересечения и пересечь с маской чёрных фигур, атакующих по горизонтали", т.е. так:

if ($m_b_queen_rook & Functions::getHighestBit($cross_mask)) { 

И всё бы корректно работало. Но метод получения старшего бита - достаточно тяжёлая операция для миллионов вызовов. Причём если маска пересечения $cross_mask пустая, то ясно что метод получения старшего бита вернёт 0. И если на доске нет чёрных ладей, то каким-бы ни был старший бит, его пересечение с пустой маской ладей даст ноль. Поэтому я поставил эти условия перед вызовом метода Functions::getHighestBit. PHP выполняет сокращённую проверку условий. Если он обнаружит что $cross_mask пустой, то остальные условия не будут проверяться, результат и так ясен. А если $cross_mask не пуст, но чёрных ладей нет на доске (т.е. $m_b_queen_rook пуст), то тоже сразу возвращается false, без вызова дорогого Functions::getHighestBit. В результате выполнение кода ускорилось.

Оценочная функция и шахматный ИИ

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

Классы фигур в этой версии исчезли, они не нужны.

Скорость перебора позиций увеличилась, минимум в 2.5 раза. А в средней и более поздних стадиях игры - в 8 - 9 раз. Но этого всё равно недостаточно чтобы увеличить глубину основного просмотра даже на 2 полухода. Точнее, можно конечно увеличить, но программа станет отвечать недостаточно быстро для комфортной игры с ней. Я сделал дробную глубину основного просмотра - 2.4 полухода. Конечно есть выборочные продления и форсированный перебор.

На такой глубине шахматный ИИ не видит недостатков раннего развития тяжёлых фигур, и "слишком рано" стремиться приблизиться к чужому королю ферзём. Чтобы "очеловечить" игру, я ввёл в оценочную функцию "штрафы" за ранний уход тяжёлых фигур со своих начальных позиций.

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

Да, глубокий перебор, куча вариантов, … но почему предыдущая версия программы очень быстро находила ход? Ведь когда я это тестировал, я не менял алгоритм ИИ, просто перевёл всё на работу с битовыми досками. Я долго это выяснял, точно так и не понял, но нашёл одно различие.

В предыдущей версии программы нашёл баг в оценочной функции. Ну как баг … Можно считать это особенностью оценочной функции. В общем, в рассчёте "взвешенного количества атак" учитывались "рентгеновкие атаки". Т.е. когда фигуру атакует например ладья, за ней стоит ещё ферзь. Так вот, просмотр луча не останавливался на фигуре, блокирующей атаку, даже на "своей фигуре". К примеру, в начальной позиции белая пешка на поле A2 считалась находящейся под рентгеновкой атакой со стороны чёрной ладьи, стоящей на поле A8, хотя ей мешала черная пешка на A7.

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

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

Итоги

Программа стала играть ещё немного сильнее за счёт небольшого увеличения средней глубины рассчёта. Скорость перебора оцененных позиций зависит от позиции и количества фигур на доске. В средней стадии она может достигать 17 тысяч оцененных позиций в секунду.

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

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