Tablas de Transposición

En ajedrez existe a menudo más de una forma de obtener una misma posición mediante diferentes secuencias de movimientos. Por ejemplo la posición resultante de la secuencia 1.e4 e5 2.f4 d6 es la misma que en la secuencia 1.f4 d6 2.e4 e5. Obtener posiciones idénticas con una secuencia distinta de movimientos se denomina transposición.

Ahora, si nuestro programa ha tomado considerable esfuerzo en buscar y evaluar la posición resultante de 1.e4 e5 2.f4 d6 sería muy útil si fuese capaz de recordar los resultados de esa posición con tal de que sea innecesario el evaluar la posición resultante de la secuencia 1.f4 d6 2.e4 e5. Desde que el programa de Richard Greenblat MacHack VI [46] desarrolló esta técnica prácticamente todos los programas la han incorporado.

Este método presenta varias ventajas, incluyendo :

• Velocidad: En situaciones donde hay muchas posibles transposiciones (por ejemplo, en la etapa del final) la tabla de transposiciones contiene con seguridad un 90% de las posiciones consultadas.



• Libre Profundidad: Supongamos que se necesita buscar cierta posición a una profundidad dada, digamos, 4 movimientos (es decir, 2 jugadas por cada bando).Si la tabla de transposiciones contiene resultados de 6 movimientos para la posición inicial no sólo se evita la búsqueda sino que se obtienen mejores resultados que los que se hubiesen obtenido de haber realizado la evaluación.



• Versatilidad : Todo programa de ajedrez posee un "libro de aperturas", es decir, una lista de posiciones conocidas en la práctica del ajedrez y los mejores movimientos seleccionados en ellas. Dado que el modus operandi del libro de aperturas es idéntico al de las tablas de transposición (buscar la posición y entregar los resultados en caso de que haya se encuentre en la tabla) se puede inicializar la tabla con el contenido del libro de aperturas tal que si se llega a una posición desconocida en el libro la tabla de transposición puede contener información acerca de ella.

El único problema real relativo a las tablas de transposición es su "voracidad" en términos de memoria. Para ser realmente útil la tabla debe contener varios miles de registros, siendo un millón o más un buen número. Con 16 bytes por entrada esto puede ser un problema en sistemas carentes de memoria.

El programa CHESS 4.5 empleaba Tablas de Hash para mantener los resultados de computaciones de alto costo que raramente cambiaban en valor o alternancia entre un pequeño numero de posibilidades :

Indexando sólo la posición de los peones esta tabla requiere poco espacio y dado que hay pocos movimientos de peones esta cambia muy poco, con decir que el 99%de las posiciones resultan en una incluida en ella.

Esto puede que no sea muy útil en estos días en que gozamos de muchos ciclos de CPU, pero la lección es muy valiosa: medidas de preprocesamiento pueden salvar mucho cálculo computacional al costo de poca memoria.