L’evoluzione dell’I.A. nei giochi e videogiochi – Parte II

Nello scorso articolo è stata affrontata l’evoluzione dell’I.A. a partire dai giochi classici ed è stato illustrato a grandi linee uno dei paradigmi più usati nello sviluppo dei videogiochi per la programmazione degli NPC, gli alberi di comportamento. Essi tuttavia appartengono a una fase già avanzata della giovane storia delle I.A. applicate ai videogiochi, per cui è necessario fare qualche passo indietro.

Tutto (circa) secondo copione

Tra i primissimi videogiochi della storia che proponessero una modalità a singolo giocatore possiamo sicuramente annoverare gli arcade spaziali come Space Invaders (1978) o Galaxian (1979). Lo schema era semplicissimo, in linea con le risorse computazionali delle macchine dell’epoca: si manovra una navicella che deve sparare ad altre navicelle che seguono o tracciati fissi tra le tile dello sfondo oppure traiettorie pseudocasuali. Questi movimenti dei nemici sono tutti descritti in porzioni di codice dedicati chiamati script (copioni): gli elementi comandati dalla CPU si comportano seguendo passo passo le istruzioni, come se fosse appunto un copione da recitare. Considerare “intelligente” una serie di comandi fissi potrebbe sembrare strano, ma a tutti gli effetti gli script sono i primi archetipi delle I.A. così come conosciute oggi. Inoltre sono ancora ampiamente utilizzati oggi, con svariate migliorie rispetto al passato, per un’ampia di generi videoludici, dagli adventure ai platform fino ai giochi di ruolo.

Gli script a livello di codice sono strutturalmente composti come blocchi if-then/else-then: se si verifica una condizione allora si effettua un’azione, altrimenti se si verifica una condizione diversa allora si effettua un’altra azione, e così via. Le condizioni possono essere diverse, che vanno da quella iniziale di spawn dell’elemento di gioco, a una semplice timer che appena scaduto risolve l’azione da far compiere all’elemento (come le navicelle di Galaxian, che ad intervalli di tempo regolari si staccano dalla formazione). Un’altra tipologia di condizione molto usata è quella pseudocasuale, che conferisce all’elemento di gioco una varietà nel suo pattern di attacco, in teoria non predicibile a priori da parte del giocatore (andrebbe conosciuta la procedura utilizzata dal generatore pseudocasuale); questa condizione, che semplicemente fa scegliere “a caso” uno tra i vari attacchi effettuabili, è molto usata per i nemici durante le battaglie a turni nei classici giochi di ruolo giapponesi, come i vari Dragon Quest e Final Fantasy.

Un primo tangibile comportamento “intelligente” di I.A. scriptate nei videogiochi si è riscontrato all’uscita dei due primi episodi della saga di Metal Gear: in Metal Gear (1987) i vari nemici al momento del loro spawn a schermo effettuano un pattugliamento dell’area su una traiettoria prefissata, ma si allertano appena sentono uno sparo oppure se scovano Snake nella linea retta di vista, definita dalla stessa ascissa o ordinata (a seconda della direzione del pattugliamento) in cui in quel momento si trova il nemico, per poi inseguirlo e attaccarlo. In Metal Gear 2: Solid Snake (1990) è stato implementato invece per i nemici un “cono visivo” a 45° anziché una semplice linea retta per cercare di scovare Snake, oltre ad avere una maggiore sensibilità ai rumori di fondo e la facoltà di inseguire Snake per oltre una schermata. Questo paradigma di programmazione di script per I.A., poi utilizzato e migliorato ad esempio per molti altri FPS come GoldenEye 007 (1997) e Unreal Tournament (1999, per la modalità single player) e per i primi veri stealth come Thief: The Dark Project (1998), è detto situazionale, poiché sono le situazioni che si configurano durante le fasi a essere appunto le condizioni di verifica.

Un paradigma simile per le I.A. scriptate è quello caratteriale: è simile a quello situazionale, ma in questo caso le condizioni da verificare si basano su alcune peculiarità dell’elemento di gioco a cui si associa lo script. Ad esempio in Doom (1993) i nemici variano la loro aggressività in base alla loro natura e al loro stato di salute. In generale l’utilizzo dello script favorisce la semplicità nello sviluppo e la giocabilità in generale, mentre ha il difetto di essere predicibile dal giocatore dopo un certo tempo di gioco, perdendo quindi in termini di tasso di sfida.

