Come creare un'IA di gioco: guida per principianti

Ho trovato un materiale interessante sull'intelligenza artificiale nei giochi. Con una spiegazione delle nozioni di base sull'IA tramite esempi semplici, e contiene anche molti strumenti e metodi utili per lo sviluppo e la progettazione comoda. Come, dove e quando usarli — ci sono anche queste informazioni.

La maggior parte degli esempi è scritta in pseudocodice, quindi non sono richieste conoscenze approfondite di programmazione. Di seguito ci sono 35 pagine di testo con immagini e GIF, quindi preparatevi.

UPD. Mi scuso, ma ho già fatto una traduzione di questo articolo su Habr. PatientZero. Puoi leggere la sua versione qui, ma per qualche motivo l'articolo mi era sfuggito (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 traduzione per gli iscritti (alcuni aspetti li ho presentati in modo diverso, altri — intenzionalmente omessi su consiglio degli sviluppatori).

Cos'è l'IA?

L'IA nei giochi si concentra su quali azioni un oggetto deve eseguire in base alle condizioni in cui si trova. Questo viene solitamente definito gestione di "agenti intelligenti", dove l'agente è un personaggio di gioco, un veicolo, un bot, e talvolta è qualcosa di più astratto: un intero gruppo di entità o persino una civiltà. In ogni caso, è un'entità che deve percepire il suo ambiente, prendere decisioni sulla base di esso e agire di conseguenza. Questo si chiama ciclo Sense/Think/Act (Percepire/Pensare/Agire):

• Percepire: l'agente trova o riceve informazioni su cose nel suo ambiente che possono influenzare il suo comportamento (minacce vicine, oggetti da raccogliere, luoghi interessanti da esplorare).
• Pensare: l'agente decide come reagire (considera se è abbastanza sicuro raccogliere oggetti o se prima deve combattere/nascondersi).
• Agire: 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, di solito, si concentra sulla parte Sense del ciclo. Ad esempio, le auto a guida autonoma scattano foto della strada, le uniscono ai dati del radar e del lidar, e le interpretano. Solitamente, questo viene fatto dall'apprendimento automatico, che elabora i dati in ingresso e dà loro significato, estraendo informazioni semantiche come "c'è un'altra auto a 20 yards davanti a te". Questi sono i cosiddetti problemi di classificazione.

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

Limitazioni dell'IA nei giochi

L'IA ha una serie di limitazioni da rispettare:

• L'IA non deve essere addestrata in anticipo, come se fosse 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 mettere alla prova, quindi gli agenti non devono trovare il miglior approccio contro le persone.
• Gli agenti devono apparire realistici, affinché i giocatori si sentano come se stessero giocando contro persone reali. Il programma AlphaGo ha superato l'uomo, ma le mosse scelte erano molto lontane dalla comprensione tradizionale del gioco. Se il gioco imita un avversario umano, non deve esserci tale sensazione. L'algoritmo deve essere modificato affinché prenda decisioni plausibili e non perfette.
• L'IA deve funzionare in tempo reale. Questo significa che l'algoritmo non può monopolizzare l'uso della CPU per un lungo periodo per prendere decisioni. Anche 10 millisecondi per questo sono troppo lunghi, poiché la maggior parte dei giochi richiede da 16 a 33 millisecondi per completare l'elaborazione e passare al fotogramma successivo.
• È ideale se almeno una parte del sistema è gestita dai dati, affinché i "non programmatori" possano apportare modifiche e per rendere le correzioni più rapide.

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

Presi di decisioni di base

Iniziamo con il gioco più semplice: Pong. Obiettivo: spostare la piattaforma (paddle) in modo che la palla rimbalzi su di essa e non la superi. È come il tennis, dove perdi se non colpisci la palla. Qui l'IA ha un compito relativamente semplice: decidere in quale direzione muovere la piattaforma.

Operatori condizionali

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

Un semplice algoritmo per questo, scritto in pseudocodice:

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

Se la piattaforma si muove alla velocità della palla, allora 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 così tanti.

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

• La parte Sense si trova nei due operatori if. Il gioco sa dove si trova la palla e dove è la piattaforma, quindi l'IA si riferisce ad essa per avere queste informazioni.
• La parte Think è anch'essa composta da due operatori if. Rappresentano due decisioni, che in questo caso sono mutuamente esclusive. Di conseguenza, viene scelta una delle 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 Muovi la piattaforma a sinistra e Muovi la piattaforma a destra. A seconda del design del gioco, possono spostare la piattaforma istantaneamente o con una certa velocità.

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

Albero delle decisioni

L'esempio del gioco Pong è infatti equivalente al concetto formale di IA chiamato albero delle decisioni. L'algoritmo lo attraversa per raggiungere una 'foglia' — la decisione su quale azione intraprendere.

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

Ogni parte dell'albero si chiama nodo (node) — l'IA 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 condizione, dove ogni alternativa è rappresentata come un nodo separato.
• Nodi finali: azione da eseguire, rappresentante la decisione finale.

L'algoritmo inizia dal primo nodo («radice» dell'albero). Esso può prendere una decisione su quale nodo figlio passare, oppure eseguire un'azione memorizzata nel nodo e concludersi.

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

Dal lato del codice avrete un sistema per leggere le righe. Create un nodo per ciascuna di esse, collegate la logica decisionale basata sulla seconda colonna e i nodi figli in base alla terza e quarta colonna. Dovrete ancora programmare le condizioni e le azioni, ma ora la struttura del gioco sarà più complessa. In essa aggiungete decisioni e azioni supplementari, e poi configurate tutta l'IA semplicemente modificando un file di testo con la definizione dell'albero. Successivamente, passate il file al game designer, che potrà cambiare il comportamento senza ricompilare il gioco e senza 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 acquisiti. Tuttavia, superiamo la semplice struttura per la scelta delle azioni degli agenti.

Scenari

Abbiamo analizzato un sistema di alberi decisionali che utilizzava condizioni e azioni predefinite. La persona che progetta l'IA può organizzare l'albero come desidera, ma deve comunque fare affidamento su un programmatore che l'ha tutto programmato. E se potessimo dare al designer gli 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, può creare un sistema in cui il designer registrerà le condizioni per controllare questi valori. Allora i dati dell'albero delle decisioni appariranno così:

In sostanza, è la stessa cosa che nella prima tabella, ma le soluzioni al loro interno hanno un proprio codice, un po' simile alla parte condizionale dell'operatore if. Dalla parte 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 viene fatto attraverso il linguaggio di scripting Lua o Angelscript. Con questi, lo sviluppatore può prendere oggetti nel proprio gioco (ball e paddle) e creare variabili che saranno accessibili nello script (ball.position). Inoltre, il linguaggio di scripting è più semplice del C++. Non richiede una fase di compilazione completa, quindi è perfetto per rapidi aggiustamenti della logica di gioco e consente ai "non programmatori" di creare le funzioni necessarie.

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

Si può andare ancora oltre e scrivere completamente un albero decisionale in linguaggio di scripting. Questo sarà codice sotto forma di operatori condizionali hardcoded, ma saranno situati in file di script esterni, ovvero possono essere modificati senza ricompilare l'intero programma. Spesso è possibile modificare il file di script direttamente durante il gioco, per testare rapidamente diverse reazioni dell'IA.

Reazione agli eventi

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

Immagina uno shooter in cui i nemici sono immobili finché non rilevano il giocatore, dopodiché agiscono in base alla loro "specializzazione": qualcuno correrà per attaccare, qualcuno attaccherà da lontano. Questa è ancora una base reattiva — "se il giocatore è visto, allora fai qualcosa" — ma può essere logicamente separata in evento Player Seen (giocatore visto) e reazione (scegli la risposta e attuala).

Questo ci riporta al ciclo Sense/Think/Act. Possiamo codificare la parte Sense, che controlla ad ogni frame se l'IA vede il giocatore. Se non lo vede, non succede nulla, ma se lo vede, si genera un evento Player Seen. Il codice avrà una sezione separata che dice: «quando si verifica l'evento Player Seen, fai », dove è la risposta necessaria per accedere alle parti Think e Act. In questo modo, imposterai le reazioni all'evento Player Seen: per il personaggio che 'corre' — ChargeAndAttack, e per il cecchino — HideAndSnipe. Questi collegamenti possono essere creati in un file dati per una modifica rapida senza la necessità di ricompilare da zero. Qui si può utilizzare anche il linguaggio di scripting.

Prendere decisioni complesse

Sebbene i sistemi di reazione semplici siano molto efficaci, ci sono molte situazioni in cui non sono sufficienti. A volte è necessario prendere diverse decisioni, basate su ciò che l'agente sta facendo in quel momento, ma rappresentare questo come una condizione è difficile. A volte ci sono troppe condizioni per rappresentarle efficacemente in un albero delle decisioni o in uno script. A volte è necessario valutare in anticipo come cambierà la situazione, prima di prendere una decisione sul passo successivo. Per affrontare questi problemi sono necessari approcci più complessi.

Macchina a stati finiti

La macchina a stati finiti o FSM (Finite State Machine) è un modo per dire che il nostro agente è attualmente in uno di diversi stati possibili, e che può passare da uno stato all'altro. Gli stati sono definiti in numero finito — da qui il nome. Il miglior esempio della vita quotidiana è un semaforo. In diversi luoghi ci sono diverse sequenze di luci, ma il principio è lo stesso: ogni stato rappresenta qualcosa (ferma, vai, ecc.). Il semaforo si trova sempre in uno stato in un dato momento, e passa da uno all'altro sulla base di semplici regole.

Con gli NPC nei giochi, la storia è simile. Prendiamo come esempio un guardiano con i seguenti stati:

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

E con queste condizioni per cambiare il suo stato:

• Se il guardiano vede un avversario, attacca.
• Se il guardiano attacca, ma non vede più l'avversario, torna in pattuglia.
• Se il guardiano attacca, ma è gravemente ferito, fugge.

È possibile anche scrivere operatori if con variabili di stato del guardiano e varie verifiche: se c'è un nemico nelle vicinanze, quale è il livello di salute dell'NPN e così via. Aggiungiamo ancora alcuni stati:

• Inattività (Idling) — tra i pattugliamenti.
• Ricerca (Searching) — quando un nemico avvistato è scomparso.
• Chiedere aiuto (Finding Help) — quando un nemico è avvistato, ma è troppo forte per combatterlo da solo.

La scelta per ognuno di essi è limitata: ad esempio, il guardiano non andrà a cercare il nemico scomparso se ha poca salute.

Alla fine, un'enorme lista "se" può diventare troppo ingombrante, quindi è necessario formalizzare un metodo che ci permetta di tenere a mente gli stati e le transizioni tra gli stati. Per fare ciò, prenderemo in considerazione tutti gli stati e, sotto ogni stato, scriveremo in un elenco tutte le transizioni verso altri stati, insieme alle condizioni necessarie per esse. <x и y, но не z>, allora <p>», potrebbe diventare troppo ingombrante, quindi è necessario formalizzare un metodo che ci consenta di tenere a mente gli stati e le transizioni tra gli stati. Per fare ciò, considereremo tutti gli stati e, per ciascuno di essi, scriveremo in un elenco tutte le transizioni verso altri stati, insieme alle condizioni necessarie per esse.

Questa è una tabella di transizione di stati — un modo complesso di rappresentare una FSM. Disegniamo un diagramma e otteniamo una panoramica completa di come cambia il comportamento dell'NPC.

Il diagramma riflette l'essenza della presa di decisioni per questo agente in base alla situazione attuale. Ogni freccia mostra la transizione tra stati, se la condizione a essa associata è vera.

Ad ogni aggiornamento controlliamo lo stato attuale dell'agente, esaminiamo l'elenco delle transizioni e se le condizioni per la transizione sono soddisfatte, egli accetta un nuovo stato. Ad esempio, ad ogni frame viene controllato se il timer di 10 secondi è scaduto e, se sì, dallo stato di Idling, il guardiano passa a Patrolling. In modo simile, lo stato di Attacking controlla la salute dell'agente: se è bassa, passa allo stato di Fleeing.

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

• Azioni che eseguiamo periodicamente per lo stato attuale.
• Azioni che intraprendiamo quando passiamo da uno stato a un altro.

Esempi per il primo tipo. Lo stato di Patrolling muoverà l'agente lungo il percorso di pattugliamento ad ogni frame. Lo stato di Attacking tenterà di avviare un attacco o passare a uno stato quando possibile ad ogni frame.

