Kuidas luua mängu tehisintellekti: algajatele mõeldud juhend

Leidsin huvitava materjali tehisintellekti kohta mängudes. Selgitustega põhiasjadest tehisintellekti kohta lihtsate näidetega, samuti 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 programmeerimise teadmised vajalikud. Postituse all 35 lehekülge teksti koos piltide ja GIFidega, seega valmistuge.

UPD. Vabandan, kuid olen juba teinud enda tõlke sellest artiklist Habras. PatientZero. Tema versiooni saab lugeda siit, kuid mingil põhjusel jäi artikkel minust mööda (kasutasin otsingut, aga midagi läks valesti). Ja kuna kirjutan mänguarendusele pühendatud blogisse, otsustasin jätta oma tõlke variandi tellijatele (mõned punktid on mul teistmoodi vormistatud, mõned – teadlaste soovitusel jäetud välja).

Mis on tehisintellekt?

Mängu tehisintellekt keskendub sellele, milliseid tegevusi objekt peab olukordade põhjal tegema, milles ta asub. Seda nimetatakse tavaliselt „intelligentsete agentide” juhtimiseks, kus agent on mängu tegelane, sõiduk, robot või mõni muu abstraktsem asi: terviklik olek või isegi tsivilisatsioon. Igal juhul peab see subjekt nägema oma keskkonda, tegema selle põhjal otsuseid ja tegutsema vastavalt. Seda nimetatakse Sense/Think/Act (Tunne/Mõtle/Toimi) tsükliks:

• Tunne: agent leiab või saab teavet oma keskkonnas asjade kohta, mis võivad mõjutada tema käitumist (läheduses olevaid ohte, kogutavaid esemeid, huvitavaid kohti uurimiseks).
• Mõtle: agent otsustab, kuidas reageerida (hindab, kas on piisavalt ohutu esemeid koguda või peaks ta esmalt võitlema/peitma).
• Toimi: agent teostab tegevusi eelmise otsuse elluviimiseks (alustab liikumist vaenlase või eseme suunas).
• …nüüd on olukord muutunud tegelaste tegevuste tõttu, seega kordub tsükkel uute andmetega.

Tehisintellekt keskendub tavaliselt Sense-osale tsüklis. Näiteks autonoomsed autod teevad teest pilte, ühendavad need radarist ja lidarst saadud andmetega ning tõlgendavad neid. Selle tavaliselt teeb masinõpe, mis töötleb sissetulevaid andmeid ja annab neile tähenduse, tuues välja semantilist teavet nagu "seal on veel üks auto 20 jala kaugusel teie ees". Need on nn klassifitseerimisprobleemid.

Mängud ei vaja keerukat süsteemi teabe väljatõmbamiseks, kuna suur osa andmeid on juba nende lahutamatu osa. Pole vaja kasutada pildituvastusalgoritme, et määrata, kas ees on vaenlane — mäng teab seda juba ja edastab teavet otsuste tegemise protsessi käigus. Seetõttu on Sense-o osa tsüklist sageli palju lihtsam kui Think ja Act.

Mängude tehisintellekti piirangud

Tehisintellektil on mitmeid piiranguid, mida tuleb järgida:

• Tehisintellekti ei ole vaja eelnevalt treenida, nagu see oleks masinõppe algoritm. Tühja mõtted kirjutada närvivõrgustiku arendamise ajal, et jälgida kümneid tuhandeid mängijaid ja õppida nende vastu parimat mängimise viisi, on mõttetu. Miks? Sest mäng ei ole veel välja antud ja mängijaid ei ole.
• Mäng peab olema lõbus ja väljakutsuv, seega ei tohi agentidel olla paremat lähenemist inimeste vastu.
• Agendid peavad välja nägema realistlikud, et mängijad tunneksid, et nad mängivad päris inimeste vastu. AlphaGo programm suudab inimesest üle, kuid valitud käigud olid väga kaugel traditsioonilisest mängu mõistmisest. Kui mäng jäljendab inimvastast vastast, 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 tohi monopoliseerida protsessori kasutamist pikka aega otsuste tegemiseks. Isegi 10 millisekundi kasutamine on liiga kaua, sest enamikule mängudele piisab kogu töötlemise ja järgmise graafikakaadri vahetamise jaoks 16 kuni 33 millisekundist.
• Ideaalis peaks vähemalt osa süsteemist olema andmete kaudu juhitud, et 'mitte-koodijad' saaksid muudatusi teha ja et kohandamised toimuksid kiiremini.

Vaatame tehisintellekti lähenemisviise, mis katab kogu Sense/Think/Act tsükli.

Põhikohtade vastuvõtmine

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

Tingimuslikud operaatorid

Pongis on AI jaoks kõige ilmsem lahendus — proovida alati hoida platvorm palliga all.

Lihtne algoritm selle jaoks, kirjutatud pseudokoodis:

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

Kui platvorm liigub sama kiiresti kui pall, siis on see ideaalne algoritm AI jaoks Pongis. Pole vaja midagi keeruliseks muuta, kui andmeid ja võimalikke tegevusi agendile pole eriti palju.

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

• Sense'i osa on kahes if operaatoris. Mäng teab, kus pall on ja kus platvorm asub, seega pöördub AI nende andmete saamiseks mängu poole.
• Osa Think sisaldab ka kahte if-operatsioonisüsteemi. Need moodustavad kaks lahendust, mis on antud juhul välistavad. Tulemusena valitakse üks kolmest tegevusest — liigutada platvorm vasakule, liigutada paremale või mitte midagi teha, kui see on juba õigesti paigutatud.
• Osa Act asub Move Paddle Left ja Move Paddle Right operatsioonides. Olenevalt mängu kujundusest võivad need platvormi liigutada koheselt või teatud kiirusel.

Selliseid lähenemisi nimetatakse reageerivateks — on olemas lihtne reeglite kogu (antud juhul koodis olevad if-operatsioonid), mis reageerivad maailma praegusele olekule ja tegutsevad.

Otsustuspuu

Näide mängust Pong on tegelikult võrdne formaalse tehisintellekti kontseptsiooniga, mida nimetatakse otsustuspuuks. Algoritm liigub selle kaudu, et jõuda 'leheni' — otsusele, millist tegevust võtta.

Vaatame otsustuspuu plokkskeemi meie platvormi algoritmile:

Iga osa puust on nimetatud node'iks (sõlm) — tehisintellekt kasutab analoogiat graafiteooriaga, et kirjeldada sarnaseid struktuure. On kaks tüüpi sõlmi:

• Otsustuspunktid: valik kahe alternatiivi vahel, mis põhineb mõnedel tingimustel, kus iga alternatiiv esindatakse kui eraldi sõlm.
• Lõppsõlmed: teostamine, mis esindab lõplikku otsust.

Algoritt algab esimesest sõlmest ("puu juurest"). See kas otsustab, millisele tütre sõlmele liikuda, või täidab sõlmes säilitatud toimingu ja lõpetatakse.

Kuidas on siis kasu, kui otsuste puu teeb sama tööd, mis if-operaatorid eelnevas osas? Siin on ühine süsteem, kus igal otsusel on ainult üks tingimus ja kaks võimalikku tulemust. See võimaldab arendajal luua tehisintellekti andmete põhjal, mis esindab otsuseid puus, vältides selle kõvasti kodeerimist. Kujutame seda tabelina:

