Next: Tablas Históricas
Up: Otros avances desarrollados
Previous: Tablas de Transposición
Índice General
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].
Next: Tablas Históricas
Up: Otros avances desarrollados
Previous: Tablas de Transposición
Índice General
Santiago de Chile, Julio 2003