insertcoin: archeologia informatica

Il primo giorno dell'anno, insieme a un po' di gente, sono andato alla Galleria Nazionale di Palazzo Arnone a Cosenza a visitare una mostra stupefacente (lo stupore era dovuto al fatto di essere a Cosenza), insertcoin, una mostra dedicata all'informatica del tempo che fu e ai giochi.
L'esordio della mostra è in puro stile geek con questo vero e proprio pezzo da museo

e con una telescrivente collegata alla rete per inviare un po' di tweet in giro per il mondo!

C'erano poi altre robine interessanti, come ad esempio il Pong

o il Pac-Man, dove mia sorella è riuscita a vincere il primo livello:

Vincere il primo livello non è semplice come si crede, in particolare a causa del joystick, che innanzitutto non è certo sensibile come quello moderno, e poi bisogna esserci abituati, e finora a Pac-Man abbiamo giocato solo con le freccette (la forza del progresso tecnologico nel campo). E poi c'è la questione degli algoritmi di comportamento dei quattro fantasmini. Ma partiamo dall'inizio:
Pac-Man è un gioco ideato da Tohru Iwatani della Namco e uscito come arcade nel 1980. Le motivazioni per creare un gioco di questo tipo vengono spiegate dallo stesso Iwatani:

All the computer games available at the time were of the violent type - war games and space invader types. There were no games that everyone could enjoy, and especially none for women. I wanted to come up with a “comical” game women could enjoy.⁽¹⁾

Il gioco si svolge all'interno di un labirinto disseminato da piccoli semi gialli e da quattro super semi che devono essere mangiati da Pac-Man per vincere ciascun livello. Suoi avversari sono quattro fantasmini di quattro colori diversi. All'inizio del gioco questi fantasmi si trovano tre all'interno di una scatola centrale, la casa, e uno a presidiare la porta esterna. Subito dopo l'inizio i quattro iniziano la caccia a Pac-Man, che ha come ulteriore compito quello di sfuggire ai suoi inseguitori. Unica eccezione durante la quale i ruoli si invertono è quando il nostro personaggio mangia uno dei super semi: in quel caso i fantasmini cambiano colore e possono essere mangiati da Pac-Man fino a quando non ritornano nella condizione originale. Il passaggio da preda a cacciatore avviene attraverso una fase oscillante, durante la quale il colore del fantasma cambia velocemente da quello di preda a quello di cacciatore e viceversa: i fantasmi possono ancora essere mangiati, durante la vibrazione, ma Pac-Man corre il rischio di addentarlo proprio nell'istante in cui ritornano cacciatori. Di un fantasma mangiato, invece, restano solo gli occhi, che oscillano verticalmente e si muovono verso la casa, dove restano in attesa di rigenerarsi.

Ognuno dei fantasmi ha una sua intelligenza artificiale differente, realizzata in modo da mostrare una sorta di personalità distinta. Ovviamente per ognuno dei fantasmini i quattro algoritmi hanno un compito ben preciso: scegliere la cella da occupare a partire dalla cella occupata, dalla topologia del labirinto e dalla posizione di Pac-Man. In particolare ognuno dei fantasmini si muoverà in maniera differente a seconda della sua personalità. A completare poi le cose c'è anche una alternanza di sotto-comportamenti nella modalità cacciatore: si può infatti distinguere tra una fase di caccia e una fase di dispersione. Queste due fasi si alternano per quattro periodi fino a che il fantasma non resta definitivamente nella fase di caccia, a meno che il fantasma non viene mangiato da Pac-Man mentre è ancora in azione l'effetto del super-seme: in questo caso l'alternanza delle due fasi ricomincia dall'inizio. Questa alternanza avviene, comunque, in questo modo: per 7 secondi dispersione, per caccia e alla quarta volta per cinque secondi dispersione e poi definitivamente caccia⁽¹⁾.

L'importanza dell'esistenza di una fase di dispersione lo capiremo più avanti, ora, però, direi che è venuto il momento di capire quali siano i caratteri impressi in ognuno dei cacciatori:

Il fantasma rosso, Blinky (in giapponese Akabei) è detto Ombra (Oikake in giapponese) ed è sostanzialmente una sorta di puntatore che si dirige verso la posizione di Pac-Man. Blinky però presenta una particolarità assente negli altri fantasmi che lo rende, in un certo senso, più pericoloso (e non mi riferisco al fatto che è l'unico a partire fuori dalla casa). Ad ogni livello, in due momenti particolari che dipendono dal numero di semi rimasti, aumenta la sua velocità del 5% e soprattutto, la sua fase di dispersione, non è puramente dispersiva, ma continua a puntare comunque Pac-Man. Questa modalità che potremmo definire killer (in originale cruise elroy) finisce con la morte di Pac-Man, ma riprende dopo la rigenerazione e l'uscita dalla casa di tutti gli altri colleghi⁽¹⁾.
Il fantasma rosa, chiamato Pinky (stesso nome in giapponese) è anche soprannominato Veloce, Machibuse in giapponese, che in effetti vuol dire agguato. In effetti Pinky nel suo movimento non punta la posizione attuale di Pac-Man ma la sua presunta posizione successiva, che è selezionata come 4 celle di fronte a Pac-Man. Nell'algoritmo di Pinky, però, c'è un baco: quando la faccia di Pac-Man è rivolta verso l'alto, Pinky punta la cella che si trova quattro celle in su e quattro celle a sinistra rispetto alla posizione attuale del giallo mangiatore di semi⁽¹⁾. Un'altra vulnerabilità di Pinky indipendente dal baco la potete poi vedere nell'immagine seguente:

Inky (Aosuke in giapponese), il fantasmino blu, ha invece un sistema di puntamento che è una sorta di combinazione dei sistemi precedenti: tiene infatti conto della posizione di Pac-Man aumentata di due celle avanti e della posizione di Blinky per calcolare la cella verso cui dirigersi. E' esemplificativa in questo senso la seguente immagine⁽¹⁾:

Clyde (Guzuta in giapponese), l'ultimo fantasmino a uscire dalla casa, di colore arancione, ha un comportamento apparentemente aleatorio, da finto tonto (otoboke in giapponese), ma in realtà la sua strategia è piuttosto precisa: se la sua distanza da Pac-Man è superiore alle 8 celle, allora punta, come Blinky, la posizione attualmente occupata da Pac-Man, altrimenti se la sua posizione è inferiore, allora punta addirittura una cella esterna al labirinto. Questo, per assurdo, potrebbe portare Clyde a chiudere il suo percorso in un loop nel casi il giocatore riesce a mantenere Pac-Man in una posizione fissa, come nell'immagine che segue⁽¹⁾:

Questi algoritmi differenti per i fantasmini furono il primo vero aggiornamento del gioco, ma molti sono stati i programmatori e le software house che hanno subito cercato di migliorare il gioco. Tra tutti questi tentativi ci sono stati anche quelli da parte di ricercatori, che ovviamente hanno anche cercato di studiare in maniera sistematica il funzionamento del gioco. Uno dei primi studi risale al 1992, Genetic Programming: on the Programming of Computers by Means of Natural Selection di John Koza (pdf) dove ci sono un po' di screenshot e di comandi dell'algoritmo. Ad ogni modo una buona rassegna di lavori di ricerca sul gioco la si può trovare nell'introduzione dell'articolo di David Robles e Simon Lucas⁽²⁾ e si nota subito che molti degli articoli e dei lavori citati utilizzano le reti neurali per la ricerca della migliore strategia di gioco. Non fanno in questo senso nessuna differenza nemmeno Mark Wittkamp, Luigi Barone e Philip Hingston, che però sono alla ricerca non tanto della migliore strategia di gioco, ma della migliore strategia di caccia⁽³⁾!
Innanzitutto un paio di righe sulle reti neurali. In pratica una rete neurale è un algoritmo in grado di imparare dalle sollecitazioni esterne, costruito come una vera e propria rete topologica, dove si identificano nodi e collegamenti e si descrive il flusso di informazioni e il modo in cui tenerne conto attraverso una serie di leggi matematiche (generalmente delle sommatorie). In questo modo, ad esempio, si riescono a progettare e realizzare molti dei software usati in astronomia, ma anche in ambito investigativo, o in base anche in alcuni programmi commerciali, in grado di ripulire una immagine e renderla sempre più nitida.
Un modo per indurre l'apprendimento di una rete neurale è costruire degli algoritmi di evoluzione, uno dei quali è NEAT, Neuroevolution of augmenting topologies di Kenneth Stanley e Risto Miikkulainen⁽⁴⁾, che ha avuto un primo successo nella determinazione della migliore strategia di gioco nell'Othello. Nel caso di Pac-Man, NEAT è stato utilizzato da Wittkamp e soci per programmare e far evolvere la rete neurale dei fantasmini: l'obiettivo dei ricercatori, infatti, era comprendere lo sviluppo di una strategia di gruppo, in questo caso finalizzata alla cattura di Pac-Man, e ovviamente cercare di ottenere la strategia migliore.⁽³⁾. Per ottenere questo risultato il gruppo ha utilizzato una versione del gioco modificata da Ben Chow⁽⁶⁾.
Scelto l'ambiente in cui svolgere l'esperimento, il primo passo è stato programmare il giocatore: i tre hanno scritto un pacbot, immaginandolo come un giocatore decente in grado di concludere il primo livello contro gli algoritmi originali. Nel caso specifico, la sua prestazione media, su un totale di 25 partite, è stata di 4808,4 punti e 1,44 vite perse ad ogni partita. Considerando che l'obiettivo principale del pacbot era quello di mangiare tutti i semi e che il punteggio massimo raggiungibile mangiando solo i semi è di 2700, è chiaro come l'algoritmo di base del giocatore alla fine non si è semplicemente limitato a superare il livello con il minimo sforzo.
La rete neurale alla base dell'intelligenza artificiale dei fantasmini, invece, è strutturata come una sorta di navigatore che deve indicare la posizione successiva a partire da come il gioco si evolve nel tempo. Questa evoluzione viene rappresentata dal numero di semi mangiati e quindi dal punteggio del pacbot, dalla posizione di quest'ultimo e dalla condizione di cacciatore o di preda del fantasma. L'idea è dunque calcolare le probabilità per ognuna delle celle adiacenti e far muovere il fantasma nella cella a maggiore probabilità (ovviamente ognuno dei fantasmini conosce la topologia del labirinto). In questo modo la rete neurale propone a ciascun fantasma un unico output, in luogo dei quattro che altri approcci propongono⁽⁵⁾.
Vengono realizzati quattro differenti tipi di reti neurali, ognuno dei quali ottiene i seguenti risultati (che vengono ovviamente confrontati con l'IA originale):

La prima strategia, detta chasing and evading Pacman non è per nulla migliore rispetto a quella standard. Non solo il pacbot ottiene un punteggio maggiore, ma il tasso di perdita di vite è inferiore.
La seconda strategia, detta remaining dispersed introduce un effetti di dispersione: i fantasmini tendono ad allontanarsi uno dall'altro quando diventano prede. Se ciò migliora la capacità di cacciare Pac-Man rispetto alla prima strategia, permette d'altra parte al pacbot di accumulare una quantità di punti anche superiore rispetto alla sfida contro l'IA originale. E' sicuramente una indicazione controintuitiva, visto che praticamente tutti i giocatori di Pac-Man preferiscono addensare i fantasmini uno vicino all'altro prima di prendere una super pillola per poterli mangiare. Il fatto che invece il pacbot non sia programmato per questo e il punteggio record ottenuto nella serie di 4 esperimenti suggerisce che una strategia conservativa da parte del giocatore è molto più efficace rispetto a quella a maggior rischio che richiede l'addensamento dei fantasmini.
La terza strategia, protection behaviour, sembra migliorare sia la capacità di limitare il punteggio medio del livello, sia la qualità della caccia. L'idea di fondo della strategia è quella di minimizzare il numero di fantasmini mangiati rendendoli meno vulnerabili nella fase di preda. In particolare le prede vengono protette dal pacbot interponendo tra questi un cacciatore. Un comportamento, però, inatteso che però, visti i risultati, sembra efficace è invece il suicidio: in alcune situazioni, infatti, le prede si gettano tra le fauci del pacbot. Il vantaggio di questo comportamento sta nel fatto che in questo modo hanno la possibilità di rientrare nella casa prima e quindi di proteggere più velocemente i fratelli rimasti ancora nello stato di prede. E' una strategia, questa, che ad esempio viene usata nel Go, dove i giocatori spesso sacrificano alcuni dei pezzi in modo da, ad esempio, far scoprire l'avversario, e rivela anche l'emergere di una collaborazione sociale tra i fantasmini semplicemente introducendo il concetto di protezione del più debole.
L'ultima strategia, ambushing Pac-Man, è, a conti fatti, la più efficace. Pur non avendo il punteggio medio di livello inferiore, resta comunque più basso rispetto al punteggio medio contro l'IA originale, mentre il tasso di perdita di vite arriva quasi a 2. Un risultato di questo genere viene raggiunto introducendo un nuovo, interessante concetto: limitare il numero di incroci controllati da Pac-Man. Questo vuol dire che, nell'ipotesi in cui un incrocio è controllato dal pacbot se ha a disposizione almeno una via di fuga, il compito dei fantasmini è ridurre al minimo le vie di fuga del giocatore. A livello di strategia di gruppo la conseguenza è che i fantasmi non attaccano più singolarmente, ma in gruppo, e soprattutto gli attacchi vengono condotti da direzioni differenti e non sono più diretti come nella prima strategia.
Se invece ci vogliamo concentrare sulla migliore strategia per vincere, può essere interessante dare un'occhiata a questo trucchetto proposto da Jamey Pittman nel suo corposo Pac-Man dossier:

Un'altra strategia interessante che il giocatore può adottare è quella sviluppata da Robles e Lucas per il gioco successivo nella serie di Pac-Man, Ms. Pac-Man, dove sulla stessa struttura di base il giallo mangiatore viene sostituito dalla sua dolce metà!
In questo caso il gioco viene strutturato come una serie di percorsi possibili che la nostra signora in giallo deve intraprendere per vincere il gioco. Ogni nodo di ciascuno dei quattro percorsi possibili (ogni percorso con una data lunghezza) può essere o vuoto, o occupato da un seme, o occupato da un fantasmino. I percorsi vengono selezionati in modo casuale, oppure selezionando quello contenente un super seme o, in sua assenza, quello con il maggior numero di semi, oppure ottimizzando variabili come il numero di semi, la presenza di super semi, la presenza di fantasmini (ovvero dove porta il percorso). Quest'ultima strategia è risultata quella vincente, non solo quando viene applicata al gioco originale, ma anche a una versione modificata (e per certi versi semplificata) del gioco stesso. Il simulatore presenta una serie di caratteristiche che in effetti semplificano il compito del giocatore, come ad esempio settare identica la velocità di giocatore e fantasmi, o non imporre alcuna diminuzione di velocità di Ms. Pac-Man mentre mangia, aggiungere un'extra-vita una volta raggiunti i 10000 punti, far ricomparire i fantasmi già pronti e senza alcun tempo di attesa per la rigenerazione.
A conti fatti il bot creato per l'occasione ha ottenuto i migliori risultati con l'ultima strategia e nel simulatore, vedendo però le proprie prestazioni notevolmente ridotte quando si è confrontato con la versione originale del gioco.

Se siete riusciti ad arrivare fino a qui, ecco che allora possiamo ritornare a concentrarci sulla mostra, che ha proposto anche alcune interessanti chicche, come ad esempio l'allestimento, nell'ultima delle tre sale messe a disposizione, di quattro tavoli con altrettanti giochi, che sembra abbiano avuto un discreto successo (uno in particolare, un tale Larry o qualcosa del genere).

Altra piacevole sorpresa è vedere, appese alle pareti, una serie di opere d'arte ispirate ai videogiochi

e, soprattutto nell'ultima sala, una serie di cartoline realizzate da nerd sparsi in giro per il mondo e ispirate ai videogiochi e all'informatica in generale che hanno partecipato al contest di mail art indetto per l'occasione dai ragazzi di verdebinario, gli organizzatori della mostra.

Prima di lasciarvi alla galleria completa, però, vi propongo un'ultima immagine

Nella foto qui sopra potete vedere il primo videogioco in assoluto, una sorta di strategico ispirato a Star Trek dove bisogna spostarsi nello spazio a bordo della Enterpirese, rappresentata a schermo da una E, cercando di evitaree possibilmente distruggere i vascelli Klingon che viaggiano in giro per il rettangolo di gioco. Il gioco è stato scritto da Mike Mayfield ai tempi in cui si trovava alla sede di Irvine dell'Università della California (1971), per poi farlo girare sui computer della HP (con il permesso dell'azienda), che aveva iniziato a frequentare. Il gioco, nella mostra, viene fatto girare su uno dei primi Apple.
L'ultimo pezzo della mostra, però, è un assente, in un certo senso, anche se poco aveva a che fare con il tema video-ludico della mostra stessa. Sto parlando del primo personal computer in senso stretto, quel Programma 101, realizzato e progettato in Italia, di cui ha brevemente raccontato la storia Lucia.

(1) Chad Birch, Understanding Pac-Man Ghost Behavior (via Slashdot)
(2) Robles, D., Lucas, S.M. (2009). A simple tree search method for playing Ms. Pac-Man Computational Intelligence and Games, 2009. CIG 2009. IEEE Symposium on, 249-255 DOI: 10.1109/CIG.2009.5286469 (pdf)
(3) Wittkamp, M., Barone, L., Hingston, P. (2008). Using NEAT for continuous adaptation and teamwork formation in Pacman Computational Intelligence and Games, 2008. CIG '08. IEEE Symposium On , 234-242 DOI: 10.1109/CIG.2008.5035645 (pdf)
(4) Kenneth O. Stanley, Risto Miikkulainen (2002). Evolving Neural Networks Through Augmenting Topologies. Evolutionary Computation 10 (2): 99–127 (pdf)
(5) G. Yannakakis, J. Hallam, “Evolving opponents for interesting interactive computer games,” in Proceedings of the 8th International Conference on the Simulation of Adaptive Behavior (SAB'04); From Animals to Animats 8. MIT Press, 2004, pp. 499-–508
(6) La versione di Chow è programmata in Java, esiste però una versione in HTML5 dove si possono progettare e giocare i propri labirinti, a patto di avere un account facebook.