Koodi poolel saate rea lugemise süsteemi. Looge igaühe jaoks sõlm, ühendage otsuste langetamise loogika teise veeru põhjal ja alamsõlmed kolmanda ja neljanda veeru põhjal. Teil on endiselt vaja programmeerida tingimused ja toimingud, kuid nüüd on mängustruktuur keerukam. Lisate täiendavaid otsuseid ja toiminguid ning seadistate kogu tehisintellekti, redigeerides lihtsalt tekstifaili puu määratlemiseks. Seejärel edastate faili mängudisainerile, kes saab käitumist muuta ilma mängu uuesti kompileerimata või koodi muutmata.

Otsustuspuud on üsna kasulikud, kui neid ehitatakse automaatselt suure näidiste kogumi põhjal (näiteks ID3 algoritmi kasutades). See muudab need tõhusaks ja suure jõudlusega tööriistaks olukordade klassifitseerimiseks saadud andmete põhjal. Siiski ületame lihtsa süsteemi, mis valib tegevusi agentide jaoks.

Stsenaariumid

Oleme välja töötanud otsuste puusüsteemi, mis kasutas eelnevalt loodud tingimusi ja tegevusi. Kunstliku intelligentsuse projekteerija saab korraldada puu nii, nagu ta soovib, kuid ta peab ikkagi tuginema programmeerijale, kes kogu selle loonud on. Mis siis, kui me saaksime anda disainerile tööriistad oma tingimuste või tegevuste loomiseks?

Kuna programmeerija ei pea pingutama koodi kirjutamisega tingimuste Is Ball Left Of Paddle ja Is Ball Right Of Paddle jaoks, võib ta luua süsteemi, kus disainer salvestab tingimused nende väärtuste kontrollimiseks. Siis näeks otsuste puu andmed välja järgmiselt:

Sisuliselt on see sama, mis esimeses tabelis, kuid lahendused omavad omavahelist koodi, mis on veidi sarnane if-lausete tingimuslikule osale. Koodi poole pealt loetaks see otsustuspindade teises veerus, kuid eristava tingimuse otsimise asemel (Kas pall on raceri vasakul küljel?) hinnatakse tingimuslauset ja tagastatakse vastavalt true või false. Selleks kasutatakse skriptikeelt Lua või Angelscript. Nende abil saab arendaja oma mängus objekte (pall ja ratas) töödelda ning luua muutujaid, mis on skriptis kergesti kätte saadavad (ball.position). Lisaks on skriptikeel lihtsam kui C++. See ei nõua täiskompileerimise etappi, mistõttu sobib see ideaalselt mängulogika kiireks kohandamiseks ja võimaldab „koodita“ inimestel ise vajalikke funktsioone luua.

Antud näites kasutatakse skriptikeelt ainult tingimuslause hindamiseks, kuid seda saab kasutada ka tegevuste jaoks. Näiteks võivad andmed Move Paddle Right muutuda skriptioperatsiooniks (ball.position.x += 10). Nii võib tegevuse määratlemine toimuda skriptis ilma vajaduseta programmeerida Move Paddle Right.

Võite minna veelgi kaugemale ja kirjutada otsuste puu täielikult skriptikeeles. See on kood, mis koosneb rangelt programmeeritud tingimuslausete põhjal, kuid need on väliste skriptifailide sees, mis tähendab, et neid saab muuta ilma kogu programmi uuesti kompileerimata. Tihti saab skriptifaili muuta otse mängu ajal, et kiiresti testida erinevaid teid AI reageerimist.

Olenemised sündmustele

Ülaltoodud näited sobivad ideaalselt Pongile. Need käivitavad pidevalt Sense/Think/Act tsükli ja tegutsevad viimase maailma seisundi põhjal. Kuid keerukamates mängudes tuleb reageerida üksikutele sündmustele, mitte hinnata kõike korraga. Pong ei ole sellisel juhul enam hea näide. Vaatame midagi muud.

Kujutage ette tulistamismängu, kus vaenlased on liikumatud seni, kuni nad avastavad mängija, pärast mida nad tegutsevad vastavalt oma 'spetsialiseerumisele': keegi jookseb 'rushing' peale, keegi ründab kaugelt. See on endiselt põhine reageerimise süsteem — 'kui mängija on nähtud, siis tee midagi', — kuid seda saab loogiliselt jagada sündmuseks Mängija Nähud (Player Seen) ja reaktsiooniks (valige vastus ja teostage see).

See tagasi meid Sense/Think/Act tsüklisse. Me saame kirjutada Sense-osa, mis iga kaadri jaoks 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 jaotis, kus on kirjas: „kui toimub sündmus Player Seen, tee”, kus — vastus, mida vajate Tellimise ja Tegevuse osadele viitamiseks. Nii seadistate reaktsioonid sündmusele Player Seen: „ründava” karakteri puhul — ChargeAndAttack, ja sniperi puhul — HideAndSnipe. Need seosed saab luua andmefailis kiireks redigeerimiseks ilma vajaduseta uuesti kompileerida. Ja siin saab kasutada ka skriptikeelt.

Kohakohaste otsuste vastuvõtmine

Kuigi lihtsad reaktsioonisüsteemid on väga tõhusad, on palju olukordi, kus need ei piisa. Mõnikord on vaja teha erinevaid otsuseid, mis põhinevad sellel, mida agent praegu teeb, kuid nende esitamine tingimustena on keeruline. Mõnikord on liiga palju tingimusi, et neid tõhusalt otsustepuudel või skriptides esitada. Mõnikord on oluline eelnevalt hinnata, kuidas olukord muutub, enne järgmise sammu jaoks otsuse tegemist. Nende probleemide lahendamiseks on vajalikud keerukamad lähenemisviisid.

Lõplik olekumasin

Lõplik olekumasin ehk FSM (lõplik automaat) on viis öelda, et meie agent on praegu ühes mitmest võimalikust olekust ning et ta võib liikuda ühest olekust teise. Sellega on määratud kindel hulk olekuid — seetõttu ka nimi. Parim näide igapäevaelust on liiklusfoor. Erinevates kohtades on erinevad tulede järjestused, kuid põhimõte on sama — iga olek esindab midagi (seisa, mine jne). Liiklusfoor on igal ajal ainult ühes olekus ja liigub ühelt teisele lihtsate reeglite alusel.

NPC-de mängudes on sarnane lugu. Võtame näiteks patrulli, millel on järgmised seisundid:

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

Ja selliste tingimustega, et muuta tema seisundit:

• Kui patrull näeb vaenlast, ründab ta.
• Kui patrull ründab, kuid enam ei näe vaenlast, naaseb ta patrullimise juurde.
• Kui patrull ründab, aga on tõsiselt haavatud, põgeneb ta.

Samuti saab kirjutada if-käsklusi, kasutades patrulli seisundi muutujat ja erinevaid kontrolle: kas vaenlane on läheduses, mis on NPC tervise tase jne. Lisa veel mõned seisundid:

• Mugavolek (Idling) — patrullide vahel.
• Otsing (Searching) — kui nähtud vaenlane on kadunud.
• Abi palumine (Finding Help) — kui vaenlane on nähtud, aga liiga tugev, et üksi temaga võidelda.

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

Lõppkokkuvõttes võib tohutu "kui... siis" nimekiri muutuda liiga mahukaks, seetõttu tuleks formaliseerida meetod, mis aitab meil meeles pidada olekuid ja üleminekuid nende vahel. Selleks võtame arvesse kõik olekud ja iga oleku puhul kirjutame üles kõik üleminekud teistesse olekutesse koos nende jaoks vajalike tingimustega. <x и y, но не z>, siis <p>», võib muutuda liiga keeruliseks, seega tuleks välja töötada meetod, mis aitab meil meeles pidada olekuid ja üleminekuid nende vahel. Selleks arvestame kõiki olekuid ja iga oleku alla koostame nimekirja kõikidest üleminekutest teistesse olekutesse koos nende jaoks vajalikud tingimustega.

