Tabla de transposición - Transposition table

Una tabla de transposición es un caché de posiciones vistas anteriormente 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 del 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 árbol y es una forma de programación dinámica .

Las tablas de transposición se implementan típicamente como tablas hash que codifican la posición actual de la placa 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 del sistema disponible y normalmente son la mayor parte de la huella de memoria de los programas de juego.

Funcionalidad

Los programas de juego funcionan analizando millones de posiciones que podrían surgir en los próximos movimientos del juego. Por lo general, 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 ahora. En muchos juegos, es posible alcanzar una posición determinada de más de una forma. Estos se llaman transposiciones . En el 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 cualquier jugador puede cambiar su orden de movimiento. 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, 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 ahora hasta una cierta profundidad. Al encontrar una nueva posición, el programa comprueba 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. En caso contrario, se calcula el valor y se ingresa la nueva posición en la tabla hash.

El número de posiciones buscadas por 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 mesa se llena, se eliminan las posiciones menos utilizadas para dejar espacio para otras nuevas; esto hace que la tabla de transposición sea una especie de caché .

El cálculo guardado por una búsqueda en la tabla de transposición no es solo 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 para los nodos a menor profundidad en el árbol del 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 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 de antemano cuál es el mejor movimiento, 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 la interacción gráfico-historial. Este problema surge en ciertos juegos porque el historial de una posición puede ser importante. Por ejemplo, en el ajedrez, un jugador no puede enrocar si el rey o la torre con la que se enroca se ha movido durante el transcurso del juego. 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 dibujo por repetición : dada una posición, puede que no sea posible determinar si ya ocurrió. 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.

Estrategias de reemplazo

Una tabla de transposición es un 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 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 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 retienen los nodos de transposición potenciales y reemplazan otros nodos pueden resultar en un tamaño de árbol significativamente reducido. El reemplazo generalmente se basa en la profundidad y el envejecimiento 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 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.

Tamaño y rendimiento

Aunque la fracción de nodos que serán transposiciones es pequeña, el árbol del 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 el ajedrez, se han informado reducciones en el tiempo de búsqueda del 0-50% en posiciones complejas del juego intermedio y hasta un factor de 5 en el juego final.

Técnicas relacionadas

  • Se pueden utilizar técnicas similares para almacenar en caché las evaluaciones de ciertas características de un puesto. 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 de peones sofisticadas porque se reutilizan muchas veces.
  • Se puede utilizar una tabla de refutación para almacenar secuencias de movimientos desde el nodo raíz a los nodos hoja. Esto incluye la variación principal y las respuestas a otras líneas que muestran que son inferiores. A veces se usaban tablas de refutación en lugar de tablas de transposición en los primeros años del ajedrez por computadora, cuando la memoria era más limitada. 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é en la inicialización del programa, de modo que los movimientos legales de una pieza (o juntos, todos los movimientos legales para la generación de movimientos) se pueden recuperar con una sola memoria cargar en lugar de tener que enumerarse en serie. Estos se utilizan comúnmente en implementaciones de bitboard.

Ver también

notas y referencias

  1. ^ Tablas de transposición , Gamedev.net, Francois-Dominic Laramee.
  2. ^ Atkin, L. y Slate, D., 1977, "Chess 4.5, the Northwestern University Chess Program", en Habilidad ajedrecística en el hombre y la máquina, Peter W. Frey, Ed. Springer-Verlag, Nueva York, NY

enlaces externos