Gli script sono anche molto utilizzati nei videogiochi di ruolo per la programmazione degli NPC alleati del giocatore, a cui spesso veniva data la facoltà nel gioco di modularla a piacimento attraverso scelte di azioni predefinite da far compiere ai propri compagni gestiti dalle I.A., in una specie di programmazione a oggetti semplificata. Il primo titolo famoso a utilizzare questo paradigma fu Dragon Quest IV (1990) con il comando delle tattiche, ma si possono citare tranquillamente Phantasy Star IV (1993), Secret of Mana (1993), Star Ocean (1996) e altri titoli più recenti come Final Fantasy XII (2006) con il suo gambit system e la saga di Dragon Age.

Nient’altro che macchine che girano in tondo

La classica struttura condizione-azione tipica della programmazione imperativa può essere vista come un primitivo stadio di comportamento intelligente di una macchina. In particolare, è possibile logicamente parlando passare a un livello successivo a partire dalla I.A. situazionale: anziché formulare ogni volta la verifica della condizione necessaria, è possibile mantenere la stessa azione fino a quando non si verifica una condizione diversa. Si introduce quindi il concetto di stato in cui la I.A. persiste fino a quando non variano le condizioni. Il modello scolastico che viene utilizzato è quello dell’automa a stati finiti o in breve FSA: come intuibile dal nome, essa è composta un numero definito di stati e da un insieme di funzioni di transizione che le permettono di cambiare stato a seconda dei valori in ingresso che riceve e dallo stato corrente, generando relative uscite (movimenti, attacchi, difese, etc.). Solitamente le FSA vengono raffigurate come dei grafi orientati, con gli stati come cerchi (dai quali si identifica quello iniziale, per convenzione cerchiato due volte) e le transizioni come frecce. L’utilizzo delle FSA per la progettazione di I.A. nei videogiochi è pratica estremamente comune, nonché molto “antica”. Un esempio?

Proprio così: i fantasmini in Pac-Man (1980) sono “animati” da semplici FSA. La potenza delle FSA è nella loro massima riusabilità per la programmazione di I.A. di elementi diversi tra loro, mantenendo lo schema di base e diversificando solo alcune particolari azioni; al contrario script uguali possono essere utilizzati solo per una particolare tipologia di elemento. Continuando l’esempio di Pac-Man, tutti e quattro i fantasmini utilizzano la stessa FSA, variando solo nel modo in cui cercano di acciuffare Pac-Man: il rosso lo insegue, il rosa cerca di tagliargli la strada, il celeste tenta imboscate e l’arancione vaga “a caso” per la mappa. Questa variazione nel comportamento è implementata con le stesse identiche funzioni, con la sola differenza del valore assegnato alla variabile della target tile verso cui il movimento del singolo fantasmino viene direzionato: in particolare per il rosso la target tile è quella in cui si trova Pac-Man al momento, per il rosa è quella quattro volte avanti sulla direttrice di Pac-Man, per il celeste è basata su una media delle due precedenti ma su entrambi le direttrici e per l’arancione è scelta “a caso” nel quadrante della mappa in cui si trova in quel momento Pac-Man (a distanza euclidea di otto tile da Pac-Man).

Le FSA sono state largamente utilizzate per lo sviluppo delle I.A. dei nemici nei videogiochi degli anni Ottanta e Novanta, in particolare nelle ormai storiche saghe di platform come Super Mario, Kirby e Spyro, e di FPS quali Battlefield, Call of Duty e Perfect Dark. Un’altra saga storica dove l’utilizzo delle FSA fu molto marcato è Tomb Raider: già dal primo capitolo (1996) è possibile notare che i diversi comportamenti degli animali selvatici variano a seconda dell’ambiente, della natura dell’animale (una tigre era più irruenta nei movimenti rispetto a un orso, ad esempio) e della presenza o meno di altri elementi, come i lupi con i loro attacchi in piccoli branchi. Anche negli RTS della prima ora come Civilization (1991), Dune II (1992) o Warcraft: Orcs and Humans (1994) il comportamento delle civiltà nemiche era gestito da FSA; lo sviluppo di questo genere poi vide l’abbandono delle FSA e il passaggio agli alberi di comportamento descritti nello scorso articolo, con l’introduzione anche di una facoltà di apprendimento trial and error come in Total War: Rome II (2013), possibile attraverso un’esplorazione dell’albero “a pezzi”, tenendo traccia delle soluzioni finali delle sottoparti all’inizio ritenute migliori per la I.A., ma sempre pronte a essere aggiornate se l’analisi di un’altra sottoparte giunga a un risultato più proficuo. Questi alberi di ricerca sono detti Monte Carlo o in breve MCST (Monte Carlo Search Tree), poiché applicano il metodo Monte Carlo, nativamente pensato per il calcolo combinatorio e statistico, ad algoritmi di ricerca su albero.

