Хеширование Зобриста
Способ хешировать позиции на доске, применяя XOR к случайным числам — по одному на фигуру и поле, — и обновлять хеш двумя XOR на ход.
При запуске для каждой комбинации типа фигуры и поля генерируется 64-битное случайное число, плюс несколько для очерёдности хода и особых прав вроде рокировки. Хеш позиции — это XOR чисел всех фигур на доске. Поскольку XOR обратим сам собой, ход фигуры означает «вычесть» старое поле и «добавить» новое; заново хешировать всю доску не нужно.
Альберт Зобрист опубликовал метод в 1970 году, и он по сей день служит ключом к транспозиционной таблице практически любого шахматного движка и движка го. Коллизии случаются, но при 64 битах настолько редко, что движки обычно просто проверяют легальность сохранённого хода и идут дальше.