Implementazione dell’algoritmo Minimax al gioco del tris e adattamento a matrici n x m.

L’algoritmo Minimax è un algoritmo ricorsivo che ha come scopo la ricerca della mossa migliore in un gioco a somma zero, in cui la somma algebrica dei payoff è nulla (o costante). Consente di individuare le mosse migliori dei due giocatori durante lo svolgimento della partita, analizzando ricorsivamente l'albero di gioco a partire dalle foglie, ossia dalle possibili situazioni in cui si conclude il match, risalendo fino alla posizione corrente dei due sfidanti. A ciascuna situazione del gioco viene attribuito un punteggio, il quale valore è massimizzato se si tratta del primo giocatore, minimizzato altrimenti. Una sua possibile implementazione riguarda il gioco del Tris: due giocatori si sfidano in una tabella 3x3 utilizzando come simboli ‘X’ oppure ‘O’ ed il primo che riesce ad allinearne tre di fila in riga, colonna o diagonale vince. La tesi si propone di mostrare come l’algoritmo Minimax venga implementato a questa particolare istanza ed è analizzata la sua applicazione in casi non convenzionali in cui la tabella di gioco sia una matrice n x m. Verranno inoltre analizzati limiti, punti di forza e punti deboli e di come ci possano essere miglioramenti per questa particolare situazione. Il codice che risolve questo problema è scritto in linguaggio C a cui è allegata una breve descrizione dell’algoritmo e delle funzioni principali.