Iniziare ad adattarsi (e a imparare)

Script, FSA e alberi di comportamento in linea generale sono applicazioni di I.A. debole che prevedono soltanto la ricerca di una soluzione di un problema già modellato a monte e in generale non mutevole poiché implementato in codice sorgente; alcuni raffinamenti di questi paradigmi includono un primitivo sistema di apprendimento dalle azioni in corso da parte del giocatore tramite l’utilizzo di variabili flag che tengono traccia delle conseguenze di alcune scelte di gioco pregresse effettuate dal giocatore.

L’apprendimento automatico (in inglese machine learning) dalle proprie azioni pregresse (e nel caso delle I.A. ludiche anche di quelle dell’avversario) è una delle storiche sfide di tutta la scienza alla base dell’I.A.. In generale si differenzia tra apprendimento supervisionato, ovvero con una serie di input particolari dati “in pasto” alla I.A. da cui deve ricavare output già noti, per poi confrontare i risultati al fine di correggere errori di computazione degli output stessi, oppure non supervisionato, con quindi piena autonomia data alla I.A. sul discernere le informazioni che necessita dagli input ambientali forniti (come fanno oggi gli automi a reti neurali alla frontiera della ricerca in questo campo). Solitamente nei giochi si applica un approccio basato su rinforzo: a partire dagli input ricevuti, una I.A. con apprendimento a rinforzo etichetta gli output e gli stati in cui si trova in base a un valore, di stato o d’azione, ricavato attraverso una funzione matematica definita (ad esempio una media regressiva) detta tecnica di rinforzo. Più è alto (o basso, dipende dal campo d’applicazione) il valore, più l’azione è proficua per la I.A. in quel particolare stato.

L’apprendimento basato su rinforzo è un paradigma utilizzato per quello che in teoria dei sistemi complessi è detto comportamento emergente, ossia quel comportamento con proprietà totali più dettagliate rispetto alla sola somma delle proprietà delle singole parti. Questo paradigma è stato largamente utilizzato in quel particolare sottogenere di gestionali chiamati simulatori di vita, nel quale il giocatore controlla una o più forme di vita artificiale e ne governa le evoluzioni fisiche e le interazioni sociali. Il primo titolo in cui è stato implementato è Creatures (1996), ma venne in seguito portato a risultati convincenti nelle due serie videoludiche Black & White e The Sims della Electronic Arts. Un’applicazione diversa ma non meno interessante dell’apprendimento delle I.A. è da ricercare in alcuni esperimenti poco noti al grande pubblico di storie interattive, nei quali il giocatore deve interagire con gli elementi del gioco attraverso comandi testuali in linguaggio comune, poi interpretati dalla stessa I.A. attraverso motori inferenziali. Il “meno ignoto” tra questi particolari titoli è Façade (2005), dove il giocatore è a interagire con due I.A. che nel “gioco” impersonano una coppia che sta attraversando un periodo di crisi coniugale. Ciò che il giocatore dirà o farà all’interno dell’ambiente di gioco, l’appartamento dei due, porterà ai finali più disparati, dal rappacificamento tra i due alla loro rottura definitiva, ma potrà anche, ad esempio, portare al tradimento uno dei due (dipende dal sesso scelto dal giocatore in partenza) con il nostro alter ego.

