Algoritmi per il wargame di strategia in tempo reale AI

Question

Sto progettando un wargame di strategia in tempo reale in cui l'IA sarà responsabile del controllo di un gran numero di unità (forse 1000+) su una grande mappa esagonale.

Un'unità ha un numero di punti azione che possono essere spesi in movimento, attaccando unità nemiche o varie azioni speciali (ad esempio costruendo nuove unità). Ad esempio, un carro armato con 5 punti azione potrebbe spendere 3 in movimento e 2 in un nemico in tiro. Diverse unità hanno costi diversi per le diverse azioni, ecc

alcune note aggiuntive:

• L'uscita del AI è un "comando" per ogni data unità
• Le linee di azione sono assegnati all'inizio di un periodo di tempo, ma può essere speso in qualsiasi momento entro il periodo di tempo (questo per consentire giochi in multiplayer in tempo reale). Quindi "non fare nulla e salvare punti azione per dopo" è una tattica potenzialmente valida (ad esempio una torretta di fucili che non può muoversi aspettando che un nemico entri nel poligono)
• Il gioco si sta aggiornando in tempo reale, ma l'IA può ottenere un istantanea coerente dello stato del gioco in qualsiasi momento (grazie allo stato del gioco come una delle strutture dati persistenti di Clojure)
• Non mi aspetto un comportamento "ottimale", solo qualcosa che non sia ovviamente stupido e offra divertimento/sfida ragionevole giocare contro

Cosa si può raccomandare in termini di specifici algoritmi/approcci che consentirebbero il giusto equilibrio tra efficienza e comportamento ragionevolmente intelligente?

Answer 1

Per prima cosa dovresti mirare a rendere il tuo gioco basato su un livello per l'IA (cioè puoi in qualche modo modellarlo a turno anche se potrebbe non essere interamente basato su turni, in RTS potresti essere in grado di rompere gli intervalli discreti di tempo a turno.) In secondo luogo, dovresti determinare la quantità di informazioni con cui l'IA dovrebbe lavorare. Cioè, se all'IA è permesso di imbrogliare e conoscere ogni mossa del suo avversario (rendendolo così più forte) o se dovrebbe conoscere meno o più. Terzo, dovresti definire una funzione di costo di uno stato. L'idea è che un costo più alto significa uno stato peggiore per il computer. Quarto hai bisogno di un generatore di mosse, generando tutti gli stati validi in cui l'AI può passare da un dato stato (questo può essere omogeneo [indipendente dallo stato] o eterogeneo [dipendente dallo stato].)

La cosa è, la funzione di costo sarà fortemente influenzata da ciò che si definisce esattamente lo stato. Più informazioni codificano nello stato, migliore sarà l'IA, più difficile sarà per l'esecuzione, poiché dovrà cercare in modo esponenziale di più per ogni variabile di stato aggiuntiva che includi (in una ricerca esauriente).

Se si fornisce una definizione di uno stato e una funzione di costo, il problema si trasforma in un problema generale nell'intelligenza artificiale che può essere affrontato con qualsiasi algoritmo di propria scelta.

Ecco un riassunto di quello che penso avrebbe funzionato bene:

1. algoritmi evolutivi possono funzionare bene se si mette abbastanza sforzo in loro, ma saranno aggiungere un livello di complessità che creerà spazio per i bug tra le altre cose che possono andare storte. Richiederanno anche quantità estreme di modifica della funzione fitness, ecc. Non ho molta esperienza nel lavorare con questi, ma se sono qualcosa di simile a reti neurali (che ritengo siano entrambe dal punto di vista euristico ispirate a modelli biologici), farai rapidamente trova che sono volubili e tutt'altro che coerenti. Soprattutto, dubito che aggiungano dei vantaggi rispetto all'opzione che descrivo in 3.

2. Con la funzione di costo e lo stato definito sarebbe tecnicamente possibile applicare gradienti decenti (supponendo che la funzione di stato sia differenziabile e il dominio delle variabili di stato sono continui) tuttavia questo probabilmente produrrebbe risultati inferiori, poiché la maggiore debolezza della discesa del gradiente si blocca nei minimi locali. Per fare un esempio, questo metodo sarebbe incline a qualcosa come attaccare il nemico sempre il più presto possibile perché c'è una probabilità non nulla di annientarli. Chiaramente, questo potrebbe non essere un comportamento desiderabile per un gioco, tuttavia, il gradiente decente è un metodo avido e non lo sa meglio.

3. Questa opzione sarebbe la più consigliata: ricottura simulata. La ricottura simulata (IMHO) ha tutti i vantaggi di 1. senza la complessità aggiunta pur essendo molto più robusta di 2. In sostanza, la SA è solo una passeggiata casuale tra gli stati. Quindi oltre al costo e agli stati dovrai definire un modo per passare casualmente tra stati. Inoltre, SA non è incline a rimanere bloccata nei minimi locali, producendo risultati molto buoni in modo abbastanza coerente. L'unico tweaking richiesto con SA sarebbe il programma di raffreddamento - che decide la velocità con cui SA convergerà. Il più grande vantaggio di SA che trovo è che è concettualmente semplice e produce risultati superiori empiricamente alla maggior parte degli altri metodi che ho provato. Informazioni su SA possono essere trovate here con una lunga lista di implementazioni generiche in basso.