Per il secondo tipo, consideriamo il passaggio "se il nemico è visibile e il nemico è troppo forte, allora passare allo stato Finding Help. L'agente deve scegliere dove andare per ricevere aiuto e conservare queste informazioni affinché lo stato Finding Help sappia dove rivolgersi. Una volta trovato aiuto, l'agente torna allo stato Attacking. A questo punto vorrà segnalare al compagno la minaccia, quindi potrebbe verificarsi l'azione NotifyFriendOfThreat.

Ancora una volta, possiamo esaminare questo sistema attraverso il ciclo Sense/Think/Act. Sense si realizza 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 nelle transizioni tra stati.

A volte, il sondaggio continuo delle condizioni di transizione può essere dispendioso. Ad esempio, se ogni agente deve eseguire calcoli complessi ogni fotogramma per determinare se vede i nemici e comprendere se può passare dallo stato Patrolling a Attacking – questo richiederà molto tempo di elaborazione.

Le importanti modifiche nello stato del mondo possono essere considerate eventi che verranno elaborati man mano che si verificano. Invece di controllare ogni fotogramma se l'agente può vedere il giocatore, è possibile impostare un sistema separato per eseguire controlli meno frequentemente (ad esempio, 5 volte al secondo). E il risultato sarà Player Seen, una volta che il controllo è superato.

Questo viene passato al FSM, il quale ora deve passare alla condizione Player Seen event received e rispondere di conseguenza. Il comportamento finale rimane lo stesso, eccetto per un ritardo quasi impercettibile prima della risposta. Tuttavia, le prestazioni sono migliorate grazie alla separazione di parte del Sense in una parte separata del programma.

Macchina a stati finiti gerarchica

Tuttavia, lavorare con grandi FSM non è sempre comodo. Se desideriamo ampliare lo stato di attacco, sostituendolo con attacchi a distanza MeleeAttacking (corpo a corpo) e RangedAttacking (da distanza), dovremo modificare le transizioni di tutti gli altri stati che portano allo stato Attacking (quelli correnti e futuri).

Sicuramente avrete notato che nel nostro esempio ci sono molte transizioni duplicate. La maggior parte delle transizioni nello stato di Idling sono identiche a quelle nello stato di Patrolling. Sarebbe opportuno non ripetersi, soprattutto se aggiungeremo altri stati simili. Ha senso raggruppare Idling e Patrolling sotto un'etichetta comune 'non bellica', dove c'è un unico insieme comune di transizioni verso stati di combattimento. Se consideriamo questa etichetta come uno stato, allora Idling e Patrolling diventeranno sottostati. Ecco un esempio di utilizzo di una tabella delle transizioni separata per un nuovo sottostato non bellico:

Stati principali:


Stato fuori combattimento:


E in forma di diagramma:

Questa è la stessa identica sistema, ma con un nuovo stato non bellico che comprende Idling e Patrolling. Con ogni stato contenente un FSM con sottostati (e questi sottostati, a loro volta, contengono i propri FSM — e così via quante volte è necessario), otteniamo una Gerarchia di Macchine a Stati Finiti o HFSM. Raggruppando lo stato non bellico, abbiamo eliminato un sacco di transizioni ridondanti. Lo stesso possiamo fare per qualsiasi nuovo stato con transizioni comuni. Ad esempio, se in futuro espandiamo lo stato Attacking in stati MeleeAttacking e MissileAttacking, questi saranno sottostati, che si scambiano transizioni tra di loro in base alla distanza dal nemico e alla disponibilità di munizioni. Alla fine, modelli di comportamento complessi e sottomodelli di comportamento possono essere rappresentati con un minimo di transizioni duplicate.

Albero dei comportamenti

Con HFSM si creano combinazioni complesse di comportamenti in modo semplice. Tuttavia, c'è una piccola difficoltà, poiché la presa di decisione sotto forma di regole di transizione è strettamente legata allo stato attuale. E in molti giochi è proprio ciò che serve. Un'attenta utilizzo della gerarchia degli stati può ridurre il numero di ripetizioni nelle transizioni. Ma a volte servono regole che funzionano indipendentemente dallo stato in cui ti trovi o che si applicano quasi in qualsiasi stato. Ad esempio, se la salute dell'agente scende al 25%, vorresti che fuggisse indipendentemente dal fatto che fosse in combattimento, inattivo o che stesse parlando — dovresti aggiungere questa condizione in ogni stato. E se in seguito il tuo designer decidesse di modificare la soglia di bassa salute dal 25% al 10%, dovresti occuparmene di nuovo.

In ideale per questa situazione serve un sistema in cui le decisioni "in quale stato trovarsi" siano al di fuori degli stati stessi, in modo da apportare modifiche in un solo posto e non modificare le condizioni di transizione. Qui entrano in gioco gli alberi dei comportamenti.

Esistono diversi modi per implementarli, ma l'essenza è più o meno la stessa e assomiglia a un albero delle decisioni: l'algoritmo inizia da un nodo "radice", e nell'albero ci sono nodi che rappresentano o decisioni o azioni. Ci sono però alcune differenze chiave:

• Ora i nodi restituiscono uno dei tre valori: Succeeded (se il lavoro è stato completato), Failed (se non è possibile avviarlo) o Running (se è ancora in esecuzione e non c'è un risultato finale).
• Non ci sono più nodi decisionali per scegliere tra due alternative. Invece, ci sono nodi Decorator, che hanno un solo nodo figlio. Se ottengono 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 modelli complessi di comportamento. Immaginiamo l'HFSM di una sentinella dall'esempio precedente rappresentata come un albero del comportamento:

Con questa struttura non dovrebbe esserci un passaggio esplicito dagli stati Idling/Patrolling allo stato Attacking o a qualsiasi altro. Se il nemico è visibile e la salute del personaggio è bassa, l'esecuzione si fermerà sul nodo Fleeing, indipendentemente dal nodo che è stato precedentemente eseguito — Patrolling, Idling, Attacking o qualsiasi altro.

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

È per questo che esistono molte implementazioni. Ad esempio, in alcuni sistemi i nodi decoratore sono stati sostituiti con decoratori incorporati. Questi rivalutano l'albero al cambiamento delle condizioni del decoratore, aiutano a collegare i nodi e forniscono aggiornamenti periodici.

Sistema basato su utilità

Alcuni giochi hanno molte meccaniche diverse. È auspicabile che tutte possano trarre vantaggio da regole semplici e comuni per le transizioni, ma non necessariamente in forma di un albero comportamentale completo. Invece di avere un insieme chiaro di scelte o un albero di possibili azioni, è più semplice esplorare tutte le azioni e scegliere quella più appropriata al momento.

Il sistema basato su utilità (utility-based system) è proprio ciò di cui abbiamo bisogno. Si tratta di un sistema in cui l’agente ha molte azioni a disposizione e sceglie autonomamente quale eseguire, basandosi sull’utilità relativa di ciascuna. Dove l'utilità è una misura arbitraria dell'importanza o della desiderabilità dell'esecuzione di quell'azione per l'agente.

L'utilità calcolata dell'azione, basata sullo stato attuale e sull'ambiente, può essere verificata dall'agente per scegliere un altro stato potenzialmente più adatto in qualsiasi momento. Questo è simile a un FSM, ad eccezione del fatto che le transizioni sono definite dalla valutazione di ciascuno stato potenziale, incluso quello attuale. Si noti che scegliamo l'azione più utile per la transizione (o rimaniamo fermi se l'abbiamo già eseguita). Per una maggiore varietà, potrebbe essere una scelta ponderata, ma casuale, da una piccola lista.

Il sistema assegna un intervallo arbitrario 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. Ritornando al nostro esempio con il guardiano:

Le transizioni tra le azioni non sono univoche: qualsiasi stato può seguire qualsiasi altro. Le priorità delle azioni sono stabilite dai valori di utilità restituiti. Se il nemico è visibile e questo nemico è forte, e la salute del personaggio è bassa, allora sia Fleeing che FindingHelp restituiranno valori alti e diversi da zero. In questo caso, FindingHelp sarà sempre superiore. Analogamente, le azioni non di combattimento non restituiscono mai più di 50, quindi saranno sempre inferiori a quelle di combattimento. Questo deve essere considerato quando si creano azioni e si calcola la loro utilità.

Nel nostro esempio, le azioni restituiscono un valore costante fisso o uno dei due valori fissi. Un sistema più realistico prevede il ritorno 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 in qualsiasi situazione in cui l'agente sente di avere una salute insufficiente per vincere contro l'avversario. Ciò consente di modificare le priorità delle azioni sulla base di un numero qualsiasi di criteri, rendendo questo approccio più flessibile e variabile rispetto a un albero comportamentale o FSM.

Ogni azione ha molte condizioni per calcolare il programma. Possono essere scritte in un linguaggio di scripting o come una serie di formule matematiche. In The Sims, che modella la giornata della persona, 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, nel tempo diventerà ancora più affamato, 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 le azioni basandosi su un sistema di valutazione è piuttosto semplice, quindi il sistema basato sull'utilità può essere utilizzato come parte dei processi decisionali dell'IA, e non come loro completa sostituzione. Un albero decisionale può richiedere una valutazione di utilità di due nodi figli e scegliere il più alto. Allo stesso modo, un albero comportamentale può avere un nodo composito Utility per valutare l'utilità delle azioni, per decidere quale elemento figlio eseguire.

Movimento e navigazione

Negli esempi precedenti avevamo una piattaforma che spostavamo a sinistra o a destra e una guardia che pattugliava o attaccava. Ma come gestiamo esattamente il movimento dell'agente per un certo periodo di tempo? Come impostiamo la velocità, come evitiamo gli ostacoli e come pianifichiamo un percorso se raggiungere la destinazione è più complesso che muoversi in linea retta? Vediamo di approfondire.

Gestione

Nella fase iniziale, consideriamo che ogni agente ha un valore di velocità che include quanto rapidamente si muove e in quale direzione. Questa può essere misurata in metri al secondo, chilometri all'ora, pixel al secondo, ecc. Ricordando il ciclo Sense/TThink/Act, possiamo immaginare che la parte Think scelga la velocità, mentre la parte Act applichi questa velocità all'agente. Di solito nei giochi esiste un sistema fisico che svolge questo compito per te, valutando il valore di velocità di ciascun oggetto e regolando di conseguenza. Pertanto, possiamo lasciare all'IA un'unica missione: decidere quale velocità debba avere l'agente. Se sappiamo dove deve trovarsi l'agente, dobbiamo muoverlo nella giusta direzione con la velocità stabilita. Un'equazione molto semplice:

desired_travel = destination_position – agent_position

Immagina un mondo 2D. L'agente si trova al punto (-2,-2), la destinazione è da qualche parte a nord-est al punto (30, 20), e il percorso necessario per l'agente per arrivarci è (32, 22). Supponiamo che queste posizioni siano misurate in metri: se prendiamo la velocità dell'agente come 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 si trovava a metà strada verso la meta, il movimento sarebbe stato la metà della lunghezza, ma poiché la velocità massima dell'agente è di 5 m/s (abbiamo stabilito questo in precedenza), la velocità rimarrà la stessa. Questo funziona anche per gli obiettivi in movimento, permettendo all'agente di apportare piccole modifiche man mano che si spostano.

Ma vogliamo maggiore variabilità: ad esempio, aumentare lentamente la velocità per simulare un personaggio che passa da uno stato stazionario a una corsa. Lo stesso può avvenire alla fine prima di fermarsi. Queste funzionalità sono note come behaviour di steering, ognuna delle quali ha nomi specifici: Seek (ricerca), Flee (fuga), Arrival (arrivo) e così via. L'idea è che forze di accelerazione possano essere applicate alla velocità dell'agente, basandosi sul confronto tra la posizione dell'agente e la velocità attuale con il punto di destinazione, per utilizzare vari 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. L'Obstacle Avoidance (evitare ostacoli) e la Separation (separazione) correggono il movimento dell'agente per aggirare gli ostacoli lungo il percorso verso l'obiettivo. L'Alignment (allineamento) e la Cohesion (coesione) mantengono gli agenti in movimento insieme. Un numero qualsiasi di comportamenti di steering diversi può essere sommato per ottenere un unico vettore di percorso tenendo conto di tutti i fattori. Un agente utilizza i comportamenti di Arrival, Separation e Obstacle Avoidance per stare lontano da muri e altri agenti. Questo approccio funziona bene in luoghi aperti senza troppi dettagli.

