Hashing de Zobrist: el algoritmo de 1970 que sigue vivo en el ajedrez

Un motor de ajedrez que analiza miles de posiciones por segundo no puede detenerse a comparar el tablero casilla por casilla en cada jugada. En su lugar mantiene un solo número de 64 bits que se actualiza con una operación XOR: el hashing de Zobrist. Ese número funciona como huella de la posición y permite reconocer al instante si el motor ya analizó ese mismo tablero antes, sin volver a mirarlo entero.

TL;DR

• El hashing de Zobrist asigna un número aleatorio de 64 bits a cada combinación de pieza y casilla, y los combina con XOR.
• Una sola operación XOR por jugada actualiza el hash completo, sin recorrer las 64 casillas del tablero de nuevo.
• La clave resultante indexa la tabla de transposición, la memoria que evita reanalizar la misma posición dos veces.
• XOR aplicado dos veces se cancela a sí mismo, por eso retirar y colocar una pieza es una operación reversible.
• Go, shogi y otros juegos de mesa usan el mismo truco para detectar repeticiones de posición sin guardar el historial completo.

¿Qué es el hashing de Zobrist?

El hashing de Zobrist es un método para resumir el estado completo de un tablero de juego en un único número de 64 bits, generado al combinar con XOR una clave aleatoria distinta por cada pieza y casilla ocupada, de forma que cualquier cambio en el tablero se refleja con una sola operación.

La idea aparece en 1970, cuando Albert Zobrist la describió en su tesis doctoral en la Universidad de Wisconsin, aplicada a un programa que jugaba Go, según documenta la entrada de Wikipedia sobre la técnica. Décadas después se volvió un estándar en motores de ajedrez, damas, shogi y cualquier juego de tablero donde haga falta reconocer posiciones repetidas rápido.

La clave del esquema es elegir, por adelantado, un número aleatorio distinto para cada combinación posible de pieza en una casilla, por ejemplo alfil blanco en c4. Para construir el hash de una posición concreta alcanza con aplicar XOR a los números que corresponden a las piezas presentes en ese momento.

Albert Zobrist creó la técnica en 1970 para un programa de Go.

Por qué importa

Los motores de ajedrez explotan un fenómeno llamado transposición: dos secuencias de jugadas distintas pueden terminar en el mismo tablero. Si el motor ya evaluó esa posición por otro camino, repetir el trabajo es tiempo perdido. La solución es guardar cada evaluación en una tabla de transposición, indexada por un identificador único de la posición.

Ahí es donde entra el hashing de Zobrist. Sin él, identificar una posición exigiría serializar las 64 casillas y compararlas una a una contra todo lo que hay guardado, algo demasiado lento para un algoritmo que visita millones de nodos. Con una clave de 64 bits, la comparación se reduce a comparar dos enteros.

El mismo problema aparece en Go, donde la regla de superko prohíbe repetir una posición exacta en toda la partida. Comparar el tablero completo contra cada posición anterior sería prohibitivo, así que los programas de Go también usan una firma Zobrist para esa verificación.

Cómo funciona la clave de Zobrist

Antes de jugar una sola partida, el motor genera una tabla de números aleatorios de 64 bits: uno por cada combinación de tipo de pieza (peón, caballo, alfil, torre, dama, rey, de cada color) y casilla del tablero. En ajedrez eso son 12 tipos de pieza por 64 casillas, además de una clave extra para el turno y claves para los derechos de enroque y la columna de captura al paso. La wiki de programación de ajedrez documenta el esquema completo: 64 por 12 claves de pieza, más una de turno, más cuatro de enroque, más ocho de columna de paso, un total de 781 números aleatorios fijos durante toda la partida.

Calcular el hash de una posición cualquiera es tan simple como aplicar XOR a las claves de todas las piezas presentes. Lo interesante no es ese cálculo inicial, sino lo que pasa después de cada jugada: en vez de recalcular todo, el motor retira del hash la clave de la pieza en su casilla de origen, agrega la clave de esa pieza en la casilla de destino, y alterna la clave de turno. Tres operaciones XOR, sin importar cuántas piezas haya en el tablero.

