Generación de Llaves de Hash para posiciones

Las tablas de trasposición descritas anteriormente son usualmente implementadas como diccionarios de hash con algún orden, lo cual lleva a la pregunta ¿ Cómo generar llaves de Hash para posiciones en forma rápida y eficiente ? El siguiente esquema fue descrito por Zobrits en 1970:

• Generar 12x64 N-bit números aleatorios (donde la tabla de transposición posee 74#74 entradas) y guardarlos en la tabla. Cada número aleatorio es asociado con una pieza o una casilla. Una casilla desocupada se representa con una palabra vacía.



• Iniciar con una llave de hash nula.



• Escanear el tablero. Al encontrar una pieza, XOR su número aleatorio con la actual llave de Hash. Repetir hasta que el tablero completo sea examinado.

Un efecto interesante de este esquema es que el valor del hash es fácil de actualizar luego de cada movimiento sin tener que re-escanear el tablero completo. Las tablas de Hash están diseñadas para mantener tanto espacio en memoria como se permita. El número de entradas es usualmente una potencia de 2. Tamaños típicos van desde 4000 hasta 4 millones de posiciones. Cada entrada mantiene la información acerca de una posición. CRAYBLITZ utilizaba 6 millones de registros en su tabla de hash con 64 bits por palabra. BEBE utilizaba una tabla con palabras de 96 bits. Podia mantener hasta 256K de posiciones con cada posición en una palabra. Una excelente descripción de estas herramientas se encuentra en el texto de Levy y Newborn, "How Computers Play Chess", 1991 [14].