Kuidas luua mängu AI: algajate juhend

Sattusin huvitavale materjalile kunstlikust intelligentsist mängudes. Seal on selgitatud põhiasju AI-st lihtsate näidete abil, samuti on sees palju kasulikke tööriistu ja meetodeid selle mugavaks arendamiseks ja projekteerimiseks. Kuidas, kus ja millal neid kasutada — ka see on olemas.

Enamik näiteid on kirjutatud pseudokoodis, seega ei ole sügavad programmeerimisoskused vajalikud. Allpool on 35 lehekülge teksti koos piltide ja GIF-idega, nii et olge valmis.

UPD. Vabandan, kuid oma tõlget sellest artiklist olen juba teinud Habras. PatientZero. Tema variandi lugemine on võimalik. siin, kuid mingi põhjusel jäi artikkel minust mööda (kasutasin otsingut, kuid midagi läks valesti). Kuna kirjutan mänguarendusele pühendatud blogisse, otsustasin jagada oma tõlkevarianti jälgijatele (mõned kohad on mul vormistatud teisiti, mõned — tahtlikult vahele jäetud arendajate soovitusel).

Mis on AI?

Mängu AI keskendub sellele, milliseid toiminguid objekt peaks tegema, tuginedes olukorrale, milles see viibib. Seda nimetatakse sageli «intelligentsete agentide» juhtimiseks, kus agent on mängu isik, transport, bot või mõnikord midagi veel abstraktsemat: terve rühm olendeid või isegi tsivilisatsioon. Igal juhul on see asi, mis peab nägema oma keskkonda, võtma selle põhjal vastu otsuseid ja tegutsema vastavalt sellele. Seda nimetatakse Sense/Think/Act (Tunne/Mõtle/Toimi) tsükliks:

• Tunne: agent leiab või saab teavet keskkonna asjade kohta, mis võivad mõjutada tema käitumist (läheduses olevad ohud, kogutavad esemed, huvitavad kohad uurimiseks).
• Mõtle: agent otsustab, kuidas reageerida (kaalub, kas on piisavalt ohutu esemeid koguda või peaks ta enne võitlema/peituma).
• Toimi: agent täidab eelneva otsuse teostamiseks tegevusi (alustab liikumist vaenlase või eseme suunas).
• …nüüd on olukord muutunud tegelaste tegevuste tõttu, seega kordub tsükkel uute andmete alusel.

Tehisintellekt keskendub enamasti Sense-etapile. Näiteks isesõitvad autod teevad teest pilte, ühendavad need radaritelt ja lidaritelt saadud andmetega ning tõlgendavad neid. Selle tavaliselt teeb masin õpe, mis töötleb sisendandmeid ja annab neile tähenduse, tuues välja semantilist teavet, nagu näiteks "teie ees on veel üks auto 20 jala kaugusel". Need on nii nimetatud klassifitseerimise probleemid.

Mängud ei vaja keerulist süsteemi teabe väljavõtmiseks, kuna enamik andmeid on juba nende lahutamatu osa. Pole vajadust käivitada pildituvastusalgoritme, et tuvastada, kas vaenlane on ette tulles — mäng teab seda juba ja edastab teavet otsuste tegemise protsessis. Seetõttu on Sense-etapi osa sageli palju lihtsam kui Think ja Act.

Mängu AI piirangud

Tehisintellektil on mõned piirangud, mida tuleb järgida:

• Tehisintellekti ei pea eelnevalt treenima nagu masinõppe algoritmi. Pole mõtet kirjutada närvivõrgustikku arendamise ajal, et jälgida kümneid tuhandeid mängijaid ja õppida parimat viisi nende vastu mängimiseks. Miks? Sest mäng ei ole veel välja antud ja mängijaid pole.
• Mäng peab olema lõbus ja väljakutseid pakkuv, seega ei tohiks agentide leida parimat lähenemist inimeste vastu.
• Agendid peavad välja nägema realistlikud, et mängijad tunneksid, nagu mängiks nad tõeliste inimeste vastu. Programm AlphaGo ületas inimese, kuid valitud sammud olid kaugel traditsioonilisest mängu mõistmisest. Kui mäng kopeerib inimvastast, ei tohi seda tunnet olla. Algoritmi tuleb muuta, et see teeks usutavaid otsuseid, mitte ideaalseid.
• Tehisintellekt peab töötama reaalajas. See tähendab, et algoritm ei saa pikka aega monopoliseerida protsessorit otsuste tegemiseks. Isegi 10 millisekundit selleks on liiga kaua, sest enamikule mängudest piisab, et täita kogu töötlemine ja minna järgmisele graafikakaadrile ajavahemikus 16 kuni 33 millisekundit.
• Ideaalne oleks, kui vähemalt osa süsteemist juhitaks andmete abil, et "mitte-kodeerijad" saaksid muudatusi teha ja et parandused toimuksid kiiremini.

Käime läbi AI lähenemised, mis katavad kogu Sense/Think/Act tsüklit.

Aluste otsuste tegemine

Alustame kõige lihtsamast mängust — Pong. Eesmärk: liikuda platvormiga (paddle) nii, et pall põrkuks sellelt tagasi, mitte ei lendaks mööda. See on nagu tennis, kus kaotate, kui ei suuda palli tagasi lüüa. Siin on AI-l suhteliselt kerge ülesanne — otsustada, millises suunas platvormi liikuda.

Tingimuslikud operaatorid

AI jaoks Pongis on kõige ilmsem lahendus — püüda alati platvormi palli alla paigutada.

Lihtne algoritm selle jaoks, kirjutatud pseudokoodis:

iga kaader/uuendus, kui mäng on käimas:
kui pall on platvormi vasakul:
liikuda platform vasakule
kui pall on platvormi paremal:
liikuda platform paremale

Kui platvorm liigub sama kiiresti kui pall, siis on see ideaalne algoritm AI jaoks Pongis. Ei ole vaja asju keerulisemaks ajada, kui andmeid ja võimalikke tegevusi agendi jaoks pole liig palju.

See lähenemine on nii lihtne, et kogu Sense/Think/Act tsükkel on vaevu tuntav. Kuid see on olemas:

• Sense'i osa sisaldub kahes tingimuslikus operaatoris. Mäng teab, kus pall ja platvorm asuvad, seega pöördub AI selle teabe saamiseks mängu poole.
• Think'i osa kuulub samuti kahte tingimuslikku operaatorisse. Need sisaldavad kahte lahendust, mis antud juhul on omavahel välistavad. Tulemuseks valitakse üks kolmest tegevusest — liikuda platvormiga vasakule, liikuda paremale või mitte midagi teha, kui see on juba õigesti paigutatud.
• Act'i osa sisaldub operaatorites Move Paddle Left ja Move Paddle Right. Sõltuvalt mängu disainist võivad need liikuda platvormi kohe või teatud kiirusel.

Selliseid lähenemisi kutsutakse reageerivateks — olemas on lihtne reeglite kogum (antud juhul koodis olevad tingimuslikud operaatorid), mis reageerivad maailma hetkeseisule ja tegutsevad.

Otsustuspuu

Näide mängust Pong on tegelikult vormiline AI kontseptsioon, mida nimetatakse otsustuspuuks. Algoritm läbib selle, et jõuda «leht» — otsus selle kohta, milline tegevus ette võtta.

Tehkem otsustuspuu algoritmi grafika jaoks plokkskeem:

Iga puu osa nimetatakse node (sõlm) — AI kasutab graafiteooriat selliste struktuuride kirjeldamiseks. On kaks tüüpi sõlmi:

• Otsustussõlmed: valik kahe alternatiivi vahel, mis põhineb mingi tingimuse kontrollimisel, kus iga alternatiiv on esitatud eraldi sõlmena.
• Lõpp-sõlmed: tegevus, mida on vaja teostada, esindades lõplikku otsust.