flowchart TD
    A["Posicion actual con hash H"] --> B["Mover una pieza de origen a destino"]
    B --> C["XOR con la clave de la pieza en la casilla de origen"]
    C --> D["XOR con la clave de la pieza en la casilla de destino"]
    D --> E["XOR con la clave de cambio de turno"]
    E --> F["Nuevo hash, calculado en tiempo constante"]

Esa propiedad depende de que XOR sea su propio inverso: aplicar la misma clave dos veces la cancela. Por eso deshacer un movimiento es trivial, se repiten las mismas tres operaciones, y por eso no hace falta guardar el tablero anterior para calcular el siguiente hash.

💡 Tip: la calidad del generador de números aleatorios importa. Un generador con patrones predecibles produce más colisiones de las que la teoría predice; conviene uno de 64 bits con buena distribución, como Mersenne Twister o xorshift64.

Durante la búsqueda, cada vez que el motor llega a una posición consulta su hash en la tabla de transposición antes de evaluarla desde cero.

sequenceDiagram
    participant M as Motor de busqueda
    participant T as Tabla de transposicion
    M->>T: busca el hash de la posicion actual
    alt hash encontrado
    T-->>M: devuelve la evaluacion guardada
    else hash no encontrado
    T-->>M: no hay entrada previa
    M->>T: guarda la nueva evaluacion con ese hash
    end

Ejemplos prácticos

El ejemplo más simple posible usa claves diminutas de 4 bits en lugar de 64, solo para poder verificar el resultado a mano. Imaginemos tres claves fijas: una para peón blanco en e2, otra para peón blanco en e4 y otra para el turno.

KEY_PEON_E2 = 0b1011  # 11
KEY_PEON_E4 = 0b0110  # 6
KEY_TURNO   = 0b1001  # 9

hash_inicial = KEY_PEON_E2 ^ KEY_TURNO
print(bin(hash_inicial))

Esto imprime 0b10: el XOR bit a bit de 1011 y 1001 da 0010. Ahora simulemos que el peón avanza de e2 a e4, lo que retira la clave de e2, agrega la de e4 y alterna el turno:

nuevo_hash = hash_inicial ^ KEY_PEON_E2 ^ KEY_PEON_E4 ^ KEY_TURNO
print(bin(nuevo_hash))

La salida es 0b110 (6), que es exactamente KEY_PEON_E4: la clave de e2 y la clave de turno se cancelaron entre sí, cada una aparece dos veces, y quedó solo la clave de la nueva casilla. Es la misma mecánica que usa un motor real, solo que con enteros de 64 bits en lugar de 4.

El siguiente paso es comprobar que el hash incremental coincide siempre con el de recalcular todo desde cero, algo que cualquier implementación real debería verificar al menos una vez durante las pruebas:

import random
random.seed(7)

CASILLAS = 64
TIPOS_DE_PIEZA = 12
tabla_zobrist = [[random.getrandbits(64) for _ in range(TIPOS_DE_PIEZA)] for _ in range(CASILLAS)]
clave_turno = random.getrandbits(64)

def hash_desde_cero(piezas_en_tablero, turno_blanco):
    h = 0
    for casilla, tipo_pieza in piezas_en_tablero:
        h ^= tabla_zobrist[casilla][tipo_pieza]
    if turno_blanco:
        h ^= clave_turno
    return h

def mover(hash_actual, tipo_pieza, origen, destino):
    h = hash_actual ^ tabla_zobrist[origen][tipo_pieza] ^ tabla_zobrist[destino][tipo_pieza]
    return h ^ clave_turno

piezas = [(12, 0)]
hash_a = hash_desde_cero(piezas, turno_blanco=True)
hash_b = mover(hash_a, tipo_pieza=0, origen=12, destino=28)
piezas_despues = [(28, 0)]
hash_c = hash_desde_cero(piezas_despues, turno_blanco=False)

print('Coinciden:', hash_b == hash_c)

La salida es Coinciden: True, y lo es sin importar qué números aleatorios haya generado random.seed(7): la igualdad se cumple porque XOR es asociativo y conmutativo, no porque los números coincidan por casualidad. Es la verificación mínima que cualquier implementación de hashing de Zobrist debería pasar antes de confiar en ella.

