Сгенерировать уникальный идентификатор для шахматной доски

Широко используемой контрольной суммой для позиций на доске является подпись Zobrist.

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

Вам нужен набор случайно сгенерированных битовых строк:

• по одному на каждую фигуру на каждом квадрате;
• один для указания стороны движения;
• четыре за право рокировки;
• восемь для файла действительного квадрата на проходе (если есть).

Если вы хотите получить хеш-код Zobrist определенной позиции, вам необходимо xor все случайные числа, связанные с данной функцией (подробности: здесь и Правильная реализация хеширования Zobrist).

Например, исходное положение:

[Hash for White Rook on a1] xor [White Knight on b1] xor ... ( all pieces )
... xor [White castling long] xor ... ( all castling rights )

XOR позволяет быстрое инкрементное обновление хеш-ключа во время выполнения/отмены ходов.

Обычно 64-битные используются в качестве стандартного размера в современных шахматных программах (см. Шахматная программа).

Вы можете столкнуться с коллизией в 32-битном хеше, если вычислите 2³² == 2¹⁶. С 64-битным хэшем вы можете ожидать коллизии примерно через 2³² или 4 миллиарда позиций (парадокс дня рождения).

Если вам нужна контрольная сумма, обычное решение — Хеширование Zobrist.

Если вы ищете настоящий уникальный идентификатор, обычное удобочитаемое решение — Нотация Форсайта.

Для нечитаемого человеком уникального идентификатора вы можете сохранить тип/цвет фигуры на каждом квадрате, используя четыре бита. Добавьте еще 3 бита для квадрата на проходе, 4 бита, для которых все еще разрешены рокировки, и один бит для того, чья очередь, и вы получите ровно 33 байта для каждой установки доски.

Вы можете использовать контрольную сумму, такую ​​​​как md5, sha, просто передайте ячейки шахматной доски в виде текста, например:

TKBQKBHT
........
........
........
tkbqkbht

И получить контрольную сумму для сгенерированного текста.

Контрольная сумма между одной и другой платой будет отличаться без какого-либо связанного значения, в этот момент лучше всего создать уникальную строку (или массив битов):

TKBQKBHT........................tkbqkbht

Потому что он тоже будет уникальным и его легко сравнить с другими.

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

Один из методов заключается в использовании матрицы членства 64x12 square-by-piecetype. Вы можете сохранить это как битовый вектор, а затем сравнить векторы для проверки. например первые 64 адреса в векторе могут показывать, в каких местах на доске находятся пешки. Следующие 64 показывают локации, в которых есть рыцари. Вы можете позволить первым 6 секциям показывать принадлежность белых фигур, а последним 6 показывать принадлежность черных фигур.

Псевдокод бинарной матрицы принадлежности:

bool[] memberships = zeros(64*12);
move(pawn,a3,a2);

def move(piece,location,oldlocation):
    memberships(pawn,location) = 1;
    memberships(pawn,oldlocation) = 0;

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

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

Псевдокод небинарной матрицы принадлежности:

half[] memberships = zeros(64);
memberships[8] = 1;        // white pawn at location a2
memberships[0] = 2;        // white rook at location a1
...
memberships[63] = 11;      // black knight at location g8
memberships[64] = 12;      // black rook at location h8

Преимущество небинарного вектора в том, что у вас не так много свободы, чтобы случайно присвоить несколько частей одному местоположению. Недостатком является то, что теперь для хранения каждого состояния требуется больше места. Более крупные представления будут медленнее выполнять сравнения на равенство. (в моем примере предположим, что каждая позиция вектора хранит 16-битное полуслово, мы получаем 64 * 16 = 1014 бит для хранения одного состояния по сравнению с 768 битами для двоичного вектора)

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

enumerate piece {
    empty = 0;
    white_pawn = 1;
    white_rook = 2;
    ...
    black_knight = 11;
    black_rook = 12;
}
enumerate location {
    a1 = 0;
    ...
}

А проверка на равенство — это просто сравнение двух векторов вместе.