Шахматы на C++

Введение

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

Битборды или битовые доски

Существует довольно удобная система представления доски, называемая битбордами или битовыми досками, если по-русски. Идея битбордов строится на замечательном совпадении: шахматная доска содержит 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 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 calc_rows() {
        std::array 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 Rows = BitboardRows::calc_rows();


    static consteval std::array calc_inversion_rows() {
        std::array inversion_rows{};

        for (uint8_t i = 0; i < 8; i = i + 1) inversion_rows[i] = ~Rows[i];

        return inversion_rows;
    }


    static constexpr std::array InversionRows = BitboardRows::calc_inversion_rows();
}


namespace BitboardColumns {
    static consteval std::array calc_columns() {
        std::array 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 Columns = BitboardColumns::calc_columns();


    static consteval std::array calc_inversion_columns() {
        std::array inversion_columns{};

        for (uint8_t i = 0; i < 8; i = i + 1) inversion_columns[i] = ~Columns[i];

        return inversion_columns;
    }


    static constexpr std::array InversionColumns = BitboardColumns::calc_inversion_columns();
}

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

Хранение фигур

Из чего складывается позиция в шахматах? Из прав на рокировку, сложных правил про троекратное повторение позиции, счетчика 50 ходов и так далее, но база — это фигуры и пешки. Сейчас нужно написать структуру, которая будет хранить все фигуры и пешки. Но какие именно типы будет хранить структура? Разумеется, 12 битбордов о которых был разговор в предыдущем разделе, но этого мало. Так же стоит хранить битборды всех белых и всех черных фигур, всех фигур вообще, и битборды, обратные этим битбордам. Такие битборды могут быть составлены на основе базовых 12 битбордов и будут обновляться после обновления базовых битбордов. Но зачем они нам нужны? Например, при генерации ходов. Когда мы будем генерируем ходы, например, коня, нам нужно будет проверять содержится ли в клетке фигура того же цвета, что и конь, и если содержится — то такой ход не может быть выполнен.

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

std::array, 2> _piece_bitboards{};
std::array _side_bitboards{};
std::array _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 
#include 


#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, 2>, 64> calc_constants() {
        std::array, 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, 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 
#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 _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 


#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 calc_masks() {
        std::array 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 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 calc_masks() {
        std::array 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 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, 64> calc_masks() {
        std::array, 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, 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];
}

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

    
            

© Habrahabr.ru