Algoritm algab puu esimese sõlmega („juurega“). Ta kas teeb otsuse, millisesse alamõlgu liikuda, või täidab sõlmes sisalduva tegevuse ning lõpetab selle.

Mis on siis eeliseid, kui otsuste puu teeb sama tööd, mis if-lause eelnevas osas? Siin on ühine süsteem, kus igal otsusel on üksainus tingimus ja kaks võimalikku tulemust. See võimaldab arendajal luua AI andmete põhjal, mis esindavad otsuseid puus, vältides selle kõvaketastamist. Kujutame seda tabelina:

Koodipoolest saate süsteemi stringide lugemiseks. Looge igaühe jaoks sõlm, ühendage otsustusloogika teise veeru alusel ja alamõlged kolmanda ja neljanda veeru alusel. Teil on endiselt vaja programmeerida tingimused ja tegevused, kuid nüüd on mängu struktuur keerukam. Siin lisate täiendavaid otsuseid ja tegevusi ning seejärel konfigureerite kogu AI, lihtsalt muutes puu määratluse tekstifaili. Edasi andsite faili mängudisainerile, kes suudab käitumist muuta ilma mängu uuesti kompileerimata ja koodi muutmata.

Otsuste puud on väga kasulikud, kui need konstrueeritakse automaatselt suure näidiste kogumi põhjal (näiteks kasutades ID3 algoritmi). See teeb neist tõhusad ja kõrge jõudlusega tööriistad olukordade klassifitseerimiseks saadud andmete põhjal. Siiski ületame lihtsa süsteemi agentide tegevuste valimiseks.

Skenaariumid

Olemesime otsuste puu süsteemi, mis kasutas ettevalmistatud tingimusi ja tegevusi. Inimesel, kes disainib AI-d, on võimalik puu korraldada, nagu soovib, kuid ta peab endiselt toetuma koodijale, kes kõik selle programmeeris. Mis siis, kui me võiksime anda disainerile tööriistad oma tingimuste või tegevuste loomiseks?

Et programmeerijal ei oleks vaja kirjutada koodi tingimuste Is Ball Left Of Paddle ja Is Ball Right Of Paddle jaoks, saab ta luua süsteemi, kus disainer kirjutab tingimused nende väärtuste kontrollimiseks. Siis näevad otsuste puu andmed välja nii:

Põhimõtteliselt on see sama, mis esimeses tabelis, kuid lahendustes on oma kood, mis on veidi sarnane if-lause tingimuslikule osale. Koodipoolest loetaks seda teises veerus otsuste sõlmpunktide jaoks, kuid selle asemel, et otsida konkreetset tingimust täitmiseks (Kas pall on paddlest vasakul), hindab see tingimuslikku avaldist ja tagastab vastavalt true või false. See toimub skriptikeele Lua või Angelscript abil. Nende abil saab arendaja mängus olevaid objekte (pall ja paddle) võtta ning luua muutujaid, mis on skriptis kasutatavad (ball.position). Lisaks on skriptikeel lihtsam kui C++. See ei nõua täielikku kompilatsioonifaasi, seega sobib see ideaalselt mängu loogika kiireks kohandamiseks ja võimaldab "koodita" inimestel ise vajalikke funktsioone luua.

Antud näites kasutatakse skriptikeelt ainult tingimuslike avalduste hindamiseks, kuid seda saab kasutada ka tegevuste jaoks. Näiteks andmed Move Paddle Right võivad muutuda skriptitegevuseks (ball.position.x += 10). Seega määratakse tegevus ka skripti kaudu, ilma et oleks vaja programmeerida Move Paddle Right.

Võib minna veel kaugemale ja kirjutada kogu otsustuspuu skriptikeeles. See oleks kood, mis koosneb rangelt programmeeritud (hardcoded) tingimuslikest operaatoritest, kuid nad asuvad välistes skriptifailides, mis tähendab, et neid saab muuta ilma terve programmi ümberkompileerimiseta. Sageli on võimalik skriptifaili muuta otse mängu ajal, et kiiresti testida erinevaid tehisintellekti reaktsioone.

Sündmustele reageerimine

Ülaltoodud näited sobivad ideaalselt Pongile. Need käivitavad pidevalt tsükli Sense/Think/Act ja tegutsevad viimase maailma oleku põhjal. Kuid keerulisemates mängudes peab reageerima eraldi sündmustele, mitte hindama kõike korraga. Pong on sellisel juhul juba halb näide. Valime teise.

Kujutage ette tulistamismängu, kus vaenlased on jõhkrad, kuni märkavad mängijat, pärast mida tegutsevad sõltuvalt oma "spetsialiseerumusest": mõned jooksevad "ründama", teised ründavad kaugelt. See on endiselt põhjalik reageerimissüsteem — "kui mängija on nähtud, siis tee midagi" — kuid seda saab loogiliselt jagada sündmuseks Player Seen (mängija nähtud) ja reaktsiooniks (vali vastus ja teosta see).

See on tagasi meie Sense/Think/Act tsüklisse. Me saame kodeerida Sense-osa, mis iga kaadri lõikes kontrollib, kas AI näeb mängijat. Kui ei — siis ei juhtu midagi, aga kui näeb, siis luuakse sündmus Player Seen. Koodil on eraldi sektsioon, kus on öeldud: „kui sündmus Player Seen toimub, tee “, kus — on vastus, mis on vajalik osadele Think ja Act viitamiseks. Nii seadistate reageerimised sündmusele Player Seen: „rünnaku“ tegelase puhul — ChargeAndAttack, ja snaiperi puhul — HideAndSnipe. Need seosed saab luua andmefailis kiireks redigeerimiseks ilma vajaduseta uuesti kompileerida. Siin võib samuti kasutada skriptikeelt.

Köitvate otsuste vastuvõtmine

Kuigi lihtsad reaktsioonisüsteemid on väga tõhusad, on palju olukordi, kus neid on liiga vähe. Mõnikord tuleb teha erinevaid otsuseid, mis põhinevad sellel, mida agent sel hetkel teeb, kuid seda esitada tingimusena on keeruline. Mõnikord on liiga palju tingimusi, et neid tõhusalt esitada otsuste puus või skriptis. Mõnikord tuleb olukorra muutust eelnevalt hinnata, enne kui järgmise sammu otsustamiseks otsus tehakse. Nende probleemide lahendamiseks on vajalikud keerukamad lähenemisviisid.

Lõppfaasi masin

Lõppfaasi masin ehk FSM (lõplik automaat) on viis öelda, et meie agent asub praegu ühes võimalikus seisundis ning et ta saab ühest seisundist teise liikuda. Selliseid seisundeid on piiratult — seetõttu nimi. Parim näide igapäevaelust on liiklusvalgud. Erinevates kohtades on erinevad valgustusjärjekorrad, kuid põhimõte on sama — iga seisund esindab midagi (seisa, mine jne). Telesaam on alati vaid ühes seisundis igal hetkel ja liigub ühest teiseni lihtsate reeglite alusel.

NPC-dega mängudes on sarnane lugu. Näiteks võtame vahti, kellel on sellised seisundid:

• Patrullimine (Patrolling).
• Rünnak (Attacking).
• Põgenemine (Fleeing).

Ja sellised tingimused, mille alusel tema seisund muutub:

• Kui vaht näeb vaenlast, ründab ta.
• Kui vaht ründab, aga ei näe vaenlast enam, naaseb ta patrullimisele.
• Kui vaht ründab, aga on tõsiselt haavata saanud, põgeneb ta.

Samuti saab kirjutada if-operatööri seisundimuutuja valvuri jaoks ja erinevaid kontrolle: kas läheduses on vaenlane, milline on NPC elutase jne. Lisame veel mõned seisundid:

• Töötus (Idling) — patrullide vahel.
• Otsimine (Searching) — kui märgatud vaenlane on varjunud.
• Abi palumine (Finding Help) — kui vaenlane on märgatud, kuid liiga tugev, et temaga üksi võidelda.