See on seisundite üleminekute tabel — kompleksne viis FSM-i esitlemiseks. Joonistame diagrammi ja saame täieliku ülevaate sellest, kuidas NPC käitumine muutub.

Diagramm illustreerib otsuste langetamise olemust selle agendi jaoks, tuginedes praegusele olukorrale. Iga nool näitab üleminekuid olekute vahel, kui kõrval olev tingimus on tõene.

Iga uuendusega kontrollime agendi praegust olekut, vaatame üleminekute nimekirja ja kui ülemineku tingimused on täidetud, võtab ta uue oleku. Näiteks kontrollitakse igal kaadril, kas 10-sekundiline timer on aegunud, ja kui jah, siis liigub strahh 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, aga kuidas on lood käitumisega, mis on seotud nende endi olekute talitustega? Mis puudutab konkreetse oleku tegelikku käitumise rakendamist, siis tavaliselt on olemas kaks tüüpi 'konksu', kus me seome tegevused FSM-iga:

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

Esimene tüüp. Patrolling olek liigub iga raami jooksul agendi patrullmarsruuti. Attacking olek püüab iga raami jooksul alustada rünnakut või minna olekusse, kui see on võimalik.

Teise tüübi puhul vaatame üleminekute avaldust: „kui vaenlane on nähtav ja vaenlane on liiga tugev, siis mine olekusse Finding Help.” Agent peab valima, kuhu abi minna ning salvestama selle teabe, et olek Finding Help teaks, kuhu pöörduda. Kui abi on leitud, naaseb agent tagasi olekusse Attacking. Sellel hetkel soovib ta teavitada liitlast ohust, seega võib tekkida tegevus NotifyFriendOfThreat.

Jällegi saame seda süsteemi vaadata Sense/Think/Act tsükli kaudu. Sense väljendub andmetes, mida kasutatakse üleminekuloogikas. Think — üleminekutes, mis on saadaval igas olekus. Ja Act toimub tegevustega, mis aset leiavad regulaarselt oleku piires või olekute vahel üleminekute ajal.

Mõnikord võib pidev ülemineku tingimuste küsitlemine olla kulukas. Näiteks, kui iga agent teostab keerulisi arvutusi igas kaadris, et määrata, kas ta näeb vaenlasi ja aru saada, kas liikuda Patrolling olekust Attacking olekusse — võtab see palju protsessoriaega.

Olulisi muutusi maailma seisundis võib käsitleda sündmustena, mida töödeldakse nende ilmumise ajal. Selle asemel, et FSM igas kaadris kontrolliks ülemineku tingimust 'kas mu agent näeb mängijat?', saab seadistada eraldi süsteemi, et teostada kontrolle harvemini (näiteks 5 korda sekundis). Tulemuseks on Player Seen, kui kontroll läbib.

See edastatakse FSM-ile, mis peab nüüd ülemineku tingimuseks Player Seen sündmuse saamise ja vastavalt reageerima. Lõppkäitumine on sama, välja arvatud peaaegu märkamatu viivitus enne vastust. Kuid nüüd on jõudlus parem, kuna osa Sense'ist on eraldatud eraldi programmiosaks.

Hierarchical finite state machine

Kuid töötamine suurte FSM-idega ei ole alati mugav. Kui soovime rünnakuseisundit laiendada, asendades selle eraldi MeleeAttacking (lähedane rünnak) ja RangedAttacking (kaug rünnak), peame muutma üleminekud kõigist teistest seisunditest, mis viivad rünnakuseisundisse (nii praegused kui tulevased).

Olete kindlasti märganud, et meie näITES on palju dubleeritud üleminekuid. Enamiku üleminekud seisu Idling on identsed üleminekud seisu Patrolling. Hea oleks mitte korduda, eriti kui lisame rohkem sarnaseid seisundeid. On mõistlik rühmitada Idling ja Patrolling ühise sildi „mitte-kerged” alla, kus on vaid üks ühine üleminekute kogum lahingu seisunditesse. Kui me kujutame seda sildi kui staatust, siis Idling ja Patrolling saavad alam-seisunditeks. Näide eraldi üleminekute tabeli kasutamisest uue mitte-kerge alam-seisundi jaoks:

Põhiseisundid:


Väljas olek:


Ja diagrammi kujul:

See on sama süsteem, kuid uue mittevõitlusliku olekuga, mis sisaldab Idling ja Patrolling. Iga olekuga on seotud FSM (lõppmõju automaat), millel on alamolekud (ja need alamolekud sisaldavad omakorda oma FSM-e — niikaua kui teil on vaja), saame Hierarchical Finite State Machine ehk HFSM (hierarhiline lõppautomaat). Ühtlustades mittevõitluslikku olekut, oleme pidevalt vähendanud üleliigseid üleminekuid. Sama saame teha kõigi uute olekute puhul, millel on ühised üleminekud. Näiteks kui tulevikus laiendame olekut Attacking olekute MeleeAttacking ja MissileAttacking juurde, siis need on alamolekud, mis üksteise vahel liiguvad sõltuvalt vahemaa suurusest vaenlase ja ammunition'i olemasolu järgi. Lõppkokkuvõttes saab keerulisi käitumismudeleid ja alamkäitumismudeleid esitada minimaalsete dubleeritud üleminekute arvuga.

Käitumiste puu

HFSM-i abil saate keerulisi käitumise kombinatsioone luua lihtsal viisil. Kuid on üks väike raskus, et otsuste tegemine ülemineku reeglite kaudu on tihedalt seotud praeguse olekuga. Ja paljudes mängudes on see täpselt see, mida vaja. Hoolikas seisundihierarhia kasutamine võib vähendada üleminekute korduste arvu. Kuid mõnikord on vajalikud reeglid, mis toimivad sõltumatult sellest, millisest seisundist oletate või mis kehtivad peaaegu igas seisundis. Näiteks kui agendi tervis langeb 25%-ni, soovite, et ta jookseks minema, olenemata sellest, kas ta on lahingus, jalutab või vestleb — peate selle tingimuse igasse olekusse lisama. Ja kui teie disainer soovib hiljem madala tervise piiri muuta 25%-lt 10%-le, peab sellega uuesti tegelema.

Ideaaljuhul vajab see olukord süsteemi, kus otsus „millises olekus olla” jääb seisundite endi piiridest välja, et muudatusi saaks teha ainult ühes kohas ning ei peaks puutuma ülemineku tingimustesse. Siin tulevad mängu käitumispuud.

On mitu viisi nende rakendamiseks, kuid sisu on kõigi puhul enam-vähem sama ja sarnaneb otsusepuule: algoritm algab „juure“ sõlmest, puus on sõlmed, mis esindavad kas otsuseid või tegevusi. Tõsi, mõned olulised erinevused on siiski olemas:

• Nüüd tagastavad sõlmed ühe kolmest väärtusest: Succeeded (kui töö on tehtud), Failed (kui ei saa käivitada) või Running (kui see on endiselt käimas ja pole lõplikku tulemust).
• Otsustuskohti, kus valida kahe alternatiivi vahel, enam pole. Selle asemel on olemas Decorator sõlmed, millel on üks alam-sõlm. Kui nad Successful, siis täidavad nad oma ainukese alam-sõlme.
• Tegevusi teostavad sõlmed tagastavad väärtuse Running, et esindada teostatavaid tegevusi.

Seda väikest sõlmede kogumit saab ühendada, et luua suur hulk keerukaid käitumismudeleid. Kujutlegem näiteks eelneva mustri HFSM valveallikat käitumispuuna:

