Introduzione 3
ricerca universitaria. È importante notare come esistano sul mercato
svariati strumenti per lo sviluppo dei video games e delle relative
applicazioni di AI3, strumenti di cui è possibile effettuare la seguente
classificazione, certo non completamente esaustiva:
• Ambienti di modellazione4, rendering e animazione: Maya,
3D Studio Max e SoftImage sono forse gli esempi più noti (per la
creazione di grafica ed animazione 3D);
• Librerie di programmazione: vengono fornite API relative ad un
particolare linguaggio di programmazione e compilate per un ben
determinato sistema operativo. Costituiscono le basi sulle quali
può essere realizzata, a partire da zero, un'applicazione di grafica
3D.
• Metalinguaggi: la modellazione della scena 3D e la gestione degli
eventi ad essa associati, avviene attraverso un linguaggio
descrittivo (un esempio è VRML).
• Piattaforme per l’implementazione di tecniche di intelligenza
artificiale: giochi come Quake, Half-Life, Unreal forniscono la
possibilità di programmare il comportamento dei propri
personaggi all’interno del gioco.
Volendo disporre del massimo controllo sul risultato finale, sia in
termini di specifiche che di prestazioni, si ricorre all'uso di un linguaggio
di programmazione, solitamente C o C++. Questo approccio è quello
normalmente seguito nella realizzazione di videogiochi e di applicazioni
di AI. Nel caso specifico di videogiochi 3D, le librerie utilizzate prendono
il nome di motori 3D (dall'inglese 3D engines).
Il mio lavoro di tesi si pone come obiettivo, tra gli altri, quello a mio
parere fondamentale di gettare le basi per un intreccio sempre più stretto
3
Da questo momento si utilizzerà la notazione AI per indicare Intelligenza Artificiale (dall’inglese
Artificial Intelligence).
4
Il processo con cui viene descritta una scena 3D.
Introduzione 4
e sempre più concreto tra i risultati della ricerca scientifica ed il lavoro
svolto dai programmatori che sfruttano le teorie e tecniche proposte per
realizzare automi ben funzionanti, similmente umani e non, nei propri
giochi. Tale sinergia, sicuramente già in parte esistente, va ampliata per
migliorare la qualità delle simulazioni disponibili nei giochi. Per questo
motivo, mi propongo di studiare quali sono le principali tecniche, già
adottate o ancora in via di sperimentazione, per inserire l’AI nei
computer games (attraverso i sopraccitati motori 3D) ed i loro possibili
sviluppi.
La prima parte del lavoro è molto teorica e prende in considerazione,
tra i vari argomenti, anche il rapporto molto stretto tra il mondo dell’AI e
quello dell’intrattenimento; in seguito, invece si prosegue nella ricerca di
una piattaforma di sviluppo adatta alla creazione di una applicazione
funzionante. A questo scopo è stata utilizzata una struttura che permette
di applicare tecniche di AI nei computer games, denominata FlexBot,
realizzata da alcuni ricercatori della Northwestern University utilizzando
il software di sviluppo messo a disposizione dal gioco Half-Life della
Valve Studios.
Il lavoro di tesi si è quindi concretizzato nella progettazione e
realizzazione di un modello comportamentale (behavior), il quale gestisce
nel modo più realistico possibile, attraverso regole prestabilite, le reazioni
di un NPC5 inserito all’interno del gioco Half-Life, in modalità
multiplayer6.
L’applicazione verrà ampiamente descritta nella parte finale della tesi.
5
Non Player Character (Personaggio non guidato dal giocatore. Entità nel gioco che non sono
controllate dall’utente).
6
Modalità di gioco tra più utenti connessi in rete, via internet o via LAN.
CAPITOLO 1
Intelligenza artificiale nei video
games
1.1. AI: Intelligenza Artificiale
6
L’intelligenza artificiale ha giocato un ruolo di importanza sempre
crescente per il successo o il fallimento di un gioco per computer. Si vuole
quindi, prima di tutto, analizzare l’uso dell’AI nei giochi, focalizzando
l’attenzione sulle difficoltà incontrate dagli sviluppatori per la loro
realizzazione e sulle tecniche che essi hanno sperimentato con successo,
per poi valutare il livello di collaborazione tra gli stessi e la comunità
accademica.
Inizialmente è indispensabile fornire una definizione appropriata di
cosa sia realmente l’intelligenza artificiale.
1.1 AI: Intelligenza Artificiale
Le più recenti definizioni di intelligenza artificiale possono essere
comprese in quattro categorie:
• Sistemi che pensano come gli esseri umani.
• Sistemi che pensano razionalmente.
• Sistemi che operano come gli esseri umani.
• Sistemi che agiscono razionalmente.
Le prime due categorie riguardano i processi del pensiero e del
ragionamento, mentre le ultime due si riferiscono al comportamento. La
prima e la terza misurano il successo in termini di prestazioni umane,
mentre le altre esprimono una misura rispetto ad un concetto ideale di
intelligenza che può essere denominato razionalità.
A questo punto è possibile individuare due definizioni per ogni categoria,
quindi per la prima:
“Il nuovo sforzo entusiasmante di far pensare i
computer…macchine con la mente, in senso completo e letterale”
(Haugeland, 1985)
1.1. AI: Intelligenza Artificiale
7
“[L’automazione di] attività che associamo al pensiero umano,
attività come prendere decisioni, risolvere problemi,
apprendere…” (Bellman, 1978)
per la seconda:
“Lo studio di facoltà mentali attraverso l’uso di modelli
computazionali” (Charniak e McDermott, 1985)
“Lo studio delle computazioni che rendono possibile percepire,
ragionare e agire” (Winston, 1992)
per la terza:
“L’arte di creare macchine che eseguono funzioni che richiedono
intelligenza se vengono eseguite da persone” (Kurzweil, 1990)
“Lo studio di come far fare ai computer delle cose che,
attualmente, le persone fanno meglio” (Rich e Knight, 1991)
infine, per la quarta:
“Un campo di studio che cerca di spiegare ed emulare un
comportamento intelligente in termini di processi
computazionali” (Schalkoff, 1990)
“Il ramo dell’informatica che si occupa di automatizzare un
comportamento intelligente” (Luger e Stubblefield, 1993)
Un sistema quindi è razionale se fa la cosa giusta e ci sono quattro
obiettivi possibili da perseguire in intelligenza artificiale. È possibile
1.2. Che cosa è un agente intelligente 8
notare in modo abbastanza evidente un contrasto tra gli approcci basati
sugli esseri umani e quelli basati sulla razionalità1. Infatti un approccio
basato sull’uomo deve costituire una scienza empirica che comporta
ipotesi e conferme sperimentali, un approccio razionalista, invece, è dato
da una combinazione di matematica ed ingegneria.
1.2 Che cosa è un agente intelligente
Si è accennato nel paragrafo precedente ad agenti predisposti a
compiere azioni intelligenti. Vogliamo ora spiegare in modo più
dettagliato cosa fa un agente intelligente e come si relaziona con
l’ambiente, passo fondamentale per capire il funzionamento
dell’applicazione riportata in seguito2, completamente basata sulla
programmazione del comportamento di un agente.
Un agente si configura come qualcosa in grado di percepire il proprio
ambiente attraverso dei sensori e di agire in quell’ambiente attraverso
degli attuatori.
Un agente umano è dotato di sensori quali ad esempio occhi, bocca,
orecchie e di attuatori quali le mani, le gambe, le braccia. Un agente
software invece possiede delle stringhe di bit codificate al posto delle
proprie percezioni ed azioni.
1
Bisogna precisare che nella distinzione tra comportamento umano e comportamento razionale,
non stiamo sostenendo che gli umani siano necessariamente “irrazionali” inteso come
“emotivamente instabili” o “pazzi”. Si osserva semplicemente che spesso commettiamo degli
errori; questo è fondamentale per capire come l’aggiunta di elementi di imprevedibilità, ad
esempio, in un automa basato su AI possa rendere il suo comportamento più simile a quello di
un essere umano.
2
Vedi cap. 3
1.2. Che cosa è un agente intelligente 9
Figura 1.1 - Gli agenti interagiscono con gli
ambienti per mezzo di sensori ed attuatori.
L’obiettivo finale di questa tesi sarà proprio quello di utilizzare i sensori
ed attuatori messi a disposizione dalla struttura FlexBot nel gioco Half-
Life per programmare e far agire secondo regole “intelligenti” un agente
(NPC).
1.2.1 Come dovrebbe agire un agente
Un agente razionale è quello che fa la cosa giusta. Ma quale è la cosa
giusta? Come prima approssimazione si può dire che la cosa giusta è
quella che provocherà all’agente maggior successo, ma ciò non elimina il
problema di decidere come e quando valutare il successo dell’agente.
Useremo il termine misura di prestazione per definire il come, termine
inteso come misura di prestazione oggettiva imposta da qualche autorità.
Possiamo considerare per esempio, il caso di un agente che si trova in una
1.2. Che cosa è un agente intelligente 10
stanza, dotato di un’arma da fuoco che deve sopravvivere uccidendo i suoi
nemici. Una misura di prestazione plausibile potrebbe essere la quantità
di nemici uccisi in un determinato arco di tempo, ovviamente questa
misura può essere complicata ulteriormente.
Per migliorare il comportamento dell’agente è importante anche tutto
ciò che esso apprende nel corso del suo itinerare nello spazio diegetico,
una specie di storia delle percezioni che può essere chiamata sequenza di
percezione. Ciò conduce ad una definizione di agente razionale
ideale: “Per ogni sequenza di percezione possibile, un agente razionale
ideale dovrebbe compiere qualsiasi azione che si aspetta massimizzare
la sua misura di prestazione, sulla base delle prove fornite dalla
sequenza di percezione e di qualsiasi conoscenza predefinita che abbia
l’agente” 3.
1.2.2 Struttura di un agente intelligente
Il compito dell’AI è quello di progettare il programma di un agente,
una funzione, cioè, che implementa il comportamento dell’agente dalle
percezioni alle azioni. Fondamentale per il progetto è l’architettura del
programma ovvero il meccanismo di calcolo attraverso il quale il
programma stesso verrà eseguito. L’architettura potrebbe essere un
semplice calcolatore , o potrebbe includere hardware specifico per
l’esecuzione di alcuni compiti, come elaborare le immagini di una
telecamera o filtrare degli input audio. Potrebbe altresì includere del
software che fornisce un livello di isolamento tra il calcolatore ed il
programma dell’agente, in modo da poter programmare ad un livello più
alto. In generale l’architettura fornisce le percezioni dei sensori al
programma, esegue il programma e trasmette le scelte delle azioni dello
stesso agli attuatori man mano che vengono generate.
3
cfr. [1], capitolo 2, pag. 36
1.2. Che cosa è un agente intelligente 11
La relazione che sussiste tra agenti, architetture e programmi può essere
quindi riassunta in questo modo:
agente = architettura + programma
Prima di poter progettare un agente, bisogna avere un’idea ben chiara
delle percezioni e delle azioni possibili, di quali obiettivi o misura di
prestazione si suppone che l’agente conseguirà e del tipo di ambiente nel
quale opererà.
Non deve sembrare una sorpresa se nel corso della tesi sarà utilizzato
un tipo di agente che opera in un ambiente interamente artificiale
definito dall’input di una tastiera e dall’output di caratteri sullo schermo.
Sicuramente si potrebbe dire che questo non è un ambiente reale, quello
che importa, però, non è la distinzione tra ambienti “reali” ed “artificiali”,
ma la complessità della relazione tra il comportamento dell’agente, la
sequenza di percezione generata dall’ambiente e gli obiettivi che l’agente
dovrebbe raggiungere. Alcuni ambienti “reali” sono in realtà molto
semplici. Ad esempio, un robot progettato per analizzare le immagini di
un satellite orbitante può fare uso di una serie di asserzioni
semplificatrici: che le immagini ricevute saranno solo di un certo tipo e
che ci sono solo due azioni, accettare l’immagine o scartarla. Al contrario,
alcuni agenti software (o softbot o semplicemente bot) esistono in
domini ricchi ed illimitati. Si immagini un bot progettato per
sopravvivere in un gioco “sparatutto”. Tale gioco è un ambiente
complesso molto dettagliato e l’agente software deve scegliere tra una
grande varietà di azioni in tempo reale.
1.3. Il linguaggio dell’AI 12
1.3 Il linguaggio dell’AI
Un grande fermento ha contraddistinto per molti anni la comunità dei
giochi, grazie alla sperimentazione di tecniche avanzate di AI provenienti
dalla ricerca accademica, come algoritmi genetici, reti neurali, ed altre
particolari procedure. Il pendolo, quindi, ha cominciato ad oscillare in
un’altra direzione e la maggior parte dei programmatori AI è ora fedele a
semplici tecniche di provato successo.
Stranamente la forte attenzione a tali sistemi ha permesso ai
programmatori di giochi di fare passi da gigante, indipendentemente
dalla comunità accademica. In realtà ciò non sorprende, in quanto i due
gruppi hanno degli obiettivi profondamente differenti. La ricerca
accademica è orientata verso il “come” un problema può essere risolto,
mentre i programmatori di giochi sono orientati soprattutto al risultato,
legato all’apparenza del prodotto finale.
La programmazione, quindi, è spesso una scienza inesatta che utilizza
delle approssimazioni nei calcoli, finalizzate ad un più grande scopo che è
quello del gioco. Viceversa la ricerca accademica si sforza di non trovare
un compromesso per la soluzione. L’algoritmo è il premio reale,
nient’altro è “corretto”. Ognuno dei gruppi ha semplicemente obiettivi e
motivazioni differenti.
Un ottimo esempio della diversità tra i due gruppi è offerto
dall’algoritmo di ricerca A*4. Tale algoritmo è usato molto
4
Particolare tipo di ricerca di un percorso, che minimizza il costo del cammino totale (vedi fig. 1.2).
1.3. Il linguaggio dell’AI 13
Figura 1.2 - Stadi in una ricerca A* per
Bucarest. I nodi sono etichettati con f = g + h. I
valori h sono le distanze in linea d’aria per
Bucarest.
di frequente nei giochi allo scopo di trovare un percorso adatto ad un
personaggio che si muove in un ambiente molto complicato. L’interesse
della comunità accademica all’A* è dovuto al fatto che questo ha la
proprietà di trovare il percorso più “breve” con una buona velocità
computazionale. Apportando una piccola modifica all’euristica5, A* può
5
La parola “euristica” deriva dal verbo greco heuriskein, che significa “trovare” o “scoprire”. Il
significato tecnico di “euristica” ha subito diversi mutamenti nella storia dell’AI. Attualmente,
euristico è usato più spesso come aggettivo, riferendosi a qualsiasi tecnica che migliora le
prestazioni del compito di risoluzione di problemi nel caso medio, ma non migliora
necessariamente le prestazioni nel caso peggiore. Nell’area specifica degli algoritmi di ricerca si
riferisce ad una funzione che fornisce una stima del costo della soluzione.