Igaühe valik on piiratud — näiteks valvur ei lähe otsima varjunud vaenlast, kui tal on madal tervis.

Lõppkokkuvõttes võib tohutu "kui"-list olla liiga tülikas, seetõttu tuleks formaliseerida meetod, mis võimaldab meil meeles pidada olekuid ja üleminekuid olekute vahel. <x и y, но не z>, siis <p>Selleks arvestame kõikide olekute ja iga oleku all loetleme kõik üleminekud teistesse olekutesse koos nende jaoks vajalike tingimustega.

See on olekute üleminekutabel — kompleksne viis FSM-i esitlemiseks. Joonistame diagrammi ja saame ülevaate sellest, kuidas NPC käitumine muutub.

Diagramm peegeldab selle agendi otsuste tegemise olemust oleva olukorra põhjal. Lisaks näitab iga nooleke üleminekut olekute vahel, kui tingimus, mille kõrval see asub, on tõene.

Iga värskenduse korral kontrollime agendi praegust olekut, vaatame üleminekutel nimekirja ja kui ülemineku tingimused on täidetud, omandab ta uue oleku. Näiteks kontrollitakse iga kaadriga, kas 10-sekundiline taimer on aegunud, ja kui jah, siis liigub valvur olekust Idling olekusse Patrolling. Samamoodi kontrollib olek Attacking agendi tervist — kui see on madal, siis liigub ta olekusse Fleeing.

See on üleminekute töötlemine olekute vahel, kuid kuidas on lood käitumisega, mis on seotud konkreetsete olekute endiga? Mis puudutab käitumise tegelikku rakendamist konkreetse oleku jaoks, siis tavaliselt on olemas kaks tüüpi "kronk":

• Tegevused, mida me perioodiliselt teostame praeguses olekus.
• Tegevused, mida me teeme, kui liigume ühest olekust teise.

Näited esimese tüübi jaoks. Oleku Patrolling ajal liigub agent iga kaadriga patrullimise marsruudil. Oleku Attacking ajal püüab ta iga kaadriga alustada rünnakut või minna olekusse, kui see on võimalik.

Teise tüübi puhul vaatame üleminekut: "kui vaenlane on nähtav ja vaenlane on liiga tugev, siis minna olekusse Finding Help. Agent peab valima, kuhu minna abi saama, ja salvestama selle teabe, et olek Findings Help teaks, kuhu pöörduda. Kui abi on leitud, naaseb agent tagasi olekusse Attacking. Selle hetkeni tahab ta teavitada liitlast ohust, mistõttu võib tekkida tegevus NotifyFriendOfThreat.

Ja jälle saame sellele süsteemile läheneda Sensori/Mõtle/Käitu tsükli kaudu. Sense väljendub andmetes, mida kasutatakse ülemineku loogikas. Think - üleminekutes, mis on igas olekus saadaval. Ja Act toimub tegevustega, mis toimuvad perioodiliselt oleku sees või üleminekute vahel.

Mõnikord võib üleminekutingimuste pidev küsitlemine olla kulukas. Näiteks, kui iga agent teeb igas kaadris keerulisi arvutusi, et määrata, kas nad näevad vaenlasi ja mõista, kas on võimalik liikuda olekust Patrolling olekusse Attacking — kulutab see palju protsessori aega.

Olulisi maailma olekumuutusi saab käsitleda sündmustena, mida töödeldakse nende ilmumise hetkel. Selle asemel, et FSM kontrolliks iga kaader ülemineku tingimust, "kas mu agent näeb mängijat?", saab seadistada eraldi süsteemi, et teostada kontrolle vähem tihti (näiteks 5 korda sekundis). Tulemuseks on Player Seen, kui kontroll läheb läbi.

See edastatakse FSM-ile, mis peab nüüd liikuma olekusse Player Seen sündmus on saadud ja reageerima vastavalt. Lõplik käitumine on sama, välja arvatud peaaegu märkamatuna viivituse enne vastust. Kuid jõudlus on paranenud, sest osa Sense'ist on eraldatud eraldi programmiosasse.

Hierarhiline lõppolekumasin

Siiski ei ole suurte FSM-ide käsitlemine alati mugav. Kui soovime rünnaku olekut laiendada, asendades selle eraldi MeleeAttacking (lähiều) ja RangedAttacking (kaugtegevus), peame muutma üleminekud kõigist teistest olukordadest, mis viivad olekusse Attacking (praegused ja tulevased).

Olete kindlasti märganud, et meie näites on palju dubleeritud üleminekuid. Enamik üleminekuid Idling (ooterežiim) ja Patrolling (patrullimine) olekute vahel on identsed. Oleks hea mitte korduda, eriti kui lisame rohkem sarnaseid olekuid. On mõistlik grupeerida Idling ja Patrolling ühise sildiga „mittesõjaline”, kus on ainult üks ühine üleminekute komplekt sõjaliste seisundite juurde. Kui esitame selle sildi olekuna, siis muutuvad Idling ja Patrolling alamolekuteks. Näide eraldi üleminekute tabeli kasutamisest uue mittesõjalise alamoleku jaoks:

Põhiolekud:


Mõlemad olekud on lahinguväljast väljas:


Ja diagrammi kujul:

See on sama süsteem, kuid uue mittesõjalise olekuga, mis sisaldab Idling ja Patrolling olekuid. Iga olek, millel on alamolekudega FSM (lõppautomaat), (ja need alamolekud sisaldavad omakorda oma FSM-e — ja nii edasi, kui palju vaja), loob meile Hierarchical Finite State Machine ehk HFSM (hierarhiline lõppautomaat). Mittesõjalise oleku grupeerimise kaudu lõikame me välja hulga üleliigseid üleminekuid. Sama saame teha mistahes uute olekute puhul, millel on ühised üleminekud. Näiteks, kui tulevikus laiendame ründamise olekut MeleeAttacking (lähedalt ründamine) ja MissileAttacking (projektilli ründamine) olekute juurde, siis need muutuvad alamolekuteks, mis üksteise vahel üleminevad sõltuvalt vahemaa kaugusest vaenlase juurde ja laskemoona olemasolust. Lõppkokkuvõttes saab keerulisi käitumismudeleid ja allmudeleid esitada minimaalse dubleerimisega.

Käitumiste puu

HFSM-i kaudu luuakse keerulisi käitumiste kombinatsioone lihtsalt. Siiski on üks väike raskus, et ülemisreeglite näol on otsuste tegemine tihedalt seotud praeguse olekuga. Paljudes mängudes on see just see, mida vajate. Ja olekute hierarhia hoolikas kasutamine võib vähendada üleminekute kordusi. Kuid mõnikord on vaja reegleid, mis töötavad sõltumatult olekust, milles te olete, või mis kehtivad peaaegu igas olekus. Näiteks, kui agendi tervis langeb 25%-ni, tahate, et ta jooksuks, olenemata sellest, kas ta on lahingus, tegutseb või vestleb — peate seda tingimust lisama igasse olekusse. Kui teie disainer hiljem soovib madala tervise piiri muuta 25%-lt 10%-le, tuleb sellega taas tegeleda.

Ideaalis on vajalik süsteem, kus otsuseid "millises olekus olla" tehakse väljaspool neid olekuid, et muuta vaid ühes kohas ja mitte puutuda üleminekutingimusi. Siin tulevad mängu käitumispuud.

On mitu võimalust nende rakendamiseks, kuid nende põhiolemus on umbes sama ja sarnaneb otsuste puudega: algoritm algab "juure" sõlmest, kus puud on sõlmed, mis esindavad kas otsuseid või tegevusi. Tõsi, siin on mõned peamised erinevused:

• Nüüd sõlmed tagastavad ühe kolmest väärtusest: Succeeded (kui töö on lõpetatud), Failed (kui seda ei saa käivitada) või Running (kui see on endiselt käimas ja lõplikku tulemust pole).
• Otsuse sõlmi pole enam kahe alternatiivi vahel valimiseks. Nende asemel on Decorator sõlmed, millel on üks tütarsõlm. Kui nad Succeed, siis teevad nad oma ainukese tütarsõlme.
• Tegevusi täitvad sõlmed tagastavad väärtuse Running, et esindada käimasolevaid tegevusi.

