Jolasetan adimen artifizialari buruzko material interesgarri bat topatu nuen. Adibide errazak erabiliz AIri buruzko oinarrizko gauzen azalpenarekin, eta barruan tresna eta metodo erabilgarriak daude bere garapen eta diseinu erosoa egiteko. Nola, non eta noiz erabili ere hor dago.
Adibide gehienak pseudokodean idatzita daude, beraz, ez da programazio ezagutza aurreratu beharrik. Ebakiaren azpian 35 testu orri daude irudiekin eta gifekin, beraz, prest.
UPD. Barkatu, baina dagoeneko egin dut nire itzulpena HabrΓ©-ri buruzko artikulu honena . Bere bertsioa irakur dezakezu , baina arrazoiren batengatik artikulua pasatu zait (bilaketa erabili dut, baina zerbait gaizki atera da). Eta jokoen garapenari eskainitako blog batean idazten ari naizenez, nire itzulpenaren bertsioa harpidedunentzat uztea erabaki nuen (puntu batzuk formatu ezberdinean daude, beste batzuk nahita utzi zituzten garatzaileen aholkuz).
Zer da AI?
Game AI objektu batek kokatutako baldintzen arabera egin behar dituen ekintzak aztertzen ditu. Hau "agente adimenduna" kudeaketa deritzo normalean, non agente bat jokalari pertsonaia bat den, ibilgailu bat, bot bat edo batzuetan zerbait abstraktuagoa den: entitate talde oso bat edo baita zibilizazio bat ere. Kasu bakoitzean, bere ingurunea ikusi behar duen gauza bat da, horren arabera erabakiak hartu eta horien arabera jokatu behar duena. Honi Sentimendu/Pentsa/Ekin zikloa deritzo:
- Zentzumena: Agenteak bere portaeran eragina izan dezakeen bere inguruneko gauzei buruzko informazioa aurkitzen edo jasotzen du (inguruko mehatxuak, biltzeko elementuak, esploratzeko leku interesgarriak).
- Pentsa: agenteak erabakitzen du nola erreakzionatu (elementuak biltzea nahikoa segurua den edo aurrena borrokatu/ezkutatu behar duen kontuan hartzen du).
- Ekintza: agenteak aurreko erabakia gauzatzeko ekintzak burutzen ditu (etsaia edo objekturantz mugitzen hasten da).
- ...orain pertsonaien ekintzen ondorioz egoera aldatu da, beraz, zikloa datu berriekin errepikatzen da.
AI begiztaren Zentzumen zatian zentratu ohi da. Esaterako, auto autonomoek errepideko argazkiak ateratzen dituzte, radar eta lidar datuekin konbinatu eta interpretatzen dituzte. Hau normalean ikaskuntza automatikoaren bidez egiten da, sarrerako datuak prozesatzen dituena eta esanahia ematen diona, informazio semantikoa ateraz "beste auto bat 20 metro aurretik dago". Hauek dira sailkapen-arazoak deitzen direnak.
Jokuek ez dute sistema konplexurik behar informazioa ateratzeko, datu gehienak dagoeneko haren parte direlako. Ez dago zertan irudiak ezagutzeko algoritmoak exekutatu aurretik etsai bat dagoen zehazteko; jokoak dagoeneko ezagutzen du eta informazioa zuzenean elikatzen du erabakiak hartzeko prozesuan. Hori dela eta, zikloaren Zentzumena zatia Pentsatu eta Ekin atala baino askoz sinpleagoa da askotan.
Game AI-ren mugak
AI-ak hainbat muga ditu, kontuan hartu beharrekoak:
- AI ez da aldez aurretik trebatu behar, ikaskuntza automatikoko algoritmo bat balitz bezala. Ez du zentzurik garapenean zehar sare neuronal bat idazteak dozenaka milaka jokalari kontrolatzeko eta haien aurka jokatzeko modurik onena ikasteko. Zergatik? Jokoa ez delako kaleratu eta jokalaririk ez dagoelako.
- Jokoak dibertigarria eta erronka izan behar du, beraz, agenteek ez lukete jendearen aurkako hurbilketarik onena aurkitu behar.
- Agenteek errealistak izan behar dute, jokalariek benetako jendearen aurka jokatzen ari direla senti dezaten. AlphaGo programak gizakiak gainditzen zituen, baina aukeratutako pausoak jokoaren ulermen tradizionaletik oso urrun zeuden. Jokoak giza aurkari bat simulatzen badu, sentimendu hori ez litzateke existitu behar. Algoritmoa aldatu egin behar da erabaki sinesgarriak har ditzan idealak baino.
- AI denbora errealean funtzionatu behar du. Horrek esan nahi du algoritmoak ezin duela CPUaren erabilera monopolizatu denbora luzez erabakiak hartzeko. Nahiz eta 10 milisegundo luzeegia da, joko gehienek 16 eta 33 milisegundo baino ez baitute behar prozesatu guztia egiteko eta hurrengo marko grafikora pasatzeko.
- Egokiena, sistemaren zati bat gutxienez datuetan oinarrituta egon beharko litzateke, kodetzaileak ez direnek aldaketak egin ditzaten eta doikuntzak azkarrago gerta daitezen.
Ikus ditzagun Zentzua/Pentsa/Ekintza ziklo osoa hartzen duten AI ikuspegiak.
Oinarrizko Erabakiak hartzea
Has gaitezen joko errazenarekin - Pong. Helburua: mugitu pala, baloia berarengandik errebota egin dezan, haren ondotik hegan egin beharrean. Tenisa bezalakoa da, non baloia jotzen ez baduzu galtzen duzun. Hemen AIak nahiko lan erraza du: plataforma zein norabidetan mugitu erabakitzea.
Baldintzazko adierazpenak
Pong-eko AIrentzat, irtenbiderik agerikoena plataforma beti pilotaren azpian jartzen saiatzea da.
Horretarako algoritmo sinple bat, pseudokodean idatzita:
marko/eguneratze bakoitza jokoa martxan dagoen bitartean:
pilota palaren ezkerrean badago:
mugitu pala ezkerrera
bestela, pilota palaren eskuinaldean badago:
mugitu pala eskuinera
Plataforma baloiaren abiaduran mugitzen bada, hau da Pong-eko AIrako algoritmo aproposa. Ez dago ezer konplikatu beharrik agentearentzat hainbeste datu eta ekintza posiblerik ez badago.
Planteamendu hau hain da sinplea, ezen Zentzumen/Pentsatu/Egin ziklo osoa apenas nabaritzen dela. Baina hor dago:
- Zentzua zatia bi if adierazpenetan dago. Jokoak badaki non dagoen pilota eta non dagoen plataforma, beraz, AI-ak informazio hori bilatzen du.
- Think zatia bi if adierazpenetan ere sartzen da. Bi irtenbide biltzen dituzte, kasu honetan elkarren artean baztertzen direnak. Ondorioz, hiru ekintzetako bat hautatzen da: mugitu plataforma ezkerrera, mugitu eskuinera edo ez egin ezer behar bezala kokatuta badago.
- Egiteko atala Mugitu paleta ezkerrera eta Mugitu paleta eskuinera adierazpenetan aurkitzen da. Jokoaren diseinuaren arabera, plataforma berehala edo abiadura zehatz batean mugi dezakete.
Horrelako planteamendu erreaktiboak deitzen dira - arau multzo sinple bat dago (kasu honetan kodean adierazpenak badira) munduaren egungo egoerari erreakzionatzen eta neurriak hartzen dituztenak.
Erabakien zuhaitza
Pong-en adibidea erabakien zuhaitza izeneko AI kontzeptu formal baten baliokidea da. Algoritmoa bertatik igarotzen da "hosto" batera iristeko, zer ekintza egin behar den erabakitzeko.
Egin dezagun gure plataformaren algoritmorako erabakien zuhaitzaren bloke-diagrama:
Zuhaitz zati bakoitzari nodo deitzen zaio - AI-ak grafoen teoria erabiltzen du egitura horiek deskribatzeko. Bi nodo mota daude:
- Erabaki-nodoak: baldintzaren bat probatzean oinarritutako bi alternatiben artean aukeratzea, non alternatiba bakoitza nodo bereizi gisa adierazten den.
- Amaierako nodoak: azken erabakia adierazten duen egin beharreko ekintza.
Algoritmoa lehen nodotik abiatzen da (zuhaitzaren "errotik"). Edo erabakitzen du zein haur-nodotara joan behar den, edo nodoan gordetako ekintza exekutatzen du eta irteten da.
Zein da erabaki-zuhaitz batek aurreko ataleko if adierazpenen lan bera egiteak? Sistema orokor bat dago hemen, non erabaki bakoitzak baldintza bakarra eta bi emaitza posible dituen. Horri esker, garatzaileak AI sor dezake zuhaitz batean erabakiak adierazten dituzten datuetatik abiatuta, gogor kodetu behar izan gabe. Aurkez dezagun taula moduan:
Kodearen aldean kateak irakurtzeko sistema bat lortuko duzu. Sortu nodo bat horietako bakoitzerako, konektatu erabaki-logika bigarren zutabean oinarrituta eta haurrak hirugarren eta laugarren zutabetan oinarrituta. Baldintzak eta ekintzak programatu behar dituzu oraindik, baina orain jokoaren egitura konplexuagoa izango da. Hemen erabaki eta ekintza gehigarriak gehitzen dituzu, eta gero pertsonalizatu AI osoa zuhaitzaren definizioko testu fitxategia editatuz. Ondoren, fitxategia joko-diseinatzaileari transferituko diozu, honek jokabidea alda dezake jokoa berriro konpilatu edo kodea aldatu gabe.
Erabaki-zuhaitzak oso erabilgarriak dira adibide multzo handi batetik automatikoki eraikitzen direnean (adibidez, ID3 algoritmoa erabiliz). Horri esker, lortutako datuen arabera egoerak sailkatzeko tresna eraginkor eta errendimendu handikoak dira. Hala ere, eragileek ekintzak hautatzeko sistema soil batetik haratago goaz.
Eszenatokiak
Aurrez sortutako baldintzak eta ekintzak erabiltzen zituen erabaki-zuhaitz sistema bat aztertu dugu. AI diseinatzen duen pertsonak nahi duen moduan antola dezake zuhaitza, baina hala ere dena programatu duen kodetzailean fidatu behar du. Zer gertatzen da diseinatzaileari bere baldintzak edo ekintzak sortzeko tresnak emango bagenio?
Programatzaileak Is Ball Left Of Paddle eta Is Ball Right Of Paddle baldintzetarako kodea idatzi behar izan ez dezan, diseinatzaileak balio horiek egiaztatzeko baldintzak idatziko dituen sistema bat sor dezake. Orduan, erabaki-zuhaitzaren datuak honelakoak izango dira:
Funtsean, lehenengo taulan dagoen berdina da, baina bere baitan soluzioek bere kodea dute, if adierazpen baten baldintzapeko zatiaren antzekoa. Kodearen aldetik, erabaki-nodoen bigarren zutabean irakurriko litzateke, baina exekutatzeko baldintza zehatz bat bilatu beharrean (Paddle-n Ball Left Of), baldintzazko adierazpena ebaluatzen du eta horren arabera egia ala gezurra itzultzen du. Hau Lua edo Angelscript gidoi hizkuntza erabiliz egiten da. Horiek erabiliz, garatzaile batek bere jokoan objektuak hartu ditzake (baloia eta pala) eta gidoian eskuragarri egongo diren aldagaiak sortu (ball.position). Gainera, gidoi-lengoaia C++ baino sinpleagoa da. Ez du konpilazio fase osoa behar, beraz, jokoaren logika azkar doitzeko aproposa da eta "kodetzaileak ez direnek" beharrezko funtzioak sortzeko aukera ematen die.
Goiko adibidean, gidoi-lengoaia baldintzazko adierazpena ebaluatzeko bakarrik erabiltzen da, baina ekintzetarako ere erabil daiteke. Adibidez, Move Paddle Right datuak script-adierazpen bat bihur daitezke (ball.position.x += 10). Ekintza gidoian ere definitu dadin, Move Paddle Right programatu beharrik gabe.
Harago joan zaitezke eta erabaki-zuhaitz osoa idazteko gidoi-lengoaia batean idatz dezakezu. Hau kode gogorra izango da baldintzapeko adierazpenen moduan, baina kanpoko script fitxategietan kokatuko dira, hau da, programa osoa birkonpilatu gabe alda daitezke. Askotan edita dezakezu script fitxategia jokatzeko garaian AI erantzun desberdinak azkar probatzeko.
Gertaera Erantzuna
Goiko adibideak ezin hobeak dira Pongentzat. Etengabe exekutatzen dute Zentzu/Pentsatu/Ekin zikloa eta munduko azken egoeran oinarrituta jarduten dute. Baina joko konplexuagoetan gertaera indibidualen aurrean erreakzionatu behar duzu, eta ez dena aldi berean ebaluatu. Pong kasu honetan jada adibide txarra da. Aukera dezagun beste bat.
Imajinatu jaurtitzaile bat non etsaiak geldirik dauden jokalaria detektatu arte, eta horren ostean bere "espezializazioa"ren arabera jokatzen dute: norbait korrika joango da "presaka", norbaitek urrunetik erasoko du. Oinarrizko sistema erreaktibo bat da oraindik - "jokalari bat ikusten bada, egin zerbait" - baina logikoki Jokalari Ikusitako gertaera eta Erreakzio batean bana daiteke (hautatu erantzun bat eta exekutatu).
Honek Sentimendu/Pentsa/Ekin ziklora garamatza. AI-ak erreproduzitzailea ikusten duen ala ez egiaztatuko duen Sense zati bat kodetu dezakegu. Hala ez bada, ez da ezer gertatzen, baina ikusten badu, Player Seen gertaera sortzen da. Kodeak atal bereizi bat izango du, "Jokalari ikusitako gertaera gertatzen denean, egin" esaten duena, non Pentsatu eta Ekin atalei aurre egiteko behar duzun erantzuna. Horrela, erreakzioak ezarriko dituzu Player Seen gertaeraren aurrean: "lasai" pertsonaiarentzat - ChargeAndAttack, eta frankotiratzailearentzat - HideAndSnipe. Erlazio hauek datu-fitxategian sor daitezke, bizkor editatzeko, birkonpilatu beharrik gabe. Hemen ere scripting lengoaia erabil daiteke.
Erabaki zailak hartzea
Erreakzio-sistema sinpleak oso indartsuak diren arren, egoera asko daude nahikoa ez diren. Batzuetan, eragileak egiten ari denaren arabera erabaki desberdinak hartu behar dituzu, baina zaila da hori baldintza gisa imajinatzea. Batzuetan baldintza gehiegi daude erabakien zuhaitz edo gidoi batean eraginkortasunez irudikatzeko. Batzuetan, egoera nola aldatuko den aldez aurretik baloratu behar duzu hurrengo urratsa erabaki aurretik. Arazo horiek konpontzeko ikuspegi sofistikatuagoak behar dira.
Egoera finituko makina
Egoera finituetako makina edo FSM (egoera finituko makina) gure agentea gaur egun egoera posibleetako batean dagoela esateko modu bat da, eta egoera batetik bestera igaro daitekeela. Badaude halako estatu kopuru bat, hortik datorkio izena. Bizitzako adibiderik onena semaforoa da. Leku ezberdinetan argi-sekuentzia desberdinak daude, baina printzipioa berdina da - egoera bakoitzak zerbait adierazten du (gelditu, ibili, etab.). Semaforoa une bakoitzean egoera bakarrean dago, eta batetik bestera mugitzen da arau sinpleetan oinarrituta.
Antzeko istorioa da jokoetan NPCekin. Adibidez, har dezagun guardia bat egoera hauek dituen:
- Patruila.
- Erasoa.
- Ihes egiten.
Eta egoera aldatzeko baldintza hauek:
- Guardiak etsaia ikusten badu, eraso egiten du.
- Guardiak eraso egiten badu, baina etsaia gehiago ikusten ez badu, patruilara itzuliko da.
- Guardia batek eraso egiten badu baina oso zaurituta badago, ihes egiten du.
Halaber, if-adierazpenak idatz ditzakezu tutorearen egoera aldagai batekin eta hainbat egiaztapenekin: gertu dagoen etsairik, zein den NPCren osasun-maila, etab. Gehi ditzagun egoera batzuk:
- Idleness - patruila artean.
- Bilatzen - nabaritutako etsaia desagertu denean.
- Laguntza aurkitzea - ββetsaia ikusten denean, baina indartsuegia denean bakarrik borrokatzeko.
Horietako bakoitzaren aukera mugatua da; adibidez, zaindaria ez da ezkutuko etsai baten bila joango osasun baxua badu.
Azken finean, "baldin" zerrenda handi bat dago , Hori "astunegi bihur daiteke, beraz, estatuen arteko trantsizioak kontuan edukitzea ahalbidetzen duen metodo bat formalizatu behar dugu. Horretarako, estatu guztiak hartzen ditugu kontuan, eta estatu bakoitzaren azpian zerrenda batean idazten ditugu beste estatu batzuetarako trantsizio guztiak, horretarako beharrezkoak diren baldintzekin batera.
Hau egoera trantsizio taula bat da - FSM irudikatzeko modu integrala. Marraz dezagun diagrama bat eta lortu NPCren portaera nola aldatzen den ikuspegi osoa.
Diagramak egungo egoeraren arabera eragile honen erabakiak hartzeko funtsa islatzen du. Gainera, gezi bakoitzak estatuen arteko trantsizio bat erakusten du ondoan dagoen baldintza egiazkoa bada.
Eguneratze bakoitzean agentearen uneko egoera egiaztatzen dugu, trantsizioen zerrendan begiratu eta trantsiziorako baldintzak betetzen badira, egoera berria onartzen du. Esate baterako, fotograma bakoitzak 10 segundoko tenporizadorea iraungi den ala ez egiaztatzen du, eta, hala bada, zaintzailea Idling egoeratik Patrolling-era igarotzen da. Era berean, Eraso-egoerak agentearen osasuna egiaztatzen du; baxua bada, Ihes-egoerara joaten da.
Hau estatuen arteko trantsizioak kudeatzea da, baina zer gertatzen da estatuekin beraiekin lotutako portaerarekin? Egoera jakin baterako benetako portaera ezartzeari dagokionez, normalean bi "kako" mota daude, non ekintzak esleitzen dizkiogun FSMri:
- Egungo egoerarako aldian-aldian egiten ditugun ekintzak.
- Egoera batetik bestera igarotzean egiten ditugun ekintzak.
Lehenengo motako adibideak. Patrullatze-egoerak agentea patruila-ibilbidean zehar mugituko du fotograma bakoitzean. Eraso-egoera eraso bat hasten saiatuko da fotograma edo trantsizio bakoitzean hori posible den egoera batera.
Bigarren motarako, kontuan hartu trantsizioa "etsaia ikusgai badago eta etsaia indartsuegia bada, orduan joan Laguntza aurkitzeko egoerara. Agenteak laguntza eskatzeko nora jo behar duen aukeratu eta informazio hori gorde behar du, Aurkitzeko Laguntza egoerak jakin dezan nora joan. Laguntza aurkitu ondoren, agentea Eraso egoerara itzultzen da. Une honetan, aliatuari mehatxuaren berri eman nahi izango dio, beraz, NotifyFriendOfThreat ekintza gerta daiteke.
Berriro ere, sistema hau Sentitu/Pentsa/Ekin zikloaren lentetik begiratu dezakegu. Zentzua trantsizio-logikak erabiltzen dituen datuetan gorpuzten da. Pentsa - trantsizioak eskuragarri daude estatu bakoitzean. Eta Acta estatu baten barruan edo estatuen arteko trantsizioetan aldian-aldian egiten diren ekintzen bidez gauzatzen da.
Batzuetan trantsizio-baldintzak etengabe galdetzea garestia izan daiteke. Adibidez, agente bakoitzak fotograma bakoitzean kalkulu konplexuak egiten baditu etsaiak ikusi ditzakeen eta Patrullatzetik Eraso egoerara igaro daitekeen ala ez jakiteko, CPU denbora asko beharko du horrek.
Munduaren egoeraren aldaketa garrantzitsuak gertatzen diren heinean prozesatu egingo diren gertakaritzat har daitezke. FSMk trantsizio-baldintza egiaztatu beharrean "nire agenteak erreproduzitzailea ikusi al dezake?" fotograma guztietan, sistema bereizi bat konfiguratu daiteke maiz gutxiago egiaztatzeko (adibidez, 5 aldiz segundoko). Eta emaitza da Player Seen jaulkitzea txekea gainditzen denean.
Hau FSMra pasatzen da, eta orain Player Seen gertaera jasotako baldintzara joan beharko luke eta horren arabera erantzun. Ondorioz, portaera berdina da erantzunaren aurreko atzerapen ia hautemanezin bat izan ezik. Baina errendimendua hobetu da Sense zatia programaren zati bereizi batean banatzearen ondorioz.
Egoera finituko makina hierarkikoa
Hala ere, FSM handiekin lan egitea ez da beti komenigarria. Eraso-egoera zabaldu nahi badugu MeleeAttacking eta RangedAttacking bereizteko, Eraso-egoera (oraingoa eta etorkizuna) eramaten duten beste egoera guztien trantsizioak aldatu beharko ditugu.
Seguruenik konturatu zara gure adibidean trantsizio bikoiztu asko daudela. Idling egoerako trantsizio gehienak Patrolling egoeran dauden trantsizioen berdinak dira. Polita litzateke geure burua ez errepikatzea, batez ere antzeko egoera gehiago gehitzen baditugu. Zentzuzkoa da Idling eta Patrolling "ez-borroka" etiketa orokorraren pean biltzea, non estatuei aurre egiteko trantsizio multzo komun bakarra dagoen. Etiketa hau egoera gisa pentsatzen badugu, Idling eta Patrolling azpi-estatu bihurtzen dira. Borroka ez den azpiestatu berri baterako trantsizio-taula bereizi bat erabiltzearen adibide bat:
Estatu nagusiak:
Borrokatik kanpo:
Eta diagrama moduan:
Sistema bera da, baina borrokarik gabeko egoera berri batekin, Idling eta Patrolling barne hartzen dituena. Egoera bakoitzak FSM bat daukan azpiestatuekin (eta azpiestatu hauek, aldi berean, beren FSM propioak dituztenak - eta abar behar duzun bitartean), Hierarchical Finite State Machine edo HFSM (hierarquical finite state machine) lortzen dugu. Borroka ez den egoera taldekatuz, trantsizio erredundante mordoa moztu dugu. Gauza bera egin dezakegu trantsizio komunak dituzten edozein estatu berrirekin. Esaterako, etorkizunean Erasoaren egoera MeleeAttacking eta MissileAttacking estatuetara zabaltzen badugu, elkarren artean trantsizioa egiten duten azpiestatuak izango dira etsaiarekiko distantziaren eta munizioaren erabilgarritasunaren arabera. Ondorioz, jokabide eta azpijokabide konplexuak gutxieneko trantsizio bikoiztuekin irudika daitezke.
Portaera zuhaitza
HFSMrekin, jokabideen konbinazio konplexuak era sinplean sortzen dira. Hala ere, zailtasun txiki bat dago trantsizio-arauen formako erabakiak hartzea egungo egoerarekin estu lotuta dagoela. Eta joko askotan hori da behar dena. Eta estatu hierarkia kontu handiz erabiltzeak trantsizio errepikapenen kopurua murriztu dezake. Baina batzuetan, edozein egoeratan zauden edozein egoeratan funtzionatzen duten arauak behar dituzu edo ia edozein estatutan aplikatzen direnak. Adibidez, agente baten osasuna % 25era jaisten bada, ihes egitea nahi izango duzu, borrokan, alferrik edo hizketan egon arren; egoera bakoitzari baldintza hau gehitu beharko diozu. Eta gero zure diseinatzaileak osasun-atalase baxua %25etik %10era aldatu nahi badu, berriro egin beharko da.
Egokiena, egoera honek βzer egoeratan egonβ erabakiak estatuetatik kanpo dauden sistema behar du, aldaketak leku bakarrean egiteko eta trantsizio-baldintzak ez ukitzeko. Hemen portaera zuhaitzak agertzen dira.
Horiek ezartzeko hainbat modu daude, baina funtsa berdina da gutxi gorabehera guztientzat eta erabakien zuhaitz baten antzekoa da: algoritmoa "erro" nodo batekin hasten da, eta zuhaitzak erabakiak edo ekintzak adierazten dituzten nodoak ditu. Hala ere, funtsezko desberdintasun batzuk daude:
- Nodoek hiru balioetako bat itzultzen dute orain: Arrakasta (lana amaituta badago), Huts egin (abiarazi ezin bada) edo Abian (oraindik exekutatzen ari bada eta azken emaitzarik ez badago).
- Ez dago erabaki-nodo gehiago bi alternatiben artean aukeratzeko. Horren ordez, Decorator nodoak dira, nodo seme-alaba dutenak. Arrakasta lortzen badute, beren seme-nodo bakarra exekutatuko dute.
- Ekintzak burutzen dituzten nodoek Exekutatzen duten balio bat ematen dute egiten ari diren ekintzak irudikatzeko.
Nodo multzo txiki hau konbinatu daiteke portaera konplexu ugari sortzeko. Imajina dezagun aurreko adibideko HFSM guardia portaera zuhaitz gisa:
Egitura honekin ez litzateke trantsizio nabarmenik egon behar Idling/Patrolling estatuetatik Erasoa edo beste edozein estatura. Etsaia ikusten bada eta pertsonaiaren osasuna baxua bada, exekuzioa Ihes-en nodoan geldituko da, aurretik exekutatzen ari zen nodoa edozein dela ere: patruilatzea, gelditzea, erasotzea edo beste edozein.
Portaera-zuhaitzak konplexuak dira: modu asko daude konposatzeko, eta dekoratzaileen eta nodo konposatuen konbinazio egokia aurkitzea zaila izan daiteke. Zuhaitza zenbat aldiz egiaztatu behar den galderak ere badaude: zati guztiak igaro nahi ditugu ala baldintzaren bat aldatu denean bakarrik? Nola gordetzen dugu nodoei dagokien egoera - nola dakigu 10 segundo inaktibo egon ginenean, edo nola dakigu zein nodo exekutatu ziren azken aldian, sekuentzia behar bezala prozesatu ahal izateko?
Horregatik inplementazio asko daude. Adibidez, sistema batzuek dekoratzaile-nodoak lerroko dekoratzaileekin ordezkatu dituzte. Dekoratzailearen baldintzak aldatzen direnean zuhaitza berriro ebaluatzen dute, nodoak batzen laguntzen dute eta aldizkako eguneraketak ematen dituzte.
Erabilgarritasunean oinarritutako sistema
Jolas batzuek mekanika ezberdin asko dituzte. Desiragarria da trantsizio-arau sinple eta orokorren onura guztiak jasotzea, baina ez nahitaez portaera-zuhaitz oso baten moduan. Aukera-multzo argia edo ekintza posibleen zuhaitza izan beharrean, errazagoa da ekintza guztiak aztertzea eta momentuan egokiena aukeratzea.
Erabilgarritasunean oinarritutako sistemak horretan lagunduko du. Sistema bat da, non agenteak hainbat ekintza dituen eta bakoitzaren erabilgarritasun erlatiboaren arabera zeintzuk egin behar dituen aukeratzen duen. Non erabilgarritasuna agenteak ekintza hori egitea garrantzitsua edo desiragarria den neurri arbitrarioa den.
Uneko egoeran eta ingurunean oinarritutako ekintza baten erabilgarritasun kalkulatua, agenteak beste egoera egokiena egiaztatu eta hauta dezake edozein unetan. Hau FSMren antzekoa da, trantsizioak egoera potentzial bakoitzaren estimazio baten bidez zehazten diren izan ezik, egungoa barne. Kontuan izan aurrera egiteko ekintzarik erabilgarriena aukeratzen dugula (edo geratzeko, dagoeneko amaitu badugu). Barietate gehiago lortzeko, zerrenda txiki batetik aukeraketa orekatua baina ausaz izan daiteke.
Sistemak erabilgarritasun-balioen tarte arbitrario bat esleitzen du, adibidez, 0tik (erabat desiragarria) 100era (erabat desiragarria). Ekintza bakoitzak balio honen kalkuluan eragina duten parametro batzuk ditu. Gure tutorearen adibidera itzuliz:
Ekintzen arteko trantsizioak anbiguoak dira: edozein estatuk beste edozeini jarraitu dezake. Ekintza-lehentasunak itzulitako erabilgarritasun-balioetan aurkitzen dira. Etsai bat ikusten bada, eta etsai hori indartsua bada, eta pertsonaiaren osasuna baxua bada, orduan bai Ihes egiteak bai FindingHelp-ek zero ez diren balio altuak itzuliko dituzte. Kasu honetan, FindingHelp beti izango da altuagoa. Era berean, borrokakoak ez diren jarduerak ez dira inoiz 50 baino gehiago itzultzen, beraz, beti izango dira borrokakoak baino baxuagoak. Hau kontuan hartu behar duzu ekintzak sortzeko eta haien erabilgarritasuna kalkulatzeko.
Gure adibidean, ekintzek balio konstante finko bat edo bi balio finkoetako bat itzultzen dute. Sistema errealistago batek balio sorta jarraitu batetik estimazio bat itzuliko luke. Esaterako, Ihes egiteko ekintzak erabilgarritasun-balio handiagoak ematen ditu agentearen osasuna baxua bada, eta Erasoko ekintzak etsaia indartsuegia bada. Hori dela eta, Ihes ekintzak Erasoa baino lehen hartzen du agenteak etsaia garaitzeko osasun nahikorik ez duela sentitzen duen edozein egoeratan. Horri esker, ekintzak edozein irizpideren arabera lehenetsi daitezke, ikuspegi hau portaera zuhaitza edo FSM bat baino malguagoa eta aldakorragoa bihurtuz.
Ekintza bakoitzak baldintza asko ditu programa kalkulatzeko. Gidoi-lengoaian edo formula matematikoen multzoan idatz daitezke. Sims-ek, pertsonaia baten eguneroko errutina simulatzen duenak, kalkulu-geruza gehigarri bat gehitzen du - agenteak erabilgarritasunen balorazioak eragiten dituzten "motibazio" sorta jasotzen du. Pertsonaia bat gose bada, are goseagoa izango da denborarekin, eta EatFood ekintzaren erabilgarritasun-balioa handituko da pertsonaiak gauzatu arte, gose maila murriztuz eta EatFood balioa zerora itzuliz.
Balorazio-sistema batean oinarritutako ekintzak hautatzeko ideia nahiko sinplea da, beraz, erabilgarritasunetan oinarritutako sistema bat AI erabakiak hartzeko prozesuen parte gisa erabil daiteke, haien ordezko osoa izan beharrean. Erabaki-zuhaitzek bi nodo umeren erabilgarritasun-balorazioa eska dezakete eta altuena hautatu. Era berean, portaera-zuhaitz batek Erabilgarritasun-nodo konposatu bat izan dezake ekintzen erabilgarritasuna ebaluatzeko zein ume exekutatu erabakitzeko.
Mugimendua eta nabigazioa
Aurreko adibideetan, ezkerrera edo eskuinera mugitzen genuen plataforma bat genuen, eta patruilatzen edo erasotzen zuen guardia bat. Baina nola kudeatzen dugu zehazki agenteen mugimendua denbora tarte batean? Nola ezartzen dugu abiadura, nola saihestu oztopoak eta nola planifikatzen dugu ibilbide bat helmuga batera iristea lerro zuzenean mugitzea baino zailagoa denean? Ikus dezagun hau.
kudeaketan
Hasierako fasean, agente bakoitzak abiadura-balio bat duela suposatuko dugu, eta horrek zenbaterainoko abiadura duen eta zein norabidetan mugitzen den barne hartzen du. Segunduko metrotan, orduko kilometrotan, segundoko pixeletan, etab. Sentenza/Pentsa/Egin begizta gogoratuz, pentsa genezake Think zatiak abiadura bat hautatzen duela, eta Act zatiak abiadura hori aplikatzen diola agenteari. Normalean jokoek zeregin hori egiten dizun sistema fisikoa dute, objektu bakoitzaren abiadura-balioa ikasiz eta hura egokituz. Hori dela eta, AI-a zeregin bakarrarekin utzi dezakezu agenteak zer abiadura izan behar duen erabakitzeko. Agentea non egon behar den badakizu, norabide egokian mugitu behar duzu abiadura ezarrita. Oso ekuazio hutsala:
nahi_bidaia = helmuga_posizioa β agente_posizioa
Imajinatu 2D mundu bat. Agentea (-2,-2) puntuan dago, helmuga ipar-ekialdeko nonbait dago (30, 20 puntuan), eta agenteak bertara heltzeko beharrezkoa den bidea (32, 22) da. Demagun posizio hauek metrotan neurtzen direla - agentearen abiadura segundoko 5 metrokoa dela hartzen badugu, orduan gure desplazamendu-bektorea eskalatuko dugu eta gutxi gorabehera (4.12, 2.83) abiadura lortuko dugu. Parametro horiekin, agentea ia 8 segundotan iritsiko litzateke helmugara.
Balioak edonoiz kalkula ditzakezu. Agentea helbururako erdibidean balego, mugimendua luzeraren erdia izango litzateke, baina agentearen abiadura maximoa 5 m/s denez (goian erabaki dugu hau), abiadura berdina izango da. Helburuak mugitzeko ere funtzionatzen du, agenteari aldaketa txikiak egiteko aukera emanez mugitzen diren bitartean.
Baina aldakuntza gehiago nahi dugu; adibidez, abiadura poliki-poliki handitzea zutik exekutatzen ari den pertsonaia bat simulatzeko. Amaieran gauza bera egin daiteke gelditu aurretik. Ezaugarri hauek gidatzeko jokabide gisa ezagutzen dira, eta horietako bakoitzak izen zehatzak ditu: Bilatu, Ihes, Iritsiera, etab. Ideia da agentearen abiadurari azelerazio-indarrak aplika daitezkeela, agentearen posizioa eta uneko abiadura helmugarekin alderatzean oinarrituta. helburura joateko metodo desberdinak erabiltzeko.
Jokabide bakoitzak helburu apur bat desberdina du. Seek eta Arrival agente bat helmuga batera eramateko bideak dira. Oztopoak saihestea eta bereiztea agentearen mugimendua doitzen du helbururako bidean oztopoak ekiditeko. Lerrokatzeak eta Kohesioak eragileek elkarrekin mugitzen dituzte. Gidatze-jokaera ezberdinen kopurua batu daiteke bide-bektore bakarra sortzeko, faktore guztiak kontuan hartuta. Iritsiera, Banaketa eta Oztopoak Saihesteko jokabideak hormetatik eta beste agenteetatik urrun egoteko erabiltzen dituen agentea. Planteamendu honek ondo funtzionatzen du leku irekietan alferrikako xehetasunik gabe.
Baldintza zailagoetan, jokabide desberdinak gehitzeak okerrago funtzionatzen du; adibidez, agente bat horma batean trabatu daiteke Arriskuaren eta Oztopoak Saihesteko gatazkaren ondorioz. Hori dela eta, balio guztiak gehitzea baino konplexuagoak diren aukerak kontuan hartu behar dituzu. Bidea hau da: jokabide bakoitzaren emaitzak batu beharrean, norabide ezberdinetako mugimendua kontuan hartu eta aukerarik onena hauta dezakezu.
Dena den, kale-muturrak eta zein bide hartu aukeratzen duen ingurune konplexu batean, are aurreratuagoa den zerbait beharko dugu.
Modu bat bilatu
Gidatze-jokabideak oso egokiak dira eremu ireki batean (futbol-zelaia edo zelaia) mugimendu errazetarako, non A-tik B-ra iristea bide zuzena den oztopoen inguruan saihesbide txikiak dituena. Ibilbide konplexuetarako, bidea bilatu behar dugu, hau da, mundua esploratzeko eta bertatik igarotzeko ibilbidea erabakitzeko modu bat.
Errazena agentearen ondoan dagoen lauki bakoitzari sareta bat aplikatzea da eta haietako zeintzuk mugitzeko baimena duten ebaluatzea da. Horietako bat helmuga bada, jarraitu lauki bakoitzetik aurrekorako ibilbidea hasierara iritsi arte. Hau da ibilbidea. Bestela, errepikatu prozesua inguruko beste karratuekin zure helmuga aurkitu arte edo laukirik gabe geratu arte (esan nahi du ez dagoela ibilbide posiblerik). Hau da, formalki, Breadth-First Search edo BFS (breadth-first search algorithm) izenez ezagutzen dena. Urrats bakoitzean norabide guztietara begiratzen du (beraz, zabalera, "zabalera"). Bilaketa-espazioa nahi den kokapenera iritsi arte mugitzen den uhin-fronte bat bezalakoa da - bilaketa-espazioa pauso bakoitzean zabaltzen da amaiera-puntua sartu arte, eta horren ondoren hasierara itzul daiteke.
Ondorioz, nahi duzun ibilbidea osatzen duten laukien zerrenda jasoko duzu. Hau da bidea (beraz, bide-bilaketa) - agenteak helmuga jarraitzen duen bitartean bisitatuko dituen lekuen zerrenda.
Munduko karratu bakoitzaren posizioa ezagutzen dugula kontuan hartuta, gidatzeko jokabideak erabil ditzakegu bidetik mugitzeko: 1. nodotik 2. nodora, gero 2. nodotik 3. nodora, eta abar. Aukerarik errazena hurrengo laukiaren erdialderantz joatea da, baina are hobeagoa oraingo karratuaren eta hurrengoaren arteko ertzaren erdian gelditzea da. Hori dela eta, agenteak bira zorrotzetan izkinak moztu ahal izango ditu.
BFS algoritmoak desabantailak ere baditu: noranzko "okerrean" noranzko "egokian" bezainbeste karratu aztertzen ditu. Hor sartzen da jokoan A* (A star) izeneko algoritmo konplexuagoa. Era berean funtzionatzen du, baina auzoko karratuak itsu-itsuan aztertu beharrean (gero auzokideen bizilagunak, gero auzokideen bizilagunak, eta abar), nodoak zerrenda batean biltzen ditu eta ordenatzen ditu, aztertutako hurrengo nodoa beti izan dadin. bide laburrenera doana. Nodoak bi gauza kontuan hartzen dituen heuristiko baten arabera ordenatzen dira: nahi den karraturako ibilbide hipotetiko baten "kostua" (bidaia-kostuak barne) eta karratu hori helmugatik noraino dagoen zenbatesteko (bilaketa alboratuz). norabide egokia).
Adibide honek erakusten du agenteak lauki bat arakatzen duela aldi berean, aldi bakoitzean itxaropentsuena den aldamenekoa aukeratuz. Ondorioz bidea BFSren berdina da, baina lauki gutxiago kontuan hartu ziren prozesuan, eta horrek eragin handia du jokoaren errendimenduan.
Sarerik gabeko mugimendua
Baina joko gehienak ez daude sare batean jarrita, eta askotan ezinezkoa da hori egitea errealismoari uko egin gabe. Konpromisoak behar dira. Zein tamaina izan behar dute karratuek? Handiegiak eta ezin izango dituzte ondo irudikatu korridore edo bira txikiak, txikiegiak eta lauki gehiegi izango dira bilatzeko, eta horrek, azken batean, denbora asko beharko du.
Ulertzen den lehenengo gauza sare batek konektatutako nodoen grafiko bat ematen digula da. A* eta BFS algoritmoek grafikoetan funtzionatzen dute eta ez zaie batere axola gure sareari. Jolas-munduko edozein lekutan jar genitzake nodoak: konektatutako bi nodoren artean konexioa dagoen bitartean, baita hasierako eta amaierako puntuen eta gutxienez nodoetako baten artean ere, algoritmoak lehen bezain ondo funtzionatuko du. Askotan bide-puntu-sistema deitzen zaio horri, nodo bakoitzak munduan posizio esanguratsu bat adierazten baitu, bide hipotetikoren zati bat izan daitekeena.
1. adibidea: korapilo bat lauki bakoitzean. Bilaketa agentea dagoen nodotik hasi eta nahi den karratuaren nodoan amaitzen da.
2. adibidea: nodo multzo txikiago bat (bide-puntuak). Bilaketa agentearen laukian hasten da, behar diren nodo kopurutik igarotzen da eta, ondoren, helmugara jarraitzen du.
Sistema guztiz malgua eta indartsua da. Baina arreta pixka bat behar da bide-puntu bat non eta nola jarri erabakitzeko, bestela, baliteke agenteek hurbileneko puntua ez ikustea eta ezingo dute bidea hasi. Errazagoa izango litzateke munduaren geometrian oinarritutako bide-puntuak automatikoki kokatuko bagenitu.
Bertan nabigazio-sarea edo navmesh (nabigazio-sarea) agertzen da. Hau, normalean, munduaren geometrian gainjartzen den triangeluen 2D sare bat da, agenteari ibiltzeko baimena ematen zaion lekuan. Sareko triangelu bakoitza grafikoan nodo bihurtzen da, eta grafikoan ondoko nodo bihurtzen diren hiru hiruki ondoko hiruki ditu.
Irudi hau Unity motorreko adibide bat da - munduko geometria aztertu zuen eta navmesh bat sortu zuen (pantaila-argazkian urdin argian). Navmesh bateko poligono bakoitza agente bat zutik edo poligono batetik beste poligono batera mugi daitekeen eremu bat da. Adibide honetan, poligonoak kokatuta dauden solairuak baino txikiagoak dira - agentearen tamaina kontuan hartzeko egiten da, bere posizio nominaletik haratago luzatuko dena.
Sare honen bidez ibilbide bat bilatu dezakegu, berriro A* algoritmoa erabiliz. Honek munduan ibilbide ia perfektua emango digu, geometria guztia kontuan hartzen duena eta alferrikako nodoak eta bide-puntuak sortzea behar ez duena.
Pathfinding gai zabalegia da eta artikulu baten atal bat nahikoa ez den. Xehetasun gehiagoz aztertu nahi baduzu, honek lagunduko dizu .
plangintza
Bidea bilatuz ikasi dugu batzuetan ez dela nahikoa norabide bat hautatzea eta mugitzea: ibilbide bat aukeratu eta buelta batzuk eman behar ditugu nahi dugun helmugara iristeko. Ideia hau orokortu dezakegu: helburu bat lortzea ez da hurrengo urratsa bakarrik, sekuentzia oso bat baizik, non batzuetan aurrera begira hainbat urrats egin behar diren lehenengoa zein izan behar den jakiteko. Horri plangintza deitzen zaio. Pathfinding plangintzaren hainbat luzapenetako bat dela pentsa daiteke. Gure Sentimendu/Pentsa/Ekintza zikloari dagokionez, hau da Pentsatu atalak etorkizunerako hainbat ekintza planifikatzen dituena.
Ikus dezagun Magic: The Gathering mahai-jokoaren adibidea. Lehenengo karta-sorta hau eskuetan goaz:
- Padura - Mana beltz 1 ematen du (lur-txartel).
- Basoa - mana berde 1 (lur karta) ematen du.
- Iheslarien morroia - mana urdin 1 behar da deitzeko.
- Elfish Mystic - mana berde 1 behar da deitzeko.
Gainerako hiru txartelei jaramonik egiten ez diegu errazago egiteko. Arauen arabera, jokalari batek lurrezko karta 1 jolastu dezake txanda bakoitzean, karta hau "kolpea" dezake bertatik mana ateratzeko, eta gero sorginkeriak egin (izaki bat deitzea barne) mana kopuruaren arabera. Egoera horretan, giza jokalariak badaki Forest jolasten, mana berde bat sakatu eta gero Elvish Mystic deitzen duela. Baina nola asmatu dezake AI jokoak hori?
Plangintza erraza
Planteamendu hutsala ekintza bakoitza txandaka probatzea da, egokirik geratzen ez den arte. Kartei begira, AI-k ikusten du Swamp-ek zer jokatu dezakeen. Eta jokatzen du. Txanda honetan geratzen al da beste ekintzarik? Ezin du dei egin ez Elfish Mystic edo Fugitive Wizard, hurrenez hurren mana berdea eta urdina behar baitituzte haiek deitzeko, Swamp-ek mana beltza soilik ematen duen bitartean. Eta aurrerantzean ezingo du Forest jokatu, dagoeneko Paduran jokatu duelako. Horrela, AI jokoak arauak jarraitu zituen, baina gaizki egin zuen. Hobetu daiteke.
Planning-ek jokoa nahi den egoerara eramaten duten ekintzen zerrenda aurki dezake. Bide bateko plaza bakoitzak bizilagunak zituen bezala (bide-bilaketan), plan bateko ekintza bakoitzak ere baditu auzokideak edo ondorengoak. Ekintza hauek eta ondorengo ekintzak bilatu ditzakegu nahi dugun egoerara iritsi arte.
Gure adibidean, nahi den emaitza "ahal bada izaki bat deitzea" da. Txanda hasieran, joko-arauek onartzen dituzten bi ekintza posible baino ez ditugu ikusten:
1. Jokatu Padura (emaitza: Padura jokoan)
2. Play Forest (emaitza: Forest jokoan)
Egindako ekintza bakoitzak ekintza gehiago egin ditzake eta beste batzuk itxi ditzake, berriro ere joko-arauen arabera. Imajinatu Paduran jokatu dugula: honek Padura kenduko du hurrengo urrats gisa (jokatu genuen jada), eta honek ere Basoa kenduko du (arauen arabera lurreko karta bat jokatu dezakezulako txanda bakoitzeko). Horren ondoren, AIak mana beltz 1 lortzea gehitzen du hurrengo urrats gisa, beste aukerarik ez dagoelako. Aurrera egiten badu eta Tap the Swamp aukeratzen badu, mana beltz unitate 1 jasoko du eta ezin izango du horrekin ezer egin.
1. Jokatu Padura (emaitza: Padura jokoan)
1.1 "Ukitu" padura (emaitza: padura "tapatua", + mana beltz unitate)
Ez dago ekintzarik erabilgarri - AMAITU
2. Play Forest (emaitza: Forest jokoan)
Ekintzen zerrenda laburra zen, bide hilera iritsi ginen. Prozesua errepikatuko dugu hurrengo urratserako. Forest jolasten dugu, "lortu mana berde 1" ekintza irekitzen dugu, eta horrek hirugarren ekintza irekiko du - Elvish Mystic deitu.
1. Jokatu Padura (emaitza: Padura jokoan)
1.1 "Ukitu" padura (emaitza: padura "tapatua", + mana beltz unitate)
Ez dago ekintzarik erabilgarri - AMAITU
2. Play Forest (emaitza: Forest jokoan)
2.1 "Ukitu" basoa (emaitza: basoa "tapatuta dago", + mana berdearen unitate)
2.1.1 Dei egin Elfish Mystic (emaitza: Elfish Mystic jokoan, -1 mana berde)
Ez dago ekintzarik erabilgarri - AMAITU
Azkenik, ekintza posible guztiak aztertu eta izaki bat deitzen duen plan bat aurkitu dugu.
Oso adibide sinplifikatua da. Komeni da ahalik eta plan onena aukeratzea, irizpide batzuk betetzen dituen edozein plan baino. Oro har, posible da balizko planak ebaluatzea haien ezarpenaren emaitza edo onura orokorraren arabera. Zeure buruari puntu 1 lor dezakezu lurreko karta bat jokatzeagatik eta 3 puntu izaki bat deitzeagatik. Padura jolastea puntu 1eko plana izango litzateke. Eta Basoa β Sakatu basoa β Elfish Mystic deitzearekin berehala 4 puntu emango ditu.
Horrela funtzionatzen du planifikazioak Magic: The Gathering-en, baina logika bera aplikatzen da beste egoera batzuetan. Esaterako, peoi bat mugitzea alpezpikuari xakean mugitzeko lekua egiteko. Edo estali horma baten atzean XCOM-en modu seguruan grabatzeko. Oro har, ideia jasotzen duzu.
Plangintza hobetua
Batzuetan, ekintza potentzial gehiegi daude aukera posible guztiak kontuan hartzeko. Magic: The Gathering-en adibidera itzuliz: demagun jokoan eta zure eskuan hainbat lur eta izaki karta daudela - mugimenduen konbinazio posibleen kopurua dozenaka izan daiteke. Hainbat irtenbide daude arazoari.
Lehenengo metodoa atzerantz kateatzea da. Konbinazio guztiak probatu beharrean, hobe da azken emaitzatik hastea eta bide zuzena bilatzen saiatzea. Zuhaitzaren errotik hosto zehatz batera joan beharrean, kontrako noranzkoan mugitzen gara hostotik errora. Metodo hau errazagoa eta azkarragoa da.
Etsaiak osasun 1 badu, "kalte bat edo gehiago egin" plana aurki dezakezu. Hori lortzeko, hainbat baldintza bete behar dira:
1. Kalteak sorginkeria batek eragin ditzake - eskuan egon behar du.
2. Sorginkeria bat egiteko, mana behar duzu.
3. Mana lortzeko, lurreko karta bat jokatu behar duzu.
4. Lurreko karta bat jokatzeko, eskuan izan behar duzu.
Beste modurik onena-lehen bilaketa da. Bide guztiak probatu beharrean, egokiena aukeratzen dugu. Gehienetan, metodo honek plan optimoa ematen du alferrikako bilaketa kosturik gabe. A* lehen bilaketa onena egiteko modua da - ibilbiderik itxaropentsuenak hasieratik aztertuz gero, biderik onena aurki dezake beste aukerarik egiaztatu beharrik gabe.
Lehen bilaketa-aukera interesgarri eta ezagunagoa da Monte Carlo Tree Search. Ondorengo ekintza bakoitza aukeratzerakoan zein plan diren beste batzuk baino hobeak asmatu beharrean, algoritmoak ausazko ondorengoak aukeratzen ditu urrats bakoitzean amaierara iritsi arte (planak garaipena edo porrota ekarri zuenean). Ondoren, azken emaitza aurreko aukeren pisua handitzeko edo gutxitzeko erabiltzen da. Prozesu hau hainbat aldiz jarraian errepikatuz, algoritmoak ondo estimatzen du zein den hurrengo mugimendu onena, nahiz eta egoera aldatu (etsaiak jokalariari oztopatzeko neurriak hartzen baditu).
Jolasetan planifikatzeari buruzko istoriorik ez litzateke osatuko helburuetara zuzendutako ekintza plangintza edo GOAP (helburuetara zuzendutako ekintza plangintza) gabe. Oso erabilia eta eztabaidatua den metodoa da hau, baina xehetasun bereizgarri batzuk ez ezik, funtsean, lehenago hitz egin dugun atzerantz kateatzeko metodoa da. Helburua "jokalaria suntsitzea" balitz eta jokalaria estalpean badago, plana hau izan daiteke: granada batekin suntsitu β lortu β bota.
Hainbat helburu izan ohi dira, bakoitzak bere lehentasunarekin. Lehentasun handieneko helburua ezin bada osatu (ekintzen konbinaziorik ez du "jokalaria hil" plan bat sortzen jokalaria ikusten ez delako), AI lehentasun txikiagoko helburuetara itzuliko da.
Prestakuntza eta egokitzapena
Dagoeneko esan dugu jokoaren IA normalean ez duela ikaskuntza automatikoa erabiltzen, ez baita egokia agenteak denbora errealean kudeatzeko. Baina horrek ez du esan nahi eremu honetatik zerbait maileguan hartu ezin denik. Jaurtitzaile batean aurkari bat nahi dugu, zerbait ikasi ahal izateko. Adibidez, ezagutu mapako posiziorik onenak. Edo borroka-joko bateko aurkari bat, jokalariak maiz erabiltzen dituen mugimendu konbinatuak blokeatuko dituena, beste batzuk erabiltzera motibatuz. Beraz, ikaskuntza automatikoa nahiko erabilgarria izan daiteke horrelako egoeretan.
Estatistika eta Probabilitateak
Adibide konplexuetan sartu aurretik, ikus dezagun noraino irits gaitezkeen neurketa erraz batzuk hartuz eta erabakiak hartzeko erabiliz. Adibidez, denbora errealeko estrategia: nola zehaztuko dugu jokalari batek jokoaren lehen minutuetan eraso bat egin dezakeen ala ez eta zein defentsa prestatu horren aurka? Jokalari baten iraganeko esperientziak azter ditzakegu etorkizuneko erreakzioak zein izan daitezkeen ulertzeko. Hasteko, ez ditugu datu gordinak, baina bil ditzakegu; AIak gizaki baten aurka jokatzen duen bakoitzean, lehen erasoaren ordua graba dezake. Saio batzuen ostean, jokalariak etorkizunean erasotzeko behar duen denboraren bataz beste lortuko dugu.
Batez besteko balioekin ere arazo bat dago: jokalari batek 20 aldiz korrika egin eta 20 aldiz poliki jokatu badu, beharrezkoak diren balioak erdialdean egongo dira, eta horrek ez digu ezer erabilgarria emango. Irtenbide bat sarrerako datuak mugatzea da - azken 20 piezak kontuan har daitezke.
Antzeko ikuspegia erabiltzen da ekintza jakin batzuen probabilitatea kalkulatzeko, jokalariaren iraganeko lehentasunak etorkizunean berdinak izango direla suposatuz. Jokalari batek bost aldiz erasotzen badigu su-bolaz, bi aldiz tximistaz eta behin buruz burukoan, begi-bistakoa da su-bolaz nahiago duela. Estrapolatu eta ikus dezagun arma desberdinak erabiltzeko probabilitatea: su-bola=%62,5, tximista=%25 eta buruz buru=%12,5. Gure jokoa AI sutik babesteko prestatu behar da.
Beste metodo interesgarri bat Naive Bayes Sailkatzailea erabiltzea da sarrerako datu kopuru handiak aztertzeko eta egoera sailkatzeko, AIak nahi den moduan erreakziona dezan. Sailkatzaile bayesiarrak posta elektronikoko spam iragazkietan erabiltzeagatik dira ezagunak. Bertan hitzak aztertzen dituzte, hitz horiek aurretik agertu diren lekuarekin alderatzen dituzte (spamean edo ez), eta sarrerako mezu elektronikoei buruzko ondorioak ateratzen dituzte. Gauza bera egin dezakegu sarrera gutxiagorekin ere. AIk ikusten duen informazio baliagarri guztian oinarrituta (adibidez, zer etsaien unitate sortzen diren, edo zer sorginkeria erabiltzen duten edo zer teknologia ikertu duten), eta azken emaitzan (gerra edo bakea, presa edo defentsa, etab.) - nahi dugun AI portaera aukeratuko dugu.
Prestakuntza-metodo hauek guztiak nahikoak dira, baina komeni da proben datuetan oinarrituta erabiltzea. AI-ak zure jokalariek erabili dituzten estrategia ezberdinetara egokitzen ikasiko du. Askatu ondoren jokalariari egokitzen zaion IA aurreikusgarriegia edo garaitzeko zailaegia izan daiteke.
Balioetan oinarritutako egokitzapena
Gure joko-munduaren edukia eta arauak kontuan hartuta, erabakiak hartzean eragina duten balio multzoa alda dezakegu, sarrerako datuak erabili beharrean. Hau egiten dugu:
- Utzi AI-k munduaren egoerari eta jokoan zehar gertakari garrantzitsuei buruzko datuak biltzea (goian bezala).
- Alda ditzagun datu hauetan oinarritutako balio garrantzitsu batzuk.
- Balio horiek prozesatzen edo ebaluatzean oinarrituta ezartzen ditugu gure erabakiak.
Adibidez, agente batek hainbat gela ditu aukeran lehen pertsonan jaurtitzailearen mapan. Gela bakoitzak bere balioa du, eta horrek zehazten du zein desiragarria den bisitatzea. AI-ak ausaz aukeratzen du zein gelatara joan balioaren arabera. Orduan, agenteak zein gelatan hil zuten gogoratzen du eta haren balioa murrizten du (bera itzultzeko probabilitatea). Era berean, alderantzizko egoerarako - agenteak aurkari asko suntsitzen baditu, orduan gelaren balioa handitzen da.
Markov eredua
Zer gertatzen da bildutako datuak iragarpenak egiteko erabiliko bagenu? Denbora-tarte jakin batean jokalari bat ikusten dugun gela guztietan gogoratzen badugu, jokalaria zein gelatara joan daitekeen iragarriko dugu. Jokalariaren mugimenduak geletan zehar (balioak) jarraituz eta erregistratuz, aurreikus ditzakegu.
Har ditzagun hiru gela: gorria, berdea eta urdina. Baita joko saioa ikusten ari ginenean grabatu genituen behaketak ere:
Gela bakoitzeko behaketa kopurua ia berdina da - oraindik ez dakigu non egin segada baterako leku ona. Estatistikak biltzea ere zaildu egiten da jokalarien birsortzearekin, mapa osoan zehar berdin agertzen baitira. Baina mapan agertu ondoren sartzen diren hurrengo gelari buruzko datuak erabilgarriak dira jada.
Ikusten da gela berdea jokalariei egokitzen zaiela βjende gehienak gela gorritik bertara mugitzen dira, eta horietatik %50 gehiago hor jarraitzen duβ. Gela urdina, aitzitik, ez da ezaguna; ia inor ez da bertara joaten, eta egiten badute, ez dira luzaroan geratzen.
Baina datuek zerbait garrantzitsuagoa esaten digute: jokalari bat gela urdin batean dagoenean, ikusten dugun hurrengo gela gorria izango da, ez berdea. Gela berdea gela gorria baino ezagunagoa den arren, egoera aldatzen da jokalaria gela urdinean badago. Hurrengo egoera (hau da, jokalaria joango den gela) aurreko egoeraren araberakoa da (hau da, jokalaria une honetan dagoen gela). Mendekotasunak aztertzen ditugunez, iragarpen zehatzagoak egingo ditugu behaketak modu independentean zenbatuko bagenitu baino.
Iraganeko egoera bateko datuetan oinarrituta etorkizuneko egoera iragartzea Markov eredua deitzen da, eta horrelako adibideei (gelekin) Markov kateak deritze. Ereduek ondoz ondoko egoeren arteko aldaketen probabilitatea adierazten dutenez, bisualki FSM gisa bistaratzen dira trantsizio bakoitzaren inguruan probabilitate batekin. Aurretik, FSM erabiltzen genuen agente bat zegoen portaera-egoera irudikatzeko, baina kontzeptu hori edozein egoeratara hedatzen da, agentearekin lotuta egon ala ez. Kasu honetan, estatuek agenteak hartzen duen gela adierazten dute:
Hau egoera aldaketen probabilitate erlatiboa irudikatzeko modu sinple bat da, AIri hurrengo egoera iragartzeko gaitasuna ematen diona. Aurrerago hainbat urrats aurreikus ditzakezu.
Jokalari bat gela berdean badago, % 50eko aukera dago behatzen den hurrengoan bertan geratzeko. Baina zeintzuk dira gero ere bertan jarraitzeko aukera? Bi behaketa egin ondoren jokalaria gela berdean geratzeko aukera ez ezik, alde egin eta itzultzeko aukera ere badago. Hona hemen taula berria datu berriak kontuan hartuta:
Bi behaketa egin ondoren jokalaria gela berdean ikusteko aukera % 51ekoa izango dela erakusten du - % 21 gela gorrikoa izango dela, % 5 jokalariak haien arteko gela urdina bisitatuko duela eta. Jokalariak ez duen %25 gela berdetik irtengo da.
Taula bisual tresna bat besterik ez da - prozedurak urrats bakoitzean probabilitateak biderkatzea besterik ez du eskatzen. Horrek esan nahi du etorkizunera urrun begiratu dezakezula ohar batekin: gela batera sartzeko aukera egungo gelaren araberakoa dela suposatzen dugu. Hau Markov Propietate deitzen da - etorkizuneko egoera orainaren araberakoa da soilik. Baina hau ez da %XNUMX zehatza. Jokalariek erabakiak alda ditzakete beste faktore batzuen arabera: osasun maila edo munizio kopurua. Balio hauek erregistratzen ez ditugunez, gure iragarpenak ez dira hain zehatzak izango.
N-gramo
Zer gertatzen da borroka-joko baten adibidearekin eta jokalariaren mugimendu konbinatuak iragartzearekin? Berdina! Baina egoera edo gertaera baten ordez, greba konbinatua osatzen duten sekuentzia osoak aztertuko ditugu.
Horretarako modu bat sarrera bakoitza (adibidez, Kick, Punch edo Block) buffer batean gordetzea eta buffer osoa gertaera gisa idaztea da. Beraz, jokalariak behin eta berriz sakatzen ditu Kick, Kick, Punch SuperDeathFist erasoa erabiltzeko, AI ββsistemak sarrera guztiak buffer batean gordetzen ditu eta urrats bakoitzean erabilitako azken hirurak gogoratzen ditu.
(Lodiz agertzen diren lerroak jokalariak SuperDeathFist erasoa abiarazten duenean daude.)
AI-k aukera guztiak ikusiko ditu jokalariak Kick hautatzen duenean, eta ondoren beste Kick bat, eta hurrengo sarrera beti Punch dela ohartuko da. Horri esker, agenteak SuperDeathFist-en konbinazio mugimendua iragartzeko eta ahal izanez gero blokeatu ahal izango du.
Gertaeren segida hauei N-grama deitzen zaie, non N gordetako elementu kopurua den. Aurreko adibidean 3 gramokoa (trigrama) zen, hau da: lehenengo bi sarrerak hirugarrena iragartzeko erabiltzen dira. Horren arabera, 5 gramo batean, lehenengo lau sarrerek bosgarrena eta abar iragartzen dute.
Diseinatzaileak N-gramen tamaina arretaz aukeratu behar du. N txikiagoak memoria gutxiago behar du, baina historia gutxiago gordetzen du. Esate baterako, 2 gramoko (bigram) batek Kick, Kick edo Kick, Punch grabatuko du, baina ezin izango ditu Kick, Kick, Punch gorde, beraz, AIak ez dio SuperDeathFist konbinazioari erantzungo.
Bestalde, kopuru handiagoek memoria gehiago behar dute eta AI entrenatzea zailagoa izango da aukera posible gehiago egongo baitira. Kick, Punch edo Block hiru sarrera posible izan bazenitu eta 10 gramo bat erabiliko bagenu, 60 mila aukera inguru izango lirateke.
Bigram eredua Markov kate sinple bat da - iraganeko egoera/uneko egoera bikote bakoitza bigrama bat da, eta bigarren egoera aurreikus dezakezu lehenengoan oinarrituta. 3 gramoko eta N-gramo handiagoak Markov kate gisa ere har daitezke, non elementu guztiek (N-grameko azkena izan ezik) elkarrekin lehenengo egoera osatzen duten eta azken elementuak bigarrena. Borroka-jokoaren adibideak Kick and Kick egoeratik Kick and Punch egoerara pasatzeko aukera erakusten du. Sarreren historiako sarrera anitz unitate bakar gisa tratatuz, funtsean, sarrera-sekuentzia egoera osoaren zati bihurtzen ari gara. Honek Markov propietatea ematen digu, eta horrek Markov kateak erabiltzeko aukera ematen digu hurrengo sarrera iragartzeko eta hurrengo konbinazio mugimendua zein izango den asmatzeko.
Ondorioa
Adimen artifizialaren garapenean ohikoenak diren tresna eta planteamenduei buruz hitz egin dugu. Erabili behar diren eta bereziki erabilgarriak diren egoerak ere aztertu ditugu.
Horrek nahikoa izan beharko luke jokoaren AIaren oinarriak ulertzeko. Baina, noski, hauek ez dira metodo guztiak. Gutxiago ezagunak, baina ez hain eraginkorrak:
- optimizazio algoritmoak, besteak beste, mendien igoera, desnibelaren jaitsiera eta algoritmo genetikoak
- aurkako bilaketa/programazio algoritmoak (minimax eta alfa-beta inausketa)
- sailkapen-metodoak (pertzeptronak, sare neuronalak eta euskarri-bektore-makina)
- agenteen pertzepzioa eta memoria prozesatzeko sistemak
- AIrako arkitektura-ikuspegiak (sistema hibridoak, azpimultzo arkitekturak eta AI sistemak gainjartzeko beste modu batzuk)
- animazio tresnak (plangintza eta mugimenduen koordinazioa)
- errendimendu-faktoreak (xehetasun-maila, edonoiz eta denbora-tarteen algoritmoak)
Gaiari buruzko sareko baliabideak:
1. GameDev.net-ek dauka Eta .
2. Aurkezpen eta artikulu ugari ditu jokoen AI garapenarekin lotutako gai askori buruzkoa.
3. GDC AI Summit-eko gaiak biltzen ditu, horietako asko doan eskuragarri.
4. Material erabilgarriak ere aurki daitezke webgunean .
5. Tommy Thompson, AI ikertzaile eta jokoen garatzailea, bideoak egiten ditu YouTuben joko komertzialetan AIren azalpen eta azterketarekin.
Gaiari buruzko liburuak:
1. Game AI Pro liburu sorta artikulu laburren bilduma da, ezaugarri zehatzak nola ezarri edo arazo zehatzak nola konpondu azaltzen duten.
2. AI Game Programming Wisdom seriea Game AI Pro seriearen aurrekoa da. Metodo zaharragoak ditu, baina ia guztiak garrantzitsuak dira gaur egun ere.
3. adimen artifizialaren eremu orokorra ulertu nahi duten guztientzat oinarrizko testuetako bat da. Hau ez da jokoen garapenari buruzko liburu bat, AIaren oinarriak irakasten ditu.
Iturria: www.habr.com