Cómo empezar

Para probar el hash incremental de tablero del ejemplo anterior no hace falta instalar nada: alcanza con tener Python 3.8 o superior, porque random.getrandbits es parte de la librería estándar.

• Guardá el código del ejemplo anterior en un archivo llamado zobrist_demo.py.
• Ejecutalo con python3 zobrist_demo.py en Linux o macOS (en Windows, python zobrist_demo.py).
• Confirmá que la última línea impresa sea Coinciden: True. Si modificás la función mover y aparece False, el error suele estar en olvidar alternar la clave de turno o en usar la clave de una pieza equivocada.

Para extender el ejemplo a un tablero completo de 8x8, el paso natural es representar las 32 piezas iniciales como una lista de tuplas de casilla, tipo de pieza y color, y generar el hash inicial recorriendo esa lista una sola vez al arrancar la partida. De ahí en adelante, cada jugada se actualiza solo con las tres operaciones XOR descritas antes.

Casos de uso reales

• Motores de ajedrez: los motores UCI usan una firma de 64 bits como índice de su tabla de transposición, lo que les permite reconocer transposiciones durante la búsqueda en lugar de reevaluar la misma posición por caminos distintos.
• Programas de Go: la regla de superko obliga a verificar que ninguna posición se repita en toda la partida; sin un hash incremental, esa verificación sería demasiado costosa para una búsqueda en árbol.
• Solvers de rompecabezas: algoritmos que exploran el espacio de estados de juegos como el 15-puzzle o Sokoban usan el mismo truco para detectar si ya visitaron un estado, evitando ciclos infinitos en la búsqueda.
• Shogi y damas: cualquier juego de tablero con reglas de repetición de posición, como el sennichite del shogi, puede apoyarse en la misma técnica para detectar tablas por repetición.

Errores comunes y buenas prácticas

El error más frecuente es olvidar incluir la clave del turno en el hash. Dos posiciones con las mismas piezas en las mismas casillas pero distinto jugador por mover son posiciones distintas, una puede ser ganadora para blancas y la otra para negras, y si el hash no distingue el turno, el motor las trata como si fueran la misma.

El segundo error es ignorar el enroque y la captura al paso. Dos tableros pueden verse idénticos pero tener distintos derechos de enroque disponibles, lo que cambia por completo las jugadas legales. Un hash que no incluya esas claves adicionales genera falsos positivos de ya vi esta posición.

La buena práctica más importante es nunca confiar ciegamente en la igualdad de hashes para decisiones irreversibles sin alguna verificación adicional. Las tablas de transposición de los motores reales suelen guardar junto a la entrada la profundidad de búsqueda con la que se generó, y algunos además guardan una verificación extra para reducir el impacto de una colisión accidental.

📌 Nota: una colisión en la tabla de transposición no corrompe la partida: en el peor caso el motor usa una evaluación levemente equivocada para una jugada y la corrige en la siguiente iteración de profundización. No es un fallo catastrófico, pero sí una fuente de bugs difíciles de reproducir si no se tiene en cuenta.

Go, shogi y el 15-puzzle resuelven el mismo problema con la misma idea.

Comparativa con alternativas

El hash incremental de tablero no es la única forma de identificar una posición, pero sí la que mejor equilibra velocidad y simplicidad para búsquedas en árbol de juego:

OpciónCuándo usarlaVentajaLimitación

Hashing de ZobristMotores de juegos con movimientos incrementalesActualización en tiempo constante con XORRequiere precomputar una tabla de claves aleatorias; no es criptográfico
Comparación directa del tableroPocas posiciones, prototipos o pruebasSimple, sin estructuras extraCompara todas las casillas en cada consulta, lento a gran escala
Hash criptográfico (SHA-256)Verificar integridad frente a manipulación adversariaColisiones prácticamente imposiblesHay que recalcular el hash completo en cada cambio, mucho más lento que un XOR
Rolling hash polinómico (Rabin-Karp)Buscar subcadenas en texto o streams de bytesTambién incremental y de tiempo constante por desplazamientoPensado para secuencias lineales, no para conjuntos de piezas en un tablero

