Tabla de transposición

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 de movimientos diferente, 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 principalmente ú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 memorización aplicada a la búsqueda en el árbol y es una forma de programación dinámica .

Las tablas de transposición se implementan normalmente como tablas hash que codifican la posición actual del tablero como índice hash. La cantidad de posiciones posibles que pueden aparecer 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, ocupan la mayor parte de la memoria de los programas de juego.

Los programas de juegos funcionan analizando millones de posiciones que podrían surgir en los próximos movimientos de la partida. Por lo general, estos programas emplean estrategias similares 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 dada de más de una manera. Estas se denominan 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 cada jugador puede intercambiar su orden de movimientos. En general, después de n movimientos, un límite superior en 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, que son tablas hash de cada una de las posiciones analizadas hasta el momento hasta una determinada profundidad. Al encontrar una nueva posición, el programa comprueba si la tabla ya ha sido analizada, lo que se puede hacer rápidamente en tiempo constante amortizado. En caso afirmativo, la tabla contiene el valor que se había asignado previamente a esta posición, que se utiliza directamente. En caso contrario, se calcula el valor y se introduce la nueva posición en la tabla hash.

La cantidad de posiciones que busca una computadora a menudo excede en gran medida las limitaciones de memoria del sistema en el que se ejecuta; por lo tanto, no se pueden almacenar todas las posiciones. Cuando la tabla se llena, se eliminan las posiciones menos utilizadas para dejar lugar a otras nuevas; esto convierte a la tabla de transposición en una especie de caché .

El cálculo que se ahorra con una búsqueda en la tabla de transposición no consiste únicamente en la evaluación de una única posición, sino que se evita la evaluación de un subárbol completo. Por lo tanto, las entradas de la tabla de transposición correspondientes a nodos que se encuentran a menor profundidad en el árbol de juego son más valiosas (ya que el tamaño del subárbol que tiene su raíz en dicho nodo es mayor) y, por lo tanto, se les da más importancia cuando la tabla se llena y se deben 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 el hijo de un nodo correspondiente al mejor movimiento siempre se considera primero. Por supuesto, no hay forma de saber el mejor movimiento de antemano, pero cuando se utiliza la profundización iterativa , el movimiento que se encontró que era el mejor en una búsqueda más 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 conducir a resultados incorrectos si no se evita cuidadosamente el problema de interacción gráfico-historial. Este problema surge en ciertas partidas porque el historial 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 enrocará se ha 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 de 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 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 la cantidad de posiciones que se pueden almacenar en caché en cualquier momento puede ser solo una pequeña fracción (incluso órdenes de magnitud más pequeñas) que la cantidad de nodos en el árbol de 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 retienen los nodos de transposición potenciales y reemplazan otros nodos pueden dar como resultado un tamaño de árbol significativamente reducido. 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 cerca de la raíz), porque los subárboles debajo de ellos son más grandes y dan como resultado un mayor ahorro; 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 son retener los nodos en la variación principal, los nodos con subárboles más grandes independientemente de la profundidad en el árbol y los 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 del tiempo de búsqueda de entre el 0 y el 50 % en posiciones complejas de la mitad del juego y hasta un factor de 5 en la partida final. ^[2]

• Se pueden utilizar técnicas similares para almacenar en caché evaluaciones de determinadas características de una posición. Por ejemplo, se puede utilizar una tabla hash de peones para almacenar una evaluación de las estructuras de peones en una posición. Dado que el número de posiciones de peones examinadas es generalmente 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 sofisticadas de peones porque se reutilizan muchas veces.
• Se puede utilizar una tabla de refutación 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 muestran que son inferiores. En los primeros años del ajedrez por computadora, cuando la memoria era más limitada, a veces se utilizaban tablas de refutación en lugar de tablas de transposición. Algunos programas de ajedrez modernos utilizan tablas de refutación además de tablas de transposición para ordenar los movimientos.
• Los mapas de bits estáticos de los posibles movimientos de cada tipo de pieza en cada espacio del tablero se pueden almacenar en caché durante la inicialización del programa, de modo que los movimientos legales de una pieza (o en conjunto, todos los movimientos legales para la generación de movimientos) se puedan recuperar con una única carga de memoria en lugar de tener que enumerarlos en serie. Estos se utilizan comúnmente en implementaciones de tableros de bits.

• Algoritmo Minimax
• Poda alfa-beta
• Hash de Zobrist

• Tablas de transposición Sigmachess.com
• Técnica La tabla de transposición principal (información sobre la estructura de datos y la implementación)
• La anatomía de los programas de ajedrez TA Marsland, Universidad de Alberta
• Tabla de transposición Wiki de programación de ajedrez