Введение
Не так давно я захотел написать свой шахматный движок. На удивление в Интернете нашлось не так много хороших статей на эту тему. Были статьи с довольно слабыми программами, многие из которых даже умудрялись пропускать некоторые важные правила. А были статьи с хорошими программами (некоторые из них были даже чуть лучше чем получилось у меня в итоге), но там авторы рассказывали лишь основные идеи, пропуская подробности, из-за чего написать что-то свое по таким статьям было проблематично. Поэтому после написания своей программы, я решил написать статью, дабы облегчить жизнь интересующимся в данной теме. Я не претендую на лучшую шахматную программу или на чистейший код, но эта статья будет хорошим и легким началом для тех, кто хочет написать что-то свое.
Битборды или битовые доски
Существует довольно удобная система представления доски, называемая битбордами или битовыми досками, если по-русски. Идея битбордов строится на замечательном совпадении: шахматная доска содержит 64 клетки, когда как современные компьютеры умеют невероятно быстро работать с 64 битовыми числами. Таким образом мы можем использовать 12 таких битбордов для хранения всех фигур. Каждый такой битборд будет хранить какую-то фигуру (или пешку), например - один битборд отвечает за черных коней, другой - за белые пешки, третий - за черного короля.
Основная причина выбора битбордов, а не массива на 64 клетки - высокая скорость и, как, это не странно, удобность. Например, нам надо проверить является ли пешка проходной. Проходная пешка, согласно Википедии, это
пешка, на одной вертикали перед которой отсутствуют пешки противника, а на
соседних вертикалях или нет пешек противника или они не держат под боем
поля, через которые пешка должна пройти до поля превращения.
Используя массив из 64 клеток, нам надо было бы проверять, в худшем случае, целых 18 клеток для каждой пешки, чтобы сказать какие являются проходными, а какие нет. Используя битборды, мы можем заранее рассчитать на каких клетках не должны стоять пешки противника, чтобы пешка называлась проходной, а затем использовать эти данные чтобы узнать является ли пешка проходной за одну операцию побитового "и".
Предлагаю перейти к реализации наших битбордов. На самом деле, реализовывать их не надо, ведь битборд - просто красивое название для 64 битного числа. Так что объявление битборда будет выглядеть так:
typedef uint64_t Bitboard;Обращаю внимание, что используется именно беззнаковое число, так как в процессе программирования будут использоваться битовые сдвиги, а битовые сдвиги со знаковыми переменными работают не так как нам надо будет (ведь 1 бит из 64 при использовании знаковых переменных отвечает за знак числа и его компьютер трогать не будет).
Но с одним объявлением жить довольно грустно, нужно реализовать несколько дополнительных операций, чтобы облегчить жизнь.
static constexpr void set_1(Bitboard &bb, uint8_t square) {
bb = bb | (1ull << square);
}
static constexpr void set_0(Bitboard &bb, uint8_t square) {
bb = bb & (~(1ull << square));
}
static constexpr bool get_bit(Bitboard bb, uint8_t square) {
return (bb & (1ull << square));
}Перед вами примитивные операции для обращения к битбордам по индексу. Нужно пытаться их избегать, так как они довольно медленные, но совсем без них никуда.
Еще нам понадобится считать количество единичных битов. Это знание нужно, например, при оценке позиции. Чтобы узнать насколько хороша позиция надо, как минимум, узнать сколько фигур у белых и сколько фигур у черных, а для этого надо их посчитать.
Но как это сделать? Самое наивное что можно придумать - пройти по всем 64 битам и посчитать, но думаю, что прекрасно понятно, что это очень не эффективно. На эту тему есть отличная статья на хабре, но подобное уже было реализовано в стандартной библиотеке, а именно в заголовке bit, так что просто воспользуемся готовой функцией:
static constexpr uint8_t count_1(Bitboard bb) {
return std::popcount(bb);
}Помимо этого нам нужны еще две функции: поиск первого единичного бита и поиск последнего. Для этих операций придумали даже специальные инструкции в процессорах. Но я ими решил не пользоваться, так как они плохо влияют на переносимость проекта. К тому же разница в скорости между этими инструкциями и оптимизированным подходом оказалась на уровне погрешности (по крайней мере, в практических условиях). Поэтому было решено использовать оптимизированный алгоритм. Объяснять его я не буду, так как на объяснение, вероятно, уйдет столько же времени, сколько и на весь остальной движок, а это явно не то зачем сюда пришли люди, так что просто посмотрите на эту замечательную реализацию, взятую с chessprogrammingwiki:
static constexpr std::array<uint8_t, 64> BitScanTable = {
0, 47, 1, 56, 48, 27, 2, 60,
57, 49, 41, 37, 28, 16, 3, 61,
54, 58, 35, 52, 50, 42, 21, 44,
38, 32, 29, 23, 17, 11, 4, 62,
46, 55, 26, 59, 40, 36, 15, 53,
34, 51, 20, 43, 31, 22, 10, 45,
25, 39, 14, 33, 19, 30, 9, 24,
13, 18, 8, 12, 7, 6, 5, 63
};
static constexpr uint8_t bsf(Bitboard bb) {
return BitboardOperations::BitScanTable[((bb ^ (bb - 1)) * 0x03f79d71b4cb0a89) >> 58];
}
static constexpr uint8_t bsr(Bitboard bb) {
bb = bb | (bb >> 1);
bb = bb | (bb >> 2);
bb = bb | (bb >> 4);
bb = bb | (bb >> 8);
bb = bb | (bb >> 16);
bb = bb | (bb >> 32);
return BitboardOperations::BitScanTable[(bb * 0x03f79d71b4cb0a89) >> 58];
}Еще нам нужно заготовить битборды с заранее вычисленными столбцами и строками, поэтому напишем еще этот кусок кода:
namespace BitboardRows {
static consteval std::array<Bitboard, 8> calc_rows() {
std::array<Bitboard, 8> rows{};
for (uint8_t y = 0; y < 8; y = y + 1) {
for (uint8_t x = 0; x < 8; x = x + 1) BitboardOperations::set_1(rows[y], y * 8 + x);
}
return rows;
}
static constexpr std::array<Bitboard, 8> Rows = BitboardRows::calc_rows();
static consteval std::array<Bitboard, 8> calc_inversion_rows() {
std::array<Bitboard, 8> inversion_rows{};
for (uint8_t i = 0; i < 8; i = i + 1) inversion_rows[i] = ~Rows[i];
return inversion_rows;
}
static constexpr std::array<Bitboard, 8> InversionRows = BitboardRows::calc_inversion_rows();
}
namespace BitboardColumns {
static consteval std::array<Bitboard, 8> calc_columns() {
std::array<Bitboard, 8> columns{};
for (uint8_t x = 0; x < 8; x = x + 1) {
for (uint8_t y = 0; y < 8; y = y + 1) BitboardOperations::set_1(columns[x], y * 8 + x);
}
return columns;
}
static constexpr std::array<Bitboard, 8> Columns = BitboardColumns::calc_columns();
static consteval std::array<Bitboard, 8> calc_inversion_columns() {
std::array<Bitboard, 8> inversion_columns{};
for (uint8_t i = 0; i < 8; i = i + 1) inversion_columns[i] = ~Columns[i];
return inversion_columns;
}
static constexpr std::array<Bitboard, 8> InversionColumns = BitboardColumns::calc_inversion_columns();
}Он супер медленный по сравнению с тем, что, вероятно, можно сделать при помощи битовых сдвигов, но это не критично, так как вычисления происходят все равно на этапе компиляции.
Хранение фигур
Из чего складывается позиция в шахматах? Из прав на рокировку, сложных правил про троекратное повторение позиции, счетчика 50 ходов и так далее, но база - это фигуры и пешки. Сейчас нужно написать структуру, которая будет хранить все фигуры и пешки. Но какие именно типы будет хранить структура? Разумеется, 12 битбордов о которых был разговор в предыдущем разделе, но этого мало. Так же стоит хранить битборды всех белых и всех черных фигур, всех фигур вообще, и битборды, обратные этим битбордам. Такие битборды могут быть составлены на основе базовых 12 битбордов и будут обновляться после обновления базовых битбордов. Но зачем они нам нужны? Например, при генерации ходов. Когда мы будем генерируем ходы, например, коня, нам нужно будет проверять содержится ли в клетке фигура того же цвета, что и конь, и если содержится - то такой ход не может быть выполнен.
Когда известно, что должна хранить структура, можно написать это в коде. Вот так это выглядит:
std::array<std::array<Bitboard, 6>, 2> _piece_bitboards{};
std::array<Bitboard, 2> _side_bitboards{};
std::array<Bitboard, 2> _inversion_side_bitboards{};
Bitboard _all;
Bitboard _empty;Для индексации по массивам битбордов нужно использовать константы. Вот они:
static constexpr uint8_t Pawn = 0;
static constexpr uint8_t Knight = 1;
static constexpr uint8_t Bishop = 2;
static constexpr uint8_t Rook = 3;
static constexpr uint8_t Queen = 4;
static constexpr uint8_t King = 5;
static constexpr uint8_t White = 0;
static constexpr uint8_t Black = 1;Так же стоит написать функцию, превращающую белое в черное, а черное в белое. Так как белое и черное у нас отмечено как 0 и 1, то для изменения цвета достаточно вызвать логическое отрицание:
uint8_t Pieces::inverse(uint8_t side) {
return !side;
}Еще нам понадобится возможность сравнивать наши структуры:
bool operator ==(Pieces left, Pieces right) {
for (uint8_t i = 0; i < 2; i = i + 1) {
for (uint8_t j = 0; j < 6; j = j + 1) {
if (left._piece_bitboards[i][j] != right._piece_bitboards[i][j]) return false;
}
}
return true;
}Уже было много сказано про хранение фигур, но еще не был создан конструктор, то есть пока неизвестно как инициализировать битборды.
Если говорить о второстепенных битбордах, то их можно легко инициализировать на основе основных, но это не помогает инициализировать основные:
void Pieces::update_bitboards() {
this->_side_bitboards[Pieces::White] = this->_piece_bitboards[Pieces::White][Pieces::Pawn] |
this->_piece_bitboards[Pieces::White][Pieces::Knight] |
this->_piece_bitboards[Pieces::White][Pieces::Bishop] |
this->_piece_bitboards[Pieces::White][Pieces::Rook] |
this->_piece_bitboards[Pieces::White][Pieces::Queen] |
this->_piece_bitboards[Pieces::White][Pieces::King];
this->_side_bitboards[Pieces::Black] = this->_piece_bitboards[Pieces::Black][Pieces::Pawn] |
this->_piece_bitboards[Pieces::Black][Pieces::Knight] |
this->_piece_bitboards[Pieces::Black][Pieces::Bishop] |
this->_piece_bitboards[Pieces::Black][Pieces::Rook] |
this->_piece_bitboards[Pieces::Black][Pieces::Queen] |
this->_piece_bitboards[Pieces::Black][Pieces::King];
this->_inversion_side_bitboards[Pieces::White] = ~this->_side_bitboards[Pieces::White];
this->_inversion_side_bitboards[Pieces::Black] = ~this->_side_bitboards[Pieces::Black];
this->_all = this->_side_bitboards[Pieces::White] | this->_side_bitboards[Pieces::Black];
this->_empty = ~this->_all;
}На самом деле инициализировать основные можно довольно легко при помощи операции установки единичного бита, которая был реализована в предыдущем разделе. Мы просто проходим по доске и, согласно шахматным правилам, расставляем фигуры. Производительность тут особо неважна, так как подобный конструктор вызывается крайне редко, но существует более хороший способ сделать это, а именно сделать поддержку нотации шотландского шахматиста, Форсайта Эдвардса, или FEN нотации (англ. Forsyth–Edwards Notation).
Идея очень проста. Сначала идет описания фигур на последней строке (та, на которой стоят фигуры черных в обычной расстановке). Каждой фигура обозначается первой буквой из ее английской записи, за исключением коня: он обозначается второй буквой, так как буква k уже занята королем. Причем если фигура черная, то она стоит в маленьком регистре, а если белая - то в большом. Если клетка пуста, то ставится единичка. Если несколько клеток подряд пусты, то цифра, отражающая сколько клеток пусто подряд. После того как последняя строка была описана ставится разделитель / и идет информация о строке ниже. Так происходит пока все строки не будут описаны. Ниже есть пару примеров, чтобы было понятнее.
Стандартная позиция |
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR |
После хода e2e4 |
rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR |
После хода d7d5 |
rnbqkbnr/ppp1pppp/8/3p4/4P3/8/PPPP1PPP/RNBQKBNR |
Все очень просто. Я немного обманул и это не все про FEN нотацию, там есть еще часть показывающая номер хода, права на рокировку, битое поле и так далее, но нам это не понадобится.
Зная это, можно написать такой вот код инициализирующий все битборды при помощи FEN строки:
Pieces::Pieces(const std::string& short_fen) {
uint8_t x = 0;
uint8_t y = 7;
uint8_t side;
for (auto buff : short_fen) {
if (buff == '/') {
x = 0;
y = y - 1;
}
else if (std::isdigit(buff)) {
x = x + buff - '0';
}
else {
if (std::isupper(buff)) {
buff = std::tolower(buff);
side = Pieces::White;
}
else side = Pieces::Black;
switch (buff) {
case 'p': BitboardOperations::set_1(this->_piece_bitboards[side][Pieces::Pawn], y * 8 + x); break;
case 'n': BitboardOperations::set_1(this->_piece_bitboards[side][Pieces::Knight], y * 8 + x); break;
case 'b': BitboardOperations::set_1(this->_piece_bitboards[side][Pieces::Bishop], y * 8 + x); break;
case 'r': BitboardOperations::set_1(this->_piece_bitboards[side][Pieces::Rook], y * 8 + x); break;
case 'q': BitboardOperations::set_1(this->_piece_bitboards[side][Pieces::Queen], y * 8 + x); break;
case 'k': BitboardOperations::set_1(this->_piece_bitboards[side][Pieces::King], y * 8 + x); break;
}
x = x + 1;
}
}
this->update_bitboards();
}Чтобы проверить, что все правильно можно написать такой вот оператор вывода:
std::ostream &operator<<(std::ostream &ostream, Pieces pieces) {
for (int8_t y = 7; y >= 0; y = y - 1) {
for (uint8_t x = 0; x < 8; x = x + 1) {
ostream << "| ";
if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::White][Pieces::Pawn], y * 8 + x)) ostream << "♙";
else if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::White][Pieces::Knight], y * 8 + x)) ostream << "♘";
else if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::White][Pieces::Bishop], y * 8 + x)) ostream << "♗";
else if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::White][Pieces::Rook], y * 8 + x)) ostream << "♖";
else if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::White][Pieces::Queen], y * 8 + x)) ostream << "♕";
else if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::White][Pieces::King], y * 8 + x)) ostream << "♔";
else if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::Black][Pieces::Pawn], y * 8 + x)) ostream << "♟";
else if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::Black][Pieces::Knight], y * 8 + x)) ostream << "♞";
else if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::Black][Pieces::Bishop], y * 8 + x)) ostream << "♝";
else if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::Black][Pieces::Rook], y * 8 + x)) ostream << "♜";
else if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::Black][Pieces::Queen], y * 8 + x)) ostream << "♛";
else if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::Black][Pieces::King], y * 8 + x)) ostream << "♚";
else ostream << " ";
ostream << " ";
}
ostream << "|\n";
}
return ostream;
}Zobrist хеширование
Часто нужно проверять одинаковы ли позиции (самое очевидно - правило троекратного повторения позиции, в будущем это понадобится нам еще для одной вещи). Это можно сделать используя структуру из предыдущего раздела, но для этого потребуется 12 операций сравнения, что дорого. Вместо этого можно хешировать позицию и хранить ее не в 12 64 битных числах, а в 1 и сравнивать не за 12 операций сравнения, а за 1. Разумеется нельзя сжать битборды в 12 раз, даже учитывая факт, что по памяти они не самые оптимальные, но мы можем это сделать если согласится с некоторыми рисками.
Итак, что нам нужно. Нам нужна функция, позволяющая сжимать позицию в одно число. Такая функция есть и называется она Zobrist хешированием, в честь Альберт Линдси Зобриста.
Идея в следующем. Нам надо заготовить константу для каждой фигуры, находящейся в каждой клетке доски. Итоге нам понадобится 12 * 64 = 768 констант, плюс несколько специальных констант для прав на рокировку и право хода (чтобы позиции с одинаковыми фигурами на доске, но с разными правами на ход или на рокировку давали разный хеш).
Это я и сделал. Я написал небольшой ГПСЧ работающий во времени компиляции для генерации случайных констант. Получилось вот что:
#include <cstdint>
#include <array>
#pragma once
namespace ZobristHashConsteval {
namespace PRNG {
static constexpr uint64_t Seed = 0x98f107;
static constexpr uint64_t Multiplier = 0x71abc9;
static constexpr uint64_t Summand = 0xff1b3f;
}
static consteval uint64_t next_random(uint64_t previous) {
return ZobristHashConsteval::PRNG::Multiplier * previous + ZobristHashConsteval::PRNG::Summand;
}
static consteval std::array<std::array<std::array<uint64_t, 6>, 2>, 64> calc_constants() {
std::array<std::array<std::array<uint64_t, 6>, 2>, 64> constants{};
uint64_t previous = ZobristHashConsteval::PRNG::Seed;
for (uint8_t square = 0; square < 64; square = square + 1) {
for (uint8_t side = 0; side < 2; side = side + 1) {
for (uint8_t type = 0; type < 6; type = type + 1) {
previous = ZobristHashConsteval::next_random(previous);
constants[square][side][type] = previous;
}
}
}
return constants;
}
static constexpr std::array<std::array<std::array<uint64_t, 6>, 2>, 64> Constants = calc_constants();
static constexpr uint64_t BlackMove = ZobristHashConsteval::next_random(ZobristHashConsteval::Constants[63][1][5]);
static constexpr uint64_t WhiteLongCastling = ZobristHashConsteval::next_random(ZobristHashConsteval::BlackMove);
static constexpr uint64_t WhiteShortCastling = ZobristHashConsteval::next_random(ZobristHashConsteval::WhiteLongCastling);
static constexpr uint64_t BlackLongCastling = ZobristHashConsteval::next_random(ZobristHashConsteval::WhiteShortCastling);
static constexpr uint64_t BlackShortCastling = ZobristHashConsteval::next_random(ZobristHashConsteval::BlackLongCastling);
}Используя эти константы, можно посчитать хеш текущей позиции при помощи применения XOR между всеми константами и нулем. Википедия дает такой псевдокод:
function hash(board):
h := 0
if is_black_turn(board):
h := h XOR table.black_to_move
for i from 1 to 64: # loop over the board positions
if board[i] ≠ empty:
j := the piece at board[i], as listed in the constant indices, above
h := h XOR table[i][j]
return hПолучается чтобы проверить равны ли позиции нам надо пройтись по всем клеткам, посчитать хеш и сравнить хеши, вместо того чтобы при проходе по всем клеткам сравнивать две позиции напрямую? Звучит как бред. И если бы это работало так на самом деле, то это действительно было бы бредом, но у такого хеширования есть замечательно свойство, делающее его очень эффективным.
Например, у нас есть позиция с двумя королями и пешкой. У нас известен ее хеш. Он получился так:
0 ^ WhiteKingOnD1 ^ BlackKingOnE7 ^ WhitePawnOnC4Теперь мы хотим добавить к этой позиции белого коня, стоящего на клетке C5. И если мы выполним XOR с текущим хешом и константой для белого коня на C5, то получится тот же самый хеш, что получился бы если бы мы посчитали его заново после добавления коня.
Другой пример. Мы хотим убрать белую пешку, стоящую на C4 из нашего хеша. Если мы выполним XOR с текущим хешом и константой этой белой пешки, стоящей на C4, то получится это:
0 ^ WhiteKingOnD1 ^ BlackKingOnE7 ^ WhitePawnOnC4 ^ WhitePawnOnC4После чего константы для белых пешек на C4 сократятся, так как XOR обладает самообратимостью, то есть
a ^ a = 0Получается, и чтобы добавить фигуру, и чтобы ее удалить из хеша, надо просто сделать XOR с текущим хешом и ключом этой фигуры на нужной позиции.
С флагами рокировки и хода все аналогично, для инверсии флага просто нужно выполнять XOR с существующим ключом и флагом.
Используя это знание и созданные константы можно легко реализовать структуру Zobrist хеша:
#include "ZobristHash.hpp"
ZobristHash::ZobristHash() = default;
ZobristHash::ZobristHash(Pieces pieces, bool black_move, bool w_l_castling, bool w_s_castling, bool b_l_castling, bool b_s_castling) {
this->_hash = 0;
if (black_move) this->invert_move();
if (w_l_castling) this->invert_w_l_castling();
if (w_s_castling) this->invert_w_s_castling();
if (b_l_castling) this->invert_b_l_castling();
if (b_s_castling) this->invert_b_s_castling();
uint8_t side;
for (uint8_t square = 0; square < 64; square = square + 1) {
if (BitboardOperations::get_bit(pieces._side_bitboards[Pieces::White], square)) side = Pieces::White;
else if (BitboardOperations::get_bit(pieces._side_bitboards[Pieces::Black], square)) side = Pieces::Black;
else continue;
for (uint8_t type = 0; type < 6; type = type + 1) {
if (BitboardOperations::get_bit(pieces._piece_bitboards[side][type], square)) {
this->invert_piece(square, type, side);
break;
}
}
}
}
bool operator ==(ZobristHash left, ZobristHash right) {
return (left._hash == right._hash);
}
bool operator <(ZobristHash left, ZobristHash right) {
return (left._hash < right._hash);
}
void ZobristHash::invert_piece(uint8_t square, uint8_t type, uint8_t side) {
this->_hash = this->_hash ^ ZobristHashConsteval::Constants[square][side][type];
}
void ZobristHash::invert_move() {
this->_hash = this->_hash ^ ZobristHashConsteval::BlackMove;
}
void ZobristHash::invert_w_l_castling() {
this->_hash = this->_hash ^ ZobristHashConsteval::WhiteLongCastling;
}
void ZobristHash::invert_w_s_castling() {
this->_hash = this->_hash ^ ZobristHashConsteval::WhiteShortCastling;
}
void ZobristHash::invert_b_l_castling() {
this->_hash = this->_hash ^ ZobristHashConsteval::BlackLongCastling;
}
void ZobristHash::invert_b_s_castling() {
this->_hash = this->_hash ^ ZobristHashConsteval::BlackShortCastling;
}Троекратное повторение позиции
В шахматах существует правило, называемое троекратным повторением позиции. Правило заключается в том, что если одна и та же позиция встречается трижды, то фиксируется ничья. Используя хеш функцию из предыдущей части, можно легко реализовать это правило.
Мы будем хранить вектор из Zobrist хешей, пополняющихся после каждого хода, а при запросе на количество повторений считать сколько есть копий последнего добавленного хеша. Это звучит очень не эффективно, но на самом деле в процессе игры можно очень часто очищать вектор, так как есть необратимые ходы. Если произошло движение пешки или взятие, то это уже нельзя отменить. Соответственно не может возникнуть никаких совпадений с позициями до продвижения пешки или взятия. Так что если происходит продвижение пешки или взятие можно полностью очистить весь вектор.
Вот полностью класс:
#include <vector>
#include "ZobristHash.hpp"
#pragma once
class RepetitionHistory {
public:
RepetitionHistory();
void add_position(ZobristHash hash);
void clear();
uint8_t get_repetition_number(ZobristHash hash);
private:
std::vector<ZobristHash> _hashes;
};#include "RepetitionHistory.hpp"
RepetitionHistory::RepetitionHistory() = default;
void RepetitionHistory::add_position(ZobristHash hash) {
this->_hashes.push_back(hash);
}
void RepetitionHistory::clear() {
this->_hashes.clear();
}
uint8_t RepetitionHistory::get_repetition_number(ZobristHash hash) {
uint8_t ctr = 0;
for (auto hash1 : this->_hashes) if (hash == hash1) ctr = ctr + 1;
return ctr;
}Хранение хода
Нам нужна структура, позволяющая хранить ход. Минимальное требование к такой структуре: она должна хранить информацию из какой клетки и куда, а также флаг хода со специальной информацией (например - информация о рокировках или в какую фигуру превращается пешка после продвижения). Я решил пойти дальше и хранить еще информацию о том какая фигура двигалась и какая фигура были съедена (если была). Это нужно для того, чтобы при применении хода не нужно было искать на каком битборде нужно убирать фигуру, а на какой ставить. Кто-то может возразить, что в любом случае это придется искать, просто не в функции применения хода, а в генераторе ходов, но он будет не совсем прав. При генерации ходов мы всегда знаем какая фигура двигалась, а иногда - какую съели. Таким образом мы меньше времени тратим на бессмысленный поиск по битбордам.
Вот заголовок структуры (саму реализацию показывать нет смысла). Обращу внимание только на то, что если защитника нет (то есть того, кого съели), то в переменную мы будем класть максимальное значение uint8_t, то есть 255.
#include <cstdint>
#pragma once
struct Move {
Move();
Move(uint8_t from, uint8_t to, uint8_t attacker_type, uint8_t attacker_side, uint8_t defender_type, uint8_t defender_side, uint8_t flag = Move::Flag::Default);
friend bool operator ==(Move left, Move right);
uint8_t _from;
uint8_t _to;
uint8_t _attacker_type;
uint8_t _attacker_side;
uint8_t _defender_type;
uint8_t _defender_side;
uint8_t _flag;
struct Flag {
static constexpr uint8_t Default = 0;
static constexpr uint8_t PawnLongMove = 1;
static constexpr uint8_t EnPassantCapture = 2;
static constexpr uint8_t WhiteLongCastling = 3;
static constexpr uint8_t WhiteShortCastling = 4;
static constexpr uint8_t BlackLongCastling = 5;
static constexpr uint8_t BlackShortCastling = 6;
static constexpr uint8_t PromoteToKnight = 7;
static constexpr uint8_t PromoteToBishop = 8;
static constexpr uint8_t PromoteToRook = 9;
static constexpr uint8_t PromoteToQueen = 10;
};
};Хранение позиции
После всего этого можно создать класс позиции. Это последний этап в представлении доски.
Что должна хранить позиция?
Во-первых, фигуры. Для них мы уже написали структуру, так что об этом беспокоится не нужно.
Во-вторых, битую клетку. Это нужно для реализации правила взятия на проходе. Если такой клетки нет, то в переменной будет лежать 255. как и в случае со структурой хода.
В-третьих, права на рокировку. Без комментариев.
В-четвертых, переменные, отражающие была ли сделана рокировка. Это не совсем то, что предыдущий пункт, так как права на рокировку можно потерять не сделав ее, а тут мы храним информацию о том была ли она сделана. Это знание поможет в разработке ИИ.
В-пятых, счетчик ходов. Это просто float переменная, добавляющая по 0.5 за каждый ход. Если переменная круглая, то ход белых. Если у нее есть дробная часть, то ход черных.
В-шестых, Zobrist хеш позиции. Структуру Zobrist хеша мы уже написали, об этом беспокоится не нужно. Главное, не забывать обновлять его после изменений в позиции.
В-седьмых, счетчик 50 ходов. Он будет такой же float переменной как и счетчик ходов, только будет обнуляться после продвижения пешки или взятия.
В-восьмых, история повторений для реализации правило троекратного повторения позиции. Класс для этого правила мы уже реализовали, остается только очищать его после продвижения пешки или взятия.
Этого достаточно. Вот как в коде выглядит все то, что я написал сверху:
Pieces _pieces;
uint8_t _en_passant;
bool _w_l_castling;
bool _w_s_castling;
bool _b_l_castling;
bool _b_s_castling;
bool _white_castling_happened;
bool _black_castling_happened;
float _move_ctr;
ZobristHash _hash;
float _fifty_moves_ctr;
RepetitionHistory _repetition_history;Теперь нам надо научится заполнять все это многообразие при помощи той же FEN строки и пары специальных переменных, отражающих права на рокировку. Выглядит это вот так:
Position::Position(const std::string& short_fen, uint8_t en_passant, bool w_l_castling, bool w_s_castling, bool b_l_castling, bool b_s_castling, float move_ctr) {
this->_pieces = {short_fen};
this->_en_passant = en_passant;
this->_w_l_castling = w_l_castling;
this->_w_s_castling = w_s_castling;
this->_b_l_castling = b_l_castling;
this->_b_s_castling = b_s_castling;
this->_white_castling_happened = false;
this->_black_castling_happened = false;
this->_move_ctr = move_ctr;
this->_hash = {this->_pieces, (this->_move_ctr - std::floor(this->_move_ctr) > 1e-4), this->_w_l_castling, this->_w_s_castling, this->_b_l_castling, this->_b_s_castling};
this->_repetition_history.add_position(this->_hash);
this->_fifty_moves_ctr = 0;
}Когда мы умеем хранить позиции, нам надо научится применять ходы. Однако просто взять и написать функцию нельзя, так как почти каждое действие требует обновление Zobrist хеша. В связи с этим было решено написать маленькие приватные методы, обновляющие переменные внутри позиции и, при необходимости, Zobrist хеш. Вот они все:
void Position::_add_piece(uint8_t square, uint8_t type, uint8_t side) {
if (!BitboardOperations::get_bit(this->_pieces._piece_bitboards[side][type], square)) {
BitboardOperations::set_1(this->_pieces._piece_bitboards[side][type], square);
this->_hash.invert_piece(square, type, side);
}
}
void Position::_remove_piece(uint8_t square, uint8_t type, uint8_t side) {
if (BitboardOperations::get_bit(this->_pieces._piece_bitboards[side][type], square)) {
BitboardOperations::set_0(this->_pieces._piece_bitboards[side][type], square);
this->_hash.invert_piece(square, type, side);
}
}
void Position::_change_en_passant(uint8_t en_passant) {
this->_en_passant = en_passant;
}
void Position::_remove_w_l_castling() {
if (this->_w_l_castling) {
this->_w_l_castling = false;
this->_hash.invert_w_l_castling();
}
}
void Position::_remove_w_s_castling() {
if (this->_w_s_castling) {
this->_w_s_castling = false;
this->_hash.invert_w_s_castling();
}
}
void Position::_remove_b_l_castling() {
if (this->_b_l_castling) {
this->_b_l_castling = false;
this->_hash.invert_b_l_castling();
}
}
void Position::_remove_b_s_castling() {
if (this->_b_s_castling) {
this->_b_s_castling = false;
this->_hash.invert_b_s_castling();
}
}
void Position::_update_move_ctr() {
this->_move_ctr = this->_move_ctr + 0.5f;
this->_hash.invert_move();
}
void Position::_update_fifty_moves_ctr(bool break_event) {
if (break_event) this->_fifty_moves_ctr = 0;
else this->_fifty_moves_ctr = this->_fifty_moves_ctr + 0.5f;
}Методы очень простые и используют все созданное в структуре Zobrist хеширования. Прокомментирую только 44 строчку, где break_event - обозначает именно взятие или продвижение пешки.
Когда у нас есть такой богатый набор можно приступать к функции применения хода. Несмотря на то, что я всеми силами пытался разбить ее на мелкие куски, получилось она довольно большая, так что показывать ее буду по кускам.
Самая основа - переместить фигуру и удалить взятую, если таковая была. Выглядит это все так:
this->_remove_piece(move._from, move._attacker_type, move._attacker_side);
this->_add_piece(move._to, move._attacker_type, move._attacker_side);
if (move._defender_type != 255) this->_remove_piece(move._to, move._defender_type, move._defender_side);После нам надо обработать все специальные флаги, объявленные в структуре Move:
switch (move._flag) {
case Move::Flag::Default:
break;
case Move::Flag::PawnLongMove:
this->_change_en_passant((move._from + move._to) / 2);
break;
case Move::Flag::EnPassantCapture:
if (move._attacker_side == Pieces::White) this->_remove_piece(move._to - 8, Pieces::Pawn, Pieces::Black);
else this->_remove_piece(move._to + 8, Pieces::Pawn, Pieces::White);
break;
case Move::Flag::WhiteLongCastling:
this->_remove_piece(0, Pieces::Rook, Pieces::White);
this->_add_piece(3, Pieces::Rook, Pieces::White);
this->_white_castling_happened = true;
break;
case Move::Flag::WhiteShortCastling:
this->_remove_piece(7, Pieces::Rook, Pieces::White);
this->_add_piece(5, Pieces::Rook, Pieces::White);
this->_white_castling_happened = true;
break;
case Move::Flag::BlackLongCastling:
this->_remove_piece(56, Pieces::Rook, Pieces::Black);
this->_add_piece(59, Pieces::Rook, Pieces::Black);
this->_black_castling_happened = true;
break;
case Move::Flag::BlackShortCastling:
this->_remove_piece(63, Pieces::Rook, Pieces::Black);
this->_add_piece(61, Pieces::Rook, Pieces::Black);
this->_black_castling_happened = true;
break;
case Move::Flag::PromoteToKnight:
this->_remove_piece(move._to, Pieces::Pawn, move._attacker_side);
this->_add_piece(move._to, Pieces::Knight, move._attacker_side);
break;
case Move::Flag::PromoteToBishop:
this->_remove_piece(move._to, Pieces::Pawn, move._attacker_side);
this->_add_piece(move._to, Pieces::Bishop, move._attacker_side);
break;
case Move::Flag::PromoteToRook:
this->_remove_piece(move._to, Pieces::Pawn, move._attacker_side);
this->_add_piece(move._to, Pieces::Rook, move._attacker_side);
break;
case Move::Flag::PromoteToQueen:
this->_remove_piece(move._to, Pieces::Pawn, move._attacker_side);
this->_add_piece(move._to, Pieces::Queen, move._attacker_side);
break;
}Это все что касается изменений с фигурами, так что можно обновить второстепенные битборды о которых было рассказано в самом начале статьи:
this->_pieces.update_bitboards();Если флаг перемещения не был длинным ходом пешки, то надо сбросить битое поле, так как взятие на проходе возможно только ответным ходом:
if (move._flag != Move::Flag::PawnLongMove) this->_change_en_passant(255);Еще нужно сбросить права на рокировку, если перемещались короли или ладьи. Фишка в том, что нам неважно какая фигура перемещалась (как это странно и не звучит), а важно перемещалась ли фигура с места на котором должны стоять короли и ладьи. Если да, то сбрасываем рокировку. Это может быть не совсем очевидно, так что давайте рассмотрим два случая. Первый - когда на клетке где должна стоять фигура она действительно стоит. После ее движения рокировка будет, естественно, невозможна. Второй - когда на клетке где должна стоять фигура ее нет. После ее движения права на рокировку не должны меняться, но раз на месте ладьи или короля стоит другая фигура, то это значит, что рокировка уже невозможно и от ее сброса ничего не изменится. Вот код:
switch (move._from) {
case 0:
this->_remove_w_l_castling();
break;
case 4:
this->_remove_w_l_castling();
this->_remove_w_s_castling();
break;
case 7:
this->_remove_w_s_castling();
break;
case 56:
this->_remove_b_l_castling();
break;
case 60:
this->_remove_b_l_castling();
this->_remove_b_s_castling();
break;
case 63:
this->_remove_b_s_castling();
break;
}После этого обновляем счетчик ходов:
this->_update_move_ctr();Обновляем счетчик 50 ходов:
this->_update_fifty_moves_ctr(move._attacker_type == Pieces::Pawn or move._defender_type != 255);Обновляем историю троекратного повторения позиции и, если произошел необратимый ход, очищаем (разумеется до добавления позиции):
if (move._attacker_type == Pieces::Pawn or move._defender_type != 255) this->_repetition_history.clear();
this->_repetition_history.add_position(this->_hash);Разделение ходов на псевдолегальные и легальные
Перед генерацией ходов нужно узнать разницу между псевдолегальными и легальными ходами.
Псевдолегальные ходы - это ходы без учета шахов. То есть все фигуры подчиняются своим правилам, конь ходит буквой "Г", слон не может перепрыгивать через фигуры и так далее, но шахи не учитываются. Это значит, что король может пойти на клетку битую вражеской фигурой, а шах просто проигнорировать.
Что такое легальные ходы объяснять не нужно. За них говорит их название.
В итоге нам нужно генерировать именно легальные ходы, но проблема в том, что без псевдолегальных сгенерировать легальные не получится. Именно поэтому следующие три части будут посвящены генерации псевдолегальных ходов.
Генерация псевдолегальных ходов коней и королей
Сгенерировать все псевдолегальные ходы коней и королей можно очень быстро. Всего за одну примитивную операцию процессора умноженную на количество коней и королей. Но для такой скорости необходимо заранее вычислить маски их перемещений для каждой клетки.
Производительность при вычислении масок неважна, поэтому я вычислил их максимально долгим, но читаемым алгоритмом:
#include "../PositionRepresentation/Bitboard.hpp"
#pragma once
namespace KnightMasks {
static consteval uint8_t abs_subtract(uint8_t left, uint8_t right) {
if (left >= right) return left - right;
return right - left;
}
static consteval std::array<Bitboard, 64> calc_masks() {
std::array<Bitboard, 64> masks{};
uint8_t dx;
uint8_t dy;
for (uint8_t x0 = 0; x0 < 8; x0 = x0 + 1) {
for (uint8_t y0 = 0; y0 < 8; y0 = y0 + 1) {
for (uint8_t x1 = 0; x1 < 8; x1 = x1 + 1) {
for (uint8_t y1 = 0; y1 < 8; y1 = y1 + 1) {
dx = KnightMasks::abs_subtract(x0, x1);
dy = KnightMasks::abs_subtract(y0, y1);
if ((dx == 2 and dy == 1) or (dx == 1 and dy == 2)) BitboardOperations::set_1(masks[y0 * 8 + x0], y1 * 8 + x1);
}
}
}
}
return masks;
}
static constexpr std::array<Bitboard, 64> Masks = KnightMasks::calc_masks();
}#include "../PositionRepresentation/Bitboard.hpp"
#pragma once
namespace KingMasks {
static consteval uint8_t abs_subtract(uint8_t left, uint8_t right) {
if (left >= right) return left - right;
return right - left;
}
static consteval std::array<Bitboard, 64> calc_masks() {
std::array<Bitboard, 64> masks{};
uint8_t dx;
uint8_t dy;
for (uint8_t x0 = 0; x0 < 8; x0 = x0 + 1) {
for (uint8_t y0 = 0; y0 < 8; y0 = y0 + 1) {
for (uint8_t x1 = 0; x1 < 8; x1 = x1 + 1) {
for (uint8_t y1 = 0; y1 < 8; y1 = y1 + 1) {
dx = KingMasks::abs_subtract(x0, x1);
dy = KingMasks::abs_subtract(y0, y1);
if (dx <= 1 and dy <= 1) BitboardOperations::set_1(masks[y0 * 8 + x0], y1 * 8 + x1);
}
}
}
}
return masks;
}
static constexpr std::array<Bitboard, 64> Masks = KingMasks::calc_masks();
}Теперь при генерации псевдолегальных ходов коней и короля достаточно одной операции:
Bitboard PsLegalMoveMaskGen::generate_knight_mask(Pieces pieces, uint8_t p, uint8_t side, bool only_captures) {
if (only_captures) {
return KnightMasks::Masks[p] & pieces._side_bitboards[Pieces::inverse(side)];
}
return KnightMasks::Masks[p] & pieces._inversion_side_bitboards[side];
}Bitboard PsLegalMoveMaskGen::generate_king_mask(Pieces pieces, uint8_t p, uint8_t side, bool only_captures) {
if (only_captures) {
return KingMasks::Masks[p] & pieces._side_bitboards[Pieces::inverse(side)];
}
return KingMasks::Masks[p] & pieces._inversion_side_bitboards[side];
}Обратите внимание на флаг only_captures. Если он включен, то будут сгенерированы только взятия. Может быть не сразу понятно зачем это надо, но оно нам пригодится, причем не один раз.
Генерация псевдолегальных ходов скользящих фигур
Сгенерировать похожим образом псевдолегальных ходы слонов, ферзей и ладей, к сожалению, нельзя, так как они подчиняются другим правилами. Существует, как минимум, два способа это сделать быстро, а именно - вращаемые битборды и магические. Идея последних заключается в том, чтобы закешировать результаты для всех расстановок блокирующих фигур.
К сожалению, меня не хватило на один из этих оптимизированных подходов, поэтому пришлось делать довольно медленным алгоритмом.
Сначала генерируются маски перемещений во всех направлениях со всех клеток. Выглядит этот вот так:
#include "../PositionRepresentation/Bitboard.hpp"
#pragma once
namespace SlidersMasks {
struct Direction {
static constexpr int8_t North = 0;
static constexpr int8_t South = 1;
static constexpr int8_t West = 2;
static constexpr int8_t East = 3;
static constexpr int8_t NorthWest = 4;
static constexpr int8_t NorthEast = 5;
static constexpr int8_t SouthWest = 6;
static constexpr int8_t SouthEast = 7;
};
static consteval Bitboard calc_mask(uint8_t p, int8_t direction) {
Bitboard mask = 0;
int8_t x = p % 8;
int8_t y = p / 8;
for (; ;) {
switch (direction) {
case SlidersMasks::Direction::North: y = y + 1; break;
case SlidersMasks::Direction::South: y = y - 1; break;
case SlidersMasks::Direction::West: x = x - 1; break;
case SlidersMasks::Direction::East: x = x + 1; break;
case SlidersMasks::Direction::NorthWest: y = y + 1; x = x - 1; break;
case SlidersMasks::Direction::NorthEast: y = y + 1; x = x + 1; break;
case SlidersMasks::Direction::SouthWest: y = y - 1; x = x - 1; break;
case SlidersMasks::Direction::SouthEast: y = y - 1; x = x + 1; break;
}
if (x > 7 or x < 0 or y > 7 or y < 0) break;
BitboardOperations::set_1(mask, y * 8 + x);
}
return mask;
}
static consteval std::array<std::array<Bitboard, 8>, 64> calc_masks() {
std::array<std::array<Bitboard, 8>, 64> masks{};
for (uint8_t i = 0; i < 64; i = i + 1) {
for (uint8_t j = 0; j < 8; j = j + 1) masks[i][j] = SlidersMasks::calc_mask(i, j);
}
return masks;
}
static constexpr std::array<std::array<Bitboard, 8>, 64> Masks = SlidersMasks::calc_masks();
};Опять же напомню, что это вычисляется на этапе компиляции, так что читаемость гораздо важнее производительности.
Теперь нам надо написать функцию, генерирующую луч в заданном направлении из заданной точки с учетом блокирующих фигур.
Для начала давайте получим эти блокирующие фигуры. Нам нужно пересечение всех фигур с данным нам лучом.
Bitboard blockers = SlidersMasks::Masks[p][direction] & pieces._all;После того как мы получили блокирующие фигуры мы обязаны проверить пусты ли они (очень скоро узнаете почему). И если пусты, то со включенным флагом only_captures возвращаем 0, а с выключенным - весь луч:
if (blockers == 0) {
if (only_captures) return 0;
return SlidersMasks::Masks[p][direction];
}Далее нам нужно найти первую клетку на которой стоит блокирующая фигура. Сделать это можно при помощи написанными нами функциями поиска первого бита или поиска последнего бита. Изначально может показаться, что так как мы ищем первый бит, то нам нужна функция поиска первого бита, но это не так. Нам нужен будет как и поиск первого бита, так и поиск последнего, зависит от направления луча. Итак, находим первую блокирующую фигуру:
uint8_t blocking_square;
if (bsr) blocking_square = BitboardOperations::bsr(blockers);
else blocking_square = BitboardOperations::bsf(blockers);Теперь заводим итоговый битборд:
Bitboard moves;И со включенным флагом только взятий заполняем его нулями, когда как с выключенным - результатом выполнения XOR'a луча, выпущенного из данной точки с лучом, выпущенным из первой блокирующей фигуры:
if (only_captures) moves = 0;
else moves = SlidersMasks::Masks[p][direction] ^ SlidersMasks::Masks[blocking_square][direction];Далее надо определить какого цвета первая блокирующая фигура. Если цвета, что и та которой генерируются перемещений, то ее не включаем. Если другого - включаем:
if (BitboardOperations::get_bit(pieces._side_bitboards[side], blocking_square)) BitboardOperations::set_0(moves, blocking_square);
else BitboardOperations::set_1(moves, blocking_square);Далее просто возвращаем результат:
return moves;Используя эту замечательную функцию можно легко сгенерировать все перемещения слона:
Bitboard PsLegalMoveMaskGen::generate_bishop_mask(Pieces pieces, uint8_t p, uint8_t side, bool only_captures) {
Bitboard nw = PsLegalMoveMaskGen::_calc_ray(pieces, p, side, only_captures, SlidersMasks::Direction::NorthWest, false);
Bitboard ne = PsLegalMoveMaskGen::_calc_ray(pieces, p, side, only_captures, SlidersMasks::Direction::NorthEast, false);
Bitboard sw = PsLegalMoveMaskGen::_calc_ray(pieces, p, side, only_captures, SlidersMasks::Direction::SouthWest, true);
Bitboard se = PsLegalMoveMaskGen::_calc_ray(pieces, p, side, only_captures, SlidersMasks::Direction::SouthEast, true);
return nw | ne | sw | se;
}Ладьи:
Bitboard PsLegalMoveMaskGen::generate_rook_mask(Pieces pieces, uint8_t p, uint8_t side, bool only_captures) {
Bitboard n = PsLegalMoveMaskGen::_calc_ray(pieces, p, side, only_captures, SlidersMasks::Direction::North, false);
Bitboard s = PsLegalMoveMaskGen::_calc_ray(pieces, p, side, only_captures, SlidersMasks::Direction::South, true);
Bitboard w = PsLegalMoveMaskGen::_calc_ray(pieces, p, side, only_captures, SlidersMasks::Direction::West, true);
Bitboard e = PsLegalMoveMaskGen::_calc_ray(pieces, p, side, only_captures, SlidersMasks::Direction::East, false);
return n | s | w | e;
}И ферзя, на основе предыдущих двух фигур:
Bitboard PsLegalMoveMaskGen::generate_queen_mask(Pieces pieces, uint8_t p, uint8_t side, bool only_captures) {
Bitboard bishop_mask = PsLegalMoveMaskGen::generate_bishop_mask(pieces, p, side, only_captures);
Bitboard rook_mask = PsLegalMoveMaskGen::generate_rook_mask(pieces, p, side, only_captures);
return bishop_mask | rook_mask;
}Такой подход медленнее вращаемых, а уж тем более магических битбордов, но все же быстрее, чем при простом представлении доски.
Генерация псевдолегальных ходов пешек
Уже было рассказано как генерировать взятия всех фигур, но еще ни слова не было сказано про пешки. А все из-за того, что пешки кардинально отличаются от фигур.
Во-первых, их очень много. Искать все пешки по доске, а потом использовать маскирование с каждой из них было бы, вероятно, даже более затратно, чем генерация ходов скользящих фигур.
Во-вторых, у них есть сложные правила вроде того, что если пешка не двигалась и следующие две клетки свободны, то она может перепрыгнуть через клетку.
В-третьих, у них перемещения не совпадают со взятиями, чего нельзя сказать ни про одну фигуру.
Из-за этих факторов перемещения пешек лучше генерировать совершенно другим способом. А именно - генерировать их всех сразу. Сейчас поясню что я имею ввиду.
У нас будет четыре функции. Одна генерирует все короткие ходы пешек, другая - все длинные, третья - все взятия налево, четвертая - все взятия направо. Но почему мы генерируем их отдельно? Почему нельзя одновременно, например, сгенерировать и взятия налево, и взятия направо? На самом деле я думаю, что можно. Просто я выбрал немного другой путь. Не нужно забывать, что кроме того, чтобы сгенерировать все маски перемещений нам надо сгенерировать ходы (мы писали структуру хода, надеюсь ее еще кто-то помнит). И эти битборды мы, в будущем, будем перебирать для генерации ходов. Проблема в том, что если мы сгенерируем в один битборд и взятия налево, и взятия направо, то мы не будем знать, смотря на битборд, какая из пешек туда может пойти. А если мы взятия генерируем отдельно, то по битборду можно понять, что попасть в такую-то клетку может пешка, находящаяся, например, на 9 индексах ниже.
Итак, приступим. Для начала научимся генерировать обычные ходы пешек. То есть на клетку вперед. Нам надо сдвинуть их на 1 по оси y (что эквивалентно сдвигу на 8 в сторону), после чего сделать объединение с пустыми клетками. Для черных пешек направление сдвига другое. Реализуется очень просто:
Bitboard PsLegalMoveMaskGen::generate_pawn_default_mask(Pieces pieces, uint8_t side) {
if (side == Pieces::White) {
return (pieces._piece_bitboards[Pieces::White][Pieces::Pawn] << 8) & pieces._empty;
}
return (pieces._piece_bitboards[Pieces::Black][Pieces::Pawn] >> 8) & pieces._empty;
}Теперь сгенерируем длинные ходы. Я сам долго не мог придумать как это сделать, пока не нашел очень простое решение: мы берем результат предыдущей функции, оставляем только те пешки, которые стояли на начальной строке, после чего, по сути, повторяем операцию. Очень просто:
Bitboard PsLegalMoveMaskGen::generate_pawn_long_mask(Pieces pieces, uint8_t side) {
Bitboard default_mask = PsLegalMoveMaskGen::generate_pawn_default_mask(pieces, side);
if (side == Pieces::White) {
return ((default_mask & BitboardRows::Rows[2]) << 8) & pieces._empty;
}
return ((default_mask & BitboardRows::Rows[5]) >> 8) & pieces._empty;
}Теперь взятия. Но перед тем как их генерировать надо немного подумать наперед. Нам не раз надо будет проверять, например, бьет ли пешка пустую клетку (самый простой пример - проверка битового поля при рокировке). Для этого мы должны добавить в нашу функцию генерации взятий флаг, который при включении будет генерировать не только псевдолегальные взятия, но и взятия всего, включая свои фигуры и пустые клетки. Этот флаг я назвал include_all_possible_captures, не забывайте о нем.
Когда о флаге поговорили, приступим к самой генерации. Нам надо сдвинуть битборд на 1 по оси y и 1 по оси x (эквивалентно сдвигу на 7 или 9 в сторону). Только вот если пешка, например, стоит с левого краю, то после сдвига налево у нее появятся взятия по правому краю, что ошибка. Поэтому после сдвига мы не только выполняем маскирование с фигурами противника (разумеется, если флаг include_all_possible_captures не включен), но и с битбордом, обратному крайнему столбцу (такие битборды мы генерировали в самом начале статьи).
Теперь мы полностью готовы для написания генератора взятий:
Bitboard PsLegalMoveMaskGen::generate_pawn_left_captures_mask(Pieces pieces, uint8_t side, bool include_all_possible_captures) {
if (side == Pieces::White) {
Bitboard mask = (pieces._piece_bitboards[Pieces::White][Pieces::Pawn] << 7) & BitboardColumns::InversionColumns[7];
if (!include_all_possible_captures) mask = mask & pieces._side_bitboards[Pieces::Black];
return mask;
}
Bitboard mask = (pieces._piece_bitboards[Pieces::Black][Pieces::Pawn] >> 9) & BitboardColumns::InversionColumns[7];
if (!include_all_possible_captures) mask = mask & pieces._side_bitboards[Pieces::White];
return mask;
}Bitboard PsLegalMoveMaskGen::generate_pawn_right_captures_mask(Pieces pieces, uint8_t side, bool include_all_possible_captures) {
if (side == Pieces::White) {
Bitboard mask = (pieces._piece_bitboards[Pieces::White][Pieces::Pawn] << 9) & BitboardColumns::InversionColumns[0];
if (!include_all_possible_captures) mask = mask & pieces._side_bitboards[Pieces::Black];
return mask;
}
Bitboard mask = (pieces._piece_bitboards[Pieces::Black][Pieces::Pawn] >> 7) & BitboardColumns::InversionColumns[0];
if (!include_all_possible_captures) mask = mask & pieces._side_bitboards[Pieces::White];
return mask;
}Проверка находится ли клетка под ударом
Нам часто придется проверять находится ли клетка под ударом (например - детектор шахов).
Проверить бьют ли клетку пешки противника можно очень легко из-за особенности генерации ходов пешек:
Bitboard opposite_pawns_left_captures = PsLegalMoveMaskGen::generate_pawn_left_captures_mask(pieces, Pieces::inverse(side), true);
Bitboard opposite_pawns_right_captures = PsLegalMoveMaskGen::generate_pawn_right_captures_mask(pieces, Pieces::inverse(side), true);
Bitboard opposite_pawns_captures = opposite_pawns_left_captures | opposite_pawns_right_captures;
if (BitboardOperations::get_bit(opposite_pawns_captures, p)) return true;Но что делать с фигурами? Самый наивный вариант - найти все фигуры противника, сгенерировать взятия найденных фигур и поискать в полученных битбордах интересующую нас клетку. Но это плохой вариант, так как можно сделать гораздо быстрее, причем как и по времени выполнения программы, так и по времени написания кода.
Все ходы в шахматах (за исключением ходов пешек, с которыми мы уже разобрались и рокировках о которых речи пока не было) обладают очень интересным свойством, которое очевидно, но мало кто замечает.
Если фигура походила с клетки A на клетку B, то следующим ходом (при отсутствии противника) она всегда может вернуться обратно на клетку А.
Из этого следует, что если фигура, находясь на клетки А, бьет клетку В, то точно такая же фигура, находясь на клетке B, будет бить клетку А.
А из этого следует, что поставив на клетку, которую мы хотим проверить, слона он будет бить вражеского слона тогда и только тогда, когда вражеский слон бьет эту клетку.
Аналогичная логика работает со всеми фигурами. Постарайтесь понять это, а чтобы было легче - снизу есть картинка, где черному королю шах (на картинке мат, но мат в каком-то смысле частный случай шаха).
Используя это знание, можно довольно легко проверить атакуется ли какая-то клетка фигурами:
if (PsLegalMoveMaskGen::generate_knight_mask(pieces, p, side, true) & pieces._piece_bitboards[Pieces::inverse(side)][Pieces::Knight]) return true;
if (PsLegalMoveMaskGen::generate_bishop_mask(pieces, p, side, true) & pieces._piece_bitboards[Pieces::inverse(side)][Pieces::Bishop]) return true;
if (PsLegalMoveMaskGen::generate_rook_mask(pieces, p, side, true) & pieces._piece_bitboards[Pieces::inverse(side)][Pieces::Rook]) return true;
if (PsLegalMoveMaskGen::generate_queen_mask(pieces, p, side, true) & pieces._piece_bitboards[Pieces::inverse(side)][Pieces::Queen]) return true;
if (PsLegalMoveMaskGen::generate_king_mask(pieces, p, side, true) & pieces._piece_bitboards[Pieces::inverse(side)][Pieces::King]) return true;И если ни пешки, ни фигура не прервали функцию, вернув истину, то надо вернуть ложь:
return false;Тип для хранения нескольких ходов
Мы уже в шаге от генератора легальных ходов, где надо будет отсеять псевдолегальные и оставить только легальные, после чего их засунуть в тип, содержащий ряд ходов.
Но какой это будет тип? Самое банальное - вектор, но вектор под капотом делает много лишних действий. Менее банальное - список, но он тоже не особо подходит, так как его долго обходить (для обхода нужна прыгать по указателям). В связи с этим надо создать "собственную структуру" на основе статического массива. Это решение показало себя как наиболее производительное.
Данная структура будет содержать в себе большой статический массив и переменную, показывающую размер массива. При добавлении элемента ход будет добавляться в последнюю не занятую ячейку, после чего размер массива будет увеличиваться на 1.
Но как выбрать размер этого большого статического массива? На том же chessprogrammingwiki я нашел, что позиция с наибольшим количеством легальных ходов содержит 218 ходов. Саму позицию я, к сожалению, не нашел (хотя и не очень искал), но все-таки предлагаю поверить chessprogrammingwiki и создать массив размером в 218 ходов.
Вот код этого класса. Он очень простой:
#include <array>
#include "../PositionRepresentation/Move.hpp"
#include "../PositionRepresentation/Pieces.hpp"
#pragma once
class MoveList {
public:
MoveList();
Move &operator[](uint8_t index);
Move operator[](uint8_t index) const;
void push_back(Move move);
[[nodiscard]] uint8_t size() const;
private:
std::array<Move, 218> _moves{};
uint8_t _size;
};#include "MoveList.hpp"
MoveList::MoveList() {
this->_size = 0;
}
Move &MoveList::operator[](uint8_t index) {
return this->_moves[index];
}
Move MoveList::operator[](uint8_t index) const {
return this->_moves[index];
}
void MoveList::push_back(Move move) {
this->_moves[this->_size] = move;
this->_size = this->_size + 1;
}
uint8_t MoveList::size() const {
return this->_size;
}Генерация легальных ходов
У нас есть генератор псевдолегальных ходов, алгоритм, проверяющий находится ли клетка под боем, тип для хранения ходов. Используя этот арсенал, можно сгенерировать все легальные ходы.
Существует два способа это сделать. Первый - делаем ход какой-то облегченной функцией, проверяем есть ли шах, если нет - ход легален. Второй основан на сложных проверках на двойные шахи, определения типа атакующей фигуры, определение связанных фигур и т.д. К сожалению, мне не хватило силы и мужества написать этот восхитительный способ, так что придется пользоваться первым.
Для начала нам надо научиться проверять является ли ход легальным. Простым способом это делается довольно просто, хоть и медленно:
bool LegalMoveGen::_is_legal(Pieces pieces, Move move, bool en_passant_capture) {
BitboardOperations::set_0(pieces._piece_bitboards[move._attacker_side][move._attacker_type], move._from);
BitboardOperations::set_1(pieces._piece_bitboards[move._attacker_side][move._attacker_type], move._to);
if (move._defender_type != 255) BitboardOperations::set_0(pieces._piece_bitboards[move._defender_side][move._defender_type], move._to);
if (en_passant_capture) {
if (move._attacker_side == Pieces::White) BitboardOperations::set_0(pieces._piece_bitboards[Pieces::Black][Pieces::Pawn], move._to - 8);
BitboardOperations::set_0(pieces._piece_bitboards[Pieces::White][Pieces::Pawn], move._to + 8);
}
pieces.update_bitboards();
if (PsLegalMoveMaskGen::in_danger(pieces, BitboardOperations::bsf(pieces._piece_bitboards[move._attacker_side][Pieces::King]), move._attacker_side)) return false;
return true;
}Обращаю внимание на то, что обрабатываем мы только флаг взятия на проходе, так как флаги продвижения на легальность ходов не влияют, а рокировка из-за своей необычности будет реализована иначе.
После того как эта функция готова можно начать генерировать ходы. Начнем с пешек, а именно с их взятий.
Сначала генерируем маски:
Bitboard pawn_left_captures_mask = PsLegalMoveMaskGen::generate_pawn_left_captures_mask(position._pieces, side, false);
Bitboard pawn_right_captures_mask = PsLegalMoveMaskGen::generate_pawn_right_captures_mask(position._pieces, side, false);После при помощи такой вот функции перегоняем их в список ходов:
void LegalMoveGen::_pawn_mask_to_moves(Pieces pieces, Bitboard mask, uint8_t attacker_side, int8_t attacker_index, bool look_for_defender, uint8_t flag, MoveList &moves) {
uint8_t defender_p;
uint8_t defender_type = 255;
Move move;
while (mask) {
defender_p = BitboardOperations::bsf(mask);
BitboardOperations::set_0(mask, defender_p);
if (look_for_defender) {
defender_type = 255;
for (uint8_t i = 0; i < 6; i = i + 1) {
if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::inverse(attacker_side)][i], defender_p)) {
defender_type = i;
break;
}
}
}
move = {(uint8_t)(defender_p + attacker_index), defender_p, Pieces::Pawn, attacker_side, defender_type, Pieces::inverse(attacker_side), flag};
if (LegalMoveGen::_is_legal(pieces, move, false)) {
if (defender_p < 8 or defender_p > 55) {
moves.push_back({(uint8_t)(defender_p + attacker_index), defender_p, 0, attacker_side, defender_type, Pieces::inverse(attacker_side), Move::Flag::PromoteToKnight});
moves.push_back({(uint8_t)(defender_p + attacker_index), defender_p, 0, attacker_side, defender_type, Pieces::inverse(attacker_side), Move::Flag::PromoteToBishop});
moves.push_back({(uint8_t)(defender_p + attacker_index), defender_p, 0, attacker_side, defender_type, Pieces::inverse(attacker_side), Move::Flag::PromoteToRook});
moves.push_back({(uint8_t)(defender_p + attacker_index), defender_p, 0, attacker_side, defender_type, Pieces::inverse(attacker_side), Move::Flag::PromoteToQueen});
}
else moves.push_back(move);
}
}
}Эта функция находит бит в маске (этот бит обозначает куда может пойти пешка), после, если включен флаг поиска защитника, находит защитника на этой клетке, далее формирует ход при помощи специального индекса по которому можно вычислить координаты атакующий пешки, и если получившийся ход легален, то он добавляется в список. Причем если клетка назначения стоит на последней строке, то генерируются ходы-продвижения.
При помощи этой функции также можно сгенерировать обычные ходы пешек, используя другую маску.
Но что делать с фигурами? Для них надо написать похожую функцию перебирания битбордов. Она гораздо легче:
void LegalMoveGen::_piece_mask_to_moves(Pieces pieces, Bitboard mask, uint8_t attacker_p, uint8_t attacker_type, uint8_t attacker_side, MoveList &moves) {
uint8_t defender_p;
uint8_t defender_type;
Move move;
while (mask) {
defender_p = BitboardOperations::bsf(mask);
BitboardOperations::set_0(mask, defender_p);
defender_type = 255;
for (uint8_t i = 0; i < 6; i = i + 1) {
if (BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::inverse(attacker_side)][i], defender_p)) {
defender_type = i;
break;
}
}
move = {attacker_p, defender_p, attacker_type, attacker_side, defender_type, Pieces::inverse(attacker_side)};
if (LegalMoveGen::_is_legal(pieces, move, false)) moves.push_back(move);
}
}Эта функция берет переданный битборд, находит там бит (этот бит отвечает куда может пойти фигура), находит защитника, стоящего на индексе этого бита, после чего формирует ход при помощи переданных координат атакующей фигуры и, если он легален, добавляет его в список.
Вот пример генерации всех ходов коней при помощи этой функции:
Bitboard all_knights = position._pieces._piece_bitboards[side][Pieces::Knight];
uint8_t attacker_p;
Bitboard mask;
while (all_knights) {
attacker_p = BitboardOperations::bsf(all_knights);
BitboardOperations::set_0(all_knights, attacker_p);
mask = PsLegalMoveMaskGen::generate_knight_mask(position._pieces, attacker_p, side, only_captures);
LegalMoveGen::_piece_mask_to_moves(position._pieces, mask, attacker_p, Pieces::Knight, side, moves);
}Также нужно сгенерировать все рокировки и взятия на проходе:
void LegalMoveGen::_add_en_passant_captures(Pieces pieces, uint8_t side, uint8_t en_passant, MoveList &moves) {
if (en_passant == 255) return;
Move move;
if (side == Pieces::White) {
if (en_passant % 8 != 7 and BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::White][Pieces::Pawn], en_passant - 7)) {
move = {(uint8_t)(en_passant - 7), en_passant, Pieces::Pawn, Pieces::White, 255, 255, Move::Flag::EnPassantCapture};
if (LegalMoveGen::_is_legal(pieces, move, true)) moves.push_back(move);
}
if (en_passant % 8 != 0 and BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::White][Pieces::Pawn], en_passant - 9)) {
move = {(uint8_t)(en_passant - 9), en_passant, Pieces::Pawn, Pieces::White, 255, 255, Move::Flag::EnPassantCapture};
if (LegalMoveGen::_is_legal(pieces, move, true)) moves.push_back(move);
}
}
else {
if (en_passant % 8 != 0 and BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::Black][Pieces::Pawn], en_passant + 7)) {
move = {(uint8_t)(en_passant + 7), en_passant, Pieces::Pawn, Pieces::Black, 255, 255, Move::Flag::EnPassantCapture};
if (LegalMoveGen::_is_legal(pieces, move, true)) moves.push_back(move);
}
if (en_passant % 8 != 7 and BitboardOperations::get_bit(pieces._piece_bitboards[Pieces::Black][Pieces::Pawn], en_passant + 9)) {
move = {(uint8_t)(en_passant + 9), en_passant, Pieces::Pawn, Pieces::Black, 255, 255, Move::Flag::EnPassantCapture};
if (LegalMoveGen::_is_legal(pieces, move, true)) moves.push_back(move);
}
}
}
void LegalMoveGen::_add_castling_moves(Pieces pieces, uint8_t side, bool long_castling, bool short_castling, MoveList &moves) {
uint8_t index;
uint8_t long_castling_flag;
uint8_t short_castling_flag;
if (side == Pieces::White) {
index = 0;
long_castling_flag = Move::Flag::WhiteLongCastling;
short_castling_flag = Move::Flag::WhiteShortCastling;
}
else {
index = 56;
long_castling_flag = Move::Flag::BlackLongCastling;
short_castling_flag = Move::Flag::BlackShortCastling;
}
if (long_castling and BitboardOperations::get_bit(pieces._piece_bitboards[side][Pieces::Rook], 0 + index) and BitboardOperations::get_bit(pieces._empty, 1 + index) and BitboardOperations::get_bit(pieces._empty, 2 + index) and BitboardOperations::get_bit(pieces._empty, 3 + index)) {
if (!PsLegalMoveMaskGen::in_danger(pieces, BitboardOperations::bsf(pieces._piece_bitboards[side][Pieces::King]), side) and !PsLegalMoveMaskGen::in_danger(pieces, 2 + index, side) and !PsLegalMoveMaskGen::in_danger(pieces, 3 + index, side)) moves.push_back({(uint8_t)(4 + index), (uint8_t)(2 + index), Pieces::King, side, 255, 255, long_castling_flag});
}
if (short_castling and BitboardOperations::get_bit(pieces._piece_bitboards[side][Pieces::Rook], 7 + index) and BitboardOperations::get_bit(pieces._empty, 5 + index) and BitboardOperations::get_bit(pieces._empty, 6 + index)) {
if (!PsLegalMoveMaskGen::in_danger(pieces, BitboardOperations::bsf(pieces._piece_bitboards[side][Pieces::King]), side) and !PsLegalMoveMaskGen::in_danger(pieces, 5 + index, side) and !PsLegalMoveMaskGen::in_danger(pieces, 6 + index, side)) moves.push_back({(uint8_t)(4 + index), (uint8_t)(6 + index), Pieces::King, side, 255, 255, short_castling_flag});
}
}Метод генерации ходов-взятий на проходе выглядит довольно не оптимальным, но он работает довольно редко из-за чего потерь в производительности почти нет.
Поиск ошибок
Было написано очень много кода и хорошо бы было поискать в нем ошибки. Существует способ сделать это довольно просто. Нужно взять какую-то позицию, после чего посчитать к скольким позициям можно прийти из этой спустя n ходов, а затем сверить эту информацию с информацией, полученной другими шахматными программистами.
Но какую позицию выбрать для теста? Самым банальным было бы взять стандартную, но толка от такого тестирования будет мало, ведь многие ошибки могут быть не выявлены на таком раннем этапе игры. Я выбрал эту позицию:
Она особенна тем, что когда-то давно вызвала ошибки во многих движках.
После того как мы определились с позицией можно начать писать тесты. Вот этот небольшой "класс" поможет протестировать наш код:
#include <chrono>
#include <iomanip>
#include "LegalMoveGen.hpp"
#pragma once
class LegalMoveGenTester {
public:
static void test();
private:
static uint64_t _get_nodes_number(const Position& position, uint8_t side, uint32_t depth);
static constexpr std::string_view Fen = "rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R";
static constexpr uint8_t EnPassant = 255;
static constexpr bool WLCastling = true;
static constexpr bool WSCastling = true;
static constexpr bool BLCastling = false;
static constexpr bool BSCastling = false;
static constexpr std::array<uint64_t, 6> Nodes = {1, 44, 1486, 62379, 2103487, 89941194};
};#include "LegalMoveGenTester.hpp"
#define nsecs std::chrono::high_resolution_clock::now().time_since_epoch().count()
void LegalMoveGenTester::test() {
Position position = {(std::string)LegalMoveGenTester::Fen, LegalMoveGenTester::EnPassant, LegalMoveGenTester::WLCastling, LegalMoveGenTester::WSCastling, LegalMoveGenTester::BLCastling, LegalMoveGenTester::BSCastling, 1};
uint64_t correct;
uint64_t got;
uint64_t time_start;
float speed;
for (uint32_t i = 0; i < 6; i = i + 1) {
time_start = nsecs;
correct = LegalMoveGenTester::Nodes[i];
got = LegalMoveGenTester::_get_nodes_number(position, Pieces::White, i);
speed = (float)got / ((float)(nsecs - time_start) / (float)1e+9) / (float)1e+6;
if (correct == got) std::cout << ANSI::Green << "Depth " << std::setw(4) << i << ". Correct: " << std::setw(18) << correct << ". Got: " << std::setw(18) << got << ". Speed: " << std::setw(10) << speed << " MNPS. OK." << ANSI::End << std::endl;
else std::cout << ANSI::Red << "Depth " << std::setw(4) << i << ". Correct: " << std::setw(18) << correct << ". Got: " << std::setw(18) << got << ". Speed: " << std::setw(10) << speed << " MNPS. Error." << ANSI::End << std::endl;
}
}
uint64_t LegalMoveGenTester::_get_nodes_number(const Position& position, uint8_t side, uint32_t depth) {
if (depth == 0) return 1;
uint64_t ctr = 0;
Position copy = position;
MoveList moves = LegalMoveGen::generate(copy, side);
Move move;
for (uint8_t i = 0; i < moves.size(); i = i + 1) {
move = moves[i];
copy = position;
copy.move(move);
ctr = ctr + LegalMoveGenTester::_get_nodes_number(copy, Pieces::inverse(side), depth - 1);
}
return ctr;
}Сейчас этот тест у меня, разумеется, выдает правильный результат, но получилось это не сразу.
Введение в шахматный ИИ
Спустя столько слов мы добрались до самого, на мой взгляд, интересного - программирование ИИ. Надеюсь, до этого места кто-то дочитал.
Типичный шахматный ИИ состоит из двух частей: статической и динамической оценки.
Статическая оценка извлекает внешние признаки из позиции. Смотрит на количество фигур, считает различные пешечные бонусы и т.д.
Динамическая оценка ищет комбинации и, как правило, использует статическую. Именно она понимает, что после такого хода белые потеряют ферзя, после другого у черных появится проходная пешка, а после этого будет пат.
Статическая оценка
Сейчас нужно разобраться с первой частью шахматного ИИ, а именно - со статической оценкой.
Давайте подумаем о том, что мы хотим получить. А получить мы хотим функцию, принимающую позицию, а возвращающую число. Причем чем больше число, тем лучше позиция для белых, а чем меньше число, тем лучше позиция для черных. Измерять оценку принято в сотых единицах пешки, так что если у белых перевес в две пешки, то оценка будет +200, а если у черных перевес в одну, то -100.
Материал
Первый фактор, самый очевидный и самый важный - материал. Материал показывает количество фигур. Чтобы учитывать материал надо обозначить для каждой фигуры ее стоимость. Я нашел на Википедии вот такую оценку фигур и решил ее использовать:
struct Material {
static constexpr int32_t Pawn = 100;
static constexpr int32_t Knight = 305;
static constexpr int32_t Bishop = 333;
static constexpr int32_t Rook = 563;
static constexpr int32_t Queen = 950;
};Посчитать материал очень просто, особенно при использовании битбордов:
int32_t StaticEvaluator::_material(Pieces pieces) {
int32_t material = 0;
material = material + StaticEvaluator::Material::Pawn * (BitboardOperations::count_1(pieces._piece_bitboards[Pieces::White][Pieces::Pawn]) - BitboardOperations::count_1(pieces._piece_bitboards[Pieces::Black][Pieces::Pawn]));
material = material + StaticEvaluator::Material::Knight * (BitboardOperations::count_1(pieces._piece_bitboards[Pieces::White][Pieces::Knight]) - BitboardOperations::count_1(pieces._piece_bitboards[Pieces::Black][Pieces::Knight]));
material = material + StaticEvaluator::Material::Bishop * (BitboardOperations::count_1(pieces._piece_bitboards[Pieces::White][Pieces::Bishop]) - BitboardOperations::count_1(pieces._piece_bitboards[Pieces::Black][Pieces::Bishop]));
material = material + StaticEvaluator::Material::Rook * (BitboardOperations::count_1(pieces._piece_bitboards[Pieces::White][Pieces::Rook]) - BitboardOperations::count_1(pieces._piece_bitboards[Pieces::Black][Pieces::Rook]));
material = material + StaticEvaluator::Material::Queen * (BitboardOperations::count_1(pieces._piece_bitboards[Pieces::White][Pieces::Queen]) - BitboardOperations::count_1(pieces._piece_bitboards[Pieces::Black][Pieces::Queen]));
return material;
}Мобильность
Второй фактор - мобильность. Чем больше развиты фигуры (то есть чем больше полей они бьют), тем лучше. Считать мы будем именно псевдолегальную мобильность (во-первых, генерация легальных ходов у нас значительно медленнее генерации псевдолегальных, во-вторых, легальная мобильность не делает программу значительно сильнее).
После того как стало ясно что это такое, надо подобрать константы для мобильности фигур. Эти значения (как и все дальше) подбирал я своими немного кривыми руками, так что они, вероятно, тоже немного кривые.
struct Mobility {
static constexpr int32_t Knight = 9;
static constexpr int32_t Bishop = 4;
static constexpr int32_t Rook = 3;
static constexpr int32_t Queen = 3;
};Реализуется вот так:
int32_t StaticEvaluator::_mobility(Pieces pieces) {
int32_t mobility = 0;
std::array<std::array<Bitboard, 6>, 2> iteration_masks = pieces._piece_bitboards;
uint8_t index;
int32_t knight_moves = 0;
int32_t bishop_moves = 0;
int32_t rook_moves = 0;
int32_t queen_moves = 0;
while (iteration_masks[Pieces::White][Pieces::Knight]) {
index = BitboardOperations::bsf(iteration_masks[Pieces::White][Pieces::Knight]);
BitboardOperations::set_0(iteration_masks[Pieces::White][Pieces::Knight], index);
knight_moves = knight_moves + BitboardOperations::count_1(PsLegalMoveMaskGen::generate_knight_mask(pieces, index, Pieces::White, false));
}
while (iteration_masks[Pieces::White][Pieces::Bishop]) {
index = BitboardOperations::bsf(iteration_masks[Pieces::White][Pieces::Bishop]);
BitboardOperations::set_0(iteration_masks[Pieces::White][Pieces::Bishop], index);
bishop_moves = bishop_moves + BitboardOperations::count_1(PsLegalMoveMaskGen::generate_bishop_mask(pieces, index, Pieces::White, false));
}
while (iteration_masks[Pieces::White][Pieces::Rook]) {
index = BitboardOperations::bsf(iteration_masks[Pieces::White][Pieces::Rook]);
BitboardOperations::set_0(iteration_masks[Pieces::White][Pieces::Rook], index);
rook_moves = rook_moves + BitboardOperations::count_1(PsLegalMoveMaskGen::generate_rook_mask(pieces, index, Pieces::White, false));
}
while (iteration_masks[Pieces::White][Pieces::Queen]) {
index = BitboardOperations::bsf(iteration_masks[Pieces::White][Pieces::Queen]);
BitboardOperations::set_0(iteration_masks[Pieces::White][Pieces::Queen], index);
queen_moves = queen_moves + BitboardOperations::count_1(PsLegalMoveMaskGen::generate_queen_mask(pieces, index, Pieces::White, false));
}
while (iteration_masks[Pieces::Black][Pieces::Knight]) {
index = BitboardOperations::bsf(iteration_masks[Pieces::Black][Pieces::Knight]);
BitboardOperations::set_0(iteration_masks[Pieces::Black][Pieces::Knight], index);
knight_moves = knight_moves - BitboardOperations::count_1(PsLegalMoveMaskGen::generate_knight_mask(pieces, index, Pieces::Black, false));
}
while (iteration_masks[Pieces::Black][Pieces::Bishop]) {
index = BitboardOperations::bsf(iteration_masks[Pieces::Black][Pieces::Bishop]);
BitboardOperations::set_0(iteration_masks[Pieces::Black][Pieces::Bishop], index);
bishop_moves = bishop_moves - BitboardOperations::count_1(PsLegalMoveMaskGen::generate_bishop_mask(pieces, index, Pieces::Black, false));
}
while (iteration_masks[Pieces::Black][Pieces::Rook]) {
index = BitboardOperations::bsf(iteration_masks[Pieces::Black][Pieces::Rook]);
BitboardOperations::set_0(iteration_masks[Pieces::Black][Pieces::Rook], index);
rook_moves = rook_moves - BitboardOperations::count_1(PsLegalMoveMaskGen::generate_rook_mask(pieces, index, Pieces::Black, false));
}
while (iteration_masks[Pieces::Black][Pieces::Queen]) {
index = BitboardOperations::bsf(iteration_masks[Pieces::Black][Pieces::Queen]);
BitboardOperations::set_0(iteration_masks[Pieces::Black][Pieces::Queen], index);
queen_moves = queen_moves - BitboardOperations::count_1(PsLegalMoveMaskGen::generate_queen_mask(pieces, index, Pieces::Black, false));
}
mobility = mobility + StaticEvaluator::Mobility::Knight * knight_moves;
mobility = mobility + StaticEvaluator::Mobility::Bishop * bishop_moves;
mobility = mobility + StaticEvaluator::Mobility::Rook * rook_moves;
mobility = mobility + StaticEvaluator::Mobility::Queen * queen_moves;
return mobility;
}Сдвоенные пешки
Третий фактор - сдвоенные пешки. Сдвоенная пешка считается слабостью. В моей программе сдвоенная пешка ухудшает оценку на 25:
static constexpr int32_t DoublePawn = -25;Реализуется просто:
int32_t StaticEvaluator::_pawn_structure_double_pawn(Pieces pieces) {
int32_t double_pawn = 0;
int32_t double_pawn_ctr = 0;
uint8_t white_pawns;
uint8_t black_pawns;
for (uint8_t x = 0; x < 8; x = x + 1) {
white_pawns = BitboardOperations::count_1(pieces._piece_bitboards[Pieces::White][Pieces::Pawn] & BitboardColumns::Columns[x]);
black_pawns = BitboardOperations::count_1(pieces._piece_bitboards[Pieces::Black][Pieces::Pawn] & BitboardColumns::Columns[x]);
double_pawn_ctr = double_pawn_ctr + std::max(0, white_pawns - 1);
double_pawn_ctr = double_pawn_ctr - std::max(0, black_pawns - 1);
}
double_pawn = double_pawn + StaticEvaluator::PawnStructure::DoublePawn * double_pawn_ctr;
return double_pawn;
}Соединенные пешки
Четвертый фактор - соединенные пешки. Соединенная пешка - пешка, защищенная другой. Наличие таких пешек является одним из признаков хорошей пешечной структуры. В моей программе соединенные пешки улучшают оценку на 12:
static constexpr int32_t ConnectedPawn = 12;Реализуется очень просто:
int32_t StaticEvaluator::_pawn_structure_connected_pawn(Pieces pieces) {
int32_t connected_pawn = 0;
int32_t connected_pawn_ctr = 0;
Bitboard white_captures = PsLegalMoveMaskGen::generate_pawn_left_captures_mask(pieces, Pieces::White, true) | PsLegalMoveMaskGen::generate_pawn_right_captures_mask(pieces, Pieces::White, true);
Bitboard black_captures = PsLegalMoveMaskGen::generate_pawn_left_captures_mask(pieces, Pieces::Black, true) | PsLegalMoveMaskGen::generate_pawn_right_captures_mask(pieces, Pieces::Black, true);
connected_pawn_ctr = connected_pawn_ctr + BitboardOperations::count_1(white_captures & pieces._piece_bitboards[Pieces::White][Pieces::Pawn]);
connected_pawn_ctr = connected_pawn_ctr - BitboardOperations::count_1(black_captures & pieces._piece_bitboards[Pieces::Black][Pieces::Pawn]);
connected_pawn = connected_pawn + StaticEvaluator::PawnStructure::ConnectedPawn * connected_pawn_ctr;
return connected_pawn;
}Продвижение пешек
Пятый фактор - продвижение пешек и тут будет кое-что особенное, о чем я упоминал в самом первом разделе. Самым простым способом реализации продвижения пешек было бы добавление всем пешкам бонус за близость к последней для них строке, но это не совсем верно. Проблема (если так можно выразится) заключается в том, что существуют проходные пешки, которых должно значительно сильнее тянуть вперед, чем обычные.
Но как проверить что пешка является проходной? Благодаря битбордам можно заранее рассчитать маски и проверка является ли пешка проходной будет происходить всего за 1-2 операции. Вот код рассчитывающий маски для опознавания проходных пешек:
#include <array>
#include "../Base/PositionRepresentation/Bitboard.hpp"
#pragma once
namespace PassedPawnMasks {
static consteval std::array<Bitboard, 64> calc_white_passed_pawn_masks() {
std::array<Bitboard, 64> masks{};
for (uint8_t x = 0; x < 8; x = x + 1) {
for (uint8_t y = 0; y < 8; y = y + 1) {
for (uint8_t y1 = y + 1; y1 < 8; y1 = y1 + 1) {
if (x != 0) BitboardOperations::set_1(masks[y * 8 + x], y1 * 8 + x - 1);
if (x != 7) BitboardOperations::set_1(masks[y * 8 + x], y1 * 8 + x + 1);
BitboardOperations::set_1(masks[y * 8 + x], y1 * 8 + x);
}
}
}
return masks;
}
static consteval std::array<Bitboard, 64> calc_black_passed_pawn_masks() {
std::array<Bitboard, 64> masks{};
for (uint8_t x = 0; x < 8; x = x + 1) {
for (uint8_t y = 0; y < 8; y = y + 1) {
for (int8_t y1 = y - 1; y1 >= 0; y1 = y1 - 1) {
if (x != 0) BitboardOperations::set_1(masks[y * 8 + x], y1 * 8 + x - 1);
if (x != 7) BitboardOperations::set_1(masks[y * 8 + x], y1 * 8 + x + 1);
BitboardOperations::set_1(masks[y * 8 + x], y1 * 8 + x);
}
}
}
return masks;
}
static constexpr std::array<Bitboard, 64> WhitePassedPawnMasks = PassedPawnMasks::calc_white_passed_pawn_masks();
static constexpr std::array<Bitboard, 64> BlackPassedPawnMasks = PassedPawnMasks::calc_black_passed_pawn_masks();
}Используя эти маски, можно легко реализовать этот фактор:
int32_t StaticEvaluator::_pawn_structure_pawn_promotion(Pieces pieces) {
int32_t pawn_promotion = 0;
Bitboard white_pawns = pieces._piece_bitboards[Pieces::White][Pieces::Pawn];
Bitboard black_pawns = pieces._piece_bitboards[Pieces::Black][Pieces::Pawn];
uint8_t index;
while (white_pawns) {
index = BitboardOperations::bsf(white_pawns);
BitboardOperations::set_0(white_pawns, index);
if (PassedPawnMasks::WhitePassedPawnMasks[index] & pieces._piece_bitboards[Pieces::Black][Pieces::Pawn]) pawn_promotion = pawn_promotion + StaticEvaluator::PawnStructure::DefaultPawnPromotion[index / 8];
else pawn_promotion = pawn_promotion + StaticEvaluator::PawnStructure::PassedPawnPromotion[index / 8];
}
while (black_pawns) {
index = BitboardOperations::bsf(black_pawns);
BitboardOperations::set_0(black_pawns, index);
if (PassedPawnMasks::BlackPassedPawnMasks[index] & pieces._piece_bitboards[Pieces::White][Pieces::Pawn]) pawn_promotion = pawn_promotion - StaticEvaluator::PawnStructure::DefaultPawnPromotion[7 - index / 8];
else pawn_promotion = pawn_promotion - StaticEvaluator::PawnStructure::PassedPawnPromotion[7 - index / 8];
}
return pawn_promotion;
}Константы я выбрал следующие:
static constexpr std::array<int32_t, 8> DefaultPawnPromotion = {0, 0, 0, 0, 10, 20, 30, 0};
static constexpr std::array<int32_t, 8> PassedPawnPromotion = {0, 50, 50, 50, 70, 90, 110, 0};Они показывают, что проходная пешка в 2 раза сильнее хочет дойти до последней строки, чем обычная. Помимо этого любая проходная пешка получает по 50 к оценке просто за то, что она есть.
Потерянная рокировка
Шестой фактор - потерянная рокировка. Если король потерял рокировку не рокировавшись, то это считается серьезной слабостью для безопасности короля. В моей программе сторона ухудшает свою оценку на 50 за каждую потерянную рокировку:
static constexpr int32_t CrashedCastling = -50;Реализуется предельно просто:
int32_t StaticEvaluator::_king_safety_crashed_castling(bool w_l_castling, bool w_s_castling, bool b_l_castling, bool b_s_castling, bool white_castling_happened, bool black_castling_happened) {
int32_t crashed_castling = 0;
if (!white_castling_happened) {
if (!w_l_castling) crashed_castling = crashed_castling + StaticEvaluator::KingSafety::CrashedCastling;
if (!w_s_castling) crashed_castling = crashed_castling + StaticEvaluator::KingSafety::CrashedCastling;
}
if (!black_castling_happened) {
if (!b_l_castling) crashed_castling = crashed_castling - StaticEvaluator::KingSafety::CrashedCastling;
if (!b_s_castling) crashed_castling = crashed_castling - StaticEvaluator::KingSafety::CrashedCastling;
}
return crashed_castling;
}Пешечный щит
Седьмой фактор - пешечный щит. Пешечный щит - один из самых простых способов реализации безопасности короля. Идея заключается в том, что после рокировки важно сохранять пешки на следующих двух строках. В моей программе сторона улучшает свою оценку на 33 за каждую такую пешку:
static constexpr int32_t PawnShield = 33;Для быстрого вычисления этого фактора имеет смысл рассчитать маски пешечных щитов заранее:
#include <array>
#include "../Base/PositionRepresentation/Bitboard.hpp"
#pragma once
namespace PawnShieldMasks {
static consteval std::array<Bitboard, 64> calc_white_pawn_shield_masks() {
std::array<Bitboard, 64> white_pawn_shield_masks{};
for (uint8_t x = 0; x < 8; x = x + 1) {
for (uint8_t y = 0; y < 7; y = y + 1) {
if (x != 0) BitboardOperations::set_1(white_pawn_shield_masks[y * 8 + x], (y + 1) * 8 + x - 1);
if (x != 7) BitboardOperations::set_1(white_pawn_shield_masks[y * 8 + x], (y + 1) * 8 + x + 1);
BitboardOperations::set_1(white_pawn_shield_masks[y * 8 + x], (y + 1) * 8 + x);
if (y != 6) {
if (x != 0) BitboardOperations::set_1(white_pawn_shield_masks[y * 8 + x], (y + 2) * 8 + x - 1);
if (x != 7) BitboardOperations::set_1(white_pawn_shield_masks[y * 8 + x], (y + 2) * 8 + x + 1);
BitboardOperations::set_1(white_pawn_shield_masks[y * 8 + x], (y + 2) * 8 + x);
}
}
}
return white_pawn_shield_masks;
}
static consteval std::array<Bitboard, 64> calc_black_pawn_shield_masks() {
std::array<Bitboard, 64> black_pawn_shield_masks{};
for (uint8_t x = 0; x < 8; x = x + 1) {
for (uint8_t y = 1; y < 8; y = y + 1) {
if (x != 0) BitboardOperations::set_1(black_pawn_shield_masks[y * 8 + x], (y - 1) * 8 + x - 1);
if (x != 7) BitboardOperations::set_1(black_pawn_shield_masks[y * 8 + x], (y - 1) * 8 + x + 1);
BitboardOperations::set_1(black_pawn_shield_masks[y * 8 + x], (y - 1) * 8 + x);
if (y != 1) {
if (x != 0) BitboardOperations::set_1(black_pawn_shield_masks[y * 8 + x], (y - 2) * 8 + x - 1);
if (x != 7) BitboardOperations::set_1(black_pawn_shield_masks[y * 8 + x], (y - 2) * 8 + x + 1);
BitboardOperations::set_1(black_pawn_shield_masks[y * 8 + x], (y - 2) * 8 + x);
}
}
}
return black_pawn_shield_masks;
}
static constexpr std::array<Bitboard, 64> WhitePawnShieldMasks = PawnShieldMasks::calc_white_pawn_shield_masks();
static constexpr std::array<Bitboard, 64> BlackPawnShieldMasks = PawnShieldMasks::calc_black_pawn_shield_masks();
}Далее реализовать этот фактор можно тоже очень просто:
int32_t StaticEvaluator::_king_safety_pawn_shield(Pieces pieces, bool white_castling_happened, bool black_castling_happened) {
int32_t pawn_shield = 0;
int32_t pawn_shield_ctr = 0;
if (white_castling_happened) {
Bitboard white_pawns = pieces._piece_bitboards[Pieces::White][Pieces::Pawn];
Bitboard white_pawn_shield = PawnShieldMasks::WhitePawnShieldMasks[BitboardOperations::bsf(pieces._piece_bitboards[Pieces::White][Pieces::King])];
pawn_shield_ctr = pawn_shield_ctr + BitboardOperations::count_1(white_pawns & white_pawn_shield);
}
if (black_castling_happened) {
Bitboard black_pawns = pieces._piece_bitboards[Pieces::Black][Pieces::Pawn];
Bitboard black_pawn_shield = PawnShieldMasks::BlackPawnShieldMasks[BitboardOperations::bsf(pieces._piece_bitboards[Pieces::Black][Pieces::King])];
pawn_shield_ctr = pawn_shield_ctr - BitboardOperations::count_1(black_pawns & black_pawn_shield);
}
pawn_shield = pawn_shield + StaticEvaluator::KingSafety::PawnShield * pawn_shield_ctr;
return pawn_shield;
}Два слона
Восьмой фактор - два слона. Если игрок смог сохранить двух слонов, то за это стоит улучшить оценку, так как два слона вместе могут отрезать пешки или короля. В моей программе два слона улучшают оценку на 50:
static constexpr int32_t TwoBishops = 50;Реализуется очень просто:
int32_t StaticEvaluator::_two_bishops(Pieces pieces) {
int32_t two_bishops = 0;
if (BitboardOperations::count_1(pieces._piece_bitboards[Pieces::White][Pieces::Bishop]) >= 2) two_bishops = two_bishops + StaticEvaluator::TwoBishops;
if (BitboardOperations::count_1(pieces._piece_bitboards[Pieces::Black][Pieces::Bishop]) >= 2) two_bishops = two_bishops - StaticEvaluator::TwoBishops;
return two_bishops;
}Особая оценка для эндшпиля
В эндшпиле компьютерные программы часто испытывают трудности, так как даже такой примитивный эндшпиль как король с ферзем против короля может содержать мат в 20-30 ходов, что не могут увидеть даже самые оптимизированные движки.
Одним из решений является подключение таблиц Налимова или таблиц syzygy - баз данных где хранятся стратегии для многих эндшпилей. При помощи этих баз ИИ может играть совершенно идеально, но у этих баз есть много недостатков. Один из них - сложность с подключением. Подключить какой-нибудь syzygy будет труднее, чем все, что вы прочитали до этого. Другой, более серьезный, - огромный размер. Эти БД могут весить терабайты, что не очень подходит для подобных движков.
Другим решением является особая оценка для эндшпиля. Она учитывает близость короля побеждающей стороны к королю проигрывающей, а также расстояние проигрывающего короля от центра:
static constexpr int32_t AttackerKingProximityToDefenderKing = 10;
static constexpr int32_t DistanceBetweenDefenderKingAndMiddle = 10;Но что такое эндшпиль? В моей программе это когда остается менее 9 фигур:
static constexpr int32_t MaximumPiecesForEndgame = 8;Реализовывается эндшпильная оценка просто:
int32_t StaticEvaluator::_endgame(Pieces pieces, bool white_leading) {
int32_t endgame = 0;
if (BitboardOperations::count_1(pieces._all) > StaticEvaluator::Endgame::MaximumPiecesForEndgame) return endgame;
uint8_t attacker_side;
uint8_t defender_side;
if (white_leading) {
attacker_side = Pieces::White;
defender_side = Pieces::Black;
}
else {
attacker_side = Pieces::Black;
defender_side = Pieces::White;
}
uint8_t attacker_king_p = BitboardOperations::bsf(pieces._piece_bitboards[attacker_side][Pieces::King]);
uint8_t attacker_king_x = attacker_king_p % 8;
uint8_t attacker_king_y = attacker_king_p / 8;
uint8_t defender_king_p = BitboardOperations::bsf(pieces._piece_bitboards[defender_side][Pieces::King]);
uint8_t defender_king_x = defender_king_p % 8;
uint8_t defender_king_y = defender_king_p / 8;
endgame = endgame + StaticEvaluator::Endgame::AttackerKingProximityToDefenderKing * (16 - std::abs(attacker_king_x - defender_king_x) - std::abs(attacker_king_y - defender_king_y));
endgame = endgame + StaticEvaluator::Endgame::DistanceBetweenDefenderKingAndMiddle * (std::abs(defender_king_x - 3) + std::abs(defender_king_y - 4));
if (!white_leading) endgame = -endgame;
return endgame;
}Минимакс
Мы закончили писать статическую оценку. Теперь самое время поговорить о динамической. Самой основой является минимакс алгоритм. Его идея очень проста: мы просто ищем наилучший ход для нашей стороны с предположением, что противник тоже будет делать наилучшие ходы. Вот псевдокод такого алгоритма:
int maxi( int depth ) {
if ( depth == 0 ) return evaluate();
int max = -oo;
for ( all moves) {
score = mini( depth - 1 );
if( score > max )
max = score;
}
return max;
}
int mini( int depth ) {
if ( depth == 0 ) return evaluate();
int min = +oo;
for ( all moves) {
score = maxi( depth - 1 );
if( score < min )
min = score;
}
return min;
}, где depth - количество полуходов на которое мы хотим искать, а evaluate() - функция статической оценки о которой был разговор выше.
Продление шахов
Улучшить программу можно продлевая шахи. Программа с продлением шахов может находить довольно глубокие матовые комбинации. Идея очень простая - если шах, то глубину не уменьшаем. Это не взрывает дерево поиска, так как шахи встречаются редко и при них доступно мало ходов.
Альфа-бета отсечение
Коэффициент ветвление шахмат - 40. Это значит, что после каждого хода есть в среднем 40 ответных ходов. В дебюте и эндшпиле этот показатель куда ниже, но в середине игры - 40. Теперь, используя эти данные, предлагаю посчитать сколько надо будет оценить позиций после 20 полуходов:
Это огромное число, даже если бы можно было оценивать трилларды позиций в секунду, что в миллионы раз больше вычислительной мощности всей планеты, то мы бы не успели даже за год. Однако, такие топовые движки как Stockfish умудряются считать на такую глубину за секунды. Очевидно, что Stockfish не оценивает все десять в тридцатой степени позиций.
Один из эффективнейших способов пропустить большинство позиций в минимаксе - альфа-бета отсечение. Идея заключается в том, что если мы понимаем, что оценка на текущей ветви по-любому будет хуже оценки на предыдущей, то считать дальше нет смысла. Внизу есть иллюстрация из Википедии, она довольно наглядная:
На картинке видно, что в самом вверху мы ищем максимум трех чисел (3, 6, 5). Эти три числа получаются из минимума других двух чисел, но минимум последней ветви мы считаем не полностью, так как изначально у нас попалась пятерка и независимо от того, что пойдет дальше эта ветвь не подходит, так как результат будет не больше 5, а для изменения максимума с 6 на что-то другое нужно 7 или больше.
Вот псевдокод:
int alphaBetaMax( int alpha, int beta, int depthleft ) {
if ( depthleft == 0 ) return evaluate();
for ( all moves) {
score = alphaBetaMin( alpha, beta, depthleft - 1 );
if( score >= beta )
return beta; // fail hard beta-cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}
int alphaBetaMin( int alpha, int beta, int depthleft ) {
if ( depthleft == 0 ) return evaluate();
for ( all moves) {
score = alphaBetaMax( alpha, beta, depthleft - 1 );
if( score <= alpha )
return alpha; // fail hard alpha-cutoff
if( score < beta )
beta = score; // beta acts like min in MiniMax
}
return beta;
}Для запуска поиска надо вызвать одну из этих функций (зависит от цвета стороны) с alpha равной отрицательной бесконечности и beta равной положительной бесконечности.
Продление взятий
Представим следующую ситуацию. Происходит анализ позиции с глубиной 8. Особо выделяется одна ветка и одна группа веток. Ветка интересно тем, что на 8 глубине мы забираем ферзя, а группа веток интересна тем, что на 2 глубине мы выигрываем коня. ИИ, естественно, выберет ветку с выигрышем ферзя, а не что-то из группы веток где мы выигрываем коня. Но это будет неправильная оценка, так как коня мы реально выигрывали, а на 9 глубине ветки с выигрышем ферзя забирали нашего ферзя, то есть никакого выигрыша не было.
Такой эффект называется эффектом горизонта. Казалось бы, что мы можем сделать, нашему ИИ просто не хватило глубины, но в этом суждении сразу две ошибки: увеличение глубины тут не поможет (подобные конфузы просто станут происходить на более глубокой глубине), а сделать с этим как раз есть что.
Идея в том, что после завершения основного поиска не возвращать статическую оценку, а запускать новый без лимита по глубине, но с рассмотрением только взятий. Разумеется, если взятия не улучшают оценку, то надо прерывать такой просмотр, а не возвращать оценку после всех взятий.
Сортировка ходов
Эффективность альфа-бета отсечения зависит от порядка ходов. Если ходы отсортированы от лучшего к худшему, то можно оценить только чуть больше корня от общего числа комбинаций, а это очень мало. С другой стороны, если ходы будут отсортированы от худшего к лучшему, то мы вообще не получим никакого профита от альфа-бета отсечения.
Зная это, надо постараться отсортировать ходы от лучшего к худшему. Это, естественно, вряд-ли получится, но приличное преимущество можно получить.
Для сортировки ходов можно воспользоваться принципом наиболее ценная жертва - наименее ценный нападающий. Идея в том, что съесть пешкой ферзя, как правило, гораздо выгоднее, чем наоборот. Согласно этому принципу, все взятия помещаются вперед и сортируются при помощи этого принципа, а тихие ходы остаются в конце.
Но как сортировать тихие ходы? Существует один способ. Он не такой эффективный как сортировка взятий, но тоже позволяет отсечь часть ходов. Идея в том, что двигать фигуру под пешку противника обычно плохая идея.
Зная все это, можно написать простую сортировку пузырьком. Она работает за квадрат, но ходов не так много из-за чего сортировка даже с плохой асимптотикой работает быстро:
#include "MoveSorter.hpp"
MoveList MoveSorter::sort(Pieces pieces, MoveList moves) {
for (uint8_t i = 0; i < moves.size() - 1; i = i + 1) {
for (uint8_t j = 0; j < moves.size() - i - 1; j = j + 1) {
if (MoveSorter::_evaluate_move(pieces, moves[j]) < MoveSorter::_evaluate_move(pieces, moves[j + 1])) std::swap(moves[j], moves[j + 1]);
}
}
return moves;
}
int32_t MoveSorter::_evaluate_move(Pieces pieces, Move move) {
int32_t evaluation = 0;
if (move._attacker_type != Pieces::Pawn) {
Bitboard opponent_pawn_attacks = PsLegalMoveMaskGen::generate_pawn_left_captures_mask(pieces, Pieces::inverse(move._attacker_side), true) | PsLegalMoveMaskGen::generate_pawn_right_captures_mask(pieces, Pieces::inverse(move._attacker_side), true);
if (BitboardOperations::get_bit(opponent_pawn_attacks, move._to)) {
switch (move._attacker_type) {
case Pieces::Knight: evaluation = evaluation - StaticEvaluator::Material::Knight; break;
case Pieces::Bishop: evaluation = evaluation - StaticEvaluator::Material::Bishop; break;
case Pieces::Rook: evaluation = evaluation - StaticEvaluator::Material::Rook; break;
case Pieces::Queen: evaluation = evaluation - StaticEvaluator::Material::Queen; break;
// Король не может быть на поле, битое пешкой противника.
}
}
}
if (move._defender_type != 255) {
switch (move._defender_type) {
case Pieces::Pawn: evaluation = evaluation + 1000 * StaticEvaluator::Material::Pawn; break;
case Pieces::Knight: evaluation = evaluation + 1000 * StaticEvaluator::Material::Knight; break;
case Pieces::Bishop: evaluation = evaluation + 1000 * StaticEvaluator::Material::Bishop; break;
case Pieces::Rook: evaluation = evaluation + 1000 * StaticEvaluator::Material::Rook; break;
case Pieces::Queen: evaluation = evaluation + 1000 * StaticEvaluator::Material::Queen; break;
// Короля нельзя съесть.
}
switch (move._attacker_type) {
case Pieces::Pawn: evaluation = evaluation - StaticEvaluator::Material::Pawn; break;
case Pieces::Knight: evaluation = evaluation - StaticEvaluator::Material::Knight; break;
case Pieces::Bishop: evaluation = evaluation - StaticEvaluator::Material::Bishop; break;
case Pieces::Rook: evaluation = evaluation - StaticEvaluator::Material::Rook; break;
case Pieces::Queen: evaluation = evaluation - StaticEvaluator::Material::Queen; break;
// Если съедает король, то ничего не вычитаем, ведь короля нельзя съесть, следовательно, никакого ответного взятия, вероятно, не будет.
}
}
return evaluation;
}Теперь перед началом альфа-бета поиска нужно отсортировать ходы, что даст прибавку к скорости.
Хеш таблица
Помните начало статьи? Там был разговор про Zobrist хеширование. Тогда я упомянул, что оно нам пригодится для троекратного повторения позиции и еще кое-чего. Так вот: это кое-чего как раз хеш таблица.
Идея в том, что дерево игры - не совсем дерево, а, скорее, граф. Многие позиции постоянно повторяются и считать их каждый раз по-новому довольно не разумно. Вместо этого стоит пробовать использовать результаты предыдущих поисков.
Создадим структуру записи:
#include "../Base/PositionRepresentation/ZobristHash.hpp"
#pragma once
struct Entry {
Entry();
Entry(ZobristHash hash, int32_t depth, uint8_t best_move_index);
friend bool operator <(Entry left, Entry right);
ZobristHash _hash;
int32_t _depth;
uint8_t _best_move_index;
};Оператор меньше показывает меньше ли хеш:
bool operator <(Entry left, Entry right) {
return (left._hash < right._hash);
}Эта структура содержит сам хеш (для возможности сравнивать текущую позицию с позицией из записи), глубину поиска на которой получен результат (чтобы оставлять в таблице только наиболее просчитанные результаты) и индекс лучшего хода.
При поиске мы будем добавлять в некоторое хранилище такие записи, а перед началом поиска искать запись с совпадающим хешом и пробовать ход по лучшему индексу в надежде, что он вызовет отсечку дерева.
Но в каком хранилище мы будем хранить эти записи? Я предлагаю в множестве, то есть в std::set. Множество - список, но не простой, ведь при вставке он бинарным поиском вставляет в список элемент так, чтобы сохранялась сортировка, что позволяет находить там элементы тоже за логарифм благодаря тому же бинарному поиску.
Вот так выглядит полный код хеш таблицы:
#include <set>
#include "Entry.hpp"
#pragma one
class TranspositionTable {
public:
TranspositionTable();
void add_entry(Entry entry);
uint8_t try_to_find_best_move_index(ZobristHash hash);
private:
std::set<Entry> _set;
};#include "TranspositionTable.hpp"
TranspositionTable::TranspositionTable() = default;
void TranspositionTable::add_entry(Entry entry) {
auto hash_copy = this->_set.find(entry);
if (hash_copy == this->_set.end() or hash_copy->_depth < entry._depth) this->_set.insert(entry);
}
uint8_t TranspositionTable::try_to_find_best_move_index(ZobristHash hash) {
auto entry = this->_set.find({hash, 0, 0});
if (entry == this->_set.end()) return 255;
return entry->_best_move_index;
}Итеративное углубление
Цель итеративного углубления позволить контролировать время выполнения альфа-бета отсечения. Проблема в том, что мы не можем просто так прервать поиск, так как его результат будет бессмысленным в этом случае.
Вместо этого мы сначала выполняем поиск на глубину 1, потом на глубину 2, потом на глубину 3 и т.д. Благодаря этому поиск всегда можно прервать и вернуть результат предыдущего. Это звучит не эффективно, так как результат каждого нового поиска переделывает все предыдущие, но при использования хеш таблицы он может быть выполнен еще быстрее, чем обычный поиск из-за большого числа отсечений.
База дебютов
Если взять все что было сверху и написать это, то получится довольно хороший алгоритм за исключением одной детали. Он будет абсолютно детерминированным и все партии будут 1 в 1. Играть против такого противника довольно скучно, поэтому стоит добавить базу дебютов из которой будут выбираться случайные ходы.
В качестве базы дебютов я буду использовать первые 6 ходов (или 12 полуходов) из заранее скаченных тысяч игр гроссмейстеров. Вот первые несколько строк из базы:
e2e4 e7e5 g1f3 b8c6 f1c4 f8c5 c2c3 g8f6 d2d3 d7d6 b2b4 c5b6
d2d4 g8f6 c2c4 g7g6 f2f3 d7d5 c4d5 f6d5 e2e4 d5b6 b1c3 f8g7
c2c4 e7e6 b1c3 d7d5 d2d4 g8f6 c4d5 e6d5 c1g5 c7c6 d1c2 f8e7
e2e4 e7e6 d2d4 d7d5 b1d2 c7c5 g1f3 c5d4 f3d4 g8f6 e4d5 d8d5
e2e4 e7e5 g1f3 b8c6 f1b5 g8f6 d2d3 f8c5 b5c6 d7c6 b1d2 e8g8
c2c4 e7e5 b1c3 g8f6 g1f3 b8c6 g2g3 f8b4 c3d5 b4c5 f1g2 d7d6
d2d4 g8f6 c2c4 e7e6 g1f3 d7d5 b1c3 c7c5 c4d5 f6d5 e2e4 d5c3
d2d4 g8f6 c2c4 g7g6 f2f3 d7d6 e2e4 f8g7 g1e2 e8g8 c1e3 c7c5
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 d2d3 d7d6
d2d4 g8f6 c2c4 e7e6 b1c3 f8b4 d1c2 e8g8 c1g5 c7c5 d4c5 d8a5
e2e4 g7g6 d2d4 f8g7 b1c3 d7d6 c1e3 a7a6 a2a4 g8f6 h2h3 e8g8
e2e4 e7e5 g1f3 b8c6 f1b5 g8f6 e1g1 f6e4 d2d4 e4d6 b5c6 d7c6
c2c4 c7c5 g2g3 b8c6 f1g2 g7g6 g1f3 f8g7 e1g1 d7d6 b1c3 f7f5
d2d4 d7d5 c2c4 c7c6 g1f3 g8f6 d1b3 d5c4 b3c4 c8g4 b1d2 e7e6 При инициализации базы ходы будут загружаться в вектор, причем эти ходы будут трансформироваться в нашу специальную структуру хода, а также проверяться на легальность (вдруг в базе ошибка). При поиске будет искаться ответ. Вот полный код:
#include <fstream>
#include <sstream>
#include <tuple>
#include "../Base/MoveGeneration/LegalMoveGen.hpp"
#pragma once
class OpeningBook {
public:
OpeningBook();
OpeningBook(const std::string& path);
std::tuple<Move, int32_t> try_to_find_move(const Position& position);
private:
std::vector<std::vector<Move>> _moves;
};#include "OpeningBook.hpp"
OpeningBook::OpeningBook() = default;
OpeningBook::OpeningBook(const std::string& path) {
std::ifstream file(path);
if (!file.is_open()) {
std::cout << ANSI::Red << "Could not find the opening book." << ANSI::End << std::endl;
std::exit(255);
}
std::string game;
std::stringstream game_thread;
std::string string_move;
uint8_t from;
uint8_t to;
MoveList possible_moves;
bool move_found;
Position buff;
while (std::getline(file, game)) {
game_thread = std::stringstream(game);
this->_moves.resize(this->_moves.size() + 1);
buff = {"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR", 255, true, true, true, true, 1};
while (game_thread >> string_move and game_thread.good()) {
from = (string_move[1] - '1') * 8 + string_move[0] - 'a';
to = (string_move[3] - '1') * 8 + string_move[2] - 'a';
possible_moves = LegalMoveGen::generate(buff, buff._move_ctr - std::floor(buff._move_ctr) > 1e-7);
move_found = false;
for (uint8_t i = 0; i < possible_moves.size(); i = i + 1) {
if (possible_moves[i]._from == from and possible_moves[i]._to == to) {
this->_moves.back().push_back(possible_moves[i]);
buff.move(possible_moves[i]);
move_found = true;
break;
}
}
if (!move_found) {
std::cout << ANSI::Red << "Error in the opening book." << ANSI::End << std::endl;
std::exit(255);
}
}
}
file.close();
}
std::tuple<Move, int32_t> OpeningBook::try_to_find_move(const Position& position) {
Position buff;
std::vector<Move> possible_moves;
bool move_exist;
for (int32_t game = 0; game < this->_moves.size(); game = game + 1) {
buff = {"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR", 255, true, true, true, true, 1};
if (buff._pieces == position._pieces) {
move_exist = false;
for (auto added_move : possible_moves) {
if (added_move == this->_moves[game][0]) {
move_exist = true;
break;
}
}
if (!move_exist) possible_moves.push_back(this->_moves[game][0]);
continue;
}
for (int32_t move = 0; move < this->_moves[game].size() - 1; move = move + 1) {
buff.move(this->_moves[game][move]);
if (buff._pieces == position._pieces) {
move_exist = false;
for (auto added_move : possible_moves) {
if (added_move == this->_moves[game][move + 1]) {
move_exist = true;
break;
}
}
if (!move_exist) possible_moves.push_back(this->_moves[game][move + 1]);
}
}
}
if (possible_moves.empty()) {
return std::make_tuple(Move(), 0);
}
return std::make_tuple(possible_moves[time(nullptr) % possible_moves.size()], possible_moves.size());
}ИИ. Финал
Настало время написать итоговый класс. Комментировать его не вижу смысла, так как он делает все то же самое о чем я говорил последнее время. Вот код:
#include <chrono>
#include <future>
#include <unistd.h>
#include <iomanip>
#include "../Base/MoveGeneration/LegalMoveGen.hpp"
#include "MoveSorter.hpp"
#include "TranspositionTable.hpp"
#include "OpeningBook.hpp"
#pragma once
class AI {
public:
AI();
AI(const std::string& opening_book_path);
Move best_move(const Position& position, uint8_t side, int32_t min_ms, int32_t max_ms);
private:
OpeningBook _opening_book;
static std::tuple<int32_t, Move> _best_move(const Position& position, uint8_t side, int32_t depth, TranspositionTable &tt);
static std::tuple<int32_t, Move> _alpha_beta_min(Position position, int32_t alpha, int32_t beta, int32_t depth_left, int32_t depth_current, TranspositionTable &tt);
static std::tuple<int32_t, Move> _alpha_beta_max(Position position, int32_t alpha, int32_t beta, int32_t depth_left, int32_t depth_current, TranspositionTable &tt);
static int32_t _alpha_beta_min_only_captures(const Position& position, int32_t alpha, int32_t beta, int32_t depth_current);
static int32_t _alpha_beta_max_only_captures(const Position& position, int32_t alpha, int32_t beta, int32_t depth_current);
struct Infinity {
static constexpr int32_t Negative = -1e+9;
static constexpr int32_t Positive = 1e+9;
};
};#include "AI.hpp"
#define nsecs std::chrono::high_resolution_clock::now().time_since_epoch().count()
static std::atomic<bool> stop_search;
static int64_t evaluated;
static int32_t maximal_depth;
static int32_t tt_cutoffs;
AI::AI() = default;
AI::AI(const std::string& opening_book_path) {
this->_opening_book = {opening_book_path};
}
Move AI::best_move(const Position& position, uint8_t side, int32_t min_ms, int32_t max_ms) {
std::cout << std::endl;
StaticEvaluator::evaluate(position._pieces, position._w_l_castling, position._w_s_castling, position._b_l_castling, position._b_s_castling, position._white_castling_happened, position._black_castling_happened, true);
int64_t time_start = nsecs;
stop_search = false;
TranspositionTable tt;
std::tuple<Move, int32_t> opening_book_result = this->_opening_book.try_to_find_move(position);
std::cout << ANSI::Green << "Number of available moves in the opening book: " << std::get<1>(opening_book_result) << "." << ANSI::End << std::endl;
if (std::get<1>(opening_book_result)) {
usleep(std::max((int64_t)0, (min_ms - (nsecs - time_start) / (int64_t)1e+6) * (int64_t)1e+3));
return std::get<0>(opening_book_result);
}
std::cout << ANSI::Green << "Search started." << std::endl;
int32_t best_move_evaluation;
Move best_move;
std::future<std::tuple<int32_t, Move>> best_move_thread;
bool update_best_move;
for (int32_t i = 1; i < 1e+3; i = i + 1) {
evaluated = 0;
maximal_depth = 0;
tt_cutoffs = 0;
best_move_thread = std::async(AI::_best_move, position, side, i, std::ref(tt));
update_best_move = true;
while (best_move_thread.wait_for(std::chrono::seconds(0)) != std::future_status::ready) {
if ((nsecs - time_start) / (int32_t)1e+6 >= max_ms) {
update_best_move = false;
break;
}
usleep(20000);
}
if (update_best_move or i == 1) std::tie(best_move_evaluation, best_move) = best_move_thread.get();
else {
stop_search = true;
break;
}
std::cout << "Base depth: " << std::setw(4) << i << ". Maximal depth: " << std::setw(4) << maximal_depth << ". Evaluation: " << std::setw(6) << (float)best_move_evaluation / 100.0f << " pawns. Evaluated (this iteration): " << std::setw(10) << evaluated << ". TT cutoffs (this iteration): " << std::setw(10) << tt_cutoffs << ". Time (full search): " << std::setw(10) << (nsecs - time_start) / (int32_t)1e+6 << " ms." << std::endl;
if (best_move_evaluation > AI::Infinity::Positive - 2000 or best_move_evaluation < AI::Infinity::Negative + 2000) break;
}
usleep(std::max((int64_t)0, (min_ms - (nsecs - time_start) / (int64_t)1e+6) * (int64_t)1e+3));
std::cout << "Search finished." << std::endl << ANSI::End;
return best_move;
}
std::tuple<int32_t, Move> AI::_best_move(const Position& position, uint8_t side, int32_t depth, TranspositionTable &tt) {
if (side == Pieces::White) return AI::_alpha_beta_max(position, AI::Infinity::Negative, AI::Infinity::Positive, depth, 0, tt);
return AI::_alpha_beta_min(position, AI::Infinity::Negative, AI::Infinity::Positive, depth, 0, tt);
}
std::tuple<int32_t, Move> AI::_alpha_beta_min(Position position, int32_t alpha, int32_t beta, int32_t depth_left, int32_t depth_current, TranspositionTable &tt) {
if (stop_search) return std::make_tuple(0, Move());
if (depth_current > maximal_depth) maximal_depth = depth_current;
if (depth_left == 0) return std::make_tuple(AI::_alpha_beta_min_only_captures(position, alpha, beta, depth_current), Move());
if (position._fifty_moves_ctr >= 50 or position._repetition_history.get_repetition_number(position._hash) >= 3) return std::make_tuple(0, Move());
MoveList moves = LegalMoveGen::generate(position, Pieces::Black);
moves = MoveSorter::sort(position._pieces, moves);
Move move;
Move best_move;
uint8_t best_move_index;
bool in_check = PsLegalMoveMaskGen::in_danger(position._pieces, BitboardOperations::bsf(position._pieces._piece_bitboards[Pieces::Black][Pieces::King]), Pieces::Black);
if (moves.size() == 0) {
if (in_check) return std::make_tuple(AI::Infinity::Positive - depth_current, Move());
return std::make_tuple(0, Move());
}
int32_t evaluation;
Position copy;
uint8_t tt_result = tt.try_to_find_best_move_index(position._hash);
for (uint8_t i = 0; i < moves.size(); i = i + 1) {
if (tt_result >= moves.size()) move = moves[i];
else {
if (i == 0) move = moves[tt_result];
else {
if (i == tt_result) move = moves[0];
else move = moves[i];
}
}
copy = position;
copy.move(move);
evaluation = std::get<0>(AI::_alpha_beta_max(copy, alpha, beta, depth_left - !in_check, depth_current + 1, tt));
if (evaluation <= alpha) {
if (tt_result >= moves.size() or i != 0) tt.add_entry({position._hash, depth_left, best_move_index});
else tt_cutoffs = tt_cutoffs + 1;
return std::make_tuple(alpha, best_move);
}
if (evaluation < beta) {
best_move = move;
best_move_index = i;
beta = evaluation;
}
}
tt.add_entry({position._hash, depth_left, best_move_index});
return std::make_tuple(beta, best_move);
}
std::tuple<int32_t, Move> AI::_alpha_beta_max(Position position, int32_t alpha, int32_t beta, int32_t depth_left, int32_t depth_current, TranspositionTable &tt) {
if (stop_search) return std::make_tuple(0, Move());
if (depth_current > maximal_depth) maximal_depth = depth_current;
if (depth_left == 0) return std::make_tuple(AI::_alpha_beta_max_only_captures(position, alpha, beta, depth_current), Move());
if (position._fifty_moves_ctr >= 50 or position._repetition_history.get_repetition_number(position._hash) >= 3) return std::make_tuple(0, Move());
MoveList moves = LegalMoveGen::generate(position, Pieces::White);
moves = MoveSorter::sort(position._pieces, moves);
Move move;
Move best_move;
uint8_t best_move_index;
bool in_check = PsLegalMoveMaskGen::in_danger(position._pieces, BitboardOperations::bsf(position._pieces._piece_bitboards[Pieces::White][Pieces::King]), Pieces::White);
if (moves.size() == 0) {
if (in_check) return std::make_tuple(AI::Infinity::Negative + depth_current, Move());
return std::make_tuple(0, Move());
}
int32_t evaluation;
Position copy;
uint8_t tt_result = tt.try_to_find_best_move_index(position._hash);
for (uint8_t i = 0; i < moves.size(); i = i + 1) {
if (tt_result >= moves.size()) move = moves[i];
else {
if (i == 0) move = moves[tt_result];
else {
if (i == tt_result) move = moves[0];
else move = moves[i];
}
}
copy = position;
copy.move(move);
evaluation = std::get<0>(AI::_alpha_beta_min(copy, alpha, beta, depth_left - !in_check, depth_current + 1, tt));
if (evaluation >= beta) {
if (tt_result >= moves.size() or i != 0) tt.add_entry({position._hash, depth_left, best_move_index});
else tt_cutoffs = tt_cutoffs + 1;
return std::make_tuple(beta, best_move);
}
if (evaluation > alpha) {
best_move = move;
best_move_index = i;
alpha = evaluation;
}
}
tt.add_entry({position._hash, depth_left, best_move_index});
return std::make_tuple(alpha, best_move);
}
int32_t AI::_alpha_beta_min_only_captures(const Position& position, int32_t alpha, int32_t beta, int32_t depth_current) {
if (stop_search) return 0;
if (depth_current > maximal_depth) maximal_depth = depth_current;
int32_t evaluation = StaticEvaluator::evaluate(position._pieces, position._w_l_castling, position._w_s_castling, position._b_l_castling, position._b_s_castling, position._white_castling_happened, position._black_castling_happened);
evaluated = evaluated + 1;
if (evaluation <= alpha) return alpha;
if (evaluation < beta) beta = evaluation;
MoveList moves = LegalMoveGen::generate(position, Pieces::Black, true);
moves = MoveSorter::sort(position._pieces, moves);
Move move;
Position copy;
for (uint8_t i = 0; i < moves.size(); i = i + 1) {
move = moves[i];
copy = position;
copy.move(move);
evaluation = AI::_alpha_beta_max_only_captures(copy, alpha, beta, depth_current + 1);
if (evaluation <= alpha) return alpha;
if (evaluation < beta) beta = evaluation;
}
return beta;
}
int32_t AI::_alpha_beta_max_only_captures(const Position& position, int32_t alpha, int32_t beta, int32_t depth_current) {
if (stop_search) return 0;
if (depth_current > maximal_depth) maximal_depth = depth_current;
int32_t evaluation = StaticEvaluator::evaluate(position._pieces, position._w_l_castling, position._w_s_castling, position._b_l_castling, position._b_s_castling, position._white_castling_happened, position._black_castling_happened);
evaluated = evaluated + 1;
if (evaluation >= beta) return beta;
if (evaluation > alpha) alpha = evaluation;
MoveList moves = LegalMoveGen::generate(position, Pieces::White, true);
moves = MoveSorter::sort(position._pieces, moves);
Move move;
Position copy;
for (uint8_t i = 0; i < moves.size(); i = i + 1) {
move = moves[i];
copy = position;
copy.move(move);
evaluation = AI::_alpha_beta_min_only_captures(copy, alpha, beta, depth_current + 1);
if (evaluation >= beta) return beta;
if (evaluation > alpha) alpha = evaluation;
}
return alpha;
}Итог
Я написал небольшой интерфейс на SDL2 для этого движка. Для счастливых пользователей deb дистрибутивов Linux я подготовил deb пакет. Тем не менее, SDL2 полностью кроссплатформенный, так что никаких проблем с компилированием под Windows или MacOS быть не должно.
Играет довольно неплохо, меня с треском обыгрывает. На одном очень популярном шахматном сайте (подсказка: он заблокирован в РФ) я нашел ботов и уровень их игры измеренный в Эло. Сыграв с ними при помощи своего движка, я примерно вычислил количество Эло этого движка, получилось около 2000, по крайней мере в рамках этой платформы.
Спасибо за чтение. Код и deb пакет есть тут.
upd. Если будете компилировать сами, то крайне желательно включить оптимизацию (в gcc -O3), а также link-time оптимизацию, дабы компилятор мог заинлайнить код многих легких функций (в gcc -flto).
Комментарии (51)
napa3um
12.08.2022 03:11+7Отличная статья, отличное введение в шахматные движки! Очень хорошо, спасибо :)
serg_meus
12.08.2022 07:50+3Спасибо за статью. Если прикрутите к своему движку UCI интерфейс, энтузиасты компьютерных шахмат, например с computerchess.org.uk, возьмут его в свои соревнования и Вы сможете поточнее узнать его силу игры, ну и просто поболеть. Но это при условиях, что движок стабильный, то есть не зависает и не вылетает, понимает все правила шахмат, можно задать размер хэша, можно отключить встроенную книгу. И главное, у движка есть exe-файл.
reloaded2000
12.08.2022 08:37+5В программировании особо не разбираюсь, но шахматы люблю, как и околошахматную тематику. Прочитал поэтому с удовольствием, даже несмотря на то, что из кода мало что понял. Спасибо большое Автору!
Очень порадовало что то, какие Автор вбирал критерии оценки позиции, практически отсылает к "человеческой" оценке, коей тот же стокфиш похвастаться зачастую не может: иной раз смотришь на позицию, оцениваешь её, а движок предлагает ну явно "нечеловеческие" ходы и "нечеловеческий" анализ (не истину сам не претендую, уровень не тот - много подобных разборов с гроссмейстерами можно найти при желании, натыкался частенько).
У компьютерных шахмат есть одна особенность: у людей шахматы - это битва не только интеллектов, но и нервов, выдержки, психики, а иногда (внезапно) и физической подготовки (посиди-ка 2 часа за доской с пульсом под 130 в пиках в стрессе); а у машины - только интеллекта (в данном случае, наверное, логики). Тема сложная, потому что сегодня шахматисты всех мастей, конечно, постоянно пользуются движками (даже такой любитель как я), и в "заготовленных" позициях тоже делают "компьютерные" ходы. Но к той позиции нужно еще прийти, правильно оценить нюансы, идеи... И где сегодня начинаются человеческие шахматы сказать уж очень сложно. Скоро победит тот, у кого память на шаблоны лучше?
Лично мне нравятся оба направления. С одной стороны - я за прогресс, за ИИ, за развитие: за нечеловеческим ходом зачастую следует глубокая тактика, которая превращается в шикарные атаки с жертвами. Но и романтику игры очень уж хочется сохранить. Вы посмотрите на партии классиков, шахматистов эпохи романтических шахмат, как они чувствовали позицию, какие ходы делали - их стокфиш часто критикует и опровергает в пух и прах, но они выигрывали и то было искусство. Не потеряем ли что-то важное здесь? Может эти 2 направления нужно как-то разделить? Как думаете?
napa3um
12.08.2022 11:40+3движок предлагает ну явно "нечеловеческие" ходы и "нечеловеческий" анализ
В последних версиях Стокфиша коэффициенты подобраны нейросеткой в триллионах игр самим с собой. Да, это не человеческие коэффициенты, это коэффициенты математического бога :).
Может эти 2 направления нужно как-то разделить?
Давно разделили, окончательно - примерно после игры Каспарова против Deep Blue :). Человеческие и компьютерные шахматы - две отдельные дисциплины.
reloaded2000
12.08.2022 12:04В последних версиях Стокфиша коэффициенты подобраны нейросеткой в триллионах игр самим с собой. Да, это не человеческие коэффициенты, это коэффициенты математического бога :)
Да, он стал очень хорош )
Давно разделили, окончательно - примерно после игры Каспарова против Deep Blue :). Человеческие и компьютерные шахматы - две отдельные дисциплины.
Да, вы конечно правы, формально оно так. Я скорее хотел сказать, что когда почти каждый шахматист анализируя свои партии и готовясь к матчам в дисциплине "человечьи шахматы" использует движок (помните, я чуть выше написал про память и шаблоны), границы этого разделения затираются. Но тут как-будто тупик, и можно наверное только побрюзжать - не запретишь же людям пользоваться достижениями прогресса. Así es la vida. А брюзжать не будем, не надо )
bevertax
13.08.2022 08:16+1Надо просто играть в шахматы Фишера, где начальная расстановка сильных фигур определяется произвольно
Nedder
12.08.2022 08:38+3Шестой фактор - потерянная рокировка. Если король потерял рокировку не рокировавшись, то это считается серьезной слабостью для безопасности короля.
Я бы тут не согласился полностью с таким утверждением. Да, в большинстве случаев это верно, но не в 100% и даже не в 90%. Чем меньше фигур на доске, тем менее важна становится рокировка, т.к. король становиться очень сильной фигурой и должен не прятаться от нападений с помощью рокировки, а наоборот двигаться в гущу событий.
Многие гроссмейстеры часто даже в самом начале игры выбирают вариант с потерей рокировки (например размен центральных пешек и после этого размен ферзей, где один король теряет право на рокировку), т.к. там имеються свои преимущества.
reloaded2000
12.08.2022 08:45Да, там есть такие детали, тоже подметил: при закрытом центре например ничего плохого в короле в центре не бывает обычно, или либо в раннем эндшпиле... Там еще критерий эндшпиля в статье спорный - насколько я понимаю, у людей эндшпиль там, где ферзей поменяли (хотя тут более субъективно, есть и эндшпили при ферзях). Но в целом же для самодельного движка неплохо! Мне показалось что при прочих критериях кроме рокировки эта потеря в оценке позиции при нерокированом короле должна нивелироваться более-менее за счет других плюшек если они есть.
Nedder
12.08.2022 08:56+1Можно считать штрафные пункты в зависимости от общего количества фигур (своих и противника) на доске, например от 50 до 0. Просто отсутствие ферзей еще особо ничего не меняет (можно поставить штраф 45), а вот если осталось на доске ладья + одна легкая фигура или две-три легких фигуры - там ценность рокировки стремиться уже к нулю.
reloaded2000
12.08.2022 09:03А может тогда пойти чуть дальше и условно выделить классические "малый центр" и "центр"? Например, отсутствие ферзей при отсутствии связанных пешек на вертикалях "малого центра" - штраф за (не)рокировку больше, чем при их наличии (закрытый центр). И скомбинировать это с Вашей идеей. А вот при ферзях и закрытом центре без рокировки уже немного хуже. А при ферзях и при открытом центре - туши свет )
Кстати, контроль над центром либо по флангам же тоже должны оцениваться при оценке позиции.
andy_p
12.08.2022 08:43+3Я бы предложил некоторые улучшения:
Запоминать main variation - наилучшую последовательность ходов в поиске и использовать ее при поиске следующего хода в алфа-бета отсечении в сортировке ходов.
Вместо простого альфа-бета отсечения использовать поиск с нулевым окном.
Вместо std::set использовать std::unordered_set.
Zara6502
12.08.2022 09:07Спасибо, почитал про битовые манипуляции, с темой не был знаком.
А для чего на титульной картинке пылесос?
rat1
12.08.2022 09:23+1В свое время читал книгу "Программирование шахмат и других логических игр" Евгений Корнилов, там достаточно подробно разбиралось программирование движка. Насколько я помню, примеры кода были больше на C, но теория разработки была подробной.
YernarShambayev
12.08.2022 09:43+2да, это чуть ли не единственная книжка на русском по программированию шахмат. Еще можно почитать книгу "Машина играет в шахматы" разработчиков Каиссы (первой шахматной чемпионки среди программ), хотя книга 1983 года.
YernarShambayev
12.08.2022 09:41+2"Не так давно я захотел написать свой шахматный движок. На удивление в
Интернете нашлось не так много хороших статей на эту тему."Значит плохо искал либо искал преимущественно на русскоязычных ресурсах. На тему компьютерных шахмат в англоязычных ресурсах МОРЕ полезной информации. Есть даже такой замечательный сайт https://www.chessprogramming.org/ с кучей теории и большим количеством ссылок.
Про perft ничего в статье не сказано, а это чуть ли не первое, что должен реализовать разработчик шахматной программы, чтобы потом не было мучительно обидно)
И классические шенноновские механизмы сейчас малоинтересны, там сказали уже почти всё и продвижения особого там нет. Сейчас state-of-the-art - это движки наподобие AlphaZero и Leela Chess Zero (глубокие нейросети + Monte Carlo Tree Search). Там сейчас совершаются открытия.
gth-other Автор
12.08.2022 12:40+6Знаю про chessprogramming, даже в статье не раз говорил про него, но последовательное изложение на родном языке с примерами кода ко всему воспринимаются куда легче, по крайней мере для меня. А perft я частично реализовывал, правда, только часть с подсчетом узлов.
Akon32
12.08.2022 10:01Неплохо. Таких статей не хватает на хабре.
Когда статья началась с описания оптимизаций, мне показалось, что шахматный движок в итоге не будет дописан. Но рейтинг 2000 говорит, что движок не просто существует, но и играет примерно на уровне других не топовых ботов.
YernarShambayev
12.08.2022 10:06-6ELO 2000 - это очень и очень мало((
Zara6502
12.08.2022 10:59+2"2000—2199 — кандидат в мастера спорта;" - какое-то "мало" у вас странное
YernarShambayev
12.08.2022 11:04-3для компьютерных шахмат - это катастрофически мало. Там уже штурмуют 3600-4000
Zara6502
13.08.2022 09:11+11) с чего вы решили что автору нужно 4000 чтобы заявить о своей работе?
2) даже в представленном рейтинге по ссылке список из 500 заканчивается на 1400 баллах, то есть автор попал в 500 - это отличный результат
3) автор не ставил целью написать что-то что "штурмует" 4000, вы вводную часть статьи прочитайте
YernarShambayev
12.08.2022 10:59Объясню. Мой шахматный движок, написанный на Delphi (!) в 2010 году (!!), играл в силу 2200. И уже тогда это был крайне посредственный результат, что я побоялся его включать в CCRL Rating List
Nedder
12.08.2022 11:04+1Это кандидат в мастера. Для простенькой программы вполне хороший результат. Первые шахматные программы до 80-х годов имели примерно 2000-2100 максимум.
unwrecker
12.08.2022 11:07+1А потом опа, и некто релизит полноценные шахматы с приличным Ai и кое-какой графикой, занимающие 1к :)
YernarShambayev
12.08.2022 11:19+8Вообще я давно мечтаю написать статью для хабра про историю развития компьютерных шахмат, начиная с Клода Шеннона и матча между программами советского института и Стэнфордского университета и заканчивая глубокими нейросетями и Leela Chess Zero. На этом пути было столько интересного и столько ярких событий, движков, идей. Сейчас мало кто помнит, что был такой шахматный компьютер, как Мефисто, про которого в свое время говорили "перворазрядник, который видит всё" (вроде так). А опубликованные исходники Fruit, после которого произошел взрыв? А Deep Blue, Rebel, Fritz, Houdini, Рыбка, какого-то странного, анонимного происхождения, но чудовищной силы движки IvanHoe, Ippolit, RobboLito. Нынешний Стокфиш, шумиха с AlphaZero. Там столько всего было.
screwer
12.08.2022 11:24+11K ZX Chess — это компьютерная шахматная программа 1982 года (с недостающими тремя правилами) для нерасширенной версии Sinclair ZX81.
...
1K ZX Chess использует только 672 байт оперативной памяти, но реализует большинство шахматных правил (не хватает рокировки, превращения пешек и взятия на проходе) и соперника, за которого играет компьютер. Это была самая маленькая реализация шахматной программы для ЭВМ, пока это место в январе 2015 года не заняла программа BootChess, хоть её искусственный интеллект и слабее, чем у 1K ZX Chess.
s_f1
12.08.2022 11:42+1Это мощно! Плюсануть не могу, так что плюсую комментом )
Он будет абсолютно детерминированным и все партии будут 1 в 1. Играть против такого противника довольно скучно, поэтому стоит добавить базу дебютов из которой будут выбираться случайные ходы.
Когда-то давно писал шахматы, совсем простые, и конечно без всякой базы. Для недетерминированности минимакс брал один из лучших найденных ходов случайным образом :)gth-other Автор
12.08.2022 16:42С простой статической оценкой такой фокус сойдет, но вот когда учитывается хотя бы такой фактор как мобильность, то позиции с одинаковой оценкой встречаются довольно редко, так что тут без базы дебютов никак).
s_f1
12.08.2022 17:05+1Брался не один из ходов с наилучшей оценкой (равная оценка действительно редка), а один из ходов, которые были в пределах «полпешки» от наилучшего (~50 в единицах из статьи). Не в пешки играем, как говорится :)
nikola-erm
12.08.2022 15:27Во введении верно отмечено, что в большинстве статей либо подробно описывается создание слабого движка, играющего чуть лучше рандома, либо движок сильный, но очень мало деталей реализации. К автору два вопроса:
Какой у Вас рейтинг на шахматном сайте заблокированном в РФ?
Не рассматривали вариант вместо альфа/бета поиска использовать Monte Carlo Tree Search?
gth-other Автор
12.08.2022 15:32Рейтинга на шахматном сайте заблокированном в РФ у меня нет, так как я им не пользуюсь (: Туда заходил чисто из-за наличия ботов с обозначенным уровнем игры. Основной аккаунт на lichess, там Эло около 1500, в шахматах обычный любитель.
Поиск по дереву Монте-Карло сперва рассматривал, но потом отказался так как алгоритм довольно сложный и редко использующийся.
YernarShambayev
13.08.2022 18:18Monte Carlo Tree Search эффективен в сочетании с глубокими нейронными сетями.
Soukhinov
12.08.2022 19:41Есть вопросы к автору по поводу этого:
Идея в том, что после завершения основного поиска не возвращать статическую оценку, а запускать новый без лимита по глубине, но с рассмотрением только взятий. Разумеется, если взятия не улучшают оценку, то надо прерывать такой просмотр, а не возвращать оценку после всех взятий.
Что такое «поиск без лимита по глубине»? Что значит «рассмотрение только взятий»? Разве можно что-то делать после завершения основного поиска, если он завершается по допустимому времени?
gth-other Автор
12.08.2022 20:26Рассмотрим этот псевдокод, он был в статье:
int alphaBetaMax( int alpha, int beta, int depthleft ) { if ( depthleft == 0 ) return evaluate(); for ( all moves) { score = alphaBetaMin( alpha, beta, depthleft - 1 ); if( score >= beta ) return beta; // fail hard beta-cutoff if( score > alpha ) alpha = score; // alpha acts like max in MiniMax } return alpha; } int alphaBetaMin( int alpha, int beta, int depthleft ) { if ( depthleft == 0 ) return evaluate(); for ( all moves) { score = alphaBetaMax( alpha, beta, depthleft - 1 ); if( score <= alpha ) return alpha; // fail hard alpha-cutoff if( score < beta ) beta = score; // beta acts like min in MiniMax } return beta; }В нем видно, что после того как заканчивается глубина происходит возврат статической оценки текущей позиции.
Идея в том, чтобы возвращать не статическую оценку, а результат выполнения другого поиска, по большей части похожего на оригинальный альфа-бета алгоритм, но без лимита по глубине и с рассмотрением только взятий. У меня в итоговом коде класса ИИ этот момент реализован.
MagicWolf
13.08.2022 11:16Не знаю, как сейчас, а раньше это называлось "форсированный вариант".
YernarShambayev
13.08.2022 18:14В шахматном программировании это называется Quiescence Search. Без этого приема сработает эффект горизонта, и движок будет безумно играть.
Daddy_Cool
13.08.2022 01:00Очень впечатлен статьёй!
Один мой друг как-то написал шахматы и я даже использовал их для игры через инет со знакомой (как в книге/фильме "Если наступит завтра" ))). В критический момент в программе нашлась ошибка... неправильно делалась длинная рокировка - и .... мне пришлось играть самому с середины партии.
Интересно - думается должна быть библиотека где учитываются все правила/интерфейс и самому надо придумывать только логику. Или я много хочу?Интересно, сложно ли написать самообучающийся нейросетевой движок?
YernarShambayev
13.08.2022 18:12"Интересно, сложно ли написать самообучающийся нейросетевой движок?"
Пожалуйста, вот исходники: https://github.com/LeelaChessZero/lc0 , можно изучать. Но тут проблема в другом. Для создания сильного движка уровня гроссмейстера и выше нужны либо вычислительные мощности, как у Гугла, либо создание распределенной сети, как поступили разработчики Leela Chess Zero.
ebt
13.08.2022 02:04В чём причина того, что репозиторий с кодом в режиме read-only? Вы же фактически отказываетесь от любых обновлений и багфиксов. И, кстати, я бы убедительно рекомендовал перевести документацию на английский, вплоть до того, что даже сам (теоретически) был бы готов создать PR, не будь эта возможность заблокирована.
Rom77
13.08.2022 08:29+1Не программист, но статью просмотрел с интересом. Как я понимаю, программа сейчас находится в положении state of art по состоянию примерно на середину 1970-х. Значит можно начинать улучшать:)
Для сортировки тихих ходов стандартными методами являются "киллеры" и сортировка по истории.
Основным источником силы подобных программ является отсечение 99% заведомо не лучших ходов. Для этого существует множество эффективных методов. В первую очередь нужно пробовать "нулевой ход", "LMR", различные отсечения на предельных глубинах (например Futility, Razoring).
Но лучше, наверное, посмотреть как реализованы эти методы в коде Стокфиша. По сути, бОльшая часть силы этой программы проистекает из небольшого участка кода (шаги с 7 по 18):
https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp#L776-L1230
YernarShambayev
13.08.2022 18:17Разработчики Стокфиша - гении! В движке реализованы все лучшие эвристики.
fregate
14.08.2022 13:31+1В-пятых, счетчик ходов. Это просто float переменная, добавляющая по 0.5 за каждый ход. Если переменная круглая, то ход белых. Если у нее есть дробная часть, то ход черных.
а вот это зачем? почему не простой int (uint, фиксированный 32, 64 - что хочется), и добавляем +1 (ну как обычно) и проверяем последний бит (четность). Быстро, безопасно в плане float и дробной части... понятно, наглядно... в общем, одни плюсы.
gth-other Автор
14.08.2022 14:16Разница в производительности между int и float одной длины находится на уровне погрешности, по крайней мере, когда использование ограничивается одной-двумя примитивными операциями за ход.
Про безопасность не совсем понял. Вы про погрешность float типов? Если для проверки стороны использовать что-то вроде
move_ctr - std::floor(move_ctr) == 0то, естественно, это будет не безопасно, но если что-то такое (это я и использую)
move_ctr - std::floor(move_ctr) > 1e-7то вряд-ли это когда-то подведет.
А читаемость и наглядность вещи, во многом, субъективные. Мне float счетчик кажется более понятным.
fregate
14.08.2022 15:59У меня ощущение, что
move_ctr - std::floor(move_ctr) > 1e-7
Медленнее, чем
(count & 0x1) == 0В любом случае пара операций на ход не критична.
Спасибо за статью, очень познавательно
mapron
Интересно, с удовольствием прочитал)
Первые несколько абзацев статьи были мысли «шо, опять?», но, к моменту про constexpr проверки позиций настрой сменился на «неплохо, годно».
Я не поклонник шахмат, не знаю, найдут ли полезное в статье именно любители шахмат, но как материал для раздумий над реализацией позиционных игр сгодится (у меня в моем проекте была часть с тактической битвой, что-то похожее применял).
napa3um
Это не совсем для любителей шахмат, а, скорее, для любителей компьютерных шахмат, в статье перечислены прям все основные вехи "классического" двигателестроения, всё аккуратно и всесторонне. Именно такие статьи и хочется видеть на Хабре :).