Una tabla de transposición es un caché de posiciones vistas previamente y evaluaciones asociadas en un árbol de juego generado por un programa de juego de computadora. Si una posición se repite a través de una secuencia diferente de movimientos, el valor de la posición se recupera de la tabla, evitando volver a buscar en el árbol de juego debajo de esa posición. Las tablas de transposición son útiles principalmente 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 memorización aplicada a la búsqueda de árboles y es una forma de programación dinámica .
Las tablas de transposición generalmente se implementan como tablas hash que codifican la posición actual del tablero como índice hash. El número de posiciones posibles que pueden ocurrir en un árbol de juego es una función exponencial de la profundidad de búsqueda y puede 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 disponible del sistema y, por lo general, constituyen la mayor parte de la huella de memoria de los programas de juego.
Los programas de juego funcionan analizando millones de posiciones que podrían surgir en los próximos movimientos del juego. Normalmente, estos programas emplean estrategias que se asemejan a la búsqueda en profundidad , lo que significa que no realizan un seguimiento de todas las posiciones analizadas hasta el momento. En muchos juegos es posible llegar a una posición determinada de más de una forma. Éstas se llaman transposiciones . [1] En ajedrez , por ejemplo, la secuencia de movimientos 1. d4 Cf6 2. c4 g6 (ver notación algebraica de ajedrez ) tiene 4 transposiciones posibles, 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 !) 2 . Aunque muchas de estas son secuencias de movimientos ilegales, aún 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 de cada una de las posiciones analizadas hasta el momento hasta una cierta profundidad. Al encontrar una nueva posición, el programa consulta la tabla para ver si la posición ya ha sido analizada; esto se puede hacer rápidamente, en tiempo constante amortizado. Si es así, la tabla contiene el valor que se asignó previamente a esta posición; este valor se utiliza directamente. De lo contrario, se calcula el valor y la nueva posición se ingresa en la tabla hash.
El número de posiciones buscadas por una computadora a menudo excede con creces las limitaciones de memoria del sistema en el que se ejecuta; por lo tanto, no se pueden almacenar todas las posiciones. Cuando la mesa se llena, las posiciones menos utilizadas se eliminan para dejar espacio a otras nuevas; esto hace que la tabla de transposición sea una especie de caché .
El cálculo guardado mediante una búsqueda en la tabla de transposición no es solo la evaluación de una sola posición. En lugar de ello, se evita la evaluación de un subárbol completo. Por lo tanto, las entradas de la tabla de transposición para nodos a menor profundidad en el árbol de juego son más valiosas (ya que el tamaño del subárbol enraizado en dicho nodo es mayor) y, por lo tanto, se les da más importancia cuando la tabla se llena y algunas entradas deben descartarse. .
La tabla hash que implementa la tabla de transposición puede tener otros usos además de buscar transposiciones. En la poda alfa-beta , la búsqueda es más rápida (de hecho, óptima) cuando el hijo de un nodo correspondiente al mejor movimiento siempre se considera primero. Por supuesto, no hay manera de saber cuál es el mejor movimiento de antemano, pero cuando se utiliza la profundización iterativa , el movimiento que resultó ser el mejor en una búsqueda menos profunda es una buena aproximación. Por lo tanto, este movimiento se intenta 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 conducir a resultados incorrectos si no se evita cuidadosamente el problema de interacción gráfico-historia. Este problema surge en ciertos juegos porque la historia de una posición puede ser importante. Por ejemplo, en ajedrez un jugador no puede 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 agregar los derechos de enroque como parte de la clave hash de Zobrist . Otro ejemplo es el sorteo por repetición : dada una posición, puede que no sea posible determinar si ya ha ocurrido. Una solución al problema general es almacenar información histórica 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 disponible del sistema y puede desbordarse en cualquier momento. De hecho, se espera que se desborde, y el número de posiciones almacenables en caché en cualquier momento puede ser sólo 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 retengan los nodos de transposición potenciales y reemplacen otros nodos pueden resultar en una reducción significativa del tamaño del árbol. El reemplazo generalmente se basa en la profundidad y el envejecimiento del árbol: se prefieren los nodos más altos en el árbol (más cerca de la raíz), porque los subárboles debajo de ellos son más grandes y generan mayores ahorros; y los nodos más recientes se ven favorecidos 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 son retener nodos en la variación principal, nodos con subárboles más grandes independientemente de la profundidad del árbol y nodos que causaron cortes.
Aunque la fracción de nodos que serán transposiciones es pequeña, el árbol de juego es una estructura exponencial, por lo que almacenar en caché una cantidad muy pequeña de dichos nodos puede marcar una diferencia significativa. En ajedrez, se han reportado reducciones en el tiempo de búsqueda del 0 al 50% en posiciones complejas del medio juego y hasta un factor de 5 en el final del juego. [2]