Mi sono imbattuto in materiale interessante sull'intelligenza artificiale nei giochi. Con una spiegazione degli aspetti fondamentali dell'intelligenza artificiale utilizzando semplici esempi e all'interno ci sono molti strumenti e metodi utili per il suo sviluppo e progettazione convenienti. C'è anche come, dove e quando usarli.
La maggior parte degli esempi sono scritti in pseudocodice, quindi non sono richieste conoscenze di programmazione avanzate. Sotto il taglio ci sono 35 fogli di testo con immagini e gif, quindi preparati.
AGGIORNAMENTO. Mi scuso, ma ho già fatto la mia traduzione di questo articolo su Habré . Puoi leggere la sua versione , ma per qualche motivo l'articolo mi è passato (ho usato la ricerca, ma qualcosa è andato storto). E poiché scrivo su un blog dedicato allo sviluppo di giochi, ho deciso di lasciare la mia versione della traduzione agli abbonati (alcuni punti sono formattati diversamente, altri sono stati deliberatamente omessi su consiglio degli sviluppatori).
Cos'è l'IA?
L'intelligenza artificiale del gioco si concentra su quali azioni un oggetto dovrebbe eseguire in base alle condizioni in cui si trova. Questa è comunemente definita gestione dell'"agente intelligente", dove un agente è un personaggio del giocatore, un veicolo, un bot o talvolta qualcosa di più astratto: un intero gruppo di entità o persino una civiltà. In ogni caso, è una cosa che deve vedere il suo ambiente, prendere decisioni basate su di esso e agire in conformità con esso. Questo è chiamato il ciclo Senso/Pensa/Agisci:
- Senso: l'agente trova o riceve informazioni su cose nel suo ambiente che possono influenzare il suo comportamento (minacce nelle vicinanze, oggetti da raccogliere, luoghi interessanti da esplorare).
- Rifletti: l'agente decide come reagire (considera se è abbastanza sicuro raccogliere oggetti o se deve prima combattere/nascondersi).
- Agire: l'agente esegue 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'intelligenza artificiale tende a concentrarsi sulla parte Senso del ciclo. Ad esempio, le auto autonome scattano foto della strada, le combinano con dati radar e lidar e le interpretano. Questo viene in genere fatto tramite l’apprendimento automatico, che elabora i dati in arrivo e gli dà significato, estraendo informazioni semantiche come “c’è un’altra macchina 20 metri davanti a te”. Questi sono i cosiddetti problemi di classificazione.
I giochi non necessitano di un sistema complesso per estrarre informazioni poiché la maggior parte dei dati ne è già parte integrante. Non è necessario eseguire algoritmi di riconoscimento delle immagini per determinare se c'è un nemico davanti: il gioco lo sa già e inserisce le informazioni direttamente nel processo decisionale. Pertanto, la parte del ciclo Senso è spesso molto più semplice della parte Pensa e agisci.
Limitazioni dell'intelligenza artificiale del gioco
L’intelligenza artificiale presenta una serie di limitazioni che devono essere rispettate:
- L’intelligenza artificiale non ha bisogno di essere addestrata in anticipo, come se fosse un algoritmo di apprendimento automatico. Non ha senso scrivere una rete neurale in fase di sviluppo per monitorare decine di migliaia di giocatori e imparare il modo migliore per giocare contro di loro. Perché? Perché il gioco non è stato rilasciato e non ci sono giocatori.
- Il gioco dovrebbe essere divertente e stimolante, quindi gli agenti non dovrebbero trovare l'approccio migliore contro le persone.
- Gli agenti devono apparire realistici in modo che i giocatori abbiano la sensazione di giocare contro persone reali. Il programma AlphaGo ha sovraperformato gli umani, ma i passaggi scelti erano molto lontani dalla concezione tradizionale del gioco. Se il gioco simula un avversario umano, questa sensazione non dovrebbe esistere. L’algoritmo deve essere modificato in modo che prenda decisioni plausibili piuttosto che ideali.
- L’intelligenza artificiale deve funzionare in tempo reale. Ciò significa che l'algoritmo non può monopolizzare l'utilizzo della CPU per lunghi periodi di tempo per prendere decisioni. Anche 10 millisecondi sono troppo lunghi, perché la maggior parte dei giochi impiega solo dai 16 ai 33 millisecondi per eseguire tutta l'elaborazione e passare al fotogramma grafico successivo.
- Idealmente, almeno una parte del sistema dovrebbe essere basata sui dati, in modo che i non programmatori possano apportare modifiche e gli aggiustamenti possano avvenire più rapidamente.
Diamo un'occhiata agli approcci all'intelligenza artificiale che coprono l'intero ciclo Senso/Pensa/Agisci.
Prendere decisioni di base
Cominciamo con il gioco più semplice: Pong. Obiettivo: muovere la racchetta in modo che la palla rimbalzi su di essa anziché oltrepassarla. È come il tennis, dove perdi se non colpisci la palla. Qui l'IA ha un compito relativamente facile: decidere in quale direzione spostare la piattaforma.
Dichiarazioni condizionali
Per l'IA di Pong la soluzione più 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 racchetta:
spostare la paletta a sinistra
altrimenti se la palla è a destra della racchetta:
spostare la paletta a destra
Se la piattaforma si muove alla velocità della palla, questo è l'algoritmo ideale per l'intelligenza artificiale di Pong. Non è necessario complicare nulla se non ci sono tanti dati e possibili azioni per l'agente.
Questo approccio è così semplice che l’intero ciclo Senso/Pensa/Agisci è appena percettibile. Ma è lì:
- La parte Senso è contenuta in due istruzioni if. Il gioco sa dove si trova la palla e dov'è la piattaforma, quindi l'intelligenza artificiale cerca quell'informazione.
- Anche la parte Think è inclusa nelle due istruzioni if. Esse racchiudono due soluzioni, che in questo caso si escludono a vicenda. Di conseguenza, viene selezionata 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 nelle istruzioni Move Paddle Left e Move Paddle Right. A seconda del design del gioco, possono spostare la piattaforma istantaneamente o ad una velocità specifica.
Tali approcci sono detti reattivi: esiste un semplice insieme di regole (in questo caso le dichiarazioni nel codice) che reagiscono allo stato attuale del mondo e agiscono.
Albero decisionale
L’esempio di Pong è in realtà equivalente a un concetto formale di intelligenza artificiale chiamato albero decisionale. L’algoritmo lo attraversa per raggiungere una “foglia”, ovvero una decisione su quale azione intraprendere.
Realizziamo uno schema a blocchi dell'albero decisionale per l'algoritmo della nostra piattaforma:
Ogni parte dell'albero è chiamata nodo: l'intelligenza artificiale utilizza la teoria dei grafi per descrivere tali strutture. Esistono due tipi di nodi:
- Nodi decisionali: scelta tra due alternative basata sul test di alcune condizioni, dove ciascuna alternativa è rappresentata come un nodo separato.
- Nodi finali: l'azione da eseguire che rappresenta la decisione finale.
L'algoritmo parte dal primo nodo (la “radice” dell'albero). Prende una decisione su quale nodo figlio raggiungere oppure esegue l'azione memorizzata nel nodo ed esce.
Qual è il vantaggio di avere un albero decisionale che svolge lo stesso lavoro delle istruzioni if nella sezione precedente? Esiste un sistema generale in cui ogni decisione ha solo una condizione e due possibili risultati. Ciò consente allo sviluppatore di creare intelligenza artificiale dai dati che rappresentano le decisioni in un albero senza doverlo codificare. Presentiamolo sotto forma di tabella:
Lato codice avrai a disposizione un sistema per la lettura delle stringhe. Crea un nodo per ciascuno di essi, collega la logica decisionale in base alla seconda colonna e i nodi secondari in base alla terza e alla quarta colonna. Devi ancora programmare le condizioni e le azioni, ma ora la struttura del gioco sarà più complessa. Qui puoi aggiungere ulteriori decisioni e azioni, quindi personalizzare l'intera intelligenza artificiale semplicemente modificando il file di testo di definizione dell'albero. Successivamente, trasferisci il file al progettista del gioco, che può modificare il comportamento senza ricompilare il gioco o modificare il codice.
Gli alberi decisionali sono molto utili quando vengono costruiti automaticamente da un ampio insieme di esempi (ad esempio, utilizzando l'algoritmo ID3). Ciò li rende uno strumento efficace e performante per classificare le situazioni in base ai dati ottenuti. Tuttavia, andiamo oltre un semplice sistema in cui gli agenti possono selezionare le azioni.
scenari
Abbiamo analizzato un sistema ad albero decisionale che utilizzava condizioni e azioni pre-create. Chi progetta l’IA può organizzare l’albero come vuole, ma deve comunque fare affidamento sul programmatore che ha programmato il tutto. E se potessimo dare al designer gli strumenti per creare le proprie condizioni o azioni?
Affinché il programmatore non debba scrivere codice per le condizioni Is Ball Left Of Paddle e Is Ball Right Of Paddle, può creare un sistema in cui il progettista scriverà le condizioni per verificare questi valori. Quindi i dati dell'albero decisionale appariranno così:
Questo è essenzialmente lo stesso della prima tabella, ma le soluzioni al loro interno hanno il proprio codice, un po' come la 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 vero o falso di conseguenza. Questo viene fatto utilizzando il linguaggio di scripting Lua o Angelscript. Usandoli, uno sviluppatore può prendere oggetti nel suo gioco (palla e racchetta) e creare variabili che saranno disponibili nello script (palla.posizione). Inoltre, il linguaggio di scripting è più semplice del C++. Non richiede una fase di compilazione completa, quindi è ideale per adattare rapidamente la logica del gioco e consente ai "non programmatori" di creare da soli le funzioni necessarie.
Nell'esempio sopra, il linguaggio di scripting viene utilizzato solo per valutare l'espressione condizionale, ma può essere utilizzato anche per le azioni. Ad esempio, i dati Move Paddle Right potrebbero diventare un'istruzione di script (ball.position.x += 10). In modo che l'azione sia definita anche nello script, senza la necessità di programmare Move Paddle Right.
Puoi andare ancora oltre e scrivere l'intero albero decisionale in un linguaggio di scripting. Questo sarà codice sotto forma di istruzioni condizionali hardcoded, ma si troveranno in file di script esterni, ovvero potranno essere modificati senza ricompilare l'intero programma. Spesso puoi modificare il file di script durante il gioco per testare rapidamente diverse reazioni dell'IA.
Risposta agli eventi
Gli esempi sopra sono perfetti per Pong. Eseguono continuamente il ciclo Senso/Pensa/Agisci e agiscono in base allo stato più recente del mondo. Ma nei giochi più complessi è necessario reagire ai singoli eventi e non valutare tutto in una volta. Pong in questo caso è già un cattivo esempio. Scegliamone un'altro.
Immagina uno sparatutto in cui i nemici restano immobili finché non rilevano il giocatore, dopodiché agiscono a seconda della loro “specializzazione”: qualcuno correrà per “correre”, qualcuno attaccherà da lontano. È ancora un sistema reattivo di base - "se un giocatore viene individuato, fai qualcosa" - ma può essere logicamente suddiviso in un evento Giocatore visto e una Reazione (seleziona una risposta ed eseguila).
Questo ci riporta al ciclo Senso/Pensa/Agisci. Possiamo codificare una parte Sense che controllerà in ogni fotogramma se l'IA vede il giocatore. In caso contrario, non succede nulla, ma se vede, viene creato l'evento Player Seen. Il codice avrà una sezione separata che dice "quando si verifica l'evento visto dal giocatore, fai" dove è la risposta necessaria per affrontare le parti Pensa e agisci. Pertanto, imposterai le reazioni all'evento Player Seen: per il personaggio "impetuoso" - ChargeAndAttack e per il cecchino - HideAndSnipe. Queste relazioni possono essere create nel file di dati per una modifica rapida senza dover ricompilare. Anche in questo caso è possibile utilizzare il linguaggio di scripting.
Prendere decisioni difficili
Sebbene i sistemi di reazione semplici siano molto potenti, ci sono molte situazioni in cui non sono sufficienti. A volte è necessario prendere decisioni diverse in base a ciò che l'agente sta attualmente facendo, ma è difficile immaginarlo come una condizione. A volte ci sono troppe condizioni per rappresentarle efficacemente in un albero decisionale o in uno script. A volte è necessario valutare in anticipo come cambierà la situazione prima di decidere il passo successivo. Per risolvere questi problemi sono necessari approcci più sofisticati.
Macchina a stati finiti
La macchina a stati finiti o FSM (macchina a stati finiti) è un modo per dire che il nostro agente si trova attualmente in uno dei diversi stati possibili e che può passare da uno stato all'altro. Esiste un certo numero di tali stati, da cui il nome. Il miglior esempio dalla vita è un semaforo. Esistono diverse sequenze di luci in luoghi diversi, ma il principio è lo stesso: ogni stato rappresenta qualcosa (fermarsi, camminare, ecc.). Un semaforo si trova in un solo stato alla volta e si sposta da uno all'altro in base a regole semplici.
È una storia simile con gli NPC nei giochi. Ad esempio, prendiamo una guardia con i seguenti stati:
- Pattugliamento.
- Attaccare.
- In fuga.
E queste condizioni per cambiare il suo stato:
- Se la guardia vede il nemico, attacca.
- Se la guardia attacca ma non vede più il nemico, torna in pattuglia.
- Se una guardia attacca ma viene gravemente ferita, scappa.
Puoi anche scrivere istruzioni if con una variabile di stato del guardiano e vari controlli: c'è un nemico nelle vicinanze, qual è il livello di salute dell'NPC, ecc. Aggiungiamo qualche altro stato:
- Ozio - tra le pattuglie.
- Ricerca: quando il nemico notato è scomparso.
- Trovare aiuto: quando un nemico viene individuato, ma è troppo forte per combattere da solo.
La scelta per ciascuno di essi è limitata: ad esempio, la guardia non andrà alla ricerca di un nemico nascosto se ha poca salute.
Dopotutto, c'è una lunga lista di "se" , Quello " può diventare troppo macchinoso, quindi dobbiamo formalizzare un metodo che ci permetta di tenere a mente gli stati e le transizioni tra stati. Per fare ciò, prendiamo in considerazione tutti gli stati e sotto ogni stato annotiamo in un elenco tutte le transizioni verso altri stati, insieme alle condizioni per esse necessarie.
Questa è una tabella di transizione tra stati: un modo completo per rappresentare FSM. Disegniamo un diagramma e otteniamo una panoramica completa di come cambia il comportamento degli NPC.
Il diagramma riflette l'essenza del processo decisionale per questo agente in base alla situazione attuale. Inoltre, ciascuna freccia mostra una transizione tra stati se la condizione accanto ad essa è vera.
Ad ogni aggiornamento controlliamo lo stato corrente dell'agente, esaminiamo l'elenco delle transizioni e, se le condizioni per la transizione sono soddisfatte, accetta il nuovo stato. Ad esempio, ogni frame controlla se il timer di 10 secondi è scaduto e, in tal caso, la guardia passa dallo stato di inattività allo stato di pattugliamento. Allo stesso modo, lo stato di attacco controlla la salute dell'agente: se è bassa, passa allo stato di fuga.
Si tratta di gestire le transizioni tra stati, ma per quanto riguarda il comportamento associato agli stati stessi? In termini di implementazione del comportamento effettivo per un particolare stato, in genere esistono due tipi di "hook" in cui assegniamo azioni all'FSM:
- Azioni che eseguiamo periodicamente per lo stato attuale.
- Le azioni che intraprendiamo quando passiamo da uno stato all’altro.
Esempi per il primo tipo. Lo stato Pattugliamento sposterà l'agente lungo il percorso di pattugliamento in ogni fotogramma. Lo stato di attacco tenterà di avviare un attacco a ogni fotogramma o di transizione a uno stato in cui ciò è possibile.
Per il secondo tipo, considera la transizione “se il nemico è visibile e il nemico è troppo forte, vai allo stato Trova aiuto. L'agente deve scegliere dove chiedere aiuto e archiviare queste informazioni in modo che lo stato Ricerca aiuto sappia dove andare. Una volta trovato aiuto, l'agente torna allo stato di attacco. A questo punto, vorrà dire all'alleato della minaccia, quindi potrebbe verificarsi l'azione NotifyFriendOfThreat.
Ancora una volta, possiamo guardare questo sistema attraverso la lente del ciclo Senso/Pensa/Agisci. Il senso è incarnato nei dati utilizzati dalla logica di transizione. Pensa: transizioni disponibili in ogni stato. E l'atto viene eseguito mediante azioni eseguite periodicamente all'interno di uno stato o durante le transizioni tra stati.
A volte il polling continuo delle condizioni di transizione può essere costoso. Ad esempio, se ogni agente esegue calcoli complessi in ogni fotogramma per determinare se può vedere i nemici e capire se può passare dallo stato di pattuglia allo stato di attacco, ciò richiederà molto tempo della CPU.
Importanti cambiamenti nello stato del mondo possono essere considerati come eventi che verranno elaborati man mano che si verificano. Invece di far sì che l'FSM controlli la condizione di transizione "il mio agente può vedere il giocatore?" ad ogni frame, è possibile configurare un sistema separato per controllare meno frequentemente (ad esempio 5 volte al secondo). E il risultato è che il giocatore viene visto quando il controllo viene superato.
Questo viene passato all'FSM, che ora dovrebbe andare alla condizione di ricezione dell'evento visto dal giocatore e rispondere di conseguenza. Il comportamento risultante è lo stesso tranne che per un ritardo quasi impercettibile prima della risposta. Ma le prestazioni sono migliorate come risultato della separazione della parte Sense in una parte separata del programma.
Macchina gerarchica a stati finiti
Tuttavia, lavorare con grandi FSM non è sempre conveniente. Se vogliamo espandere lo stato di attacco per separare Attacco in mischia e Attacco a distanza, dovremo modificare le transizioni da tutti gli altri stati che portano allo stato di Attacco (attuale e futuro).
Probabilmente hai notato che nel nostro esempio ci sono molte transizioni duplicate. La maggior parte delle transizioni nello stato Inattivo sono identiche alle transizioni nello stato Pattugliamento. Sarebbe bello non ripeterci, soprattutto se aggiungiamo altri stati simili. Ha senso raggruppare Inattività e Pattugliamento sotto l'etichetta generale di "non combattimento", dove esiste un solo insieme comune di transizioni agli stati di combattimento. Se pensiamo a questa etichetta come a uno stato, allora Idling e Patrolling diventano sottostati. Un esempio di utilizzo di una tabella di transizione separata per un nuovo sottostato non di combattimento:
Stati principali:
Stato fuori combattimento:
E in forma di diagramma:
È lo stesso sistema, ma con un nuovo stato di non combattimento che include Inattività e Pattugliamento. Con ogni stato contenente una FSM con sottostati (e questi sottostati, a loro volta, contenenti le proprie FSM - e così via per tutto il tempo necessario), otteniamo una macchina a stati finiti gerarchica o HFSM (macchina a stati finiti gerarchica). Raggruppando lo stato di non combattimento, abbiamo eliminato una serie di transizioni ridondanti. Possiamo fare lo stesso per tutti i nuovi stati con transizioni comuni. Ad esempio, se in futuro espandessimo lo stato di Attacco agli stati Attacco in mischia e Attacco missilistico, saranno sottostati che transiteranno tra loro in base alla distanza dal nemico e alla disponibilità di munizioni. Di conseguenza, comportamenti e sottocomportamenti complessi possono essere rappresentati con un minimo di transizioni duplicate.
Albero del comportamento
Con HFSM si creano combinazioni complesse di comportamenti in modo semplice. Tuttavia, vi è una leggera difficoltà nel fatto che il processo decisionale sotto forma di norme di transizione sia strettamente correlato allo stato attuale. E in molti giochi questo è esattamente ciò di cui hai bisogno. E un uso attento della gerarchia statale può ridurre il numero di ripetizioni della transizione. Ma a volte hai bisogno di regole che funzionino indipendentemente dallo stato in cui ti trovi, o che si applichino in quasi tutti gli stati. Ad esempio, se la salute di un agente scende al 25%, vorrai che scappi indipendentemente dal fatto che fosse in combattimento, inattivo o parlando: dovrai aggiungere questa condizione a ciascuno stato. E se in seguito il tuo progettista desidera modificare la soglia di salute bassa dal 25% al 10%, sarà necessario farlo di nuovo.
Idealmente, questa situazione richiede un sistema in cui le decisioni su “in quale stato trovarsi” siano al di fuori degli stati stessi, in modo da apportare modifiche solo in un luogo e non toccare le condizioni di transizione. Gli alberi di comportamento vengono visualizzati qui.
Esistono diversi modi per implementarli, ma l’essenza è più o meno la stessa per tutti ed è simile a un albero decisionale: l’algoritmo inizia con un nodo “radice” e l’albero contiene nodi che rappresentano decisioni o azioni. Ci sono però alcune differenze fondamentali:
- I nodi ora restituiscono uno dei tre valori: Succeeded (se il lavoro è stato completato), Failed (se non può essere avviato) o Running (se è ancora in esecuzione e non c'è alcun risultato finale).
- Non ci sono più nodi decisionali per scegliere tra due alternative. Sono invece nodi Decoratori, che hanno un nodo figlio. Se hanno successo, eseguono il loro unico nodo figlio.
- I nodi che eseguono azioni restituiscono un valore Running per rappresentare le azioni eseguite.
Questo piccolo insieme di nodi può essere combinato per creare un gran numero di comportamenti complessi. Immaginiamo la guardia HFSM dell'esempio precedente come un albero di comportamento:
Con questa struttura non dovrebbe esserci alcuna transizione ovvia dallo stato di Inattività/Pattugliamento allo stato di Attacco o qualsiasi altro stato. Se un nemico è visibile e la salute del personaggio è bassa, l'esecuzione si fermerà al nodo Fuga, indipendentemente da quale nodo stava eseguendo in precedenza: Pattugliamento, Inattività, Attacco o qualsiasi altro.
Gli alberi di comportamento sono complessi: esistono molti modi per comporli e trovare la giusta combinazione di decoratori e nodi composti può essere difficile. Ci sono anche domande sulla frequenza con cui controllare l'albero: vogliamo esaminarlo in ogni sua parte o solo quando una delle condizioni è cambiata? Come memorizziamo lo stato relativo ai nodi: come facciamo a sapere quando siamo rimasti inattivi per 10 secondi o come facciamo a sapere quali nodi erano in esecuzione l'ultima volta in modo da poter elaborare correttamente la sequenza?
Questo è il motivo per cui ci sono molte implementazioni. Ad esempio, alcuni sistemi hanno sostituito i nodi decoratori con decoratori in linea. Rivalutano l'albero quando cambiano le condizioni del decoratore, aiutano a unire i nodi e forniscono aggiornamenti periodici.
Sistema basato sull'utilità
Alcuni giochi hanno molte meccaniche diverse. È auspicabile che ricevano tutti i vantaggi delle regole di transizione semplici e generali, ma non necessariamente sotto forma di un albero di comportamento completo. Invece di avere un insieme chiaro di scelte o un albero di possibili azioni, è più semplice esaminare tutte le azioni e scegliere quella più appropriata al momento.
Il sistema basato su Utilità aiuterà proprio in questo. Si tratta di un sistema in cui l'agente ha una varietà di azioni e sceglie quali eseguire in base all'utilità relativa di ciascuna. Dove l'utilità è una misura arbitraria di quanto sia importante o desiderabile per l'agente eseguire tale azione.
L'utilità calcolata di un'azione in base allo stato e all'ambiente corrente, l'agente può verificare e selezionare l'altro stato più appropriato in qualsiasi momento. Questo è simile alla FSM, tranne per il fatto che le transizioni sono determinate da una stima per ogni stato potenziale, compreso quello attuale. Tieni presente che scegliamo l'azione più utile per andare avanti (o restare se l'abbiamo già completata). Per una maggiore varietà, questa potrebbe essere una selezione equilibrata ma casuale da un piccolo elenco.
Il sistema assegna un intervallo arbitrario di valori di utilità, ad esempio da 0 (del tutto indesiderabile) a 100 (del tutto desiderabile). Ogni azione ha una serie di parametri che influenzano il calcolo di questo valore. Ritornando all'esempio del nostro tutore:
Le transizioni tra le azioni sono ambigue: qualsiasi stato può seguirne un altro. Le priorità delle azioni si trovano nei valori di utilità restituiti. Se un nemico è visibile, e quel nemico è forte, e la salute del personaggio è bassa, sia Fleeing che FindingHelp restituiranno valori alti diversi da zero. In questo caso, FindingHelp sarà sempre più alto. Allo stesso modo, le attività non di combattimento non restituiscono mai più di 50, quindi saranno sempre inferiori a quelle di combattimento. È necessario tenerne conto 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 restituirebbe una stima da un intervallo continuo di valori. Ad esempio, l'azione di Fuga restituisce valori di utilità più elevati se la salute dell'agente è bassa, mentre l'azione di Attacco restituisce valori di utilità inferiori se il nemico è troppo forte. Per questo motivo, l'azione Fuga ha la precedenza sull'Attacco in qualsiasi situazione in cui l'agente ritiene di non avere abbastanza salute per sconfiggere il nemico. Ciò consente di dare priorità alle 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 il calcolo del programma. Possono essere scritti in linguaggio di scripting o come una serie di formule matematiche. The Sims, che simula la routine quotidiana del personaggio, aggiunge un ulteriore livello di calcolo: l'agente riceve una serie di "motivazioni" che influenzano le valutazioni di utilità. Se un personaggio ha fame, diventerà ancora più affamato nel tempo e il valore di utilità dell'azione MangiaCibo aumenterà finché il personaggio non la eseguirà, riducendo il livello di fame e riportando il valore MangiaCibo a zero.
L’idea di selezionare le azioni in base a un sistema di valutazione è abbastanza semplice, quindi un sistema basato su Utilità può essere utilizzato come parte dei processi decisionali dell’IA, piuttosto che come loro completo sostituto. L'albero decisionale può richiedere una valutazione di utilità di due nodi figli e selezionare quello più alto. Allo stesso modo, un albero dei comportamenti può avere un nodo Utilità composito per valutare l'utilità delle azioni e decidere quale 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 degli agenti in un periodo di tempo? Come impostiamo la velocità, come evitiamo gli ostacoli e come pianifichiamo un percorso quando raggiungere una destinazione è più difficile che spostarsi semplicemente in linea retta? Diamo un'occhiata a questo.
Управление
Nella fase iniziale, assumeremo che ciascun agente abbia un valore di velocità, che include la velocità con cui si muove e in quale direzione. Può essere misurato in metri al secondo, chilometri all'ora, pixel al secondo, ecc. Ricordando il ciclo Senso/Pensa/Agisci, possiamo immaginare che la parte Pensa selezioni una velocità e la parte Agi applichi quella velocità all'agente. In genere i giochi hanno un sistema fisico che svolge questo compito per te, apprendendo il valore di velocità di ciascun oggetto e regolandolo. Pertanto, puoi lasciare all'IA un compito: decidere quale velocità dovrebbe avere l'agente. Se sai dove dovrebbe trovarsi l'agente, devi spostarlo nella giusta direzione a una velocità prestabilita. Un'equazione molto banale:
viaggio_desiderato = posizione_destinazione – posizione_agente
Immagina un mondo 2D. L'agente è nel punto (-2,-2), la destinazione è da qualche parte a nord-est nel punto (30, 20) e il percorso richiesto dall'agente per arrivarci è (32, 22). Diciamo che queste posizioni sono misurate in metri: se consideriamo la velocità dell'agente pari a 5 metri al secondo, scaleremo il nostro vettore di spostamento e otterremo una velocità di circa (4.12, 2.83). Con questi parametri l'agente arriverebbe a destinazione in quasi 8 secondi.
Puoi ricalcolare i valori in qualsiasi momento. Se l'agente fosse a metà strada dal bersaglio, il movimento sarebbe lungo la metà, ma poiché la velocità massima dell'agente è 5 m/s (lo abbiamo deciso sopra), la velocità sarà la stessa. Funziona anche per i bersagli in movimento, consentendo all'agente di apportare piccole modifiche mentre si muovono.
Ma vogliamo più variazione, ad esempio aumentando lentamente la velocità per simulare un personaggio che si muove da fermo a correre. Lo stesso si può fare alla fine prima di fermarsi. Queste caratteristiche sono conosciute come comportamenti di guida, ognuno dei quali ha nomi specifici: Cerca, Fuggi, Arrivo, ecc. L'idea è che le forze di accelerazione possono essere applicate alla velocità dell'agente, in base al confronto della posizione dell'agente e della velocità attuale con la destinazione in per utilizzare diversi metodi per raggiungere l'obiettivo.
Ogni comportamento ha uno scopo leggermente diverso. La ricerca e l'arrivo sono modi per spostare un agente verso una destinazione. L'evitamento degli ostacoli e la separazione regolano il movimento dell'agente per evitare gli ostacoli sulla strada verso l'obiettivo. Allineamento e coesione mantengono gli agenti in movimento insieme. È possibile sommare qualsiasi numero di comportamenti di sterzata diversi per produrre un unico vettore di percorso che tenga conto di tutti i fattori. Un agente che utilizza i comportamenti Arrivo, Separazione ed Evitamento ostacoli per stare lontano dai muri e da altri agenti. Questo approccio funziona bene in luoghi aperti senza dettagli inutili.
In condizioni più difficili, l'aggiunta di comportamenti diversi funziona peggio: ad esempio, un agente può rimanere bloccato in un muro a causa di un conflitto tra Arrivo ed Evitamento degli ostacoli. Pertanto, è necessario considerare opzioni più complesse rispetto alla semplice somma di tutti i valori. Il modo è questo: invece di sommare i risultati di ciascun comportamento, puoi considerare il movimento in diverse direzioni e scegliere l'opzione migliore.
Tuttavia, in un ambiente complesso, pieno di vicoli ciechi e di scelte sulla strada da percorrere, avremo bisogno di qualcosa di ancora più avanzato.
Trovare la strada
I comportamenti di sterzata sono ottimi per i movimenti semplici in un'area aperta (campo di calcio o arena) dove spostarsi da A a B è un percorso rettilineo con solo piccole deviazioni attorno agli ostacoli. Per percorsi complessi, abbiamo bisogno del pathfinding, che è un modo di esplorare il mondo e decidere un percorso attraverso di esso.
Il più semplice è applicare una griglia a ciascun quadrato accanto all'agente e valutare quale di essi può muoversi. Se uno di essi è una destinazione, segui il percorso da ogni casella a quella precedente fino a raggiungere l'inizio. Questo è il percorso. Altrimenti, ripeti il processo con altri quadrati vicini finché non trovi la tua destinazione o finisci i quadrati (il che significa che non esiste un percorso possibile). Questo è ciò che è formalmente noto come Breadth-First Search o BFS (algoritmo di ricerca in ampiezza). Ad ogni passo guarda in tutte le direzioni (da qui larghezza, "larghezza"). Lo spazio di ricerca è come un fronte d'onda che si muove fino a raggiungere la posizione desiderata: lo spazio di ricerca si espande ad ogni passo fino a includere il punto finale, dopodiché è possibile risalire all'inizio.
Di conseguenza, riceverai un elenco di quadrati lungo i quali viene compilato il percorso desiderato. Questo è il percorso (da qui, pathfinding): un elenco di luoghi che l'agente visiterà mentre segue la destinazione.
Dato che conosciamo la posizione di ogni quadrato nel mondo, possiamo usare comportamenti di guida per muoverci lungo il percorso: dal nodo 1 al nodo 2, poi dal nodo 2 al nodo 3 e così via. L'opzione più semplice è dirigersi verso il centro del quadrato successivo, ma un'opzione ancora migliore è fermarsi al centro del bordo tra il quadrato attuale e quello successivo. Per questo motivo, l'agente sarà in grado di tagliare gli angoli nelle curve strette.
L'algoritmo BFS presenta anche degli svantaggi: esplora tanti quadrati nella direzione "sbagliata" quanti nella direzione "giusta". È qui che entra in gioco un algoritmo più complesso chiamato A* (A stella). Funziona allo stesso modo, ma invece di esaminare ciecamente i quadrati vicini (quindi vicini di vicini, poi vicini di vicini di vicini e così via), raccoglie i nodi in un elenco e li ordina in modo che il nodo successivo esaminato sia sempre quello quello che porta al percorso più breve. I nodi vengono ordinati in base a un'euristica che tiene conto di due cose: il "costo" di un ipotetico percorso verso il quadrato desiderato (inclusi eventuali costi di viaggio) e una stima di quanto quel quadrato è distante dalla destinazione (distorcendo la ricerca nel riquadro). giusta direzione).
Questo esempio mostra che l'agente esplora un quadrato alla volta, scegliendo ogni volta quello adiacente che è il più promettente. Il percorso risultante è lo stesso di BFS, ma nel processo sono stati considerati meno quadrati, il che ha un grande impatto sulle prestazioni del gioco.
Movimento senza griglia
Ma la maggior parte dei giochi non sono disposti su una griglia, e spesso è impossibile farlo senza sacrificare il realismo. Sono necessari compromessi. Che dimensioni dovrebbero avere i quadrati? Troppo grandi e non saranno in grado di rappresentare correttamente piccoli corridoi o svolte, troppo piccoli e ci saranno troppi quadrati da cercare, il che alla fine richiederà molto tempo.
La prima cosa da capire è che una mesh ci fornisce un grafico di nodi connessi. Gli algoritmi A* e BFS funzionano effettivamente sui grafici e non si preoccupano affatto della nostra mesh. Potremmo mettere i nodi ovunque nel mondo di gioco: finché c'è una connessione tra due nodi qualsiasi collegati, così come tra i punti iniziale e finale e almeno uno dei nodi, l'algoritmo funzionerà altrettanto bene di 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 ipotetici percorsi.
Esempio 1: un nodo in ogni quadrato. La ricerca inizia dal nodo dove si trova l'agente e termina al nodo della piazza desiderata.
Esempio 2: un insieme più piccolo di nodi (waypoint). La ricerca inizia nella piazza dell'agente, attraversa il numero richiesto di nodi e poi continua fino alla destinazione.
Questo è un sistema completamente flessibile e potente. Ma è necessaria una certa attenzione nel decidere dove e come posizionare un punto di passaggio, altrimenti gli agenti potrebbero semplicemente non vedere il punto più vicino e non essere in grado di iniziare il percorso. Sarebbe più semplice se potessimo posizionare automaticamente i punti di passaggio in base alla geometria del mondo.
Qui è dove appare la mesh di navigazione o navmesh (mesh di navigazione). Di solito si tratta di una mesh 2D di triangoli sovrapposti alla geometria del mondo, ovunque l'agente possa camminare. Ciascuno dei triangoli nella mesh diventa un nodo nel grafico e ha fino a tre triangoli adiacenti che diventano nodi adiacenti nel grafico.
Questa immagine è un esempio del motore Unity: ha analizzato la geometria del mondo e creato un navmesh (nello screenshot in azzurro). Ogni poligono in una navmesh è un'area in cui un agente può sostare o spostarsi da un poligono a un altro poligono. In questo esempio, i poligoni sono più piccoli dei piani su cui si trovano: questo viene fatto per tenere conto delle dimensioni dell'agente, che si estenderà oltre la sua posizione nominale.
Possiamo cercare un percorso attraverso questa mesh, sempre utilizzando l'algoritmo A*. Questo ci darà un percorso quasi perfetto nel mondo, che terrà conto di tutta la geometria e non richiederà nodi inutili e la creazione di waypoint.
Il pathfinding è un argomento troppo ampio per il quale una sezione di un articolo non è sufficiente. Se vuoi studiarlo più in dettaglio, questo ti aiuterà .
pianificazione
Con il pathfinding abbiamo imparato che a volte non è sufficiente scegliere semplicemente una direzione e muoversi: dobbiamo scegliere un percorso e fare qualche svolta per raggiungere la destinazione desiderata. Possiamo generalizzare questa idea: il raggiungimento di un obiettivo non è solo il passo successivo, ma un'intera sequenza in cui a volte è necessario guardare avanti diversi passaggi per scoprire quale dovrebbe essere il primo. Questa si chiama pianificazione. Il pathfinding può essere considerato una delle numerose estensioni della pianificazione. In termini del nostro ciclo Senso/Pensa/Agisci, è qui che la parte Pensa pianifica più parti Agisci per il futuro.
Diamo un'occhiata all'esempio del gioco da tavolo Magic: The Gathering. Iniziamo con il seguente set di carte in mano:
- Palude: fornisce 1 mana nero (carta terra).
- Foresta: dà 1 mana verde (carta terra).
- Mago fuggitivo: richiede 1 mana blu per essere evocato.
- Elfo Mistico: richiede 1 mana verde per essere evocato.
Ignoriamo le restanti tre carte per renderlo più semplice. Secondo le regole, un giocatore può giocare 1 carta terra per turno, può "taccare" questa carta per estrarne mana e poi lanciare incantesimi (inclusa l'evocazione di una creatura) in base alla quantità di mana. In questa situazione, il giocatore umano sa che deve giocare Foresta, tappare 1 mana verde e poi evocare Elvish Mystic. Ma come può l’intelligenza artificiale del gioco capirlo?
Pianificazione semplice
L'approccio banale è provare ogni azione a turno finché non ne rimangono più adatte. Guardando le carte, l’IA vede cosa può giocare Swamp. E lo suona. Ci sono altre azioni rimaste in questo turno? Non può evocare né Elvish Mystic né Fugitive Wizard, poiché richiedono rispettivamente mana verde e blu per evocarli, mentre Swamp fornisce solo mana nero. E non potrà più giocare alla Foresta, perché ha già giocato alla Palude. Pertanto, l'IA del gioco ha seguito le regole, ma lo ha fatto male. Può essere migliorato.
La pianificazione può trovare un elenco di azioni che portano il gioco allo stato desiderato. Proprio come ogni casella di un percorso ha dei vicini (nel pathfinding), anche ogni azione in un piano ha dei vicini o successori. Possiamo cercare queste azioni e le azioni successive fino a raggiungere lo stato desiderato.
Nel nostro esempio, il risultato desiderato è “evoca una creatura se possibile”. All'inizio del turno vediamo solo due possibili azioni consentite dalle regole del gioco:
1. Gioca a Swamp (risultato: Swamp nel gioco)
2. Gioca a Forest (risultato: Forest nel gioco)
Ogni azione intrapresa può portare ad ulteriori azioni e chiuderne altre, sempre a seconda delle regole del gioco. Immagina di aver giocato a Palude: questo rimuoverà la Palude come passo successivo (l'abbiamo già giocato), e rimuoverà anche la Foresta (perché secondo le regole puoi giocare una carta terra per turno). Successivamente, l'IA aggiunge come passaggio successivo l'ottenimento di 1 mana nero perché non ci sono altre opzioni. Se va avanti e sceglie Tocca la Palude, riceverà 1 unità di mana nero e non potrà farci nulla.
1. Gioca a Swamp (risultato: Swamp nel gioco)
1.1 Palude “TAP” (risultato: Palude “tappata”, +1 unità di mana nero)
Nessuna azione disponibile - FINE
2. Gioca a Forest (risultato: Forest nel gioco)
L'elenco delle azioni era breve, siamo arrivati a un vicolo cieco. Ripetiamo il processo per il passaggio successivo. Giochiamo a Forest, apriamo l'azione "ottieni 1 mana verde", che a sua volta aprirà la terza azione: evoca Elvish Mystic.
1. Gioca a Swamp (risultato: Swamp nel gioco)
1.1 Palude “TAP” (risultato: Palude “tappata”, +1 unità di mana nero)
Nessuna azione disponibile - FINE
2. Gioca a Forest (risultato: Forest nel gioco)
2.1 Foresta “TAP” (risultato: la foresta è “TAPATA”, +1 unità di mana verde)
2.1.1 Evoca Elvish Mystic (risultato: Elvish Mystic in gioco, -1 mana verde)
Nessuna azione disponibile - FINE
Alla fine, abbiamo esplorato tutte le possibili azioni e trovato un piano che evocasse una creatura.
Questo è un esempio molto semplificato. È consigliabile scegliere il miglior piano possibile, piuttosto che un piano qualsiasi che soddisfi alcuni criteri. In genere è possibile valutare i potenziali piani in base al risultato o al beneficio complessivo della loro attuazione. Puoi ottenere 1 punto giocando una carta terra e 3 punti evocando una creatura. Giocare a Swamp sarebbe un piano da 1 punto. E giocare a Foresta → Tocca la foresta → evoca Elvish Mystic darà immediatamente 4 punti.
È così che funziona la pianificazione in Magic: The Gathering, ma la stessa logica si applica in altre situazioni. Ad esempio, spostare un pedone per fare spazio all'alfiere per muoversi negli scacchi. Oppure riparati dietro un muro per sparare in sicurezza in XCOM in questo modo. In generale, hai un'idea.
Pianificazione migliorata
A volte ci sono troppe azioni potenziali per considerare ogni opzione possibile. Tornando all'esempio di Magic: The Gathering: diciamo che nel gioco e nella tua mano ci sono diverse carte terra e creatura: il numero di possibili combinazioni di mosse può essere dell'ordine delle dozzine. Esistono diverse soluzioni al problema.
Il primo metodo è il concatenamento all'indietro. Invece di provare tutte le combinazioni, è meglio partire dal risultato finale e cercare di trovare una via diretta. Invece di andare dalla radice dell'albero a una foglia specifica, ci muoviamo nella direzione opposta: dalla foglia alla radice. Questo metodo è più semplice e veloce.
Se il nemico ha 1 salute, puoi trovare il piano "infliggi 1 o più danni". Per raggiungere questo obiettivo è necessario che siano soddisfatte una serie di condizioni:
1. Il danno può essere causato da un incantesimo: deve essere in mano.
2. Per lanciare un incantesimo, hai bisogno di mana.
3. Per ottenere mana, devi giocare una carta terra.
4. Per giocare una carta terra, devi averla in mano.
Un altro modo è la ricerca best-first. Invece di provare tutte le strade, scegliamo quella più adatta. Molto spesso, questo metodo fornisce il piano ottimale senza costi di ricerca inutili. A* è una forma di prima ricerca migliore: esaminando fin dall'inizio i percorsi più promettenti, può già trovare il percorso migliore senza dover verificare altre opzioni.
Un'opzione di ricerca best-first interessante e sempre più popolare è Monte Carlo Tree Search. Invece di indovinare quali piani sono migliori degli altri quando si sceglie ogni azione successiva, l’algoritmo sceglie successori casuali in ogni passaggio fino a raggiungere la fine (quando il piano ha portato alla vittoria o alla sconfitta). Il risultato finale viene quindi utilizzato per aumentare o diminuire il peso delle opzioni precedenti. Ripetendo questo processo più volte di seguito, l'algoritmo fornisce una buona stima di quale sarà la migliore mossa successiva, anche se la situazione cambia (se il nemico interviene per interferire con il giocatore).
Nessuna storia sulla pianificazione nei giochi sarebbe completa senza la pianificazione dell'azione orientata agli obiettivi o GOAP (pianificazione dell'azione orientata agli obiettivi). Questo è un metodo ampiamente utilizzato e discusso, ma a parte alcuni dettagli distintivi, è essenzialmente il metodo di concatenamento all'indietro di cui abbiamo parlato prima. Se l'obiettivo fosse "distruggere il giocatore" e il giocatore è al riparo, il piano potrebbe essere: distruggere con una granata → prendila → lanciala.
Di solito ci sono diversi obiettivi, ciascuno con la propria priorità. Se l'obiettivo con la priorità più alta non può essere completato (nessuna combinazione di azioni crea un piano "uccidi il giocatore" perché il giocatore non è visibile), l'IA tornerà agli obiettivi con priorità inferiore.
Formazione e adattamento
Abbiamo già detto che l'intelligenza artificiale dei giochi solitamente non utilizza il machine learning perché non è adatta a gestire gli agenti in tempo reale. Ma questo non significa che non puoi prendere in prestito qualcosa da quest'area. Vogliamo un avversario in uno sparatutto da cui possiamo imparare qualcosa. Scopri ad esempio le migliori posizioni sulla mappa. O un avversario in un gioco di combattimento che blocca le mosse combo usate di frequente dal giocatore, motivandolo a usarne altre. Quindi l’apprendimento automatico può essere molto utile in tali situazioni.
Statistiche e probabilità
Prima di addentrarci in 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 determiniamo se un giocatore può lanciare un attacco nei primi minuti di gioco e quale difesa preparare contro questo? Possiamo studiare le esperienze passate di un giocatore per capire quali potrebbero essere le reazioni future. Per cominciare, non disponiamo di questi dati grezzi, ma possiamo raccoglierli: ogni volta che l'IA gioca contro un essere umano, può registrare l'ora del primo attacco. Dopo alcune sessioni, otterremo una media del tempo necessario al giocatore per attaccare in futuro.
C'è anche un problema con i valori medi: se un giocatore si è precipitato 20 volte e ha giocato lentamente 20 volte, i valori richiesti saranno da qualche parte nel mezzo e questo non ci darà nulla di utile. Una soluzione è limitare i dati di input: possono essere presi in considerazione gli ultimi 20 pezzi.
Un approccio simile viene utilizzato quando si stima la probabilità di determinate azioni presupponendo che le preferenze passate del giocatore saranno le stesse in futuro. Se un giocatore ci attacca cinque volte con la palla di fuoco, due volte con il fulmine e una volta con il corpo a corpo, è ovvio che preferisce la palla di fuoco. Estrapoliamo e vediamo la probabilità di utilizzare armi diverse: palla di fuoco=62,5%, fulmine=25% e corpo a corpo=12,5%. L'intelligenza artificiale del nostro gioco deve prepararsi a proteggersi dal fuoco.
Un altro metodo interessante è utilizzare il Naive Bayes Classifier per studiare grandi quantità di dati di input e classificare la situazione in modo che l’IA reagisca nel modo desiderato. I classificatori bayesiani sono conosciuti soprattutto per il loro utilizzo nei filtri antispam della posta elettronica. Lì esaminano le parole, le confrontano con dove sono apparse prima (nello spam o meno) e traggono conclusioni sulle e-mail in arrivo. Possiamo fare la stessa cosa anche con meno input. Sulla base di tutte le informazioni utili che l'IA vede (come ad esempio quali unità nemiche vengono create, o quali incantesimi usano, o quali tecnologie hanno ricercato) e il risultato finale (guerra o pace, corsa o difesa, ecc.) - Sceglieremo il comportamento AI desiderato.
Tutti questi metodi di allenamento sono sufficienti, ma è consigliabile utilizzarli sulla base dei dati dei test. L'IA imparerà ad adattarsi alle diverse strategie utilizzate dai tuoi playtester. L'IA che si adatta al giocatore dopo il rilascio potrebbe diventare troppo prevedibile o troppo difficile da sconfiggere.
Adattamento basato sul valore
Considerando il contenuto del nostro mondo di gioco e le regole, possiamo modificare l’insieme di valori che influenzano il processo decisionale, anziché utilizzare semplicemente i dati di input. Facciamo questo:
- Lascia che l'IA raccolga dati sullo stato del mondo e sugli eventi chiave durante il gioco (come sopra).
- Modifichiamo alcuni valori importanti in base a questi dati.
- Implementiamo le nostre decisioni basandoci sull'elaborazione o sulla valutazione di questi valori.
Ad esempio, un agente ha diverse stanze tra cui scegliere su una mappa sparatutto in prima persona. Ogni stanza ha il suo valore, che determina quanto sia desiderabile visitarla. L'IA sceglie casualmente in quale stanza andare in base al valore. L'agente poi ricorda in quale stanza è stato ucciso e ne riduce il valore (la probabilità che ritorni lì). Allo stesso modo per la situazione inversa: se l'agente distrugge molti avversari, il valore della stanza aumenta.
Modello markoviano
E se utilizzassimo i dati raccolti per fare previsioni? Se ricordiamo ogni stanza in cui vediamo un giocatore per un certo periodo di tempo, prediremo in quale stanza il giocatore potrebbe andare. Tracciando e registrando i movimenti del giocatore attraverso le stanze (valori), possiamo prevederli.
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 in ogni stanza è quasi uguale: non sappiamo ancora dove creare un buon posto per un'imboscata. La raccolta delle statistiche è complicata anche dal respawn dei giocatori, che appaiono in modo uniforme su tutta la mappa. Ma i dati sulla stanza successiva in cui entrano dopo essere apparsi sulla mappa sono già utili.
Si può vedere che la stanza verde si adatta ai giocatori: la maggior parte delle persone si sposta dalla stanza rossa ad essa, il 50% delle quali rimane lì ulteriormente. La sala blu, invece, non è frequentata, non ci va quasi nessuno e, se ci va, non ci resta molto.
Ma i dati ci dicono qualcosa di più importante: quando un giocatore è in una stanza blu, la stanza successiva in cui lo vedremo sarà rossa, non verde. Anche se la stanza verde è più popolare di quella rossa, la situazione cambia se il giocatore si trova nella stanza blu. Lo stato successivo (ovvero la stanza in cui andrà il giocatore) dipende dallo stato precedente (ovvero la stanza in cui si trova attualmente il giocatore). Poiché esploriamo le dipendenze, faremo previsioni più accurate che se contassimo semplicemente le osservazioni in modo indipendente.
La previsione di uno stato futuro sulla base dei dati di uno stato passato è chiamata modello di Markov e tali esempi (con stanze) sono chiamati catene di Markov. Poiché i modelli rappresentano la probabilità di cambiamenti tra stati successivi, vengono visualizzati visivamente come FSM con una probabilità attorno a ciascuna transizione. In precedenza, utilizzavamo la FSM per rappresentare lo stato comportamentale in cui si trovava un agente, ma questo concetto si estende a qualsiasi stato, indipendentemente dal fatto che sia associato o meno all'agente. In questo caso, gli stati rappresentano la stanza occupata dall'agente:
Questo è un modo semplice per rappresentare la probabilità relativa dei cambiamenti di stato, dando all’intelligenza artificiale una certa capacità di prevedere lo stato successivo. Puoi anticipare diversi passi avanti.
Se un giocatore si trova nella stanza verde, c'è una probabilità del 50% che rimarrà lì la prossima volta che verrà osservato. Ma quali sono le probabilità che sarà ancora lì anche dopo? Non solo esiste la possibilità che il giocatore sia rimasto nella stanza verde dopo due osservazioni, ma esiste anche la possibilità che se ne sia andato e sia tornato. Ecco la nuova tabella che tiene conto dei nuovi dati:
Ciò dimostra che la probabilità di vedere il giocatore nella stanza verde dopo due osservazioni sarà pari al 51% - 21% che verrà dalla stanza rossa, 5% che il giocatore visiterà la stanza blu tra di loro, e Il 25% che il giocatore non lascerà la green room.
La tabella è semplicemente uno strumento visivo: la procedura richiede solo la moltiplicazione delle probabilità ad ogni passaggio. Ciò significa che puoi guardare lontano nel futuro con un avvertimento: presupponiamo che la possibilità di entrare in una stanza dipenda interamente dalla stanza attuale. Questa è chiamata proprietà di Markov: lo stato futuro dipende solo dal presente. Ma questo non è accurato al XNUMX%. I giocatori possono cambiare 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-grammi
Che ne dici dell'esempio di un gioco di combattimento e della previsione delle mosse combo del giocatore? Lo stesso! Ma invece di uno stato o evento, esamineremo l'intera sequenza che costituisce un colpo combinato.
Un modo per farlo è memorizzare ogni input (come Kick, Punch o Block) in un buffer e scrivere l'intero buffer come evento. Quindi il giocatore preme ripetutamente Kick, Kick, Punch per utilizzare l'attacco SuperDeathFist, il sistema AI memorizza tutti gli input in un buffer e ricorda gli ultimi tre utilizzati in ogni passaggio.
(Le linee in grassetto indicano quando il giocatore lancia l'attacco SuperDeathFist.)
L'IA vedrà tutte le opzioni quando il giocatore seleziona Calcio, seguito da un altro Calcio, e poi noterà che l'input successivo è sempre Pugno. Ciò consentirà all'agente di prevedere la mossa combinata di 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 3 grammi (trigramma), il che significa: le prime due voci vengono utilizzate per prevedere la terza. Di conseguenza, in un 5 grammi, le prime quattro voci predicono la quinta e così via.
Il progettista deve scegliere attentamente la dimensione degli N grammi. Un N più piccolo richiede meno memoria ma memorizza anche meno cronologia. Ad esempio, un 2 grammi (bigram) registrerà Kick, Kick o Kick, Punch, ma non sarà in grado di memorizzare Kick, Kick, Punch, quindi l'IA non risponderà alla combo SuperDeathFist.
D'altra parte, numeri più grandi richiedono più memoria e l'IA sarà più difficile da addestrare poiché ci saranno molte più opzioni possibili. Se avessimo tre possibili input di Calcio, Pugno o Blocco, e usassimo un 10 grammi, ci sarebbero circa 60mila opzioni diverse.
Il modello bigramma è una semplice catena di Markov: ogni coppia stato passato/stato attuale è un bigramma ed è possibile prevedere il secondo stato in base al primo. Gli N-grammi da 3 grammi e più grandi possono anche essere pensati come catene di Markov, dove tutti gli elementi (tranne l'ultimo nell'N-gramma) insieme formano il primo stato e l'ultimo elemento il secondo. L'esempio del gioco di combattimento mostra la possibilità di passare dallo stato Calcio e calcio allo stato Calcio e pugno. Trattando più voci della cronologia di input come una singola unità, stiamo essenzialmente trasformando la sequenza di input in parte dell'intero stato. Questo ci dà la proprietà di Markov, che ci consente di utilizzare le catene di Markov per prevedere l'input successivo e indovinare quale sarà la prossima mossa combinata.
conclusione
Abbiamo parlato degli strumenti e degli approcci più comuni nello sviluppo dell'intelligenza artificiale. Abbiamo anche esaminato le situazioni in cui devono essere utilizzati e dove sono particolarmente utili.
Questo dovrebbe essere sufficiente per comprendere le basi dell'intelligenza artificiale del gioco. Ma, ovviamente, questi non sono tutti i metodi. Meno popolari, ma non per questo meno efficaci includono:
- algoritmi di ottimizzazione tra cui arrampicata in collina, discesa del gradiente e algoritmi genetici
- algoritmi di ricerca/programmazione contraddittori (minimax e potatura alfa-beta)
- metodi di classificazione (percettroni, reti neurali e macchine a vettori di supporto)
- sistemi di elaborazione della percezione e della memoria degli agenti
- approcci architetturali all'intelligenza artificiale (sistemi ibridi, architetture di sottoinsiemi e altri modi di sovrapporre i sistemi di intelligenza artificiale)
- strumenti di animazione (pianificazione e coordinamento del movimento)
- fattori di prestazione (livello di dettaglio, in qualsiasi momento e algoritmi di suddivisione temporale)
Risorse correlate:
1. GameDev.net ha e .
2. contiene molte presentazioni e articoli su una vasta gamma di argomenti relativi allo sviluppo dell'intelligenza artificiale dei giochi.
3. include argomenti del GDC AI Summit, molti dei quali sono disponibili gratuitamente.
4. Sul sito web si possono trovare anche materiali utili .
5. Tommy Thompson, ricercatore di intelligenza artificiale e sviluppatore di giochi, realizza video su YouTube con una spiegazione e uno studio dell'intelligenza artificiale nei giochi commerciali.
Libri sull'argomento:
1. La serie di libri Game AI Pro è una raccolta di brevi articoli che spiegano come implementare funzionalità specifiche o come risolvere problemi specifici.
2. La serie AI Game Programming Wisdom è il predecessore della serie Game AI Pro. Contiene metodi più vecchi, ma quasi tutti sono rilevanti anche oggi.
3. è uno dei testi fondamentali per tutti coloro che vogliono comprendere il campo generale dell'intelligenza artificiale. Questo non è un libro sullo sviluppo di giochi: insegna le basi dell'intelligenza artificiale.
Fonte: habr.com