Il gioco
Tic-tac-toe è un gioco molto popolare per due giocatori, X e O, che a turno segnano gli spazi in una griglia 3×3. Il giocatore che riesce a mettere tre dei loro marchi in una riga verticale, orizzontale o diagonale vince la partita.,
Proprietà Matematiche
Da un punto di vista matematico il gioco ha due proprietà molto importanti:
Proprietà 1:
Il gioco ammette il giocatore che utilizza questa strategia ottimale sarà vittoria o pareggio, ma esso non perdere.
Proprietà 2:
Il numero di possibili corrispondenze diverse è relativamente piccolo.
All’inizio, il primo giocatore può segnare uno qualsiasi dei 9 spazi. Nel turno successivo il secondo giocatore può segnare uno dei restanti 8 spazi e così via., Il gioco continua fino a quando tutti gli spazi sono contrassegnati o uno dei giocatori vince.
È quindi facile capire che il numero totale di corrispondenze diverse è inferiore a:
987….1 = 9! = 362880
Questo è un numero ragionevolmente piccolo per un computer.
L’algoritmo
Dalle proprietà 1 e 2 ne consegue che un algoritmo pratico, e generale, per vincere / disegnare il gioco è quello di utilizzare la ricerca Alpha Beta.,
Ad ogni turno l’algoritmo valuta tutte le possibili conseguenze di ogni mossa (possibile a causa della proprietà 2) e sceglie quella che garantirà una vittoria o un pareggio (possibile a causa della proprietà 1).
Un giocatore AI che sceglie ogni mossa con l’algoritmo di ricerca alpha beta non perderà mai. Per rendere il gioco più realistico è bello introdurre un fattore stocastico in modo che ogni volta con una probabilità predefinita il giocatore AI si muova in modo casuale piuttosto che seguire l’algoritmo alpha beta., Questo renderà il gioco più realistico in quanto renderà il giocatore AI più umano e talvolta perderà.