Stefano Vettor’s blog

Nel mio recente viaggio negli Stati Uniti ho comprato un piccolo gioiellino che è impossibile trovare sul mercato europeo… l’e-book reader di Sony, modello PRS-505! La meraviglia era in vendita alla modica cifra di 267$, che con le tasse son divemtati 310$ (circa 225€ al cambio di allora).

Per trovarlo ho faticato non poco… sembrerebbe infatti che i negozi di elettronica a Manhattan non siano diffusissimo, ma alla fine sono riuscito a trovarlo presso un punto vendita di B & H Photo Video che si trovava vicino al mio albergo. Il lettore di e-book era disponibile in 3 diverse colorazioni: Silver, Black e Red. Io ho optato per la versione silver perchè mi sembrava la più riposante per gli occhi.

Ma veniamo alle caratteristiche di questo dispositivo:

• Peso: 250g
• Dimensioni: 12,3 x 17,43 x 0,78 cm
• Memoria: 192 MB (in realtà sono 256MB ma 64MB sono occupati dal firmware)
• Memoria aggiuntiva: slot SD e slot Sony Memory Stick
• Autonomia della batteria: circa 7500 refresh dello schermo
• Connettività: USB 2.0 che funge anche da carica-batterie
• Formati supportati: BBeB  Book, PDF, EPUB, RTF, TXT, JPEG, PNG, GIF, BMP, MP3, AAC
• Accessori inclusi: Copertina in similpelle e cavo USB

Il Sony PRS-505 oltre ad essere un lettore di e-book (il cui mercato ufficiale in italia è ahimè inesistente) funge anche da lettore MP3, anche se a mio avviso usarlo per riprodurre musica sarebbe uno spreco poiché accorcerebbe notevolmente la durata della batteria del dispositivo che è proprio uno dei suoi punti di forza (ben 7500 cambi di pagina sono davvero tanti… soprattutto se si considera che un libro ha di solito non più di 1000 pagine). 

Il PRS-505 è in grado di leggere qualsiasi PDF ma se la formattazione non è compatibile con le dimensioni del suo schermo (che è più piccolo di un A4… formato in cui si trovano molti PDF) si può agire in 2 modi: in un caso il PDF viene “rimpicciolito” fino a farlo stare nella pagina mantenendo la formattazione originale, oppure viene alterata la formattazione sul momento (viene anche quindi aumentato il numero di pagine) per permettere del file usando caratteri sufficientemente grandi da non dare problemi a nessuno.

Le immagini ovviamente vengono convertiti in scala di grigi sicché lo schermo E-Ink di cui è dotato il dispositivo possa rappresentarla. Per quanto riguarda i formati ePub e BBeB Book non ci sono problemi di rappresentazione poiché hanno di solito formattazioni adatte agli schermi degli e-book reader.

Una volta collegato via USB al computer il PRS-505 viene visto come una qualsiasi periferica di archiviazione di massa (quindi utilizzabile anche con Mac OS X e Linux oltre che con Windows) ed è possibile quindi caricarci sopra i file semplicemente copiandoli nelle apposite cartelle… è però anche vero che adottando questa soluzione si perdono alcune “chicche” come la creazione di raccolte e l’editing dei metadati accessibili solo tramite il software originale (ahimè Windows Only). Per chi si stesse già preoccupando di non poter utilizzare appieno questo dispositivo senza dover avere un computer con windows fughi immediatamente ogni timore… infatti grazie al software Calibre (disponibile sia per Mac OS X che per Linux) è possibile gestire il dispositivo al 100% delle sue potenzialità (e con esso tutta la propria libreria di e-book). Calibre, oltre a permettere di gestire la libreria, i metadati, le raccolte, ecc… del proprio e-book reader permette anche di riformattare i PDF in maniera che siano comodamente leggibili sullo schermo del dispositivo (evitando così di far fare questa operazione al reader che risparmierebbe così parecchia energia non dovendo farlo da se).

