Hashing de Zobrist

El hashing de Zobrist asigna números seudoaleatorios a los elementos que pueden formar una posición. Normalmente existe un número para cada combinación de tipo de pieza, color y casilla, además de números para el turno, los derechos de enroque, que indican si rey y torre todavía pueden realizar ese movimiento especial, y el estado relevante de captura al paso, una captura especial de peón. Seudoaleatorio significa que los valores parecen aleatorios, pero se generan de forma reproducible.

La clave de la posición se obtiene combinando los valores activos con XOR, u OR exclusivo, una operación binaria que funciona como un interruptor: aplicar dos veces el mismo valor deshace su efecto. Cuando una pieza se mueve, el programa puede quitar de la clave su presencia en la casilla anterior y agregarla en la nueva, sin reconstruir todo desde cero. Capturas, promociones y cambios de turno se actualizan del mismo modo.

Esta huella permite reconocer rápidamente que una posición ya apareció. Un motor de ajedrez, un programa que analiza posiciones, puede reutilizar análisis almacenado cuando diferentes secuencias llegan al mismo estado, detectar repeticiones y organizar cachés, que son almacenamientos rápidos de resultados anteriores. La comparación correcta exige incluir no solo la ubicación de las piezas, sino también la información que cambia las jugadas legales o las reglas aplicables.

Una clave de Zobrist no es una descripción única garantizada. Dos posiciones diferentes pueden producir el mismo número, fenómeno llamado colisión. Con claves suficientemente grandes el riesgo es bajo, pero los programas deben diseñar su almacenamiento y verificación teniendo presente que no es imposible. En pruebas como perft, una clave incremental también puede ayudar a descubrir errores si no vuelve al valor original después de hacer y deshacer una jugada.