Jeg kom over noe interessant materiale om kunstig intelligens i spill. Med en forklaring på grunnleggende ting om AI ved hjelp av enkle eksempler, og inne er det mange nyttige verktøy og metoder for praktisk utvikling og design. Hvordan, hvor og når du skal bruke dem er også der.
De fleste eksemplene er skrevet i pseudokode, så det kreves ingen avansert programmeringskunnskap. Under kuttet er det 35 tekstark med bilder og gifs, så gjør deg klar.
UPD. Jeg beklager, men jeg har allerede gjort min egen oversettelse av denne artikkelen på Habré . Du kan lese hans versjon , men av en eller annen grunn gikk artikkelen meg forbi (jeg brukte søket, men noe gikk galt). Og siden jeg skriver på en blogg dedikert til spillutvikling, bestemte jeg meg for å overlate min versjon av oversettelsen til abonnenter (noen punkter er formatert annerledes, noen ble bevisst utelatt etter råd fra utviklerne).
Hva er AI?
Game AI fokuserer på hvilke handlinger et objekt skal utføre basert på forholdene det befinner seg i. Dette blir ofte referert til som "intelligent agent" ledelse, der en agent er en spillerkarakter, et kjøretøy, en bot eller noen ganger noe mer abstrakt: en hel gruppe enheter eller til og med en sivilisasjon. I hvert tilfelle er det en ting som må se omgivelsene sine, ta avgjørelser basert på det og handle i samsvar med dem. Dette kalles Sense/Think/Act-syklusen:
- Sense: Agenten finner eller mottar informasjon om ting i miljøet som kan påvirke oppførselen (trusler i nærheten, gjenstander å samle, interessante steder å utforske).
- Tenk: Agenten bestemmer hvordan han skal reagere (vurderer om det er trygt nok å samle gjenstander eller om han skal slåss/gjemme seg først).
- Handle: agenten utfører handlinger for å implementere den forrige beslutningen (begynner å bevege seg mot fienden eller objektet).
- ...nå har situasjonen endret seg på grunn av handlingene til karakterene, så syklusen gjentas med nye data.
AI har en tendens til å fokusere på Sense-delen av loopen. For eksempel tar autonome biler bilder av veien, kombinerer dem med radar- og lidardata og tolker dem. Dette gjøres vanligvis ved maskinlæring, som behandler innkommende data og gir det mening, og trekker ut semantisk informasjon som "det er en annen bil 20 yards foran deg." Dette er de såkalte klassifiseringsproblemene.
Spill trenger ikke et komplekst system for å trekke ut informasjon siden mesteparten av dataene allerede er en integrert del av den. Det er ikke nødvendig å kjøre bildegjenkjenningsalgoritmer for å finne ut om det er en fiende foran – spillet kjenner allerede og mater informasjonen direkte inn i beslutningsprosessen. Derfor er Sense-delen av syklusen ofte mye enklere enn Think and Act-delen.
Begrensninger for Game AI
AI har en rekke begrensninger som må overholdes:
- AI trenger ikke trenes på forhånd, som om det var en maskinlæringsalgoritme. Det gir ingen mening å skrive et nevralt nettverk under utvikling for å overvåke titusenvis av spillere og lære den beste måten å spille mot dem. Hvorfor? Fordi spillet ikke er utgitt og det er ingen spillere.
- Spillet skal være morsomt og utfordrende, så agenter bør ikke finne den beste tilnærmingen mot folk.
- Agenter må se realistiske ut slik at spillerne føler at de spiller mot ekte mennesker. AlphaGo-programmet ga bedre resultater enn mennesker, men trinnene som ble valgt var veldig langt fra den tradisjonelle forståelsen av spillet. Hvis spillet simulerer en menneskelig motstander, burde ikke denne følelsen eksistere. Algoritmen må endres slik at den tar plausible beslutninger i stedet for ideelle.
- AI må fungere i sanntid. Dette betyr at algoritmen ikke kan monopolisere CPU-bruk i lange perioder for å ta avgjørelser. Til og med 10 millisekunder er for lenge, fordi de fleste spill trenger bare 16 til 33 millisekunder for å gjøre all prosessering og gå videre til neste grafikkramme.
- Ideelt sett bør i det minste en del av systemet være datadrevet, slik at ikke-kodere kan gjøre endringer og justeringer kan skje raskere.
La oss se på AI-tilnærminger som dekker hele Sense/Think/Act-syklusen.
Ta grunnleggende avgjørelser
La oss starte med det enkleste spillet - Pong. Mål: flytt åren slik at ballen spretter av den i stedet for å fly forbi den. Det er som tennis, hvor du taper hvis du ikke treffer ballen. Her har AI en relativt enkel oppgave - å bestemme i hvilken retning plattformen skal flyttes.
Betingede uttalelser
For AI i Pong er den mest åpenbare løsningen å alltid prøve å plassere plattformen under ballen.
En enkel algoritme for dette, skrevet i pseudokode:
hver frame/oppdatering mens spillet kjører:
hvis ballen er til venstre for åren:
flytt padlen til venstre
ellers hvis ballen er til høyre for åren:
flytt padle til høyre
Hvis plattformen beveger seg med ballens hastighet, er dette den ideelle algoritmen for AI i Pong. Det er ikke nødvendig å komplisere noe hvis det ikke er så mye data og mulige handlinger for agenten.
Denne tilnærmingen er så enkel at hele Sense/Think/Act-syklusen knapt er merkbar. Men det er der:
- Sense-delen er i to hvis-utsagn. Spillet vet hvor ballen er og hvor plattformen er, så AI ser etter den informasjonen.
- Tenk-delen er også inkludert i de to if-utsagnene. De inneholder to løsninger, som i dette tilfellet utelukker hverandre. Som et resultat er en av tre handlinger valgt - flytt plattformen til venstre, flytt den til høyre, eller gjør ingenting hvis den allerede er riktig plassert.
- Akt-delen finnes i setningene Move Paddle Left og Move Paddle Right. Avhengig av spilldesignet kan de flytte plattformen umiddelbart eller med en bestemt hastighet.
Slike tilnærminger kalles reaktive - det er et enkelt sett med regler (i dette tilfellet hvis uttalelser i koden) som reagerer på den nåværende tilstanden i verden og tar affære.
Beslutningstre
Pong-eksemplet tilsvarer faktisk et formelt AI-konsept kalt et beslutningstre. Algoritmen går gjennom den for å nå et "blad" - en beslutning om hva som skal gjøres.
La oss lage et blokkdiagram av beslutningstreet for algoritmen til plattformen vår:
Hver del av treet kalles en node – AI bruker grafteori for å beskrive slike strukturer. Det er to typer noder:
- Beslutningsnoder: å velge mellom to alternativer basert på testing av en tilstand, hvor hvert alternativ er representert som en egen node.
- Sluttnoder: Handlingen som skal utføres som representerer den endelige avgjørelsen.
Algoritmen starter fra den første noden ("roten" til treet). Den tar enten en beslutning om hvilken underordnet node den skal gå til, eller den utfører handlingen som er lagret i noden og avslutter.
Hva er fordelen med å la et beslutningstre gjøre den samme jobben som hvis-utsagnene i forrige avsnitt? Det er et generelt system her hvor hver avgjørelse kun har én betingelse og to mulige utfall. Dette lar utvikleren lage AI fra data som representerer beslutninger i et tre uten å måtte hardkode det. La oss presentere det i tabellform:
På kodesiden vil du få et system for å lese strenger. Lag en node for hver av dem, koble til beslutningslogikk basert på den andre kolonnen, og underordnede noder basert på den tredje og fjerde kolonnen. Du må fortsatt programmere betingelsene og handlingene, men nå vil strukturen til spillet være mer kompleks. Her legger du til flere avgjørelser og handlinger, og deretter tilpasser du hele AI ved ganske enkelt å redigere tredefinisjonstekstfilen. Deretter overfører du filen til en spilldesigner, som kan endre atferden uten å rekompilere spillet eller endre koden.
Beslutningstrær er svært nyttige når de bygges automatisk fra et stort sett med eksempler (for eksempel ved å bruke ID3-algoritmen). Dette gjør dem til et effektivt og høyytelsesverktøy for å klassifisere situasjoner basert på innhentede data. Vi går imidlertid lenger enn et enkelt system for agenter til å velge handlinger.
Scenarier
Vi analyserte et beslutningstresystem som brukte forhåndslagrede forhold og handlinger. Personen som designer AI kan organisere treet slik han vil, men han må fortsatt stole på koderen som programmerte alt. Hva om vi kunne gi designeren verktøyene til å skape sine egne forhold eller handlinger?
For at programmereren ikke trenger å skrive kode for betingelsene Is Ball Left Of Paddle og Is Ball Right Of Paddle, kan han lage et system der designeren vil skrive betingelser for å sjekke disse verdiene. Da vil beslutningstredataene se slik ut:
Dette er i hovedsak det samme som i den første tabellen, men løsningene i seg selv har sin egen kode, litt som den betingede delen av en if-setning. På kodesiden vil dette leses i den andre kolonnen for beslutningsnodene, men i stedet for å se etter en spesifikk betingelse som skal utføres (Er Ball Left Of Paddle), evaluerer den det betingede uttrykket og returnerer sant eller usant tilsvarende. Dette gjøres ved å bruke skriptspråket Lua eller Angelscript. Ved å bruke dem kan en utvikler ta objekter i spillet sitt (ball og padle) og lage variabler som vil være tilgjengelige i skriptet (ball.position). Dessuten er skriptspråket enklere enn C++. Det krever ikke et fullstendig kompileringsstadium, så det er ideelt for raskt å justere spilllogikken og lar "ikke-kodere" lage de nødvendige funksjonene selv.
I eksemplet ovenfor brukes skriptspråket kun for å evaluere det betingede uttrykket, men det kan også brukes til handlinger. For eksempel kan dataene Move Paddle Right bli en skriptsetning (ball.position.x += 10). Slik at handlingen også er definert i scriptet, uten behov for å programmere Move Paddle Right.
Du kan gå enda lenger og skrive hele beslutningstreet på et skriptspråk. Dette vil være kode i form av hardkodede betingede setninger, men de vil ligge i eksterne skriptfiler, det vil si at de kan endres uten å rekompilere hele programmet. Du kan ofte redigere skriptfilen under spilling for raskt å teste forskjellige AI-responser.
Event Response
Eksemplene ovenfor er perfekte for Pong. De kjører kontinuerlig Sense/Think/Act-syklusen og handler basert på den nyeste tilstanden i verden. Men i mer komplekse spill må du reagere på individuelle hendelser, og ikke evaluere alt på en gang. Pong i dette tilfellet er allerede et dårlig eksempel. La oss velge en annen.
Se for deg et skytespill hvor fiendene er ubevegelige til de oppdager spilleren, hvoretter de handler avhengig av deres "spesialisering": noen vil løpe for å "rushe", noen vil angripe langveisfra. Det er fortsatt et grunnleggende reaktivt system - "hvis en spiller blir oppdaget, gjør noe" - men det kan logisk deles inn i en spiller sett hendelse og en reaksjon (velg et svar og utfør det).
Dette bringer oss tilbake til Sense/Think/Act-syklusen. Vi kan kode en Sense-del som vil sjekke hver frame om AI ser spilleren. Hvis ikke, skjer ingenting, men hvis den ser, opprettes Player Seen-hendelsen. Koden vil ha en egen del som sier "når Player Seen-hendelsen inntreffer, gjør" hvor er svaret du trenger for å ta tak i Think og Act-delene. Dermed vil du sette opp reaksjoner på Player Seen-hendelsen: for den "rushende" karakteren - ChargeAndAttack, og for snikskytteren - HideAndSnipe. Disse relasjonene kan opprettes i datafilen for rask redigering uten å måtte rekompilere. Skriptspråk kan også brukes her.
Ta vanskelige avgjørelser
Selv om enkle reaksjonssystemer er svært kraftige, er det mange situasjoner hvor de ikke er nok. Noen ganger må du ta forskjellige beslutninger basert på hva agenten gjør for øyeblikket, men det er vanskelig å forestille seg dette som en betingelse. Noen ganger er det for mange forhold til å representere dem effektivt i et beslutningstre eller et manus. Noen ganger må du på forhånd vurdere hvordan situasjonen vil endre seg før du bestemmer deg for neste trinn. Mer sofistikerte tilnærminger er nødvendig for å løse disse problemene.
Endelig tilstandsmaskin
Finite state machine eller FSM (finite state machine) er en måte å si at vår agent for øyeblikket er i en av flere mulige tilstander, og at den kan gå over fra en tilstand til en annen. Det er et visst antall slike stater - derav navnet. Det beste eksemplet fra livet er et trafikklys. Det er forskjellige sekvenser av lys på forskjellige steder, men prinsippet er det samme - hver tilstand representerer noe (stopp, gå, etc.). Et trafikklys er kun i én tilstand til enhver tid, og beveger seg fra ett til et annet basert på enkle regler.
Det er en lignende historie med NPC-er i spill. La oss for eksempel ta en vakt med følgende tilstander:
- Patruljerer.
- Angriper.
- Flykter.
Og disse betingelsene for å endre tilstanden:
- Hvis vakten ser fienden, angriper han.
- Hvis vakten angriper, men ikke lenger ser fienden, går han tilbake for å patruljere.
- Hvis en vakt angriper, men blir hardt såret, løper han bort.
Du kan også skrive hvis-utsagn med en vergetilstandsvariabel og ulike kontroller: er det en fiende i nærheten, hva er helsenivået til NPC osv. La oss legge til noen flere tilstander:
- Lediggang - mellom patruljer.
- Søker - når den oppdagede fienden har forsvunnet.
- Finne hjelp - når en fiende blir oppdaget, men er for sterk til å kjempe alene.
Valget for hver av dem er begrenset - for eksempel vil vakten ikke lete etter en skjult fiende hvis han har dårlig helse.
Tross alt er det en enorm liste over "hvis" , Det " kan bli for tungvint, så vi må formalisere en metode som lar oss ha tilstander og overganger mellom stater i tankene. For å gjøre dette tar vi hensyn til alle statene, og under hver stat skriver vi ned i en liste alle overgangene til andre stater, sammen med betingelsene som er nødvendige for dem.
Dette er en tilstandsovergangstabell - en omfattende måte å representere FSM på. La oss tegne et diagram og få en fullstendig oversikt over hvordan NPC-atferd endres.
Diagrammet gjenspeiler essensen av beslutningstaking for denne agenten basert på den nåværende situasjonen. Dessuten viser hver pil en overgang mellom tilstander hvis betingelsen ved siden av er sann.
Hver oppdatering sjekker vi den nåværende tilstanden til agenten, ser gjennom listen over overganger, og hvis betingelsene for overgangen er oppfylt, godtar den den nye tilstanden. For eksempel sjekker hver ramme om 10-sekunders-timeren har utløpt, og i så fall går vakten fra tomgangstilstand til patruljering. På samme måte kontrollerer den Angripende staten agentens helse - hvis den er lav, går den inn i den flyktende staten.
Dette er å håndtere overganger mellom stater, men hva med oppførselen knyttet til statene selv? Når det gjelder implementering av den faktiske oppførselen for en bestemt stat, er det vanligvis to typer "krok" der vi tildeler handlinger til FSM:
- Handlinger som vi utfører med jevne mellomrom for gjeldende tilstand.
- Handlingene vi tar når vi går fra en stat til en annen.
Eksempler for den første typen. Patruljeringstilstanden vil flytte agenten langs patruljeruten hver ramme. Angripende tilstand vil forsøke å starte et angrep hver frame eller overgang til en tilstand der dette er mulig.
For den andre typen, vurder overgangen "hvis fienden er synlig og fienden er for sterk, så gå til Finnehjelp-tilstanden. Agenten må velge hvor han skal henvende seg for å få hjelp og lagre denne informasjonen slik at Finding Help-statusen vet hvor den skal gå. Når hjelp er funnet, går agenten tilbake til den angripende staten. På dette tidspunktet vil han fortelle den allierte om trusselen, slik at NotifyFriendOfThreat-handlingen kan oppstå.
Nok en gang kan vi se på dette systemet gjennom linsen til Sense/Think/Act-syklusen. Sense er nedfelt i dataene som brukes av overgangslogikken. Tenk - overganger tilgjengelig i hver stat. Og handling utføres av handlinger som utføres periodisk i en stat eller ved overganger mellom stater.
Noen ganger kan det være kostbart med overgangsforhold for kontinuerlig polling. For eksempel, hvis hver agent utfører komplekse beregninger hver ramme for å avgjøre om den kan se fiender og forstå om den kan gå over fra patruljerende til angripende tilstand, vil dette ta mye CPU-tid.
Viktige endringer i verdens tilstand kan betraktes som hendelser som vil bli behandlet etter hvert som de inntreffer. I stedet for at FSM sjekker overgangsbetingelsen "kan agenten min se spilleren?" hver frame, kan et eget system konfigureres til å sjekke sjeldnere (f.eks. 5 ganger per sekund). Og resultatet er å utstede Player Seen når sjekken passerer.
Dette sendes til FSM, som nå skal gå til Player Seen-hendelsen mottatt tilstand og svare deretter. Den resulterende oppførselen er den samme bortsett fra en nesten umerkelig forsinkelse før du svarer. Men ytelsen har forbedret seg som et resultat av å separere Sense-delen i en egen del av programmet.
Hierarkisk endelig tilstandsmaskin
Det er imidlertid ikke alltid praktisk å jobbe med store FSM-er. Hvis vi ønsker å utvide angrepstilstanden til å skille MeleeAttacking og RangedAttacking, må vi endre overgangene fra alle andre tilstander som fører til Attacking state (nåværende og fremtidig).
Du har sikkert lagt merke til at i vårt eksempel er det mange dupliserte overganger. De fleste overganger i tomgangstilstand er identiske med overganger i patruljerende tilstand. Det ville være fint å ikke gjenta oss selv, spesielt hvis vi legger til flere lignende tilstander. Det er fornuftig å gruppere tomgang og patruljering under den generelle etiketten "ikke-kamp", der det bare er ett felles sett med overganger til kampstater. Hvis vi tenker på denne merkelappen som en stat, blir tomgang og patruljering understater. Et eksempel på bruk av en separat overgangstabell for en ny ikke-kampdelstat:
Hovedtilstander:
Ute av kampstatus:
Og i diagramform:
Det er det samme systemet, men med en ny ikke-kamptilstand som inkluderer tomgang og patruljering. Med hver tilstand som inneholder en FSM med undertilstander (og disse undertilstandene inneholder på sin side sine egne FSM-er - og så videre så lenge du trenger), får vi en Hierarchical Finite State Machine eller HFSM (hierarchical finite state machine). Ved å gruppere den ikke-stridende staten, kuttet vi ut en haug med overflødige overganger. Vi kan gjøre det samme for alle nye stater med felles overganger. For eksempel, hvis vi i fremtiden utvider Angripende-staten til MeleeAttacking- og MissileAttacking-statene, vil de være understater som går over mellom hverandre basert på avstand til fienden og tilgjengelighet av ammunisjon. Som et resultat kan kompleks atferd og sub-atferd representeres med et minimum av dupliserte overganger.
Atferdstreet
Med HFSM skapes komplekse kombinasjoner av atferd på en enkel måte. Det er imidlertid en liten vanskelighet at beslutningstaking i form av overgangsregler er nært knyttet til dagens tilstand. Og i mange spill er dette akkurat det som trengs. Og forsiktig bruk av statlig hierarki kan redusere antallet overgangsrepetisjoner. Men noen ganger trenger du regler som fungerer uansett hvilken stat du er i, eller som gjelder i nesten alle stater. For eksempel, hvis en agents helse faller til 25 %, vil du at han skal stikke av uansett om han var i kamp, tomgang eller snakket – du må legge til denne tilstanden til hver stat. Og hvis designeren din senere ønsker å endre den lave helseterskelen fra 25 % til 10 %, så må dette gjøres på nytt.
Ideelt sett krever denne situasjonen et system der beslutninger om "hvilken stat man skal være i" er utenfor statene selv, for å gjøre endringer kun på ett sted og ikke berøre overgangsforholdene. Atferdstrær vises her.
Det er flere måter å implementere dem på, men essensen er omtrent den samme for alle og ligner på et beslutningstre: Algoritmen starter med en "rot"-node, og treet inneholder noder som representerer enten beslutninger eller handlinger. Det er imidlertid noen få viktige forskjeller:
- Noder returnerer nå en av tre verdier: Vellykket (hvis jobben er fullført), Mislyktes (hvis den ikke kan startes), eller Kjører (hvis den fortsatt kjører og det ikke er noe endelig resultat).
- Det er ikke flere beslutningsnoder å velge mellom to alternativer. I stedet er de dekorasjonsnoder, som har én underordnet node. Hvis de lykkes, utfører de sin eneste underordnede node.
- Noder som utfører handlinger returnerer en Running-verdi for å representere handlingene som utføres.
Dette lille settet med noder kan kombineres for å skape et stort antall kompleks atferd. La oss forestille oss HFSM-vakten fra forrige eksempel som et atferdstre:
Med denne strukturen skal det ikke være noen åpenbar overgang fra tomgangs-/patruljeringstilstander til angripende eller andre stater. Hvis en fiende er synlig og karakterens helse er dårlig, vil henrettelsen stoppe ved den flyktende noden, uavhengig av hvilken node den tidligere utførte - patruljering, tomgang, angrep eller noe annet.
Atferdstrær er komplekse – det er mange måter å komponere dem på, og det kan være utfordrende å finne den rette kombinasjonen av dekoratører og sammensatte noder. Det er også spørsmål om hvor ofte man skal sjekke treet - ønsker vi å gå gjennom alle deler av det eller bare når en av forholdene har endret seg? Hvordan lagrer vi tilstand knyttet til noder - hvordan vet vi når vi har vært i tomgang i 10 sekunder, eller hvordan vet vi hvilke noder som kjørte sist, slik at vi kan behandle sekvensen riktig?
Dette er grunnen til at det er mange implementeringer. For eksempel har noen systemer erstattet dekoratornoder med inline-dekoratorer. De revurderer treet når dekorasjonsforholdene endres, hjelper til med å koble sammen noder og gir periodiske oppdateringer.
Verktøybasert system
Noen spill har mange forskjellige mekanikker. Det er ønskelig at de får alle fordelene ved enkle og generelle overgangsregler, men ikke nødvendigvis i form av et fullstendig oppførselstre. I stedet for å ha et klart sett med valg eller et tre med mulige handlinger, er det lettere å undersøke alle handlingene og velge den mest passende for øyeblikket.
Det Utility-baserte systemet vil hjelpe med nettopp dette. Dette er et system der agenten har en rekke handlinger og velger hvilke som skal utføres basert på den relative nytten av hver. Hvor nytte er et vilkårlig mål på hvor viktig eller ønskelig det er for agenten å utføre denne handlingen.
Den beregnede nytten av en handling basert på gjeldende tilstand og miljø, kan agenten sjekke og velge den mest passende andre tilstanden når som helst. Dette ligner på FSM, bortsett fra der overganger bestemmes av et estimat for hver potensielle tilstand, inkludert den nåværende. Vær oppmerksom på at vi velger den mest nyttige handlingen for å gå videre (eller bli hvis vi allerede har fullført den). For mer variasjon kan dette være et balansert, men tilfeldig utvalg fra en liten liste.
Systemet tildeler et vilkårlig område av nytteverdier – for eksempel fra 0 (helt uønsket) til 100 (helt ønskelig). Hver handling har en rekke parametere som påvirker beregningen av denne verdien. Tilbake til vårt vergeeksempel:
Overganger mellom handlinger er tvetydige - enhver stat kan følge enhver annen. Handlingsprioriteter finnes i de returnerte nytteverdiene. Hvis en fiende er synlig, og den fienden er sterk, og karakterens helse er lav, vil både Fleeing og FindingHelp returnere høye verdier som ikke er null. I dette tilfellet vil FindingHelp alltid være høyere. På samme måte gir ikke-kampaktiviteter aldri mer enn 50, så de vil alltid være lavere enn kampaktiviteter. Du må ta hensyn til dette når du oppretter handlinger og beregner nytten.
I vårt eksempel returnerer handlingene enten en fast konstant verdi eller en av to faste verdier. Et mer realistisk system vil returnere et estimat fra et kontinuerlig verdiområde. For eksempel, Flykt-handlingen returnerer høyere nytteverdier hvis agentens helse er lav, og Angripende handling returnerer lavere nytteverdier hvis fienden er for sterk. På grunn av dette har flykting-handlingen forrang fremfor angrep i enhver situasjon der agenten føler at han ikke har nok helse til å beseire fienden. Dette gjør at handlinger kan prioriteres basert på et hvilket som helst antall kriterier, noe som gjør denne tilnærmingen mer fleksibel og variabel enn et atferdstre eller FSM.
Hver handling har mange betingelser for programberegning. De kan skrives i skriptspråk eller som en serie matematiske formler. The Sims, som simulerer en karakters daglige rutine, legger til et ekstra lag med beregning - agenten mottar en rekke "motivasjoner" som påvirker bruksvurderinger. Hvis en karakter er sulten, vil de bli enda mer sultne over tid, og nytteverdien til EatFood-handlingen vil øke til karakteren utfører den, redusere sultnivået og tilbakestille EatFood-verdien til null.
Ideen om å velge handlinger basert på et rangeringssystem er ganske enkel, så et Utility-basert system kan brukes som en del av AI-beslutningsprosesser, i stedet for som en fullstendig erstatning for dem. Beslutningstreet kan be om en nyttevurdering på to underordnede noder og velge den høyeste. På samme måte kan et atferdstre ha en sammensatt Utility-node for å evaluere nytten av handlinger for å bestemme hvilket barn som skal utføres.
Bevegelse og navigering
I de forrige eksemplene hadde vi en plattform som vi flyttet til venstre eller høyre, og en vakt som patruljerte eller angrep. Men hvordan håndterer vi agentbevegelse over en periode? Hvordan setter vi hastighet, hvordan unngår vi hindringer, og hvordan planlegger vi en rute når det er vanskeligere å komme til et mål enn å bare bevege oss i en rett linje? La oss se på dette.
administrasjon
I det innledende stadiet vil vi anta at hver agent har en hastighetsverdi, som inkluderer hvor raskt den beveger seg og i hvilken retning. Det kan måles i meter per sekund, kilometer i timen, piksler per sekund osv. Når vi gjenkaller Sense/Think/Act-løkken, kan vi forestille oss at Think-delen velger en hastighet, og Act-delen bruker den hastigheten på agenten. Vanligvis har spill et fysikksystem som gjør denne oppgaven for deg, lærer hastighetsverdien til hvert objekt og justerer den. Derfor kan du forlate AI med én oppgave - å bestemme hvilken hastighet agenten skal ha. Hvis du vet hvor agenten skal være, må du flytte den i riktig retning med en bestemt hastighet. En veldig triviell ligning:
ønsket_reise = destinasjonsposisjon – agentposisjon
Se for deg en 2D-verden. Agenten er på punkt (-2,-2), destinasjonen er et sted i nordøst ved punkt (30, 20), og den nødvendige banen for agenten for å komme dit er (32, 22). La oss si at disse posisjonene måles i meter - hvis vi tar agentens hastighet til å være 5 meter per sekund, vil vi skalere forskyvningsvektoren vår og få en hastighet på omtrentlig (4.12, 2.83). Med disse parameterne ville agenten ankomme sin destinasjon på nesten 8 sekunder.
Du kan beregne verdiene på nytt når som helst. Hvis agenten var halvveis til målet, ville bevegelsen vært halve lengden, men siden agentens maksimale hastighet er 5 m/s (vi bestemte dette ovenfor), vil hastigheten være den samme. Dette fungerer også for bevegelige mål, slik at agenten kan gjøre små endringer mens de beveger seg.
Men vi ønsker mer variasjon – for eksempel sakte øke hastigheten for å simulere en karakter som beveger seg fra stående til løpende. Det samme kan gjøres på slutten før du stopper. Disse funksjonene er kjent som styreatferd, som hver har spesifikke navn: Søk, flykte, ankomst osv. Tanken er at akselerasjonskrefter kan påføres agentens hastighet, basert på å sammenligne agentens posisjon og nåværende hastighet med destinasjonen i for å bruke forskjellige metoder for å bevege seg mot målet.
Hver oppførsel har en litt annen hensikt. Søk og ankomst er måter å flytte en agent til en destinasjon. Hindringsunngåelse og -separasjon justerer agentens bevegelse for å unngå hindringer på veien til målet. Justering og kohesjon holder agenter i bevegelse. Et hvilket som helst antall forskjellige styreegenskaper kan summeres for å produsere en enkelt banevektor som tar alle faktorer i betraktning. En agent som bruker atferden Ankomst, Separasjon og Hindring for å holde seg unna vegger og andre agenter. Denne tilnærmingen fungerer godt på åpne steder uten unødvendige detaljer.
Under vanskeligere forhold fungerer tillegg av ulik atferd dårligere – for eksempel kan en agent sette seg fast i en vegg på grunn av en konflikt mellom Ankomst og Hindringsunngåelse. Derfor må du vurdere alternativer som er mer komplekse enn bare å legge til alle verdiene. Måten er denne: i stedet for å legge sammen resultatene av hver atferd, kan du vurdere bevegelse i forskjellige retninger og velge det beste alternativet.
Men i et komplekst miljø med blindveier og valg om hvilken vei vi skal gå, vil vi trenge noe enda mer avansert.
Å finne en måte
Styreatferd er flott for enkel bevegelse i et åpent område (fotballbane eller arena) der det å komme seg fra A til B er en rett vei med kun små omveier rundt hindringer. For komplekse ruter trenger vi stifinning, som er en måte å utforske verden på og bestemme en rute gjennom den.
Det enkleste er å bruke et rutenett på hver rute ved siden av agenten og vurdere hvilke av dem som har lov til å bevege seg. Hvis en av dem er en destinasjon, følg ruten fra hver rute til den forrige til du kommer til begynnelsen. Dette er ruten. Ellers gjentar du prosessen med andre ruter i nærheten til du finner destinasjonen din eller du går tom for ruter (som betyr at det ikke er noen mulig rute). Dette er det som formelt er kjent som Breadth-First Search eller BFS (breadth-first search algorithm). Ved hvert trinn ser han i alle retninger (derav bredde, "bredde"). Søkerommet er som en bølgefront som beveger seg til den når ønsket plassering – søkerommet utvides for hvert trinn til endepunktet er inkludert, hvoretter det kan spores tilbake til begynnelsen.
Som et resultat vil du motta en liste over ruter som den ønskede ruten er kompilert langs. Dette er banen (derav stifinning) - en liste over steder som agenten vil besøke mens han følger destinasjonen.
Gitt at vi kjenner posisjonen til hvert kvadrat i verden, kan vi bruke styreatferd for å bevege oss langs banen - fra node 1 til node 2, deretter fra node 2 til node 3, og så videre. Det enkleste alternativet er å gå mot midten av neste rute, men et enda bedre alternativ er å stoppe midt på kanten mellom den nåværende ruten og den neste. På grunn av dette vil agenten kunne kutte hjørner i skarpe svinger.
BFS-algoritmen har også ulemper - den utforsker like mange firkanter i "feil" retning som i "riktig" retning. Det er her en mer kompleks algoritme kalt A* (A star) kommer inn i bildet. Det fungerer på samme måte, men i stedet for å blindt undersøke nabofeltene (deretter naboer til naboer, deretter naboer til naboer til naboer, og så videre), samler den nodene i en liste og sorterer dem slik at den neste noden som undersøkes alltid er en som fører til den korteste veien. Noder er sortert basert på en heuristikk som tar hensyn til to ting – «kostnaden» for en hypotetisk rute til ønsket rute (inkludert eventuelle reisekostnader) og et estimat på hvor langt denne ruten er fra destinasjonen (forutsette søket i riktig retning).
Dette eksemplet viser at agenten utforsker én rute om gangen, hver gang han velger den tilstøtende som er mest lovende. Den resulterende banen er den samme som BFS, men færre firkanter ble vurdert i prosessen – noe som har stor innvirkning på spillytelsen.
Bevegelse uten rutenett
Men de fleste spill er ikke lagt ut på et rutenett, og det er ofte umulig å gjøre det uten å ofre realismen. Kompromisser er nødvendig. Hvilken størrelse skal rutene være? For store og de vil ikke kunne representere små korridorer eller svinger riktig, for små og det vil være for mange firkanter å søke etter, noe som til slutt vil ta mye tid.
Det første vi må forstå er at et nett gir oss en graf over tilkoblede noder. A*- og BFS-algoritmene fungerer faktisk på grafer og bryr seg ikke om nettet vårt i det hele tatt. Vi kan plassere noder hvor som helst i spillverdenen: så lenge det er en forbindelse mellom to tilkoblede noder, samt mellom start- og sluttpunktene og minst én av nodene, vil algoritmen fungere like bra som før. Dette kalles ofte et veipunktsystem, siden hver node representerer en betydelig posisjon i verden som kan være en del av et hvilket som helst antall hypotetiske baner.
Eksempel 1: en knute i hver rute. Søket starter fra noden der agenten befinner seg og slutter ved noden til ønsket firkant.
Eksempel 2: Et mindre sett med noder (veipunkter). Søket starter på agentens plass, går gjennom det nødvendige antallet noder, og fortsetter deretter til destinasjonen.
Dette er et fullstendig fleksibelt og kraftig system. Men litt forsiktighet er nødvendig for å bestemme hvor og hvordan et veipunkt skal plasseres, ellers kan det hende at agenter rett og slett ikke ser det nærmeste punktet og vil ikke være i stand til å starte banen. Det ville vært enklere om vi automatisk kunne plassere veipunkter basert på verdens geometri.
Det er her navigasjonsnettverket eller navigasjonsnettverket (navigasjonsnettverket) vises. Dette er vanligvis et 2D-nett av trekanter som er lagt over geometrien til verden – uansett hvor agenten har lov til å gå. Hver av trekantene i nettet blir en node i grafen, og har opptil tre tilstøtende trekanter som blir tilstøtende noder i grafen.
Dette bildet er et eksempel fra Unity-motoren - den analyserte geometrien i verden og skapte en navmesh (i skjermbildet i lyseblått). Hver polygon i en navmesh er et område der en agent kan stå eller flytte fra en polygon til en annen polygon. I dette eksemplet er polygonene mindre enn etasjene de er plassert på - dette gjøres for å ta hensyn til størrelsen på agenten, som vil strekke seg utover dens nominelle posisjon.
Vi kan søke etter en rute gjennom dette nettet, igjen ved å bruke A*-algoritmen. Dette vil gi oss en nesten perfekt rute i verden, som tar hensyn til all geometri og ikke krever unødvendige noder og oppretting av veipunkter.
Pathfinding er et for bredt emne som en del av en artikkel ikke er nok for. Hvis du vil studere det mer detaljert, vil dette hjelpe .
Планирование
Vi har lært med stifinning at noen ganger er det ikke nok å bare velge en retning og flytte – vi må velge en rute og gjøre noen svinger for å komme til ønsket reisemål. Vi kan generalisere denne ideen: å oppnå et mål er ikke bare neste trinn, men en hel sekvens der du noen ganger må se fremover flere trinn for å finne ut hva det første skal være. Dette kalles planlegging. Pathfinding kan betraktes som en av flere utvidelser til planlegging. Når det gjelder vår Sense/Think/Act-syklus, er det her Think-delen planlegger flere Act-deler for fremtiden.
La oss se på eksemplet med brettspillet Magic: The Gathering. Vi går først med følgende sett med kort i hendene:
- Sump - Gir 1 svart mana (landkort).
- Skog - gir 1 grønn mana (landkort).
- Fugitive Wizard - Krever 1 blå mana for å tilkalle.
- Elvish Mystic - Krever 1 grønn mana for å tilkalle.
Vi ignorerer de resterende tre kortene for å gjøre det enklere. I henhold til reglene har en spiller lov til å spille 1 landkort per tur, han kan "trykke" på dette kortet for å trekke ut mana fra det, og deretter kaste trolldom (inkludert tilkalle en skapning) i henhold til mengden mana. I denne situasjonen vet den menneskelige spilleren å spille Forest, trykke på 1 grønn mana og deretter tilkalle Elvish Mystic. Men hvordan kan spillets AI finne ut av dette?
Enkel planlegging
Den trivielle tilnærmingen er å prøve hver handling etter tur til det ikke er noen passende igjen. Ved å se på kortene ser AI hva Swamp kan spille. Og han spiller det. Er det noen andre handlinger igjen denne svingen? Den kan ikke tilkalle verken Elvish Mystic eller Fugitive Wizard, da de krever henholdsvis grønn og blå mana for å tilkalle dem, mens Swamp bare gir svart mana. Og han vil ikke lenger kunne spille Forest, fordi han allerede har spilt Swamp. Dermed fulgte spillet AI reglene, men gjorde det dårlig. Kan forbedres.
Planlegging kan finne en liste over handlinger som bringer spillet til ønsket tilstand. Akkurat som hver rute på en sti hadde naboer (i stifinning), har hver handling i en plan også naboer eller etterfølgere. Vi kan se etter disse handlingene og påfølgende handlinger til vi når ønsket tilstand.
I vårt eksempel er det ønskede resultatet "tilkalle en skapning hvis mulig." I begynnelsen av svingen ser vi bare to mulige handlinger tillatt av spillereglene:
1. Spill Swamp (resultat: Swamp i spillet)
2. Spill Skog (resultat: Skog i spillet)
Hver handling som tas kan føre til ytterligere handlinger og lukke andre, igjen avhengig av spillereglene. Tenk deg at vi spilte Swamp - dette vil fjerne Swamp som neste trinn (vi har allerede spilt det), og dette vil også fjerne Forest (fordi i henhold til reglene kan du spille ett landkort per tur). Etter dette legger AI til å få 1 svart mana som neste trinn fordi det ikke er andre alternativer. Hvis han går videre og velger Tap the Swamp, vil han motta 1 enhet svart mana og vil ikke kunne gjøre noe med den.
1. Spill Swamp (resultat: Swamp i spillet)
1.1 "Tap" Swamp (resultat: Swamp "tapped", +1 enhet svart mana)
Ingen handlinger tilgjengelig - SLUTT
2. Spill Skog (resultat: Skog i spillet)
Listen over handlinger var kort, vi kom til en blindvei. Vi gjentar prosessen for neste trinn. Vi spiller Forest, åpner handlingen "få 1 grønn mana", som igjen vil åpne den tredje handlingen - tilkalle Elvish Mystic.
1. Spill Swamp (resultat: Swamp i spillet)
1.1 "Tap" Swamp (resultat: Swamp "tapped", +1 enhet svart mana)
Ingen handlinger tilgjengelig - SLUTT
2. Spill Skog (resultat: Skog i spillet)
2.1 "Tap"-skog (resultat: Skogen "tappes", +1 enhet med grønn mana)
2.1.1 Summon Elvish Mystic (resultat: Elvish Mystic i spill, -1 grønn mana)
Ingen handlinger tilgjengelig - SLUTT
Til slutt utforsket vi alle mulige handlinger og fant en plan som tilkaller en skapning.
Dette er et veldig forenklet eksempel. Det er tilrådelig å velge den best mulige planen, i stedet for bare en plan som oppfyller noen kriterier. Det er generelt mulig å evaluere potensielle planer basert på resultatet eller den generelle fordelen av implementeringen. Du kan score deg selv 1 poeng for å spille et landkort og 3 poeng for å tilkalle en skapning. Å spille Swamp ville være en 1 poeng plan. Og å spille Forest → Trykk på skogen → tilkalle Elvish Mystic vil umiddelbart gi 4 poeng.
Slik fungerer planleggingen i Magic: The Gathering, men den samme logikken gjelder i andre situasjoner. For eksempel å flytte en bonde for å gi plass til at biskopen kan bevege seg i sjakk. Eller ta dekning bak en vegg for trygt å skyte i XCOM som dette. Generelt forstår du ideen.
Forbedret planlegging
Noen ganger er det for mange potensielle handlinger til å vurdere alle mulige alternativer. Tilbake til eksemplet med Magic: The Gathering: la oss si at i spillet og i hånden din er det flere land- og skapningskort - antall mulige kombinasjoner av trekk kan være i dusinvis. Det er flere løsninger på problemet.
Den første metoden er kjetting bakover. I stedet for å prøve alle kombinasjonene, er det bedre å begynne med det endelige resultatet og prøve å finne en direkte rute. I stedet for å gå fra roten av treet til et bestemt blad, beveger vi oss i motsatt retning - fra bladet til roten. Denne metoden er enklere og raskere.
Hvis fienden har 1 helse, kan du finne planen "deal 1 or more damage". For å oppnå dette må en rekke betingelser være oppfylt:
1. Skade kan være forårsaket av en trylleformel - den må være i hånden.
2. For å fortrylle trenger du mana.
3. For å få mana, må du spille et landkort.
4. For å spille et landkort må du ha det på hånden.
En annen måte er best-først-søk. I stedet for å prøve alle stiene, velger vi den som passer best. Oftest gir denne metoden den optimale planen uten unødvendige søkekostnader. A* er en form for beste første søk - ved å undersøke de mest lovende rutene fra begynnelsen, kan den allerede finne den beste banen uten å måtte sjekke andre alternativer.
Et interessant og stadig mer populært beste-første-søk er Monte Carlo Tree Search. I stedet for å gjette hvilke planer som er bedre enn andre når du velger hver påfølgende handling, velger algoritmen tilfeldige etterfølgere på hvert trinn til den når slutten (når planen resulterte i seier eller tap). Det endelige resultatet brukes deretter til å øke eller redusere vekten av tidligere alternativer. Ved å gjenta denne prosessen flere ganger på rad, gir algoritmen et godt estimat på hva som er det beste neste trekk, selv om situasjonen endrer seg (hvis fienden tar grep for å forstyrre spilleren).
Ingen historie om planlegging i spill ville vært komplett uten målorientert handlingsplanlegging eller GOAP (målorientert handlingsplanlegging). Dette er en mye brukt og diskutert metode, men bortsett fra noen få særegne detaljer, er det i hovedsak den bakoverlenkede metoden vi snakket om tidligere. Hvis målet var å "ødelegge spilleren" og spilleren er bak dekning, kan planen være: ødelegge med en granat → hent den → kast den.
Det er vanligvis flere mål, hver med sin egen prioritet. Hvis det høyest prioriterte målet ikke kan fullføres (ingen kombinasjon av handlinger skaper en "drep spilleren"-plan fordi spilleren ikke er synlig), vil AI falle tilbake til lavere prioriterte mål.
Trening og tilpasning
Vi har allerede sagt at spill-AI vanligvis ikke bruker maskinlæring fordi det ikke er egnet for å administrere agenter i sanntid. Men dette betyr ikke at du ikke kan låne noe fra dette området. Vi vil ha en motstander i en skytter som vi kan lære noe av. Finn for eksempel ut om de beste posisjonene på kartet. Eller en motstander i et kampspill som ville blokkere spillerens ofte brukte kombinasjonsbevegelser, og motiverte ham til å bruke andre. Så maskinlæring kan være ganske nyttig i slike situasjoner.
Statistikk og sannsynligheter
Før vi kommer inn på komplekse eksempler, la oss se hvor langt vi kan gå ved å ta noen få enkle målinger og bruke dem til å ta avgjørelser. For eksempel sanntidsstrategi – hvordan avgjør vi om en spiller kan sette i gang et angrep i løpet av de første minuttene av spillet og hvilket forsvar for å forberede seg mot dette? Vi kan studere en spillers tidligere erfaringer for å forstå hva fremtidige reaksjoner kan være. Til å begynne med har vi ikke slike rådata, men vi kan samle det - hver gang AI spiller mot et menneske, kan den registrere tidspunktet for det første angrepet. Etter noen økter vil vi få et gjennomsnitt av tiden det vil ta for spilleren å angripe i fremtiden.
Det er også et problem med gjennomsnittsverdier: hvis en spiller skyndte seg 20 ganger og spilte sakte 20 ganger, vil de nødvendige verdiene være et sted i midten, og dette vil ikke gi oss noe nyttig. En løsning er å begrense inndataene – de siste 20 stykkene kan tas med i betraktningen.
En lignende tilnærming brukes når man estimerer sannsynligheten for visse handlinger ved å anta at spillerens tidligere preferanser vil være de samme i fremtiden. Hvis en spiller angriper oss fem ganger med ildkule, to ganger med lyn og en gang med nærkamp, er det åpenbart at han foretrekker ildkule. La oss ekstrapolere og se sannsynligheten for å bruke forskjellige våpen: ildkule=62,5 %, lyn=25 % og nærkamp=12,5 %. Spillets AI må forberede seg for å beskytte seg mot brann.
En annen interessant metode er å bruke Naive Bayes Classifier til å studere store mengder inndata og klassifisere situasjonen slik at AI-en reagerer på ønsket måte. Bayesianske klassifiserere er mest kjent for deres bruk i spamfiltre for e-post. Der undersøker de ordene, sammenligner dem med der disse ordene har dukket opp før (i spam eller ikke), og trekker konklusjoner om innkommende e-poster. Vi kan gjøre det samme selv med færre innspill. Basert på all nyttig informasjon som AI ser (som hvilke fiendtlige enheter som er opprettet, eller hvilke trollformler de bruker, eller hvilke teknologier de forsket på), og det endelige resultatet (krig eller fred, rush eller forsvar, etc.) - vi vil velge ønsket AI-adferd.
Alle disse treningsmetodene er tilstrekkelige, men det er tilrådelig å bruke dem basert på testdata. AI vil lære seg å tilpasse seg de forskjellige strategiene spilletesterne dine har brukt. AI som tilpasser seg spilleren etter utgivelse kan bli for forutsigbar eller for vanskelig å beseire.
Verdibasert tilpasning
Gitt innholdet i spillverdenen vår og reglene, kan vi endre settet med verdier som påvirker beslutningstaking, i stedet for bare å bruke inndataene. Vi gjør dette:
- La AI-en samle inn data om verdens tilstand og viktige hendelser under spillet (som ovenfor).
- La oss endre noen viktige verdier basert på disse dataene.
- Vi implementerer våre beslutninger basert på behandling eller evaluering av disse verdiene.
For eksempel har en agent flere rom å velge mellom på et førstepersons skytespill. Hvert rom har sin egen verdi, som avgjør hvor ønskelig det er å besøke. AI velger tilfeldig hvilket rom den skal gå til basert på verdien. Agenten husker da hvilket rom han ble drept i og reduserer verdien (sannsynligheten for at han kommer tilbake dit). Tilsvarende for den omvendte situasjonen - hvis agenten ødelegger mange motstandere, øker verdien av rommet.
Markov modell
Hva om vi brukte de innsamlede dataene til å lage spådommer? Hvis vi husker hvert rom vi ser en spiller i i en viss periode, vil vi forutsi hvilket rom spilleren kan gå til. Ved å spore og registrere spillerens bevegelser på tvers av rom (verdier), kan vi forutsi dem.
La oss ta tre rom: rød, grønn og blå. Og også observasjonene vi tok opp mens vi så på spilløkten:
Antall observasjoner i hvert rom er nesten likt - vi vet fortsatt ikke hvor vi skal lage et godt sted for et bakhold. Innsamling av statistikk er også komplisert av gjenoppliving av spillere, som vises jevnt over hele kartet. Men dataene om neste rom de går inn i etter å ha vist seg på kartet er allerede nyttige.
Det kan ses at det grønne rommet passer spillerne – de fleste flytter fra det røde rommet til det, 50 % av dem forblir der lenger. Det blå rommet, tvert imot, er ikke populært; nesten ingen går til det, og hvis de gjør det, blir de ikke lenge.
Men dataene forteller oss noe viktigere - når en spiller er i et blått rom, vil neste rom vi ser ham i være rødt, ikke grønt. Selv om det grønne rommet er mer populært enn det røde rommet, endrer situasjonen seg hvis spilleren er i det blå rommet. Den neste tilstanden (dvs. rommet spilleren vil gå til) avhenger av forrige tilstand (dvs. rommet spilleren er i). Fordi vi utforsker avhengigheter, vil vi gjøre mer nøyaktige spådommer enn om vi bare telte observasjoner uavhengig.
Å forutsi en fremtidig tilstand basert på data fra en tidligere tilstand kalles en Markov-modell, og slike eksempler (med rom) kalles Markov-kjeder. Siden mønstrene representerer sannsynligheten for endringer mellom påfølgende tilstander, vises de visuelt som FSM-er med en sannsynlighet rundt hver overgang. Tidligere brukte vi FSM for å representere atferdstilstanden som en agent var i, men dette konseptet strekker seg til enhver tilstand, enten det er assosiert med agenten eller ikke. I dette tilfellet representerer statene rommet agenten opptar:
Dette er en enkel måte å representere den relative sannsynligheten for tilstandsendringer, og gir AI en viss evne til å forutsi neste tilstand. Du kan forutse flere skritt fremover.
Hvis en spiller er i green room, er det 50 % sjanse for at han blir der neste gang han blir observert. Men hva er sjansene for at han fortsatt vil være der også etter? Ikke bare er det en sjanse for at spilleren forble i det grønne rommet etter to observasjoner, men det er også en sjanse for at han dro og returnerte. Her er den nye tabellen som tar hensyn til de nye dataene:
Den viser at sjansen for å se spilleren i det grønne rommet etter to observasjoner vil være lik 51 % - 21 % at han vil være fra det røde rommet, 5 % av dem at spilleren vil besøke det blå rommet mellom dem, og 25 % som spilleren ikke vil forlate green room.
Tabellen er ganske enkelt et visuelt verktøy - prosedyren krever bare å multiplisere sannsynlighetene ved hvert trinn. Dette betyr at du kan se langt inn i fremtiden med ett forbehold: vi antar at sjansen for å komme inn i et rom avhenger helt av det aktuelle rommet. Dette kalles Markov Property - den fremtidige staten avhenger bare av nåtiden. Men dette er ikke XNUMX% nøyaktig. Spillere kan endre avgjørelser avhengig av andre faktorer: helsenivå eller mengde ammunisjon. Fordi vi ikke registrerer disse verdiene, vil prognosene våre være mindre nøyaktige.
N-gram
Hva med eksempelet på et kampspill og å forutsi spillerens kombinasjonsbevegelser? Det samme! Men i stedet for én tilstand eller hendelse, vil vi undersøke hele sekvensen som utgjør en kombinasjonsstreik.
En måte å gjøre dette på er å lagre hver inngang (som Kick, Punch eller Block) i en buffer og skrive hele bufferen som en hendelse. Så spilleren trykker gjentatte ganger på Kick, Kick, Punch for å bruke SuperDeathFist-angrepet, AI-systemet lagrer alle inngangene i en buffer og husker de tre siste som ble brukt i hvert trinn.
(Linjene i fet skrift er når spilleren starter SuperDeathFist-angrepet.)
AI vil se alle alternativene når spilleren velger Kick, etterfulgt av et nytt Kick, og legger så merke til at neste inngang alltid er Punch. Dette vil tillate agenten å forutsi SuperDeathFists kombinasjonsbevegelse og blokkere den hvis mulig.
Disse hendelsesforløpene kalles N-gram, hvor N er antall elementer som er lagret. I forrige eksempel var det en 3-gram (trigram), som betyr: de to første oppføringene brukes til å forutsi den tredje. Følgelig, i en 5-grams, forutsier de fire første oppføringene den femte og så videre.
Designeren må velge størrelsen på N-gram nøye. En mindre N krever mindre minne, men lagrer også mindre historie. For eksempel vil en 2-grams (bigram) ta opp Kick, Kick eller Kick, Punch, men vil ikke kunne lagre Kick, Kick, Punch, så AI vil ikke svare på SuperDeathFist-komboen.
På den annen side krever større tall mer minne og AI vil være vanskeligere å trene siden det vil være mange flere mulige alternativer. Hvis du hadde tre mulige innganger av Kick, Punch eller Block, og vi brukte en 10-grams, ville det vært omtrent 60 tusen forskjellige alternativer.
Bigrammodellen er en enkel Markov-kjede - hvert tidligere tilstand/nåværende tilstandspar er et bigram, og du kan forutsi den andre tilstanden basert på den første. N-grammene på 3 gram og større kan også betraktes som Markov-kjeder, der alle elementene (unntatt det siste i N-grammet) sammen danner den første tilstanden og det siste elementet den andre. Kampspilleksemplet viser muligheten for å gå over fra Kick and Kick-tilstanden til Kick and Punch-tilstanden. Ved å behandle flere inngangshistorikkoppføringer som en enkelt enhet, transformerer vi i hovedsak inndatasekvensen til en del av hele tilstanden. Dette gir oss Markov-egenskapen, som lar oss bruke Markov-kjeder til å forutsi neste inngang og gjette hvilket kombinasjonstrekk som blir neste.
Konklusjon
Vi snakket om de vanligste verktøyene og tilnærmingene i utviklingen av kunstig intelligens. Vi har også sett på situasjonene der de må brukes og hvor de er spesielt nyttige.
Dette burde være nok til å forstå det grunnleggende om spill-AI. Men dette er selvfølgelig ikke alle metoder. Mindre populære, men ikke mindre effektive inkluderer:
- optimeringsalgoritmer inkludert bakkeklatring, gradientnedstigning og genetiske algoritmer
- motstridende søk/planleggingsalgoritmer (minimax og alfa-beta beskjæring)
- klassifiseringsmetoder (perseptroner, nevrale nettverk og støttevektormaskiner)
- systemer for behandlingsagenters persepsjon og hukommelse
- arkitektoniske tilnærminger til AI (hybridsystemer, delsettarkitekturer og andre måter å overlegge AI-systemer på)
- animasjonsverktøy (planlegging og bevegelseskoordinering)
- ytelsesfaktorer (detaljnivå, når som helst og tidsskjæringsalgoritmer)
Nettressurser om emnet:
1. GameDev.net har Og .
2. inneholder mange presentasjoner og artikler om et bredt spekter av emner relatert til utvikling av spill-AI.
3. inkluderer emner fra GDC AI Summit, hvorav mange er tilgjengelige gratis.
4. Nyttig materiale finnes også på nettsiden .
5. Tommy Thompson, AI-forsker og spillutvikler, lager videoer på YouTube med en forklaring og studie av AI i kommersielle spill.
Bøker om emnet:
1. Game AI Pro-bokserien er en samling korte artikler som forklarer hvordan du implementerer spesifikke funksjoner eller hvordan du løser spesifikke problemer.
2. AI Game Programming Wisdom-serien er forgjengeren til Game AI Pro-serien. Den inneholder eldre metoder, men nesten alle er aktuelle også i dag.
3. er en av grunntekstene for alle som ønsker å forstå det generelle feltet kunstig intelligens. Dette er ikke en bok om spillutvikling – den lærer det grunnleggende om AI.
Kilde: www.habr.com