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.

Una delle cose che mi fanno amare particolarmente lo sviluppo del software su Mac OS X sono XCode e Cocoa che rendono davvero facile il lavoro allo sviluppatore!

Cio che rende Cocoa un framework tanto fantastico è il fatto che ti permette di concentrarti appieno sul progetto a cui stai lavorando in quanto ti astrae totalmente dai livelli più bassi del sistema mettendoti a disposizione classi e funzioni che semplificano e velocizzano enormemente il processo di sviluppo.

Per esempio è possibile creare un browser web scrivendo una sola linea di codice sorgente (ed ovviamente disegnando la GUI usando Interface Builder):

[[webView mainFrame] loadRequest:[NSURLRequest requestWithURL:[NSURL URLWithString: [urlText stringValue]]]];

Io credo che sia una cosa davvero fenomenale! Per esempio… se si stesse lavorando ad un aggregatore RSS basterebbe concentrarsi sul “core-task” dell’applicazione senza perdersi in mille problemi sviluppando anche tutto il motore di rendering delle news!

Il codice sorgente del browser dell’esempio può essere scaricato qui: ibrowser.zip

In questi giorni, ispirato da un articolo sul “Gioco della vita” del matematico inglese John Conway ho deciso di realizzare CocoLife. 

Il programma (per Mac OS X), che implementa per l’appunto il gioco sopracitato, ha un mondo a matrice con 4 possibili configurazioni: 50×50, 100×100, 250×250 e 500×500 (quest’ultima ha un carico elaborativo particolarmente alto per la CPU). CocoLife permette in oltre di configurare il colore dello sfondo del mondo e degli automi e la velocità di esecuzione del programma (controllabile tramite la barra a scorrimento in basso che varia il tempo tra una transizione ed un’altra). Tramite il menu in alto alla voce “Matrice” è possibile attivare l’editor che permetterà di crearsi le proprie configurazioni (normalmente viene generata una configurazione random). A differenza di molte implementazioni di questo gioco i bordi del mondo sono connessi uno con l’altro… cioè se un automa sfora a destra comparirà a sinistra, altrettanto con l’alto ed il basso. Il programma è scritto in Objective-C usando il framework Cocoa di Mac OS X.

Il programma ed i relativi sorgenti sono scaricabili nella sezione portfolio di questo sito.

Dopo l’articolo “12 giorni con Leopard”, che descriveva la mia user-experience con il nuovo felino di Apple, ho deciso di scrivere questo per parlare della mia developer-experience. 

Con Leopard si sono rinnovati XCode (che giunge alla versione 3.0) ed Interface Builder, in particolare quest’ultimo ha subito migliorie radicali che lo rendono finalmente un’ottimo software di sviluppo per OS X (prima, per quanto fosse utile, aveva qualche grossa mancanza come l’impossibilità di inserire NSToolBar con un semplice drag & drop), e sono arrivati anche nuove utilities come Instruments che permette di passare ai “Raggi X” la propria esecuzione monitorandone praticamente ogni aspetto… dell’utilizzo delle risorse al singolo accesso a dati tramite Core Data.

Interface Builder, tra le varie, ha ampliato tantissimo l’elenco di oggetti che è possibile utilizzare (giò per i bottoni è possibile scegliere almeno tra 5 o 6 modelli differenti), è ora inoltre possibile creare finestre HUD (quelle nere semitrasparenti) semplicemente selezionandole dal menu e la ToolBar può essere aggiunta alle finestre e modificata semplicemente trascinandole dal menu laterale fin sulla finestra. Le modifiche sono anche altre ma non è mia intenzione fare una lista una per una di tutte le sue nuove feature (tra l’altro c’è anche il nuovo pannello per le impostazioni Core Animation). In assoluto è migliorato molto dal punto di vista sia dell’immediatezza che della completezza!

XCode ha avuto “improvement” minori (anche perché era già buono com’era) ma qualcuno c’è stato… ad esempio adesso spostando il mouse su aree di codice racchiuse da parentesi queste vengono evidenziate rispetto al resto del sorgente.

Non è stato solo il linguaggio ad essere aggiornato… ma anche la libreria… tanto per dirne una adesso per chi volesse cambiare l’icona dell’applicazione nel dock, o volesse aggiungervi una badge, invece che “perdere” tempo prezioso a scriversi classi apposite può limitarsi a scrivere il seguente codice usando la classe NSDockTile:

NSDockTile *dock = [NSApp dockTile];
[dock setBadgeLabel: @"Quello che vuoi"];
[dock display];

Le novità sono ancora moltissime e per avere una panoramica più completa vi invito a visitare http://developer.apple.com

Mi scuso con i miei lettori per l’essenzialità del post ma purtroppo l’imminenza delle prime sessioni d’esami (prove in itinere) mi tengono molto occupato!