Selle struktuuriga ei tohiks olla selget üleminekut olekute Idling/Patrolling ja oleku Attacking või mõnede teiste vahel. Kui vaenlane on nähtav ja tegelase elu on madal, siis peatub täitmine sõlmes Fleeing, sõltumata sellest, millist sõlme ta varem täitis — Patrolling, Idling, Attacking või mõni muu.

Käitumispuud on keerulised — neid on palju erinevaid koostamise viise, kuid õige dekoratorite ja komposiit-sõlmede kombinatsiooni leidmine võib olla probleem. On ka küsimusi selle kohta, kui sageli puu kontrollida — kas me soovime seda läbida iga osa või ainult siis, kui üks tingimus muutub? Kuidas hoida sõlmedega seotud olekut — kuidas teada, kui oleme olnud olekus Idling 10 sekundi jooksul või kuidas teada, millised sõlmed viimasel korral täideti, et õigesti järjestust töödelda?

Just sellepärast on olemas mitmeid teostusi. Näiteks mõnedes süsteemides on dekoratorisõlmed asendatud sisseehitatud dekoratoritega. Need uuesti hindavad puu tingimuste muutumisel, aitavad sõlmedega liituda ja tagavad perioodilised uuendused.

Utility-põhine süsteem

Mõnel mängul on mitmeid erinevaid mehhanisme. Soovitav on, et nad saaksid kõik eelised lihtsatest ja ühestest reeglitevahenditest, kuid see ei pea olema täieliku käitumise puu kujul. Selle asemel, et omada selget valikute komplekti või võimalike tegevuste puu, on lihtsam uurida kõiki tegevusi ja valida hetke kõige sobivam.

Kasulikkusele põhinev süsteem aitab selles osas. See on süsteem, kus agendil on palju tegevusi ja ta valib ise, millist teostada, põhinedes iga tegevuse suhteliselt kasulikusele. Siinjuures tähendab kasulikkus meelevaldset mõõtu, kuivõrd oluline või soovitav on selle tegevuse teostamine agendi jaoks.

Arvestatud tegevuse kasulikkust praeguse oleku ja keskkonna põhjal saab agent igal ajal kontrollida ja valida sobivama teise oleku. See sarnaneb FSM-iga, välja arvatud see, et üleminekud määratakse iga potentsiaalse oleku, sealhulgas praeguse, hindamise järgi. Pöörake tähelepanu sellele, et valime üleminekuks kõige kasulikuma tegevuse (või jääme paigale, kui oleme juba selle teinud). Suurema mitmekesisuse jaoks võib see olla kaalutud, kuid juhuslik valik väiksemast nimekirjast.

Süsteem määrab suvalise kasulikkuse väärtuste vahemiku — näiteks vahemikus 0 (täiesti ebasoovitav) kuni 100 (täiesti soovitav). Igal tegevusel on mitmed parameetrid, mis mõjutavad selle väärtuse arvutamist. Tagasi meie näite juurde valvuri kohta:

Tegevuste vahelised üleminekud on mitmeti mõistetavad — ükski olek ei saa järgneda ainult teisele. Tegevuste prioriteedid tulenevad tagastatavast kasulikkusest. Kui vaenlane on nähtav, tugev ja tegelase elu on madal, siis nii põgenemine kui ka abi leidmine annavad kõrgeid mitte-null väärtusi. Samas on abi leidmine alati kõrgem. Samuti ei anna mitte-eri tegevused kunagi rohkem kui 50, seega jäävad need alati madalamale kui lahingu tegevused. Seda tuleb arvestada tegevuste loomisel ja nende kasulikkuse arvutamisel.

Meie näites tagastavad toimingud kas fikseeritud väärtuse või ühe kahest fikseeritud väärtusest. Realistlikum süsteem eeldab, et hindamine toimub pidevas väärtuste vahemikus. Näiteks, kui agent on madala elujõu tasemega, tagastab toiming „Põgenemine” kõrgema kasulikkuse väärtuse, samas kui toiming „Ründamine” tagastab madalama, kui vaenlane on liiga tugev. Seetõttu on toimingul „Põgenemine” prioriteet toimingu „Ründamine” üle igas olukorras, kus agent tunneb, et tal ei ole piisavalt elujõudu vastase võitmiseks. See võimaldab muuta toimingute prioriteete, tuginedes mistahes kriteeriumitele, muutes lähenemise paindlikumaks ja varieeruvamaks kui käitumise puu või FSM.

Iga tegevus sisaldab paljusid tingimusi programmi arvutamiseks. Neid saab kirjutada skriptikeeles või matemaatiliste valemite seeriana. The Sims, mis modelleerib tegelase päevakava, lisab täiendava arvutustaseme — agent saab rea "motivatsioone", mis mõjutavad kasulikkuse hinnanguid. Kui tegelane on näljane, siis aja jooksul muutub ta näljasemaks, ja EatFood tegevuse kasulikkuse tulemus tõuseb, kuni tegelane teeb selle, vähendades nälga ja naastes EatFood väärtusega null.

Tegevuste valimise idee põhineb hinna süsteemil, seega saab Utility-based süsteemi kasutada AI otsustusprotsessides osana, mitte nende täieliku asendusena. Otsustuspuu võib küsida kahe alamõle otsuse kasulikkuse hindamist ja valida kõrgema. Samamoodi võib käitumispuu sisaldada komposiitnode Utility, et hinnata tegevuste kasulikkust, et otsustada, millist alamelementi täita.

Liikumine ja navigeerimine

Eelmistes näidetes oli meil platvorm, mida me liigutame vasakule või paremale, ja valvuri, kes patrullib või ründab. Kuid kuidas me täpselt käsitleme agendi liikumist teatava aja jooksul? Kuidas me määrame kiirus, kuidas me takistusi vältime ja kuidas me marsruuti planeerime, kui sihtkohta jõudmine on keerulisem kui lihtsalt sirgjooneliselt liikuda? Vaatame sellele lähemalt.

Halduse

Alguses eeldame, et igal agendil on kiirus, mis hõlmab, kui kiiresti ta liigub ja mis suunas. Seda saab mõõta meetrites sekundis, kilomeetrites tunnis, pikseldes sekundis jne. Meeles pidades tunnustamine / Mõtle / Toimi tsüklit, võime ette kujutada, et osa mõtlemisest valib kiirus ja osa tegevusest rakendab seda kiirusest agenti. Mängudes on tavaliselt füüsikasüsteem, mis teeb selle ülesande teie eest, uurides iga objekti kiirusväärtust ja reguleerides seda. Seetõttu võib jätta AI-le ühe ülesande — otsustada, kui kiiresti agent peab olema. Kui on teada, kus agent peab olema, tuleb see liikuda õiges suunas määratud kiirusel. Väga triviaalne võrrand:

desired_travel = destination_position – agent_position

Kujutage ette 2D maailma. Agend asub punktis (-2,-2), sihtkoht asub kuskil kirdes punktis (30, 20), ning vajalik tee agendi jõudmiseks sinna on (32, 22). Eeldame, et need positsioonid on mõõdetud meetrites — kui võtta agendi kiirus 5 meetrit sekundis, siis me skaleerime meie liikumisvektori ja saame kiirusena umbes (4.12, 2.83). Nende parameetritega jõuaks agent sihtkohta peaaegu 8 sekundi pärast.

Väärtusi saab igal ajal uuesti arvutada. Kui agent oleks sihtpunkti poole poolel teel, oleks liikumine poole pikem, kuid kuna agendi maksimaalne kiirus on 5 m/s (nagu me eespool otsustasime), jääb kiirus samaks. See kehtib ka liikuvate sihtide puhul, võimaldades agendil teha väikeseid kohandusi nende liikumise ajal.

