Hashing de Zobrist

O hashing de Zobrist atribui números pseudoaleatórios aos elementos que podem formar uma posição. Normalmente há um número para cada combinação de tipo de peça, cor e casa, além de números para o lado a jogar, os direitos de roque, que registram se o rei e a torre ainda podem realizar esse movimento especial, e o estado relevante de en passant para a captura especial de peão. Pseudoaleatório significa que os valores parecem aleatórios, mas são gerados de forma reproduzível.

A chave da posição é formada pela combinação dos valores ativos com XOR, abreviação de exclusive OR, ou OU exclusivo, uma operação binária que funciona como um interruptor: aplicar duas vezes o mesmo valor desfaz seu efeito. Quando uma peça se move, o programa pode remover o valor da casa anterior e acrescentar o valor da nova casa sem reconstruir a chave do zero. Capturas, promoções e mudanças do lado a jogar podem ser atualizadas da mesma forma.

Essa impressão digital permite que um motor de xadrez, um programa que analisa posições, reconheça rapidamente que uma posição já apareceu. Ele pode reutilizar análises armazenadas quando diferentes sequências de lances chegam ao mesmo estado, detectar repetições e organizar memórias cache, que são armazenamentos rápidos de resultados anteriores. Uma comparação correta exige mais do que a disposição das peças, pois o lado a jogar e os direitos especiais podem alterar as possibilidades legais.

Uma chave de Zobrist não tem garantia de ser única. Duas posições diferentes podem produzir o mesmo número, evento chamado de colisão. Chaves grandes tornam isso improvável, mas o armazenamento e a verificação ainda precisam considerar essa possibilidade. Em testes como perft, uma chave incremental também pode revelar erros de atualização quando não retorna ao valor original depois que um lance é feito e desfeito.