Хеширование Зобриста

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

Ключ позиции образуется объединением активных значений с помощью XOR, сокращения от exclusive OR, то есть исключающего ИЛИ, бинарной операции, работающей как переключатель: повторное применение того же значения отменяет его эффект. Когда фигура ходит, программа может удалить из ключа значение её прежнего поля и добавить значение нового, не перестраивая ключ с нуля. Таким же способом обновляются взятия, превращения и смена стороны хода.

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

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