Kuid me soovime rohkem variatiivsust — näiteks, et kiirus kasvaks aeglaselt, simuleerides tegelast, kes liigub seismise seisundist jooksmisele. Sama saab teha ka enne peatumist. Need omadused on tuntud kui steering behaviours, millest igaühel on spetsiifilised nimed: Seek (otsimine), Flee (põgenemine), Arrival (saabumine) jne. Idee on selles, et kiirusjõud võivad olla rakendatud agendi kiirusest, võttes aluseks agendi asendi ja praeguse kiiruse võrdlemise sihtpunktiga, et kasutada erinevaid viise eesmärgini jõudmiseks.

Iga käitumine omab veidi erinevat eesmärki. Seek ja Arrival on viisid, kuidas agent liigub sihtkohta. Obstacle Avoidance (takistuste vältimine) ja Separation (eraldamine) kohandavad agendi liikumist, et vältida teel olevaid takistusi. Alignment (sünkroniseerimine) ja Cohesion (sidusus) hoiavad agente koos liikumise ajal. Erinevaid steering behaviours (suunamisviise) saab kokku liita, et luua üks marsruut, arvestades kõiki tegureid. Agent, kes kasutab Arrival, Separation ja Obstacle Avoidance käitumisi, et hoida eemale seintest ja teistest agentidest. See lähenemine töötab hästi avatud paikades, kus ei ole liigseid detaile.

Raskemates tingimustes erinevate käitumiste liitmine töötab halvemini — näiteks võib agent lõksu jääda seina, kuna Arrival ja Obstacle Avoidance konfliktimeetodid. Seetõttu tuleks arvesse võtta keerulisemaid variante kui lihtsalt kõigi väärtuste liitmine. Üks võimalus on see, et tulemuste liitmise asemel saab kaaluda liikumist erinevates suundades ja valida parim variant.

Kuid keerulises keskkonnas, kus on ummikud ja on valik, millises suunas minna, vajame midagi veelgi arenenumat.

Teekonna leidmine

Juhitavad käitumised sobivad suurepäraselt lihtsaks liikumiseks avatud maastikul (jalgpalliväljak või areen), kus A-st B-sse jõudmine on sirge tee väikeste kõrvalekaldumistega takistustest mööda. Kompleksemate marsruutide jaoks on meil vaja teepunktide leidmist, mis on viis maailma uurimiseks ja marsruudi valimiseks selle kaudu.

Kõige lihtsam viis on kanda ruudustik iga ruudu kohal, kus agent asub, ja hinnata, millised neist on liikumise jaoks lubatud. Kui mõni neist on sihtkoht, siis liikuge sellest mööda teed igast ruudust tagasi eelmise suunas, kuni jõuate algusesse. See on marsruut. Kui ei, korrake protsessi lähimates muudes ruutudes, kuni leiate sihtkoha või kui ruudud on otsa saanud (mis tähendab, et ei ole võimalikku marsruuti). Seda tuntakse ametlikult kui laiaulatuslikku otsingut või BFS (Breadth-First Search). Iga sammu korral vaatab see igas suunas (seega on see 'laius'). Otsinguruum sarnaneb lainete frontiga, mis liigub, kuni saavutab soovitud koha — otsinguala laieneb iga sammu kaupa, kuni see saavutab lõpp-punkti, pärast mida saab trajektoori algusesse jälgida.

Tulemusena saate loendi ruutudest, mille kaudu koostatakse vajalik marsruut. See on teekond (seetõttu 'pathfinding') — loetelu kohtadest, mida agent külastab, liikudes sihtkohta.

Arvestades, et me teame iga ruudu asukohta maailmas, on võimalik kasutada steering behaviours'i, et liikuda mööda teed — alates sõlmest 1 sõlmeni 2, seejärel 2 sõlmest 3 ja nii edasi. Lihtsaim variant on liikuda järgmise ruudu keskpunkti suunas, kuid veel parem oleks peatuda praeguse ruudu ja järgmise vaheline äär keskel. Sel viisil suudab agent teravaid nurki järsudel pöördel kärpida.

BFS-algoritmil on ka miinuseid — see uurib sama palju ruute 'vale' suunas kui 'õige'. Siit tuleb keerulisem algoritm, mida nimetatakse A* (A star). See töötab samuti, kuid selle asemel, et irratiivselt uurida naaberruute (seejärel naabrid naabritele jne), kogub see sõlmed listi ja sorteerib need nii, et järgmiseks uurimiseks on alati sõlm, mis viib lühimale marsruudile. Sõlmi sorteeritakse heuristika alusel, mis arvestab kahte asja — 'kulude' hüpoteetilist marsruuti soovitud ruuduni (sealhulgas kõik liikumiskulud) ja hindamist, kui kaugel see ruut sihtkohast on (suunates otsingut õigesse suunda).

Selles näites uurib agent ruute ükshaaval, valides iga kord naaberi, mis näib kõige lootustandvam. Saadud tee on sama nagu BFS-i puhul, kuid protsessi käigus on kaalutud vähem ruute — see on mängu jõudluse jaoks väga oluline.

Liikumine ilma ruudustikuta

Kuid enamik mänge ei põhine ruudustikul, ja tihti ei saa seda realistlikkuse nimel ära teha. Vajalikud on kompromissid. Millised peaksid olema ruutude mõõtmed? Kui need on liiga suured, ei suuda nad korralikult näidata väikeseid koridore või pöördeid, ja kui nad on liiga väiksed, on otsimiseks liiga palju ruute, mis lõpuks aega raiskab.

Esimene asi, mida mõista, on see, et võrk annab meile seotud sõlmede graafi. A* ja BFS algoritmid töötavad tegelikult graafidel ega hooli meie võrgust üldse. Me võime paigutada sõlmed mängumaailma mistahes kohtadesse: kui kahe seotud sõlme vahel on ühendus ning algus- ja lõpp-punkti vahel vähemalt üks sõlm, töötab algoritm endiselt sama hästi kui varem. Seda nimetatakse sageli teepunktide süsteemiks, kuna iga sõlm esindab olulist positsiooni maailmas, mis võib olla osa igasugustest hüpoteetilistest teedest.

Näide 1: sõlm igas ruudus. Otsing algab sõlmest, kus agent asub, ja lõpeb soovitud ruudu sõlmes.

Näide 2: väiksem sõlmede kogum (teepunktid). Otsing algab ruudust, kus agent on, läbib vajaliku arvu sõlmi ja jätkub seejärel sihtpunkti.

See on üsna paindlik ja võimas süsteem. Kuid vajatakse teatud ettevaatust otsuste tegemisel, kus ja kuidas waypoint paigutada, vastasel juhul võivad agentid lihtsalt lähimat punkti mitte märgata ja oma teed alustada. Oluliselt lihtsam oleks, kui saaksime automaatselt teepunktid paigutada maailma geomeetria põhjal.

Siia tuleb navigeerimisvõrk ehk navmesh. See on tavaliselt 2D kolmnurkade võrk, mis kantakse maailma geomeetriale — igal pool, kus agent on lubatud liikuda. Iga kolmnurk võrgus muutub graafis sõlmpunktiks ja sellel on kuni kolm külgnevat kolmnurka, mis muutuvad graafis naabersõlmedeks.

See pilt on näide Unity mootorist — see analüüsis maailma geomeetriat ja lõi navmeshi (halli sinise värviga ekraanipildil). Iga polügoon navmeshis on piirkond, kus agent saab seista või liikuda ühest polügoonist teise. Antud näites on polügoonid väiksemad kui korrused, millel nad asuvad — see on tehtud, et arvestada agendi suurusi, mis võivad ületada tema nimelisest asukohast väljapoole.

