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.

Da quando è stato è stato rilasciato l’SDK per l’iPhone e per l’iPod Touch ed è stata rivelata la politica di Apple nei confronti dello sviluppo di applicazioni per queste due piattaforme non mi sono mai espresso… aspettavo di vedere come sarebbe evoluta la cosa!

Ebbene ad ora posso dire che una cosa che già di suo era nata male è evoluta in peggio!

Tanto per cominciare non digerisco il fatto che solo anche per poter installare un’applicazione da me sviluppata sul mio iPod Touch (o iPhone) debba pagare 90€ ad Apple… capirei per la pubblicazione sull’Apple Store (capisco ma non condivido), ma che io debba pagare per utilizzare qualcosa fatto da me su qualcosa che mi appartiene è scandaloso!

Che la pubblicazione di un’applicazione sullo store sia a pagamento posso trovarlo giusto… ma non nel caso (quale poi in realtà è) questo sia l’unico modo disponibile per la sua diffusione! Se scelgo di usare un canale particolare per distribuire la mia applicazione è giusto che paghi i fornitori di questo canale… ma non se questo è l’unico disponibile perché mi troverei nella condizione di non poter scegliere liberamente cosa fare con il frutto dei miei sforzi!

Si aggiunga poi che Apple può anche rifiutarsi di pubblicare il mio lavoro senza necessariamente essere in possesso di validi motivi… quindi può portare lo sviluppatore a trovarsi nella spiacevole situazione di aver lavorato, speso tempo e faticato per mesi e di veder poi tutti questi sforzi vanificati! Non è un comportamento accettabile!

Ho il forte sospetto che questa politica di cancellazione (ed anche la politica che impedisce la creazione di software quali i sistemi di navigazione satellitare) sia tutta dovuta ad accordi con grandi software-hause che hanno stipulato accordi (forti del loro potere economico) con Jobs & friends per ottenere l’esclusiva su alcune tipologie di prodotti assicurandosi il 100% di profitti e lo 0% di concorrenza…. il tutto a scapito dei piccoli sviluppatori (che tra l’altro sono la vera forza dell’iPhone)! Alla faccia del libero mercato!

E’ davvero deludente vedere l’atteggiamento di Cupertino nei confronti di questa piattaforma… una politica simile applicata alla piattaforma Mac probabilmente porterebbe al fallimento della stessa a causa della fuga in massa di tutti gli sviluppatori! Ci si chiede come possa essere tollerata!

Apple tratta gli iPhone developer davvero di “cacca”… ne calpesta impunemente i diritti e come se non bastasse tramite discutibili NDA (Non Disclosure Agreement - accordo di non divulgazione) impedisce loro di rendere pubblici i soprusi di cui sono vittime! Davvero un comportamento scorretto… talmente scorretto che mi ha fatto abbandonare ogni proposito di sviluppare applicazioni per iPhone ed iPod Touch (e dire che avevo già in mente un sacco di belle idee… ma per ora resteran tali)!

Che dire… se Cupertino non cambierà rotta è probabile che continuerà a perdere sempre più sviluppatori… magari in favore del ben più libero Android! Spero francamente che la situazione migliori… anche se a dire il vero sarei felice anche se si limitesse a non peggiorare!

Speriamo che alla “Mela Morsicata” si rendano conto di quel che fanno e rinsaviscano!

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

Ho poc’anzi terminato di creare due stencil per OmniGraffle (noto software per la creazione di grafici e diagrammi per Mac OS X) che permettono la creazione di diagrammi IDM (Interactive Dialogue Model) sia nella versione C-IDM (Conceptual IDM) che L-IDM (Logical IDM).

Per chi non lo sapesse IDM è una tecnica di progettazione per applicazioni web orientata al dialogo. Questa metodologia nasce dal connubio di ricerca del campo del design di applicazioni web e delle scienze linguistico-comunicative.

I due stencil, di cui do degli screenshot qua sotto, sono liberamente scaricabili da questo link: IDM-Stencil.zip

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!