Seda väikest sõlmede kogumit saab kombineerida, et luua palju keerukaid käitumismudeleid. Kujutame ette HFSM valvurit eelnevas näites käitumispuu kujul:

Selle struktuuriga ei tohiks olla selget üleminekut Idling/Patrolling olekust ründamise või mõne muu oleku juurde. Kui vaenlane on nähtav ja tegelase elu on madal, peatub täitmine Fleeing sõlmel, sõltumata sellest, millisest sõlmest ta varem täitis — Patrolling, Idling, Attacking või mõni muu.

Käitumispuud on keerulised — on palju viise nende koostamiseks, ja õige kombinatsiooni leidmine dekoratoritest ja komposiit-sõlmest võib olla keeruline. Samuti on küsimusi, kui tihti puud kontrollida — kas tahame läbida seda iga osa või ainult siis, kui mõni tingimus on muutunud? Kuidas hoida sõlmedega seotud olekut — kuidas teada, kas oleme olnud Idling olekus 10 sekundit või kuidas teada, millised sõlmed viimasel korral täideti, et õiget järjestust õigesti töödelda?

Sel põhjusel on olemas palju rakendusi. Näiteks mõnes süsteemis asendavad dekoratori sõlmed sisseehitatud dekoratoreid. Need hindavad puud uuesti dekoratori tingimuste muutumisel, aitavad liituda sõlmedega ja tagavad perioodilised värskendused.

Kasumipõhine süsteem

Mõnedel mängudel on palju erinevaid mehhanisme. Soovitav on, et need saaksid kõik kasu lihtsatest ja üldistest üleminekureeglitest, kuid mitte tingimata täieliku käitumispuu kujul. Selle asemel, et omada selget valikute kogumit või võimalike tegevuste puu, on lihtsam õppida kõik tegevused ja valida hetkel sobivaim.

Kasulikku põhine süsteem aitab siin. See on süsteem, kus agendil on palju tegevusi ja ta valib ise, milline neist teostada, tuginedes igaühe suhtelisele kasulikkusele. Kus kasulikkus on meelevaldne mõõt, kui oluline või soovitav on selle tegevuse teostamine agendi jaoks.

Käitumise kasulikkust, mis põhineb hetke olekul ja keskkonnal, saab agent igal ajal kontrollida ja valida sobivama teise oleku. See sarnaneb FSM-iga, välja arvatud sellega, et üleminekud määratakse iga potentsiaalse oleku hindamise kaudu, sealhulgas praeguse. Pange tähele, et valime ülemineku jaoks kõige kasulikuma tegevuse (või jääme paigale, kui oleme selle juba teinud). Suurema mitmekesisuse nimel võib see olla kaalutud, kuid juhuslik valik väikese nimekirja hulgast.

Süsteem määrab juhuslikud kasulikkuse väärtuste vahemikud - näiteks, alates 0 (täiesti soovimatu) kuni 100 (täielikult soovitav). Igal tegevusel on mitmed parameetrid, mis mõjutavad selle väärtuse arvutamist. Tagasi tulles meie näite juurde valvekoerast:

Üleminekud tegevuste vahel on ebamugavad - iga olek võib järgida mis tahes muud. Tegevuste prioriteedid on tagastatud kasulikkuse väärtustes. Kui vaenlane on nähtav ja see vaenlane on tugev, samas kui tegelase elu on madal, siis nii Põgenemine kui ka Abiotsimine tagastavad kõrged mitte-null väärtused. Sellega arvestades on Abiotsimine alati kõrgem. Samuti ei tagasta mitte-sõjalised tegevused kunagi rohkem kui 50, seega on nad alati madalamad kui sõjalised. Seda tuleb arvestada tegevuste loomisel ja nende kasulikkuse arvutamisel.

Meie näites tagastavad toimingud kas fikseeritud konstantsed väärtused või ühe kahest fikseeritud väärtusest. Realistlikum süsteem eeldab, et tagastatakse hinnang pidevast väärtuste vahemikust. Näiteks toiming Fleeing tagastab kõrgemaid utiliteedi väärtusi, kui agendi tervis on madal, samas kui toiming Attacking tagastab madalamaid väärtusi, kui vaenlane on liiga tugev. Seetõttu on toimingul Fleeing alati prioriteet toimingu Attacking ees olukordades, kus agent tunneb, et tal ei ole piisavalt tervist, et vastasega võidelda. See võimaldab muuta tegevuste prioriteete, tuginedes mis tahes hulgale kriteeriumidele, muutes sellise lähenemise paindlikumaks ja varieeruvamaks kui tegevuste puu või FSM.

Igal toimingul on palju tingimusi programmi arvutamiseks. Need võib kirjutada skriptikeeles või seeria matemaatilisi valemeid. The Sims'is, mis modelleerib karakteri igapäevast rutiini, lisatakse täiendav arvutustasand — agent saab rea 'motivatsioone', mis mõjutavad utiliteedi hindamisi. Kui karakter on näljane, siis aja jooksul muutub ta veelgi näljasemaks ja toime EatFood utiliteedi tulemus kasvab, kuni karakter täidab selle, vähendades oma nälga ja tuues EatFood väärtuse tagasi nulli.

Tegevuste valimise idee hindamissüsteemi põhjal on üsna lihtne, seetõttu saab Utility-based süsteemi kasutada osana AI otsustusprotsessidest, mitte nende täielikuks asendamiseks. Otsustuspuu võib küsida kahe tütarnõlva utiliteedi hindamist ja valida kõrgema. Samamoodi võib käitumispuul olla koostisosa sõlm Utility, et hinnata tegevuste utiliteeti, et otsustada, millist tütarüksust täita.

Liikumine ja navigeerimine

Eelnevates näidetes oli meil platvorm, mida liikusime vasakule või paremale, ja valve, kes patrullis või ründas. Kuid kuidas me täpselt töötame agendi liikumise üle teatud aja jooksul? Kuidas me määrame kiirus, kuidas me väldime takistusi, ja kuidas me plaanime marsruuti, kui sihtkohta jõudmine on keerulisem kui lihtsalt sirgjoonelise liikumisega? Vaatame seda lähemalt.

Haldamine

Alguses oletame, et igal agendil on kiirus, mis sisaldab tema liikumise kiirus ja suund. Seda saab mõõta meetrites sekundis, kilomeetrites tunnis, pikslites sekundis jne. Tuletades meelde sensoorsete/mõtlemise/tegevuse tsüklit, võime ette kujutada, et osa mõttetegevusest valib kiirus ja osa tegevusest rakendab seda kiirus agenti. Tüüpiliselt mängudes on füüsikasüsteem, mis teeb selle töö teie eest, uurides iga objekti kiirus ja reguleerides seda. Seetõttu võib tehisintellekti jätta ühe ülesande — otsustada, kui kiiresti agent peaks liikuma. Kui on teada, kuhu agent peab jõudma, tuleb ta liikuda õiges suunas seatud kiirusel. Väga lihtne võrrand:

desired_travel = sihtkoha_asukoht – agendi_asukoht

Kujutage ette 2D maailma. Agent asub punktis (-2,-2), sihtkoht kusagil kirdes punktis (30, 20), ja vajalik tee, et agent sinna jõuaks, on (32, 22). Oletame, et need positsioonid on mõõdetud meetrites — kui võtame agendi kiirusena 5 meetrit sekundis, siis me skaleerime oma liikumisvektori ja saame kiirusena umbes (4.12, 2.83). Nende parameetritega jõuaks agent sihtpunkti peaaegu 8 sekundiga.

