Creo que el minimax no es la mejor opción de algoritmo para puntos y casillas. Para la historia completa sobre este juego, realmente necesitas leer el libro The Dots and Boxes Game: Sophisticated Child's Play by Elwyn R. Berlekamp, pero te daré un breve resumen aquí.
Berlekamp hace una serie de poderosas observaciones. La primera es la estrategia de doble cruz , que supongo que usted conoce (se describe en el Wikipedia page on the game).
La segunda es la regla de paridad para cadenas largas. Esto se desprende de tres hechos sobre la mayoría de los juegos bien jugados:
- Las cadenas largas se jugarán al final del juego.
- Habrá una cruz doble en cada cadena, excepto la última.
- El jugador que primero tiene que jugar en cualquier cadena larga pierde el juego.
más la restricción de que el número de puntos con los que empiezas, más el número de dobleces, es igual al número de giros en el juego. Entonces, si hay dieciséis puntos para empezar, y hay una doble cruz, habrá diecisiete giros. (Y en la mayoría de los juegos, esto significa que el primer jugador ganará).
Esto simplifica enormemente el análisis de las posiciones en mitad del juego. Por ejemplo, considere esta posición con 16 puntos y 11 movimientos jugados (problema 3.3 del libro de Berlekamp). ¿Cuál es la mejor jugada aquí?
Bueno, si hay dos cadenas largas, habrá una cruz doble, el juego terminará después de otros seis movimientos (16 + 1 = 11 + 6), y el jugador a mover perderá . Pero si solo hay una cadena larga, no habrá doble cruz y el juego terminará después de otros cinco movimientos (16 + 0 = 11 + 5) y el jugador que mueva ganará. Entonces, ¿cómo puede el jugador moverse para asegurarse de que haya una sola cadena larga? El único movimiento que gana sacrifica dos cajas:
Minimax habría encontrado este movimiento, pero con mucho más trabajo.
La tercera y más poderosa observación es que los puntos y las casillas son impartial game: los movimientos disponibles son los mismos independientemente de a quién le toca jugar y en las posiciones típicas que surgen durante el juego (es decir, que contiene cadenas largas de cajas) también es un normal game: el último jugador en mover gana. La combinación de estas propiedades significa que las posiciones se pueden analizar estáticamente usando Sprague–Grundy theory.
Aquí hay un ejemplo de cuán poderoso es este enfoque, usando la figura 25 del libro de Berlekamp.
Hay 33 movimientos posibles en esta posición, y un juego bien jugado tiene una duración de alrededor de 20 más movimientos, por lo que me sorprendería si fuera factible para Minimax para completar su análisis en un razonable hora. Pero la posición tiene una cadena larga (la cadena de seis cuadrados en la mitad superior) para que pueda analizarse estáticamente. La posición se divide en tres piezas cuyos valores son nimbers:
Estos nimbers se pueden calcular por programación dinámica en tiempo O (2 n) para una posición con n mueve restante, y es probable que desee almacenar en caché los resultados para muchas posiciones pequeñas comunes de todos modos.
Nimbers agregar usando exclusivo o: * 1 + * 4 + * 2 = * 7. Entonces, el único movimiento ganador (un movimiento que reduce el nim-sum a * 0) es cambiar * 4 a * 3 (de modo que la suma de las posiciones sea * 1 + * 3 + * 2 = * 0). Cualquiera de los tres movimientos de puntos rojos es ganar:
Editado para añadir: Soy consciente de que este resumen no constituye realmente un algoritmo como tal, y deja muchas preguntas sin respuesta.Para algunas de las respuestas, puedes leer el libro de Berlekamp. Pero hay una brecha en lo que respecta a la apertura: el conteo de cadenas y la teoría de Sprague-Grundy son realmente prácticos en el juego de mitad y final. Para la apertura necesitarás probar algo nuevo: si fuera yo, estaría tentado de probar Monte Carlo tree search hasta el punto en que se puedan contar las cadenas. Esta técnica funcionó de maravilla para el juego de Go y podría ser productiva aquí también.
Esta es una gran sugerencia, pero parece demasiado compleja para mi proyecto. –
@CaseyPatton: entonces con un 100% de probabilidad perderá un programa que hace esto, a menos que haya una heurística conocida para este juego que dicte perfectamente el juego óptimo. Incluso una búsqueda de fuerza bruta implica hacer esto. – ninjagecko
@CaseyPatton: Este es prácticamente el mejor y más usado algoritmo para todos los juegos de suma cero. ** La diferencia entre los agentes en la actualidad es la heurística utilizada, y no la utilizamos o no **. Además, creo que puede encontrar una implementación existente en python en línea, y la implementación del algoritmo de mínimo no es tan difícil de todos modos. – amit