Profundizando: colisiones y hashing sin bloqueos

Con claves de 64 bits, la cantidad de posiciones distintas que hace falta generar antes de que una colisión por azar sea probable crece aproximadamente con la raíz cuadrada del espacio total de claves, siguiendo la misma lógica que la paradoja del cumpleaños. En la práctica, ningún motor de ajedrez analiza suficientes posiciones en una partida como para que eso sea un problema real; por eso la mayoría usa solo la clave de 64 bits sin verificación criptográfica adicional.

Los motores que buscan en paralelo con varios hilos enfrentan otro problema: dos hilos pueden escribir en la misma entrada de la tabla de transposición al mismo tiempo y corromperla a medias. La comunidad de programación de ajedrez documenta una técnica conocida como hashing sin bloqueos. En vez de proteger la escritura con un lock, cada entrada guarda el hash combinado con XOR contra los datos de la evaluación, de forma que al leerla se puede detectar si una escritura a medias la dejó inconsistente, sin pagar el costo de sincronizar hilos en cada acceso.

La misma idea de Zobrist se generaliza fácilmente: cualquier conjunto de elementos independientes que pueden aparecer o no, piezas en casillas, cartas en una mano, celdas activas en un autómata celular, puede resumirse con una clave aleatoria por elemento y XOR para combinarlas. Lo que hace especial al caso del ajedrez es que fue, históricamente, el que popularizó la técnica fuera de los círculos de investigación en Go.

📖 Resumen en Telegram: Ver resumen

Tu próximo paso: copiá el script de verificación de este artículo, cambiá CASILLAS y TIPOS_DE_PIEZA para modelar un juego distinto, como el 15-puzzle con 16 casillas y 15 tipos de ficha, y comprobá que la igualdad entre hash incremental y hash desde cero sigue cumpliéndose.

Preguntas frecuentes

¿Qué diferencia a la clave de Zobrist de un hash criptográfico como SHA-256?

La clave de Zobrist no busca resistir ataques deliberados, solo distinguir posiciones distintas de forma rápida y actualizable con XOR. SHA-256 es mucho más lento de recalcular y no ofrece la propiedad incremental que necesita una búsqueda en árbol de juego.

¿Por qué un motor de ajedrez necesita una tabla de transposición?

Porque jugadas en distinto orden pueden llegar al mismo tablero. Sin una tabla indexada por hash, el motor repetiría el análisis de esa posición cada vez que la alcanza por un camino distinto, multiplicando el trabajo.

¿El hash incremental de tablero puede fallar y dar falsos positivos?

En teoría sí, por una colisión entre dos posiciones distintas con el mismo hash de 64 bits, pero la probabilidad es extremadamente baja y casi ningún motor la trata como un problema práctico.

¿Se puede usar la firma Zobrist en juegos distintos al ajedrez?

Sí. Los programas de Go la usan para la regla de superko, y cualquier algoritmo de búsqueda de estados, como un solver de Sokoban, puede aplicarla para detectar estados ya visitados.

¿Cuántas claves Zobrist hace falta precomputar para un ajedrez completo?

El esquema documentado por la wiki de programación de ajedrez usa 781 claves: 64 casillas por 12 tipos de pieza, más una de turno, cuatro de enroque y ocho de columna de captura al paso.

¿Qué pasa si dos hilos de un motor acceden a la tabla de transposición al mismo tiempo?

Pueden corromper una entrada a medias. La técnica de hashing sin bloqueos evita ese problema sin usar locks, combinando con XOR el hash y los datos guardados para detectar inconsistencias al leer.

Referencias

• Chess Programming Wiki: Zobrist Hashing: especificación del esquema de claves y su uso en motores de ajedrez.
• Wikipedia: Zobrist hashing: origen de la técnica en la tesis doctoral de Albert Zobrist de 1970.
• Chess Programming Wiki: Transposition Table: cómo los motores indexan evaluaciones guardadas con la clave de Zobrist.
• Chess Programming Wiki: Shared Hash Table: la técnica de hashing sin bloqueos para tablas de transposición compartidas entre hilos.

📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.