Stefano Vettor’s blog

Siamo dunque giunti al secondo appuntamento delle cronache dello sviluppo della nostra applicazione per giocare a Forza 4 e…

“Annuntio vobis gaudium magnum: habemus AI” (in soldoni… abbiamo un’intelligenza artificiale)!

Inizialmente avevo pensato di sviluppare l’intelligenza artificiale del gioco seguendo rigidamente l’algoritmo MinMax con potatura Alfa-Beta ma appena cominciato ho incontrato subito un problema: la funzione di utilità!

MinMax utilizza una funzione di utilità per valutare uno stato terminale all’interno dell’albero di ricerca assegnandoli un valore numerico che ne rappresenta la “bontà“… il problema è come decidere se uno stato è migliore di un altro (ovvero con che criterio la funzione utilità ritorna un determinato numero ricevendo come argomento un determinato stato). Alla fine ho deciso di optare per una valutazione basata sulla profondità!

Nell’attuale implementazione dell’AI un a soluzione è preferibile ad un’altra principalmente se è a profondità inferiore (ma anche rispetto ad altri fattori). Non essendo però del tutto ancora convinti di come gestire la componente “avversaria” all’interno della ricerca della strategia giusta (la componente Min dell’algoritmo MinMax) abbiamo deciso di usare l’idea di fondo di MinMax per costruire un nuovo algoritmo che avremo patchato “on the way” che ci avrebbe aiutato a comprendere quali fattori sono veramente importanti nella ricerca della soluzione ideale in Forza 4 (per poi, in una fase successiva dello sviluppo, usarli per la costruzione della funzione utilità dell’algoritmo MinMax della versione finale).

L’attuale algoritmo procede nel seguente modo:

1. Prendeo stato attuale del gioco e per ognuna delle sue 7 (o meno se alcune colonne sono piene) possibili mosse inizia un iter di valutazione per scegliere la migliore. Innanzitutto si sincera che facendo quella mossa l’avversario non possa vincere al turno immediatamente successivo oppure che non possa creare una composizione a tris inbloccabile che porterebbe l’avversario a vincere il turno successivo ancora ( _XXX_ ad esempio è una configurazione a tris inbloccablie perche indipendentemente dal bloccare a destra o a sinistra l’avversario farà comunque 4 al turno dopo)
2. Se le condizioni sopracitate sono rispettate dalla mossa allora l’algoritmo genera 2 alberi di ricerca: uno che cerca la vittoria a profondità minima per l’AI (quando trova una vittoria ad una determinata profondità nel continuare a cercare altre soluzioni migliori non scenderà mai a profondità superiori di quelle della soluzione già trovata “potando” così l’albero) ed uno che cerca la vittoria a profondità minima per l’avversario.
3. Una volta calcolata la profondità minima della vittoria grazie agli alberi di ricerca controlla se la propria è minore di quella dell’avversario… l’algoritmo predilige scegliere mosse che abbiano profondità di vittoria inferiori a quelle dell’avversario. Non sempre però questo è possibile… in ogni caso a questo tipo di mosse viene data una priorità più alta.
4. A questo punto si controlla se questa mossa ha una profondità minore rispetto alla mossa selezionata come migliore precedentemente, la profondità è inferiore la mossa da effettuare viene aggiornata selezionando quella attuale altrimenti se ha profondità uguale si continua la valutazione.
5. Se la valutazione continua si controllerà se la vittoria avversaria è più lontana in questo caso che nella mossa già selezionata… in caso affermativo la mossa da fare viene aggiornata con la corrente, se invece la profondità è uguale si continua la valutazione.
6. Se la valutazione continua si controlla se questa mossa è più centrale rispetto alla precedente. Questa decisione si basa più su un’impressione empirica che ho del forza 4, cioè che una mossa centrale è preferibile ad una laterale (non sempre ma in generale); Se anche in questo caso la centralità è identica (per centralità si intende la vicinanza alla colonna centrale) si tira a caso (tramite funzione random) se aggiornare o no la mossa.
7. Se nell’iter precedente non si è riusciti a trovare una mossa significa che si sta per perdere (a meno di una grave disattenzione dell’avversario) e quindi si cercherà di giocare una mossa che per lo meno non ci faccia perdere al turno successivo… sia mai che l’avversario sia poco scaltro e non riesca a vincere nonostante il vantaggio!

L’AI sviluppata è passabilmente brava (ma potrebbe essere molto meglio) e stiamo lavorando ad ulteriori metodi che le permettano una maggiore attenzione alle mosse avversarie ed una migliore valutazione delle mosse (ad esempio preferire una mossa che porta ad un tris con possibilità di evolvere in un 4 o mosse che portano ad una composizione tipo xx_x sono preferibili a mosse che “non lo fanno“).

Nel frattempo potete scaricare quanto fatto fin’ora da questo pacchetto compresso contenente tutti i sorgenti: Forza4-v0.1

Come nella versione precedente il software è rilasciato sotto licenza GNU GPL v2. Per far partire il programma eseguire la classe Test editando il metodo “main” per scegliere la modalità di gioco (PC vs. PC, Umano vs. PC, PC vs. Umano) decommentando (togliendo il “//” che sta davanti al nome del metodo) l’istruzione che fa partire il metodo della modalità di gioco prescelta (commentando ovviamente quella che parte di default che è PC vs. PC).

P.S.: siccome l’AI fa ampio uso dello heap è possibile che le impostazioni di default di Java siano insufficienti per il suo corretto funzionamento quindi può essere necessario dover aumentare l’heap a 256 MB (di default sono 128MB) usando da terminale il comando “java -Xms32m -Xmx256m”.