El hash Zobrist (también conocido como claves Zobrist o firmas Zobrist [1] ) es una construcción de función hash utilizada en programas de computadora que juegan juegos de mesa abstractos , como ajedrez y Go , para implementar tablas de transposición , un tipo especial de tabla hash que es indexado por una posición de la junta y utilizado para evitar analizar la misma posición más de una vez. El hash de 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]
Cálculo del valor hash
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 16 x 64 si un rey puede todavía castillo y un peón 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 de Zobrist final se calcula combinando esas cadenas de bits utilizando XOR bit a bit . Ejemplo de pseudocódigo para el juego de ajedrez: [ cita requerida ]
índices constantes peón_blanco: = 1 torre_blanco: = 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 de 1 a 64: # bucle sobre el tablero, representado como una matriz lineal para j de 1 a 12: # bucle sobre las piezas tabla [i] [j]: = cadena_bits_aleatoria ()función hash (tablero): h: = 0 para i de 1 a 64: # bucle sobre las posiciones del tablero si el tablero [i] ≠ está vacío: j: = la pieza en el tablero [i], como se indica en los índices constantes, arriba h: = h tabla XOR [i] [j] volver h
Uso del valor hash
Si las cadenas de bits son lo suficientemente largas, es casi seguro que las diferentes posiciones de la placa generarán valores diferentes; sin embargo, las cadenas de bits más largas requieren proporcionalmente más recursos informáticos para su manipulación. La longitud de la cadena de bits (clave) más utilizada es de 64 bits. Muchos motores de juegos almacenan solo los valores hash en la tabla de transposición, omitiendo la información de posición por completo para reducir el uso de la 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 se producen.
El hash de Zobrist es la primera instancia conocida de hash de tabulación . El resultado es una familia de hachís independiente de tres tipos . En particular, es fuertemente universal .
Por ejemplo, en el ajedrez , cada una de las 64 casillas puede estar vacía en cualquier momento o contener una de las 6 piezas del juego, que son blancas o negras. Es decir, cada cuadrado puede estar en uno de 1 + 6 x 2 = 13 estados posibles en cualquier momento. Por lo tanto, es necesario generar como máximo 13 x 64 = 832 cadenas de bits aleatorias. Dada una posición, uno obtiene su hash Zobrist al descubrir qué piezas están en qué cuadrados y combinar las cadenas de bits relevantes.
Actualización del valor hash
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 simplemente haciendo XOR de la (s) cadena (s) de bits para las posiciones que han cambiado, y XORing en las cadenas de bits para el nuevo posiciones. Por ejemplo, si un peón en una casilla de tablero de ajedrez es reemplazado por una torre de otra casilla, la posición resultante se produciría haciendo XOR del hash existente con las cadenas de bits para:
'peón en esta plaza' (XOR a cabo el peón en esta plaza)'torre en esta plaza' (XORing en la torre en esta plaza)'torre en la plaza de la fuente' (XOR a cabo la torre en la plaza de la fuente)'nada en el cuadro de origen' (XORing en nada en el cuadro de origen).
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 .
Uso más amplio
El mismo método se ha utilizado para reconocer configuraciones de aleación de sustitución durante las simulaciones de Monte Carlo con el fin de evitar el desperdicio de esfuerzo computacional en estados que ya se han calculado. [3]
Ver también
Referencias
- ^ Teclas Zobrist: un medio para permitir la comparación de posiciones.
- ^ Albert Lindsey Zobrist, Un nuevo método de hash con aplicación para juegos , Tech. Rep. 88, Departamento de Ciencias de la Computación, Universidad de Wisconsin, Madison, Wisconsin, (1969).
- ^ a b Mason, DR; Hudson, TS; Sutton, AP (2005). "Rápida recuperación de la historia del estado en simulaciones cinéticas de Monte Carlo utilizando la clave Zobrist". Comunicaciones de Física Informática . 165 : 37. Código Bibliográfico : 2005CoPhC.165 ... 37M . doi : 10.1016 / j.cpc.2004.09.007 .