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”. 

Ebbene signori, siccome nella mia vita ho abbondanza di tempo libero (spero si sia notata l’ironia delle mie parole), ho deciso di unire la mia passione per il forza 4 (famoso gioco da tavola) ed i miei recenti studi nel campo delle intelligenze artificiali per creare un applicazione dotata di AI per il succitato gioco!

L’obiettivo finale sarebbe quello di creare un’applicazione per iPhone ed iPod Touch ma siccome ho deciso di procedere per gradi la fase di studio dell’AI verrà fatta “codando” in Java.

Come cominciare quindi? Si inizia sviluppando l’ambiente in cui andrà ad operare la nostra intelligenza artificiale… cioè il “campo” di gioco. Scriveremo quindi la classe Java “Board” che conterrà come variabile una matrice di interi di 6 righe per 7 colonne (la rappresentazione del campo di gioco ufficiale) con i metodi relativi alla sua gestione:

• Costruttore
• Metodo di inizializzazione della matrice
• mossa (inserimento di un gettone da parte di un giocatore)
• controllo sul fatto che una mossa sia possibile
• controllo se un giocatore ha vinto
• controllo sul fatto che il gioco sia finito o no (vincita di un giocatore o Board piena)
• metodo di “stampa” della board
• getters e setters

Nella matrice del campo di gioco il valore 0 starà a significare casella libera, il valore 1 gettone del giocatore 1 ed il valore 2 gettone del giocatore 2. Nel metodo di controllo della vincita di un giocatore ho cercato di strutturare l’algoritmo in modo che esegua il minor numero possibile di calcoli, anche a costo di una aumento della complessità del codice, poiché questo sarà utilizzato tantissimo dall’AI quindi anche un piccolo risparmio in termini di calcolo sarà sicuramente apprezzato dal processore!

Il codice sorgente della classe Board è liberamente scaricabile da qua (licenza GPL v2): Board.java

Per testare il funzionamento della classe “Board” è stata scritta una classe “Test” che inplementa una versione rudimentale del gioco (via console) priva di intelligenza artificiale (essere umano vs. essere umano).

Il codice sorgente della classe Test è liberamente scaricabile da qua (licenza GPL v2): Test.java

Per il seguito della progettazione e dello sviluppo del gioco di Forza 4 vi invito a seguire il Blog nei prossimi giorni!

P.S.: Si ringrazia il Dott. (in Ingegneria Informatica) Marco Casiero per la collaborazione al progetto.

Molti di voi avranno sentito parlare del test di Alan Turing per determinare se un calcolatore può essere definito o no intelligente… quello che però non sapete è che la versione che viene sovente raccontata ai giorni nostri differisce lievemente dalla versione proposta nel 1950 da Turing poichè quasta non era particolarmete “politically correct”!

Il test come lo conoscono i più è strutturato nel seguente modo: si prendono 3 stanze diverse una in fila all’altra; in quella centrale si mette un essere umano che fungerà da interrogatore, nelle altre due in una un uomo e nell’altra un computer. L’interrogatore può comunicare con le due stanze adiacenti solo via chat (all’epoca di Turing via telescrivente) ed il suo scopo e capire in quale stanza si trovi l’uomo ed in quale il computer. Lo scopo dell’uomo è ovviamente convincere l’interrogatore di essere effettivamente un uomo mentre quello del computer è quello di ingannare l’interrogatore fingendosi uomo anche lui (e cercare quindi di convincere l’interrogatore della cosa). Il test definisce che il calcolatore è intelligente solo se riesce ad ingannare l’interrogatore convincendolo di essere lui l’uomo.

Nella versione originale invece il test si svolgeva in due fasi: nella prima nelle due stanze adiacenti a quella dell’interrogatore venivano posti un uomo ed una donna; l’omo come sopra doveva convincere l’interrogatore di essere un uomo mentre la donna doveva ingannare l’interrogatore fingendosi uomo anche lei… il test si ripeteva un certo numero di volte e si misurava la percentuale con la quale l’interrogatore indovinava in quale stanza fosse effettivamente la donna ed in quale uomo.

Nella seconda fase si svolgeva poi il test col computer (come spiegato sopra) lo stesso numero di volte e se la percentuale di volte in cui l’interrogatore distingueva l’uomo dal calcolatore era minore o uguale (circa uguale) a quella in cui distingueva l’uomo dalla donna allora il calcolatore poteva essere considerato intelligente.

Il fatto che nella prima fase del test la donna avesse il ruolo di ingannatrice creò qualche problema durante l’ascesa del femminismo nel mondo anglosassone cosicché,  da allora, si preferì raccontare una versione più “soft” oppure aggiungere lunghissimi disclaimer alla fine dei testi dove si specifica che non era intenzionale alcuna offesa nei confronti delle donne e che non si intendeva alcun modo dire che loro sono più propense all’inganno degli uomini.