Jeg stødte på noget interessant materiale om kunstig intelligens i spil. Med en forklaring af grundlæggende ting om AI ved hjælp af enkle eksempler, og indeni er der mange nyttige værktøjer og metoder til dens bekvemme udvikling og design. Hvordan, hvor og hvornår man skal bruge dem, er der også.
De fleste eksempler er skrevet i pseudokode, så der kræves ingen avanceret programmeringsviden. Under snittet er der 35 ark tekst med billeder og gifs, så gør dig klar.
UPD. Jeg undskylder, men jeg har allerede lavet min egen oversættelse af denne artikel om Habré . Du kan læse hans version , men af en eller anden grund gik artiklen mig forbi (jeg brugte søgningen, men noget gik galt). Og da jeg skriver på en blog dedikeret til spiludvikling, besluttede jeg at overlade min version af oversættelsen til abonnenter (nogle punkter er formateret anderledes, nogle blev bevidst udeladt efter råd fra udviklerne).
Hvad er AI?
Game AI fokuserer på, hvilke handlinger et objekt skal udføre baseret på de forhold, det er placeret under. Dette omtales almindeligvis som "intelligent agent"-ledelse, hvor en agent er en spillerkarakter, et køretøj, en bot eller nogle gange noget mere abstrakt: en hel gruppe af enheder eller endda en civilisation. I hvert tilfælde er det en ting, der skal se sine omgivelser, træffe beslutninger baseret på det og handle i overensstemmelse med dem. Dette kaldes Sense/Think/Act-cyklussen:
- Sense: Agenten finder eller modtager information om ting i sit miljø, der kan påvirke dens adfærd (trusler i nærheden, genstande at indsamle, interessante steder at udforske).
- Tænk: Agenten bestemmer, hvordan han skal reagere (overvejer om det er sikkert nok at samle genstande eller om han skal slås/gemme sig først).
- Handling: Agenten udfører handlinger for at implementere den tidligere beslutning (begynder at bevæge sig mod fjenden eller objektet).
- ...nu har situationen ændret sig på grund af karakterernes handlinger, så cyklussen gentages med nye data.
AI har en tendens til at fokusere på Sense-delen af loopet. For eksempel tager autonome biler billeder af vejen, kombinerer dem med radar- og lidardata og fortolker dem. Dette gøres typisk ved maskinlæring, som behandler indgående data og giver det mening, udtrækker semantisk information som "der er en anden bil 20 yards foran dig." Det er de såkaldte klassifikationsproblemer.
Spil behøver ikke et komplekst system for at udtrække information, da det meste af dataene allerede er en integreret del af det. Der er ingen grund til at køre billedgenkendelsesalgoritmer for at afgøre, om der er en fjende forude – spillet kender allerede og fører informationen direkte ind i beslutningsprocessen. Derfor er Sense-delen af cyklussen ofte meget enklere end Tænk og Handl-delen.
Begrænsninger af Game AI
AI har en række begrænsninger, som skal overholdes:
- AI behøver ikke være trænet på forhånd, som var det en maskinlæringsalgoritme. Det giver ingen mening at skrive et neuralt netværk under udviklingen for at overvåge titusindvis af spillere og lære den bedste måde at spille mod dem. Hvorfor? Fordi spillet ikke er blevet udgivet, og der er ingen spillere.
- Spillet skal være sjovt og udfordrende, så agenter bør ikke finde den bedste tilgang til folk.
- Agenter skal se realistiske ud, så spillerne føler, at de spiller mod rigtige mennesker. AlphaGo-programmet klarede sig bedre end mennesker, men de valgte trin var meget langt fra den traditionelle forståelse af spillet. Hvis spillet simulerer en menneskelig modstander, burde denne følelse ikke eksistere. Algoritmen skal ændres, så den træffer plausible beslutninger frem for ideelle.
- AI skal fungere i realtid. Dette betyder, at algoritmen ikke kan monopolisere CPU-brug i lange perioder for at træffe beslutninger. Selv 10 millisekunder er for lang tid, fordi de fleste spil kun har brug for 16 til 33 millisekunder for at klare hele behandlingen og gå videre til den næste grafikramme.
- Ideelt set bør i det mindste en del af systemet være datadrevet, så ikke-kodere kan foretage ændringer og justeringer kan ske hurtigere.
Lad os se på AI-tilgange, der dækker hele Sense/Think/Act-cyklussen.
Træffe grundlæggende beslutninger
Lad os starte med det enkleste spil - Pong. Mål: flyt pagajen, så bolden hopper af den i stedet for at flyve forbi den. Det er ligesom tennis, hvor man taber, hvis man ikke rammer bolden. Her har AI en forholdsvis nem opgave - at bestemme i hvilken retning platformen skal flyttes.
Betingede erklæringer
For kunstig intelligens i Pong er den mest oplagte løsning altid at forsøge at placere platformen under bolden.
En simpel algoritme til dette, skrevet i pseudokode:
hver frame/opdatering, mens spillet kører:
hvis bolden er til venstre for pagajen:
flyt pagajen til venstre
ellers hvis bolden er til højre for pagajen:
flyt padlen til højre
Hvis platformen bevæger sig med boldens hastighed, så er dette den ideelle algoritme til AI i Pong. Der er ingen grund til at komplicere noget, hvis der ikke er så meget data og mulige handlinger for agenten.
Denne tilgang er så enkel, at hele Sense/Think/Act-cyklussen knap er mærkbar. Men det er der:
- Sense-delen er i to if-udsagn. Spillet ved, hvor bolden er, og hvor platformen er, så AI ser efter den information.
- Tænk-delen indgår også i de to if-udsagn. De rummer to løsninger, som i dette tilfælde udelukker hinanden. Som et resultat vælges en af tre handlinger - flyt platformen til venstre, flyt den til højre, eller gør ingenting, hvis den allerede er korrekt placeret.
- Akt-delen findes i sætningerne Move Paddle Left og Move Paddle Right. Afhængigt af spildesignet kan de flytte platformen med det samme eller med en bestemt hastighed.
Sådanne tilgange kaldes reaktive - der er et simpelt sæt regler (i dette tilfælde hvis udsagn i koden), der reagerer på den aktuelle tilstand i verden og skrider til handling.
Beslutningstræ
Pong-eksemplet svarer faktisk til et formelt AI-koncept kaldet et beslutningstræ. Algoritmen gennemgår det for at nå et "blad" - en beslutning om, hvilken handling der skal tages.
Lad os lave et blokdiagram af beslutningstræet for vores platforms algoritme:
Hver del af træet kaldes en node - AI bruger grafteori til at beskrive sådanne strukturer. Der er to typer noder:
- Beslutningsknudepunkter: valg mellem to alternativer baseret på test af en tilstand, hvor hvert alternativ er repræsenteret som en separat knude.
- Slutnoder: Den handling, der skal udføres, der repræsenterer den endelige beslutning.
Algoritmen starter fra den første knude ("roden" af træet). Den træffer enten en beslutning om, hvilken underordnet node den skal gå til, eller den udfører handlingen, der er gemt i noden, og afslutter.
Hvad er fordelen ved at have et beslutningstræ til at udføre det samme arbejde som hvis-udsagnene i det foregående afsnit? Der er et generelt system her, hvor hver beslutning kun har én betingelse og to mulige udfald. Dette giver udvikleren mulighed for at skabe AI ud fra data, der repræsenterer beslutninger i et træ uden at skulle hårdkode det. Lad os præsentere det i form af en tabel:
På kodesiden får du et system til at læse strenge. Opret en node for hver af dem, forbind beslutningslogik baseret på den anden kolonne og underordnede noder baseret på den tredje og fjerde kolonne. Du skal stadig programmere betingelserne og handlingerne, men nu bliver spillets struktur mere kompleks. Her tilføjer du yderligere beslutninger og handlinger og tilpasser derefter hele AI ved blot at redigere trædefinitionstekstfilen. Dernæst overfører du filen til spildesigneren, som kan ændre adfærden uden at genkompilere spillet eller ændre koden.
Beslutningstræer er meget nyttige, når de bygges automatisk ud fra et stort sæt eksempler (f.eks. ved hjælp af ID3-algoritmen). Dette gør dem til et effektivt og højtydende værktøj til at klassificere situationer baseret på de indhentede data. Men vi går ud over et simpelt system for agenter til at vælge handlinger.
scenarier
Vi analyserede et beslutningstræsystem, der brugte forudskabte betingelser og handlinger. Personen, der designer AI'en, kan organisere træet, som han vil, men han er stadig nødt til at stole på koderen, der har programmeret det hele. Hvad hvis vi kunne give designeren værktøjerne til at skabe deres egne betingelser eller handlinger?
For at programmøren ikke skal skrive kode for betingelserne Is Ball Left Of Paddle og Is Ball Right Of Paddle, kan han oprette et system, hvor designeren vil skrive betingelser for at kontrollere disse værdier. Så vil beslutningstræets data se sådan ud:
Dette er i det væsentlige det samme som i den første tabel, men løsningerne i sig selv har deres egen kode, lidt ligesom den betingede del af en if-sætning. På kodesiden ville dette læses i anden kolonne for beslutningsknuderne, men i stedet for at lede efter en specifik betingelse, der skal udføres (Er Ball Left Of Paddle), evaluerer den det betingede udtryk og returnerer sandt eller falsk i overensstemmelse hermed. Dette gøres ved at bruge scriptsproget Lua eller Angelscript. Ved at bruge dem kan en udvikler tage objekter i sit spil (bold og pagaj) og skabe variabler, der vil være tilgængelige i scriptet (ball.position). Også scriptsproget er enklere end C++. Det kræver ikke et komplet kompileringstrin, så det er ideelt til hurtigt at justere spillogikken og tillader "ikke-kodere" selv at skabe de nødvendige funktioner.
I eksemplet ovenfor bruges scriptsproget kun til at evaluere det betingede udtryk, men det kan også bruges til handlinger. For eksempel kan dataene Flyt Paddle Right blive en script-sætning (ball.position.x += 10). Sådan at handlingen også er defineret i scriptet, uden at det er nødvendigt at programmere Move Paddle Right.
Du kan gå endnu længere og skrive hele beslutningstræet i et scriptsprog. Dette vil være kode i form af hårdkodede betingede sætninger, men de vil være placeret i eksterne scriptfiler, det vil sige, at de kan ændres uden at genkompilere hele programmet. Du kan ofte redigere scriptfilen under gameplay for hurtigt at teste forskellige AI-reaktioner.
Hændelsessvar
Eksemplerne ovenfor er perfekte til Pong. De kører kontinuerligt Sense/Think/Act-cyklussen og handler baseret på den nyeste tilstand i verden. Men i mere komplekse spil skal du reagere på individuelle begivenheder og ikke evaluere alt på én gang. Pong i dette tilfælde er allerede et dårligt eksempel. Lad os vælge en anden.
Forestil dig et skydespil, hvor fjenderne er ubevægelige, indtil de opdager spilleren, hvorefter de handler afhængigt af deres "specialisering": nogen vil løbe for at "haste", nogen vil angribe langvejs fra. Det er stadig et grundlæggende reaktivt system - "hvis en spiller bliver opdaget, så gør noget" - men det kan logisk opdeles i en spiller set begivenhed og en reaktion (vælg et svar og udfør det).
Dette bringer os tilbage til Sense/Think/Act-cyklussen. Vi kan kode en Sense-del, der kontrollerer hver frame, om AI ser afspilleren. Hvis ikke, sker der intet, men hvis den ser, så oprettes Player Seen-begivenheden. Koden vil have en separat sektion, der siger "når Player Seen-begivenheden indtræffer, så gør", hvor er det svar, du skal bruge for at adressere Tænk og Handl-delene. Således vil du opsætte reaktioner på Player Seen-begivenheden: for den "rushende" karakter - ChargeAndAttack, og for snigskytten - HideAndSnipe. Disse relationer kan oprettes i datafilen for hurtig redigering uden at skulle rekompilere. Scriptsprog kan også bruges her.
At tage svære beslutninger
Selvom simple reaktionssystemer er meget kraftfulde, er der mange situationer, hvor de ikke er nok. Nogle gange er du nødt til at træffe forskellige beslutninger baseret på, hvad agenten gør i øjeblikket, men det er svært at forestille sig dette som en betingelse. Nogle gange er der for mange betingelser til effektivt at repræsentere dem i et beslutningstræ eller et script. Nogle gange skal du på forhånd vurdere, hvordan situationen vil ændre sig, før du beslutter dig for næste skridt. Mere sofistikerede tilgange er nødvendige for at løse disse problemer.
Finite state maskine
Finite state machine eller FSM (finite state machine) er en måde at sige, at vores agent i øjeblikket er i en af flere mulige tilstande, og at den kan skifte fra en tilstand til en anden. Der er et vist antal af sådanne stater - deraf navnet. Det bedste eksempel fra livet er et lyskryds. Der er forskellige sekvenser af lys forskellige steder, men princippet er det samme - hver tilstand repræsenterer noget (stop, gå, osv.). Et trafiklys er kun i én tilstand på et givet tidspunkt og bevæger sig fra det ene til det andet baseret på simple regler.
Det er en lignende historie med NPC'er i spil. Lad os f.eks. tage en vagt med følgende tilstande:
- Patruljering.
- Angribende.
- Flygter.
Og disse betingelser for at ændre dens tilstand:
- Hvis vagten ser fjenden, angriber han.
- Hvis vagten angriber, men ikke længere ser fjenden, vender han tilbage for at patruljere.
- Hvis en vagt angriber, men bliver hårdt såret, løber han væk.
Du kan også skrive hvis-udsagn med en guardian state-variabel og forskellige kontroller: er der en fjende i nærheden, hvad er sundhedsniveauet for NPC'en osv. Lad os tilføje nogle flere tilstande:
- Lediggang - mellem patruljer.
- Søgning - når den bemærkede fjende er forsvundet.
- Finde hjælp - når en fjende bliver opdaget, men er for stærk til at kæmpe alene.
Valget for hver af dem er begrænset - for eksempel vil vagten ikke gå på udkig efter en skjult fjende, hvis han har lavt helbred.
Der er trods alt en enorm liste over "hvis" , At "kan blive for besværlig, så vi er nødt til at formalisere en metode, der giver os mulighed for at holde tilstande og overgange mellem stater i tankerne. For at gøre dette tager vi hensyn til alle stater, og under hver stat skriver vi ned i en liste alle overgange til andre stater sammen med de nødvendige betingelser for dem.
Dette er en tilstandsovergangstabel - en omfattende måde at repræsentere FSM på. Lad os tegne et diagram og få et komplet overblik over, hvordan NPC-adfærd ændrer sig.
Diagrammet afspejler essensen af beslutningstagning for denne agent baseret på den aktuelle situation. Desuden viser hver pil en overgang mellem tilstande, hvis betingelsen ved siden af er sand.
Hver opdatering tjekker vi agentens aktuelle tilstand, ser listen over overgange igennem, og hvis betingelserne for overgangen er opfyldt, accepterer den den nye tilstand. For eksempel tjekker hver frame, om 10-sekunders timeren er udløbet, og hvis det er tilfældet, så går vagten fra tomgangstilstand til patruljering. På samme måde kontrollerer den angribende stat agentens helbred - hvis det er lavt, så går det over i den flygtede tilstand.
Dette er håndtering af overgange mellem stater, men hvad med adfærden forbundet med staterne selv? Med hensyn til implementering af den faktiske adfærd for en bestemt stat, er der typisk to typer "hook", hvor vi tildeler handlinger til FSM:
- Handlinger, som vi med jævne mellemrum udfører for den aktuelle tilstand.
- De handlinger, vi tager, når vi skifter fra en stat til en anden.
Eksempler på den første type. Den patruljerende tilstand vil flytte agenten langs patruljeruten hver ramme. Den angribende tilstand vil forsøge at starte et angreb hver frame eller overgang til en tilstand, hvor dette er muligt.
For den anden type skal du overveje overgangen "hvis fjenden er synlig, og fjenden er for stærk, så gå til tilstanden Find hjælp. Agenten skal vælge, hvor han skal henvende sig for at få hjælp og gemme disse oplysninger, så tilstanden Finding Help ved, hvor den skal henvende sig. Når der er fundet hjælp, går agenten tilbage til den angribende tilstand. På dette tidspunkt vil han gerne fortælle den allierede om truslen, så NotifyFriendOfThreat-handlingen kan forekomme.
Endnu en gang kan vi se på dette system gennem linsen af Sense/Think/Act-cyklussen. Sense er inkorporeret i de data, der bruges af overgangslogikken. Tænk - overgange tilgængelige i hver stat. Og handling udføres af handlinger, der udføres periodisk i en stat eller ved overgange mellem stater.
Sommetider kan løbende afstemningsovergangsforhold være dyrt. For eksempel, hvis hver agent udfører komplekse beregninger hver frame for at bestemme, om den kan se fjender og forstå, om den kan skifte fra patruljerende til angrebstilstand, vil dette tage meget CPU-tid.
Vigtige ændringer i verdens tilstand kan opfattes som begivenheder, der vil blive bearbejdet, efterhånden som de opstår. I stedet for at FSM kontrollerer overgangsbetingelsen "kan min agent se spilleren?" hver frame, kan et separat system konfigureres til at tjekke mindre hyppigt (f.eks. 5 gange pr. sekund). Og resultatet er at udstede Player Seen, når checken passerer.
Dette videregives til FSM, som nu skal gå til Player Seen-begivenhedens modtagne tilstand og svare i overensstemmelse hermed. Den resulterende adfærd er den samme bortset fra en næsten umærkelig forsinkelse, før du reagerer. Men ydeevnen er blevet forbedret som følge af, at Sense-delen er adskilt i en separat del af programmet.
Hierarkisk finite state maskine
Det er dog ikke altid praktisk at arbejde med store FSM'er. Hvis vi ønsker at udvide angrebstilstanden til at adskille MeleeAttacking og RangedAttacking, bliver vi nødt til at ændre overgangene fra alle andre tilstande, der fører til angrebstilstanden (nuværende og fremtidig).
Du har sikkert bemærket, at der i vores eksempel er mange dobbelte overgange. De fleste overgange i tomgangstilstand er identiske med overgange i patruljerende tilstand. Det ville være rart ikke at gentage os selv, især hvis vi tilføjer flere lignende tilstande. Det giver mening at gruppere tomgang og patruljering under den generelle betegnelse "ikke-kamp", hvor der kun er ét fælles sæt af overgange til kampstater. Hvis vi tænker på denne etiket som en stat, så bliver tomgang og patruljering undertilstande. Et eksempel på brug af en separat overgangstabel til en ny ikke-kamp undertilstand:
Hovedstater:
Ude af kampstatus:
Og i diagramform:
Det er det samme system, men med en ny ikke-kamptilstand, der inkluderer tomgang og patruljering. Når hver tilstand indeholder en FSM med undertilstande (og disse undertilstande til gengæld indeholder deres egne FSM'er - og så videre, så længe du har brug for det), får vi en Hierarchical Finite State Machine eller HFSM (hierarchical finite state machine). Ved at gruppere den ikke-kampstat, skærer vi en masse overflødige overgange ud. Vi kan gøre det samme for alle nye stater med fælles overgange. For eksempel, hvis vi i fremtiden udvider Angrebstilstanden til MeleeAttacking- og MissileAttacking-staterne, vil de være understater, der skifter mellem hinanden baseret på afstand til fjenden og ammunitions tilgængelighed. Som et resultat kan kompleks adfærd og sub-adfærd repræsenteres med et minimum af dobbelte overgange.
Adfærdstræ
Med HFSM skabes komplekse kombinationer af adfærd på en enkel måde. Det er dog en lille vanskelighed, at beslutningstagning i form af overgangsregler er tæt forbundet med den nuværende tilstand. Og i mange spil er det præcis det, der skal til. Og omhyggelig brug af statens hierarki kan reducere antallet af overgangsgentagelser. Men nogle gange har du brug for regler, der virker, uanset hvilken stat du er i, eller som gælder i næsten enhver stat. For eksempel, hvis en agents helbred falder til 25 %, vil du have ham til at løbe væk, uanset om han var i kamp, inaktiv eller talte - du bliver nødt til at tilføje denne betingelse til hver stat. Og hvis din designer senere ønsker at ændre den lave sundhedstærskel fra 25 % til 10 %, så skal det gøres igen.
Ideelt set kræver denne situation et system, hvor beslutninger om "hvilken tilstand at være i" er uden for staterne selv, for kun at foretage ændringer ét sted og ikke berøre overgangsbetingelserne. Adfærdstræer vises her.
Der er flere måder at implementere dem på, men essensen er nogenlunde den samme for alle og ligner et beslutningstræ: Algoritmen starter med en "rod"-knude, og træet indeholder noder, der repræsenterer enten beslutninger eller handlinger. Der er dog et par vigtige forskelle:
- Noder returnerer nu en af tre værdier: Succeeded (hvis jobbet er fuldført), Failed (hvis det ikke kan startes) eller Kører (hvis det stadig kører, og der ikke er noget endeligt resultat).
- Der er ikke flere beslutningsknuder at vælge mellem to alternativer. I stedet er de Decorator noder, som har en underordnet node. Hvis de lykkes, udfører de deres eneste underordnede node.
- Noder, der udfører handlinger, returnerer en kørende værdi for at repræsentere de handlinger, der udføres.
Dette lille sæt af noder kan kombineres for at skabe et stort antal komplekse adfærd. Lad os forestille os HFSM-vagten fra det forrige eksempel som et adfærdstræ:
Med denne struktur bør der ikke være nogen åbenlys overgang fra tomgangs-/patruljeringstilstande til angribende eller andre stater. Hvis en fjende er synlig, og karakterens helbred er lavt, vil henrettelsen stoppe ved den flygtede node, uanset hvilken node den tidligere udførte - patruljering, tomgang, angreb eller en hvilken som helst anden.
Adfærdstræer er komplekse – der er mange måder at sammensætte dem på, og det kan være en udfordring at finde den rigtige kombination af dekoratører og sammensatte noder. Der er også spørgsmål om, hvor ofte man skal tjekke træet - vil vi gennemgå alle dele af det eller kun, når en af betingelserne har ændret sig? Hvordan gemmer vi tilstand vedrørende noder - hvordan ved vi, hvornår vi har været i tomgang i 10 sekunder, eller hvordan ved vi, hvilke noder der kørte sidste gang, så vi kan behandle sekvensen korrekt?
Derfor er der mange implementeringer. For eksempel har nogle systemer erstattet dekoratornoder med inline-dekoratorer. De revurderer træet, når dekorationsbetingelserne ændrer sig, hjælper med at forbinde noder og sørger for periodiske opdateringer.
Forsyningsbaseret system
Nogle spil har mange forskellige mekanikker. Det er ønskeligt, at de modtager alle fordelene ved enkle og generelle overgangsregler, men ikke nødvendigvis i form af et komplet adfærdstræ. I stedet for at have et klart sæt af valg eller et træ af mulige handlinger, er det lettere at undersøge alle handlingerne og vælge den mest passende i øjeblikket.
Det Utility-baserede system vil hjælpe med netop dette. Dette er et system, hvor agenten har en række handlinger og vælger, hvilke der skal udføres baseret på den relative nytte af hver. Hvor nytte er et vilkårligt mål for, hvor vigtigt eller ønskeligt det er for agenten at udføre denne handling.
Den beregnede nytte af en handling baseret på den aktuelle tilstand og miljø, kan agenten til enhver tid kontrollere og vælge den mest passende anden tilstand. Dette svarer til FSM, undtagen hvor overgange bestemmes af et estimat for hver potentiel tilstand, inklusive den nuværende. Bemærk venligst, at vi vælger den mest nyttige handling for at komme videre (eller blive, hvis vi allerede har gennemført den). For mere variation kan dette være et afbalanceret, men tilfældigt udvalg fra en lille liste.
Systemet tildeler et vilkårligt interval af nytteværdier - for eksempel fra 0 (helt uønsket) til 100 (helt ønskværdigt). Hver handling har en række parametre, der påvirker beregningen af denne værdi. For at vende tilbage til vores værgeeksempel:
Overgange mellem handlinger er tvetydige - enhver tilstand kan følge enhver anden. Handlingsprioriteter findes i de returnerede nytteværdier. Hvis en fjende er synlig, og den fjende er stærk, og karakterens helbred er lavt, så vil både Fleeing og FindingHelp returnere høje værdier, der ikke er nul. I dette tilfælde vil FindingHelp altid være højere. Ligeledes returnerer ikke-kampaktiviteter aldrig mere end 50, så de vil altid være lavere end kampaktiviteter. Du skal tage højde for dette, når du opretter handlinger og beregner deres nytte.
I vores eksempel returnerer handlingerne enten en fast konstant værdi eller en af to faste værdier. Et mere realistisk system ville returnere et estimat fra et kontinuerligt interval af værdier. For eksempel returnerer flygtningshandlingen højere nytteværdier, hvis agentens helbred er lavt, og angrebshandlingen returnerer lavere nytteværdier, hvis fjenden er for stærk. På grund af dette har flugthandlingen forrang frem for angreb i enhver situation, hvor agenten føler, at han ikke har nok helbred til at besejre fjenden. Dette gør det muligt at prioritere handlinger baseret på et vilkårligt antal kriterier, hvilket gør denne tilgang mere fleksibel og variabel end et adfærdstræ eller FSM.
Hver handling har mange betingelser for programberegning. De kan skrives i scriptsprog eller som en række matematiske formler. The Sims, som simulerer en karakters daglige rutine, tilføjer et ekstra lag af beregninger - agenten modtager en række "motivationer", der påvirker nyttevurderinger. Hvis en karakter er sulten, vil de blive endnu mere sultne med tiden, og brugsværdien af EatFood-handlingen vil stige, indtil karakteren udfører den, hvilket reducerer sultniveauet og returnerer EatFood-værdien til nul.
Ideen med at vælge handlinger baseret på et ratingsystem er ret simpel, så et Utility-baseret system kan bruges som en del af AI-beslutningsprocesser, snarere end som en komplet erstatning for dem. Beslutningstræet kan bede om en nyttevurdering af to underordnede noder og vælge den højeste. På samme måde kan et adfærdstræ have en sammensat Utility-node til at evaluere nytten af handlinger for at beslutte, hvilket barn der skal udføres.
Bevægelse og navigation
I de foregående eksempler havde vi en platform, som vi flyttede til venstre eller højre, og en vagt, der patruljerede eller angreb. Men præcis hvordan håndterer vi agentbevægelser over en periode? Hvordan indstiller vi hastighed, hvordan undgår vi forhindringer, og hvordan planlægger vi en rute, når det er sværere at komme til en destination end blot at bevæge os i en lige linje? Lad os se på dette.
ledelse
I den indledende fase vil vi antage, at hver agent har en hastighedsværdi, som inkluderer, hvor hurtigt den bevæger sig og i hvilken retning. Det kan måles i meter i sekundet, kilometer i timen, pixels i sekundet osv. Når vi genkalder Sense/Think/Act-løkken, kan vi forestille os, at Think-delen vælger en hastighed, og Act-delen anvender denne hastighed på agenten. Typisk har spil et fysiksystem, der udfører denne opgave for dig, ved at lære hastighedsværdien for hvert objekt og justere det. Derfor kan du forlade AI med én opgave - at bestemme, hvilken hastighed agenten skal have. Hvis du ved, hvor agenten skal være, så skal du flytte den i den rigtige retning med en fastsat hastighed. En meget triviel ligning:
ønsket_rejse = destination_position – agent_position
Forestil dig en 2D-verden. Agenten er ved punktet (-2,-2), destinationen er et sted i nordøst ved punktet (30, 20), og den nødvendige sti for agenten at komme dertil er (32, 22). Lad os sige, at disse positioner måles i meter - hvis vi tager agentens hastighed til at være 5 meter i sekundet, så skalerer vi vores forskydningsvektor og får en hastighed på cirka (4.12, 2.83). Med disse parametre ville agenten ankomme til sin destination på næsten 8 sekunder.
Du kan til enhver tid genberegne værdierne. Hvis agenten var halvvejs til målet, ville bevægelsen være den halve længde, men da agentens maksimale hastighed er 5 m/s (det besluttede vi ovenfor), vil hastigheden være den samme. Dette fungerer også for bevægelige mål, hvilket gør det muligt for agenten at foretage små ændringer, mens de bevæger sig.
Men vi ønsker mere variation - for eksempel langsomt at øge hastigheden for at simulere en karakter, der bevæger sig fra stående til løbende. Det samme kan gøres til sidst, inden du stopper. Disse funktioner er kendt som styreadfærd, som hver især har specifikke navne: Seek, Flee, Arrival osv. Idéen er, at accelerationskræfter kan påføres agentens hastighed, baseret på at sammenligne agentens position og aktuelle hastighed med destinationen i for at bruge forskellige metoder til at bevæge sig til målet.
Hver adfærd har et lidt forskelligt formål. Søg og ankomst er måder at flytte en agent til en destination. Hindringsundgåelse og -adskillelse justerer agentens bevægelse for at undgå forhindringer på vej mod målet. Alignment og Cohesion holder agenter i bevægelse sammen. Et hvilket som helst antal forskellige styreadfærd kan summeres til at producere en enkelt vejvektor, der tager alle faktorer i betragtning. En agent, der bruger adfærden Ankomst, Adskillelse og Forhindring til at holde sig væk fra vægge og andre agenter. Denne tilgang fungerer godt på åbne steder uden unødvendige detaljer.
Under vanskeligere forhold virker tilføjelsen af forskellig adfærd dårligere – for eksempel kan en agent sidde fast i en væg på grund af en konflikt mellem Ankomst og Hindring. Derfor skal du overveje muligheder, der er mere komplekse end blot at tilføje alle værdierne. Måden er denne: I stedet for at lægge resultaterne af hver adfærd sammen, kan du overveje bevægelse i forskellige retninger og vælge den bedste løsning.
Men i et komplekst miljø med blindgyder og valg om, hvilken vej vi skal gå, får vi brug for noget endnu mere avanceret.
At finde en måde
Styreadfærd er fantastisk til simpel bevægelse i et åbent område (fodboldbane eller arena), hvor det at komme fra A til B er en lige vej med kun mindre omveje rundt om forhindringer. For komplekse ruter har vi brug for stifinding, som er en måde at udforske verden på og beslutte en rute igennem den.
Det enkleste er at anvende et gitter på hver firkant ved siden af agenten og vurdere, hvilke af dem der får lov til at flytte sig. Hvis en af dem er en destination, så følg ruten fra hver firkant til den forrige, indtil du når begyndelsen. Dette er ruten. Ellers skal du gentage processen med andre firkanter i nærheden, indtil du finder din destination, eller du løber tør for felter (hvilket betyder, at der ikke er nogen mulig rute). Dette er det, der formelt er kendt som Breadth-First Search eller BFS (breadth-first search algorithm). Ved hvert skridt kigger han i alle retninger (deraf bredde, "bredde"). Søgerummet er som en bølgefront, der bevæger sig, indtil det når det ønskede sted – søgerummet udvides ved hvert trin, indtil slutpunktet er inkluderet, hvorefter det kan spores tilbage til begyndelsen.
Som et resultat vil du modtage en liste over firkanter, langs hvilke den ønskede rute er kompileret. Dette er stien (derfor stifinding) - en liste over steder, som agenten vil besøge, mens han følger destinationen.
Da vi kender placeringen af hvert kvadrat i verden, kan vi bruge styreadfærd til at bevæge os langs stien - fra node 1 til node 2, derefter fra node 2 til node 3, og så videre. Den enkleste mulighed er at gå mod midten af det næste felt, men en endnu bedre mulighed er at stoppe midt på kanten mellem det nuværende felt og det næste. På grund af dette vil agenten være i stand til at skære hjørner ved skarpe sving.
BFS-algoritmen har også ulemper - den udforsker lige så mange firkanter i den "forkerte" retning som i den "rigtige" retning. Det er her en mere kompleks algoritme kaldet A* (A star) kommer ind i billedet. Det fungerer på samme måde, men i stedet for blindt at undersøge nabopladser (derefter naboer til naboer, så naboer til naboer til naboer og så videre), samler den noderne i en liste og sorterer dem, så den næste undersøgte node altid er en der fører til den korteste rute. Noder er sorteret baseret på en heuristik, der tager højde for to ting – "omkostningerne" ved en hypotetisk rute til den ønskede plads (inklusive eventuelle rejseomkostninger) og et estimat af, hvor langt denne firkant er fra destinationen (forspænding af søgningen i rigtige retning).
Dette eksempel viser, at agenten udforsker en firkant ad gangen, hver gang han vælger den tilstødende, der er den mest lovende. Den resulterende sti er den samme som BFS, men færre firkanter blev overvejet i processen - hvilket har stor indflydelse på spillets ydeevne.
Bevægelse uden et gitter
Men de fleste spil er ikke lagt ud på et gitter, og det er ofte umuligt at gøre det uden at ofre realismen. Der er brug for kompromiser. Hvilken størrelse skal firkanterne være? For store og de vil ikke være i stand til korrekt at repræsentere små korridorer eller sving, for små og der vil være for mange firkanter at søge efter, hvilket i sidste ende vil tage meget tid.
Den første ting at forstå er, at et mesh giver os en graf over forbundne noder. A*- og BFS-algoritmerne virker faktisk på grafer og er slet ikke ligeglade med vores mesh. Vi kunne placere noder hvor som helst i spilverdenen: så længe der er en forbindelse mellem to forbundne noder, såvel som mellem start- og slutpunkterne og mindst én af noderne, vil algoritmen fungere lige så godt som før. Dette kaldes ofte et waypoint-system, da hver knude repræsenterer en væsentlig position i verden, som kan være en del af et hvilket som helst antal hypotetiske stier.
Eksempel 1: en knude i hver firkant. Søgningen starter fra det knudepunkt, hvor agenten er placeret, og slutter ved knudepunktet på den ønskede firkant.
Eksempel 2: Et mindre sæt af noder (waypoints). Søgningen starter ved agentens plads, går gennem det nødvendige antal noder og fortsætter derefter til destinationen.
Dette er et fuldstændig fleksibelt og kraftfuldt system. Men en vis omhu er nødvendig for at beslutte, hvor og hvordan et waypoint skal placeres, ellers kan agenter simpelthen ikke se det nærmeste punkt og vil ikke være i stand til at starte stien. Det ville være nemmere, hvis vi automatisk kunne placere waypoints baseret på verdens geometri.
Det er her navigationsmasken eller navmesh (navigationsmaske) vises. Dette er normalt et 2D-net af trekanter, der er overlejret på verdens geometri - hvor end agenten får lov til at gå. Hver af trekanter i nettet bliver en knude i grafen og har op til tre tilstødende trekanter, der bliver til tilstødende knudepunkter i grafen.
Dette billede er et eksempel fra Unity-motoren - den analyserede geometrien i verden og skabte en navmesh (i skærmbilledet i lyseblå). Hver polygon i en navmesh er et område, hvor en agent kan stå eller flytte fra en polygon til en anden polygon. I dette eksempel er polygonerne mindre end de etager, de er placeret på - dette gøres for at tage højde for størrelsen af agenten, som vil strække sig ud over dens nominelle position.
Vi kan søge efter en rute gennem dette net, igen ved hjælp af A*-algoritmen. Dette vil give os en næsten perfekt rute i verden, som tager højde for al geometri og ikke kræver unødvendige noder og oprettelse af waypoints.
Pathfinding er et for bredt emne, hvor et afsnit af en artikel ikke er nok. Hvis du vil studere det mere detaljeret, så vil dette hjælpe .
planlægning
Vi har lært med stifinding, at nogle gange er det ikke nok bare at vælge en retning og flytte - vi skal vælge en rute og lave et par sving for at komme til vores ønskede destination. Vi kan generalisere denne idé: at opnå et mål er ikke bare det næste skridt, men en hel sekvens, hvor du nogle gange skal se fremad flere skridt for at finde ud af, hvad det første skal være. Dette kaldes planlægning. Pathfinding kan opfattes som en af flere udvidelser til planlægning. Med hensyn til vores Sense/Think/Act-cyklus er det her, Think-delen planlægger flere Act-dele for fremtiden.
Lad os se på eksemplet med brætspillet Magic: The Gathering. Vi går først med følgende sæt kort i vores hænder:
- Sump - Giver 1 sort mana (landkort).
- Skov - giver 1 grøn mana (landkort).
- Fugitive Wizard - Kræver 1 blå mana for at tilkalde.
- Elvish Mystic - Kræver 1 grøn mana for at tilkalde.
Vi ignorerer de resterende tre kort for at gøre det nemmere. I henhold til reglerne har en spiller lov til at spille 1 landkort pr. tur, han kan "tappe" på dette kort for at udtrække mana fra det, og derefter kaste trylleformularer (inklusive tilkalde et væsen) i henhold til mængden af mana. I denne situation ved den menneskelige spiller at spille Skov, trykke på 1 grøn mana og derefter tilkalde Elvish Mystic. Men hvordan kan spillets AI finde ud af dette?
Nem planlægning
Den trivielle tilgang er at prøve hver handling efter tur, indtil der ikke er nogen passende tilbage. Ved at se på kortene ser AI, hvad Swamp kan spille. Og han spiller det. Er der andre handlinger tilbage denne tur? Den kan hverken tilkalde Elvish Mystic eller Fugitive Wizard, da de kræver henholdsvis grøn og blå mana for at tilkalde dem, mens Swamp kun giver sort mana. Og han vil ikke længere kunne spille Skov, for han har allerede spillet Swamp. Således fulgte spillet AI reglerne, men gjorde det dårligt. Kan forbedres.
Planlægning kan finde en liste over handlinger, der bringer spillet til den ønskede tilstand. Ligesom hver firkant på en sti havde naboer (i stifinding), har enhver handling i en plan også naboer eller efterfølgere. Vi kan lede efter disse handlinger og efterfølgende handlinger, indtil vi når den ønskede tilstand.
I vores eksempel er det ønskede resultat "tilkalde et væsen, hvis det er muligt." I begyndelsen af turen ser vi kun to mulige handlinger tilladt af spillets regler:
1. Spil Swamp (resultat: Sump i spillet)
2. Spil Skov (resultat: Skov i spillet)
Hver handling, der tages, kan føre til yderligere handlinger og lukke andre, igen afhængigt af spillets regler. Forestil dig, at vi spillede Swamp - dette vil fjerne Swamp som det næste trin (vi har allerede spillet det), og dette vil også fjerne Forest (fordi ifølge reglerne kan du spille et landkort pr. tur). Herefter tilføjer AI at få 1 sort mana som næste trin, fordi der ikke er andre muligheder. Hvis han går videre og vælger Tap the Swamp, vil han modtage 1 enhed sort mana og vil ikke være i stand til at gøre noget med det.
1. Spil Swamp (resultat: Sump i spillet)
1.1 "Tap" sump (resultat: sump "tappet", +1 enhed sort mana)
Ingen tilgængelige handlinger - SLUT
2. Spil Skov (resultat: Skov i spillet)
Listen over handlinger var kort, vi nåede en blindgyde. Vi gentager processen til næste trin. Vi spiller Skov, åbner handlingen "få 1 grøn mana", som igen vil åbne den tredje handling - tilkalde Elvish Mystic.
1. Spil Swamp (resultat: Sump i spillet)
1.1 "Tap" sump (resultat: sump "tappet", +1 enhed sort mana)
Ingen tilgængelige handlinger - SLUT
2. Spil Skov (resultat: Skov i spillet)
2.1 "Tap" Skov (resultat: Skov er "tappet", +1 enhed grøn mana)
2.1.1 Summon Elvish Mystic (resultat: Elvish Mystic i spil, -1 grøn mana)
Ingen tilgængelige handlinger - SLUT
Til sidst undersøgte vi alle mulige handlinger og fandt en plan, der tilkalder et væsen.
Dette er et meget forenklet eksempel. Det er tilrådeligt at vælge den bedst mulige plan frem for blot en plan, der opfylder nogle kriterier. Det er generelt muligt at evaluere potentielle planer baseret på resultatet eller den samlede fordel ved deres implementering. Du kan score dig selv 1 point for at spille et landkort og 3 point for at tilkalde et væsen. At spille Swamp ville være en 1 point plan. Og at spille Skov → Tryk på Skoven → tilkald Elvish Mystic vil straks give 4 point.
Sådan fungerer planlægningen i Magic: The Gathering, men den samme logik gælder i andre situationer. For eksempel at flytte en bonde for at give plads til, at biskoppen kan bevæge sig i skak. Eller dæk dig bag en mur for sikkert at skyde i XCOM som denne. Generelt forstår du ideen.
Forbedret planlægning
Nogle gange er der for mange potentielle handlinger til at overveje alle mulige muligheder. For at vende tilbage til eksemplet med Magic: The Gathering: lad os sige, at der i spillet og i din hånd er flere land- og væsenkort - antallet af mulige kombinationer af træk kan være i snesevis. Der er flere løsninger på problemet.
Den første metode er baglæns kæde. I stedet for at prøve alle kombinationerne, er det bedre at starte med det endelige resultat og prøve at finde en direkte rute. I stedet for at gå fra træets rod til et bestemt blad, bevæger vi os i den modsatte retning – fra bladet til roden. Denne metode er nemmere og hurtigere.
Hvis fjenden har 1 helbred, kan du finde "deal 1 or more damage"-planen. For at opnå dette skal en række betingelser være opfyldt:
1. Skader kan være forårsaget af en besværgelse - den skal være i hånden.
2. For at besværge, skal du bruge mana.
3. For at få mana skal du spille et landkort.
4. For at spille et landkort skal du have det på hånden.
En anden måde er bedst-først-søgning. I stedet for at prøve alle veje, vælger vi den bedst egnede. Oftest giver denne metode den optimale plan uden unødvendige søgeomkostninger. A* er en form for bedste første søgning - ved at undersøge de mest lovende ruter fra begyndelsen, kan den allerede finde den bedste vej uden at skulle tjekke andre muligheder.
En interessant og stadig mere populær bedste-første søgemulighed er Monte Carlo Tree Search. I stedet for at gætte, hvilke planer der er bedre end andre, når de vælger hver efterfølgende handling, vælger algoritmen tilfældige efterfølgere ved hvert trin, indtil den når slutningen (når planen resulterede i sejr eller nederlag). Det endelige resultat bruges derefter til at øge eller mindske vægten af tidligere muligheder. Ved at gentage denne proces flere gange i træk giver algoritmen et godt bud på, hvad det bedste næste træk er, selvom situationen ændrer sig (hvis fjenden griber ind for at forstyrre spilleren).
Ingen historie om planlægning i spil ville være komplet uden målorienteret handlingsplanlægning eller GOAP (målorienteret handlingsplanlægning). Dette er en meget brugt og diskuteret metode, men bortset fra nogle få karakteristiske detaljer, er det i det væsentlige den baglæns kædemetode, vi talte om tidligere. Hvis målet var "ødelægge spilleren", og spilleren er bagdækket, kunne planen være: ødelægge med en granat → få den → smid den.
Der er normalt flere mål, hver med sin egen prioritet. Hvis det højest prioriterede mål ikke kan fuldføres (ingen kombination af handlinger skaber en "dræb spilleren"-plan, fordi spilleren ikke er synlig), vil AI falde tilbage til lavere prioriterede mål.
Træning og tilpasning
Vi har allerede sagt, at spil AI normalt ikke bruger maskinlæring, fordi det ikke er egnet til at administrere agenter i realtid. Men det betyder ikke, at du ikke kan låne noget fra dette område. Vi vil have en modstander i en skytte, som vi kan lære noget af. Find for eksempel ud af de bedste positioner på kortet. Eller en modstander i et kampspil, der ville blokere spillerens ofte brugte kombinationsbevægelser og motivere ham til at bruge andre. Så maskinlæring kan være ret nyttig i sådanne situationer.
Statistik og sandsynligheder
Før vi kommer ind på komplekse eksempler, lad os se, hvor langt vi kan gå ved at tage et par enkle målinger og bruge dem til at træffe beslutninger. For eksempel realtidsstrategi - hvordan afgør vi, om en spiller kan starte et angreb i de første par minutter af spillet, og hvilket forsvar skal forberede sig mod dette? Vi kan studere en spillers tidligere oplevelser for at forstå, hvad fremtidige reaktioner kan være. Til at begynde med har vi ikke sådanne rådata, men vi kan indsamle dem - hver gang AI'en spiller mod et menneske, kan den registrere tidspunktet for det første angreb. Efter et par sessioner vil vi få et gennemsnit af den tid, det vil tage for spilleren at angribe i fremtiden.
Der er også et problem med gennemsnitlige værdier: hvis en spiller skyndte sig 20 gange og spillede langsomt 20 gange, så vil de nødvendige værdier være et sted i midten, og det vil ikke give os noget nyttigt. En løsning er at begrænse inputdata - de sidste 20 stykker kan tages i betragtning.
En lignende tilgang bruges, når man estimerer sandsynligheden for visse handlinger ved at antage, at spillerens tidligere præferencer vil være de samme i fremtiden. Hvis en spiller angriber os fem gange med ildkugle, to gange med lyn og en gang med nærkamp, er det tydeligt, at han foretrækker ildkugle. Lad os ekstrapolere og se sandsynligheden for at bruge forskellige våben: ildkugle=62,5%, lyn=25% og nærkamp=12,5%. Vores AI-spil skal forberede sig på at beskytte sig selv mod ild.
En anden interessant metode er at bruge Naive Bayes Classifier til at studere store mængder inputdata og klassificere situationen, så AI’en reagerer på den ønskede måde. Bayesianske klassifikatorer er bedst kendt for deres brug i e-mail-spamfiltre. Der undersøger de ordene, sammenligner dem med, hvor disse ord er dukket op før (i spam eller ej), og drager konklusioner om indgående e-mails. Vi kan gøre det samme selv med færre input. Baseret på al den nyttige information, som AI ser (såsom hvilke fjendtlige enheder er oprettet, eller hvilke besværgelser de bruger, eller hvilke teknologier de undersøgte), og det endelige resultat (krig eller fred, jag eller forsvar osv.) - vi vælger den ønskede AI-adfærd.
Alle disse træningsmetoder er tilstrækkelige, men det er tilrådeligt at bruge dem baseret på testdata. AI vil lære at tilpasse sig de forskellige strategier, som dine playtestere har brugt. AI, der tilpasser sig spilleren efter udgivelsen, kan blive for forudsigelig eller for svær at besejre.
Værdibaseret tilpasning
I betragtning af indholdet af vores spilverden og reglerne kan vi ændre det sæt af værdier, der påvirker beslutningstagningen, i stedet for blot at bruge inputdataene. Vi gør dette:
- Lad AI’en indsamle data om verdens tilstand og vigtige begivenheder under spillet (som ovenfor).
- Lad os ændre et par vigtige værdier baseret på disse data.
- Vi implementerer vores beslutninger baseret på behandling eller evaluering af disse værdier.
For eksempel har en agent flere rum at vælge imellem på et first-person shooter-kort. Hvert værelse har sin egen værdi, som afgør, hvor ønskværdigt det er at besøge. AI'en vælger tilfældigt, hvilket rum der skal gå til baseret på værdien. Agenten husker så, hvilket rum han blev dræbt i og reducerer dets værdi (sandsynligheden for, at han vender tilbage dertil). Tilsvarende for den omvendte situation - hvis agenten ødelægger mange modstandere, så stiger værdien af rummet.
Markov model
Hvad hvis vi brugte de indsamlede data til at lave forudsigelser? Hvis vi husker hvert rum, vi ser en spiller i i en vis periode, vil vi forudsige, hvilket rum spilleren kan gå til. Ved at spore og registrere spillerens bevægelser på tværs af rum (værdier), kan vi forudsige dem.
Lad os tage tre rum: rød, grøn og blå. Og også de observationer, som vi optog, mens vi så spilsessionen:
Antallet af observationer i hvert rum er næsten det samme - vi ved stadig ikke, hvor vi skal lave et godt sted for et baghold. Indsamling af statistik er også kompliceret af, at spillere genopstår, som vises jævnt over hele kortet. Men dataene om det næste rum, de går ind i, efter at de er blevet vist på kortet, er allerede nyttige.
Det kan ses, at green room passer til spillerne - de fleste flytter fra det røde rum til det, hvoraf 50% bliver der længere. Det blå rum er tværtimod ikke populært; næsten ingen går til det, og hvis de gør det, bliver de ikke længe.
Men dataene fortæller os noget mere vigtigt - når en spiller er i et blåt rum, vil det næste rum, vi ser ham i, være rødt, ikke grønt. Selvom det grønne rum er mere populært end det røde rum, ændrer situationen sig, hvis spilleren er i det blå rum. Den næste tilstand (dvs. det rum, spilleren vil gå til) afhænger af den tidligere tilstand (dvs. det rum, spilleren er i i øjeblikket). Fordi vi udforsker afhængigheder, vil vi lave mere præcise forudsigelser, end hvis vi blot talte observationer uafhængigt.
At forudsige en fremtidig tilstand baseret på data fra en tidligere tilstand kaldes en Markov-model, og sådanne eksempler (med rum) kaldes Markov-kæder. Da mønstrene repræsenterer sandsynligheden for ændringer mellem på hinanden følgende tilstande, vises de visuelt som FSM'er med en sandsynlighed omkring hver overgang. Tidligere brugte vi FSM til at repræsentere den adfærdsmæssige tilstand, som en agent var i, men dette koncept strækker sig til enhver tilstand, uanset om det er forbundet med agenten eller ej. I dette tilfælde repræsenterer staterne det rum, agenten optager:
Dette er en enkel måde at repræsentere den relative sandsynlighed for tilstandsændringer, hvilket giver AI en vis evne til at forudsige den næste tilstand. Du kan forudse flere skridt frem.
Hvis en spiller er i green room, er der 50 % chance for, at han bliver der, næste gang han bliver observeret. Men hvad er chancerne for, at han stadig vil være der selv efter? Ikke alene er der en chance for, at spilleren forblev i green room efter to observationer, men der er også en chance for, at han forlod og vendte tilbage. Her er den nye tabel, der tager højde for de nye data:
Det viser, at chancen for at se spilleren i det grønne rum efter to observationer vil være lig med 51 % - 21 % for, at han kommer fra det røde rum, 5 % af dem, at spilleren vil besøge det blå rum mellem dem, og 25%, at spilleren ikke vil forlade green room.
Tabellen er simpelthen et visuelt værktøj - proceduren kræver kun at gange sandsynligheden på hvert trin. Det betyder, at du kan se langt ud i fremtiden med én advarsel: Vi antager, at chancen for at komme ind i et rum afhænger helt af det aktuelle rum. Dette kaldes Markov-ejendommen - den fremtidige tilstand afhænger kun af nutiden. Men dette er ikke XNUMX% nøjagtigt. Spillere kan ændre beslutninger afhængigt af andre faktorer: sundhedsniveau eller mængden af ammunition. Fordi vi ikke registrerer disse værdier, vil vores prognoser være mindre nøjagtige.
N-gram
Hvad med eksemplet med et kampspil og forudsigelse af spillerens kombinationsbevægelser? Det samme! Men i stedet for én tilstand eller begivenhed, vil vi undersøge hele sekvensen, der udgør et kombinationsstrejke.
En måde at gøre dette på er at gemme hvert input (såsom Kick, Punch eller Block) i en buffer og skrive hele bufferen som en hændelse. Så spilleren trykker gentagne gange på Kick, Kick, Punch for at bruge SuperDeathFist-angrebet, AI-systemet gemmer alle input i en buffer og husker de sidste tre brugte i hvert trin.
(Linjerne med fed skrift er, når spilleren starter SuperDeathFist-angrebet.)
AI vil se alle mulighederne, når spilleren vælger Kick, efterfulgt af endnu et Kick, og så bemærker, at det næste input altid er Punch. Dette vil give agenten mulighed for at forudsige SuperDeathFists kombinationsbevægelse og blokere den, hvis det er muligt.
Disse sekvenser af begivenheder kaldes N-gram, hvor N er antallet af lagrede elementer. I det foregående eksempel var det et 3-gram (trigram), hvilket betyder: de første to indgange bruges til at forudsige den tredje. Derfor forudsiger de første fire poster i en 5-grams den femte og så videre.
Designeren skal vælge størrelsen på N-gram omhyggeligt. Et mindre N kræver mindre hukommelse, men gemmer også mindre historie. For eksempel vil et 2-gram (bigram) optage Kick, Kick eller Kick, Punch, men vil ikke være i stand til at gemme Kick, Kick, Punch, så AI vil ikke reagere på SuperDeathFist-kombinationen.
På den anden side kræver større antal mere hukommelse, og AI vil være sværere at træne, da der vil være mange flere mulige muligheder. Hvis du havde tre mulige input af Kick, Punch eller Block, og vi brugte en 10-grams, ville det være omkring 60 tusinde forskellige muligheder.
Bigrammodellen er en simpel Markov-kæde - hvert tidligere tilstand/nuværende tilstandspar er et bigram, og du kan forudsige den anden tilstand baseret på den første. De 3-grams og større N-grammer kan også opfattes som Markov-kæder, hvor alle elementer (undtagen det sidste i N-grammet) tilsammen danner den første tilstand og det sidste element den anden. Eksemplet med kampspil viser chancen for at skifte fra Kick and Kick-tilstanden til Kick and Punch-tilstanden. Ved at behandle flere inputhistorikposter som en enkelt enhed, transformerer vi i det væsentlige inputsekvensen til en del af hele tilstanden. Dette giver os Markov-egenskaben, som giver os mulighed for at bruge Markov-kæder til at forudsige det næste input og gætte, hvilket kombinationstræk der bliver det næste.
Konklusion
Vi talte om de mest almindelige værktøjer og tilgange i udviklingen af kunstig intelligens. Vi har også set på de situationer, hvor de skal bruges, og hvor de er særligt nyttige.
Dette burde være nok til at forstå det grundlæggende i spil AI. Men det er selvfølgelig ikke alle metoder. Mindre populær, men ikke mindre effektiv inkluderer:
- optimeringsalgoritmer inklusive bakkeklatring, gradientnedstigning og genetiske algoritmer
- modstridende søge-/planlægningsalgoritmer (minimax og alfa-beta beskæring)
- klassifikationsmetoder (perceptroner, neurale netværk og støttevektormaskiner)
- systemer til behandlingsagenters opfattelse og hukommelse
- arkitektoniske tilgange til AI (hybride systemer, undergruppearkitekturer og andre måder at overlejre AI-systemer på)
- animationsværktøjer (planlægning og bevægelseskoordinering)
- præstationsfaktorer (detaljeringsniveau, når som helst og tidsopdelingsalgoritmer)
Online ressourcer om emnet:
1. GameDev.net har og .
2. indeholder mange præsentationer og artikler om en bred vifte af emner relateret til udvikling af spil AI.
3. indeholder emner fra GDC AI Summit, hvoraf mange er tilgængelige gratis.
4. Nyttige materialer kan også findes på hjemmesiden .
5. Tommy Thompson, AI-forsker og spiludvikler, laver videoer på YouTube med en forklaring og undersøgelse af AI i kommercielle spil.
Bøger om emnet:
1. Game AI Pro-bogserien er en samling korte artikler, der forklarer, hvordan man implementerer specifikke funktioner, eller hvordan man løser specifikke problemer.
2. AI Game Programming Wisdom-serien er forgængeren til Game AI Pro-serien. Den indeholder ældre metoder, men næsten alle er relevante også i dag.
3. er en af grundteksterne for alle, der ønsker at forstå det generelle felt af kunstig intelligens. Dette er ikke en bog om spiludvikling - den lærer det grundlæggende i AI.
Kilde: www.habr.com