El hash Zobrist (también conocido como claves Zobrist o firmas Zobrist [1] ) es una construcción de función hash utilizada en programas informáticos que juegan juegos de mesa abstractos , como el ajedrez y el Go , para implementar tablas de transposición , un tipo especial de tabla hash que es indexado por una posición en el tablero y utilizado para evitar analizar la misma posición más de una vez. El hashing Zobrist lleva el nombre de su inventor, Albert Lindsey Zobrist . [2] También se ha aplicado como método para reconocer configuraciones de aleaciones sustitutivas en simulaciones de materiales cristalinos. [3] El hash de Zobrist es el primer caso conocido de la técnica subyacente generalmente útil llamada hash de tabulación .
El hash de Zobrist comienza generando aleatoriamente cadenas de bits para cada elemento posible de un juego de mesa, es decir, para cada combinación de una pieza y una posición (en el juego de ajedrez, son 12 piezas × 64 posiciones del tablero, o 18 × 64 si son reyes y torres). todavía pueden enrocarse, [ dudoso ] y los peones que pueden capturar al paso , se tratan por separado para ambos colores). Ahora cualquier configuración de placa se puede dividir en componentes independientes de pieza/posición, que se asignan a las cadenas de bits aleatorias generadas anteriormente. El hash final de Zobrist se calcula combinando esas cadenas de bits utilizando XOR bit a bit . Pseudocódigo de ejemplo para el juego de ajedrez: [ cita necesaria ]
índices constantes peón_blanco := 1 torre_blanca := 2 # etc. rey_negro := 12función init_zobrist(): # llenar una tabla de números aleatorios/cadenas de bits tabla := una matriz 2-d de tamaño 64×12 para i del 1 al 64: # bucle sobre el tablero, representado como una matriz lineal para j del 1 al 12: # bucle sobre las piezas tabla[i][j] := cadena_bit_aleatoria() table.black_to_move = cadena_bits_aleatoria()hash de función (tablero): h := 0 si is_black_turn(tablero): h := h XOR tabla.black_to_move para i de 1 a 64: # recorra las posiciones del tablero si el tablero[i] ≠ está vacío: j := la pieza en el tablero [i], como se enumera en los índices constantes, arriba h := h Tabla XOR[i][j] volver h
Si las cadenas de bits son lo suficientemente largas, es casi seguro que diferentes posiciones de la placa obtendrán valores diferentes; sin embargo, las cadenas de bits más largas requieren proporcionalmente más recursos informáticos para manipularlas. La longitud de cadena de bits (clave) más utilizada es de 64 bits. [1] Muchos motores de juegos almacenan solo los valores hash en la tabla de transposición, omitiendo por completo la información de posición para reducir el uso de memoria y asumiendo que no se producirán colisiones hash , o que no influirán en gran medida en los resultados de la tabla si ocurren.
El hash de Zobrist es el primer caso conocido de hash de tabulación . El resultado es una familia de hash independiente de 3 componentes . En particular, es fuertemente universal .
Por ejemplo, en el ajedrez , en cualquier momento, cada una de las 64 casillas puede estar vacía o contener una de las 6 piezas del juego, que son blancas o negras. Además, puede ser el turno de jugar de las negras o de las blancas. Por lo tanto, es necesario generar 6 x 2 x 64 + 1 = 769 cadenas de bits aleatorias. Dada una posición, se obtiene su hash Zobrist averiguando qué piezas están en qué cuadrados y combinando las cadenas de bits relevantes. Si la posición es negra para mover, la cadena de bits de negro para mover también se incluye en el hash de Zobrist. [1]
En lugar de calcular el hash para toda la placa cada vez, como lo hace el pseudocódigo anterior, el valor hash de una placa se puede actualizar incrementalmente simplemente aplicando XOR en las cadenas de bits para las posiciones que han cambiado, y aplicando XOR en las cadenas de bits para las posiciones que han cambiado. nuevas posiciones. [1] Por ejemplo, si un peón en una casilla del tablero de ajedrez es reemplazado por una torre de otra casilla, la posición resultante se produciría aplicando XOR al hash existente con las cadenas de bits para:
'peón en esta casilla' (XORando el peón en esta casilla)'torre en esta casilla' (XOR en la torre en esta casilla)'torre en la casilla fuente' (XORando la torre en la casilla fuente)
Esto hace que el hash de Zobrist sea muy eficiente para atravesar un árbol de juego .
En Computer Go , esta técnica también se utiliza para la detección de superko .
De manera más genérica, el hash Zobrist se puede aplicar sobre conjuntos finitos de elementos (en el ejemplo del ajedrez, estos elementos son tuplas ), siempre que se pueda asignar una cadena de bits aleatoria a cada elemento posible. Esto se puede hacer con un generador de números aleatorios para espacios de elementos más pequeños o con una función hash para espacios más grandes. Este método se ha utilizado para reconocer configuraciones de aleaciones sustitutivas durante simulaciones de Monte Carlo para evitar desperdiciar esfuerzo computacional en estados que ya han sido calculados. [3]