Väärtusi saab igal ajal ümber arvutada. Kui agent oli poolel teel sihtkohta, oleks liikumine olnud poole pikkusest, kuid kuna agendi maksimaalne kiirus on 5 m/s (nagu me eespool otsustasime), jääb kiirus samaks. See töötab ka liikuvate sihtmärkide puhul, võimaldades agentidel teha väikeseid kohandusi nende liikudes.

Aga me tahame rohkem variatiivsust — näiteks aeglaselt suurendada kiirus, et simuleerida tegelast, kes liigub seismisest jooksmiseks. Sama saab teha ka enne peatamist. Need funktsioonid on tuntud kui steering behaviours, igaühel neist on spetsiifilised nimed: Seek (otsimine), Flee (põgenemine), Arrival (saabumine) jne. Idee on selline, et kiirusese kiirusel saab rakendada kiirusjõude, tuginedes agendi asukoha ja hetke kiiruse ning sihtkoha võrdlemisele, et kasutada erinevaid liikumismeetodeid sihtkohta jõudmiseks.

Iga käitumine on veidi erineva eesmärgiga. Seek ja Arrival on viisid, kuidas suunata agent sihtkohta. Obstacle Avoidance (takistuste vältimine) ja Separation (eraldi hoidmine) kohandavad agendi liikumist, et mööda minna takistustest sihtkoha poole. Alignment (kooskõlastamine) ja Cohesion (sidusus) hoiavad agendid liikumas koos. Erinevaid steering behaviors (suunamisvõtteid) saab summida üheks teepunktiks, arvesse võttes kõiki tegureid. Agent kasutab Arrival, Separation ja Obstacle Avoidance käitumisi, et hoida eemale seintest ja teistest agentidest. See lähenemine töötab hästi avatud linnades, kus pole liigseid detaile.

Raskemates tingimustes töötab erinevate käitumiste kokku liitmine kehvemini — näiteks võib agent jääda seina kinni Arrival ja Obstacle Avoidance konfliktide tõttu. Seetõttu tuleb kaaluda keerulisemaid variante kui lihtsalt kõigi väärtuste kokku liitmine. Üks viis on: mitte liita iga käitumise tulemusi, vaid uurida liikuvusi erinevates suundades ja valida parim variant.

Kuid keerulises keskkonnas, kus on ummikud ja suunad valida, vajame midagi veelgi arenenumat.

Teepunktide leidmine

Steering behaviours sobivad suurepäraselt lihtsaks liikumiseks avatud aladel (jalgpalliväljak või areen), kus sihtpunkti A kuni B jõudmine on sirge tee väheste kõrvalekaldumisega takistustest mööda. Keerukamate marsruutide jaoks vajame pathfinding'ut (teepunktide leidmine), mis on viis maailma uurimiseks ja selle kaudu marsruudi valimiseks.

Lihtsaim viis on panna igasse ruutu, mis asub agendi kõrval, võrk ja hinnata, millistes neist on lubatud liikuda. Kui mõni neist on sihtkoht, järgige sealt teed, liikudes igast ruudust tagasi eelmisse, kuni jõuate alguspunkti. Just see on marsruut. Vastasel juhul korrake protsessi lähimates teiste ruutide puhul, kuni leiate sihtkoha või ruudud saavad otsa (see tähendab, et pole võimalikku teed). Seda tuntakse ametlikult kui laieesmärgi otsingu (Breadth-First Search ehk BFS) algoritmina. Igal sammul vaatab see igas suunas (seetõttu „laius”). Otsinguruum sarnaneb lainefrontiga, mis liigub kuni jõuab soovitud kohta — otsingu valdkond laieneb igal sammul, kuni see hõlmab lõpp-punkti, pärast mida saab jälgida teed algusesse.

Tulemuseks on ruutide loetelu, mille kaudu formaalitakse vajalik marsruut. See on tee (siit tuleb ka termin pathfinding) — loetelu kohtadest, mida agent külastab, liikudes sihtpunkti suunas.

Arvestades, et me teame iga ruudu asukohta maailmas, saame kasutada juhtimisprotseduure (steering behaviours), et liikuda mööda teed — sõlmedelt 1 sõlmesse 2, seejärel sõlmedelt 2 sõlmesse 3 ja nii edasi. Lihtsaim variant on suunduda järgmise ruudu keskpunkti, kuid veel parem on peatuda praeguse ruudu ja järgmise vahepeal. Nii saab agent teravaid pöördeid sujuvamalt läbida.

BFS-algoritmil on ka puudused — see uurib sama palju ruute „vale” suunas kui „õige” suunas. Siin tuleb mängu keerulisem algoritm nimega A* (A star). See töötab sarnaselt, kuid selle asemel, et pimesi uurida naaberruute (järelnaabrite, seejärel naabrite naabrite jne), kogub see sõlmed loendisse ja sorteerib need nii, et järgmine uuritav sõlm on alati see, mis viib lühima marsruudini. Sõlmed sorteeritakse hüpoteetilise marsruudi „kulude” põhjal, et jõuda soovitud ruutu (kaasa arvatud kõik liikumise kulud) ja hinnstatusse, kui kaugel see ruut on sihtkohast (suunates otsingu õiges suunas).

Selles näites uurib agent ühte ruutu korraga, valides iga kord naabruse, mis tundub kõige rohkem lootustandev. Saadud tee on sama, mis BFS-il, kuid protsessi käigus on arvestatud vähemate ruutudega — see on mängu jõudluse jaoks märkimisväärne.

Liikumine ilma ruudustikuta

Kuid enamik mänge ei ole ruudustikus, ja sageli ei saa seda realistlikkuse kahjustamata luua. Kompromisse on vajalikud. Kui suured peaksid ruudud olema? Liialt suured — ja nad ei suuda korralikult kujutada väikseid koridore või pöördeid, liiga väikesed — ruute on otsimiseks liiga palju, mis lõpuks võtab palju aega.

Esimene asi, mida mõista — ruudustik annab meile seotud sõlmede graafiku. A* ja BFS algoritmid töötavad tegelikult graafikutel ja ei hooli meie ruudustikust. Me võiksime paigutada sõlmed igal pool mängumaailmas: kui kahe ühendatud sõlme vahel on side, samuti algus- ja lõpupunkti vahel ning vähemalt ühe sõlmega — töötab algoritm endiselt sama hästi kui varem. Seda nimetatakse sageli teepunktide süsteemiks, kuna iga sõlm esindab tähenduslikku positsiooni maailmas, mis võib olla osa paljusid hüpoteetilisi teevariatsioone.

Näide 1: sõlm igas ruudis. Otsing algab sõlmest, kus agent asub, ja lõppeb vajaliku ruudu sõlmes.

Näide 2: väiksem sõlmede komplekt (teepunktid). Otsing algab ruudust, kus agent asub, liigub läbi vajalike sõlmede ja jätkub siis sihtkohta.

See on üsna paindlik ja võimas süsteem. Kuid teepunktide asukohtade otsimisel on ettevaatlikkust, muidu ei pruugi agenid lihtsalt lähima punkti näha ja ei saa oma teed alustada. Oleks lihtsam, kui saaksime automaatselt teepunkte paigutada maailmaga seotud geomeetria põhjal.

Siia tuleb navigeerimisvõrk või navmesh (navigeerimissegu). See on tavaliselt 2D- võrk kolmnurgadest, mis asetatakse maailma geomeetriale — igal pool, kus agent võib liikuda. Iga kolmnurk võrgus muutub graafikus sõlmeks ja tal on kuni kolm külgnevat kolmnurka, mis muutuvad graafikus naabrussõlmedeks.

See pilt on näide Unity mootorist — see analüüsis maailma geomeetriat ja lõi navmesh'i (ekraanipildil helesinise värviga). Iga polügoon navmesh'is on ala, millel agent võib seista või liikuda ühest polügoonist teise. Antud näites on polügoonid väiksemad kui korrused, mille peal nad asuvad — see on tehtud agendi suuruste arvestamiseks, mis ulatuvad tema nominaalsest asukohast välja.

