Come implementare Minimax in Tictactoe

Question

ho letto questa risposta, e appena mi ha confuso: TicTacToe AI Fare errato Le decisioni

Qualcuno potrebbe aiutarmi a capire come ho potuto applicare questo per Tictactoe?

1. Come faccio a "lavorare la mia strada attraverso l'albero?
2. Come faccio persino creare un albero di mosse?

Nota: Al momento ho una classe di bordo che memorizza lo stato del gioco (ad esempio, è l'esatto gioco con le mosse attuali ?, C'è un vincitore ?, ecc) Ogni mossa sulla scheda corrente viene memorizzata come 1-9 (in alto a sinistra a destra inferiore in righe). Posso fare copie dello stato attuale consiglio con facilità. Posso restituire un elenco delle attuali mosse per "X" e "O", così come si muove disponibili da un Consiglio.

Answer 1

Risoluzione Tic-Tac-Toe: Gioco Albero Basics
Categoria: Teoria dei giochi
Inviato il: 30 luglio 2008 11:38, da Mark C. Chu-Carroll

L'immagine dice più o meno tutto, ma qui è un link al post del blog: http://scienceblogs.com/goodmath/2008 / 07/30 / solving-tictactoe-game-tree-BA /

Answer 2

posso rispondere alla tua domanda "2", e speriamo che questo dovrebbe aiutare a capire domanda "1":

Ogni nodo nell'albero rappresenta lo stato attuale del gioco dopo un certo numero di mosse. Quindi la radice dell'albero rappresenta il gioco alla partenza (cioè nessun pezzi giocati finora). Ha nove figli (uno per ogni possibile prima mossa). Ogni bambino a sua volta ha 8 bambini (uno per ogni possibile seconda mossa). E così via, fino a raggiungere i punti in cui il gioco è stato vinto o disegnati. Questi sono i nodi foglia.