Simulazione e AI sono oggi parole chiave nel gergo informatico e nelle chiavi di ricerca dei profiler. Vediamo come applicare tali concetti al RaspberryPI.

Ricordo ancora con piacere le lezioni universitarie dei professori Vittorio Somenzi e Domenico Parisi su epistemologia della conoscenza e rappresentazione della realtà. In particolare la definizione di  “senso dell’Io” di Parisi, che influenza il concetto stesso di coscienza depotenziando il paradosso nichilista della realtà come cervello in scatola.

Era il periodo dello scontro aperto tra neuroscienziati e cognitivisti, tra olismo fisiologico e connettivismo logico. E tutto il loro lavoro, a causa delle sempre maggiori capacità di calcolo dei computer odierni, “sta scomparendo tristemente come lacrime nella pioggia”. Paradossalmente, si vorrebbe far passare il computer come un’intelligenza in grado di pensare per proprio conto, dimenticando che un computer non è altro che un completo idiota in grado di contare molto velocemente.

Niente test di Turing, quindi, almeno sin quando un elaboratore elettronico non sarà in grado di percepire una realtà intima e metterla in contrapposizione con la realtà fisica mutuata dai propri sensori esterni. Ma come la mettiamo con la simulazione?

Se proprio non riesci a comportarti da individuo intelligente, almeno fai finta di esserlo

Questa frase viene costantemente ripetuta da genitori esasperati ai propri figli un po’ distratti e un po’ discoli, e contiene una grande verità. Il test di Turing è esattamente questo: un gioco delle parti in cui uno degli attori deve fingere di essere qualcosa che in realtà non è, sino a convincere l’interlocutore. Esiste dunque una fondamentale differenza tra intelligenza simulata e intelligenza effettiva.

Una simulazione è sostanzialmente un algoritmo logico eseguito da un attore per rappresentare una situazione specifica: quanto più l’algoritmo è preciso e ricco di particolari, tanto più la simulazione risulta credibile. Ed è appunto nelle simulazioni che il nostro computer eccelle: quando si tratta di scegliere tra milioni di opzioni possibili un comportamento che conduca ad un risultato positivo. La moderna AI, dal machine learning alle simulazioni complete in deep learning, non è altro che la ripetizione continua e instancabile di miliardi di test di tipo if…then…else.

Questo concetto vale a maggior forza nella Teoria dei Giochi, dove paradossalmente al computer è vietato “barare”, ma è consentito utilizzare euristiche per abbattere la complessità computazionale richiesta dalle scelte. Lo stesso IBM Deep Blue, il computer in grado di battere i campioni mondiali umani di scacchi, funzionava in base alla scelta di posizioni dei pezzi sulla scacchiera, mediata dal valore che ciascuna posizione avrebbe avuto nello svolgimento della partita, e valutata sino ad un livello definito (e finito) di profondità per evitare una esplosione combinatoria delle scelte.

Il concetto è molto meno complesso di quanto appaia: come vedremo più avanti, anch’esso si basa su di una serie di if…then.

Ma iniziamo dalle basi. Vedremo di seguito un paio di semplici giochi di simulazione, ne analizzeremo la logica e scriveremo un algoritmo per utilizzare il nostro Raspberry PI come giocatore “consapevole” e non solo come arbitro. Vedremo quanto conti l’analisi della strategia vincente e l’utilizzo delle esperienze precedenti. Infine daremo un’occhiata all’algoritmo minimax, alla base di tutti i programmi di simulazione informatica che si rispettino.

Le versioni di Marienbad

Marienbad è nato in Polonia nel 1962, come gioco per mainframe creato da Witold Podgórski, un ingegnere della Elwro residente a Wrocław, per il proprio Odra 1003. Si trattava di una versione particolare del gioco di logica nim. Ispirato dalla discussione sul periodico Przekrój riguardo ad una variante del nim apparsa nel film del 1961  Last Year at Marienbad (L’Année dernière à Marienbad), e chiamato per l’appunto “Marienbad” dall’editore, Podgórski programmò il gioco su di un mainframe 1003 in sviluppo. Nel gioco, due avversari di fronteggiano al computer, alternando mosse di rimozione di fiammiferi posti in una struttura specifica. Il giocatore che resta con l’ultimo fiammifero perde.

Occorre notare che il gioco è stato analizzato completamente in tutte le mosse possibili, e chi gioca per secondo ha in genere sempre la possibilità di vincere. Si trata di un cosiddetto “gioco ingiusto” (unfair game), in quanto la possibilità di vittoria non è equidistribuita tra i giocatori, ma dipende da chi gioca per primo.

In questo articolo presenteremo una versione di Marienbad con i giocatori che potranno scegliere 1, 2, 3 o 4 fiammiferi.

Già da una analisi superficiale risulta evidente la strategia vincente: con 16 fiammiferi sul tavolo occorre pensare modulo cinque per lasciarne uno sul tavolo. Pertanto qualunque sia la scelta del primo giocatore (1, 2, 3 o 4), basterà scegliere il valore complementare (ovvero 4, 3, 2 o 1) necessario che, sommato alla scelta del primo giocatore, raggiunga 5. Togliendo 5 fiammiferfi a turno di gioco dal tavolo, il primo giocatore resterà necessariamente con l’ultimo fiammifero in mano.

In questo caso la strategia è particolarmente semplice. Non ci occorrono mappe di riferimento o regressioni per valutare volta per volta la soluzione ottimale, dal momento che le mosse sono imposte. Siamo di fronte ad uno di quei casi in cui riflettere prima di parlare consente di risparmiare tempo e denaro.

