Vacanze da informatico

Intanto Buone Feste a tutti! Purtroppo sono rimasto indietro col gli aggiornamenti del blog, ma è stato un periodo abbastanza intenso (e non prevedo miglioramenti nel prossimo futuro): quando ci sono progetti universitari tra le "scatole" non è mai vera vacanza.

Comunque non voglio lasciarvi senza un augurio di Buone Feste e senza scrivere qualcosa su quanto sto combinando (cercando di non scadere nei tecnicismi, visto che il blog non lo scrivo per leggermelo da solo... in teoria).

La "postazione" da lavoro

Il mio assistente marsupiale

Il labirinto dell'intelligenza, ovvero l'intelligenza nel labirinto
L'11 maggio del 1997 a New York è accaduto qualcosa di inaspettato: un computer (Deep Blue) ha battuto il campione mondiale di scacchi Garry Kasparov che nell'occasione arrivò ad affermare "Sentivo--subodoravo--un nuovo tipo di intelligenza, aldilà del tavolo": Per la prima volta la fantasia e l'inventiva umane sono state mandate a farsi friggere sotto gli occhi di un mondo stupito. Ma un computer è capace di intelligenza? Potrà mai esserlo? Belle domande, per ora neanche sappiamo cosa effettivamente sia, l'intelligenza. In compenso, possiamo tentare di definire il comportamento razionale come il comportamento che ci permette di ottenere il miglior risultato o, in situazioni di incertezza, il miglior risultato atteso. Cosa sia il "miglior" risultato dipende dal problema che si vuole risolvere: per Deep Blue è stato trovare una sequenza di mosse di scacchi in grado di battere Kasparov.
Ma come si fa a trovare una sequenza vincente di mosse? Beh, per quanto gli scacchi siano un gioco nobile e complicato, sono anche un gioco determinato, ovvero per ogni situazione che si può presentare esiste almeno una strategia vincente per uno dei giocatori (negli scacchi esiste il pareggio, ma possiamo "piegare" le regole definendolo una forma di vittoria). Cosa ne deduciamo? Che per trovare una strategia vincente è sufficiente (in linea teorica) provare tutte le possibili combinazioni di mosse (e relative contromosse). Peccato che siano tante (ma proprio TANTE) combinazioni: troppe per la velocità e la memoria di un calcolatore odierno. Bisogna usare delle scorciatoie!
Visto che il problema degli scacchi è troppo complicato per un articolo di un blog come questo (e comunque, anche per me) porterò un esempio molto più semplice con il quale molti avranno familiarità: la soluzione di labirinti. Roba da Settimana Enigmistica!

Un povero eremita miope si è perso in un labirinto e sta cercando di uscirne (trovare una motivazione valida per cui l'eremita è finito nel labirinto è lasciato come esercizio al lettore). Il poverino ha anche perso i suoi occhiali e quindi non vede che a pochi passi da sé. Una brutta situazione, ma se ne può uscire.

Se l'eremita non conosce assolutamente nulla del labirinto una soluzione può essere quella di fare un passo in una zona inesplorata di una strada, segnarsi dov'è arrivato (su un pezzo di carta, o altro), tornare indietro, fare un passo nella strada successiva, segnare, tornare indietro... e continuare così fino a che non trova l'uscita. Chiaramente l'eremita sarà obbligato a fare delle gran corse e a perdere un sacco di tempo nella ricerca, ma questo approccio garantisce che se la soluzione esiste verrà immancabilmente trovata e che questa sarà la soluzione migliore, ovvero il percorso più breve dal punto di partenza all'uscita. Questa tecnica si chiama ricerca in ampiezza e non presuppone alcun tipo di conoscenza preesistente (una ricerca non informata) del labirinto per trovare una soluzione. Questo video dovrebbe chiarirvi le idee...

(Guardate il video in alta qualità per godervi la meravigliosa grafica che ho disegnato a mano! :-P)

I blocchi rosso scuro rappresentano i pezzi di strada già esaminati, quelli rosso chiaro sono "in lista" per essere esaminati. Vedrete che il povero eremita si guarda tutto il labirinto prima di trovare l'uscita: questo approccio è lento e dispendioso in termini di memoria (al punto di essere totalmente inapplicabile per problemi di dimensione maggiore). Naturalmente esistono altri algoritmi per la ricerca non informata ma stare a presentarli tutti diventerebbe inutilmente noioso. Vi descrivo invece un secondo tipo di approccio: quello della ricerca informata. Supponiamo che il nostro eremita sia anche uno spilungone in grado di sbirciare oltre i muri del labirinto con un cannocchiale e che grazie a questo vantaggio sia in grado di stimare la distanza tra una posizione e l'uscita, e anche quanti muri stanno tra l'uscita e la relativa posizione. Questa conoscenza è fornita da una cosiddetta funzione euristica, ovvero una funzione che fornisce per ogni possibile azione una stima della "distanza" tra il risultato di questa e la nostra destinazione. Per costruire una funzione euristica è necessaria almeno una conoscenza approssimata del problema (ad esempio la capacità di stimare la distanza e il numero dei muri da superare). Questo tipo di ricerca in genere risparmia molto tempo e memoria durante la risoluzione del problema (dipendentemente dalla qualità dell'euristica, ovvero la vicinanza tra il valore stimato e quello reale), ritardando la ricerca per strade poco promettenti. Però è possibile che la soluzione trovata non sia ottima (per i curiosi: l'algoritmo A* sta usando un'euristica non consistente), ovvero che la strada sia una deviazione più lunga. Ecco un video con la risoluzione implementata tramite la semplice euristica descritta qui sopra...

Vedete che non sono state provate tutte le soluzioni, risparmiando tempo e memoria, però il percorso è diverso (e più lungo) di quello trovato in precedenza.

Ecco, ora che abbiamo aiutato l'eremita a fuggire vi posso direi che i due video sono tratti da un programma risolutore di labirinti che ho scritto come piccolo progettino per un corso, uno dei modi per impiegare le vacanze.

Memory vocale

Il progetto successivo è l'implementazione del gioco di Memory... con comandi vocali (infatti è per il corso di Elaborazione del Linguaggio Naturale). Per ora sto ancora disegnando la grafica del gioco:

Ecco alcune delle tessere... disegnate rigorosamente in grafica EGA a 16 colori, stile 1989!

uzebox!
E per finire... ho ordinato i componenti e mi sono costruito una uzebox: una piccola console programmabile dal carattere minimalista (un solo integrato, 28mhz e 4kb di RAM! Circa 1000000 volte meno di quella che trovate su un comune PC da supermercato). Sto già progettando il primo giochino da programmare per questo affarino!

La mia uzebox

Vabbè, spero di non avervi annoiato troppo! Buone Feste a tutti!