Tabla de transposición

Una tabla de transposición es una base de datos de posiciones vistas previamente, junto con sus evaluaciones asociadas, en un árbol de juego generado por un programa informático. Si una posición se repite mediante una secuencia de movimientos diferente, se recupera su valor de la tabla, evitando así tener que volver a buscar en el árbol de juego por debajo de esa posición. Las tablas de transposición son especialmente útiles en juegos de información perfecta (donde todos los jugadores conocen el estado completo del juego en todo momento). El uso de tablas de transposición es esencialmente una técnica de memorización aplicada a la búsqueda en el árbol y constituye una forma de programación dinámica .

Las tablas de transposición suelen implementarse como tablas hash, donde el índice hash codifica la posición actual del tablero. El número de posiciones posibles en un árbol de juego es una función exponencial de la profundidad de búsqueda, pudiendo ser de miles a millones o incluso mucho mayor. Por lo tanto, las tablas de transposición pueden consumir la mayor parte de la memoria del sistema disponible y, por lo general, representan la mayor parte del consumo de memoria de los programas de juegos.

Los programas de simulación de juegos funcionan analizando millones de posiciones que podrían surgir en los próximos movimientos de la partida. Normalmente, estos programas emplean estrategias similares a la búsqueda en profundidad , lo que significa que no registran todas las posiciones analizadas hasta el momento. En muchos juegos, es posible llegar a una posición dada de más de una manera. Estas se denominan transposiciones . ^{[ 1 ]} En ajedrez , por ejemplo, la secuencia de movimientos 1. d4 Nf6 2. c4 g6 (véase la notación algebraica de ajedrez ) tiene 4 posibles transposiciones, ya que cualquiera de los jugadores puede intercambiar su orden de movimientos. En general, después de n movimientos, el límite superior de las posibles transposiciones es ( n !) ² . Aunque muchas de estas son secuencias de movimientos ilegales, es probable que el programa termine analizando la misma posición varias veces.

Para evitar este problema, se utilizan tablas de transposición. Dicha tabla es una tabla hash que almacena todas las posiciones analizadas hasta cierta profundidad. Al encontrar una nueva posición, el programa consulta la tabla para comprobar si ya ha sido analizada; esto se realiza rápidamente, en tiempo constante amortizado. Si es así, la tabla contiene el valor que se le asignó previamente a esta posición; este valor se utiliza directamente. Si no, se calcula el valor y se añade la nueva posición a la tabla hash.

El número de posiciones que busca un ordenador suele superar con creces las limitaciones de memoria del sistema en el que se ejecuta; por lo tanto, no todas las posiciones pueden almacenarse. Cuando la tabla se llena, se eliminan las posiciones menos utilizadas para dejar espacio a las nuevas; esto convierte a la tabla de transposición en una especie de caché .

El cálculo que se ahorra al consultar una tabla de transposición no se limita a la evaluación de una sola posición. En cambio, se evita la evaluación de un subárbol completo. Por lo tanto, las entradas de la tabla de transposición correspondientes a nodos con menor profundidad en el árbol del juego son más valiosas (ya que el tamaño del subárbol con raíz en dicho nodo es mayor) y, en consecuencia, se les otorga mayor importancia cuando la tabla se llena y es necesario descartar algunas entradas.

La tabla hash que implementa la tabla de transposición puede tener otros usos además de encontrar transposiciones. En la poda alfa-beta , la búsqueda es más rápida (de hecho, óptima) cuando se considera primero el hijo de un nodo que corresponde al mejor movimiento. Por supuesto, no hay forma de conocer el mejor movimiento de antemano, pero cuando se utiliza la profundización iterativa , el movimiento que se encontró como el mejor en una búsqueda superficial es una buena aproximación. Por lo tanto, este movimiento se prueba primero. Para almacenar el mejor hijo de un nodo, se utiliza la entrada correspondiente a ese nodo en la tabla de transposición.