Passando ad un analisi più personale de “feeling” di utilizzo devo dire che l’apparecchio è davvero comodo, è piccolo leggero ed ha davvero un’autonomia eccezionale. Per i viaggi lunghi in cui si portano dietro più di un libro (o magari dove ci si deve portare dietro dispense dell’università) è davero l’ideale… o anche semplicemente per leggersi un libro comodamente sulla poltrona di casa propria. Lo schermi E-Ink non affatica minimamente lo sguardo (da lo stesso “feeling” della carta) ed essendo opaco è esente da qualsivoglia riflesso. Come si può poi vedere dalle immagini per il controllo è dotato di numerosi tasti… per sfogliare le pagine del proprio libro si può ricorrere o ai 2 tasti “freccia” situati sul bordo destro del dispositivo oppure 1 due tasti altrettanto “frecciosi” presenti nel più grosso tasto “circolare” presente in basso a sinistra. Per l’interazione col menu invece si può ricorrere o ai tasti numerati (ogni opzione viene contraddistinta da un tasto che le sta giusto a fianco) o navigando con le frecce presenti sul tasto “circolare” situato in basso a destra. Il dispositivo può essere semplicemente sospeso (con un consumo molto basso di energia ma comunque presente) oppure spento (consumo energetico assente): in caso di sospensione il riavvio è immediato mentre in caso di spegnimento il caricamento del firmware richiede almeno 30 secondi.

Se dovesse uscire in italia è un prodotto che consiglio veramente a tutti… in particolare il suo prezzo e davvero concorrenziale se si considera che qua da noi l’analogo più economico (CyBook Gen3) costa almeno 280€.

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.

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

Chi di voi ha letto la sezione di questo sito intitolata “Chi sono” avrà avuto modo di leggere il titolo della mia tesi di laurea (”Definizione ed Implementazione della Rappresentazione Interna delle Espressioni del Linguaggio PERLA”) e forse si sarà chiesto cosa sia mai questo “linguaggio PERLA”.

PERLA (PERvasive LAnguage) è un linguaggio completamente dichiarativo che permette all’utente di interrogare un sistema pervasivo in modo simile a come interrogherebbe una base di dati utilizzando SQL. Un sistema pervasivo è una grande rete eterogenea composta da diversi dispositivi, ognuno dei quali può utilizzare diverse tecnologie, come ad esempio reti di sensori wireless (WSN), sistemi RFID, GPS e molti altri tipi di sensori. 

Per linguaggio dichiarativo si intende un linguaggio con cui si stabilisce che cosa debba fare il programma, cioè che relazione intercorre fra input ed output, a differenza dei linguaggi imperativi, con i quali si stabilisce come un problema deve essere risolto, cioè come derivare un output da uno o più input. 

Lo scopo principale del linguaggio PERLA è quindi nascondere all’utente l’elevata complessità del sistema (dovuta all’eterogeneità ed al numero dei sensori con cui si andrà ad operare) e della programmazione di basso livello, fornendogli una interfaccia simile a quella di una base di dati, sicché possa recuperare i dati dal sistema in modo semplice e veloce. 

Il linguaggio è stato pensato per essere eseguito su un’architettura costituita da tre livelli: 

    1. livello di accesso fisico ai dispositivi 
    2. livello degli oggetti logici 
    3. livello applicativo 

All’interno dell’ultimo livello è presente il parser: esso è il componente che riceve le query sottoposte dall’utente in formato di stringhe, e ne verifica la correttezza sintattica. Obiettivo del parser è quello di tradurre ciascuna query in una struttura ad oggetti semanticamente equivalente, ma che risulti facilmente utilizzabile dal motore di esecuzione della query. 

PERLA, che è un progetto del Politecnico di Milano, è nato in seno al progetto ART DECO (Adaptive InfRasTructures for DECentralized Organizations). Quest’ultimo, che è finanziato dal Ministero dell’Università e della Ricerca, mira allo sviluppo di tecniche e strumenti per favorire la diffusione delle “networked enterprise” tra le piccole e medie imprese italiane.