Saame otsida marsruuti läbi selle võrgu, kasutades jälle A* algoritmi. See annab meile praktiliselt ideaalse marsruudi maailmas, mis arvestab kogu geomeetriat ning ei vaja liigseid sõlmi ja teetäppetähti.

Pathfinding on liiga ulatuslik teema, millest ei piisa ühest artikli jaost. Kui soovite seda põhjalikumalt uurida, aitab see Amit Patel'i veebisait.

Planeerimine

Oleme pathfinding'uga veendunud, et mõnikord ei piisa lihtsalt suuna valimisest ja liikumisest — me peame valima marsruudi ja tegema mitu pöördet, et jõuda sihtkohta. Saame selle idee kokku võtta: eesmärgi saavutamine ei ole lihtsalt järgmine samm, vaid pigem tervikjärjekord, kus mõnikord peame ette vaatama paar sammu, et teada, kuidas esimene samm peaks olema. Seda nimetatakse planeerimiseks. Pathfinding'ut võib pidada üheks mitmest planeerimise täienduseks. Meie Sense/Think/Act tsükli vaatenurgast on see koht, kus osa Think planeerib tulevikus mitmeid osi Act.

Vaatame näidet kaardimängust Magic: The Gathering. Me liigume esimesena selliste kaartidega käes:

• Swamp — annab 1 musta mannat (maa kaart).
• Forest — annab 1 roheline mannat (maa kaart).
• Fugitive Wizard — nõuab 1 sinist mannat, et seda võtta.
• Elvish Mystic — nõuab 1 roheline mannat, et seda võtta.

Jätame ülejäänud kolm kaarti kõrvale, et oleks lihtsam. Reeglite kohaselt on mängijal lubatud mängida 1 maa kaart iga käigu ajal, ta võib selle kaardi "tapada", et saada mannat ning seejärel kasutada loitsu (sealhulgas olendi toomist) saadud mana koguse alusel. Antud olukorras teab inim mängija, et peab mängima Forest'i, "tapama" 1 roheline mannat ja seejärel kutsuma Elvish Mystic'i. Kuid kuidas sellest teada saada mängu AI-le?

Lihtne planeerimine

Triviaalne lähenemine on proovida iga tegevust järjest, kuni enam sobivaid ei jää. Kaardile vaadates näeb tehisintellekt, et ta saab mängida Swampi. Ja ta mängib selle. Kas selle käigu jooksul on teisi tegevusi? Ta ei saa kutsuda ei Elvish Mysticit ega Fugitive Wizardit, kuna nende mängimiseks on vajalik vastavalt roheline ja sinine mana, aga Swamp toob ainult musta mana. Ja ta ei saa juba mängida Forestit, kuna on juba mänginud Swampi. Seega mängib mängu tehisintellekt reeglite järgi, kuid teeb seda halvasti. Seda oleks võimalik parandada.

