Come creare un'IA di gioco: guida per principianti

Ho trovato un materiale interessante sull'intelligenza artificiale nei giochi. Spiega le basi dell'IA con esempi semplici e include molti strumenti e metodi utili per la sua comodità nello sviluppo e nella progettazione. Anche informazioni su dove, come e quando usarli sono disponibili.

La maggior parte degli esempi è scritta in pseudocodice, quindi non servono conoscenze approfondite di programmazione. Sotto ci sono 35 pagine di testo con immagini e gif, quindi preparati.

UPD. Mi scuso, ma ho già fatto una mia traduzione di questo articolo su Habr PatientZero. Puoi leggere la sua versione qui, ma per qualche motivo l'articolo è passato inosservato (ho usato la ricerca, ma qualcosa è andato storto). E poiché scrivo in un blog dedicato allo sviluppo di giochi, ho deciso di lasciare la mia variante di traduzione per gli iscritti (alcuni punti sono formulati diversamente, altri sono intenzionalmente omessi su consiglio degli sviluppatori).

Che cos'è l'IA?

L'IA di gioco si concentra su quali azioni un oggetto deve compiere in base alle condizioni in cui si trova. Di solito, questo viene chiamato gestione di "agenti intelligenti", dove l'agente può essere un personaggio di gioco, un veicolo, un bot, e a volte anche qualcosa di più astratto: un'intera squadra di entità o addirittura una civiltà. In ogni caso, si tratta di qualcosa che deve percepire l'ambiente circostante, prendere decisioni sulla base di esso e agire di conseguenza. Questo è chiamato ciclo Sense/Think/Act (Percepire/Pensare/Agire):

• Sense: l'agente trova o riceve informazioni sulle cose nel suo ambiente che possono influenzare il suo comportamento (minacce vicine, oggetti da raccogliere, luoghi interessanti da esplorare).
• Think: l'agente decide come reagire (valuta se sia sicuro raccogliere oggetti o se debba combattere/nascostarsi prima).
• Act: l'agente compie azioni per attuare la decisione precedente (inizia a muoversi verso il nemico o l'oggetto).
• …ora la situazione è cambiata a causa delle azioni dei personaggi, quindi il ciclo si ripete con nuovi dati.

L'IA si concentra generalmente sulla fase Sense del ciclo. Ad esempio, le auto autonome scattano foto della strada, le combinano con i dati del radar e del lidar, e le interpretano. Di solito, questo viene fatto tramite l'apprendimento automatico, che elabora i dati in entrata e assegna loro un significato, estraendo informazioni semantiche come «c'è un'altra auto a 20 iarde davanti a te». Questi sono noti come problemi di classificazione.

I giochi non hanno bisogno di un sistema complesso per estrarre informazioni, poiché gran parte dei dati fa già parte integrante del gioco. Non è necessario eseguire algoritmi di riconoscimento delle immagini per stabilire se c'è un nemico davanti: il gioco lo sa già e comunica queste informazioni direttamente nel processo decisionale. Pertanto, la fase Sense del ciclo è spesso molto più semplice rispetto a Think e Act.

Limitazioni dell'IA di gioco

L'IA presenta una serie di limitazioni che devono essere rispettate:

• L'IA non deve essere addestrata in anticipo, come un algoritmo di apprendimento automatico. È inutile scrivere una rete neurale durante lo sviluppo per osservare decine di migliaia di giocatori e studiare il miglior modo di giocare contro di loro. Perché? Perché il gioco non è stato rilasciato e non ci sono giocatori.
• Il gioco deve intrattenere e sfidare, quindi gli agenti non dovrebbero trovare l'approccio migliore contro gli esseri umani.
• Gli agenti devono apparire realistici affinché i giocatori si sentano come se stessero giocando contro persone reali. Il programma AlphaGo ha superato l'umano, ma le mosse selezionate erano molto lontane dalla tradizionale comprensione del gioco. Se il gioco simula un avversario umano, non dovrebbe esserci questa sensazione. L'algoritmo deve essere modificato affinché prenda decisioni plausibili, anziché perfette.
• L'IA deve funzionare in tempo reale. Questo significa che l'algoritmo non può monopolizzare l'uso del processore per un lungo periodo durante la presa di decisioni. Anche 10 millisecondi per questo sono troppo lunghi, perché la maggior parte dei giochi richiede da 16 a 33 millisecondi per completare tutta l'elaborazione e procedere al fotogramma successivo.
• È ideale se almeno una parte del sistema è controllata dai dati, affinché i "non programmatori" possano apportare modifiche e affinché le correzioni avvengano più rapidamente.

Consideriamo gli approcci dell'IA che coprono l'intero ciclo Sense/Think/Act.

Prendere decisioni di base

Iniziamo con un gioco semplice: Pong. L'obiettivo è spostare la piattaforma (paddle) in modo che la pallina rimbalzi su di essa e non passi oltre. È come il tennis, dove perdi se non colpisci la pallina. Qui l'IA ha compiti relativamente facili: deve decidere in quale direzione spostare la piattaforma.

Operatori condizionali

Per l'IA in Pong, c'è una soluzione ovvia: cercare sempre di posizionare la piattaforma sotto la pallina.

Un algoritmo semplice per fare questo, scritto in pseudocodice:

ogni frame/aggiornamento mentre il gioco è in esecuzione:
se la pallina è a sinistra della piattaforma:
muovi la piattaforma a sinistra
altrimenti se la pallina è a destra della piattaforma:
muovi la piattaforma a destra

Se la piattaforma si muove alla stessa velocità della pallina, questo è l'algoritmo ideale per l'IA in Pong. Non c'è bisogno di complicare le cose se i dati e le possibili azioni per l'agente non sono molti.

Questo approccio è così semplice che l'intero ciclo Sense/Think/Act è appena percepibile. Ma è presente:

• La parte Sense si trova in due operatori if. Il gioco conosce la posizione della pallina e della piattaforma, quindi l'IA fa riferimento a queste informazioni.
• La parte Think comprende anche due operatori if. Questi rappresentano due soluzioni che, in questo caso, sono mutuamente esclusive. Di conseguenza, viene scelta una tra tre azioni: spostare la piattaforma a sinistra, spostarla a destra o non fare nulla se è già posizionata correttamente.
• La parte Act si trova negli operatori Move Paddle Left e Move Paddle Right. A seconda del design del gioco, questi possono spostare la piattaforma istantaneamente o a una certa velocità.

Questi approcci vengono chiamati reattivi: ci sono un insieme semplice di regole (in questo caso gli operatori if nel codice) che reagiscono allo stato attuale del mondo e agiscono.

Albero delle decisioni

L'esempio del gioco Pong corrisponde effettivamente al concetto formale di AI chiamato albero delle decisioni. L'algoritmo lo percorre per raggiungere una "foglia" — una decisione su quale azione intraprendere.

Creiamo un diagramma di flusso dell'albero delle decisioni per l'algoritmo della nostra piattaforma:

Ogni parte dell'albero è chiamata nodo — l'AI utilizza la teoria dei grafi per descrivere strutture simili. Ci sono due tipi di nodi:

• Nodi decisionali: scelta tra due alternative basata sul controllo di una certa condizione, dove ogni alternativa è rappresentata come un nodo separato.
• Nodi terminali: azione da eseguire, che rappresenta una decisione finale.

L'algoritmo inizia con il primo nodo (il "radice" dell'albero). Esso decide se passare a un nodo figlio o eseguire l'azione memorizzata nel nodo e termina.

