Érdekes anyagokra bukkantam a játékok mesterséges intelligenciájáról. A mesterséges intelligencia alapvető dolgainak magyarázatával egyszerű példákon keresztül, belül pedig számos hasznos eszköz és módszer található a kényelmes fejlesztéshez és tervezéshez. Az is megtalálható, hogyan, hol és mikor kell használni őket.
A példák többsége pszeudokóddal van megírva, így nincs szükség fejlett programozási ismeretekre. A vágás alatt 35 lapnyi szöveg található képekkel és gifekkel, úgyhogy készüljetek.
UPD. Elnézést kérek, de ezt a cikket már lefordítottam Habréról . Az ő verzióját olvashatjátok , de valamiért elment mellettem a cikk (használtam a keresést, de valami elromlott). És mivel egy játékfejlesztéssel foglalkozó blogra írok, úgy döntöttem, hogy az én fordításomat meghagyom az előfizetőknek (néhány pont másképp van formázva, néhányat a fejlesztők tanácsára szándékosan kihagytak).
Mi az az AI?
A játék mesterséges intelligencia arra összpontosít, hogy egy objektumnak milyen műveleteket kell végrehajtania az elhelyezkedése körülményei alapján. Ezt általában "intelligens ügynök" menedzsmentnek nevezik, ahol az ügynök egy játékos karakter, egy jármű, egy bot, vagy néha valami elvontabb: entitások egész csoportja vagy akár egy civilizáció. Minden esetben olyan dologról van szó, amelynek látnia kell a környezetét, az alapján kell döntéseket hoznia, és ennek megfelelően kell cselekednie. Ezt nevezzük Érzékelés/Gondolkodj/Cselekedj ciklusnak:
- Érzékelés: Az ügynök olyan információkat talál vagy kap a környezetében lévő dolgokról, amelyek befolyásolhatják viselkedését (fenyegetések a közelben, gyűjtendő tárgyak, érdekes helyek, amelyeket felfedezni kell).
- Gondolkodj: Az ügynök dönti el, hogyan reagál (megfontolja, hogy elég biztonságos-e a tárgyak összegyűjtése, vagy először harcolnia/elrejtőznie kell).
- Cselekvés: az ügynök cselekvéseket hajt végre az előző döntés végrehajtása érdekében (elindul az ellenség vagy a tárgy felé).
- ...most a szereplők cselekedetei miatt megváltozott a helyzet, így a ciklus új adatokkal ismétlődik.
A mesterséges intelligencia általában a hurok érzéki részére összpontosít. Az autonóm autók például képeket készítenek az útról, kombinálják azokat radar és lidar adatokkal, és értelmezik azokat. Ez jellemzően gépi tanulással történik, amely feldolgozza a bejövő adatokat, és jelentést ad nekik, olyan szemantikai információkat nyerve ki, mint például: „20 méterrel előtted van egy másik autó”. Ezek az úgynevezett osztályozási problémák.
A játékoknak nincs szükségük összetett rendszerre az információk kinyeréséhez, mivel az adatok nagy része már szerves részét képezi. Nincs szükség képfelismerő algoritmusok futtatására annak megállapítására, hogy van-e ellenség – a játék már ismeri, és közvetlenül a döntéshozatali folyamatba táplálja be az információkat. Ezért a ciklus Érzékelés része gyakran sokkal egyszerűbb, mint a Gondolkozz és cselekedj.
A Game AI korlátai
Az AI-nak számos korlátozása van, amelyeket be kell tartani:
- Az AI-t nem kell előre betanítani, mintha gépi tanulási algoritmus lenne. Nincs értelme neurális hálózatot írni a fejlesztés során, hogy több tízezer játékost figyeljen, és megtanulja a legjobb játékmódot ellenük. Miért? Mert a játék nem jelent meg, és nincsenek játékosok.
- A játéknak szórakoztatónak és kihívást jelentőnek kell lennie, így az ügynökök nem találhatják meg a legjobb megközelítést az emberekkel szemben.
- Az ügynököknek reálisan kell kinézniük, hogy a játékosok úgy érezzék, valódi emberek ellen játszanak. Az AlphaGo program jobban teljesített, mint az emberek, de a választott lépések nagyon távol álltak a játék hagyományos felfogásától. Ha a játék emberi ellenfelet szimulál, ennek az érzésnek nem szabad léteznie. Az algoritmust meg kell változtatni, hogy az inkább elfogadható döntéseket hozzon, mintsem ideálisat.
- Az AI-nak valós időben kell működnie. Ez azt jelenti, hogy az algoritmus nem tudja hosszú ideig monopolizálni a CPU-használatot, hogy döntéseket hozzon. Még a 10 ezredmásodperc is túl hosszú, mert a legtöbb játéknak csak 16-33 ezredmásodperc kell ahhoz, hogy elvégezze az összes feldolgozást és továbblépjen a következő grafikus keretre.
- Ideális esetben a rendszer legalább egy részének adatvezéreltnek kell lennie, hogy a nem kódolók változtatásokat hajthassanak végre, és a módosítások gyorsabban megtörténhessenek.
Nézzük meg a mesterséges intelligencia megközelítéseit, amelyek lefedik a teljes Érzékelés/Gondolkodj/Cselekedj ciklust.
Alapvető döntések meghozatala
Kezdjük a legegyszerűbb játékkal - a Ponggal. Cél: mozgasd a lapátot úgy, hogy a labda ne repüljön el mellette, hanem lepattanjon róla. Olyan ez, mint a tenisz, ahol az ember veszít, ha nem üti el a labdát. Itt az AI-nak viszonylag könnyű dolga van - eldönteni, hogy melyik irányba mozgassa a platformot.
Feltételes kijelentések
A Pong-ban a mesterséges intelligencia számára a legkézenfekvőbb megoldás az, hogy mindig megpróbáljuk a platformot a labda alá helyezni.
Egy egyszerű algoritmus ehhez, pszeudokóddal írva:
minden képkocka/frissítés a játék futása közben:
ha a labda az evező bal oldalán van:
mozgassa a lapátot balra
egyébként, ha a labda az evező jobb oldalán van:
mozgassa az evezőt jobbra
Ha a platform a labda sebességével mozog, akkor ez az ideális algoritmus a Pong AI-jához. Nem kell semmit bonyolítani, ha nincs annyi adat és lehetséges műveletek az ügynök számára.
Ez a megközelítés annyira egyszerű, hogy a teljes Érzékelés/Gondolkodj/Cselekedj ciklus alig észrevehető. De ott van:
- A Sense rész két if állításból áll. A játék tudja, hol van a labda és hol a platform, ezért az AI ezt az információt keresi.
- A Think rész is benne van a két if utasításban. Két megoldást testesítenek meg, amelyek jelen esetben kölcsönösen kizárják egymást. Ennek eredményeként a három művelet egyike kerül kiválasztásra – mozgassa a platformot balra, mozgassa jobbra, vagy ne tegyen semmit, ha már megfelelően van elhelyezve.
- Az Act rész a Move Paddle Left és Move Paddle Right utasításokban található. A játék kialakításától függően azonnal vagy meghatározott sebességgel mozgathatják a platformot.
Az ilyen megközelítéseket reaktívnak nevezik - van egy egyszerű szabálykészlet (ebben az esetben a kódban lévő utasítások), amelyek reagálnak a világ aktuális állapotára és intézkednek.
Döntési fa
A Pong-példa valójában egy formális mesterséges intelligencia-koncepcióval, az úgynevezett döntési fával egyenértékű. Az algoritmus végigmegy rajta, hogy elérje a „levelet” – a döntést arról, hogy mit kell tennie.
Készítsünk blokkdiagramot a platformunk algoritmusához tartozó döntési fáról:
A fa minden részét csomópontnak nevezik – az AI gráfelméletet használ az ilyen struktúrák leírására. Kétféle csomópont létezik:
- Döntési csomópontok: két alternatíva közötti választás valamilyen feltétel tesztelése alapján, ahol mindegyik alternatíva külön csomópontként jelenik meg.
- Végcsomópontok: A végrehajtandó művelet, amely a végső döntést jelenti.
Az algoritmus az első csomóponttól (a fa „gyökérétől”) indul. Vagy dönt arról, hogy melyik gyermekcsomóponthoz lépjen, vagy végrehajtja a csomópontban tárolt műveletet, és kilép.
Mi az előnye annak, ha egy döntési fa ugyanazt a munkát végzi, mint az előző szakaszban szereplő if utasítások? Itt van egy általános rendszer, ahol minden döntésnek csak egy feltétele és két lehetséges kimenetele van. Ez lehetővé teszi a fejlesztő számára, hogy mesterséges intelligenciát hozzon létre egy fában lévő döntéseket reprezentáló adatokból anélkül, hogy azokat keményen kellene kódolnia. Mutassuk be táblázat formájában:
A kód oldalán kapsz egy rendszert a karakterláncok olvasására. Hozzon létre mindegyikhez egy csomópontot, kösse össze a döntési logikát a második oszlop, és a gyermek csomópontokat a harmadik és negyedik oszlop alapján. Még mindig be kell programozni a feltételeket és a műveleteket, de most a játék felépítése bonyolultabb lesz. Itt további döntéseket és műveleteket adhat hozzá, majd testreszabhatja a teljes AI-t a fadefiníciós szövegfájl egyszerű szerkesztésével. Ezután átvisszük a fájlt a játéktervezőnek, aki a játék újrafordítása vagy a kód megváltoztatása nélkül módosíthatja a viselkedést.
A döntési fák nagyon hasznosak, ha automatikusan épülnek fel nagy számú példából (például az ID3 algoritmus használatával). Ez hatékony és nagy teljesítményű eszközzé teszi őket a helyzetek osztályozására a kapott adatok alapján. Azonban túllépünk egy egyszerű rendszeren, ahol az ügynökök választhatják ki a műveleteket.
Forgatókönyvek
Elemeztünk egy döntési farendszert, amely előre létrehozott feltételeket és cselekvéseket használt. Az AI-t tervező személy tetszés szerint rendezheti a fát, de továbbra is a kódolóra kell hagyatkoznia, aki az egészet programozta. Mi lenne, ha megadnánk az eszközöket a tervezőnek, hogy saját feltételeit vagy cselekvéseit létrehozhassa?
Annak érdekében, hogy a programozónak ne kelljen kódot írnia az Is Ball Left Of Paddle és a Ball Right Of Paddle feltételekhez, létrehozhat egy rendszert, amelyben a tervező feltételeket ír ezeknek az értékeknek az ellenőrzéséhez. Ekkor a döntési fa adatai így fognak kinézni:
Ez lényegében ugyanaz, mint az első táblázatban, de az önmagukban lévő megoldásoknak saját kódjuk van, kicsit olyan, mint egy if utasítás feltételes része. A kód oldalán ez a döntési csomópontok második oszlopában olvasható, de ahelyett, hogy egy konkrét végrehajtandó feltételt keresne (Is Ball Left Of Paddle), kiértékeli a feltételes kifejezést, és ennek megfelelően igaz vagy hamis értéket ad vissza. Ez a Lua vagy Angelscript szkriptnyelv használatával történik. Segítségükkel a fejlesztő tárgyakat vehet fel a játékában (labda és lapát), és olyan változókat hozhat létre, amelyek elérhetőek lesznek a szkriptben (ball.position). Ezenkívül a szkriptnyelv egyszerűbb, mint a C++. Nem igényel teljes fordítási szakaszt, így ideális a játék logikájának gyors beállításához, és lehetővé teszi a „nem kódolók” számára, hogy maguk hozzák létre a szükséges funkciókat.
A fenti példában a szkriptnyelv csak a feltételes kifejezés kiértékelésére szolgál, de műveletekhez is használható. Például a Move Paddle Right adat script utasítássá válhat (ball.position.x += 10). Annak érdekében, hogy a művelet a szkriptben is meg legyen határozva, anélkül, hogy a Move Paddle Right programozása szükséges lenne.
Még tovább is léphet, és megírhatja a teljes döntési fát szkriptnyelven. Ez kódolt feltételes utasítások formájában lesz kód, de ezek külső szkriptfájlokban helyezkednek el, vagyis a teljes program újrafordítása nélkül módosíthatók. Gyakran szerkesztheti a szkriptfájlt játék közben, hogy gyorsan tesztelje a különböző AI-reakciókat.
Eseményre adott válasz
A fenti példák tökéletesek Ponghoz. Folyamatosan futtatják a Sense/Think/Act ciklust, és a világ legújabb állapota alapján cselekszenek. De az összetettebb játékokban reagálni kell az egyes eseményekre, és nem kell mindent egyszerre értékelni. A pong ebben az esetben már rossz példa. Válasszunk másikat.
Képzeljünk el egy lövöldözőt, ahol az ellenségek mozdulatlanul állnak, amíg fel nem fedezik a játékost, majd „szakosodásuk” függvényében cselekszenek: valaki rohanni fog, valaki messziről támad. Ez még mindig egy alapvető reaktív rendszer - "ha egy játékost észrevesznek, csinálj valamit" -, de logikusan lebontható egy Player Seen eseményre és egy reakcióra (válasszon választ és hajtsa végre).
Ezzel visszajutunk az Érzékelés/Gondolkodj/Cselekedj ciklushoz. Kódolhatunk egy Sense részt, amely minden képkockában ellenőrzi, hogy az AI látja-e a lejátszót. Ha nem, akkor nem történik semmi, de ha lát, akkor létrejön a Player Seen esemény. A kódnak lesz egy külön szakasza, amely azt mondja, hogy "ha a Player Seen esemény bekövetkezik, tedd meg", ahol a válasz, amire szükséged van a Gondolkozz és cselekedj részekkel kapcsolatban. Így beállíthatja a reakciókat a Player Seen eseményre: a „rohanó” karakternek - ChargeAndAttack, és a mesterlövésznek - HideAndSnipe. Ezek a kapcsolatok létrehozhatók az adatfájlban a gyors szerkesztés érdekében, újrafordítás nélkül. A szkriptnyelv itt is használható.
Nehéz döntések meghozatala
Bár az egyszerű reakciórendszerek nagyon erősek, sok olyan helyzet van, amikor ezek nem elegendőek. Néha különböző döntéseket kell hoznia az alapján, amit az ügynök jelenleg csinál, de nehéz ezt feltételként elképzelni. Néha túl sok feltétel van ahhoz, hogy hatékonyan jelenítse meg őket egy döntési fában vagy szkriptben. Néha előre fel kell mérnie, hogyan fog változni a helyzet, mielőtt a következő lépésről döntene. E problémák megoldásához kifinomultabb megközelítésekre van szükség.
Véges állapotú gép
A véges állapotú gép vagy az FSM (véges állapotú gép) egy módja annak, hogy elmondjuk, hogy ügynökünk jelenleg a számos lehetséges állapot egyikében van, és át tud váltani egyik állapotból a másikba. Bizonyos számú ilyen állapot létezik – innen ered a név. A legjobb példa az életből a közlekedési lámpa. Különböző helyeken különböző fénysorrendek vannak, de az elv ugyanaz - minden állapot képvisel valamit (megáll, séta stb.). Egy közlekedési lámpa egy adott időpontban csak egy állapotban van, és egyszerű szabályok alapján mozog egyikből a másikba.
Hasonló a történet az NPC-kkel a játékokban. Például vegyünk egy őrt a következő állapotokkal:
- Járőrözés.
- Támadó.
- Menekülés.
És ezek a feltételek az állapot megváltoztatásához:
- Ha az őr meglátja az ellenséget, támad.
- Ha az őr támad, de már nem látja az ellenséget, visszatér járőrözni.
- Ha egy őr támad, de súlyosan megsebesül, elfut.
Írhat if-utasításokat is gyám állapotváltozóval és különféle ellenőrzésekkel: van-e ellenség a közelben, milyen az NPC állapota stb. Adjunk hozzá még néhány állapotot:
- Tétlenség – járőrözés között.
- Keresés – amikor az észlelt ellenség eltűnt.
- Segítség keresése – amikor egy ellenséget észlelnek, de túl erős ahhoz, hogy egyedül harcoljon.
Mindegyikük választása korlátozott - például az őr nem fog rejtett ellenséget keresni, ha alacsony az egészségi állapota.
Végül is van egy hatalmas lista a "ha"-ról , Azt " túl nehézkessé válhat, ezért formalizálnunk kell egy olyan módszert, amely lehetővé teszi, hogy szem előtt tartsuk az állapotokat és az állapotok közötti átmeneteket. Ehhez az összes állapotot figyelembe vesszük, és minden állapot alá listába írjuk az összes átmenetet más állapotokba, a hozzájuk szükséges feltételekkel együtt.
Ez egy állapotátmeneti táblázat – átfogó módja az FSM ábrázolásának. Rajzoljunk egy diagramot, és kapjunk teljes áttekintést arról, hogyan változik az NPC viselkedése.
A diagram az adott ügynök döntéshozatalának lényegét tükrözi az aktuális helyzet alapján. Sőt, minden nyíl átmenetet mutat az állapotok között, ha a mellette lévő feltétel igaz.
Minden frissítésnél ellenőrizzük az ügynök aktuális állapotát, átnézzük az átmenetek listáját, és ha az átmenet feltételei teljesülnek, akkor elfogadja az új állapotot. Például minden keret ellenőrzi, hogy a 10 másodperces időzítő lejárt-e, és ha igen, akkor az őr az alapjárati állapotból járőrözésbe lép. Ugyanígy a Támadó állapot is ellenőrzi az ügynök egészségi állapotát – ha alacsony, akkor menekülő állapotba kerül.
Ez az állapotok közötti átmenetek kezelése, de mi a helyzet az állapotokhoz kapcsolódó viselkedéssel? Egy adott állapot tényleges viselkedésének megvalósítása szempontjából jellemzően kétféle „horog” létezik, ahol műveleteket rendelünk az FSM-hez:
- Műveletek, amelyeket rendszeresen végrehajtunk az aktuális állapothoz.
- Azok a műveletek, amelyeket az egyik állapotból a másikba való átmenet során végzünk.
Példák az első típusra. A Járőrözés állapota minden keretben mozgatja az ügynököt az őrjárati útvonalon. A Támadó állapot minden egyes keretben megpróbál támadást kezdeményezni, vagy olyan állapotba lépni, ahol ez lehetséges.
A második típus esetében fontolja meg az átmenetet: „ha az ellenség látható, és az ellenség túl erős, akkor lépjen a Segítség keresése állapotba. Az ügynöknek ki kell választania, hová forduljon segítségért, és el kell tárolnia ezeket az információkat, hogy a Segítség keresése állapot tudja, hová forduljon. Amint segítséget talál, az ügynök visszatér Támadó állapotba. Ezen a ponton beszélni akar a szövetségesével a fenyegetésről, így előfordulhat a NotifyFriendOfThreat akció.
Ezt a rendszert ismét az Érzékelés/Gondolkodj/Cselekedj ciklus lencséjén keresztül tekinthetjük meg. Az értelmet az átmeneti logika által használt adatok testesítik meg. Gondolkozz – az egyes állapotokban elérhető átmenetek. Az Actet pedig egy állapoton belül, vagy az állapotok közötti átmenetek során periodikusan végrehajtott cselekvések hajtják végre.
Néha a folyamatos lekérdezés átmeneti feltételei költségesek lehetnek. Például, ha minden ügynök minden keretben összetett számításokat végez annak megállapítására, hogy látja-e az ellenséget, és megérti, hogy át tud-e váltani a Járőrözés állapotból a Támadó állapotba, ez sok CPU-időt vesz igénybe.
A világ állapotában bekövetkezett fontos változásokat olyan eseményeknek tekinthetjük, amelyek feldolgozásra kerülnek, amint bekövetkeznek. Ahelyett, hogy az FSM minden keretben ellenőrizné a „láthatja-e az ügynököm a lejátszót?” átmeneti feltételt, külön rendszer konfigurálható a ritkább (pl. másodpercenként 5-ször) ellenőrzésre. Az eredmény pedig a Player Seen kiadása, amikor a csekk átmegy.
Ezt továbbítja az FSM-nek, amelynek most a Player Seen esemény fogadott állapotába kell lépnie, és ennek megfelelően válaszolnia kell. A kapott viselkedés ugyanaz, kivéve a válaszadás előtti szinte észrevehetetlen késést. De a teljesítmény javult annak eredményeként, hogy a Sense részt a program külön részévé választották.
Hierarchikus véges állapotú gép
A nagy FSM-ekkel való munka azonban nem mindig kényelmes. Ha ki akarjuk terjeszteni a támadási állapotot a MeleeAttacking és a RangedAttacking elkülönítésére, akkor meg kell változtatnunk az összes többi állapot átmenetét, amely a Támadó állapothoz vezet (jelenlegi és jövőbeli).
Valószínűleg észrevette, hogy példánkban sok ismétlődő átmenet van. Az alapjárati állapot legtöbb átmenete megegyezik az őrjárati állapot átmeneteivel. Jó lenne, ha nem ismételnénk magunkat, különösen, ha több hasonló állapotot adunk hozzá. Az alapjáratot és a járőrözést célszerű a „nem harc” általános címke alá csoportosítani, ahol csak egy közös átmenet van a harci állapotokba. Ha ezt a címkét állapotnak tekintjük, akkor az üresjárat és a járőrözés részállapotokká válnak. Példa külön átmeneti táblázat használatára egy új, nem harci részállapothoz:
Főbb állapotok:
Harcon kívüli állapot:
És diagram formájában:
Ez ugyanaz a rendszer, de egy új, nem harci állapottal, amely magában foglalja az alapjáratot és a járőrözést. Minden olyan állapottal, amely egy FSM-et tartalmaz részállapotokkal (és ezek az alállapotok viszont tartalmazzák a saját FSM-eiket - és így tovább, ameddig csak szükséges), kapunk egy Hierarchikus véges állapotú gépet vagy HFSM-et (hierarchikus véges állapotú gép). A nem harci állapot csoportosításával egy csomó redundáns átmenetet kivágtunk. Ugyanezt megtehetjük bármely közös átmenettel rendelkező új állapot esetén. Például, ha a jövőben kiterjesztjük a Támadó állapotot a MeleeAttacking és Missile Attacking állapotokra, akkor ezek olyan részállapotok lesznek, amelyek az ellenségtől való távolság és a lőszer rendelkezésre állása alapján váltanak át egymás között. Ennek eredményeként az összetett viselkedések és részviselkedések minimális ismétlődő átmenetekkel reprezentálhatók.
Viselkedés fa
A HFSM segítségével a viselkedések összetett kombinációi egyszerű módon jönnek létre. Némi nehézséget jelent azonban, hogy az átmeneti szabályok formájában történő döntéshozatal szorosan összefügg a jelenlegi állapottal. És sok játékban pontosan erre van szükség. Az állapothierarchia gondos használata pedig csökkentheti az átmenet-ismétlések számát. De néha olyan szabályokra van szükség, amelyek működnek függetlenül attól, hogy milyen állapotban van, vagy amelyek szinte minden államban érvényesek. Például, ha egy ügynök egészségi állapota 25%-ra csökken, akkor azt akarja, hogy elfusson, függetlenül attól, hogy harcban volt, tétlen volt vagy beszélt – ezt a feltételt minden állapothoz hozzá kell adnia. És ha a tervezője később 25%-ról 10%-ra szeretné módosítani az alacsony egészségügyi küszöböt, akkor ezt újra meg kell tenni.
Ideális esetben ez a helyzet egy olyan rendszert kíván meg, amelyben a „milyen állapotba kerülés” döntései magukon az állapotokon kívül esnek, hogy csak egy helyen hajtsanak végre változtatásokat, és ne érintsék az átmenet feltételeit. Viselkedésfák jelennek meg itt.
Megvalósításuknak többféle módja van, de a lényeg nagyjából mindenkinél ugyanaz, és hasonló a döntési fához: az algoritmus egy „gyökér” csomóponttal kezdődik, és a fa olyan csomópontokat tartalmaz, amelyek akár döntéseket, akár cselekvéseket reprezentálnak. Van azonban néhány lényeges különbség:
- A csomópontok a következő három érték valamelyikét adják vissza: Sikeres (ha a feladat befejeződött), Sikertelen (ha nem indítható) vagy Fut (ha még fut, és nincs végeredmény).
- Nincs több döntési csomópont, amely két alternatíva közül választhat. Ehelyett Decorator csomópontok, amelyeknek egy gyermek csomópontja van. Ha sikerrel járnak, végrehajtják egyetlen gyermekcsomópontjukat.
- A műveleteket végrehajtó csomópontok Futó értéket adnak vissza a végrehajtott műveletek megjelenítéséhez.
Ez a kis csomópontkészlet kombinálható nagyszámú összetett viselkedés létrehozásához. Képzeljük el az előző példa HFSM őrét viselkedési faként:
Ezzel a struktúrával nem lehet nyilvánvaló átmenet alapjárati/járőrözési állapotból támadó vagy bármely más állapotba. Ha egy ellenség látható, és a karakter állapota alacsony, a végrehajtás leáll a menekülő csomópontnál, függetlenül attól, hogy az előzőleg melyik csomópontot hajtotta végre – járőrözést, tétlenséget, támadást vagy bármilyen mást.
A viselkedésfák összetettek – sokféleképpen lehet összeállítani őket, és a dekorátorok és az összetett csomópontok megfelelő kombinációjának megtalálása kihívást jelenthet. Kérdések merülnek fel azzal kapcsolatban is, hogy milyen gyakran kell ellenőrizni a fát – minden részét át akarjuk menni, vagy csak akkor, ha valamelyik feltétel megváltozott? Hogyan tároljuk a csomópontokra vonatkozó állapotokat – honnan tudhatjuk meg, hogy mikor voltunk 10 másodpercig üresjáratban, vagy honnan tudjuk, hogy melyik csomópont futott utoljára, hogy megfelelően tudjuk feldolgozni a sorozatot?
Ezért van sok megvalósítás. Például egyes rendszerek a dekorátor csomópontokat beépített dekorátorokra cserélték. Újraértékelik a fát, amikor megváltoznak a dekorátor feltételei, segítenek a csomópontok összekapcsolásában, és rendszeres frissítéseket biztosítanak.
Közmű alapú rendszer
Egyes játékoknak sokféle mechanikája van. Kívánatos, hogy az egyszerű és általános átmeneti szabályok minden előnyét megkapják, de nem feltétlenül egy teljes viselkedésfa formájában. Ahelyett, hogy világos választási lehetőségekkel vagy lehetséges cselekvések fájával rendelkeznénk, könnyebb az összes cselekvést megvizsgálni, és kiválasztani a pillanatnyilag legmegfelelőbbet.
A segédprogram-alapú rendszer éppen ebben segít. Ez egy olyan rendszer, amelyben az ügynök számos műveletet hajt végre, és az egyes műveletek relatív hasznossága alapján választja ki, hogy melyiket hajtsa végre. Ahol a hasznosság tetszőleges mértéke annak, hogy mennyire fontos vagy kívánatos az ügynök számára ennek a műveletnek a végrehajtása.
Egy műveletnek az aktuális állapot és környezet alapján számított hasznossága, az ügynök bármikor ellenőrizheti és kiválaszthatja a legmegfelelőbb egyéb állapotot. Ez hasonló az FSM-hez, kivéve, ha az átmeneteket az egyes potenciális állapotok becslése határozza meg, beleértve az aktuális állapotot is. Felhívjuk figyelmét, hogy a leghasznosabb műveletet választjuk a továbblépéshez (vagy maradjunk, ha már befejeztük). A változatosság kedvéért ez egy kiegyensúlyozott, de véletlenszerű válogatás lehet egy kis listából.
A rendszer a hasznossági értékek tetszőleges tartományát rendeli hozzá – például 0-tól (teljesen nem kívánatos) 100-ig (teljesen kívánatos). Minden műveletnek számos paramétere van, amelyek befolyásolják ennek az értéknek a kiszámítását. Visszatérve a gyámi példánkhoz:
A cselekvések közötti átmenetek kétértelműek – bármely állapot követheti a másikat. A műveleti prioritások a visszaadott segédprogramértékekben találhatók. Ha egy ellenség látható, és az ellenség erős, és a karakter egészsége alacsony, akkor a Fleeing és a FindingHelp is magas, nullától eltérő értéket ad vissza. Ebben az esetben a FindingHelp mindig magasabb lesz. Hasonlóképpen, a nem harci tevékenységek soha nem adnak többet 50-nél, tehát mindig alacsonyabbak lesznek, mint a harciak. Ezt figyelembe kell vennie a műveletek létrehozásakor és hasznosságuk kiszámításakor.
Példánkban a műveletek vagy egy rögzített állandó értéket, vagy két rögzített érték valamelyikét adják vissza. Egy reálisabb rendszer folytonos értéktartományból adna becslést. Például a Menekülés akció magasabb hasznossági értékeket ad vissza, ha az ügynök állapota alacsony, a Támadás akció pedig alacsonyabb hasznossági értékeket ad vissza, ha az ellenség túl erős. Emiatt a Menekülés akció elsőbbséget élvez a Támadással szemben minden olyan helyzetben, amikor az ügynök úgy érzi, hogy nincs elég egészsége az ellenség legyőzéséhez. Ez lehetővé teszi a műveletek tetszőleges számú kritérium alapján történő rangsorolását, így ez a megközelítés rugalmasabb és változékonyabb, mint egy viselkedési fa vagy az FSM.
Minden műveletnek számos feltétele van a programszámításhoz. Írhatók szkriptnyelven vagy matematikai képletek sorozataként. A Sims, amely egy karakter napi rutinját szimulálja, további számítási réteget ad – az ügynök egy sor „motivációt” kap, amelyek befolyásolják a hasznossági besorolásokat. Ha egy karakter éhes, idővel még éhesebbé válik, és az EatFood akció hasznossági értéke növekszik, amíg a karakter végrehajtja azt, csökkentve az éhség szintjét és az EatFood értékét nullára.
A besorolási rendszeren alapuló műveletek kiválasztásának ötlete meglehetősen egyszerű, így a segédprogram-alapú rendszer inkább az AI döntéshozatali folyamatok részeként használható, nem pedig teljes helyettesítőjeként. A döntési fa kérheti két gyermek csomópont hasznossági besorolását, és kiválaszthatja a magasabbat. Hasonlóképpen, egy viselkedésfának lehet egy összetett segédprogram-csomópontja, amely értékeli a műveletek hasznosságát, és eldönti, hogy melyik gyermeket hajtsa végre.
Mozgás és navigáció
Az előző példákban volt egy emelvényünk, amelyet balra vagy jobbra mozgattunk, és egy őr, amely járőrözött vagy támadott. De hogyan kezeljük pontosan az ügynökmozgást egy bizonyos időszakon keresztül? Hogyan állítsuk be a sebességet, hogyan kerüljük el az akadályokat, és hogyan tervezzünk útvonalat, ha egy úti cél elérése nehezebb, mint egyenes vonalban haladni? Nézzük ezt.
vezetés
A kezdeti szakaszban feltételezzük, hogy minden ügynöknek van sebességértéke, amely magában foglalja, hogy milyen gyorsan és milyen irányban mozog. Mérhető méter per másodpercben, kilométer per óra, pixel per másodperc, stb. A Sense/Think/Act hurkot felidézve elképzelhetjük, hogy a Think rész kiválaszt egy sebességet, és az Act rész ezt a sebességet alkalmazza az ügynökre. Általában a játékoknak van egy fizikai rendszere, amely elvégzi ezt a feladatot, megtanulja az egyes objektumok sebességértékét, és beállítja azt. Ezért az AI-t egyetlen feladattal hagyhatja - eldönteni, milyen sebességgel kell rendelkeznie az ügynöknek. Ha tudja, hol kell lennie az ügynöknek, akkor beállított sebességgel kell mozgatnia a megfelelő irányba. Egy nagyon triviális egyenlet:
kívánt_utazás = rendeltetési hely – ügynök pozíciója
Képzelj el egy 2D-s világot. Az ügynök a (-2,-2) pontban van, a cél valahol északkeleten van a (30, 20) pontban, és az ügynök eléréséhez szükséges útvonal (32, 22). Tegyük fel, hogy ezeket a pozíciókat méterben mérjük – ha az ügynök sebességét 5 méter/másodpercnek vesszük, akkor az elmozdulásvektorunkat skálázzuk, és körülbelül (4.12, 2.83) sebességet kapunk. Ezekkel a paraméterekkel az ügynök közel 8 másodperc alatt megérkezne a rendeltetési helyére.
Az értékeket bármikor újraszámolhatja. Ha az ügynök félúton lenne a cél felé, akkor a mozgás fele akkora lenne, de mivel az ügynök maximális sebessége 5 m/s (ezt fentebb döntöttük el), a sebesség ugyanaz lesz. Ez a mozgó célok esetében is működik, lehetővé téve az ügynök számára, hogy kis változtatásokat hajtson végre mozgásuk során.
De több variációra van szükségünk – például lassan növeljük a sebességet, hogy szimuláljuk a karaktert, aki állóból futni kezd. Ugyanezt meg lehet tenni a végén, a leállás előtt. Ezeket a jellemzőket kormányzási viselkedésnek nevezik, amelyek mindegyikének sajátos neve van: keresés, menekülés, érkezés stb. Az ötlet az, hogy a gyorsító erők az ügynök sebességére vonatkoztathatók, az ügynök helyzetének és aktuális sebességének összehasonlítása alapján a célállomással. hogy különböző módszereket alkalmazzanak a cél felé való elmozdulás érdekében.
Minden viselkedésnek kicsit más a célja. A keresés és az érkezés az ügynökök rendeltetési helyre történő mozgatásának módjai. Az Akadálykerülés és az Elkülönülés úgy állítja be az ügynök mozgását, hogy elkerülje az akadályokat a cél felé vezető úton. Az összehangolás és a kohézió együtt mozgatja az ügynököket. Tetszőleges számú különböző kormányzási viselkedés összegezhető, hogy egyetlen útvonalvektort állítsunk elő, minden tényezőt figyelembe véve. Egy ügynök, amely az Érkezés, az Elválasztás és az Akadálykerülés viselkedését használja, hogy távol maradjon a falaktól és más ügynököktől. Ez a megközelítés jól működik nyitott helyeken, szükségtelen részletek nélkül.
Nehezebb körülmények között a különböző viselkedésmódok összeadása rosszabbul működik – például egy ügynök beszorulhat a falba az Érkezés és az Akadálykerülés közötti konfliktus miatt. Ezért olyan lehetőségeket kell mérlegelnie, amelyek összetettebbek, mint az összes érték egyszerű hozzáadása. A módszer a következő: ahelyett, hogy összeadná az egyes viselkedések eredményeit, mérlegelheti a különböző irányú mozgásokat, és kiválaszthatja a legjobb lehetőséget.
Azonban egy bonyolult környezetben, ahol zsákutcák és választási lehetőségek vannak arra vonatkozóan, hogy melyik utat választjuk, szükségünk lesz valami még fejlettebbre.
Az út megtalálása
A kormányzási viselkedés kiválóan alkalmas nyílt területen (futballpálya vagy aréna) való egyszerű mozgáshoz, ahol az A-ból B-be való eljutás egyenes út, csak kisebb kerülőkkel az akadályok körül. Összetett útvonalakhoz útkeresésre van szükségünk, ami egy módja annak, hogy felfedezzük a világot és eldöntsük, milyen útvonalat vezetünk át rajta.
A legegyszerűbb az, ha rácsot helyezünk az ügynök melletti minden négyzetre, és értékeljük, melyikük mozoghat. Ha az egyik úti cél, akkor kövesse az útvonalat minden mezőtől az előzőig, amíg el nem éri az elejére. Ez az útvonal. Ellenkező esetben ismételje meg a folyamatot a közeli többi mezővel, amíg meg nem találja az úti célt, vagy el nem fogy a négyzet (ami azt jelenti, hogy nincs lehetséges útvonal). Ezt hivatalosan Breadth-First Search vagy BFS (szélesség-első keresési algoritmus) néven ismerik. Minden lépésnél minden irányba néz (tehát szélesség, "szélesség"). A keresési tér olyan, mint egy hullámfront, amely addig mozog, amíg el nem éri a kívánt helyet - a keresési tér minden lépésnél kitágul, amíg be nem foglalja a végpontot, ami után visszavezethető az elejére.
Ennek eredményeként kap egy listát azokról a négyzetekről, amelyek mentén a kívánt útvonalat összeállítják. Ez az útvonal (tehát az útkeresés) – azon helyek listája, amelyeket az ügynök meglátogat, miközben követi a célt.
Tekintettel arra, hogy ismerjük a világ minden négyzetének helyzetét, kormányzási viselkedésekkel haladhatunk az útvonalon - az 1. csomóponttól a 2. csomópontig, majd a 2. csomóponttól a 3. csomópontig, és így tovább. A legegyszerűbb megoldás a következő négyzet közepe felé haladni, de még jobb megoldás, ha megállunk az aktuális és a következő négyzet közötti perem közepén. Emiatt az ügynök képes lesz sarkokat vágni éles kanyarokban.
A BFS-algoritmusnak vannak hátrányai is - annyi négyzetet tár fel „rossz” irányba, mint „jó” irányba. Itt jön képbe az A* (A csillag) nevű bonyolultabb algoritmus. Ugyanúgy működik, de ahelyett, hogy vakon vizsgálná a szomszéd négyzeteket (majd a szomszédok szomszédai, majd a szomszédok szomszédai és így tovább), összegyűjti a csomópontokat egy listába, és úgy rendezi őket, hogy a következő vizsgált csomópont mindig a amelyik a legrövidebb útra vezet. A csomópontok egy heurisztika alapján vannak rendezve, amely két dolgot vesz figyelembe: a kívánt négyzethez vezető hipotetikus útvonal „költségét” (beleértve az esetleges utazási költségeket), valamint annak becslését, hogy a négyzet milyen messze van a céltól (a keresést a jó irány).
Ez a példa azt mutatja, hogy az ügynök egyszerre egy négyzetet vizsgál meg, és minden alkalommal kiválasztja a szomszédos mezőt, amelyik a legígéretesebb. A kapott útvonal ugyanaz, mint a BFS, de kevesebb négyzetet vettek figyelembe a folyamatban - ami nagy hatással van a játék teljesítményére.
Mozgás rács nélkül
De a legtöbb játék nincs rácsra rakva, és ez gyakran lehetetlen a realizmus feláldozása nélkül. Kompromisszumokra van szükség. Milyen méretűek legyenek a négyzetek? Túl nagyok, és nem tudják helyesen ábrázolni a kis folyosókat vagy kanyarokat, túl kicsik, és túl sok négyzetet kell keresni, ami végül sok időt vesz igénybe.
Az első dolog, amit meg kell értenünk, hogy a háló a kapcsolódó csomópontok grafikonját adja meg. Az A* és BFS algoritmusok valójában gráfokon működnek, és egyáltalán nem törődnek a hálónkkal. Bárhol elhelyezhetnénk csomópontokat a játék világában: amíg van kapcsolat bármely két összekapcsolt csomópont, valamint a kezdő- és végpont és legalább az egyik csomópont között, addig az algoritmus ugyanolyan jól fog működni, mint korábban. Ezt gyakran nevezik útpontrendszernek, mivel minden csomópont egy jelentős pozíciót képvisel a világban, amely tetszőleges számú hipotetikus útvonal része lehet.
1. példa: egy csomó minden négyzetben. A keresés attól a csomóponttól kezdődik, ahol az ügynök található, és a kívánt négyzet csomópontjánál ér véget.
2. példa: Csomópontok (útpontok) kisebb halmaza. A keresés az ügynök négyzeténél kezdődik, végigmegy a szükséges számú csomóponton, majd a célig folytatódik.
Ez egy teljesen rugalmas és hatékony rendszer. De némi körültekintésre van szükség annak eldöntésében, hogy hol és hogyan helyezzen el egy útpontot, különben az ügynökök egyszerűen nem látják a legközelebbi pontot, és nem tudják elindítani az utat. Könnyebb lenne, ha a világ geometriája alapján automatikusan elhelyezhetnénk az útpontokat.
Itt jelenik meg a navigációs háló vagy navmesh (navigációs háló). Ez általában egy háromszögekből álló 2D-s háló, amely a világ geometriájára fedi – bárhol is járhat az ügynök. A hálóban lévő háromszögek mindegyike csomóponttá válik a grafikonon, és legfeljebb három szomszédos háromszögük lesz, amelyek szomszédos csomópontokká válnak a grafikonon.
Ez a kép egy példa a Unity motorból - elemezte a világ geometriáját, és létrehozott egy navmesh-t (a képernyőképen világoskék). A navigációs háló minden sokszöge egy olyan terület, ahol egy ügynök állhat vagy mozoghat egyik sokszögről a másik poligonra. Ebben a példában a sokszögek kisebbek, mint az emeletek, amelyeken találhatók – ez azért történik, hogy figyelembe vegyék az ügynök méretét, amely túlnyúlik a névleges helyzetén.
Ezen a hálón keresztül kereshetünk útvonalat, ismét az A* algoritmus használatával. Ezzel szinte tökéletes útvonalat kapunk a világban, amely minden geometriát figyelembe vesz, és nem igényel felesleges csomópontokat és útpontok létrehozását.
Az útkeresés túl tág téma, amelyhez a cikk egy része nem elég. Ha részletesebben szeretné tanulmányozni, akkor ez segít .
Планирование
Az útkeresés során megtanultuk, hogy néha nem elég csak kiválasztani az irányt és haladni – ki kell választanunk egy útvonalat, és néhány kanyarral el kell érnünk a kívánt célt. Általánosíthatjuk ezt az elképzelést: a cél elérése nem csak a következő lépés, hanem egy egész sorozat, ahol néha több lépést is előre kell tekinteni, hogy megtudja, mi legyen az első. Ezt hívják tervezésnek. Az útkeresés a tervezés számos kiterjesztésének egyikeként fogható fel. Ami az Érzékelés/Gondolkodj/Cselekedj ciklust illeti, ez az a hely, ahol a Gondolkodó rész több cselekvési részt tervez a jövőre nézve.
Nézzük a Magic: The Gathering társasjáték példáját. Először a következő kártyakészlettel a kezünkben megyünk:
- Mocsár – 1 fekete manát ad (földkártyát).
- Erdő – ad 1 zöld manát (földkártyát).
- Fugitive Wizard – 1 kék mana szükséges az előhíváshoz.
- Elvish Mystic – 1 zöld mana szükséges az előhíváshoz.
A maradék három kártyát figyelmen kívül hagyjuk, hogy könnyebb legyen. A szabályok szerint egy játékos körönként 1 földkártyát játszhat ki, erre a kártyára „koppintva” manát húzhat ki belőle, majd a mana mennyiségének megfelelően varázsolhat (beleértve a lény megidézését is). Ebben a helyzetben az emberi játékos tudja, hogy játsszon Forest-tel, érintsen meg 1 zöld manát, majd megidézze az Elvish Mystic-et. De hogyan tudja ezt kitalálni a játék AI?
Könnyű tervezés
A triviális megközelítés az, hogy minden egyes akciót egymás után próbálunk meg, amíg nem marad a megfelelő. A kártyákra nézve az AI látja, hogy Swamp mit tud játszani. És eljátssza. Maradtak még egyéb teendők ebből a körből? Nem tudja megidézni sem az Elvish Mystic-et, sem a Fugitive Wizard-ot, mivel zöld és kék manára van szükségük megidézéséhez, míg a Swamp csak fekete manát biztosít. Erdőt pedig már nem játszhatja, mert már játszotta Swampot. Így a játék mesterséges intelligencia követte a szabályokat, de rosszul tette. Javítható.
A tervezés megkeresheti azon műveletek listáját, amelyek a játékot a kívánt állapotba hozzák. Ahogy az ösvényen minden négyzetnek voltak szomszédai (az útkeresésben), úgy a terv minden tevékenységének is vannak szomszédai vagy utódai. Ezeket a cselekvéseket és az azt követő cselekvéseket addig kereshetjük, amíg el nem érjük a kívánt állapotot.
Példánkban a kívánt eredmény „ha lehetséges, hívj meg egy lényt”. A kör elején csak két lehetséges akciót látunk, amelyet a játékszabályok engedélyeznek:
1. Játssz a Swamp játékkal (eredmény: Swamp a játékban)
2. Játssz az Erdővel (eredmény: Erdő a játékban)
Minden egyes tett további akciókhoz vezethet, és bezárhat másokat is, a játékszabályoktól függően. Képzeld el, hogy Mocsárral játszottunk – ez a következő lépésként eltávolítja a Swamp-ot (már játszottunk vele), és ezzel az Erdőt is eltávolítjuk (mert a szabályok szerint körönként egy földkártyát játszhatsz ki). Ezt követően az AI következő lépésként 1 fekete manát ad hozzá, mert nincs más lehetőség. Ha továbbmegy, és a Tap the Swamp lehetőséget választja, 1 egység fekete manát kap, és nem tud vele mit kezdeni.
1. Játssz a Swamp játékkal (eredmény: Swamp a játékban)
1.1 „Tap” mocsár (eredmény: Swamp „csapolt”, +1 egység fekete mana)
Nincsenek elérhető műveletek – END
2. Játssz az Erdővel (eredmény: Erdő a játékban)
Az akciók listája rövid volt, zsákutcába jutottunk. A folyamatot megismételjük a következő lépéshez. Játsszunk az Erdővel, megnyitjuk a „kap 1 zöld manát” akciót, ami viszont megnyitja a harmadik akciót – megidézzük az Elvish Mystic-et.
1. Játssz a Swamp játékkal (eredmény: Swamp a játékban)
1.1 „Tap” mocsár (eredmény: Swamp „csapolt”, +1 egység fekete mana)
Nincsenek elérhető műveletek – END
2. Játssz az Erdővel (eredmény: Erdő a játékban)
2.1 „Tap” erdő (eredmény: Az erdő „csapolt”, +1 egység zöld mana)
2.1.1 Elvish Mystic megidézése (eredmény: Elvish Mystic játékban, -1 zöld mana)
Nincsenek elérhető műveletek – END
Végül megvizsgáltuk az összes lehetséges cselekvést, és találtunk egy tervet, amely megidéz egy lényt.
Ez egy nagyon leegyszerűsített példa. Célszerű a lehető legjobb tervet választani, nem pedig bármilyen, bizonyos kritériumoknak megfelelő tervet. Általában lehetséges a potenciális tervek értékelése végrehajtásuk eredménye vagy általános haszna alapján. Földkártya kijátszásáért 1 pontot, lény megidézéséért pedig 3 pontot szerezhetsz magadnak. A Swamp játéka 1 pontos terv lenne. Az Erdő → Érintse meg az Erdőt → Az Elvish Mystic megidézése pedig azonnal 4 pontot ad.
Így működik a tervezés a Magic: The Gatheringben, de ugyanez a logika más helyzetekben is érvényesül. Például egy gyalog mozgatása, hogy helyet adjon a püspöknek a sakkban való mozgáshoz. Vagy takarodjon a fal mögé, hogy biztonságosan lőjön XCOM-ban, mint ez. Általában megérted az ötletet.
Továbbfejlesztett tervezés
Néha túl sok lehetséges lépés van ahhoz, hogy minden lehetséges lehetőséget mérlegeljünk. Visszatérve a Magic: The Gathering példájához: tegyük fel, hogy a játékban és a kezedben több föld- és lénykártya van – a lehetséges lépéskombinációk száma tucatnyi lehet. A problémára többféle megoldás is létezik.
Az első módszer a visszafelé láncolás. Ahelyett, hogy minden kombinációt kipróbálnánk, jobb, ha a végeredménnyel kezdjük, és megpróbálunk közvetlen útvonalat találni. Ahelyett, hogy a fa gyökerétől egy adott levélig mennénk, az ellenkező irányba haladunk - a levéltől a gyökér felé. Ez a módszer egyszerűbb és gyorsabb.
Ha az ellenségnek 1 életereje van, megtalálhatja az "egy vagy több sebzést" tervet. Ennek eléréséhez számos feltételnek kell teljesülnie:
1. Sebzést okozhat egy varázslat – kézben kell lennie.
2. A varázslathoz manára van szüksége.
3. A mana megszerzéséhez ki kell játszani egy földkártyát.
4. Földkártya kijátszásához a kezedben kell lennie.
Egy másik módszer a legjobb első keresés. Ahelyett, hogy az összes utat kipróbálnánk, a legmegfelelőbbet választjuk. Leggyakrabban ez a módszer az optimális tervet adja meg felesleges keresési költségek nélkül. Az A* a legjobb első keresés egyik formája – a legígéretesebb útvonalak kezdettől fogva megvizsgálásával máris megtalálhatja a legjobb utat anélkül, hogy más lehetőségeket kellene ellenőriznie.
Egy érdekes és egyre népszerűbb legjobb első keresési lehetőség a Monte Carlo Tree Search. Ahelyett, hogy az egyes további akciók kiválasztásakor azt találgatná, hogy mely tervek jobbak a többinél, az algoritmus minden lépésnél véletlenszerű utódot választ a végére (amikor a terv győzelmet vagy vereséget eredményezett). A végeredmény ezután az előző opciók súlyának növelésére vagy csökkentésére szolgál. Ha ezt a folyamatot egymás után többször megismétli, az algoritmus jó becslést ad arra vonatkozóan, hogy mi a legjobb következő lépés, még akkor is, ha a helyzet megváltozik (ha az ellenség megzavarja a játékost).
A játékokban a tervezésről szóló történet sem lenne teljes a célorientált cselekvési tervezés vagy a GOAP (célorientált cselekvéstervezés) nélkül. Ez egy széles körben használt és tárgyalt módszer, de néhány megkülönböztető részlettől eltekintve lényegében az a visszafelé láncolási módszer, amelyről korábban beszéltünk. Ha a cél a „játékos elpusztítása” volt, és a játékos a fedezék mögött van, a terv a következő lehet: pusztíts gránáttal → szerezd meg → dobd el.
Általában több cél van, mindegyiknek megvan a maga prioritása. Ha a legmagasabb prioritású célt nem lehet teljesíteni (egyetlen akciókombináció sem hoz létre "öld meg a játékost" tervet, mert a játékos nem látható), az AI visszaáll az alacsonyabb prioritású célokra.
Képzés és alkalmazkodás
Azt már mondtuk, hogy a játék mesterséges intelligencia általában nem használ gépi tanulást, mert nem alkalmas ügynökök valós idejű kezelésére. De ez nem jelenti azt, hogy nem kölcsönözhetsz valamit erről a területről. Olyan ellenfelet akarunk egy lövészben, akitől tanulhatunk valamit. Például tájékozódjon a legjobb pozíciókról a térképen. Vagy egy verekedős játékban egy ellenfél, aki blokkolná a játékos gyakran használt kombómozdulatait, motiválva ezzel másokat. Tehát a gépi tanulás nagyon hasznos lehet ilyen helyzetekben.
Statisztikák és valószínűségek
Mielőtt bonyolult példákba kezdenénk, nézzük meg, meddig juthatunk el néhány egyszerű mérés elvégzésével, és ezek felhasználásával döntéseket hozunk. Például valós idejű stratégia – hogyan határozzuk meg, hogy egy játékos indíthat-e támadást a játék első perceiben, és milyen védekezéssel kell ez ellen felkészülni? Tanulmányozhatjuk a játékos múltbeli tapasztalatait, hogy megértsük, milyen reakciók lehetnek a jövőben. Kezdetben nem rendelkezünk ilyen nyers adatokkal, de össze tudjuk gyűjteni – minden alkalommal, amikor az AI ember ellen játszik, rögzítheti az első támadás időpontját. Néhány session után átlagosan megkapjuk azt az időt, amely alatt a játékos a jövőben támad.
Az átlagértékekkel is van probléma: ha egy játékos 20-szor rohant, és 20-szor lassan játszott, akkor a szükséges értékek valahol középen lesznek, és ez nem ad nekünk semmi hasznosat. Az egyik megoldás a bemeneti adatok korlátozása - az utolsó 20 darabot lehet figyelembe venni.
Hasonló megközelítést alkalmaznak bizonyos cselekvések valószínűségének becslésekor, feltételezve, hogy a játékos múltbeli preferenciái a jövőben is megegyeznek. Ha egy játékos ötször tűzgolyóval, kétszer villámmal és egyszer közelharccal támad ránk, nyilvánvaló, hogy a tűzgolyót preferálja. Extrapoláljuk és nézzük meg a különböző fegyverek használatának valószínűségét: tűzgolyó=62,5%, villám=25% és közelharci=12,5%. A játékunknak az AI-nak fel kell készülnie, hogy megvédje magát a tűztől.
Egy másik érdekes módszer a Naive Bayes osztályozó használata nagy mennyiségű bemeneti adat tanulmányozására és a helyzet osztályozására, hogy az AI a kívánt módon reagáljon. A Bayes-féle osztályozók leginkább az e-mail spamszűrőkben való használatukról ismertek. Ott megvizsgálják a szavakat, összehasonlítják őket azzal, ahol a szavak korábban megjelentek (spamben vagy sem), és következtetéseket vonnak le a bejövő e-mailekről. Ugyanezt még kevesebb bemenettel is megtehetjük. Az AI által látott összes hasznos információ (például milyen ellenséges egységeket hoznak létre, milyen varázslatokat használnak, vagy milyen technológiákat kutattak) és a végeredmény (háború vagy béke, rohanás vagy védekezés stb.) alapján. - kiválasztjuk a kívánt AI viselkedést.
Mindezek a képzési módszerek elegendőek, de a tesztelési adatok alapján célszerű alkalmazni őket. A mesterséges intelligencia megtanul alkalmazkodni a játéktesztelői által használt különféle stratégiákhoz. Az a mesterséges intelligencia, amely a megjelenés után alkalmazkodik a lejátszóhoz, túl kiszámíthatóvá válhat, vagy túl nehéz lesz legyőzni.
Értékalapú adaptáció
Tekintettel a játékvilágunk tartalmára és a szabályokra, a bemeneti adatok felhasználása helyett megváltoztathatjuk a döntéshozatalt befolyásoló értékrendet. Ezt csináljuk:
- Hagyja, hogy az AI adatokat gyűjtsön a világ állapotáról és a játék során a legfontosabb eseményekről (a fentiek szerint).
- Ezen adatok alapján változtassunk meg néhány fontos értéket.
- Döntéseinket ezen értékek feldolgozása vagy értékelése alapján hajtjuk végre.
Például egy ügynöknek több szoba közül választhat egy első személyű lövöldözős térképen. Minden helyiségnek megvan a maga értéke, amely meghatározza, mennyire kívánatos a látogatás. Az AI véletlenszerűen választja ki, hogy melyik helyiségbe menjen az érték alapján. Az ügynök ezután emlékszik, hogy melyik szobában ölték meg, és csökkenti annak értékét (a valószínűségét, hogy visszatér oda). Hasonlóan a fordított helyzethez - ha az ügynök sok ellenfelet elpusztít, akkor a szoba értéke nő.
Markov modell
Mi lenne, ha az összegyűjtött adatokat előrejelzésekhez használnánk fel? Ha egy bizonyos ideig emlékezünk minden helyiségre, amelyben egy játékost látunk, akkor megjósoljuk, hogy a játékos melyik helyiségbe kerülhet. Ha nyomon követjük és rögzítjük a játékos mozgását a szobákban (értékekben), előre jelezhetjük azokat.
Vegyünk három szobát: pirosat, zöldet és kéket. És azok a megfigyelések is, amelyeket a játékmenet nézése közben rögzítettünk:
A megfigyelések száma minden helyiségben majdnem egyenlő – még mindig nem tudjuk, hol készítsünk jó helyet egy lesnek. A statisztikák gyűjtését nehezíti a játékosok újraszületése is, akik egyenletesen jelennek meg a térképen. De a térképen való megjelenés után a következő helyiségre vonatkozó adatok már hasznosak.
Látható, hogy a zöld szoba megfelel a játékosoknak - a legtöbben a piros szobából költöznek oda, akiknek 50%-a ott marad tovább. A kék szoba éppen ellenkezőleg, nem népszerű, szinte senki sem megy oda, és ha igen, nem marad sokáig.
Az adatok azonban valami fontosabbat árulnak el – ha egy játékos egy kék szobában van, a következő szoba, ahol látjuk, piros lesz, nem zöld. Annak ellenére, hogy a zöld szoba népszerűbb, mint a piros szoba, a helyzet megváltozik, ha a játékos a kék szobában van. A következő állapot (azaz az a szoba, ahová a játékos megy) az előző állapottól függ (azaz attól a helyiségtől, amelyben a játékos éppen tartózkodik). Mivel függőségeket tárunk fel, pontosabb előrejelzéseket adunk, mintha egyszerűen egymástól függetlenül számolnánk a megfigyeléseket.
A jövő állapotának előrejelzését egy múltbeli állapot adatai alapján Markov-modellnek, az ilyen példákat (a szobákkal) pedig Markov-láncoknak nevezzük. Mivel a minták az egymást követő állapotok közötti változások valószínűségét jelzik, vizuálisan FSM-ként jelennek meg, minden átmenet körüli valószínűséggel. Korábban az FSM-et használtuk annak a viselkedési állapotnak a reprezentálására, amelyben egy ügynök volt, de ez a fogalom minden állapotra kiterjed, függetlenül attól, hogy az az ügynökhöz kapcsolódik-e vagy sem. Ebben az esetben az állapotok azt a helyiséget jelentik, amelyet az ügynök elfoglal:
Ez egy egyszerű módja az állapotváltozások relatív valószínűségének megjelenítésére, amely lehetővé teszi az MI-nek a következő állapot előrejelzését. Több lépéssel előre is számíthat.
Ha egy játékos a green roomban van, 50% az esélye, hogy ott marad, amikor legközelebb megfigyelik. De mennyi az esélye, hogy még ezután is ott lesz? Nemcsak annak van esélye, hogy a játékos két megfigyelés után a green roomban maradt, hanem arra is, hogy elment és visszatért. Íme az új táblázat az új adatok figyelembevételével:
Ez azt mutatja, hogy annak az esélye, hogy a játékost két megfigyelés után a zöld szobában látja, 51% - 21% annak az esélye, hogy a piros szobából lesz, 5% pedig annak, hogy a játékos meglátogatja a köztük lévő kék szobát, ill. 25%, hogy a játékos nem hagyja el a green room-ot.
A táblázat egyszerűen egy vizuális eszköz – az eljárás csak a valószínűségek szorzását igényli minden lépésnél. Ez azt jelenti, hogy egy figyelmeztetéssel a távoli jövőbe tekinthet: feltételezzük, hogy a helyiségbe való belépés esélye teljes mértékben az aktuális helyiségtől függ. Ezt Markov-tulajdonnak hívják – a jövő állapota csak a jelentől függ. De ez nem száz százalékig pontos. A játékosok más tényezőktől függően módosíthatják a döntéseiket: az egészségi állapot vagy a lőszer mennyisége. Mivel ezeket az értékeket nem rögzítjük, előrejelzéseink kevésbé lesznek pontosak.
N-gramm
Mi a helyzet a harcos játék példájával és a játékos kombinált lépéseinek előrejelzésével? Ugyanaz! De egy állapot vagy esemény helyett megvizsgáljuk a kombinált ütést alkotó teljes sorozatot.
Ennek egyik módja az, hogy minden bemenetet (például Kick, Punch vagy Block) egy pufferben tárol, és a teljes puffert eseményként írja. Tehát a játékos ismételten megnyomja a Kick, Kick, Punch gombot a SuperDeathFist támadás használatához, az AI rendszer tárolja az összes bemenetet egy pufferben, és megjegyzi az egyes lépésekben használt utolsó hármat.
(A félkövér vonalak azt jelzik, amikor a játékos elindítja a SuperDeathFist támadást.)
Az AI minden opciót látni fog, amikor a játékos a Kick-et választja, majd egy másik Kick-et, majd észreveszi, hogy a következő bemenet mindig a Punch. Ez lehetővé teszi az ügynök számára, hogy előre jelezze a SuperDeathFist kombinált mozgását, és ha lehetséges, blokkolja azt.
Ezeket az eseménysorozatokat N-gramoknak nevezzük, ahol N a tárolt elemek száma. Az előző példában ez egy 3 gramm (trigram) volt, ami azt jelenti: az első két bejegyzés a harmadik előrejelzésére szolgál. Ennek megfelelően egy 5 grammosban az első négy bejegyzés előrejelzi az ötödik és így tovább.
A tervezőnek gondosan meg kell választania az N-gramm méretét. Egy kisebb N kevesebb memóriát igényel, de kevesebb előzményt is tárol. Például egy 2 grammos (bigramm) rögzíti a Kick, Kick vagy Kick, Punch, de nem tudja tárolni a rúgást, rúgást, ütést, így az AI nem reagál a SuperDeathFist kombóra.
Másrészt a nagyobb számok több memóriát igényelnek, és az AI-t nehezebb lesz betanítani, mivel sokkal több lehetőség lesz. Ha három lehetséges bemeneted lenne: Kick, Punch vagy Block, és mi egy 10 grammost használnánk, az körülbelül 60 ezer különböző lehetőség lenne.
A bigrammodell egy egyszerű Markov-lánc – minden múltbeli állapot/aktuális állapot pár egy bigram, és az első alapján megjósolhatja a második állapotot. A 3 grammos és nagyobb N-gramok felfoghatók Markov-láncoknak is, ahol az összes elem (kivéve az utolsót az N-grammban) együtt alkotja az első állapotot, az utolsó elem pedig a másodikat. A verekedős játék példája bemutatja a Kick and Kick állapotból a Kick and Punch állapotba való átmenet esélyét. Ha több bemeneti előzmény bejegyzést egyetlen egységként kezelünk, lényegében a bemeneti sorozatot a teljes állapot részévé alakítjuk. Ez megadja nekünk a Markov tulajdonságot, amely lehetővé teszi számunkra, hogy Markov-láncokat használjunk a következő bemenet megjósolására, és kitaláljuk, milyen kombinált lépés lesz a következő.
Következtetés
A mesterséges intelligencia fejlesztésének leggyakoribb eszközeiről, megközelítéseiről beszélgettünk. Azt is megvizsgáltuk, hogy milyen helyzetekben kell őket használni, és hol különösen hasznosak.
Ennek elegendőnek kell lennie a játék AI alapjainak megértéséhez. De természetesen ez nem minden módszer. A kevésbé népszerű, de nem kevésbé hatékony a következők:
- optimalizálási algoritmusok, beleértve a hegymászást, a gradiens süllyedést és a genetikai algoritmusokat
- ellenséges keresési/ütemezési algoritmusok (minimax és alfa-béta metszés)
- osztályozási módszerek (perceptronok, neurális hálózatok és támogató vektorgépek)
- rendszerek az ágensek észlelésének és memóriájának feldolgozására
- A mesterséges intelligencia építészeti megközelítései (hibrid rendszerek, részhalmaz-architektúrák és az AI-rendszerek átfedésének egyéb módjai)
- animációs eszközök (tervezés és mozgáskoordináció)
- teljesítménytényezők (részletesség szintje, bármikor és időszeletelési algoritmusok)
Internetes források a témában:
1. A GameDev.net rendelkezik És .
2. számos előadást és cikket tartalmaz a játékok mesterséges intelligencia fejlesztésével kapcsolatos témák széles skálájáról.
3. a GDC AI Summit témáit tartalmazza, amelyek közül sok ingyenesen elérhető.
4. A honlapon hasznos anyagok is találhatók .
5. Tommy Thompson AI-kutató és játékfejlesztő videókat készít a YouTube-on az AI magyarázatával és tanulmányozásával a kereskedelmi játékokban.
Könyvek a témában:
1. A Game AI Pro könyvsorozat rövid cikkek gyűjteménye, amelyek elmagyarázzák, hogyan valósítson meg bizonyos funkciókat vagy hogyan oldjon meg konkrét problémákat.
2. AI Game Programming Wisdom sorozat a Game AI Pro sorozat elődje. Régebbi módszereket tartalmaz, de szinte mindegyik aktuális még ma is.
3. Az egyik alapszöveg mindenkinek, aki meg akarja érteni a mesterséges intelligencia általános területét. Ez a könyv nem a játékfejlesztésről szól, hanem az AI alapjait tanítja.
Forrás: will.com