Ik kwam interessant materiaal tegen over kunstmatige intelligentie in games. Met een uitleg van basiszaken over AI aan de hand van eenvoudige voorbeelden, en binnenin zijn er veel handige tools en methoden voor de gemakkelijke ontwikkeling en ontwerp ervan. Hoe, waar en wanneer je ze moet gebruiken staat er ook bij.
De meeste voorbeelden zijn geschreven in pseudocode, er is dus geen geavanceerde programmeerkennis vereist. Onder de snit bevinden zich 35 vellen tekst met afbeeldingen en gifs, dus maak je klaar.
UPD. Mijn excuses, maar ik heb mijn eigen vertaling van dit artikel al op Habré gedaan . Je kunt zijn versie lezen , maar om de een of andere reden kwam het artikel aan mij voorbij (ik gebruikte de zoekopdracht, maar er ging iets mis). En aangezien ik aan het schrijven ben op een blog gewijd aan de ontwikkeling van games, heb ik besloten mijn versie van de vertaling voor abonnees achter te laten (sommige punten zijn anders opgemaakt, sommige zijn opzettelijk weggelaten op advies van de ontwikkelaars).
Wat is AI?
Game AI richt zich op welke acties een object moet uitvoeren op basis van de omstandigheden waarin het zich bevindt. Dit wordt gewoonlijk 'intelligente agent'-beheer genoemd, waarbij een agent een personage van een speler, een voertuig, een bot of soms iets abstracters is: een hele groep entiteiten of zelfs een beschaving. In elk geval is het iets dat zijn omgeving moet zien, op basis daarvan beslissingen moet nemen en in overeenstemming daarmee moet handelen. Dit wordt de Sense/Think/Act-cyclus genoemd:
- Sense: De agent vindt of ontvangt informatie over dingen in zijn omgeving die zijn gedrag kunnen beïnvloeden (bedreigingen in de buurt, te verzamelen items, interessante plaatsen om te verkennen).
- Denk na: de agent beslist hoe hij moet reageren (denkt na of het veilig genoeg is om items te verzamelen of dat hij eerst moet vechten/verbergen).
- Handelen: de agent voert acties uit om de eerdere beslissing uit te voeren (begint richting de vijand of het object te bewegen).
- ...nu is de situatie veranderd door de acties van de personages, dus herhaalt de cyclus zich met nieuwe gegevens.
AI heeft de neiging zich te concentreren op het Sense-gedeelte van de lus. Zelfrijdende auto’s maken bijvoorbeeld foto’s van de weg, combineren deze met radar- en lidargegevens en interpreteren deze. Dit wordt meestal gedaan door machine learning, dat binnenkomende gegevens verwerkt en betekenis geeft, door semantische informatie te extraheren zoals ‘er staat nog een auto 20 meter voor je’. Dit zijn de zogenaamde classificatieproblemen.
Games hebben geen complex systeem nodig om informatie te extraheren, omdat de meeste gegevens er al een integraal onderdeel van zijn. Het is niet nodig om beeldherkenningsalgoritmen uit te voeren om te bepalen of er een vijand in de buurt is: de game weet het al en voert de informatie rechtstreeks in het besluitvormingsproces in. Daarom is het Sense-gedeelte van de cyclus vaak veel eenvoudiger dan het Think and Act-gedeelte.
Beperkingen van Game-AI
AI heeft een aantal beperkingen die in acht moeten worden genomen:
- AI hoeft niet vooraf getraind te worden, alsof het een machine learning-algoritme is. Het heeft geen zin om tijdens de ontwikkeling een neuraal netwerk te schrijven om tienduizenden spelers te monitoren en te leren hoe je het beste tegen hen kunt spelen. Waarom? Omdat de game nog niet is uitgebracht en er geen spelers zijn.
- Het spel moet leuk en uitdagend zijn, dus agenten moeten niet de beste aanpak tegen mensen vinden.
- Agenten moeten er realistisch uitzien, zodat spelers het gevoel krijgen dat ze tegen echte mensen spelen. Het AlphaGo-programma presteerde beter dan mensen, maar de gekozen stappen stonden ver af van de traditionele opvatting van het spel. Als het spel een menselijke tegenstander simuleert, zou dit gevoel niet moeten bestaan. Het algoritme moet zodanig worden gewijzigd dat het plausibele beslissingen neemt in plaats van ideale beslissingen.
- AI moet in realtime werken. Dit betekent dat het algoritme het CPU-gebruik niet gedurende lange perioden kan monopoliseren om beslissingen te nemen. Zelfs 10 milliseconden is te lang, omdat de meeste games slechts 16 tot 33 milliseconden nodig hebben om alle verwerking uit te voeren en door te gaan naar het volgende grafische frame.
- Idealiter zou tenminste een deel van het systeem datagestuurd moeten zijn, zodat niet-codeerders wijzigingen kunnen aanbrengen en aanpassingen sneller kunnen plaatsvinden.
Laten we eens kijken naar AI-benaderingen die de hele Sense/Think/Act-cyclus bestrijken.
Basisbeslissingen nemen
Laten we beginnen met het eenvoudigste spel: Pong. Doel: beweeg de peddel zo dat de bal ertegen stuitert in plaats van er voorbij vliegt. Het is net als tennis, waarbij je verliest als je de bal niet raakt. Hier heeft de AI een relatief eenvoudige taak: beslissen in welke richting het platform moet worden verplaatst.
Voorwaardelijke stellingen
Voor de AI in Pong is de meest voor de hand liggende oplossing om altijd te proberen het platform onder de bal te plaatsen.
Een eenvoudig algoritme hiervoor, geschreven in pseudocode:
elk frame/update terwijl het spel draait:
als de bal zich links van de peddel bevindt:
beweeg de peddel naar links
anders als de bal zich rechts van de paddle bevindt:
beweeg de peddel naar rechts
Als het platform beweegt met de snelheid van de bal, dan is dit het ideale algoritme voor de AI in Pong. Het is niet nodig om iets ingewikkelds te maken als er niet zoveel gegevens en mogelijke acties voor de agent zijn.
Deze aanpak is zo eenvoudig dat de hele Sense/Think/Act-cyclus nauwelijks merkbaar is. Maar het is er:
- Het Sense-gedeelte bestaat uit twee if-instructies. De game weet waar de bal ligt en waar het platform zich bevindt, dus de AI kijkt ernaar op zoek naar die informatie.
- Het Think-gedeelte is ook opgenomen in de twee if-instructies. Ze belichamen twee oplossingen, die in dit geval elkaar uitsluiten. Als gevolg hiervan wordt een van de drie acties geselecteerd: verplaats het platform naar links, verplaats het naar rechts of doe niets als het al correct is gepositioneerd.
- Het Act-gedeelte is te vinden in de uitspraken Move Paddle Left en Move Paddle Right. Afhankelijk van het spelontwerp kunnen ze het platform onmiddellijk of met een bepaalde snelheid verplaatsen.
Dergelijke benaderingen worden reactief genoemd - er is een eenvoudige reeks regels (in dit geval als uitspraken in de code) die reageren op de huidige toestand van de wereld en actie ondernemen.
Beslissingsboom
Het Pong-voorbeeld is feitelijk gelijk aan een formeel AI-concept dat een beslisboom wordt genoemd. Het algoritme gaat er doorheen om een ‘blad’ te bereiken: een beslissing over welke actie moet worden ondernomen.
Laten we een blokdiagram maken van de beslisboom voor het algoritme van ons platform:
Elk deel van de boom wordt een knooppunt genoemd. AI gebruikt grafentheorie om dergelijke structuren te beschrijven. Er zijn twee soorten knooppunten:
- Beslissingsknooppunten: kiezen tussen twee alternatieven op basis van het testen van een bepaalde voorwaarde, waarbij elk alternatief wordt weergegeven als een afzonderlijk knooppunt.
- Eindknooppunten: de uit te voeren actie die de uiteindelijke beslissing vertegenwoordigt.
Het algoritme begint vanaf het eerste knooppunt (de “wortel” van de boom). Het neemt een beslissing over naar welk onderliggende knooppunt het moet gaan, of voert de actie uit die in het knooppunt is opgeslagen en verlaat het knooppunt.
Wat is het voordeel als een beslisboom hetzelfde werk doet als de if-instructies in de vorige sectie? Er is hier sprake van een algemeen systeem waarbij elke beslissing slechts één voorwaarde en twee mogelijke uitkomsten heeft. Hierdoor kan de ontwikkelaar AI creëren op basis van gegevens die beslissingen in een boom vertegenwoordigen, zonder deze hard te hoeven coderen. Laten we het in de vorm van een tabel presenteren:
Aan de codekant krijg je een systeem voor het lezen van strings. Maak voor elk daarvan een knooppunt, verbind beslissingslogica op basis van de tweede kolom en onderliggende knooppunten op basis van de derde en vierde kolom. Je moet nog steeds de voorwaarden en acties programmeren, maar nu zal de structuur van het spel complexer zijn. Hier voegt u extra beslissingen en acties toe en past u vervolgens de gehele AI aan door eenvoudigweg het boomdefinitietekstbestand te bewerken. Vervolgens draagt u het bestand over aan de gameontwerper, die het gedrag kan veranderen zonder het spel opnieuw te compileren of de code te wijzigen.
Beslisbomen zijn erg handig als ze automatisch worden opgebouwd op basis van een grote reeks voorbeelden (bijvoorbeeld met behulp van het ID3-algoritme). Dit maakt ze tot een effectief en krachtig hulpmiddel voor het classificeren van situaties op basis van de verkregen gegevens. We gaan echter verder dan een eenvoudig systeem waarmee agenten acties kunnen selecteren.
Scripts
We analyseerden een beslisboomsysteem dat gebruik maakte van vooraf gecreëerde voorwaarden en acties. De persoon die de AI ontwerpt, kan de boom indelen zoals hij wil, maar hij is nog steeds afhankelijk van de codeur die alles heeft geprogrammeerd. Wat als we de ontwerper de tools konden geven om zijn eigen voorwaarden of acties te creëren?
Zodat de programmeur geen code hoeft te schrijven voor de voorwaarden Is Ball Left Of Paddle en Is Ball Right Of Paddle, kan hij een systeem maken waarin de ontwerper voorwaarden schrijft om deze waarden te controleren. De beslisboomgegevens zien er dan als volgt uit:
Dit is in wezen hetzelfde als in de eerste tabel, maar de oplossingen op zichzelf hebben hun eigen code, een beetje zoals het voorwaardelijke deel van een if-instructie. Aan de codekant zou dit in de tweede kolom staan voor de beslissingsknooppunten, maar in plaats van te zoeken naar een specifieke voorwaarde om uit te voeren (Is Ball Left Of Paddle), evalueert het de voorwaardelijke expressie en retourneert dienovereenkomstig waar of onwaar. Dit gebeurt met behulp van de Lua- of Angelscript-scripttaal. Met behulp hiervan kan een ontwikkelaar objecten in zijn spel nemen (bal en peddel) en variabelen creëren die beschikbaar zullen zijn in het script (ball.position). Bovendien is de scripttaal eenvoudiger dan C++. Het vereist geen volledige compilatiefase, dus het is ideaal om de spellogica snel aan te passen en stelt “niet-codeurs” in staat zelf de nodige functies te creëren.
In het bovenstaande voorbeeld wordt de scripttaal alleen gebruikt om de voorwaardelijke expressie te evalueren, maar deze kan ook voor acties worden gebruikt. De gegevens Move Paddle Right kunnen bijvoorbeeld een scriptinstructie worden (ball.position.x += 10). Zodat de actie ook in het script wordt gedefinieerd, zonder dat Move Paddle Right hoeft te worden geprogrammeerd.
Je kunt nog verder gaan en de hele beslisboom in een scripttaal schrijven. Dit zal code zijn in de vorm van hardgecodeerde voorwaardelijke instructies, maar deze zullen zich in externe scriptbestanden bevinden, dat wil zeggen dat ze kunnen worden gewijzigd zonder het hele programma opnieuw te compileren. Je kunt het scriptbestand vaak tijdens het spelen bewerken om snel verschillende AI-reacties te testen.
Reactie op gebeurtenis
De bovenstaande voorbeelden zijn perfect voor Pong. Ze doorlopen voortdurend de Sense/Think/Act-cyclus en handelen op basis van de laatste stand van de wereld. Maar in complexere games moet je reageren op individuele gebeurtenissen en niet alles in één keer evalueren. Pong is in dit geval al een slecht voorbeeld. Laten we een andere kiezen.
Stel je een shooter voor waarbij de vijanden bewegingloos zijn totdat ze de speler detecteren, waarna ze handelen afhankelijk van hun “specialisatie”: iemand zal rennen om te “rushen”, iemand zal van ver aanvallen. Het is nog steeds een fundamenteel reactief systeem - "als een speler wordt opgemerkt, doe dan iets" - maar het kan logischerwijs worden opgesplitst in een Player Seen-gebeurtenis en een Reactie (selecteer een reactie en voer deze uit).
Dit brengt ons terug bij de cyclus van voelen/denken/handelen. We kunnen een Sense-onderdeel coderen dat elk frame controleert of de AI de speler ziet. Als dit niet het geval is, gebeurt er niets, maar als het ziet, wordt het Player Seen-evenement aangemaakt. De code heeft een apart gedeelte met de tekst "wanneer de Player Seen-gebeurtenis plaatsvindt, doe dan", waar het antwoord is dat u nodig hebt om de Denk- en Handel-onderdelen aan te pakken. Zo stel je reacties op de Player Seen-gebeurtenis in: voor het "haastende" personage - ChargeAndAttack, en voor de sluipschutter - HideAndSnipe. Deze relaties kunnen in het gegevensbestand worden aangemaakt, zodat ze snel kunnen worden bewerkt zonder dat ze opnieuw hoeven te compileren. Hier kan ook scripttaal worden gebruikt.
Moeilijke beslissingen nemen
Hoewel eenvoudige reactiesystemen zeer krachtig zijn, zijn er veel situaties waarin ze niet voldoende zijn. Soms moet je andere beslissingen nemen op basis van wat de agent momenteel doet, maar het is moeilijk voor te stellen dat dit een voorwaarde is. Soms zijn er te veel voorwaarden om deze effectief weer te geven in een beslisboom of script. Soms moet je vooraf inschatten hoe de situatie zal veranderen, voordat je besluit over de volgende stap. Er zijn meer geavanceerde benaderingen nodig om deze problemen op te lossen.
Eindigetoestandsautomaat
Finite State Machine of FSM (finite State Machine) is een manier om te zeggen dat onze agent zich momenteel in een van de verschillende mogelijke staten bevindt en dat hij van de ene staat naar de andere kan overgaan. Er zijn een bepaald aantal van dergelijke staten – vandaar de naam. Het beste voorbeeld uit het leven is een stoplicht. Er zijn verschillende lichtreeksen op verschillende plaatsen, maar het principe is hetzelfde: elke toestand vertegenwoordigt iets (stoppen, lopen, enz.). Een verkeerslicht bevindt zich op elk moment in slechts één toestand en beweegt van de ene naar de andere op basis van eenvoudige regels.
Het is een soortgelijk verhaal met NPC's in games. Laten we bijvoorbeeld een bewaker nemen met de volgende toestanden:
- Patrouilleren.
- Aanvallend.
- Op de vlucht.
En deze voorwaarden voor het veranderen van de staat:
- Als de bewaker de vijand ziet, valt hij aan.
- Als de bewaker aanvalt maar de vijand niet meer ziet, keert hij terug om te patrouilleren.
- Als een bewaker aanvalt maar zwaar gewond raakt, rent hij weg.
Je kunt ook if-statements schrijven met een Guardian State-variabele en verschillende controles: is er een vijand in de buurt, wat is het gezondheidsniveau van de NPC, enz. Laten we nog een paar staten toevoegen:
- Luiheid - tussen patrouilles.
- Zoeken - wanneer de opgemerkte vijand verdwenen is.
- Hulp zoeken - wanneer een vijand wordt opgemerkt, maar te sterk is om alleen te vechten.
De keuze voor elk van hen is beperkt: de bewaker zal bijvoorbeeld niet op zoek gaan naar een verborgen vijand als hij een lage gezondheid heeft.
Er is tenslotte een enorme lijst met ‘als’ , Dat ' kan te omslachtig worden, dus moeten we een methode formaliseren waarmee we staten en overgangen tussen staten in gedachten kunnen houden. Om dit te doen, houden we rekening met alle staten, en onder elke staat noteren we in een lijst alle overgangen naar andere staten, samen met de voorwaarden die daarvoor nodig zijn.
Dit is een statusovergangstabel - een uitgebreide manier om FSM weer te geven. Laten we een diagram tekenen en een compleet overzicht krijgen van hoe het gedrag van NPC's verandert.
Het diagram weerspiegelt de essentie van de besluitvorming voor deze agent op basis van de huidige situatie. Bovendien toont elke pijl een overgang tussen toestanden als de voorwaarde ernaast waar is.
Bij elke update controleren we de huidige status van de agent, bekijken we de lijst met overgangen en als aan de voorwaarden voor de overgang is voldaan, accepteert deze de nieuwe staat. Elk frame controleert bijvoorbeeld of de timer van 10 seconden is verstreken, en als dat het geval is, gaat de bewaker van de status Inactief naar Patrouilleren. Op dezelfde manier controleert de aanvallende staat de gezondheid van de agent. Als deze laag is, gaat deze naar de vluchtende staat.
Dit betreft de afhandeling van overgangen tussen staten, maar hoe zit het met het gedrag dat met de staten zelf samenhangt? Wat betreft het implementeren van het daadwerkelijke gedrag voor een bepaalde staat, zijn er doorgaans twee soorten ‘hook’ waarbij we acties aan de FSM toewijzen:
- Acties die we periodiek uitvoeren voor de huidige staat.
- De acties die we ondernemen bij de overgang van de ene staat naar de andere.
Voorbeelden voor het eerste type. De patrouillestatus verplaatst de agent elk frame langs de patrouilleroute. De aanvallende staat zal elk frame proberen een aanval te initiëren of over te gaan naar een staat waarin dit mogelijk is.
Overweeg voor het tweede type de overgang: “Als de vijand zichtbaar is en de vijand te sterk is, ga dan naar de status Hulp zoeken. De agent moet kiezen waar hij hulp moet zoeken en deze informatie opslaan, zodat de status Hulp zoeken weet waar hij heen moet. Zodra er hulp is gevonden, keert de agent terug naar de aanvalsstatus. Op dit punt wil hij de bondgenoot over de dreiging vertellen, zodat de actie NotifyFriendOfThreat kan plaatsvinden.
Opnieuw kunnen we naar dit systeem kijken door de lens van de Sense/Think/Act-cyclus. Sense wordt belichaamd in de gegevens die door de transitielogica worden gebruikt. Think - overgangen beschikbaar in elke staat. En Act wordt uitgevoerd door acties die periodiek worden uitgevoerd binnen een staat of bij overgangen tussen staten.
Soms kan het voortdurend peilen naar de transitievoorwaarden kostbaar zijn. Als elke agent bijvoorbeeld elk frame complexe berekeningen uitvoert om te bepalen of hij vijanden kan zien en kan begrijpen of hij van de status Patrouilleren naar Aanvallen kan overgaan, zal dit veel CPU-tijd kosten.
Belangrijke veranderingen in de toestand van de wereld kunnen worden gezien als gebeurtenissen die zullen worden verwerkt zodra ze zich voordoen. In plaats van dat de FSM bij elk frame de overgangsvoorwaarde "Kan mijn agent de speler zien?" controleert, kan een afzonderlijk systeem worden geconfigureerd om minder vaak te controleren (bijvoorbeeld 5 keer per seconde). En het resultaat is dat Player Seen wordt uitgegeven wanneer de cheque slaagt.
Dit wordt doorgegeven aan de FSM, die nu naar de status Speler gezien-gebeurtenis moet gaan en dienovereenkomstig moet reageren. Het resulterende gedrag is hetzelfde, afgezien van een bijna onmerkbare vertraging voordat er gereageerd wordt. Maar de prestaties zijn verbeterd als gevolg van het opsplitsen van het Sense-gedeelte in een apart deel van het programma.
Hiërarchische eindige toestandsmachine
Het werken met grote FSM's is echter niet altijd handig. Als we de aanvalsstatus willen uitbreiden om MeleeAttacking en RangedAttacking te scheiden, zullen we de overgangen van alle andere staten die naar de Aanvallende staat leiden (huidig en toekomstig) moeten veranderen.
Je hebt waarschijnlijk gemerkt dat er in ons voorbeeld veel dubbele overgangen zijn. De meeste overgangen in de status Inactief zijn identiek aan overgangen in de status Patrouilleren. Het zou leuk zijn om onszelf niet te herhalen, vooral als we meer vergelijkbare staten toevoegen. Het is zinvol om Idling en Patrolling te groeperen onder het algemene label 'non-combat', waarbij er slechts één gemeenschappelijke reeks overgangen naar gevechtsstaten is. Als we dit label als een staat beschouwen, worden Idling en Patrolling substaten. Een voorbeeld van het gebruik van een aparte overgangstabel voor een nieuwe niet-gevechtssubstaat:
Belangrijkste staten:
Buiten gevechtsstatus:
En in diagramvorm:
Het is hetzelfde systeem, maar met een nieuwe niet-gevechtsstatus die Idling en Patrolling omvat. Wanneer elke staat een FSM met substaten bevat (en deze substaten op hun beurt hun eigen FSM's bevatten - enzovoort, zo lang als je nodig hebt), krijgen we een hiërarchische eindige-toestandsmachine of HFSM (hiërarchische eindige-toestandsmachine). Door de niet-gevechtsstatus te groeperen, hebben we een aantal overbodige overgangen weggelaten. Hetzelfde kunnen we doen voor nieuwe staten met gemeenschappelijke transities. Als we in de toekomst bijvoorbeeld de aanvallende staat uitbreiden naar de meleeattacking- en raketaanvalstaten, zullen dit substaten zijn die van elkaar overgaan op basis van de afstand tot de vijand en de beschikbaarheid van munitie. Als gevolg hiervan kunnen complexe gedragingen en deelgedragingen worden weergegeven met een minimum aan dubbele overgangen.
Gedragsboom
Met HFSM worden op eenvoudige wijze complexe combinaties van gedrag gecreëerd. Er is echter een klein probleem dat besluitvorming in de vorm van overgangsregels nauw verband houdt met de huidige stand van zaken. En in veel games is dit precies wat nodig is. En een zorgvuldig gebruik van de staatshiërarchie kan het aantal transitieherhalingen verminderen. Maar soms heb je regels nodig die werken, ongeacht in welke staat je je bevindt, of die in vrijwel elke staat van toepassing zijn. Als de gezondheid van een agent bijvoorbeeld naar 25% daalt, wil je dat hij wegrent, ongeacht of hij aan het vechten was, inactief was of aan het praten was. Je moet deze voorwaarde aan elke staat toevoegen. En als uw ontwerper later de lage gezondheidsdrempel wil wijzigen van 25% naar 10%, dan zal dit opnieuw moeten gebeuren.
Idealiter vereist deze situatie een systeem waarin beslissingen over ‘in welke staat we moeten zijn’ buiten de staten zelf liggen, om veranderingen slechts op één plek door te voeren en de overgangsvoorwaarden niet aan te raken. Hier verschijnen gedragsbomen.
Er zijn verschillende manieren om ze te implementeren, maar de essentie is voor iedereen ongeveer hetzelfde en lijkt op een beslissingsboom: het algoritme begint met een ‘root’-knooppunt en de boom bevat knooppunten die beslissingen of acties vertegenwoordigen. Er zijn echter een paar belangrijke verschillen:
- Knooppunten retourneren nu een van de drie waarden: Geslaagd (als de taak is voltooid), Mislukt (als deze niet kan worden gestart) of Actief (als deze nog steeds actief is en er geen eindresultaat is).
- Er zijn geen beslissingsknooppunten meer om tussen twee alternatieven te kiezen. In plaats daarvan zijn het Decorator-knooppunten, die één onderliggend knooppunt hebben. Als ze slagen, voeren ze hun enige onderliggende knooppunt uit.
- Knooppunten die acties uitvoeren retourneren een Running-waarde om de acties weer te geven die worden uitgevoerd.
Deze kleine set knooppunten kan worden gecombineerd om een groot aantal complexe gedragingen te creëren. Laten we ons de HFSM-bewaker uit het vorige voorbeeld voorstellen als een gedragsboom:
Met deze structuur zou er geen duidelijke overgang moeten zijn van inactieve/patrouillerende staten naar aanvallende of andere staten. Als een vijand zichtbaar is en de gezondheid van het personage laag is, stopt de uitvoering bij het vluchtknooppunt, ongeacht welk knooppunt het eerder uitvoerde: patrouilleren, stationair draaien, aanvallen of een ander knooppunt.
Gedragsbomen zijn complex: er zijn veel manieren om ze samen te stellen, en het vinden van de juiste combinatie van decorateurs en samengestelde knooppunten kan een uitdaging zijn. Er zijn ook vragen over hoe vaak we de boom moeten controleren: willen we elk onderdeel ervan doornemen of alleen als een van de omstandigheden is veranderd? Hoe slaan we de status met betrekking tot knooppunten op - hoe weten we wanneer we 10 seconden inactief zijn geweest, of hoe weten we welke knooppunten de vorige keer werden uitgevoerd, zodat we de reeks correct kunnen verwerken?
Daarom zijn er veel implementaties. Sommige systemen hebben bijvoorbeeld decorateurknooppunten vervangen door inline decorateurs. Ze evalueren de boom opnieuw wanneer de omstandigheden van de decorateur veranderen, helpen bij het verbinden van knooppunten en zorgen voor periodieke updates.
Utility-gebaseerd systeem
Sommige games hebben veel verschillende mechanismen. Het is wenselijk dat ze alle voordelen krijgen van eenvoudige en algemene transitieregels, maar niet noodzakelijkerwijs in de vorm van een volledige gedragsboom. In plaats van een duidelijke reeks keuzes of een boom met mogelijke acties te hebben, is het gemakkelijker om alle acties te onderzoeken en de meest geschikte op dat moment te kiezen.
Het op Utility gebaseerde systeem helpt hierbij. Dit is een systeem waarbij de agent verschillende acties uitvoert en kiest welke hij wil uitvoeren op basis van het relatieve nut van elke actie. Waar nut een willekeurige maatstaf is voor hoe belangrijk of wenselijk het is dat de agent deze actie uitvoert.
Het berekende nut van een actie op basis van de huidige status en omgeving. De agent kan op elk moment de meest geschikte andere status controleren en selecteren. Dit is vergelijkbaar met FSM, behalve waar transities worden bepaald door een schatting voor elke potentiële toestand, inclusief de huidige. Houd er rekening mee dat we de nuttigste actie kiezen om verder te gaan (of te blijven als we deze al hebben voltooid). Voor meer variatie kan dit een evenwichtige maar willekeurige selectie uit een kleine lijst zijn.
Het systeem kent een willekeurig bereik van nutswaarden toe, bijvoorbeeld van 0 (volledig ongewenst) tot 100 (volledig wenselijk). Elke actie heeft een aantal parameters die van invloed zijn op de berekening van deze waarde. Terugkerend naar ons voorbeeld van een voogd:
Overgangen tussen acties zijn dubbelzinnig: elke staat kan elke andere volgen. Actieprioriteiten zijn te vinden in de geretourneerde nutswaarden. Als een vijand zichtbaar is, en die vijand sterk is, en de gezondheid van het personage laag is, zullen zowel Fleeing als FindingHelp hoge waarden opleveren die niet nul zijn. In dit geval zal FindingHelp altijd hoger zijn. Op dezelfde manier leveren niet-gevechtsactiviteiten nooit meer dan 50 op, dus zullen ze altijd lager zijn dan gevechtsactiviteiten. U moet hiermee rekening houden bij het maken van acties en het berekenen van hun nut.
In ons voorbeeld retourneren de acties een vaste constante waarde of een van twee vaste waarden. Een realistischer systeem zou een schatting opleveren op basis van een continu bereik van waarden. De vluchtactie retourneert bijvoorbeeld hogere nutswaarden als de gezondheid van de agent laag is, en de aanvalsactie retourneert lagere nutswaarden als de vijand te sterk is. Hierdoor heeft de vluchtactie voorrang op de aanval in elke situatie waarin de agent het gevoel heeft dat hij niet genoeg gezondheid heeft om de vijand te verslaan. Hierdoor kunnen acties worden geprioriteerd op basis van een willekeurig aantal criteria, waardoor deze aanpak flexibeler en variabeler wordt dan een gedragsboom of FSM.
Elke actie heeft veel voorwaarden voor programmaberekening. Ze kunnen worden geschreven in scripttaal of als een reeks wiskundige formules. De Sims, die de dagelijkse routine van een personage simuleert, voegt een extra rekenlaag toe: de agent ontvangt een reeks 'motivaties' die de nutsbeoordelingen beïnvloeden. Als een personage honger heeft, zal hij of zij in de loop van de tijd zelfs nog hongeriger worden, en de gebruikswaarde van de EatFood-actie zal toenemen totdat het personage deze uitvoert, waardoor het hongerniveau afneemt en de EatFood-waarde teruggaat naar nul.
Het idee om acties te selecteren op basis van een beoordelingssysteem is vrij eenvoudig, dus een op nutsvoorzieningen gebaseerd systeem kan worden gebruikt als onderdeel van AI-besluitvormingsprocessen, in plaats van als een volledige vervanging ervan. De beslissingsboom kan vragen om een nutsbeoordeling van twee onderliggende knooppunten en de hoogste selecteren. Op dezelfde manier kan een gedragsboom een samengesteld hulpprogramma-knooppunt hebben om het nut van acties te evalueren en te beslissen welk kind moet worden uitgevoerd.
Beweging en navigatie
In de vorige voorbeelden hadden we een platform dat we naar links of rechts konden bewegen, en een bewaker die patrouilleerde of aanviel. Maar hoe gaan we precies om met de verplaatsingen van agenten gedurende een bepaalde periode? Hoe bepalen we de snelheid, hoe vermijden we obstakels en hoe plannen we een route als het bereiken van een bestemming moeilijker is dan alleen maar in een rechte lijn bewegen? Laten we hier eens naar kijken.
Управление
In de beginfase gaan we ervan uit dat elke agent een snelheidswaarde heeft, die aangeeft hoe snel hij beweegt en in welke richting. Het kan worden gemeten in meters per seconde, kilometer per uur, pixels per seconde, enz. Als we ons de Sense/Think/Act-lus herinneren, kunnen we ons voorstellen dat het Think-gedeelte een snelheid selecteert, en het Act-gedeelte die snelheid op de agent toepast. Meestal hebben games een natuurkundig systeem dat deze taak voor je uitvoert, waarbij de snelheidswaarde van elk object wordt geleerd en wordt aangepast. Daarom kunt u de AI met één taak overlaten: beslissen welke snelheid de agent moet hebben. Als je weet waar de agent moet zijn, moet je hem met een bepaalde snelheid in de goede richting bewegen. Een heel triviale vergelijking:
gewenste_reis = bestemmingspositie – agent_positie
Stel je een 2D-wereld voor. De agent bevindt zich op punt (-2,-2), de bestemming ligt ergens in het noordoosten op punt (30, 20) en het vereiste pad voor de agent om daar te komen is (32, 22). Laten we zeggen dat deze posities worden gemeten in meters - als we aannemen dat de snelheid van de agent 5 meter per seconde is, dan zullen we onze verplaatsingsvector schalen en een snelheid van ongeveer (4.12, 2.83) krijgen. Met deze parameters zou de agent binnen bijna 8 seconden op zijn bestemming aankomen.
U kunt de waarden op elk moment opnieuw berekenen. Als de agent zich halverwege het doel zou bevinden, zou de beweging de helft van de lengte zijn, maar aangezien de maximale snelheid van de agent 5 m/s is (we hebben dit hierboven besloten), zal de snelheid hetzelfde zijn. Dit werkt ook voor bewegende doelen, waardoor de agent kleine wijzigingen kan aanbrengen terwijl ze bewegen.
Maar we willen meer variatie, bijvoorbeeld door de snelheid langzaam te verhogen om een personage te simuleren dat van staand naar rennen gaat. Hetzelfde kan aan het einde worden gedaan voordat u stopt. Deze kenmerken staan bekend als stuurgedrag en hebben elk een specifieke naam: zoeken, vluchten, aankomst, enz. Het idee is dat versnellingskrachten kunnen worden toegepast op de snelheid van de agent, gebaseerd op het vergelijken van de positie en de huidige snelheid van de agent met de bestemming in het gebied. om verschillende methoden te gebruiken om naar het doel te gaan.
Elk gedrag heeft een iets ander doel. Zoeken en aankomen zijn manieren om een agent naar een bestemming te verplaatsen. Obstakelvermijding en scheiding passen de beweging van de agent aan om obstakels op weg naar het doel te vermijden. Afstemming en cohesie zorgen ervoor dat agenten samen in beweging blijven. Een willekeurig aantal verschillende stuurgedragingen kan worden opgeteld om één enkele padvector te produceren, waarbij alle factoren in aanmerking worden genomen. Een agent die de gedragingen Aankomst, Scheiding en Obstakel vermijden gebruikt om uit de buurt van muren en andere agenten te blijven. Deze aanpak werkt goed op open locaties zonder onnodige details.
In moeilijkere omstandigheden werkt de toevoeging van verschillende gedragingen slechter. Een agent kan bijvoorbeeld vast komen te zitten in een muur als gevolg van een conflict tussen aankomst en obstakelvermijding. Daarom moet u opties overwegen die complexer zijn dan alleen het optellen van alle waarden. De manier is als volgt: in plaats van de resultaten van elk gedrag bij elkaar op te tellen, kunt u bewegingen in verschillende richtingen overwegen en de beste optie kiezen.
In een complexe omgeving met doodlopende wegen en keuzes over welke kant we op moeten, hebben we echter iets nog geavanceerders nodig.
Een manier vinden
Het stuurgedrag is ideaal voor eenvoudige bewegingen in een open gebied (voetbalveld of arena) waar het reizen van A naar B een recht pad is met slechts kleine omwegen rond obstakels. Voor complexe routes hebben we pathfinding nodig, een manier om de wereld te verkennen en een route er doorheen te bepalen.
Het eenvoudigste is om op elk vakje naast de agent een raster aan te brengen en te beoordelen welke van hen mag bewegen. Als een van deze een bestemming is, volg dan de route van elk plein naar het vorige totdat je het begin bereikt. Dit is de route. Herhaal anders het proces met andere vakjes in de buurt totdat je je bestemming hebt gevonden of totdat je geen vakjes meer hebt (wat betekent dat er geen route mogelijk is). Dit is wat formeel bekend staat als Breadth-First Search of BFS (breedte-eerst zoekalgoritme). Bij elke stap kijkt hij in alle richtingen (vandaar breedte, "breedte"). De zoekruimte is als een golffront dat beweegt totdat het de gewenste locatie bereikt - de zoekruimte breidt zich bij elke stap uit totdat het eindpunt is opgenomen, waarna deze terug te voeren is naar het begin.
Als resultaat ontvangt u een lijst met vierkanten waarlangs de gewenste route is samengesteld. Dit is het pad (vandaar pathfinding) - een lijst met plaatsen die de agent zal bezoeken terwijl hij de bestemming volgt.
Gegeven dat we de positie van elk vierkant ter wereld kennen, kunnen we stuurgedrag gebruiken om langs het pad te bewegen - van knooppunt 1 naar knooppunt 2, vervolgens van knooppunt 2 naar knooppunt 3, enzovoort. De eenvoudigste optie is om naar het midden van het volgende vierkant te gaan, maar een nog betere optie is om in het midden van de rand tussen het huidige vierkant en het volgende te stoppen. Hierdoor kan de agent scherpe bochten afsnijden.
Het BFS-algoritme heeft ook nadelen: het onderzoekt evenveel vierkanten in de “verkeerde” richting als in de “goede” richting. Dit is waar een complexer algoritme genaamd A* (A-ster) in het spel komt. Het werkt op dezelfde manier, maar in plaats van blind aangrenzende vierkanten te onderzoeken (dan buren van buren, dan buren van buren van buren, enzovoort), verzamelt het de knooppunten in een lijst en sorteert ze zo dat het volgende onderzochte knooppunt altijd het één die naar de kortste route leidt. Knooppunten worden gesorteerd op basis van een heuristiek die rekening houdt met twee dingen: de ‘kosten’ van een hypothetische route naar het gewenste vierkant (inclusief eventuele reiskosten) en een schatting van hoe ver dat vierkant van de bestemming verwijderd is (wat de zoekopdracht in het gewenste vierkant vertekent). juiste richting).
Dit voorbeeld laat zien dat de agent één vakje tegelijk verkent, waarbij hij telkens het aangrenzende vakje kiest dat het meest veelbelovend is. Het resulterende pad is hetzelfde als bij BFS, maar er is tijdens het proces met minder vierkanten rekening gehouden - wat een grote impact heeft op de spelprestaties.
Beweging zonder raster
Maar de meeste games zijn niet in een raster ingedeeld, en dat is vaak onmogelijk zonder dat dit ten koste gaat van het realisme. Er zijn compromissen nodig. Hoe groot moeten de vierkanten zijn? Te groot en ze zullen kleine gangen of bochten niet correct kunnen weergeven, te klein en er zullen te veel vierkanten zijn om naar te zoeken, wat uiteindelijk veel tijd zal kosten.
Het eerste dat we moeten begrijpen is dat een mesh ons een grafiek van verbonden knooppunten geeft. De A*- en BFS-algoritmen werken feitelijk op grafieken en geven helemaal niets om onze mesh. We zouden knooppunten overal in de spelwereld kunnen plaatsen: zolang er een verbinding is tussen twee verbonden knooppunten, maar ook tussen het begin- en eindpunt en ten minste één van de knooppunten, zal het algoritme net zo goed werken als voorheen. Dit wordt vaak een waypoint-systeem genoemd, omdat elk knooppunt een belangrijke positie in de wereld vertegenwoordigt die deel kan uitmaken van een willekeurig aantal hypothetische paden.
Voorbeeld 1: een knoop in elk vierkant. De zoekopdracht begint vanaf het knooppunt waar de agent zich bevindt en eindigt bij het knooppunt van het gewenste vierkant.
Voorbeeld 2: Een kleinere set knooppunten (waypoints). De zoekopdracht begint op het plein van de agent, gaat door het vereiste aantal knooppunten en gaat vervolgens verder naar de bestemming.
Dit is een volledig flexibel en krachtig systeem. Maar er is enige zorg nodig bij het beslissen waar en hoe een waypoint moet worden geplaatst, anders kunnen agenten het dichtstbijzijnde punt eenvoudigweg niet zien en kunnen ze het pad niet starten. Het zou eenvoudiger zijn als we automatisch waypoints zouden kunnen plaatsen op basis van de geometrie van de wereld.
Dit is waar het navigatiegaas of navmesh (navigatiegaas) verschijnt. Dit is meestal een 2D-netwerk van driehoeken dat over de geometrie van de wereld heen wordt gelegd - waar de agent ook mag lopen. Elk van de driehoeken in de mesh wordt een knooppunt in de grafiek en heeft maximaal drie aangrenzende driehoeken die aangrenzende knooppunten in de grafiek worden.
Deze afbeelding is een voorbeeld van de Unity-engine: deze analyseerde de geometrie in de wereld en creëerde een navmesh (in de schermafbeelding in lichtblauw). Elke polygoon in een navmesh is een gebied waar een agent kan staan of van de ene polygoon naar de andere kan bewegen. In dit voorbeeld zijn de polygonen kleiner dan de verdiepingen waarop ze zich bevinden - dit wordt gedaan om rekening te houden met de grootte van de agent, die verder reikt dan zijn nominale positie.
We kunnen een route door dit gaas zoeken, opnieuw met behulp van het A*-algoritme. Dit geeft ons een bijna perfecte route in de wereld, die rekening houdt met alle geometrie en geen onnodige knooppunten en het creëren van waypoints vereist.
Pathfinding is een te breed onderwerp waarvoor één sectie van een artikel niet voldoende is. Als je het in meer detail wilt bestuderen, dan zal dit helpen .
planning
Met Pathfinding hebben we geleerd dat het soms niet genoeg is om alleen maar een richting te kiezen en verder te gaan; we moeten een route kiezen en een paar bochten maken om onze gewenste bestemming te bereiken. We kunnen dit idee generaliseren: het bereiken van een doel is niet alleen de volgende stap, maar een hele reeks waarbij je soms meerdere stappen vooruit moet kijken om erachter te komen wat de eerste zou moeten zijn. Dit heet plannen. Pathfinding kan worden gezien als een van de vele uitbreidingen van planning. In termen van onze Sense/Think/Act-cyclus plant het Think-deel hier meerdere Act-delen voor de toekomst.
Laten we eens kijken naar het voorbeeld van het bordspel Magic: The Gathering. We gaan eerst met de volgende set kaarten in onze handen:
- Moeras - Geeft 1 zwarte mana (landkaart).
- Bos - geeft 1 groene mana (landkaart).
- Voortvluchtige tovenaar - Vereist 1 blauwe mana om op te roepen.
- Elvish Mystic - Vereist 1 groene mana om op te roepen.
We negeren de overige drie kaarten om het gemakkelijker te maken. Volgens de regels mag een speler per beurt 1 landkaart spelen. Hij kan op deze kaart ‘tikken’ om er mana uit te halen en vervolgens spreuken uitspreken (inclusief het oproepen van een wezen) afhankelijk van de hoeveelheid mana. In deze situatie weet de menselijke speler Forest te spelen, op 1 groene mana te tikken en vervolgens Elvish Mystic op te roepen. Maar hoe kan de spel-AI dit uitzoeken?
Gemakkelijk plannen
De triviale benadering is om elke actie achtereenvolgens uit te proberen totdat er geen geschikte meer over zijn. Door naar de kaarten te kijken, ziet de AI wat Swamp kan spelen. En hij speelt het. Zijn er nog andere acties over deze beurt? Het kan Elvish Mystic of Fugitive Wizard niet oproepen, omdat ze respectievelijk groene en blauwe mana nodig hebben om ze op te roepen, terwijl Swamp alleen zwarte mana levert. En hij kan Forest niet meer spelen, omdat hij al Swamp heeft gespeeld. De spel-AI volgde dus de regels, maar deed het slecht. Kan verbeterd worden.
Planning kan een lijst met acties vinden die het spel in de gewenste staat brengen. Net zoals elk vakje op een pad buren had (bij padvinden), heeft ook elke actie in een plan buren of opvolgers. We kunnen naar deze acties en daaropvolgende acties zoeken totdat we de gewenste staat bereiken.
In ons voorbeeld is het gewenste resultaat ‘roep indien mogelijk een wezen op’. Aan het begin van de beurt zien we slechts twee mogelijke acties die volgens de spelregels zijn toegestaan:
1. Speel Moeras (resultaat: Moeras in het spel)
2. Speel Bos (resultaat: Bos in het spel)
Elke genomen actie kan leiden tot verdere acties en andere acties sluiten, wederom afhankelijk van de spelregels. Stel je voor dat we Swamp speelden - dit zal Swamp verwijderen als de volgende stap (we hebben het al gespeeld), en dit zal ook Forest verwijderen (omdat je volgens de regels één landkaart per beurt kunt spelen). Hierna voegt de AI het krijgen van 1 zwarte mana toe als volgende stap omdat er geen andere opties zijn. Als hij doorgaat en Tap the Swamp kiest, ontvangt hij 1 eenheid zwarte mana en kan hij daar niets mee doen.
1. Speel Moeras (resultaat: Moeras in het spel)
1.1 “Tap” Moeras (resultaat: Moeras “getapt”, +1 eenheid zwarte mana)
Geen acties beschikbaar - EINDE
2. Speel Bos (resultaat: Bos in het spel)
De lijst met acties was kort, we liepen op een dood spoor. We herhalen het proces voor de volgende stap. We spelen Forest, openen de actie "krijg 1 groene mana", die op zijn beurt de derde actie opent: roep Elvish Mystic op.
1. Speel Moeras (resultaat: Moeras in het spel)
1.1 “Tap” Moeras (resultaat: Moeras “getapt”, +1 eenheid zwarte mana)
Geen acties beschikbaar - EINDE
2. Speel Bos (resultaat: Bos in het spel)
2.1 “Tik op” bos (resultaat: bos wordt “getapt”, +1 eenheid groene mana)
2.1.1 Roep Elvish Mystic op (resultaat: Elvish Mystic in het spel, -1 groene mana)
Geen acties beschikbaar - EINDE
Ten slotte hebben we alle mogelijke acties onderzocht en een plan gevonden dat een wezen oproept.
Dit is een zeer vereenvoudigd voorbeeld. Het is raadzaam om het best mogelijke plan te kiezen, in plaats van zomaar een plan dat aan bepaalde criteria voldoet. Het is over het algemeen mogelijk om potentiële plannen te evalueren op basis van de uitkomst of het algemene voordeel van de implementatie ervan. Je kunt 1 punt scoren voor het spelen van een landkaart en 3 punten voor het oproepen van een wezen. Het spelen van Swamp zou een 1-puntsplan zijn. En het spelen van Bos → Tap the Forest → roep Elvish Mystic op levert onmiddellijk 4 punten op.
Dit is hoe planning werkt in Magic: The Gathering, maar dezelfde logica is van toepassing in andere situaties. Bijvoorbeeld het verplaatsen van een pion om ruimte te maken voor de loper om te schaken. Of zoek dekking achter een muur om zo veilig in XCOM te fotograferen. Over het algemeen begrijp je het idee.
Verbeterde planning
Soms zijn er te veel potentiële acties om alle mogelijke opties te overwegen. Terugkerend naar het voorbeeld met Magic: The Gathering: laten we zeggen dat er in het spel en in je hand verschillende land- en wezenkaarten zijn - het aantal mogelijke combinaties van zetten kan in de tientallen lopen. Er zijn verschillende oplossingen voor het probleem.
De eerste methode is achterwaarts ketenen. In plaats van alle combinaties uit te proberen, kun je beter beginnen met het eindresultaat en proberen een directe route te vinden. In plaats van van de wortel van de boom naar een specifiek blad te gaan, gaan we in de tegenovergestelde richting: van het blad naar de wortel. Deze methode is eenvoudiger en sneller.
Als de vijand 1 gezondheid heeft, kun je het plan '1 of meer schade toebrengen' vinden. Om dit te bereiken moet aan een aantal voorwaarden worden voldaan:
1. Schade kan worden veroorzaakt door een spreuk - deze moet in de hand zijn.
2. Om een spreuk uit te spreken heb je mana nodig.
3. Om mana te krijgen, moet je een landkaart spelen.
4. Om een landkaart te kunnen spelen, moet je deze in je hand hebben.
Een andere manier is de best-eerst-zoekopdracht. In plaats van alle paden uit te proberen, kiezen we de meest geschikte. Meestal levert deze methode het optimale plan op zonder onnodige zoekkosten. A* is een vorm van best first search: door vanaf het begin de meest veelbelovende routes te onderzoeken, kan het programma al het beste pad vinden zonder andere opties te hoeven controleren.
Een interessante en steeds populairdere best-first-zoekoptie is Monte Carlo Tree Search. In plaats van te raden welke plannen beter zijn dan andere bij het kiezen van elke volgende actie, kiest het algoritme bij elke stap willekeurige opvolgers totdat het einde wordt bereikt (wanneer het plan resulteerde in overwinning of nederlaag). Het eindresultaat wordt vervolgens gebruikt om het gewicht van eerdere opties te verhogen of te verlagen. Door dit proces meerdere keren achter elkaar te herhalen, geeft het algoritme een goede inschatting van wat de beste volgende zet is, ook als de situatie verandert (als de vijand actie onderneemt om de speler te hinderen).
Geen enkel verhaal over planning in games zou compleet zijn zonder Goal-Oriented Action Planning of GOAP (Doelgerichte Actieplanning). Dit is een veelgebruikte en besproken methode, maar afgezien van enkele onderscheidende details is het in wezen de achterwaartse ketenmethode waar we het eerder over hadden. Als het doel was om "de speler te vernietigen" en de speler bevindt zich achter dekking, zou het plan kunnen zijn: vernietigen met een granaat → pakken → gooien.
Er zijn meestal meerdere doelen, elk met zijn eigen prioriteit. Als het doel met de hoogste prioriteit niet kan worden voltooid (geen enkele combinatie van acties creëert een ‘kill the player’-plan omdat de speler niet zichtbaar is), zal de AI terugvallen op doelstellingen met een lagere prioriteit.
Opleiding en aanpassing
We hebben al gezegd dat game-AI meestal geen gebruik maakt van machine learning, omdat het niet geschikt is om agenten in realtime te beheren. Maar dit betekent niet dat je niets uit deze omgeving kunt lenen. We willen een tegenstander in een shooter waar we iets van kunnen leren. Ontdek bijvoorbeeld de beste posities op de kaart. Of een tegenstander in een vechtgame die de vaak gebruikte combo-bewegingen van de speler blokkeert en hem motiveert om andere te gebruiken. Machine learning kan in dergelijke situaties dus behoorlijk nuttig zijn.
Statistieken en waarschijnlijkheden
Voordat we ingaan op complexe voorbeelden, laten we eens kijken hoe ver we kunnen gaan door een paar eenvoudige metingen uit te voeren en deze te gebruiken om beslissingen te nemen. Bijvoorbeeld realtime strategie: hoe bepalen we of een speler in de eerste paar minuten van het spel een aanval kan lanceren en welke verdediging we hiertegen moeten voorbereiden? We kunnen de ervaringen uit het verleden van een speler bestuderen om te begrijpen wat toekomstige reacties kunnen zijn. Om te beginnen beschikken we niet over zulke ruwe gegevens, maar we kunnen deze verzamelen: elke keer dat de AI tegen een mens speelt, kan hij het tijdstip van de eerste aanval registreren. Na een paar sessies krijgen we een gemiddelde van de tijd die de speler nodig heeft om in de toekomst aan te vallen.
Er is ook een probleem met de gemiddelde waarden: als een speler 20 keer haastte en 20 keer langzaam speelde, dan zullen de vereiste waarden ergens in het midden liggen, en dit levert ons niets nuttigs op. Eén oplossing is om de invoergegevens te beperken; er kan rekening worden gehouden met de laatste 20 stuks.
Een soortgelijke aanpak wordt gebruikt bij het inschatten van de waarschijnlijkheid van bepaalde acties door aan te nemen dat de voorkeuren van de speler uit het verleden in de toekomst hetzelfde zullen zijn. Als een speler ons vijf keer aanvalt met vuurbal, twee keer met bliksem en één keer met melee, is het duidelijk dat hij de voorkeur geeft aan vuurbal. Laten we extrapoleren en de waarschijnlijkheid bekijken van het gebruik van verschillende wapens: vuurbal=62,5%, bliksem=25% en melee=12,5%. Onze game-AI moet zich voorbereiden om zichzelf tegen brand te beschermen.
Een andere interessante methode is om met de Naive Bayes Classifier grote hoeveelheden inputdata te bestuderen en de situatie zo te classificeren dat de AI op de gewenste manier reageert. Bayesiaanse classificaties zijn vooral bekend vanwege hun gebruik in e-mailspamfilters. Daar onderzoeken ze de woorden, vergelijken ze met waar die woorden eerder zijn verschenen (in spam of niet) en trekken ze conclusies over inkomende e-mails. We kunnen hetzelfde doen, zelfs met minder input. Op basis van alle nuttige informatie die de AI ziet (zoals welke vijandelijke eenheden zijn gemaakt, of welke spreuken ze gebruiken, of welke technologieën ze hebben onderzocht) en het eindresultaat (oorlog of vrede, haast of verdediging, etc.) - we kiezen het gewenste AI-gedrag.
Al deze trainingsmethoden zijn voldoende, maar het is raadzaam om ze te gebruiken op basis van testgegevens. De AI zal zich leren aanpassen aan de verschillende strategieën die uw playtesters hebben gebruikt. AI die zich na release aanpast aan de speler, kan te voorspelbaar of te moeilijk worden om te verslaan.
Op waarde gebaseerde aanpassing
Gezien de inhoud van onze spelwereld en de regels kunnen we de set waarden die de besluitvorming beïnvloeden veranderen, in plaats van simpelweg de invoergegevens te gebruiken. Wij doen dit:
- Laat de AI gegevens verzamelen over de toestand van de wereld en belangrijke gebeurtenissen tijdens het spel (zoals hierboven).
- Laten we op basis van deze gegevens een paar belangrijke waarden wijzigen.
- We implementeren onze beslissingen op basis van de verwerking of evaluatie van deze waarden.
Een agent heeft bijvoorbeeld verschillende kamers waaruit hij kan kiezen op een first-person shooter-kaart. Elke kamer heeft zijn eigen waarde, die bepaalt hoe wenselijk het is om te bezoeken. De AI kiest willekeurig naar welke kamer hij gaat op basis van de waarde. De agent onthoudt vervolgens in welke kamer hij is vermoord en verlaagt de waarde ervan (de kans dat hij daar terugkeert). Hetzelfde geldt voor de omgekeerde situatie: als de agent veel tegenstanders vernietigt, neemt de waarde van de kamer toe.
Markov-model
Wat als we de verzamelde gegevens zouden gebruiken om voorspellingen te doen? Als we elke kamer onthouden waarin we een speler gedurende een bepaalde periode zien, kunnen we voorspellen naar welke kamer de speler mogelijk gaat. Door de bewegingen van de speler in kamers (waarden) te volgen en vast te leggen, kunnen we deze voorspellen.
Laten we drie kamers nemen: rood, groen en blauw. En ook de observaties die we opnamen tijdens het bekijken van de spelsessie:
Het aantal observaties in elke kamer is vrijwel gelijk - we weten nog steeds niet waar we een goede plek voor een hinderlaag kunnen vinden. Het verzamelen van statistieken wordt ook bemoeilijkt door het respawnen van spelers, die gelijkmatig over de kaart verschijnen. Maar de gegevens over de volgende kamer die ze binnenkomen nadat ze op de kaart zijn verschenen, zijn al nuttig.
Het is duidelijk dat de groene kamer bij de spelers past - de meeste mensen gaan van de rode kamer ernaartoe, van wie 50% daar verder blijft. De blauwe kamer daarentegen is niet populair; bijna niemand gaat er naartoe, en als ze dat wel doen, blijven ze niet lang.
Maar de gegevens vertellen ons iets belangrijkers: wanneer een speler zich in een blauwe kamer bevindt, zal de volgende kamer waarin we hem zien rood zijn, en niet groen. Hoewel de groene kamer populairder is dan de rode kamer, verandert de situatie als de speler zich in de blauwe kamer bevindt. De volgende staat (d.w.z. de kamer waar de speler naartoe gaat) hangt af van de vorige staat (d.w.z. de kamer waarin de speler zich momenteel bevindt). Omdat we afhankelijkheden onderzoeken, zullen we nauwkeurigere voorspellingen doen dan wanneer we de waarnemingen eenvoudigweg onafhankelijk zouden tellen.
Het voorspellen van een toekomstige toestand op basis van gegevens uit een vroegere toestand wordt een Markov-model genoemd, en dergelijke voorbeelden (met kamers) worden Markov-ketens genoemd. Omdat de patronen de waarschijnlijkheid van veranderingen tussen opeenvolgende toestanden vertegenwoordigen, worden ze visueel weergegeven als FSM's met een waarschijnlijkheid rond elke overgang. Voorheen gebruikten we FSM om de gedragstoestand weer te geven waarin een agent zich bevond, maar dit concept strekt zich uit tot elke toestand, of deze nu met de agent wordt geassocieerd of niet. In dit geval vertegenwoordigen de staten de ruimte waarin de agent zich bevindt:
Dit is een eenvoudige manier om de relatieve waarschijnlijkheid van toestandsveranderingen weer te geven, waardoor de AI enig vermogen krijgt om de volgende toestand te voorspellen. Je kunt een aantal stappen vooruit anticiperen.
Als een speler zich in de groene kamer bevindt, is er een kans van 50% dat hij daar de volgende keer dat hij wordt waargenomen, zal blijven. Maar hoe groot is de kans dat hij er daarna nog zal zijn? Niet alleen is er een kans dat de speler na twee observaties in de groene kamer is gebleven, maar ook is er een kans dat hij vertrok en terugkeerde. Hier is de nieuwe tabel, rekening houdend met de nieuwe gegevens:
Het laat zien dat de kans om de speler na twee observaties in de groene kamer te zien gelijk zal zijn aan 51% - 21% dat hij uit de rode kamer komt, 5% daarvan dat de speler de blauwe kamer ertussen zal bezoeken, en 25% dat de speler de groene kamer niet zal verlaten.
De tabel is eenvoudigweg een visueel hulpmiddel; de procedure vereist alleen het vermenigvuldigen van de kansen bij elke stap. Dit betekent dat je ver in de toekomst kunt kijken met één kanttekening: we gaan ervan uit dat de kans om een kamer te betreden geheel afhankelijk is van de huidige kamer. Dit wordt de Markov-eigenschap genoemd: de toekomstige toestand hangt alleen af van het heden. Maar dit is niet honderd procent nauwkeurig. Spelers kunnen beslissingen veranderen afhankelijk van andere factoren: gezondheidsniveau of hoeveelheid munitie. Omdat we deze waarden niet registreren, zullen onze voorspellingen minder nauwkeurig zijn.
N-gram
Hoe zit het met het voorbeeld van een vechtspel en het voorspellen van de combo-bewegingen van de speler? Hetzelfde! Maar in plaats van één toestand of gebeurtenis zullen we de volledige reeksen onderzoeken die deel uitmaken van een combo-aanval.
Eén manier om dit te doen is door elke invoer (zoals Kick, Punch of Block) in een buffer op te slaan en de gehele buffer als een gebeurtenis te schrijven. Dus de speler drukt herhaaldelijk op Kick, Kick, Punch om de SuperDeathFist-aanval te gebruiken, het AI-systeem slaat alle invoer op in een buffer en onthoudt de laatste drie die bij elke stap zijn gebruikt.
(De vetgedrukte regels zijn wanneer de speler de SuperDeathFist-aanval lanceert.)
De AI ziet alle opties wanneer de speler Kick selecteert, gevolgd door nog een Kick, en merkt dan dat de volgende invoer altijd Punch is. Hierdoor kan de agent de combo-beweging van SuperDeathFist voorspellen en deze indien mogelijk blokkeren.
Deze reeksen gebeurtenissen worden N-grammen genoemd, waarbij N het aantal opgeslagen elementen is. In het vorige voorbeeld was het een 3-gram (trigram), wat betekent: de eerste twee invoeren worden gebruikt om de derde te voorspellen. Dienovereenkomstig voorspellen de eerste vier inzendingen in een 5-gram de vijfde enzovoort.
De ontwerper moet de grootte van N-grammen zorgvuldig kiezen. Een kleinere N vereist minder geheugen, maar slaat ook minder geschiedenis op. Een 2 gram (bigram) neemt bijvoorbeeld Kick, Kick of Kick, Punch op, maar kan Kick, Kick, Punch niet opslaan, dus de AI reageert niet op de SuperDeathFist-combo.
Aan de andere kant vereisen grotere aantallen meer geheugen en zal de AI lastiger te trainen zijn omdat er veel meer opties mogelijk zijn. Als je drie mogelijke inputs had: Kick, Punch of Block, en we gebruikten een 10-gram, dan zouden dat ongeveer 60 verschillende opties zijn.
Het bigrammodel is een eenvoudige Markov-keten: elk paar uit het verleden en de huidige toestand is een bigram, en je kunt de tweede toestand voorspellen op basis van de eerste. De N-grammen van 3 gram en groter kunnen ook worden gezien als Markov-ketens, waarbij alle elementen (behalve de laatste in het N-gram) samen de eerste toestand vormen en het laatste element de tweede. Het vechtspelvoorbeeld laat de kans zien op de overgang van de Kick and Kick-status naar de Kick and Punch-status. Door meerdere invoergeschiedenisvermeldingen als een enkele eenheid te behandelen, transformeren we in wezen de invoerreeks in een deel van de hele staat. Dit geeft ons de Markov-eigenschap, waarmee we Markov-ketens kunnen gebruiken om de volgende invoer te voorspellen en te raden welke combo-beweging de volgende zal zijn.
Conclusie
We spraken over de meest voorkomende tools en benaderingen bij de ontwikkeling van kunstmatige intelligentie. We hebben ook gekeken naar de situaties waarin ze moeten worden gebruikt en waar ze vooral nuttig zijn.
Dit zou voldoende moeten zijn om de basisprincipes van game-AI te begrijpen. Maar dit zijn natuurlijk niet alle methoden. Minder populair, maar niet minder effectief zijn onder meer:
- optimalisatie-algoritmen, waaronder heuvelklimmen, gradiëntafdaling en genetische algoritmen
- vijandige zoek-/planningsalgoritmen (minimax en alfa-bèta-pruning)
- classificatiemethoden (perceptrons, neurale netwerken en ondersteunende vectormachines)
- systemen voor de perceptie en het geheugen van verwerkingsagenten
- architecturale benaderingen van AI (hybride systemen, subset-architecturen en andere manieren om AI-systemen over elkaar heen te leggen)
- animatietools (planning en bewegingscoördinatie)
- prestatiefactoren (detaillering, altijd en timeslicing-algoritmen)
Internetbronnen over het onderwerp:
1. GameDev.net heeft En .
2. bevat veel presentaties en artikelen over een breed scala aan onderwerpen die verband houden met de ontwikkeling van game-AI.
3. bevat onderwerpen van de GDC AI Summit, waarvan er vele gratis beschikbaar zijn.
4. Ook op de website zijn nuttige materialen te vinden .
5. Tommy Thompson, AI-onderzoeker en game-ontwikkelaar, maakt video's op YouTube met een uitleg en studie van AI in commerciële games.
Boeken over het onderwerp:
1. De Game AI Pro-boekenreeks is een verzameling korte artikelen waarin wordt uitgelegd hoe u specifieke functies kunt implementeren of hoe u specifieke problemen kunt oplossen.
2. AI Game Programming Wisdom-serie is de voorloper van de Game AI Pro-serie. Het bevat oudere methoden, maar ze zijn bijna allemaal zelfs vandaag nog relevant.
3. is een van de basisteksten voor iedereen die het algemene vakgebied van de kunstmatige intelligentie wil begrijpen. Dit is geen boek over game-ontwikkeling; het leert de basisprincipes van AI.
Bron: www.habr.com