Qual è quindi il vantaggio, se l'albero delle decisioni esegue lo stesso lavoro degli operatori if nella sezione precedente? Qui c'è un sistema generale, dove ogni decisione ha solo una condizione e due possibili risultati. Questo consente allo sviluppatore di creare IA dai dati che rappresentano decisioni nell'albero, evitando il loro hardcoding. Immaginiamolo in forma di tabella:

Dal lato del codice, avrai un sistema per la lettura delle stringhe. Crea un nodo per ognuna di esse, collega la logica decisionale basata sulla seconda colonna e i nodi figli basati sulla terza e quarta colonna. Dovrai ancora programmare le condizioni e le azioni, ma ora la struttura del gioco sarà più complessa. Aggiungi ulteriori decisioni e azioni, e poi configura l'intera IA semplicemente modificando il file di testo che definisce l'albero. Poi, trasferisci il file al game designer, che potrà modificare il comportamento senza ricompilare il gioco e modificare il codice.

Gli alberi decisionali sono molto utili quando vengono costruiti automaticamente sulla base di un ampio insieme di esempi (ad esempio, utilizzando l'algoritmo ID3). Questo li rende uno strumento efficace e ad alte prestazioni per la classificazione delle situazioni in base ai dati ricevuti. Tuttavia, andiamo oltre un semplice sistema per decidere le azioni degli agenti.

Scenari

Abbiamo esaminato un sistema ad albero decisionale che utilizzava condizioni e azioni predefinite. La persona che progetta l'intelligenza artificiale può organizzare l'albero come desidera, ma deve comunque dipendere da un programmatore che lo ha codificato. E se potessimo dare al designer strumenti per creare le proprie condizioni o azioni?

Per evitare che il programmatore debba scrivere codice per le condizioni Is Ball Left Of Paddle e Is Ball Right Of Paddle, potrebbe realizzare un sistema in cui il designer registra le condizioni per controllare questi valori. Allora i dati dell'albero decisionale appariranno in questo modo:

In sostanza, è la stessa cosa della prima tabella, ma le soluzioni al suo interno hanno un proprio codice, simile alla parte condizionale di un'istruzione if. Dal lato del codice, questo verrebbe letto nella seconda colonna per i nodi decisionali, ma invece di cercare una condizione specifica da eseguire (Is Ball Left Of Paddle), valuta l'espressione condizionale e restituisce true o false di conseguenza. Questo avviene utilizzando il linguaggio di scripting Lua o Angelscript. Con questi, lo sviluppatore può gestire oggetti nel suo gioco (ball e paddle) e creare variabili che saranno disponibili nello script (ball.position). Inoltre, il linguaggio di scripting è più semplice del C++. Non richiede una fase di compilazione completa, rendendolo ideale per modifiche rapide alla logica di gioco e permettendo ai 'non programmatori' di creare le funzioni necessarie.

Nell'esempio fornito, il linguaggio di scripting viene utilizzato solo per valutare l'espressione condizionale, ma può essere usato anche per le azioni. Ad esempio, i dati Move Paddle Right possono diventare un'istruzione di script (ball.position.x += 10). In questo modo, l'azione è definita anche nello script, senza la necessità di programmare Move Paddle Right.

È possibile andare oltre e scrivere completamente un albero delle decisioni in un linguaggio di scripting. Si tratterà di codice sotto forma di operatori condizionali hardcoded, ma saranno contenuti in file esterni di script, quindi possono essere modificati senza ricompilare l'intero programma. Spesso è possibile modificare il file dello script direttamente durante il gioco per testare rapidamente diverse reazioni dell'IA.

Reazione agli eventi

Gli esempi sopra si applicano perfettamente a Pong. Eseguono continuamente il ciclo Sense/Think/Act e agiscono in base all'ultimo stato del mondo. Ma nei giochi più complessi è necessario reagire a eventi singoli, piuttosto che valutare tutto e subito. In questo caso, Pong non è un buon esempio. Scegliamo un altro.

Immagina uno sparatutto dove i nemici rimangono fermi finché non vedono il giocatore, dopodiché agiscono in base alla loro "specializzazione": qualcuno correrà per attaccare, qualcun altro attaccherà da lontano. Questo è ancora un sistema reattivo di base — "se il giocatore è visto, fai qualcosa" — ma può essere logicamente diviso in evento Player Seen (giocatore visto) e reazione (scegli una risposta e eseguila).

Questo ci riporta al ciclo Sense/Think/Act. Possiamo codificare la parte Sense, che ogni fotogramma verificherà se l'IA vede il giocatore. Se non lo vede, non succede nulla, ma se lo vede, viene generato un evento Player Seen. Il codice avrà una sezione separata che dirà: "quando si verifica l'evento Player Seen, fa ", dove è la risposta necessaria per accedere alle parti Think e Act. In questo modo, puoi impostare le reazioni all'evento Player Seen: per un personaggio che avanza - ChargeAndAttack, e per un cecchino - HideAndSnipe. Questi legami possono essere creati in un file di dati per una rapida modifica senza la necessità di ricompilare. E qui puoi utilizzare anche un linguaggio di scripting.

Prendere decisioni complesse

Sebbene i semplici sistemi di reazione siano molto efficaci, ci sono molte situazioni in cui non sono sufficienti. A volte è necessario prendere decisioni diverse in base a ciò che l'agente sta facendo in quel momento, ma rappresentare questo come una condizione è difficile. A volte ci sono troppe condizioni da rappresentare in modo efficace in un albero decisionale o in uno script. Occasionalmente, è necessario valutare in anticipo come cambierà la situazione prima di decidere quale sarà il passo successivo. Per affrontare questi problemi sono necessarie soluzioni più complesse.

Macchina a stati finiti

La macchina a stati finiti, o FSM (Finite State Machine) è un modo per indicare che il nostro agente si trova attualmente in uno di diversi stati possibili e che può passare da uno stato all'altro. Gli stati sono un numero definito—da qui il nome. Il miglior esempio nella vita reale è il semaforo. In luoghi diversi ci sono sequenze di luci differenti, ma il principio è lo stesso: ogni stato rappresenta qualcosa (fermo, vai, ecc.). Il semaforo è in uno stato solo in qualsiasi momento e passa da uno all'altro basandosi su semplici regole.

Con NPC nei giochi c'è una storia simile. Prendiamo come esempio una guardia con i seguenti stati:

• In pattugliamento (Patrolling).
• In attacco (Attacking).
• In fuga (Fleeing).

E con queste condizioni per cambiare il suo stato:

• Se la guardia vede un nemico, attacca.
• Se la guardia attacca, ma non vede più il nemico, torna a pattugliare.
• Se la guardia attacca, ma è gravemente ferita, fugge.

È possibile anche scrivere operatori if con una variabile di stato della guardia e vari controlli: c'è un nemico vicino, qual è il livello di salute dell’NPC, e così via. Aggiungiamo qualche altro stato:

• Inattività (Idling) — tra le pattuglie.
• Ricerca (Searching) — quando un nemico avvistato si è nascosto.
• Chiedere aiuto (Finding Help) — quando un nemico è stato avvistato, ma è troppo forte per combatterlo da solo.

La scelta per ognuno di essi è limitata — per esempio, la guardia non andrà a cercare un nemico nascosto se ha poca salute.

Alla fine, un lungo elenco di "se" può diventare troppo ingombrante, pertanto è necessario formalizzare un metodo che ci permetta di tenere a mente gli stati e le transizioni tra gli stati. <x и y, но не z>, allora <p>Per fare ciò, considereremo tutti gli stati e, sotto ciascuno stato, annoteremo un elenco di tutte le transizioni verso altri stati, insieme alle condizioni necessarie per esse.

Questa è una tabella di transizioni di stato — un modo complesso per rappresentare una FSM. Disegniamo un diagramma e otteniamo una panoramica completa di come cambia il comportamento dell’NPC.

Il diagramma riflette la natura della presa di decisioni per questo agente in base alla situazione attuale. Ogni freccia indica una transizione tra stati, se la condizione accanto ad essa è vera.

Ad ogni aggiornamento verifichiamo lo stato attuale dell'agente, consultiamo l'elenco delle transizioni e, se le condizioni per la transizione sono soddisfatte, accetta un nuovo stato. Ad esempio, ogni fotogramma verifica se il timer di 10 secondi è scaduto e, in tal caso, l'agente passa dallo stato Idling a Patrolling. Allo stesso modo, lo stato Attacking controlla la salute dell'agente: se è bassa, passa allo stato Fleeing.

Questa è la gestione delle transizioni tra stati, ma che dire del comportamento associato agli stati stessi? Per quanto riguarda l'implementazione del comportamento effettivo per uno stato specifico, di solito ci sono due tipi di "hook" dove assegnamo azioni alla FSM:

• Azioni che eseguiamo periodicamente per lo stato attuale.
• Azioni che intraprendiamo durante la transizione da uno stato all'altro.

Esempi per il primo tipo. Lo stato Patrolling sposterà l'agente lungo il percorso di pattugliamento ad ogni fotogramma. Lo stato Attacking tenterà ogni fotogramma di iniziare un attacco o passare a uno stato in cui ciò è possibile.

Per il secondo tipo, consideriamo la transizione "se il nemico è visibile e il nemico è troppo forte, allora passare allo stato Finding Help." L'agente deve scegliere dove andare a cercare aiuto e memorizzare queste informazioni affinché lo stato Finding Help sappia a chi rivolgersi. Una volta trovato aiuto, l'agente torna allo stato Attacking. A questo punto, vorrà informare l'alleato della minaccia, quindi può sorgere l'azione NotifyFriendOfThreat.

Ancora una volta, possiamo guardare questo sistema attraverso il ciclo Sense/Think/Act. Sense si materializza nei dati utilizzati dalla logica di transizione. Think — nelle transizioni disponibili in ogni stato. E Act si concretizza nelle azioni eseguite periodicamente all'interno dello stato o durante le transizioni tra gli stati.

A volte, il monitoraggio continuo delle condizioni di transizione può risultare costoso. Ad esempio, se ogni agente deve eseguire calcoli complessi a ogni frame per determinare se vede nemici e se può passare dallo stato di Pattugliamento a quello di Attacco, ciò richiederà molte risorse del processore.

I cambiamenti significativi nello stato del mondo possono essere considerati eventi da elaborare man mano che si presentano. Invece di far sì che la FSM controlli ogni frame la condizione di transizione 'può il mio agente vedere il giocatore?', si può impostare un sistema separato per effettuare i controlli meno frequentemente (ad esempio, 5 volte al secondo). Il risultato sarebbe emettere Player Seen quando il controllo ha successo.

Questo viene passato alla FSM, che ora deve passare alla condizione event received per Player Seen e rispondere di conseguenza. Il comportamento finale è lo stesso, tranne per un ritardo quasi impercettibile prima della risposta. Tuttavia, le prestazioni sono migliorate grazie alla separazione della parte Sense in un'area distinta del programma.

Macchina a stati finiti gerarchica

Tuttavia, lavorare con grandi FSM non è sempre comodo. Se volessimo espandere lo stato di attacco, sostituendolo con MeleeAttacking (combattimento corpo a corpo) e RangedAttacking (combattimento a distanza) separati, dovremmo modificare le transizioni da tutti gli altri stati che portano allo stato Attacking (attuale e futuro).

Sicuramente avrete notato che nel nostro esempio ci sono molte transizioni duplicate. La maggior parte delle transizioni nello stato Idling è identica a quelle nello stato Patrolling. È meglio evitare ripetizioni, specialmente se aggiungeremo altri stati simili. Ha senso raggruppare Idling e Patrolling sotto un'etichetta comune "non combattenti", dove c'è solo un unico insieme di transizioni verso stati combattivi. Se consideriamo questa etichetta come uno stato, allora Idling e Patrolling diventeranno sottostati. Un esempio di utilizzo di una tabella di transizione separata per il nuovo sottostato non combattente:

Stati principali:


Stato fuori combattimento:


E in forma di diagramma:

Si tratta dello stesso sistema, ma con un nuovo stato non bellico, che include Idling e Patrolling. Ogni stato contiene una FSM con sottostati (e questi sottostati, a loro volta, contengono la propria FSM — e così via quante ne servono), ottenendo così una Hierarchical Finite State Machine o HFSM (macchina a stati finiti gerarchica). Raggruppando lo stato non bellico, abbiamo eliminato molte transizioni ridondanti. Lo stesso possiamo fare per nuovi stati con transizioni comuni. Ad esempio, se in futuro espandiamo lo stato Attacking fino a includere gli stati MeleeAttacking e MissileAttacking, questi saranno sottostati che si scambiano tra di loro in base alla distanza dal nemico e alla disponibilità di munizioni. Di conseguenza, modelli di comportamento complessi e sotto-modelli di comportamento possono essere rappresentati con il minimo di transizioni duplicate.

Albero dei comportamenti

Con HFSM si possono creare combinazioni complesse di comportamenti in modo semplice. Tuttavia, c'è una piccola difficoltà: le decisioni sotto forma di regole di transizione sono strettamente legate allo stato attuale. E in molti giochi, questo è esattamente ciò di cui si ha bisogno. Un uso attento della gerarchia degli stati può ridurre il numero di ripetizioni durante le transizioni. Ma a volte sono necessarie regole che funzionano indipendentemente dallo stato in cui ci si trova o che si applicano quasi a tutti gli stati. Ad esempio, se la salute dell'agente scende al 25%, si vorrà che scappi indipendentemente dal fatto che sia stato in combattimento, si fosse riposato o stesse parlando: sarà necessario aggiungere questa condizione in ogni stato. E se successivamente il designer decide di cambiare la soglia di bassa salute dal 25% al 10%, si dovrà occuparne di nuovo.

Ideale per questa situazione sarebbe un sistema in cui le decisioni su "in quale stato trovarsi" siano al di fuori degli stati stessi, in modo da apportare modifiche in un solo luogo senza toccare le condizioni di transizione. Qui entrano in gioco gli alberi di comportamento.

Ci sono diversi modi per implementarli, ma il concetto è sostanzialmente lo stesso e somiglia a un albero delle decisioni: l'algoritmo inizia da un nodo 'radice', e nell'albero ci sono nodi che rappresentano sia decisioni che azioni. Tuttavia, ci sono alcune differenze chiave:

• Ora i nodi restituiscono uno dei tre valori: Succeeded (se il lavoro è completato), Failed (se non può essere avviato) o Running (se è ancora in esecuzione e non ci sono risultati finali).
• Non ci sono più nodi decisionali per scegliere tra due alternative. Al loro posto, ci sono i nodi Decorator, che hanno un solo nodo figlio. Se restituiscono Succeed, eseguono il loro unico nodo figlio.
• I nodi che eseguono azioni restituiscono il valore Running per rappresentare le azioni in corso.

Questo piccolo insieme di nodi può essere combinato per creare un gran numero di complessi modelli comportamentali. Immaginiamo l'HFSM della guardia dal precedente esempio sotto forma di un albero comportamentale:

Con questa struttura non dovrebbe esserci un passaggio diretto dagli stati Idling/Patrolling allo stato Attacking o ad altri stati. Se il nemico è visibile e la salute del personaggio è bassa, l'esecuzione si fermerà al nodo Fleeing, indipendentemente da quale nodo stesse eseguendo in precedenza — Patrolling, Idling, Attacking o qualsiasi altro.

Gli alberi comportamentali sono complessi: ci sono molti modi per comporli e trovare la giusta combinazione di decoratori e nodi compositi può risultare problematico. Ci sono anche domande su quanto spesso controllare l'albero: vogliamo passare attraverso ogni parte o solo quando una delle condizioni è cambiata? Come mantenere lo stato relativo ai nodi — come sapere quando siamo stati in uno stato Idling per 10 secondi o come sapere quali nodi sono stati eseguiti l'ultima volta per gestire correttamente la sequenza?

Proprio per questo esistono molteplici implementazioni. Ad esempio, in alcuni sistemi, i nodi decoratori sono stati sostituiti da decoratori integrati. Questi rivalutano l'albero al variare delle condizioni del decoratore, aiutano a collegare i nodi e forniscono aggiornamenti periodici.

Sistema basato sull'utilità

Alcuni giochi presentano molte meccaniche diverse. È consigliabile che traggano tutti i vantaggi di regole semplici e generali di transizione, ma non necessariamente in forma di un albero completo di comportamenti. Invece di avere un insieme chiaro di scelte o un albero di azioni possibili, è più semplice esplorare tutte le azioni e scegliere quella più appropriata al momento.

Il sistema basato sulla utilità aiuta proprio in questo. È un sistema in cui l'agente ha molte azioni, e sceglie quale eseguire, basandosi sulla relativa utilità di ciascuna. Dove l'utilità è una misura arbitraria di quanto sia importante o desiderabile l'esecuzione di quell'azione per l'agente.

L'agente può calcolare l'utilità delle azioni in base allo stato e all'ambiente attuali, verificando e selezionando in qualsiasi momento il più appropriato stato alternativo. Questo è simile a un FSM, tranne per il fatto che le transizioni sono definite dalla valutazione di ciascuno stato potenziale, incluso quello attuale. Si noti che scegliamo l'azione più utile per il passaggio (o restiamo fermi se l'abbiamo già eseguita). Per maggiore varietà, può essere una scelta ponderata ma casuale da un breve elenco.

Il sistema assegna un intervallo casuale di valori di utilità, ad esempio, da 0 (completamente indesiderabile) a 100 (completamente desiderabile). Ogni azione ha una serie di parametri che influenzano il calcolo di questo valore. Tornando al nostro esempio con la guardia:

Le transizioni tra le azioni sono ambigue: qualsiasi stato può seguire un altro. Le priorità delle azioni sono determinate dai valori di utilità restituiti. Se il nemico è visibile, e questo nemico è forte, mentre la salute del personaggio è bassa, sia Fuggire che TrovareAiuto restituiranno valori alti e diversi da zero. Tuttavia, TrovareAiuto avrà sempre una priorità maggiore. Allo stesso modo, le azioni non combative non restituiscono mai più di 50, quindi saranno sempre inferiori alle azioni di combattimento. È necessario tenerne conto nella creazione delle azioni e nel calcolo della loro utilità.

Nel nostro esempio, le azioni restituiscono un valore costante fisso oppure uno dei due valori fissi. Un sistema più realistico prevede la restituzione di una valutazione da un intervallo continuo di valori. Ad esempio, l'azione Fleeing restituisce valori di utilità più elevati se la salute dell'agente è bassa, mentre l'azione Attacking restituisce valori più bassi se il nemico è troppo forte. Per questo motivo, l'azione Fleeing ha la priorità su Attacking ogni volta che l'agente percepisce di avere una salute insufficiente per vincere contro il suo avversario. Questo permette di modificare le priorità delle azioni in base a un numero qualsiasi di criteri, rendendo questo approccio più flessibile e variabile rispetto a un albero comportamentale o a un FSM.

Ogni azione ha molte condizioni per calcolare il programma. Queste possono essere scritte in un linguaggio di scripting o come una serie di formule matematiche. In The Sims, che simula la routine quotidiana del personaggio, viene aggiunto un ulteriore livello di calcolo: l'agente riceve una serie di "motivazioni" che influenzano le valutazioni di utilità. Se il personaggio ha fame, col tempo avrà ancora più fame, e il risultato dell'azione EatFood aumenterà finché il personaggio non la eseguirà, riducendo il livello di fame e riportando il valore di EatFood a zero.

L'idea di scegliere azioni basate su un sistema di valutazione è piuttosto semplice, quindi il sistema basato sull'utilità può essere utilizzato come parte dei processi decisionali dell'IA, non come un loro completo sostituto. Un albero delle decisioni può richiedere la valutazione dell'utilità di due nodi figli e scegliere quello con il valore più elevato. Allo stesso modo, un albero del comportamento può avere un nodo composto di Utilità per valutare l'utilità delle azioni, decidendo quale elemento figlio eseguire.

Movimento e navigazione

Nei precedenti esempi avevamo una piattaforma che spostavamo a sinistra o a destra e una sentinella che pattugliava o attaccava. Ma come gestiamo esattamente il movimento dell'agente nel corso del tempo? Come impostiamo la velocità, come evitiamo gli ostacoli e come pianifichiamo il percorso se raggiungere la destinazione è più complesso che muoversi in linea retta? Analizziamo questo.

Gestione

Inizialmente, supponiamo che ogni agente abbia un valore di velocità che include quanto velocemente si muove e in quale direzione. Può essere misurata in metri al secondo, chilometri all'ora, pixel al secondo, ecc. Ricordando il ciclo Sense/Think/Act, possiamo immaginare che la parte Think scelga la velocità, mentre la parte Act applichi quella velocità all'agente. Di solito, nei giochi esiste un sistema fisico che esegue questo compito per te, monitorando il valore di velocità di ogni oggetto e regolando di conseguenza. Pertanto, possiamo lasciare all'IA un compito: decidere quale velocità deve avere l'agente. Se si sa dove l'agente deve trovarsi, allora deve essere spostato nella giusta direzione a una velocità stabilita. È un'equazione molto triviale:

desired_travel = destination_position – agent_position

Immagina un mondo 2D. L'agente si trova nel punto (-2,-2), mentre la destinazione è da qualche parte a nord-est, nel punto (30, 20), e il percorso necessario per l'agente per arrivarci è (32, 22). Supponiamo che queste posizioni siano misurate in metri: se consideriamo la velocità dell'agente di 5 metri al secondo, scaleremo il nostro vettore di movimento e otterremo una velocità di circa (4.12, 2.83). Con questi parametri, l'agente arriverebbe a destinazione in quasi 8 secondi.

I valori possono essere ricalcolati in qualsiasi momento. Se l'agente era a metà strada verso l'obiettivo, il movimento sarebbe stato la metà della lunghezza, ma poiché la velocità massima dell'agente è di 5 m/s (come deciso sopra), la velocità sarà uguale. Questo funziona anche per obiettivi in movimento, consentendo all'agente di apportare piccole modifiche mentre si muovono.

Tuttavia, desideriamo maggiore varietà: ad esempio, aumentare lentamente la velocità per simulare un personaggio che passa da una posizione ferma alla corsa. Lo stesso vale per l'arresto finale. Queste funzionalità sono conosciute come comportamenti di guida, ciascuno con un nome specifico: Seek (ricerca), Flee (fuga), Arrival (arrivo) e così via. L'idea è che le forze di accelerazione possono essere applicate alla velocità dell'agente, confrontando la posizione dell'agente e la velocità attuale con il punto di destinazione, in modo da utilizzare diversi metodi di movimento verso l'obiettivo.

Ogni comportamento ha un obiettivo leggermente diverso. Seek e Arrival sono modi per muovere l'agente verso una destinazione. Obstacle Avoidance (evitamento ostacoli) e Separation (separazione) correggono il movimento dell'agente per aggirare gli ostacoli lungo il percorso verso l'obiettivo. Alignment (allineamento) e Cohesion (coesione) mantengono gli agenti uniti durante il movimento. Un numero qualsiasi di diversi comportamenti di guida può essere sommato per ottenere un unico vettore di percorso che tiene conto di tutti i fattori. Un agente utilizza i comportamenti Arrival, Separation e Obstacle Avoidance per mantenere la distanza da pareti e altri agenti. Questo approccio funziona bene in spazi aperti senza troppi dettagli.

In condizioni più difficili, la somma di diversi comportamenti funziona peggio — per esempio, un agente potrebbe rimanere bloccato in un muro a causa di un conflitto tra Arrival e Obstacle Avoidance. Pertanto, è necessario considerare opzioni più complesse rispetto a una semplice somma di tutti i valori. Un modo per farlo è: invece di sommare i risultati di ciascun comportamento, si possono considerare i movimenti in diverse direzioni e scegliere la migliore opzione.

Tuttavia, in un ambiente complesso con vicoli ciechi e scelte su quale direzione andare, avremo bisogno di qualcosa di ancora più avanzato.

Ricerca del percorso

I comportamenti di guida sono ideali per la semplice navigazione in spazi aperti (un campo da calcio o un'arena), dove raggiungere A da B è un percorso diretto con lievi deviazioni attorno agli ostacoli. Per percorsi più complessi, abbiamo bisogno del pathfinding, che è un modo per esplorare il mondo e decidere il miglior tragitto attraverso di esso.

Il modo più semplice è sovrapporre una griglia su ogni quadrato accanto all'agente e valutare in quali di essi è permesso muoversi. Se uno di essi è una destinazione, segui da esso il percorso da ogni quadrato al precedente, fino a tornare all'inizio. Questo è il percorso. In caso contrario, ripeti il processo con i quadrati vicini finché non trovi la destinazione o non ci sono più quadrati (il che significa che non esiste alcun percorso possibile). Questo è formalmente noto come Breadth-First Search o BFS (algoritmo di ricerca in ampiezza). Ad ogni passo, guarda in tutte le direzioni (da qui 'breadth', 'ampiezza'). Lo spazio di ricerca assomiglia a un fronte d'onda che si muove fino a raggiungere il punto desiderato — l'area di ricerca si espande ad ogni passo fino a quando non raggiunge il punto finale, dopo di che è possibile tracciare il percorso verso l'inizio.

Di conseguenza, avrai un elenco di quadrati da cui si compone il percorso desiderato. Questo è il percorso (da qui 'pathfinding') — l'elenco dei luoghi che l'agente visiterà mentre si dirige verso la destinazione.

Considerando che conosciamo la posizione di ciascun quadrato nel mondo, possiamo utilizzare i comportamenti di steering per muoverci lungo il percorso — dal nodo 1 al nodo 2, poi dal nodo 2 al nodo 3 e così via. La soluzione più semplice è dirigersi verso il centro del prossimo quadrato, ma è ancora meglio fermarsi a metà del lato tra il quadrato attuale e quello successivo. Questo permette all'agente di tagliare gli angoli nelle curve strette.

L'algoritmo BFS ha anche degli svantaggi — esplora quanti più quadrati nella direzione «sbagliata» quanti quelli nella direzione «giusta». Qui entra in gioco un algoritmo più complesso chiamato A* (A star). Funziona in modo simile, ma invece di esplorare ciecamente i quadrati vicini (poi i vicini dei vicini, poi i vicini dei vicini dei vicini e così via), raccoglie i nodi in una lista e li ordina in modo tale che il prossimo nodo esplorato sia sempre quello che porterà al percorso più breve. I nodi vengono ordinati sulla base di un'euristica che considera due aspetti — il «costo» del percorso ipotetico verso il quadrato desiderato (inclusi eventuali costi di spostamento) e una stima di quanto questo quadrato sia lontano dalla destinazione (spostando la ricerca nella direzione giusta).

In questo esempio, l'agente esplora un quadrato alla volta, scegliendo ogni volta quello vicino che offre le migliori possibilità. Il percorso ottenuto è lo stesso del BFS, ma nel processo sono stati considerati meno quadrati, il che è significativo per le prestazioni del gioco.

Movimento senza griglia

Ma la maggior parte dei giochi non è organizzata su una griglia, e spesso non è possibile crearla senza compromettere il realismo. Sono necessari dei compromessi. Quali dovrebbero essere le dimensioni dei quadrati? Troppo grandi — e non potranno rappresentare correttamente corridoi o curve strette, troppo piccoli — ci sarebbero troppi quadrati da cercare, il che richiederebbe molto tempo.

La prima cosa da comprendere è che la griglia ci fornisce un grafo di nodi collegati. Gli algoritmi A* e BFS funzionano fondamentalmente su grafi e non si preoccupano affatto della nostra griglia. Potremmo posizionare i nodi in qualsiasi punto del mondo di gioco: con una connessione tra due nodi, così come tra il punto di partenza e di arrivo e almeno uno dei nodi, l'algoritmo funzionerà altrettanto bene come prima. Questo è spesso chiamato sistema di waypoint, poiché ogni nodo rappresenta una posizione significativa nel mondo, che può far parte di un numero qualsiasi di percorsi ipotetici.

Esempio 1: un nodo in ogni quadrato. La ricerca inizia dal nodo in cui si trova l'agente e termina nel nodo del quadrato desiderato.

Esempio 2: un insieme ridotto di nodi (waypoint). La ricerca inizia nel quadrato con l'agente, passa attraverso il numero necessario di nodi e poi continua fino alla destinazione.

Si tratta di un sistema piuttosto flessibile e potente. Tuttavia, è necessaria una certa prudenza nelle decisioni riguardo a dove e come posizionare i waypoint; altrimenti, gli agenti potrebbero semplicemente non vedere il punto più vicino e non riuscire a partire. Sarebbe più semplice se potessimo disporre automaticamente i waypoint sulla base della geometria del mondo.

Qui entra in gioco la navigation mesh o navmesh (rete di navigazione). Si tratta solitamente di una rete 2D di triangoli che si sovrappone alla geometria del mondo, in tutte le aree in cui all'agente è consentito muoversi. Ciascuno dei triangoli nella rete diventa un nodo nel grafo e ha fino a tre triangoli adiacenti che diventano nodi vicini nel grafo.

Questa immagine è un esempio dal motore Unity: ha analizzato la geometria del mondo e creato il navmesh (nella schermata di colore blu chiaro). Ogni poligono nel navmesh è un'area su cui l'agente può stare o spostarsi da un poligono a un altro. In questo esempio, i poligoni sono più piccoli dei piani su cui si trovano, per tenere conto delle dimensioni dell'agente, che potrebbero estendersi oltre la sua posizione nominale.

Possiamo cercare un percorso attraverso questa rete, utilizzando nuovamente l'algoritmo A*. Questo ci darà un percorso praticamente perfetto in un mondo che tiene conto di tutta la geometria e non richiede nodi inutili e creazione di punti di passaggio.

La ricerca di percorsi è un argomento troppo vasto per essere trattato in un solo articolo. Se vuoi approfondire, puoi trovare aiuto sul sito di Amit Patel..

Pianificazione

Abbiamo appreso con la ricerca di percorsi che a volte non basta semplicemente scegliere una direzione e muoversi: dobbiamo scegliere un percorso e effettuare alcune svolte per raggiungere la destinazione desiderata. Possiamo riassumere questa idea: raggiungere un obiettivo non è solo il prossimo passo, ma una vera e propria sequenza, in cui a volte è necessario guardare avanti di alcuni passi per sapere quale dovrebbe essere il primo. Questo è chiamato pianificazione. La ricerca di percorsi può essere vista come una delle varie integrazioni della pianificazione. Dal punto di vista del nostro ciclo Sensore/Pensiero/Azione, è qui che la parte Pensiero pianifica diverse parti dell'Azione per il futuro.

Analizziamo con l'esempio del gioco da tavolo Magic: The Gathering. Iniziamo per primi con questa mano di carte:

• Palude — fornisce 1 mana nero (carta terreno).
• Foresta — fornisce 1 mana verde (carta terra).
• Mago Fuggitivo — richiede 1 mana blu per l'invocazione.
• Mistico Elfico — richiede 1 mana verde per l'invocazione.

Ignoriamo le tre carte rimanenti per semplificare. Secondo le regole, un giocatore può giocare 1 carta terra per turno; può 'tappare' questa carta per ottenere mana e poi usare incantesimi (incluso l'invocazione di creature) in base alla quantità di mana. In questa situazione, un giocatore umano sa che deve giocare Foresta, 'tappare' 1 mana verde e poi invocare il Mistico Elfico. Ma come può capirlo l'IA del gioco?

Pianificazione semplice

L'approccio triviale è provare ogni azione a turno, finché non rimangono opzioni valide. Guardando le carte, l'IA vede che può giocare Pantano. E lo gioca. Ci sono altre azioni disponibili in questo turno? Non può invocare né il Mistico Elfico né il Mago Fuggitivo, poiché richiedono rispettivamente mana verde e blu, e il Pantano fornisce solo mana nera. E non potrà giocare Foresta, perché ha già giocato il Pantano. In questo modo, l'IA di gioco ha agito secondo le regole, ma lo ha fatto male. Si può migliorare.

La pianificazione può trovare un elenco di azioni che conducono il gioco allo stato desiderato. Proprio come ogni quadrato nel percorso ha avuto dei vicini (nel pathfinding), ogni azione nel piano ha anche dei vicini o successori. Possiamo esplorare queste azioni e le azioni successive finché non raggiungiamo lo stato desiderato.

Nel nostro esempio, il risultato desiderato è «evocare una creatura, se possibile». All'inizio del turno vediamo solo due possibili azioni consentite dalle regole del gioco:

1. Giocare Swamp (risultato: Swamp in gioco)
2. Giocare Forest (risultato: Forest in gioco)

Ogni azione intrapresa può portare a ulteriori azioni e chiudere altre, ancora una volta a seconda delle regole del gioco. Immaginate di aver giocato Swamp — questo rimuoverà Swamp come prossimo passo (lo abbiamo già giocato), e rimuoverà anche Forest (perché secondo le regole si può giocare solo una carta terra per turno). Successivamente, l'IA aggiunge come prossimo passo — ottenere 1 mana nero, perché non ci sono altre opzioni. Se procederà ulteriormente e sceglierà di tappare lo Swamp, otterrà 1 mana nero e non potrà fare nulla con esso.

1. Giocare Swamp (risultato: Swamp in gioco)
1.1 «Tappare» Swamp (risultato: Swamp «tappato», +1 unità di mana nera)
Nessuna azione disponibile – FINE
2. Giocare Forest (risultato: Forest in gioco)

L'elenco delle azioni è corto, siamo bloccati. Ripetiamo il processo per la prossima azione. Giochiamo Forest, attiviamo l'azione «ottenere 1 mana verde», che a sua volta attiverà la terza azione — evocare Elvish Mystic.

1. Giocare Swamp (risultato: Swamp in gioco)
1.1 «Tappare» Swamp (risultato: Swamp «tappato», +1 unità di mana nera)
Nessuna azione disponibile – FINE
2. Giocare Forest (risultato: Forest in gioco)
2.1 «Tappare» Forest (risultato: Forest «tappata», +1 unità di mana verde)
2.1.1 Evocare Elvish Mystic (risultato: Elvish Mystic in gioco, -1 unità di mana verde)
Nessuna azione disponibile – FINE

Infine, abbiamo esaminato tutte le possibili azioni e trovato un piano per evocare una creatura.

Questo è un esempio molto semplificato. È preferibile scegliere il miglior piano possibile, piuttosto che qualsiasi piano che soddisfi determinati criteri. In generale, è possibile valutare i piani potenziali in base al risultato finale o ai benefici complessivi derivanti dalla loro attuazione. Si possono guadagnare 1 punto per ogni carta terra giocata e 3 punti per l'evocazione di una creatura. Giocare Swamp sarebbe un piano che fornisce 1 punto. Giocare Forest → Tappare la Forest → evocare Elvish Mystic darebbe immediatamente 4 punti.

Ecco come funziona la pianificazione in Magic: The Gathering, ma la stessa logica si applica anche in altre situazioni. Ad esempio, spostare un pedone per liberare spazio per muovere un alfiere negli scacchi. O ripararsi dietro un muro per poter sparare in sicurezza in XCOM. Insomma, hai capito il concetto.

Pianificazione avanzata

A volte ci sono troppe possibili azioni da considerare per esaminare ogni opzione. Tornando all'esempio di Magic: The Gathering: supponiamo che ci siano diverse carte di terra e creature in gioco e nella tua mano: il numero di possibili combinazioni di mosse può essere enorme. Ci sono alcune soluzioni a questo problema.

Il primo metodo è il backwards chaining (formazione della catena al contrario). Invece di esaminare tutte le combinazioni, è meglio iniziare dal risultato finale e cercare un percorso diretto. Invece di muoversi dalla radice dell'albero verso una foglia specifica, ci muoviamo in direzione opposta — dalla foglia alla radice. Questo metodo è più semplice e veloce.

Se il nemico ha 1 punto vita, possiamo trovare un piano per 'infliggere 1 o più danni'. Per farlo è necessario soddisfare una serie di condizioni:

1. Un incantesimo può causare danni — deve essere nella mano.
2. Per lanciare un incantesimo — è necessaria la mana.
3. Per ottenere mana — è necessario giocare una carta terreno.
4. Per giocare una carta terreno — è necessario averla in mano.

Un altro modo è la ricerca best-first (cerca il migliore per primo). Invece di esaminare tutti i percorsi, scegliamo il più idoneo. Questo metodo frequentemente fornisce un piano ottimale senza costi aggiuntivi per la ricerca. A* è una forma di ricerca best-first — esplorando i percorsi più promettenti sin dall'inizio, può già trovare il percorso migliore senza dover controllare le altre opzioni.

Una delle varianti più interessanti e sempre più popolari della ricerca best-first è il Monte Carlo Tree Search. Invece di indovinare quali piani siano migliori ad ogni azione successiva, l'algoritmo sceglie successori casuali ad ogni passo, fino a raggiungere la fine (quando il piano porta alla vittoria o alla sconfitta). Il risultato finale viene poi utilizzato per aumentare o diminuire la valutazione del 'peso' delle opzioni precedenti. Ripetendo questo processo più volte, l'algoritmo fornisce una buona stima di quale possa essere il passo successivo migliore, anche se la situazione cambia (se l'avversario prende misure per ostacolare il giocatore).

Nel racconto del pianificare nei giochi non si può prescindere dal Goal-Oriented Action Planning o GOAP (pianificazione delle azioni orientata agli obiettivi). Questo è un metodo ampiamente utilizzato e discusso, ma al di là di alcuni dettagli distintivi, è essenzialmente un metodo di backwards chaining, di cui abbiamo parlato in precedenza. Se l'obiettivo è 'eliminare il giocatore', e il giocatore è dietro a una copertura, il piano potrebbe essere: distruggi con una granata → prendila → lanciala.

Di solito ci sono più obiettivi, ognuno con la propria priorità. Se l'obiettivo con la massima priorità non può essere raggiunto (nessuna combinazione di azioni crea un piano per 'eliminare il giocatore', poiché il giocatore non è visibile), l'IA tornerà agli obiettivi con priorità inferiore.

Apprendimento e adattamento

Abbiamo già detto che l'IA di gioco di solito non utilizza il machine learning, poiché non è adatta per gestire agenti in tempo reale. Ma questo non significa che non si possa imparare qualcosa da quest'area. Vogliamo un avversario in uno sparatutto da cui si possa apprendere qualcosa. Per esempio, scoprire le migliori posizioni sulla mappa. Oppure un avversario in un picchiaduro che bloccasse frequentemente le combo usate dai giocatori, motivando a utilizzare altre mosse. Quindi, il machine learning in tali situazioni può essere molto utile.

Statistiche e probabilità

Prima di immergerci in esempi complessi, vediamo quanto possiamo scorprire prendendo alcune semplici misure e utilizzandole per prendere decisioni. Ad esempio, nella strategia in tempo reale, come possiamo determinare se un giocatore possa iniziare un attacco nei primi minuti del gioco e quale difesa preparare contro di esso? Possiamo analizzare le esperienze passate del giocatore per capire quale potrebbe essere la futura reazione. Partiamo dal presupposto che non abbiamo dati di partenza, ma possiamo raccoglierli — ogni volta che l'IA gioca contro un umano, può registrare il tempo della prima attacco. Dopo alcune sessioni, avremo una media del tempo che ci vorrà per il giocatore per attaccare in futuro.

Le medie hanno anche un problema: se un giocatore ha "rushato" 20 volte e ha giocato lentamente 20 volte, i valori necessari saranno da qualche parte nel mezzo, e ciò non ci fornirà nulla di utile. Una soluzione è limitare i dati in ingresso — possiamo considerare solo gli ultimi 20 eventi.

Un approccio simile viene utilizzato per valutare la probabilità di determinate azioni, assumendo che le preferenze passate del giocatore rimarranno le stesse in futuro. Se un giocatore ci attacca cinque volte con palle di fuoco, due volte con fulmini e una volta corpo a corpo, è chiaro che preferisce le palle di fuoco. Espandiamo e vediamo la probabilità di utilizzo delle diverse armi: palladi fuoco = 62,5%, fulmine = 25% e corpo a corpo = 12,5%. La nostra IA di gioco deve prepararsi a difendersi dal fuoco.

Un altro metodo interessante è utilizzare il Naive Bayes Classifier (classificatore bayesiano naive) per analizzare grandi volumi di dati in ingresso e classificare la situazione affinché l'IA reagisca in modo appropriato. I classificatori bayesiani sono più noti per il loro utilizzo nei filtri antispam delle email. In questo caso, esaminano le parole, le confrontano con le precedenti apparizioni di quelle parole (in spam o meno) e traggono conclusioni sulle email in arrivo. Possiamo fare lo stesso anche con un minor numero di dati in ingresso. Sulla base di tutte le informazioni utili che l'IA osserva (ad esempio, quali unità nemiche sono state create, quali incantesimi vengono utilizzati o quali tecnologie sono state esplorate) e il risultato finale (guerra o pace, attaccare o difendersi, ecc.) — selezioneremo il comportamento più adeguato per l'IA.

Tutti questi metodi di apprendimento sono sufficienti, ma è preferibile utilizzarli basandosi sui dati dei test. L'IA apprenderà ad adattarsi a diverse strategie utilizzate dai tuoi playtester. Un'IA che si adatta ai giocatori dopo il rilascio potrebbe diventare troppo prevedibile o, al contrario, troppo difficile da battere.

Adattamento basato sui valori

Tenendo conto della struttura del nostro mondo di gioco e delle regole, possiamo modificare il set di valori che influenzano le decisioni, anziché semplicemente utilizzare i dati in ingresso. Procediamo in questo modo:

• Lasciamo che l'IA raccolga dati sullo stato del mondo e sugli eventi chiave durante il gioco (come indicato sopra).
• Modifichiamo alcuni valori importanti in base a questi dati.
• Implementiamo le nostre decisioni basate sull'elaborazione o sulla valutazione di questi valori.

Ad esempio, l'agente ha diverse stanze tra cui scegliere sulla mappa di uno sparatutto in prima persona. Ogni stanza ha il proprio valore, che determina quanto sia desiderabile per la visita. L'IA sceglie casualmente in quale stanza andare, basandosi sul valore. Poi l'agente ricorda in quale stanza è stato ucciso e diminuisce il suo valore (la probabilità che torni lì). Analogamente, se l'agente elimina molti avversari, il valore della stanza aumenta.

Modello di Markov

Cosa succede se utilizziamo i dati raccolti per le previsioni? Se ricordiamo ogni stanza in cui vediamo un giocatore per un certo periodo, possiamo anticipare in quale stanza il giocatore potrebbe andare. Monitorando e registrando i movimenti del giocatore tra le stanze (valori), possiamo fare delle previsioni.

Prendiamo tre stanze: rossa, verde e blu. E anche le osservazioni che abbiamo registrato durante la visione della sessione di gioco:

Il numero di osservazioni per ogni stanza è quasi uguale — non sappiamo ancora dove creare un buon punto di appostamento. La raccolta di statistiche è inoltre complicata dal respawn dei giocatori, che appaiono uniformemente in tutta la mappa. Tuttavia, i dati sulla successiva stanza in cui entrano dopo essere apparsi sulla mappa sono già utili.

È chiaro che la stanza verde soddisfa i giocatori — la maggior parte delle persone dalla stanza rossa vi si trasferisce, e il 50% di esse rimane lì. Al contrario, la stanza blu non gode di popolarità; vi entrano molto pochi e, se ci vanno, non si fermano.

Ma i dati ci dicono qualcosa di più importante: quando il giocatore si trova nella stanza blu, la stanza successiva in cui è più probabile che lo vediamo sarà rossa e non verde. Sebbene la stanza verde sia più popolare di quella rossa, la situazione cambia se il giocatore è nella stanza blu. Il prossimo stato (cioè la stanza in cui il giocatore passerà) dipende dallo stato precedente (cioè dalla stanza in cui il giocatore si trova attualmente). Grazie all'analisi delle dipendenze, saremo in grado di fare previsioni più accurate rispetto a se semplicemente conteggiassimo le osservazioni in modo indipendente l'una dall'altra.

La previsione dello stato futuro sulla base dei dati dello stato passato è chiamata modello di Markov, e tali esempi (con stanze) vengono definiti catene di Markov. Poiché i modelli rappresentano la probabilità di cambiamenti tra stati successivi, vengono visualizzati come FSM con probabilità associate a ciascun passaggio. In precedenza, abbiamo utilizzato le FSM per rappresentare lo stato comportamentale in cui si trovava l'agente, ma questo concetto si estende a qualsiasi stato, indipendentemente dal fatto che sia associato all'agente o meno. In questo caso, gli stati rappresentano la stanza occupata dall'agente:

Questa è una semplice rappresentazione della probabilità relativa dei cambiamenti di stato, che offre all'IA una certa possibilità di prevedere il prossimo stato. È possibile prevedere diversi passaggi avanti.

Se un giocatore si trova nella stanza verde, c'è il 50% di probabilità che rimanga lì al prossimo osservazione. Ma qual è la probabilità che ci sia ancora anche dopo? Non c'è solo la possibilità che il giocatore rimanga nella stanza verde dopo due osservazioni, ma anche la possibilità che sia uscito e poi tornato. Ecco una nuova tabella basata sui nuovi dati:

Da essa si evince che la probabilità di vedere il giocatore nella stanza verde dopo due osservazioni sarà del 51% — 21% che provenga dalla stanza rossa, 5% di probabilità che il giocatore visiti la stanza blu nel mezzo, e 25% che il giocatore non esca affatto dalla stanza verde.

La tabella è uno strumento visivo semplice: la procedura richiede solo di moltiplicare le probabilità a ogni passo. Questo significa che puoi guardare lontano nel futuro con un'unica riserva: presumiamo che la probabilità di entrare in una stanza dipenda completamente dalla stanza attuale. Questo è conosciuto come proprietà di Markov (Markov Property) — il futuro stato dipende solo dallo stato presente. Tuttavia, non è totalmente preciso. I giocatori possono modificare le decisioni in base ad altri fattori: livello di salute o quantità di munizioni. Poiché non registriamo questi valori, le nostre previsioni saranno meno accurate.

N-Grams

E per quanto riguarda l'esempio del combattimento e la previsione delle combo dei giocatori? È lo stesso! Ma invece di uno stato o evento, esploreremo intere sequenze che compongono il colpo in combo.

Uno dei modi per farlo è memorizzare ogni input (ad esempio, Kick, Punch o Block) in un buffer e registrare l'intero buffer come evento. Quindi, se un giocatore preme ripetutamente Kick, Kick, Punch per eseguire l'attacco SuperDeathFist, il sistema AI memorizza tutti gli input nel buffer e ricorda gli ultimi tre utilizzati a ogni passaggio.

(Le righe sono evidenziate in grassetto quando il giocatore avvia l'attacco SuperDeathFist.)

L'IA vedrà tutte le opzioni quando il giocatore seleziona Kick, seguito da un altro Kick, e poi noterà che il prossimo input è sempre Punch. Questo permetterà all'agente di prevedere la combo SuperDeathFist e di bloccarla se possibile.

Queste sequenze di eventi sono chiamate N-grammi, dove N è il numero di elementi memorizzati. Nell'esempio precedente, si trattava di un 3-gramma, il che significa: i primi due elementi vengono utilizzati per prevedere il terzo. Di conseguenza, in un 5-gramma, i primi quattro elementi prevedono il quinto e così via.

Lo sviluppatore deve scegliere con attenzione la dimensione degli N-grammi. Un numero minore di N richiede meno memoria, ma memorizza anche una storia minore. Ad esempio, un 2-gramma registrerà Kick, Kick o Kick, Punch, ma non sarà in grado di memorizzare Kick, Kick, Punch, pertanto l'IA non risponderà alla combo SuperDeathFist.

D'altra parte, numeri più grandi richiedono più memoria e sarà più difficile per l'IA addestrarsi, poiché ci saranno molte più varianti possibili. Se avevate tre possibili input: Kick, Punch o Block, e utilizzavamo un modello di 10-grammi, ci sarebbero circa 60.000 varianti diverse.

Il modello dei bigrammi è una semplice catena di Markov: ogni coppia «stato passato/stato attuale» è un bigramma, e si può prevedere il secondo stato basandosi sul primo. I 3-grammi e le N-grammi più grandi possono anche essere considerati catene di Markov, dove tutti gli elementi (eccetto l'ultimo nell'N-gramma) insieme formano il primo stato, e l'ultimo elemento è il secondo. L'esempio con il combattimento mostra la probabilità di passare dallo stato Kick e Kick allo stato Kick e Punch. Considerando più registrazioni della storia di input come un'unità, stiamo fondamentalmente trasformando la sequenza di input in una parte di uno stato intero. Questo ci dà la proprietà di Markov, permettendoci di utilizzare le catene di Markov per prevedere il prossimo input e indovinare quale mossa combo sarà successiva.

Conclusione

Abbiamo parlato dei più comuni strumenti e approcci nello sviluppo dell'intelligenza artificiale, analizzando anche le situazioni in cui devono essere applicati e dove sono particolarmente utili.

Questo dovrebbe essere sufficiente per comprendere le nozioni di base sull'IA nei giochi. Tuttavia, sicuramente non è tutto. Tra i metodi meno comuni, ma altrettanto efficaci, ci sono:

• algoritmi di ottimizzazione, compresi l'ascensione nei colli, il gradiente discendente e gli algoritmi genetici
• algoritmi competitivi di ricerca/pianificazione (minimax e potatura alpha-beta)
• metodi di classificazione (perceptron, reti neurali e macchine a vettori di supporto)
• sistemi per la gestione della percezione e della memoria degli agenti
• approcci architettonici all'IA (sistemi ibridi, sottoinsiemi di architetture e altri metodi di sovrapposizione dei sistemi di IA)
• strumenti di animazione (pianificazione e coordinamento del movimento)
• fattori di prestazione (livello di dettaglio, algoritmi anytime e timeslicing)

Risorse online sull'argomento:

1. Su GameDev.net c'è una sezione con articoli e tutorial sull'IA, così come un forum.
2. AiGameDev.com offre molte presentazioni e articoli su un ampio spettro di argomenti legati allo sviluppo dell'IA nei giochi.
3. Il GDC Vault include argomenti dal summit GDC AI, molti dei quali sono disponibili gratuitamente.
4. Materiali utili possono essere trovati anche sul sito AI Game Programmers Guild.
5. Tommy Thompson, ricercatore di IA e sviluppatore di giochi, realizza video sul canale YouTube AI and Games con spiegazioni e analisi dell'IA nei giochi commerciali.

Libri sul tema:

1. La serie di libri Game AI Pro è una raccolta di articoli brevi che spiegano come implementare funzioni specifiche o risolvere problemi concreti.

Game AI Pro: Collected Wisdom of Game AI Professionals
Game AI Pro 2: Collected Wisdom of Game AI Professionals
Game AI Pro 3: Collected Wisdom of Game AI Professionals

2. La serie AI Game Programming Wisdom è il precursore della serie Game AI Pro. Presenta metodi più vecchi, ma quasi tutti sono ancora pertinenti oggi.

AI Game Programming Wisdom 1
AI Game Programming Wisdom 2
AI Game Programming Wisdom 3
AI Game Programming Wisdom 4

3. Artificial Intelligence: A Modern Approach è uno dei testi fondamentali per chiunque voglia comprendere l'ampia area dell'intelligenza artificiale. Questo libro non è sulla sviluppo di giochi - insegna le basi dell'IA.

Fonte: habr.com