Planeerimine võib leida tegevuste loendi, mis viivad mängu soovitud olekusse. Nii nagu iga ruut teel omas naabreid (pathfinding'e puhul), on igal plaanis tegevusel samuti naabrid või järglased. Saame otsida neid tegevusi ja edasisi tegevusi, kuni saavutame soovitud oleku.

Meie näites on soovitud tulemus „kutset teha, kui see on võimalik“. Käigu alguses näeme ainult kahte võimalikku tegevust, mis on mängureeglite poolt lubatud:

1. Mängi Swamp (tulemus: Swamp mängus)
2. Mängi Forest (tulemus: Forest mängus)

Iga vastuvõetud tegevus võib viia edasi uute tegevusteni ja sulgeda teisi, jälle mängureeglitest lähtuvalt. Kujutage ette, et me mängisime Swampi – see eemaldab Swampi järgmiseks sammuks (oleme selle juba mänginud), see eemaldab ka Foresti (sest reeglite järgi võib ühe ringi jooksul mängida vaid ühe maakaardi). Pärast seda lisab tehisintellekt järgmiseks sammuks – 1 musta mana saamine, kuna muid võimalusi pole. Kui ta edasi läheb ja valib Tap the Swamp, siis saab ta 1 musta mana ja ei saa sellega midagi teha.

1. Mängi Swamp (tulemus: Swamp mängus)
1.1 „Täpida“ Swamp (tulemus: Swamp on „täpitud“, +1 musta mana)
Ei ole saadaval tegevusi – LÕPP
2. Mängi Forest (tulemus: Forest mängus)

Tegevuste loend on liiga lühike, oleme ummikus. Korrake protsessi järgmise tegevuse jaoks. Mängime Foresti, avame tegevuse „saada 1 roheline mana“, mis omakorda avab kolmanda tegevuse – Elvish Mystici kutse.

1. Mängi Swamp (tulemus: Swamp mängus)
1.1 „Täpida“ Swamp (tulemus: Swamp on „täpitud“, +1 musta mana)
Ei ole saadaval tegevusi – LÕPP
2. Mängi Forest (tulemus: Forest mängus)
2.1 „Täpida“ Forest (tulemus: Forest on „täpitud“, +1 roheline mana)
2.1.1 Kutsuda Elvish Mystic (tulemus: Elvish Mystic mängus, -1 roheline mana)
Ei ole saadaval tegevusi – LÕPP

Lõpuks oleme uurinud kõiki võimalikke tegevusi ja leidnud plaani, mis kutsub esile olendi.

See on väga lihtsustatud näide. Soovitav on valida parim võimalik plaan, mitte lihtsalt selline, mis vastab mingitele kriteeriumitele. Üldiselt saab potentsiaalseid plaane hinnata lõpptulemuse või nende täitmise koguhinna alusel. Mängides maakaardiga saab koguda 1 punkti ning looma kutsumisega 3 punkti. Swampi mängimine oleks plaan, mis annab 1 punkti. Foresti mängimine → Foresti sisselülitamine → Elvish Mystici kutsumine annab aga kohe 4 punkti.

Nii töötab planeerimine Magic: The Gathering'is, kuid sama loogikat rakendatakse ka muudesse olukordadesse. Näiteks, nii saate liikuda nupuga, et teha ruumi elevandi käiguks šahhis. Või peituda seina taha, et XCOM-is ohutult tulistada. Ühesõnaga, saad aru.

Parandatud planeerimine

Mõnikord on liiga palju potentsiaalseid tegusid, et kaaluda iga võimalikke variante. Naaseme Magic: The Gathering'i näite juurde: oletame, et mängus on teil mitmeid maakaarte ja olendeid – võimalike käikude arv võib ulatuda kümnete kaupa. Probleemi lahendamiseks on mitu meetodit.

Esimene viis on backwards chaining (tagasiulatuv ahel). Selle asemel, et kõiki kombinatsioone läbi vaadata, on parem alustada lõpptulemusest ja proovida leida otsetee. Selle asemel, et liikuda puu juurest kindla leheni, liigume vastassuunas – lehest juure juurde. See meetod on lihtsam ja kiirem.

Kui vastasel on 1 elupunkt, saab leida plaani „teha 1 või rohkem kahju“. Selle saavutamiseks tuleb täita mitmeid tingimusi:

1. Kahju võib teha loits – see peab olema käes.
2. Loitsu mängimiseks on vajalik mana.
3. Mana saamiseks tuleb mängida maakaart.
4. Maakaardi mängimiseks peab see olema käes.

Teine võimalus on best-first search (parim esimene otsing). Selle asemel, et kõiki teid uurida, valime kõige sobivama. Sageli annab see meetod optimaalse plaani, ilma et peaksite otsinguteks ülemääraselt vaeva nägema. A* on parima esimese otsingu vorm – uurides kõige lootustandvamaid marsruute alates algusest, suudab see juba leida parima tee, ilma et peaks kontrollima teisi variante.

Huvitav ja aina populaarsem variant parima esmaklassilise otsingu jaoks on Monte Carlo puuotsing. Selle asemel, et ära arvata, millised plaanid on paremad iga järgmise tegevuse valimisel, valib algoritm iga sammu korral juhuslikke järgijaid, kuni jõuab lõpuni (kui plaan viib võiduni või kaotusele). Seejärel kasutatakse lõpptulemust selleks, et tõsta või langetada varasemaid valikute "kaalu" hindamisi. Korrates seda protsessi mitu korda järjest, annab algoritm hea hinnangu, milline järgmine samm on parem, isegi kui olukord muutub (kui vastane astub samme, et mängijat takistada).

Mängude planeerimisest rääkides ei saa me mööda minna sihitud tegevuste planeerimist ehk GOAP (Goal-Oriented Action Planning). See on laialdaselt kasutatav ja arutletud meetod, kuid peale mõnede eristavate detailide on see sisuliselt tagasipöördumise ahela meetod, millest me varem rääkisime. Kui ülesanne on "mängija hävitamine" ja mängija on varjupaiga taga, võib plaan olla järgmine: hävitada granaadiga → võtta see üles → visata.

Tavaliselt on mitmeid eesmärke, igal neist on oma prioriteet. Kui kõige kõrgema prioriteediga eesmärki ei saa täita (ühegi tegevuste kombinatsioon ei loo plaani "hävitada mängija", kuna mängija ei ole nähtav), siis tagastab tehisintellekt madalama prioriteedi eesmärkide juurde.

Koolitus ja kohandamine

Oleme juba rääkinud, et mängu tehisintellekt ei kasuta tavaliselt masinõpet, kuna see ei sobi reaalajas agente juhtimiseks. Kuid see ei tähenda, et sealt ei saaks midagi laenata. Me tahame sellist vastast tulistamismängus, kellelt on võimalik õppida. Näiteks teada saada parimatest kohtadest kaardil. Või vastast kaklusmängus, kes blokeerib mängija tihti kasutatavaid kombo-käike, motiveerides kasutama teisi. Nii et masinõpe sellistes olukordades võib olla üsna kasulik.

Statistika ja tõenäosused

Enne kui läheme keerukate näidete juurde, vaatame, kui kaugele me saame minna, tehes mõned lihtsad mõõtmised ja kasutades neid otsuste tegemiseks. Näiteks, reaalaja strateegia — kuidas me saame kindlaks teha, kas mängija suudab alustada rünnakut mängu esimestel minutitel ja millist kaitset selle vastu valmistada? Saame uurida mängija varasemat kogemust, et mõista, milline võib olla tulevane reaktsioon. Alustuseks meil pole selliseid algandmeid, kuid saame need koguda — iga kord, kui AI mängib inimese vastu, saab ta salvestada esimese rünnaku aja. Pärast mitmeid sessioone saame keskmise aja, mille jooksul mängija tulevikus ründab.

Keskväärtustel on probleem: kui mängija on 20 korda 'rushinud' ja 20 korda mänginud aeglaselt, siis vajalikud väärtused jäävad kuskil keskele, mis ei paku meile midagi kasulikku. Üks lahendustest on sisendandmete piiramine — võime arvesse võtta viimased 20 juhtumit.

Sarnast lähenemist kasutatakse teatud toimingute tõenäosuse hindamisel, eeldades, et mängija varasemad eelistused jäävad tulevikus samaks. Kui mängija ründab meid viis korda tulepalliga, kaks korda välguga ja ühe korra lähivõitluses, on ilmne, et ta eelistab tulepalli. Ekstrapoleerime ja näeme erineva relva kasutamise tõenäosust: tulepall=62,5%, välk=25% ja lähivõitlus=12,5%. Meie mängu AI peab valmistuma tule eest kaitsmiseks.

Veel üks huvitav meetod on kasutada Naive Bayes Classifier'i (naiivne bayeslik klassifikaator) suurte sisendandmete koguste uurimiseks ja olukorra klassifitseerimiseks, et AI reageeriks õigesti. Bayeslikud klassifikaatorid on kõige tuntumad selle poolest, kuidas neid kasutatakse e-kirjade rämpsposti filtrites. Seal uurivad nad sõnu, võrdlevad neid sellega, kus need sõnad varem esinesid (rämpspostis või mitte), ja teevad järeldusi saabuvate kirjade kohta. Saame teha sama isegi väiksema sisendandmete hulgaga. Tuginedes kõikidele kasulikule teabele, mida AI näeb (nt millised vaenlase üksused on loodud, milliseid loitse nad kasutavad või milliseid tehnoloogiaid on nad uurinud) ja lõpptulemusele (sõda või rahu, 'rushida' või kaitsta jne) — valime vajaliku AI käitumise.

Kõik need õppimise meetodid on piisavad, kuid oleks soovitatav neid kasutada testimise andmete põhjal. Tehisintellekt õpib kohanduma erinevate strateegiatega, mida teie mängijad kasutasid. Tehisintellekt, mis kohandub mängijaga pärast väljaandmist, võib osutuda liiga ennustatavaks või vastupidi, liiga keeruliseks võidetavaks.

Kohandamine väärtuste põhjal

Arvestades meie mängumaailma sisu ja reegleid, saame muuta nende otsuste tegemiseks mõjutavaid väärtuste komplekte, mitte lihtsalt kasutada sisendandmeid. Teeme seda järgmiselt:

• Las tehisintellekt kogub andmeid mängu ajal maailma olekute ja võtmeeventside kohta (nagu on varem mainitud).
• Muudame mõningaid olulisi väärtusi (value) nende andmete põhjal.
• Rakendame oma otsuseid, mis põhinevad nende väärtuste töötlemisel või hindamisel.

Näiteks, kui agentil on mitu tuba valimiseks esimese isiku tulistamismängu kaardil. Igal toal on oma väärtus, mis määrab, kui soovitav see külastamiseks on. Tehisintellekt valib juhuslikult, millisesse tuppa minna, põhinedes väärtusele. Siis mäletab agent, millises toas ta hävines, ja vähendab selle väärtust (tõenäosus, et ta sinna naaseb). Vastupidisel juhul — kui agent hävib palju vastaseid, siis toaga seotud väärtus suureneb.

Markovi mudel

Mis siis, kui me kasutame kogutud andmeid ennustamiseks? Kui me mäletame iga tuba, kus mängijat teatud aja jooksul nägime, suudame ennustada, millisesse tuppa mängija võib minna. Jälgides ja registreerides mängija liikumisi tubade vahel (values), saame neid ennustada.

Võtame kolm tuba: punane, roheline ja sinine. Ja ka tähelepanekud, mida oleme kogunud mängu sessiooni vaatamisel:

Iga toa jälgimise arv on peaaegu sama — kus on hea koha jaoks varitseda, ei tea me siiani. Statistika kogumine on samuti keeruline, kuna mängijad ilmuvad kaardil ühtlaselt. Kuid järgmise toa andmed, kuhu nad sisenevad pärast kaardile ilmumist, on juba kasulikud.

Näha on, et roheline tuba meeldib mängijatele — enamik inimesi punasest liigub sinna, kellest 50% jääb sinna edasi. Sinine tuba aga ei naudi populaarsust, sinna peaaegu ei minda ja kui minnakse, siis ei viibita seal kaua.

Kuid andmed räägivad meile midagi tõeliselt olulist — kui mängija viibib sinises toas, siis on järgmine tuba, kus me teda kõige tõenäolisemalt näeme, punane, mitte roheline. Kuigi roheline tuba on punasest populaarsem, muutub olukord, kui mängija viibib sinises. Järgmine seisund (ehk tuba, kuhu mängija läheb) sõltub eelnevast seisundist (ehk toast, kus mängija hetkel viibib). Seoste uurimise tõttu prognoosime me täpsemalt, kui kui me lihtsalt loendame vaatlemisi iseseisvalt.

Tuleviku seisundi ennustamist möödunud seisundi andmete põhjal nimetatakse Markovi mudeliks (Markov model) ja selliseid näiteid (tubadega) nimetatakse Markovi ahelateks. Kuna mudelid kujutavad endast tõenäosust muutusteks järjestikuste seisundite vahel, esitatakse need visuaalselt FSM-ina, kus iga ülemineku tõenäosus on ligikaudu näidatud. Varem kasutasime FSM-i agendi käitumise seisundi esitamiseks, kuid see kontseptsioon laieneb igasugusele seisundile, olenemata sellest, kas see on seotud agendiga või mitte. Antud juhul esindavad seisundid agenti hõivatud tuba:

See on lihtne variant suhtelise tõenäosuse muutuste esitamiseks, andes tehisintellektille võimaluse ennustada järgmist seisundit. Võib teha prognoose mitu sammu ettepoole.

Kui mängija viibib rohelises toas, siis on 50% tõenäosus, et ta jääb sinna ka järgmise vaatlemise ajal. Kuid kui suur on tõenäosus, et ta jääb sinna ka pärast seda? On olemas mitte ainult tõenäosus, et mängija jäi rohelisse tuppa pärast kahte vaatlemist, vaid ka tõenäosus, et ta lahkus ja naasis. Siin on uus tabel uute andmete arvestamisel:

Tabelist on näha, et tõenäosus näha mängijat rohelises toas pärast kahte vaatlemist on 51% — 21%, et ta tuleb punasest toast, 5% nende hulgast, et mängija külastab sinist tuba nende vahel, ja 25%, et mängija ei lahku üldse rohelisest toast.

Tabel on lihtsalt visuaalne tööriist - protseduur nõuab vaid tõenäosuste korrutamist igal sammul. See tähendab, et saate vaadata kaugele tulevikku, ühe parandusega: oletame, et tõenäosus siseneda ruumi sõltub täielikult praegusest ruumist. Seda kutsutakse Markovi omaduseks - tulevane olek sõltub ainult olevikust. Kuid see ei ole täiesti täpne. Mängijad võivad otsuseid muuta sõltuvalt teistest teguritest: tervise tase või kuulide arv. Kuna me ei fikseeri neid väärtusi, on meie ennustused vähem täpsed.

N-grammid

Kuidas on asi näitel, kus mängija võitleb ja ennustab combo-võtteid? Täpselt sama! Kuid ühe oleku või sündmuse asemel uurime tervet järjestust, millest combo-ütlus koosneb.

Üks viis seda teha on salvestada iga sisend (näiteks Kick, Punch või Block) puhvrisse ja salvestada kogu puhver sündmusena. Seega, kui mängija järjestikku vajutab Kick, Kick, Punch, et kasutada rünnakut SuperDeathFist, salvestab AI kõik sisendid puhvrisse ja mäletab viimaseid kolme, mida kasutatakse igal sammul.

(Rasvases kirjas on read, kui mängija käivitab rünnaku SuperDeathFist.)

AI näeb kõiki võimalusi, kui mängija valis Kick, järgneb teine Kick, ning seejärel märkab, et järgmine sisend on alati Punch. See võimaldab agendil ennustada combo-võtet SuperDeathFist ja blokeerida selle, kui see on võimalik.

Need sündmuste järjestused nimetatakse N-grammideks, kus N on salvestatud elementide arv. Eelnevas näites oli see 3-gramm (triaagramm), mis tähendab: esimesed kaks salvestust kasutatakse kolmanda ennustamiseks. Seeläbi ennustavad 5-grammis esimesed neli salvestust viiendat ja nii edasi.

Arendajal on vaja hoolikalt valida N-grammide suurus. Vähem N-d nõuab vähem mälu, kuid salvestab ka vähem ajalugu. Näiteks 2-gramm (bikgramm) salvestab Kick, Kick või Kick, Punch, kuid ei suuda salvestada Kick, Kick, Punch, seega ei reageeri AI combo SuperDeathFist-le.

Teiselt poolt, suuremad numbrid nõuavad rohkem mälu ja AI-l on raskem õppida, kuna tekib palju rohkem võimalikke kombinatsioone. Kui teil oli kolm võimaliku sisendit Kick, Punch või Block, ja kasutasime 10-grammi, siis tekib umbes 60 tuhat erinevat varianti.

Bigrammi mudel on lihtne Markovi ahel — iga paar "eelmine seisund / praegune seisund" on bigramm ja võite ennustada teist seisundit esimesest. 3-gramm ja suuremad N-grammid võivad samuti olla Markovi ahelad, kus kõik elemendid (v.a viimane N-grammis) koos moodustavad esimese seisundi ja viimane element — teise. Näide, kus on võitlus, näitab ülemineku tõenäosust olukorrast Kick ja Kick olukorda Kick ja Punch. Arvestades mitmeid sissejuhatusajaloo kirjeid kui ühte üksust, muundame me sisendi järjestuse osaks terviklikust seisundist. See annab meile Markovi omaduse, mis võimaldab kasutada Markovi ahelaid järgnevate sisendite ennustamiseks ja ära arvata, milline tehnikakäik järgneb.

Kokkuvõte

Rääkisime kõige levinumatest tööriistadest ja lähenemistest tehisintellekti arenduses. Samuti arutasime olukordi, kus neid tuleks rakendada ja kus nad on eriti kasulikud.

Seda peaks olema piisavalt, et mõista mängu tehisintellekti põhiasju. Kuid muidugi pole see kaugeltki kõik meetodid. Vähem levinud, kuid samas efektiivsed on:

• optimeerimisalgoritmid, sealhulgas mägede tõus, gradientne langus ja geneetilised algoritmid
• konkurentsilised otsingu / planeerimise algoritmid (minimax ja alpha-beta kärpimine)
• klassifitseerimismeetodid (perceptroonid, närvivõrgud ja toele suunatud masinad)
• süsteemid agentide tajumise ja mälu töötlemiseks
• arhitektuurilised lähenemised tehisintellektile (hübriidsüsteemid, arhitektuuride alamkogud ja teised tehisintellekti süsteemide ülekandmise viisid)
• animatsiooni tööriistad (liikumise planeerimine ja sünkroniseerimine)
• tulemusfaktorid (detailide tase, anytime algoritmid ja timeslicing)

Internetiallikad teemal:

1. GameDev.net sisaldab artiklite ja õpetuste jaotist tehisintellekti kohta, samuti a forum.
2. AiGameDev.com kätkeb hulgaliselt esitlusmaterjale ja artikleid laia valiku teemade kohta seotud mängu tehisintellekti arendusega.
3. The GDC Vault sisaldab GDC AI tippkohtumise teemasid, mille hulgast paljusid saab tasuta ligipääseda.
4. Kasulikke materjale võib leida ka saidilt AI Game Programmers Guild.
5. Tommy Thompson, tehisintellekti ja mängude arendamise uurija, teeb YouTube'i kanalil AI and Games videoid tehisintellekti selgitamiseks ja uurimiseks kommertsmängudes.

Teemakohased raamatud:

1. Raamatute sari Game AI Pro koosneb lühikestest artiklitest, mis selgitavad, kuidas rakendada konkreetseid funktsioone või kuidas lahendada konkreetseid probleeme.

Game AI Pro: Mängude AI professionaalide kogutud tarkus
Game AI Pro 2: Mängude AI professionaalide kogutud tarkus
Game AI Pro 3: Mängude AI professionaalide kogutud tarkus

2. Sarja AI Game Programming Wisdom eelkäija on sari Game AI Pro. Selles on vanemaid meetodeid, kuid peaaegu kõik on tänapäeval siiski asjakohased.

AI Game Programming Wisdom 1
AI Game Programming Wisdom 2
AI Game Programming Wisdom 3
AI Game Programming Wisdom 4

3. Tehisintellekt: Kaasaegne lähenemine — see on üks põhitekste kõigile, kes soovivad aru saada tehisintellekti üldisest valdkonnast. See raamat ei käsitle mängude arendust — see õpetab tehisintellekti põhialuseid.

Allikas: habr.com