El uso de una tabla de transposición puede llevar a resultados incorrectos si no se evita cuidadosamente el problema de la interacción entre el grafo y el historial. Este problema surge en ciertos juegos porque el historial de una posición puede ser importante. Por ejemplo, en ajedrez, un jugador puede no enrocar si el rey o la torre con la que se va a enrocar se han movido durante el transcurso de la partida. Una solución común a este problema es añadir los derechos de enroque como parte de la clave hash de Zobrist . Otro ejemplo es el empate por repetición : dada una posición, puede que no sea posible determinar si ya se ha producido. Una solución al problema general es almacenar la información del historial en cada nodo de la tabla de transposición, pero esto es ineficiente y rara vez se hace en la práctica.

Una tabla de transposición es una caché cuyo tamaño máximo está limitado por la memoria del sistema disponible, y puede desbordarse en cualquier momento. De hecho, se espera que se desborde, y el número de posiciones que se pueden almacenar en caché en un momento dado puede ser solo una pequeña fracción (incluso órdenes de magnitud menor) que el número de nodos en el árbol del juego. La gran mayoría de los nodos no son nodos de transposición, es decir, posiciones que se repetirán, por lo que las estrategias de reemplazo efectivas que conservan los nodos de transposición potenciales y reemplazan otros nodos pueden resultar en una reducción significativa del tamaño del árbol. El reemplazo generalmente se basa en la profundidad y la antigüedad del árbol: se favorecen los nodos más altos en el árbol (más cercanos a la raíz), porque los subárboles debajo de ellos son más grandes y resultan en mayores ahorros; y se favorecen los nodos más recientes porque los nodos más antiguos ya no son similares a la posición actual, por lo que las transposiciones a ellos son menos probables.

Otras estrategias consisten en conservar los nodos de la variación principal, los nodos con subárboles más grandes independientemente de la profundidad en el árbol y los nodos que provocaron cortes.

Aunque la fracción de nodos que serán transposiciones es pequeña, el árbol del juego tiene una estructura exponencial, por lo que almacenar en caché un número muy pequeño de dichos nodos puede marcar una diferencia significativa. En ajedrez, se han reportado reducciones en el tiempo de búsqueda de entre el 0 y el 50 % en posiciones complejas del medio juego y hasta un factor de 5 en el final del juego. ^{[ 2 ]}

• Se pueden utilizar técnicas similares para almacenar en caché evaluaciones de ciertas características de una posición. Por ejemplo, una tabla hash de peones puede utilizarse para guardar la evaluación de las estructuras de peones en una posición. Dado que el número de posiciones de peones examinadas suele ser mucho menor que el número total de posiciones buscadas, la tabla hash de peones tiene una tasa de aciertos muy alta , lo que permite que un programa dedique más tiempo a evaluaciones de peones sofisticadas, ya que se reutilizan muchas veces.
• Una tabla de refutación se puede usar para almacenar secuencias de movimientos desde el nodo raíz hasta los nodos hoja. Esto incluye la variante principal y las respuestas a otras líneas que demuestran su inferioridad. En los primeros años del ajedrez por computadora, cuando la memoria era más limitada, a veces se usaban tablas de refutación en lugar de tablas de transposición. Algunos programas de ajedrez modernos usan tablas de refutación además de tablas de transposición para ordenar los movimientos, mientras que la mayoría no las usa en absoluto.
• Los mapas de bits estáticos de los posibles movimientos de cada tipo de pieza en cada casilla del tablero se pueden almacenar en caché al inicializar el programa, de modo que los movimientos legales de una pieza (o todos los movimientos legales para la generación de movimientos) se puedan recuperar con una sola carga de memoria en lugar de tener que enumerarlos secuencialmente. Estos mapas se utilizan comúnmente en implementaciones de tableros de bits .

• algoritmo Minimax
• Poda alfa-beta
• Hashing de Zobrist

• Tablas de transposición Sigmachess.com
• Información técnica: Tabla principal de transposición (información sobre la estructura de datos y su implementación).
• Anatomía de los programas de ajedrez TA Marsland, Universidad de Alberta
• Tabla de transposición La wiki de programación de ajedrez