Pari o dispari?

Un gioco in apparenza altrettanto semplice da implementare è il gicoo del pari e dispari.
Il programma presentato è una di quelle pesti che vincono contro l’uomo. Ha una strategia, per quanto superficiale, e può risultare interessante proprio per questo.
In sostanza il programma mantiene una matrice tetradimensionale delle ultime uscite (pari o dispari), e gioca quella più frequente, partendo dal presupposto che le azioni umane sono di solito abbastanza simili tra loro. Se il giocatore non pone la massima attenzione a non ripetere le sequenze di uscita di zero (pari) e di uno (dispari) si trovera’ ben presto a dover recuperare punti su punti.

Il programma non usa trucchi o liste o alberi, ed e’ di una semplicita’ disarmante.

In realtà, la differenza fondamentale tra questo gioco ed il precedente consiste nel fatto che il pari e dispari è un gioco a somma zero. In teoria dei giochi un gioco a somma zero descrive una situazione in cui il guadagno o la perdita di un partecipante è perfettamente bilanciato da una perdita o un guadagno di un altro partecipante in una somma uguale e opposta. Ciò che cambia, invece, è il concetto di variabilità, o randomness, implicito nella scelta del giocatore. Vediamo un esempio.

Potrei giocare alternando pari o dispari, ma in questo caso la sequenza sarebbe predicibile, e non random.

Oppure potrei giocare sempre lo stesso valore, per rendere il gioco più imprevedibile. Ma anche in questo caso la sequenza sarebbe facilmente riconoscibile, e l’avversario potrebbe agire di conseguenza.

Infine, potrei cercare di rendere la sequenza di uscite il più variata possibile. Ma, anche in questo caso, un computer avrà facilmente campo libero nell’interpretare la sequenza, trovandovi un pattern riconoscibile anche dove io, povero umano, non ne vedo.

Se non ci credete, il codice riportato di seguito servirà da esempio.

Provate il programma, e confrontatevi con questa piccola ma efficace Intelligenza Artificiale! Confrontando il pattern delle ultime giocate, il programma riconoscerà quali sono le “variazioni” da voi preferite.

L’algoritmo Minimax

In un certo senso, il programma precedente cerca di massimizzare le probabilità di successo analizzando il peso delle ultime uscite, vale a dire quali sono i pattern più comuni, ed imposterà scelte che lo renderanno vincitore in caso di ripetizione.

Il minimax, nella teoria delle decisioni, è un metodo per minimizzare la massima (minimax) perdita possibile; in alternativa, per massimizzare il minimo guadagno (maximin). Fu scoperto nella teoria dei giochi in caso di gioco a somma zero con due giocatori, sia nel caso di mosse alternative (turni) sia di mosse simultanee, venendo successivamente esteso a giochi più complessi e al supporto decisionale in presenza di incertezza.

Una versione semplice dell’algoritmo si può vedere in giochi come il tris (o TicTacToe), dove è possibile vincere, perdere o pareggiare.

• Se il giocatore A può vincere con una sola mossa, la mossa migliore è quella vincente.
• Se il giocatore B sa che una data mossa porterà A a poter vincere con la sua prossima mossa, mentre un’altra lo porterà a pareggiare, la migliore mossa del giocatore B è quella che lo porterà alla patta.

Verso la fine del gioco è facile capire quali sono le mosse migliori; l’algoritmo minimax trova la mossa migliore in un dato momento cercandola a partire dalla fine del gioco e risalendo verso la situazione corrente. Ad ogni passo l’algoritmo assume che il giocatore A cerchi di massimizzare le sue probabilità di vincere, mentre B cerchi di minimizzare le probabilità di vittoria di A, per esempio massimizzando le proprie chance di vittoria.

Tratteremo diffusamente l’algoritmo minimax, le sue estensioni (o potatura dell’albero delle decisioni) e le euristiche applicabili per rendere il problema della scelta della soluzione ottimale trattabile, in un prossimo articolo. L’argomento è infatti piuttosto complesso, e può applicarsi tanto alla soluzione di giochi semplici come il tris, quanto alla soluzione di problemi relativi al gioco degli scacchi. Mentre però la tabella delle scelte possiili nel tris assomma a 360.000 opzioni diverse (pari a 9! o 9 fattoriale) negli scacchi abbiamo oltre 10⁴⁰ posizioni differenti da valutare (10.000 miliardi di miliardi di miliardi di miliardi di posizioni). È evidente come, data la complessità di situazioni simili, sia d’obbligo ricorrere ad euristiche che consentano di ridurre al minimo l’esplosione combinatoria delle soluzioni.

Conclusioni

Per questa volta abbiamo concluso. L’indice che compare sul titolo dichiara comunque che avremo altre puntate relative all’analisi di sistemi informatici che simulano le scelte umane. Il materiale a nostra disposizione è davvero molto, sia a livello di esempi di codice (boardgames, griglie e scacchiere, automi cellulari e così via), sia a livello di presentazione grafica, sia a livello di algoritmi (ottimizzazioni, ricorsione e backtracking, potatura alfa-beta). E il tutto è predisposto per poter essere utilizzato sui nostri computer su scheda, quindi con esigenze di sistema ridotte ai minimi termini.

Ovviamente, se avete programmi da presentare, idee da proporre o curiosità da sviscerare, relative a simulazione o AI su RaspberryPI, potete contattarci. Le idee migliori potranno vedere la luce su queste pagine.

Vi aspetto quindi numerosi e interessati. Alla prossima!