Cómo implementar Minimax en Tictactoe

Question

Me leer esta respuesta, y que sólo me confundió: TicTacToe AI Haciendo incorrecta Las decisiones

Podría alguien ayuda a entender cómo podría aplicar esto a Tictactoe?

1. ¿Cómo iba a "trabajar mi camino a través del árbol?
2. ¿Cómo puedo incluso crear un árbol de movimientos?

Nota: Actualmente tengo una clase que almacena el estado Junta sobre el juego (por ejemplo, ¿Está el juego completo con los actuales movimientos ?, ¿Hay un ganador ?, etc.) Cada movimiento en el tablero actual se almacena como 1 - 9 (parte superior izquierda a la inferior derecha en filas). Puedo hacer copias del estado actual de la mesa con facilidad. Puedo devolver una lista de movimientos actuales de "X" y "O", así como los movimientos disponibles a partir de una tabla.

Answer 1

Solución de Tic-Tac-Toe: Juego árbol Fundamentos
Categoría: Teoría de Juegos
Publicado el: julio 30 2008 11:38 AM, por Mark C. Chu-Carroll

La imagen lo dice prácticamente todo, pero aquí hay un enlace a la entrada del blog: http://scienceblogs.com/goodmath/2008 / 07/30 / resolver-tictactoe-juego-árbol-ba /

Answer 2

Me puede responder a su pregunta "2", y espero que esto debería ayudar a determinar pregunta "1":

Cada nodo del árbol representa el estado actual del juego después de algún número de movimientos. Así que la raíz del árbol representa el juego en el inicio (es decir, no hay piezas jugadas hasta ahora). Tiene nueve hijos (uno para cada posible primer movimiento). Cada niño, a su vez cuenta con 8 niños (uno para cada posible segundo movimiento). Y así sucesivamente, hasta llegar a puntos donde el juego se ha ganado o trefilado. Estos son los nodos hoja.