Saame otsida marsruuti selle võrgu kaudu, kasutades jälle A* algoritmi. See annab meile peaaegu ideaalse marsruudi maailmas, mis arvestab kogu geomeetriaga ja samal ajal ei vaja ülearuseid sõlmi ega teepunkte.

Marsruudi leidmine on liiga ulatuslik teema, mille kohta ei piisa ühest artikli jaost. Kui soovite seda põhjalikumalt uurida, siis aitab teid Amit Patel'i veebisait.

Planeerimine

Oleme leidnud, et marsruudi leidmine ei tähenda lihtsalt suuna valimist ja liikumist — peame valima marsruudi ja tegema mitu pöörde, et jõuda soovitud sihtkohta. Saame selle idee kokku võtta: eesmärgi saavutamine ei ole lihtsalt järgmine samm, vaid terviklik jada, kus mõnikord on vajalik ette näha mitu sammu, et teada, milline peaks olema esimene. Seda nimetatakse planeerimiseks. Marsruudi leidmist võib pidada üheks planeerimise lisandiks. Meie Sense/Think/Act tsükli perspektiivist on see see, kus Think plaanib mitmeid tulevasi Act komponente.

Käsitleme näidet lauamängust Magic: The Gathering. Meie käik alustab selliste kaartidega käes:

• Swamp — annab 1 musta mannat (maa kaart).
• Mets — annab 1 rohelise mana (maa kaart).
• Põgenenud nõid — nõuab 1 sinist mana kutsumiseks.
• Elfide müstik — nõuab 1 rohelist mana kutsumiseks.

Jätame viimased kolm kaarti tähelepanuta, et asjad lihtsamaks teha. Reeglite järgi on mängijal lubatud mängida 1 maa kaarti ühel käigul, ta võib selle kaardi 'tapida', et saada mana, ja siis kasutada loitse (sealhulgas olendi kutsumist) nii palju kui tuleb mana. Selles olukorras teab inimesest mängija, et peab mängima Mets, 'tapima' 1 rohelise mana ja siis kutsuma Elfide müstiku. Kuid kuidas sellest mängu AI-le teada anda?

Lihtne planeerimine

Triviaalne lähenemine — proovida iga tegevust järjestikku, kuni sobivaid enam ei jää. Kaartidele vaadates näeb AI, et saab mängida Soost. Ja mängib selle. Kas sellel käigul on veel muid tegevusi? Ta ei saa kutsuda ei Elfide müstikut ega põgenenud nõida, kuna nende kutsumiseks on vastavalt vajalikud roheline ja sinine mana, aga Soost annab ainult musta mana. Ja ta ei saa enam mängida Mets, kuna on juba mänginud Soost. Seega mängis mängu AI reeglite järgi, kuid tegi seda halvasti. Seda saab parandada.

Planeerimine võib leida loetelu tegevustest, mis viivad mängu soovitud olekusse. Nii nagu iga ruut teel omas naabreid (teede leidmine), on igal tegevusel plaanis samuti naabrid või järgijad. Me saame neid tegevusi ja järgmisi samme otsida, kuni saavutame soovitud oleku.

Meie näites on soovitud tulemus „kutsuda olend, kui see on võimalik“. Käigu alguses näeme vaid kahte võimalikku tegevust, mille mängureeglid lubavad:

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

Iga tehtud tegevus võib viia edasiste tegevusteni ja sulgeda teisi, uuesti mängureeglite kohaselt. Kujutage ette, et mängisime Swamp — see eemaldab Swamp järgmise sammuna (me oleme selle juba mänginud), samuti eemaldab see Forest (sest reeglite järgi saab ühe mängimise käigus mängida vaid ühe maakaardi). Pärast seda lisab AI järgmise sammu — 1 musta mana saamine, kuna teisi võimalusi pole. Kui ta jätkab ja valib Tap the Swamp, siis saab ta 1 musta mana ja ei saa sellega midagi teha.

1. Mängida Swamp (tulemus: Swamp mängus)
1.1 «Tap» Soost (tulemus: Soost «tapped», +1 musta maagi ühik)
Ei ole saadaval tegevusi – LÕPP
2. Mängida Forest (tulemus: Forest mängus)

Tegevuste nimekiri on lühike, oleme ummikusse jõudnud. Korrake protsessi järgmise tegevuse jaoks. Me mängime Mets, avame tegevuse „saada 1 roheline maagi“, mis omakorda avab kolmanda tegevuse — Elvish Mystic'i kutse.

1. Mängida Swamp (tulemus: Swamp mängus)
1.1 «Tap» Soost (tulemus: Soost «tapped», +1 musta maagi ühik)
Ei ole saadaval tegevusi – LÕPP
2. Mängida Forest (tulemus: Forest mängus)
2.1 «Tap» Mets (tulemus: Mets «tapped», +1 roheline maagi ühik)
2.1.1 Kutse Elvish Mystic (tulemus: Elvish Mystic mängus, -1 roheline maagi ühik)
Ei ole saadaval tegevusi – LÕPP

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

See on väga lihtsustatud näide. Soovitav on valida parim võimalik plaan, mitte lihtsalt miski, mis vastab mõningatele kriteeriumidele. Üldiselt saab potentsiaalseid plaane hinnata lõpptulemuse või nende täitmisest saadava koguhinna põhjal. Võite endale teenida 1 punkti maakaartide mängimise eest ja 3 punkti olendi väljakutsumise eest. Soost mängimine oleks plaan, mis annab 1 punkti. Kuid Mets → Tap the Mets → Elvish Mystic'i väljakutsumine toob kohe 4 punkti.

Nii toimib Magic: The Gathering'i planeerimine, kuid sama loogika kehtib ka teistes olukordades. Näiteks nihutada odavat, et vabastada ruumi elevandi käiguks malet. Või peituda seina taha, et XCOMis ohutult tulistada. Üldiselt saite aru.

Parandatud planeerimine

Mõnikord on liiga palju võimalikke tegevusi, et kaaluda iga võimalikku varianti. Tagasi tulles Magic: The Gathering'i näitena: oletame, et mängus ja teil on käes mitu maakaarti ja olendit — võimalike kombinatsioonide arv võib olla kümnete kaupa. Probleemi lahendamiseks on mitu võimalust.

Esimene meetod on backwards chaining (tagurpidi ahelate loomine). Selle asemel, et kõiki kombinatsioone läbi töötada, on parem alustada lõpptulemusest ja proovida leida otsene marsruut. Selle asemel, et liikuda puu juurest konkreetse leheni, liigume vastupidises suunas — lehelt juure poole. See meetod on lihtsam ja kiirem.

Kui vastasel on 1 elupunkt, saab leida plaani, et "tekitada 1 või rohkem kahju". Selle saavutamiseks tuleb täita mitu tingimust:

1. Kahju võib tekitada loits — see peab olema käes.
2. Loitsimise jaoks on vajalik mana.
3. Mana saamiseks tuleb mängida maakaart.
4. Maakaardi mängimiseks tuleb see olla käes.

Teine võimalus on best-first search (parim esimene otsing). Selle asemel, et uurida kõiki teid, valime kõige sobivama. Enamasti annab see meetod optimaalse plaani ilma liigsete otsingukuludeta. A* on parima esimese otsingu vorm — uurides kõige lootustandvamaid marsruute algusest peale, võib see leida parima tee ilma vajaduseta kontrollida ülejäänud variante.

