Esta crónica fue analizado por nuestros especialistas para asegurar la exactitud de este ensayo.
Solución:
Primero, el algoritmo minimax, si se aplica ingenuamente, tiene que calcular la mejor jugada (en un sentido minimax) para cada posición del tablero con la que posiblemente te puedas encontrar en el futuro. La poda alfa beta ayuda a reducir los cálculos innecesarios porque si sabe que nunca va a realizar un movimiento determinado, no es necesario que calcule el valor de realizar ese movimiento.
Con algunos juegos, la mejor jugada en un tablero dado se puede determinar completamente por el estado del tablero en ese momento. El ajedrez es así, así como también lo son algunos otros juegos. los key La comprensión es que cómo llegaste a un estado de juego en particular no importa realmente (desde un punto de vista minimax) una vez que hayas llegado a ese estado.
Específicamente, una transposición en el sentido ajedrecístico de la palabra es lo que sucede cuando tomas 2 caminos diferentes de movimientos para pasar de una posición inicial a una posición final.
Las tablas de transposición simplemente te permiten optimizar el cálculo de la mejor jugada cuando te encuentras con situaciones en las que diferentes jugadas dan como resultado que el tablero esté en el mismo estado final. Básicamente, una vez que llega a una posición específica del tablero, simplemente almacena el resultado de su cálculo minimax en esa posición en la tabla de transposición. Esto significa que más adelante, si alguna otra lista diferente de movimientos llega al mismo tablero, entonces, de repente, no es necesario volver a calcular completamente el minimax en ese tablero porque ya lo ha hecho y puede buscarlo en la tabla de transposición.
Entonces, si hay varias formas en que los jugadores pueden jugar que llegan a la misma posición del tablero, no es necesario que duplique mirar hacia abajo esa rama del árbol del juego más de una vez si puede guardar los resultados de ese cálculo de alguna manera. Para hacer esto de manera eficiente, necesita poder representar eficientemente una posición de tablero y luego tener alguna estructura de datos que le permita buscar esa posición de tablero rápidamente en la tabla de transposición. Encontrar la representación correcta dependerá en gran medida del juego que estés analizando.
Si connect6 es este juego, quizás un ejemplo sería bueno:
Digamos que el tablero comienza así (posición A):
X 0
0 X
Hay más de un conjunto de movimientos que te llevan a (posición B):
X 0 0 0
0 X X X
0 X
Digamos que hay n formas de pasar de la posición A a la posición B, si lo hiciste ingenuamente, es posible que tengas que probar para encontrar el mejor movimiento en la posición B hasta n veces (dependiendo de qué ramas del árbol se poden alfa-beta) . Pero realmente sería genial si no tuviéramos que hacer el exactamente el mismo cálculo varias veces para la posición de la placa B, ¡con suerte una vez sería suficiente!
Lo que tiene que hacer para aprovechar esta idea es encontrar una forma de representar una posición de placa de conexión 6. Una forma en que podríamos representar a la junta es simplemente tener un N by N array dónde N es la dimensión del tablero y simplemente almacena un valor de enumeración para cada celda que corresponde a si está vacía, tiene un X en él o tiene un 0 en eso. Sin embargo, este enfoque ingenuo no tiene grandes propiedades para buscar posiciones porque siempre estaríamos pasando por alto estos desagradables N by N matrices. Sin mencionar que tener que almacenar siempre muchos de estos N by N las matrices ocuparían mucha memoria.
Entonces, si podemos definir una función hash que tome la N by N board y lo asigna a un número entero casi único sin una tonelada de sobrecarga de procesamiento, entonces podemos agilizar este proceso. Es de esperar que hacer hash en un tablero y ver si está en la mesa sea más rápido de esta manera.
Entonces, esta es la razón por la que las personas intentan hacer una función de hash para el juego específico que están analizando. Para Connect 6, no tengo idea de cuál es la mejor función de hash, eso es algo que tendrías que resolver.
Obtener el mejor rendimiento de algo como esto requiere un montón de retoques, pero espero que esta publicación te haya dado algunas ideas. Por favor comente si desea que amplíe algo.
Este artículo de MediocreChess explica las tablas de transposición en detalle. El algoritmo Zobrist es muy simple para crear tablas de transposición.
los sistema zobrist en dos palabras:
- Genere un número aleatorio (digamos 32 bits) para cada par de [possible piece, possible cell] (para tic-tac-toe es 2 * 9) y guárdelos en un array.
- Comience en hash = 0, y XOR el hash con el número almacenado para cada par de [played piece, position of played piece]
- Obtienes tu Zobrist key !
¡Es un muy buen sistema que permite quitar una pieza! solo tienes que XOR el mismo número nuevamente. Es realmente útil para los algoritmos negamax / alpha-beta porque tenemos que cambiar / restaurar el estado muchas veces. Es fácil mantener un Zobrist key A hoy.
El sistema de tabla de transposición es :
- Para una determinada posición del juego, generas un hash, que es la firma de la posición del juego, con el algoritmo Zobrist, y obtienes un número entero (32 bits o 64 bits por ejemplo).
- Este “zobrist key”podría usarse directamente para almacenar la mejor jugada y puntuación para la posición dada, en una tabla de transposición.
-
Pero probablemente no querrá almacenar 2 ^ 32 o 2 ^ 64 entradas, por lo que toma un “hash” de Zobrist key para limitar las entradas de la tabla de transposición, digamos 16 bits para 2 ^ 16 posiciones de juego (en realidad es probablemente> = 2 ^ 20). Para obtener este hash, un método simple es “modulo” el zobrist keyo haz un “binario y”:
índice de la tabla de transposición = zobrist_key & 0xFFFF
Obtienes un número entero entre 0 y 2 ^ 16-1, ¡este es tu índice en la tabla de transposición! Por supuesto, podemos encontrarnos con colisiones, por lo que podríamos almacenar el zobrist completo. key en la tabla de transposición.
Resumamos:
- Para una posición dada, calcule el zobrist key, y luego un hash del zobrist key, que será su índice en su tabla de transposición. Guardemos datos importantes en esta entrada de la tabla: puntuación, mejor_movimiento, zobrist_key, bandera, profundidad.
- Cuando necesite buscar en la tabla de transposición, calcule el zobrist key para la posición de juego dada, luego el hash de la misma, y obtenga la entrada correspondiente. Luego verifique si la entrada es zobrist key es igual al tuyo, para evitar problemas de colisión de “false positivo”.
Así que para un Conectar 6, tienes 2 colores de piedra, y digamos 59×59 posiciones, así que tienes que crear un array de 59x59x2 = 6962 números aleatorios. Para codificar una posición de juego en un Zobrist key, toma cada piedra, y por su color y su posición, toma el número que generaste y XOR las juntas. Reduzca su Zobrist Key a un índice (hash, binario “y”, …) y almacene sus datos en este índice en su tabla de transposición.
valoraciones y comentarios
Te invitamos a añadir valor a nuestro contenido tributando tu veteranía en las ilustraciones.