3b. (Modifica Aggiunta molto più tardi) SA e le tecniche che ho elencato sopra sono tecniche di IA generali e non molto specializzate per AI per i giochi. In generale, più l'algoritmo è specializzato più possibilità ha di esibirsi meglio. Vedi il Teorema del "Free Lunch" 2. Un'altra estensione di 3 è qualcosa chiamato "tempering parallelo" che migliora notevolmente le prestazioni di SA aiutandole ad evitare l'ottimismo locale. Alcuni dei documenti originali sulla tempera parallela sono piuttosto datati 3, ma altri sono stati aggiornati 4.

Indipendentemente dal metodo scelto alla fine, sarà molto importante suddividere il problema in stati e funzioni di costo come ho detto prima. Come regola generale, inizierei con le variabili di stato 20-50 poiché lo spazio di ricerca dello stato è esponenziale nel numero di queste variabili.

Answer 2

Questa domanda ha una portata enorme. Stai praticamente chiedendo come scrivere un gioco di strategia.

Ci sono tonnellate di libri e articoli online per questa roba. Raccomando caldamente la Saggezza della programmazione di giocoe la serie di saggezza della programmazione di gioco AI . In particolare, la Sezione 6 del primo volume di Sapienza della programmazione dei giochi AI riguarda l'architettura generale, la Sezione 7 riguarda le architetture decisionali e la Sezione 8 riguarda le architetture per generi specifici (8.2 fa il genere RTS).

Answer 3

Se leggi Russell and Norvig, troverai una vasta gamma di algoritmi per tutti gli scopi, aggiornati praticamente allo stato attuale del settore. Detto questo, sono rimasto sbalordito da quante diverse classi di problemi possono essere affrontate con successo con algoritmi bayesiani.

Tuttavia, nel tuo caso penso che sarebbe una cattiva idea che ogni unità abbia il proprio motore di rete o inferenza Petri ... c'è solo così tanta CPU e memoria e tempo a disposizione. Quindi, un approccio diverso:

Mentre in qualche modo forse un pazzo, Stephen Wolfram ha dimostrato che è possibile programmare un comportamento notevolmente complesso su base very simple rules. Si è coraggiosamente estrapolato dal Game of Life alla fisica quantistica e all'intero universo.

Analogamente, molte ricerche su piccoli robot si stanno concentrando su emergent behavior o swarm intelligence. Mentre il classico military strategy e la pratica sono fortemente basati sulle gerarchie, penso che un esercito di combattenti completamente disinteressati e senza paura (come può essere trovato in marcia nel tuo computer) potrebbe essere straordinariamente efficace se opera come cluster auto-organizzanti.

Questo approccio sarebbe probabilmente un po 'meglio con il modello di concorrenza basato su attori di Erlang o di Scala che con lo STM di Clojure: penso che l'auto-organizzazione e gli attori andrebbero insieme molto bene. Tuttavia, potrei immaginare di sfogliare una lista di unità ad ogni turno, e fare in modo che ciascuna unità valuti solo una piccola manciata di regole molto semplici per determinare la sua prossima azione. Sarei molto interessato a sapere se hai provato questo approccio e come è andata!

EDIT

Un'altra cosa che era sul retro della mia mente, ma che scivolato di nuovo mentre stavo scrivendo: Penso che si possono ottenere risultati notevoli da questo approccio se si combinano con genetic o programmazione evolutiva ; Lascia che i tuoi soldatini virtuali si scontrino a vicenda mentre dormi, lascia che codifichino le loro strategie e mischiano, abbinino e mutino il loro codice per quelle strategie; e lascia che un programma arbitrale selezioni i guerrieri di maggior successo.

Ho letto di alcuni sorprendenti successi ottenuti con queste tecniche, con unità operative in modi che non avremmo mai pensato. Ho sentito dire che le IA che lavorano su questi principi hanno dovuto essere intenzionalmente ammutolite per non frustrare gli avversari umani.

Answer 4

È una domanda enorme, e le altre risposte hanno messo in evidenza risorse sorprendenti da esaminare.

Ho affrontato questo problema in passato e ho scoperto che l'approccio comportamentale semplice-comportamentale-complesso/emergente è un po 'troppo ingombrante per la progettazione umana se non si avvicina geneticamente/evolutivamente.

Alla fine ho usato strati astratti di intelligenza artificiale, simili a un modo in cui gli eserciti funzionano nella vita reale. Le unità sarebbero raggruppate con unità vicine dello stesso tempo in squadre, che sono raggruppate con squadre vicine per creare un mini battaglione di sorta. Più strati potrebbero essere usati qui (battaglioni di gruppo in una regione, ecc.), Ma alla fine nella parte superiore c'è l'IA strategica di alto livello.

Ogni livello può solo inviare comandi ai livelli direttamente sotto di esso. Lo strato sottostante cercherà quindi di eseguire il comando con le risorse disponibili (cioè i livelli sotto quel livello).

Un esempio di comando emesso su una singola unità è "Vai qui" e "Spara su questo target". I comandi di livello superiore emessi a livelli più alti sarebbero "sicuri di questa posizione", che quel livello avrebbe elaborato ed emesso i comandi appropriati ai livelli inferiori.

L'intelligenza artificiale di livello più elevato è responsabile di decisioni strategiche del consiglio di amministrazione, ad esempio "abbiamo bisogno di più ____ unità" o "dovremmo mirare a spostarci verso questa posizione".

L'analogia dell'esercito funziona qui; comandanti e luogotenenti e catena di comando.