Funzionamento minmax method
Welcome to the TicTacToe wiki!
Il metodo viene invocato ogni volta che deve eseguire una mossa il computer Il metodo prende due parametri in ingresso: il grado di profondità (0 ad ogni chiamata) e il giocatore per il quale si vuole calcolare il risultato ottimo con la minmax(PLAYER_X appunto). L'algoritmo è ricorsivo, e pertanto presenta 3 casi base:
- Situazione di vittoria per il PLAYER_X
- Situazione di vittoria per il PLAYER_O
- Situazione di pareggio tra le parti
Il suo funzionamento è il seguente: Dopo aver assegnato il valore più grande possibile alla variabile min (quindi ciò che equivale a +infinito) e dopo aver assegnato il valore più piccolo possibile alla variabile max (quindi ciò che equivale a -infinito), viene eseguito un ciclo. Il ciclo continua la sua esecuzione fintanto che ci sono celle disponibili in cui eseguire una mossa. La mossa viene scelta ogni volta in base alla prima cella libera: dopodiché viene eseguita la logica vera e propria del metodo, a seconda del turno (PLAYER_X o PLAYER_O)
Di fatto l'algoritmo va occupando tutte le caselle disponibili nella scacchiera, cercando di capire se la soluzione porta ad una situazione di vantaggio (vittoria PLAYER_X), di svantaggio (vittoria PLAYER_O) o di pareggio.
Scelta una mossa, tramite la funzione placeMove(point, player), vengono eseguite (solo a livello teorico) le seguenti, fino a che non ci sono più celle disponibili. Si osserva dunque il risultato ottenuto (0, 1 o -1) per ogni possibile combinazione di situazioni a partire dalla mossa scelta, e si seleziona il punteggio più basso possibile, ovvero quello che più avvicina il PLAYER_O alla vittoria, e lo si memorizza.
ATTENZIONE! Non viene selezionato il punteggio uguale a 1, perché l'algoritmo minmax prevede che anche il giocatore avversario esegua una mossa, che sia la più vantaggiosa per lui, e di conseguenza la più svantaggiosa per PLAYER_X. Per questo motivo viene scelta sempre la mossa che porta al valore più piccolo possibile.
Il ciclo continua la sua iterazione cercando di ottenere una combinazione di soli 1, cosicché il valore più piccolo possibile sia appunto 1. Quello che accade è che, al termine dell'esecuzione del metodo, l'algoritmo dovrà selezionare tra i valori che si è memorizzato, quello con valore più alto, ovvero quello che più avvicina il PLAYER_X alla vittoria (vedi screen seguente)
L'algoritmo continua la sua esecuzione fintanto che non trova una combinazione di mosse che lo porti alla vittoria (ottenimento del valore di ritorno pari a 1) oppure che non lo porti alla sconfitta (ottenimento valore di ritorno pari a 0). Qualora tutte le combinazioni dell'algoritmo portino come risultato -1, l'algoritmo sarà obbligato nella scelta.
Allego, a titolo di esempio, uno screen delle scelte effettuate dall'algoritmo in una particolare situazione
Come si evince dallo screen, l'algoritmo segue il seguente ragionamento: Sceglie come mossa da eseguire [0, 2]. Dunque prova tutte le combinazioni, proprio a partire dalla sua scelta. Le combinazioni sono solo due:
- L'avversario mette la sua pedina su [1, 0] e di conseguenza PLAYER_X mette la pedina su [1, 2] vincendo la partita (valore 1)
- L'avversario compie la mossa opposta, e quindi PLAYER_X posiziona la pedina su [1, 0] pareggiando la partita. Tra le due soluzioni, la seconda è quella con il valore minimo, perciò viene selezionata. A seguire l'algoritmo ripete il ragionamento, ma considerando di mettere la sua pedina prima in posizione [1, 0] ottenendo in entrambe le combinazioni un pareggio, e poi mettendola in [1, 2] ottenendo in questo caso un pareggio o una vittoria. Avendo ottenuto quindi 3 risultati possibili (presi negativamente perché corrispondenti al turno ipotetico del pLAYER_O) l'algoritmo seleziona quello con valore maggiore (perché corrispondente alla scelta migliore per il PLAYER_X), posizionando dunque la pedina in [1, 2]