Üha populaarsem alternatiiv parim-eesotsas otsingule on Monte Carlo puuotsing. Selle asemel, et arvata, millised plaanid on parimad iga järgmise tegevuse valimisel, valib algoritm igal sammul juhuslikke järeltulijaid, kuni jõuab lõpuni (kui plaan viib võiduni või kaotusele). Seejärel kasutatakse lõpptulemust eelnevate valikute „kaalu“ tõstmiseks või langetamiseks. 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 planeerimise narratiivis ei saa mööda Goal-Oriented Action Planning'ust ehk GOAP'ist (sihtsuunatud tegevuste planeerimine). See on laialdaselt kasutatav ja arutatav meetod, kuid lisaks mõnele eristavale detailile on see põhimõtteliselt tagasikett, millest me varem rääkisime. Kui ülesanne on „hävitada mängija“ ja mängija on varjatud, võib plaan olla järgnev: hävita granadiga → saa see kätte → viska.

Tavaliselt on mitmeid eesmärke, millest igaühel on oma prioriteet. Kui kõrgeima prioriteediga eesmärk ei ole täidetav (kuna mängija ei ole nähtav, ei suuda ükski tegevuste kombinatsioon luua plaani "hävitada mängijat"), pöördub tehisintellekt madalama prioriteediga eesmärkide juurde.

Koolitus ja kohandamine

Oleme juba maininud, et mängu tehisintellekt ei kasuta tavaliselt masinõpet, kuna see ei sobi reaalajas agentide juhtimiseks. Kuid see ei tähenda, et sellest valdkonnast midagi laenata ei saa. Me tahame, et laskmismängus oleks vastane, kellelt saab õppida. Näiteks teada parimad positsioonid kaardil. Või maadlusmängus, kus vastane blokeeriks tihti kasutatavaid mängijate kombotehnikaid, motiveerides kasutama teisi. Seega võib masinõpe sellistes olukordades olla väga kasulik.

Statistika ja tõenäosused

Enne kui liigume keerukate näidete juurde, arutame, kui kaugele me saame minna, tehes mõned lihtsad mõõtmised ja kasutades neid otsuste tegemiseks. Näiteks reaalajas strateegia — kuidas saame määrata, kas mängija suudab mängu esimestel minutitel rünnaku alustada ja millise kaitse selle vastu valmistada? Saame uurida mängija varasemaid kogemusi, et mõista, milline võib olla tema tulevane reaktsioon. Alguses ei ole meil selliseid algandmeid, kuid me saame neid koguda — iga kord, kui IA mängib inimese vastu, saab ta registreerida esimese rünnaku aja. Pärast mitmeid seansse saame keskmise aja, mille jooksul mängija tulevikus ründab.

Keskmiste väärtustega on aga probleem: kui mängija 20 korda „kiirusest” mängib ja 20 korda aeglaselt, siis vajalikud väärtused asuvad kuskil keskel, mis ei paku meile midagi kasulikku. Üks lahendus on sisendandmete piiramine - saame arvesse võtta viimased 20 juhtumit.

Sarnast lähenemist kasutatakse teatud tegevuste 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 üks kord lähivõitlusena, on ilmselge, et ta eelistab tulepalli. Ekstrapoleerime ja näeme erineva relvastuse 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.

Teine huvitav meetod on kasutada Naive Bayes Classifier (naivne Bayesi klassifikaator) suurte andmemahtude uurimiseks ja olukorra klassifitseerimiseks, et tehisintellekt saaks õigesti reageerida. Bayesi klassifikaatoreid tuntakse enim e-kirjade rämpsposti filtrite kasutamise tõttu. Need uurivad sõnu, võrreldes neid varasemate esinemistega (kas rämpspostis või mitte) ja teevad järeldusi saabuvate kirjade kohta. Saame sama teha, isegi väiksema sisendi hulgaga. Kõikide kasulike andmete põhjal, mida tehisintellekt näeb (näiteks milliseid vaenulikke üksusi on loodud, milliseid loitse kasutatakse või milliseid tehnoloogiaid uuritakse) ja lõpptulemus (sõda või rahu, „ründamine” või kaitsmine jne) — valime tehisintellekti jaoks sobiva käitumise.

Kõik need õppeviisid on piisavad, kuid soovitatav on kasutada neid testimise käigus kogutud andmete põhjal. Tehisintellekt õpib kohanduma erinevate strateegiatega, mida on kasutanud teie mängijate testijad. Tehisintellekt, mis kohandub mängijaga pärast väljaandmist, võib muutuda liiga ettearvatavaks või vastupidi, liiga raskeks võita.

Kohandamine väärtuste põhjal

Arvestades meie mängumaailma ja reeglite täitmist, saame muuta väärtuste kogumit, mis mõjutab otsuste tegemist, mitte lihtsalt kasutada sisendandmeid. Teeme nii:

• Lubame tehisintellektil koguda andmeid maailma seisundist ja olulistest sündmustest mängu ajal (nagu ülalpool kirjeldatud).
• 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 agent saab valida mitme toa vahel esmaklassilise tulistamismängu kaardil. Igal toal on oma value, mis määrab, kui soovitav see külastamiseks on. Tehisintellekt valib juhuslikult, millisesse tuppa minna, lähtudes value'ist. Seejärel mäletab agent, millises toas ta tapeti, ja vähendab selle value't (tõenäosust, et ta sinna tagasi pöördub). Sama kehtib vastupidise olukorra puhul — kui agent hävitab palju vastaseid, siis toa value suureneb.

Markovi mudel

Kuidas oleks, kui kasutaksime kogutud andmeid prognoosimiseks? Kui märkida iga toa, kus näeme mängijat teatud aja jooksul, siis oskame prognoosida, millisesse tuppa mängija võib minna. Jälgides ja salvestades mängija liikumisi tubades (values), saame neid ennustada.

Võtame kolm tuba: punane, roheline ja sinine. Samuti vaatame tähelepanekuid, mida oleme kogunud mängu sessiooni jälgimise käigus:

Iga toa jälgimise arv on peaaegu ühesugune - kus luua hea peidupaik, me ikka veel ei tea. Statistika kogumist raskendab ka mängijate respawn, kes ilmuvad kaardil ühtlaselt. Kuid andmed järgmise toa kohta, kuhu nad pärast kaardile ilmumist sisenevad, on juba kasulikud.

On näha, et roheline tuba meeldib mängijatele - enamus punase toa inimesi liigub sinna, kellest 50% jääb sinna edasi. Sinine tuba on vastupidiselt ebaõnnestunud, sinna peaaegu ei minda, aga kui minnakse, siis ei peeta seal kaua aega.

Kuid andmed räägivad meile midagi veel olulisemat — kui mängija viibib sinises toas, on järgmine tuba, kus me teda tõenäoliselt näeme, punane, mitte roheline. Kuigi roheline tuba on populaarsem kui punane, muutub olukord sinises toas viibides. Järgmine seisund (st tuba, kuhu mängija liigub) sõltub eelnevast seisundist (st toast, kus mängija hetkel viibib). Seoste uuringu tõttu saame teha täpsemaid prognoose, kui kui arvutaksime vaatlusandmeid iseseisvalt.

Mine minevikus toimunud andmete põhjal tuleviku seisundi ennustamist nimetatakse Markovi mudeliks (Markov model), ning selliseid näiteid (tubadega) nimetatakse Markovi ahelateks. Kuna mudelid esindavad tõenäosust muutuste vahel järjestikustes seisundites, kuvatakse need visuaalselt FSM-ina, kus iga üleminekuga kaasneb tõenäosus. Varem oleme kasutanud FSM-i agendi käitumisseisundi esitlemiseks, kuid see kontseptsioon laieneb kõikidele seisunditele, olenemata sellest, kas need on seotud agendiga või mitte. Sellisel juhul esindavad seisundid tuba, kus agent viibib:

See on lihtne variant suhtepärase tõenäosuse muutuste esitlemiseks, andes AI-le võimaluse ennustada järgmist seisundit. Saame ennustada mitmeid samme ette.

Kui mängija on rohelises toas, on 50% tõenäosus, et ta jääb sinna ka järgmisel vaatlusel. Aga kui suur on tõenäosus, et ta on seal isegi pärast seda? On olemas mitte ainult tõenäosus, et mängija jäi rohelisse tuppa pärast kahte vaatlust, vaid ka võimalus, et ta lahkus ja tuli tagasi. Siin on uus tabel, mis arvestab uusi andmeid:

Sellest nähtub, et tõenäosus näha mängijat rohelises toas pärast kahte vaatlust on 51% — 21%, et ta tuli punasest toast, 5% sellest, 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 igas etapis. See tähendab, et saate vaadata kaugele tulevikku, ühe reservatsiooniga: me eeldame, et sisenemise võimalus ruumi sõltub täielikult praegusest ruumist. Seda nimetatakse Markovi omaduseks (Markov Property) - tulevane seisund sõltub ainult olevikust. Kuid see ei ole 100% täpne. Mängijad võivad teha otsuseid sõltuvalt muudest teguritest: tervise tasemest või muude laskemoona kogusest. Kuna me neid väärtusi ei fikseeri, on meie prognoosid vähem täpsed.

N-Gramid

Aga mis saab näiteks näitest võitlusmängust ja mängija kombo-move ennustamisest? Sama asi! Kuid ühe seisundi või sündmuse asemel uurime terveid järjestusi, millest kombo-löök koosneb.

Üks viis seda teha on salvestada iga sisend (nt Kick, Punch või Block) vahemuisti ja salvestada kogu vahemälu ühe sündmusena. Nii et mängija vajutab korduvalt Kick, Kick, Punch, et kasutada rünnakut SuperDeathFist, AI süsteem salvestab kõik sisendid vahemuisti ja mäletab viimaseid kolme, mida kasutatakse igas etapis.

(Rasvīti rādījumi tiek parādīti, kad spēlētājs uzsāk SuperDeathFist uzbrukumu.)

Mākslīgais intelekts redzēs visas iespējas, kad spēlētājs izvēlas Kick, pēc tam vēl vienu Kick, un beigās pamanīs, ka nākamais ievads vienmēr ir Punch. Tas ļaus aģentam prognozēt SuperDeathFist kombinācijas un bloķēt to, ja tas ir iespējams.

Šīs notikumu secības sauc par N-gramām, kur N ir saglabāto elementu skaits. Iepriekšējā piemērā tas bija 3-grama (trigramma), kas nozīmē: pirmās divas ieraksti tiek izmantoti, lai prognozētu trešo. Tādējādi 5-gramā pirmie četri ieraksti paredz piekto un tā tālāk.

Izstrādātājam rūpīgi jāizvēlas N-gramu izmērs. Mazāks N skaits prasa mazāk atmiņas, bet arī glabā mazāku vēsturi. Piemēram, 2-grama (bigramma) pierakstīs Kick, Kick vai Kick, Punch, bet nespēs uzglabāt Kick, Kick, Punch, tādēļ mākslīgais intelekts nereaģēs uz SuperDeathFist kombināciju.

Teiselt poolt nõuavad suured numbrid rohkem mälu ning AI-l on keerulisem õppida, kuna võimalike variantide arv suureneb oluliselt. Kui teil oli kolm võimalikku sisendit: Kick, Punch või Block, ja me kasutasime 10-grammi, siis saame umbes 60 tuhat erinevat varianti.

Bigrammimudel on lihtne Markovi ahel — iga paar "eelmine seisund/praegune seisund" on bigramm, ning saate ennustada teist seisundit esimese põhjal. 3-grammid ja suuremad N-grammid võib samuti käsitleda kui Markovi ahelaid, kus kõik elemendid (välja arvatud viimane N-grammis) koos moodustavad esimese seisundi, ja viimane element — teise. Näide võitlusmängust näitab ülemineku võimalust olukorrast Kick ja Kick olukorda Kick ja Punch. Vaadates mitmeid sisendi ajalugu kirjeid kui ühtset üksust, muudame sisendisegu põhimõtteliselt osaks terviklikust seisundist. See annab meile Markovi omaduse, mis võimaldab kasutada Markovi ahelaid järgmise sisendi ennustamiseks ja arvata, milline kombo käik järgmiseks tuleb.

Kokkuvõte

Rääkisime kõige levinumatest tööriistadest ja lähenemistest tehisintellekti arendamisel. Samuti vaatasime üle olukorrad, kus neid tuleks rakendada ja kus need eriti kasulikud on.

Seda peaks olema piisavalt, et mõista põhiteemasid mängu tehisintellektis. Kuid see ei ole muidugi kaugeltki kõik meetodid. Vähem tuntud, kuid mitte vähem efektiivsed on:

• optimeerimisalgoritmid, sealhulgas mäest üles ronimine, gradientne allakäik ja geneetilised algoritmid
• konkurentsi otsingu/planeerimise algoritmid (minimax ja alfa-beeta kärpimine)
• klassifitseerimismeetodid (perceptroonid, närvivõrgud ja tugivektorite masinad)
• agentide tajumise ja mälu töötlemise süsteemid
• tehisintellekti arhitektuuri lähenemised (hübriidsüsteemid, arhitektuuride alamhulged ja muud tehisintellekti süsteemide ülevõtmise viisid)
• animatsioonitööriistad (liikumise planeerimine ja sünkroniseerimine)
• toimefaktorid (detailide tase, anytime algoritmid ja timeslicing)

Teemaga seotud Interneti-ressursid:

1. GameDev.net-l on osi artiklite ja õpetustega tehisintellekti kohta, samuti projekti foorum,.
2. AiGameDev.com pakub palju esitlusi ja artikleid laia valiku mängu tehisintellekti arendamisega seotud teemadel.
3. GDC Vault sisaldab GDC AI tippseminari teemasid, millest paljusid on tasuta saadaval.
4. Kasulikke materjale leiate ka veebisaidilt AI Mängu Arendajate Gild.
5. Tommy Thompson, tehisintellekti teadlane ja mänguarendaja, teeb YouTube'i kanalis videoid AI ja Mängud selgitustega ja tehisintellekti uurimisega kommerts mängudes.

Teemaga seotud raamatud:

1. Game AI Pro raamatute seeria koosneb lühikesi artikleid sisaldavatest kogumikest, mis selgitavad, kuidas rakendada konkreetseid funktsioone või kuidas lahendada konkreetseid probleeme.

Game AI Pro: Kogutud Tarkus Mängu AI Professionaalidelt
Game AI Pro 2: Kogutud Tarkus Mängu AI Professionaalidelt
Game AI Pro 3: Kogutud Tarkus Mängu AI Professionaalidelt

2. AI Mängu Programmeerimise Tarkuse seeria — eelkäija Game AI Pro seeriale. Seal on vanemaid meetodeid, kuid peaaegu kõik on tänapäevani aktuaalsed.

AI Mängu Programmeerimise Tarkus 1
AI Mängu Programmeerimise Tarkus 2
AI Mängu Programmeerimise Tarkus 3
AI Mängu Programmeerimise Tarkus 4

3. Tehisintellekt: Kaasaegne Lähenemine — on üks põhiteoseid kõikidele, kes soovivad mõista tehisintellekti laiemat valdkonda. See raamat ei käsitle mängu arendamist — see õpetab tehisintellekti põhialuseid.

Allikas: habr.com