Una tipologia di I.A. capace di apprendere applicata a problemi più specifici è quella che implementa un algoritmo di pathfinding. Nell’accezione più generale, il pathfinding (ricerca di cammino) è un classico problema dell’informatica: dato un ambiente modellato secondo un grafo orientato e pesato, cioè con i collegamenti caratterizzati da un valore numero (ad esempio, per uno stradario possono essere i chilometri di strada che bisogna percorrere per arrivare da una città alla seguente), a partire da un nodo di partenza bisogna cercare il cammino, inteso come sequenza di nodi intermedi, che porti ad un nodo destinazione secondo una politica definita (cammino più breve, meno oneroso, che aggiri eventuali ostacoli, etc.). Gli algoritmi di pathfinding, tra cui il più comune è l’A* (si legge a star), basato su una stima euristica di costo di cammino, applicano un apprendimento semplice per tenere traccia dei cammini intermedi e della frontiera di nodi tra cui scegliere il seguente. Il pathfinding nei videogiochi viene utilizzato sovente in parallelo con gli alberi di comportamento: per ogni azione preferibile al momento scelta dell’I.A. nell’albero, l’algoritmo di pathfinding poi ha il compito di ricercare il punto all’interno dell’ambiente di gioco più congeniale per tale azione. La combinazione dei due paradigmi rappresenta probabilmente il risultato più convincente mai visto da un’I.A. applicata ai videogiochi: è possibile citare ad esempio le saghe FPS F.E.A.R., Crysis e S.T.A.L.K.E.R., ma anche i bot di Starcraft II (2010) e Rocket League (2015) per la modalità single player.

Ulteriore paradigma da citare è il cosiddetto adattivo o a elastico (in inglese rubber band). Le I.A. a elastico sono programmate affinché gli elementi che governa si comportino in maniera differente a seconda del giocatore, adattandosi al suo stile di gioco e principalmente alla sua bravura. Sono ampiamente utilizzate nei videogiochi di corsa: in base alla posizione in gara e alle capacità di guida del giocatore, le auto governate dalle I.A. variano la loro velocità di punta o la loro capacità di tenere la corda in curva, così ad esempio se il giocatore è ai primi posti si troverà concorrenti più forti, mentre se è più attardato gli viene concessa possibilità di recuperare posizioni, come se appunto le automobili in gara fossero legate da un elastico che non può essere teso oltre un punto di rottura (ed è compito della I.A. far sì che non si raggiunga). Applicazioni delle I.A. a elastico si ritrovano nelle saghe di Gran Turismo, Forza Motorsport e Burnout, ma anche nei capitoli più recenti di Mario Kart. Le I.A. a elastico sono intensamente utilizzate non solo nei videogiochi di corsa, ma anche in quelli di simulazione sportiva o nei picchiaduro a incontri.

Da avversario a giocatore

Negli ultimi anni, data la direzione del mercato videoludico orientata verso le esperienze di gioco multi-giocatore online a discapito di quelle in single player, non si sta verificando un significativo sviluppo per quanto concerne le I.A. “avversarie” nei videogiochi, tangibile invece fino a circa un decennio fa. Inoltre la ricerca in questo ambito sta favorendo lo sviluppo delle reti neurali e della I.A. forte, a discapito degli altri paradigmi. Le reti neurali molto brevemente sono dei modelli matematici che cercano di emulare quanto più verosimilmente possibile il comportamento del cervello umano, composto da una moltitudine di neuroni estremamente interconnessi tra loro e con funzionalità bioelettriche diverse, durante l’apprendimento che ognuno di noi compie per effettuare un comportamento “intelligente”.

Le I.A. tuttavia vengono utilizzate in questo particolare periodo storico non tanto per far giocare altri utenti, ma per giocare loro stesse a videogiochi, per scopi di ricerca. Vengono utilizzati in questo ambito videogiochi arcade classici, quelli con l’unico scopo di massimizzare il punteggio finale, per lo stesso motivo per cui le I.A. prototipali sono state sviluppate a partire dai giochi classici, come detto nell’articolo precedente. Ad esempio da anni esiste un contest annuale mondiale per lo sviluppo di I.A. che giochino a Ms. Pac-Man (1981), sia come giocatore che come fantasmini. Notizia di poche settimane fa inoltre è la scoperta effettuata da una I.A. basata su algoritmo evolutivo sviluppata da un gruppo di ricerca dell’università di Friburgo di un bug all’interno del vecchio arcade Q*bert (1982) che permette di aumentare a dismisura il punteggio attraverso una serie di comandi all’inizio incomprensibili (basta vedere il video poco sopra, la I.A. deliberatamente perde due vite ed effettua passaggi ripetuti in caselle già marcate) e soprattutto impensabili da effettuare per un giocatore umano.