In condizioni più difficili, la somma di comportamenti diversi funziona peggio: ad esempio, un agente potrebbe bloccarsi contro un muro a causa di un conflitto tra Arrival e Obstacle Avoidance. Pertanto, è necessario considerare opzioni più complesse rispetto alla semplice somma di tutti i valori. Un modo è: invece di sommare i risultati di ogni comportamento, possiamo considerare il movimento in diverse direzioni e scegliere l'opzione migliore.

Tuttavia, in un ambiente complesso con vicoli ciechi e scelta della direzione in cui andare, avremo bisogno di qualcosa di ancora più avanzato.

Ricerca del percorso

I comportamenti di steering sono eccellenti per il semplice movimento in spazi aperti (un campo da calcio o un'arena), dove arrivare da A a B è una linea retta con poche deviazioni da ostacoli. Per percorsi complessi abbiamo bisogno di pathfinding, che è un modo per esplorare il mondo e decidere un percorso attraverso di esso.

Il metodo più semplice consiste nell'applicare una griglia a ogni quadrato adiacente all'agente e valutare in quali di essi è consentito muoversi. Se uno di questi quadrati è il punto di arrivo, segui il percorso da quel quadrato fino al precedente, continuando fino a raggiungere l'inizio. Questo rappresenta il percorso. Altrimenti, ripeti il processo con i quadrati vicini, finché non trovi il punto di arrivo o non ci sono più quadrati disponibili (il che significa che non esiste un percorso possibile). Questo è formalmente noto come Breadth-First Search o BFS (algoritmo di ricerca in ampiezza). A ogni passo, analizza in tutte le direzioni (da qui il termine

Di conseguenza, otterrai un elenco di quadrati che compongono il percorso necessario. Questo è il cammino (da cui pathfinding) — l'elenco dei luoghi che l'agente visiterà seguendo verso il punto di arrivo.

Considerando che conosciamo la posizione di ogni quadrato nel mondo, possiamo utilizzare i comportamenti di guida per muoverci lungo il percorso — da nodo 1 a nodo 2, poi da nodo 2 a nodo 3 e così via. La soluzione più semplice è dirigersi verso il centro del quadrato successivo, ma è ancora meglio fermarsi a metà del bordo tra il quadrato corrente e quello successivo. In questo modo, l'agente può tagliare gli angoli nelle curve più strette.

L'algoritmo BFS ha anche dei lati negativi: esplora tanti quadrati nella “direzione sbagliata” quanto in quella “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, e così via), raccoglie i nodi in un elenco e li ordina in modo che il prossimo nodo esplorato sia sempre quello che porterà al percorso più breve. I nodi sono ordinati in base a un'euristica che considera due fattori: il “costo” del percorso ipotetico verso il quadrato desiderato (inclusi eventuali costi di movimento) e una stima della distanza di quel quadrato dal punto di arrivo (orientando così la ricerca nella direzione corretta).

In questo esempio si mostra che l'agente esplora un quadrato alla volta, scegliendo di volta in volta il più promettente tra i vicini. Il percorso risultante è lo stesso di quello di BFS, ma sono stati considerati meno quadrati durante il processo, il che è fondamentale per le prestazioni del gioco.

Movimento senza griglia

Ma la maggior parte dei giochi non è costruita su una griglia, e spesso non è possibile farlo senza compromettere la realtà. Sono necessari compromessi. Quali dovrebbero essere le dimensioni dei quadrati? Se sono troppo grandi, non riusciranno a rappresentare adeguatamente corridoi stretti o curve; se troppo piccoli, ci saranno troppi quadrati da cercare, il che richiederà molto tempo.

La prima cosa da capire è che la griglia ci fornisce un grafo di nodi collegati. Gli algoritmi A* e BFS funzionano effettivamente su grafi e non si interessano affatto della nostra griglia. Potremmo posizionare i nodi in qualsiasi luogo del mondo di gioco: con una connessione tra qualsiasi due nodi connessi, nonché tra il punto di partenza e quello di arrivo e almeno uno dei nodi, l'algoritmo funzionerà altrettanto bene come prima. Questo è frequentemente chiamato sistema di waypoint, poiché ogni nodo rappresenta una posizione significativa nel mondo, che può far parte di qualsiasi quantità 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 set più piccolo di nodi (waypoint). La ricerca inizia nel quadrato con l'agente, attraversa il numero necessario di nodi e poi prosegue verso la destinazione.

Questo è un sistema piuttosto flessibile e potente. Ma è necessaria un po' di cautela nelle decisioni su dove e come posizionare i waypoint, altrimenti gli agenti potrebbero semplicemente non vedere il punto più vicino e non riuscire ad avviare il percorso. Sarebbe più semplice se potessimo posizionare automaticamente i waypoint in base alla geometria del mondo.

Qui entra in gioco la navigation mesh o navmesh (griglia di navigazione). Di solito è una griglia 2D di triangoli sovrapposta alla geometria del mondo, ovunque sia consentito all'agente muoversi. Ogni triangolo nella griglia diventa un nodo nel grafo e può avere fino a tre triangoli adiacenti, che diventano nodi vicini nel grafo.

Questa immagine è un esempio del motore Unity: ha analizzato la geometria nel mondo e ha creato un navmesh (nella schermata di colore azzurro chiaro). Ogni poligono nel navmesh è un’area su cui un agente può stare o muoversi da un poligono a un altro. In questo esempio, i poligoni sono più piccoli dei piani su cui sono situati, per tenere conto delle dimensioni dell’agente, che uscirà al di fuori della sua posizione nominale.

Possiamo cercare un percorso attraverso questa rete, riutilizzando l’algoritmo A*. Questo ci darà un percorso praticamente ideale nel mondo, che tiene conto di tutta la geometria e non richiede nodi aggiuntivi e creazione di waypoint.

Il pathfinding è un argomento troppo vasto, che non può essere trattato in un solo capitolo di un articolo. Se desideri esplorarlo più a fondo, questo può essere utile sito di Amit Patel.

Pianificazione

Abbiamo appurato con il pathfinding che a volte non basta semplicemente scegliere una direzione e muoversi: dobbiamo selezionare un percorso e fare diverse inversioni per arrivare alla meta desiderata. Possiamo generalizzare questa idea: raggiungere un obiettivo non è solo il passo successivo, ma un'intera sequenza, dove a volte è necessario guardare avanti di alcuni passi per capire quale dovrebbe essere il primo. Questo si chiama pianificazione. Il pathfinding può essere considerato come uno dei tanti complementi alla pianificazione. Dal punto di vista del nostro ciclo Sense / Think / Act, è qui che parte del Think pianifica alcune parti dell'Act per il futuro.

Prendiamo come esempio il gioco di carte Magic: The Gathering. Siamo i primi a giocare con questa mano di carte:

• Palude — fornisce 1 mana nero (carta terreno).
• Foresta — fornisce 1 mana verde (carta terreno).
• Mago Fuggitivo — richiede 1 mana blu per essere evocato.
• Mistico Elfico — richiede 1 mana verde per essere evocato.

Ignoriamo le restanti tre carte per semplificare. Secondo le regole, al giocatore è consentito giocare 1 carta terreno a turno; può "tapparla" per ottenere mana da essa e poi utilizzare incantesimi (incluso evocare creature) in base al mana disponibile. In questa situazione, il giocatore umano sa che deve giocare Foresta, "tappare" 1 mana verde e poi evocare il Mistico Elfico. Ma come può scoprirlo l'IA di gioco?

Pianificazione semplice

Un approccio banale consiste nel provare ogni azione a turno, fino a quando non rimangono opzioni valide. Guardando le carte, l'IA vede che può giocare Swamp. E lo gioca. Ci sono altre azioni rimaste in questo turno? Non può evocare né Elvish Mystic né Fugitive Wizard, poiché per evocare questi ultimi sono richieste rispettivamente mana verde e blu, mentre Swamp fornisce solo mana nera. E non potrà giocare Forest, perché ha già giocato Swamp. Pertanto, l'IA del gioco ha rispettato le regole, ma lo ha fatto male. Si può migliorare.

La pianificazione può trovare un elenco di azioni che portano il gioco nello stato desiderato. Proprio come ogni quadrato del percorso aveva vicini (nella ricerca del percorso), ogni azione nel piano ha anche vicini o successori. Possiamo cercare queste azioni e le azioni successive, fino a quando 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 presa può portare a ulteriori azioni e chiudere altre, ancora una volta a seconda delle regole del gioco. Immagina di aver giocato Swamp — questo rimuoverà Swamp come passo successivo (l'abbiamo già giocato), così come rimuoverà Forest (perché secondo le regole si può giocare una sola carta terra per turno). Dopo di ciò, l'IA aggiunge come passo successivo - ottenere 1 mana nera, perché non ci sono altre opzioni. Se va avanti e sceglie di Tap the Swamp, riceverà 1 unità di mana nera e non potrà fare nulla con essa.

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

L'elenco delle azioni è risultato breve, siamo giunti a un vicolo cieco. Ripetiamo il processo per l'azione successiva. Giocando Forest, sblocchiamo l'azione «ottenere 1 mana verde», che a sua volta sbloccherà la terza azione - evocare Elvish Mystic.

1. Giocare Swamp (risultato: Swamp in gioco)
1.1 «Tappare» Swamp (risultato: Swamp «tappata», +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 azioni possibili 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 alcuni criteri. Di norma, si possono valutare i potenziali piani in base al risultato finale o al guadagno complessivo derivante dalla loro esecuzione. Puoi guadagnare 1 punto per la giocata di una terra e 3 punti per il richiamo di una creatura. Giocare una Swamp sarebbe un piano che fornisce 1 punto. Giocare una Forest → Tap the Forest → evocare un Elvish Mystic darà subito 4 punti.

Ecco come funziona la pianificazione in Magic: The Gathering, ma la stessa logica si applica anche in altre situazioni. Per esempio, muovere un pedone per liberare spazio per il movimento di un alfiere negli scacchi. Oppure nascondersi dietro un muro per sparare in sicurezza in XCOM. In generale, hai capito il concetto.

Pianificazione avanzata

A volte ci sono troppe azioni potenziali per considerare ogni possibile opzione. Ritornando all'esempio di Magic: The Gathering: supponiamo che in gioco tu abbia diverse carte terra e creature in mano; il numero di possibili combinazioni di mosse può contarsi a decine. Ci sono diverse soluzioni a questo problema.

Il primo metodo è il backwards chaining (catena di retrocessione). Invece di esaminare tutte le combinazioni, è meglio partire dal risultato finale e cercare di trovare un percorso diretto. Invece di muoversi dalla radice dell'albero a una foglia specifica, ci spostiamo in direzione opposta: dalla foglia alla radice. Questo metodo è più semplice e veloce.

Se l'avversario ha 1 punto vita, puoi trovare un piano "infliggere 1 o più danni". Per ottenere ciò, è necessario soddisfare una serie di condizioni:

1. Il danno può essere inflitto da un incantesimo — deve essere in mano.
2. Per lanciare l'incantesimo serve mana.
3. Per ottenere mana — bisogna giocare una carta terra.
4. Per giocare una carta terra — bisogna averla in mano.

Un altro metodo è il best-first search (cerca il migliore per primo). Invece di esaminare tutte le strade, scegliamo quella più appropriata. Questo metodo fornisce spesso un piano ottimale senza costi aggiuntivi per la ricerca. L'A* è una forma di ricerca del migliore per primo — esplorando i percorsi più promettenti fin dall'inizio, può già trovare il percorso migliore senza la necessità di esaminare le altre opzioni.

Un'opzione interessante e sempre più popolare della best-first search è la Monte Carlo Tree Search. Invece di indovinare quali piani siano migliori rispetto agli altri nella scelta di ogni successivo passo, l'algoritmo seleziona successori casuali a ogni passo, fino a raggiungere la fine (quando il piano porta a una vittoria o a una sconfitta). Il risultato finale viene utilizzato per aumentare o diminuire la valutazione del 'peso' delle opzioni precedenti. Ripetendo questo processo più volte, l'algoritmo fornisce una buona valutazione di quale sia il passo successivo migliore, anche se la situazione cambia (se l'avversario prende misure per ostacolare il giocatore).

Nella narrazione sulla pianificazione nei giochi non può mancare il Goal-Oriented Action Planning o GOAP (pianificazione delle azioni orientate agli obiettivi). Questo è un metodo ampiamente utilizzato e discusso, ma a parte alcuni dettagli distintivi, è sostanzialmente un metodo di backwards chaining, di cui abbiamo parlato in precedenza. Se l'obiettivo era 'eliminare il giocatore', e il giocatore si trova dietro un riparo, il piano potrebbe essere: lancia una granata → avvicinati → lanciala.

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

Apprendimento e adattamento

Abbiamo già detto che l'IA nei giochi di solito non utilizza l'apprendimento automatico, perché non è adatta alla gestione degli agenti in tempo reale. Ma ciò non significa che non si possano prendere in prestito elementi da questo ambito. Vogliamo un avversario in uno sparatutto dal quale poter imparare qualcosa. Ad esempio, conoscere le migliori posizioni sulla mappa. O un avversario in un picchiaduro che bloccasse le combo frequentemente utilizzate dal giocatore, spingendo a usare altre mosse. Quindi, l'apprendimento automatico in tali situazioni può essere molto utile.

Statistiche e probabilità

Prima di passare a esempi complessi, vediamo fino a che punto possiamo spingerci, prendendo alcune semplici misurazioni e utilizzandole per prendere decisioni. Ad esempio, la strategia in tempo reale: come possiamo determinare se un giocatore può iniziare un attacco nei primi minuti del gioco e quale difesa preparare contro questo? Possiamo studiare l'esperienza passata del giocatore per capire quale potrebbe essere la futura reazione. Cominciamo col dire che non abbiamo tali dati di partenza, ma possiamo raccolgiere — ogni volta che l'IA gioca contro un umano, può registrare il tempo del primo attacco. Dopo alcune sessioni otterremo un valore medio del tempo in cui il giocatore attaccherà in futuro.

Esiste anche un problema con le medie: se un giocatore ha "rushato" 20 volte e ha giocato lentamente 20 volte, i valori necessari saranno da qualche parte nel mezzo, e questo non ci darà nulla di utile. Una delle soluzioni è limitare i dati in ingresso: possiamo considerare le ultime 20 istanze.

Un approccio simile viene utilizzato nella valutazione della probabilità di determinate azioni, assumendo che le preferenze passate del giocatore siano le stesse nel futuro. Se un giocatore ci attacca cinque volte con una palla di fuoco, due volte con una saetta e una volta in corpo a corpo, è evidente che preferisce la palla di fuoco. Estendiamo e vediamo la probabilità di utilizzo di diverse armi: palla di fuoco = 62,5%, saetta = 25% e corpo a corpo = 12,5%. La nostra IA di gioco deve prepararsi a difendersi dal fuoco.

Un altro metodo interessante è l'uso del Naive Bayes Classifier (classificatore bayesiano naive) per analizzare grandi volumi di dati in ingresso e classificare la situazione, affinché l'IA reagisca nel modo corretto. I classificatori bayesiani sono noti principalmente per il loro uso nei filtri antispam delle email. Qui esaminano le parole, le confrontano con quelle che sono apparse in precedenza (nello spam o meno) e traggono conclusioni sui messaggi 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, o quali incantesimi stanno usando, o quali tecnologie hanno ricercato), e il risultato finale (guerra o pace, "rushare" o difendersi, ecc.) — sceglieremo il comportamento appropriato dell'IA.

Tutti questi metodi di apprendimento sono sufficienti, ma è preferibile utilizzarli sulla base dei dati ottenuti dai test. L'IA imparerà ad adattarsi a diverse strategie utilizzate dai vostri playtester. Un'IA che si adatta al giocatore dopo il rilascio può diventare troppo prevedibile o, al contrario, troppo difficile da battere.

Adattamento basato sui valori

Considerando il contenuto del nostro mondo di gioco e delle regole, possiamo modificare l'insieme di valori che influenzano le decisioni, anziché utilizzare semplicemente i dati in ingresso. Procediamo così:

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

Ad esempio, un agente ha diverse stanze tra cui scegliere in una mappa di uno sparatutto in prima persona. Ogni stanza ha un proprio valore che determina quanto sia desiderabile visitarla. L'IA sceglie casualmente quale stanza esplorare, basandosi sul valore. Poi l'agente ricorda in quale stanza è stato ucciso e riduce il valore di quella stanza (la probabilità che vi ritorni). Analogamente, se l'agente distrugge molti nemici, il valore della stanza aumenta.

Modello di Markov

E se utilizzassimo i dati raccolti per fare previsioni? Se memorizziamo ogni stanza in cui vediamo il giocatore per un certo periodo di tempo, potremmo anticipare in quale stanza potrebbe spostarsi. Monitorando e registrando i movimenti del giocatore tra le stanze (valori), possiamo prevederli.

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

Il numero di osservazioni in ogni stanza è quasi uguale — dobbiamo ancora determinare dove creare un buon punto di imboscata. La raccolta delle statistiche è ulteriormente complicata dal respawn dei giocatori, che si presenta uniformemente su tutta la mappa. Ma i dati sulla stanza successiva in cui entrano dopo il respawn sulla mappa sono già utili.

È evidente che la stanza verde soddisfa i giocatori: la maggior parte delle persone dalla stanza rossa si trasferisce lì, il 50% delle quali rimane poi lì. Al contrario, la stanza blu non gode di popolarità, quasi nessuno ci entra, e se lo fa, non si ferma.

Ma i dati ci dicono qualcosa di più importante: quando un giocatore si trova nella stanza blu, la stanza successiva in cui probabilmente lo vedremo sarà rossa, e non verde. Nonostante la stanza verde sia più popolare di quella rossa, la situazione cambia se il giocatore si trova nella blu. Il prossimo stato (cioè la stanza in cui il giocatore si trasferirà) dipende dallo stato precedente (cioè dalla stanza in cui si trova attualmente il giocatore). A causa dello studio delle dipendenze, faremo previsioni più accurate rispetto a se semplicemente conteggiassimo le osservazioni in modo indipendente l'una dall'altra.

Prevedere il futuro stato basandosi sui dati dello stato passato è chiamato modello di Markov (Markov model), e tali esempi (con le stanze) vengono chiamati catene di Markov. Poiché i modelli rappresentano la probabilità di cambiamenti tra stati successivi, vengono visualizzati come un FSM con la probabilità associata a ciascun passaggio. In precedenza, abbiamo usato 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 collegato all'agente o meno. In questo caso, gli stati rappresentano la stanza occupata dall'agente:

Questo è un semplice modo per rappresentare la probabilità relativa dei cambiamenti di stato, offrendo all'IA una certa possibilità di prevedere il prossimo stato. È possibile prevedere diversi passi in avanti.

Se il giocatore è nella stanza verde, c'è il 50% di probabilità che rimanga lì al prossimo rilevamento. Ma qual è la probabilità che lui sia ancora lì anche dopo? Non c'è solo la possibilità che il giocatore sia rimasto nella stanza verde dopo due rilevamenti, ma anche che sia andato via e poi tornato. Ecco una nuova tabella che tiene conto dei nuovi dati:

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

La tabella è semplicemente uno strumento visivo; la procedura richiede solo la moltiplicazione delle probabilità in ogni passaggio. Questo significa che puoi guardare lontano nel futuro con una sola precisazione: presumiamo che la possibilità di entrare in una stanza dipenda interamente dalla stanza attuale. Questo è noto come proprietà di Markov (Markov Property): lo stato futuro dipende solo dal presente. Ma non è garantito al 100%. I giocatori possono cambiare decisioni a seconda di altri fattori: livello di salute o numero di munizioni. Poiché non fissiamo questi valori, le nostre previsioni saranno meno accurate.

N-Grams

E per quanto riguarda l'esempio del fighting e della previsione delle combo del giocatore? È lo stesso! Ma invece di uno stato o di un evento singolo, esploreremo intere sequenze che compongono il colpo combo.

Uno dei modi per farlo è mantenere ogni input (ad esempio, Calcio, Pugno o Blocco) in un buffer e registrare l'intero buffer come un evento. Quindi, se il giocatore preme ripetutamente Calcio, Calcio, Pugno per utilizzare l'attacco SuperDeathFist, il sistema IA memorizza tutti gli input nel buffer e ricorda gli ultimi tre usati in ogni passaggio.

(In grassetto sono evidenziate le righe quando il giocatore lancia l'attacco SuperDeathFist.)

L'IA vedrà tutte le possibilità quando il giocatore sceglie Calcio, seguito da un altro Calcio, per poi notare che il prossimo input è sempre Pugno. Questo consentirà all'agente di prevedere la combo SuperDeathFist e bloccarla se possibile.

Queste sequenze di eventi sono chiamate N-grammi (N-grams), dove N è il numero di elementi memorizzati. Nell'esempio precedente era un trigramma (3-gram), il che significa: i primi due registrazioni sono utilizzate per prevedere la terza. Di conseguenza, in un 5-grammo, le prime quattro registrazioni prevedono la quinta, e così via.

Lo sviluppatore deve scegliere con attenzione la dimensione degli N-grammi. Un numero minore di N richiede meno memoria, ma conserva anche una storia minore. Ad esempio, un bigramma (2-gram) registrerebbe Calcio, Calcio o Calcio, Pugno, ma non potrebbe memorizzare Calcio, Calcio, Pugno, quindi l'IA non reagirebbe alla combo SuperDeathFist.

D'altra parte, numeri maggiori richiedono più memoria e sarà più difficile per l'IA apprendere, poiché ci saranno molte più possibilità. Se hai tre possibili input: Calcio, Pugno o Blocco, e utilizziamo un 10-grammo, avremo circa 60.000 varianti diverse.

Il modello di bigramma è una semplice catena di Markov: ogni coppia "stato passato/stato attuale" è un bigramma e puoi prevedere il secondo stato sulla base del primo. Le 3-grammi e le N-grammi più grandi possono anche essere considerate catene di Markov, dove tutti gli elementi (tranne l'ultimo nella N-gramma) insieme formano il primo stato, e l'ultimo elemento è il secondo. Un esempio con il combattimento mostra la probabilità di transizione dallo stato Calcio e Calcio allo stato Calcio e Pugno. Considerando più registrazioni della storia di ingresso come un'unica unità, in sostanza, trasformiamo la sequenza di ingresso in parte di uno stato intero. Questo ci fornisce la proprietà markoviana, permettendo di utilizzare catene di Markov per prevedere il prossimo input e indovinare quale mossa combinata sarà la prossima.

Conclusione

Abbiamo discusso degli strumenti e degli approcci più diffusi nello sviluppo dell'intelligenza artificiale. Inoltre, abbiamo analizzato le situazioni in cui è necessario applicarli e dove sono particolarmente utili.

Questo dovrebbe essere sufficiente per comprendere le basi dell'IA nei giochi. Ma, naturalmente, non esaurisce tutti i metodi. Tra quelli meno popolari, ma comunque efficaci, ci sono:

• algoritmi di ottimizzazione, tra cui l'ascensione collinare, il gradiente discendente e gli algoritmi genetici
• algoritmi competitivi di ricerca/pianificazione (minimax e potatura alpha-beta)
• metodi di classificazione (percettroni, reti neurali e macchine a vettori di supporto)
• sistemi per l'elaborazione della percezione e della memoria degli agenti
• approcci architettonici all'IA (sistemi ibridi, sottoinsieme di architetture e altri modi di sovrapporre i 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, e inoltre forum.
2. AiGameDev.com contiene numerose presentazioni e articoli su un'ampia gamma 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 anche essere trovati 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 approfondimenti sull'IA nei giochi commerciali.

Libri sull'argomento:

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

Game AI Pro: Saggezza Raccolta dai Professionisti dell'AI nei Giochi
Game AI Pro 2: Saggezza Raccolta dai Professionisti dell'AI nei Giochi
Game AI Pro 3: Saggezza Raccolta dai Professionisti dell'AI nei Giochi

2. La serie AI Game Programming Wisdom è il predecessore della serie Game AI Pro. Contiene metodi più datati, ma quasi tutti sono ancora rilevanti oggi.

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

3. Intelligenza Artificiale: Un Approccio Moderno — è uno dei testi fondamentali per chiunque voglia capire il campo dell'intelligenza artificiale. Non è un libro sulla sviluppo di giochi — insegna le basi dell'IA.

Fonte: habr.com