Ad ora il progetto PERLA è ancora in fase di sviluppo, infatti benchè sia stata completata la stesura della grammatica alcune parti dell’esecutore delle query non sono ancora state completate, così come i driver di alcuni tipi di sensori. Tuttavia numerose sono le persone che vi stanno attivamente lavorando e sarà quindi  presto completato.

Il progetto è estremamente interessante (considerando anche il fatto che è in un settore all’avanguardi) e quindi continuerò a seguirlo anche ora che la mia parte di collaborazione è terminata… posterò qua sopra gli sviluppi futuri di cui verrò a conoscenza!

La grande sfida giunge dunque al termine, eccomi infatti qua con i benchmark finali dove vengono valutate le prestazioni di alcuni dei più noti browser anche su Linux! La gara si svolge tra Firefox 2.0.0.12, Firefox 3 beta 4 ed Opera 9.26 (non ho considerato konqueror perché è crashato al primo bench… se qualcuno ha altri browser da proporre basta comunicarmelo che provvederò ad aggiornare il tutto).

La macchina su cui si è svolta la sfida è identica a quella della sfida su Windows… un PC con una CPU Intel Pentium 4 3,2 GHz e 512 kb di Cache, 1 GB di RAM DDR 1 e Slackware Linux 12.0 installata (kernel 2.6 di default).

Il primo test è, come al solito, il SunSpider benchmark i cui risultati sono (minore è il tempo maggiori sono le performance):

Come avevo già preannunciato nel precedente post mi sono cimentato nei benchmark dei browser anche su Windows XP ed i risultati (ben illustrati da esaurienti grafici) li potete ammirare qua sotto! Ovviamente da notare che, a differenza che nei test su OS X, qua ci sarà anche Internet Explorer 7 (Internet Explorer 8 verrà confrontato con la versione 7 separatamente).

Ed eccomi allora qua con gli esiti dei miei test fatti utilizzando Safari 3.1, Firefox 2.0.0.12, Firefox 3 beta 4, Opera 9.26 ed Internet Explorer 7 (aggiornato all’ultima release) su una macchina con una CPU Intel Pentium 4 3,2 GHz e 512 kb di Cache, 1 GB di RAM DDR 1 e Windows XP SP2 (con tutti gli ultimi aggiornamenti installati).  

Il primo test è il SunSpider benchmark i cui risultati sono (minore è il tempo maggiori sono le performance):

Opera 9.26 spicca per velocità ma sembra non eccellere in quanto aderenza agli standard (il suo risultato nell’Acid Test 3 lascia un po’ a desiderare).

Firefox 2 è senza infamia e senza lode.

Safari, benché spicchi per rapidità ed aderenza agli standard, è il più lento nel rendering di pagine enormi e comunque non sempre renderizza correttamente le pagine (trovo che Safari per Windows sia di qualità infinitamente inferiore rispetto alla versione per OS X… quasi due software diversi).

Internet Explorer 7 è invece scandaloso, il più lento tra i browser ed il meno aderente agli standard… il vero “fanalino di coda” di questo test!

Inizialmente, visto che stavo testando anche Firefox 3 beta 4, ritenevo doveroso inserire anche Internet Explorer 8 nel confronto generale… ma visti i numerosi errori di rendering ho deciso che è ancora troppo “giovane” e necessita di parecchio sviluppo prima di poter essere realmente confrontato con dei browser funzionanti! In ogni caso riporto qua sotto una mini-sfida IE 7 vs. IE 8 riguardo agli stessi benchmark fatti sopra.

Ripartiamo con SunSpider benchmark i cui risultati sono (minore è il tempo maggiori sono le performance):

E’ pur sempre vero che si tratta di una beta… ma se continuano su questa strada a Redmond non saranno in grado di fare nulla che valga anche solo la pena confrontare con il resto del “mondo dei browser”.