Kam hasur në disa materiale interesante në lidhje me inteligjencën artificiale në lojëra. Me një shpjegim të gjërave themelore rreth AI duke përdorur shembuj të thjeshtë, dhe brenda ka shumë mjete dhe metoda të dobishme për zhvillimin dhe dizajnimin e saj të përshtatshëm. Si, ku dhe kur t'i përdorni ato është gjithashtu atje.
Shumica e shembujve janë shkruar në pseudokod, kështu që nuk kërkohet njohuri e avancuar programimi. Nën prerjen ka 35 fletë teksti me fotografi dhe gif, prandaj bëhuni gati.
UPD. Kërkoj falje, por tashmë e kam bërë përkthimin tim të këtij artikulli në Habré . Mund të lexoni versionin e tij , por për disa arsye artikulli më kaloi (përdora kërkimin, por diçka shkoi keq). Dhe meqenëse po shkruaj në një blog kushtuar zhvillimit të lojërave, vendosa të lë versionin tim të përkthimit për abonentët (disa pika janë formatuar ndryshe, disa janë hequr qëllimisht me këshillën e zhvilluesve).
Çfarë është AI?
Loja AI fokusohet në veprimet që duhet të kryejë një objekt bazuar në kushtet në të cilat ndodhet. Kjo zakonisht quhet menaxhimi i "agjentit inteligjent", ku një agjent është një personazh lojtar, një automjet, një bot, ose ndonjëherë diçka më abstrakte: një grup i tërë entitetesh apo edhe një qytetërim. Në çdo rast, është një gjë që duhet të shohë mjedisin e saj, të marrë vendime bazuar në të dhe të veprojë në përputhje me to. Ky quhet cikli Sense/Mendo/Vepro:
- Sense: Agjenti gjen ose merr informacion rreth gjërave në mjedisin e tij që mund të ndikojnë në sjelljen e tij (kërcënime pranë, sende për të mbledhur, vende interesante për të eksploruar).
- Mendoni: Agjenti vendos se si të reagojë (konsideron nëse është mjaft e sigurt për të mbledhur sende ose nëse ai duhet të luftojë/fshihet i pari).
- Akti: agjenti kryen veprime për të zbatuar vendimin e mëparshëm (fillon të lëvizë drejt armikut ose objektit).
- ...tani situata ka ndryshuar për shkak të veprimeve të personazheve, kështu që cikli përsëritet me të dhëna të reja.
AI tenton të fokusohet në pjesën Sense të ciklit. Për shembull, makinat autonome bëjnë fotografi të rrugës, i kombinojnë ato me të dhënat e radarit dhe lidarit dhe i interpretojnë ato. Kjo zakonisht bëhet nga mësimi i makinerisë, i cili përpunon të dhënat hyrëse dhe u jep atyre kuptim, duke nxjerrë informacion semantik si "ka një makinë tjetër 20 metra përpara jush". Këto janë të ashtuquajturat probleme të klasifikimit.
Lojërat nuk kanë nevojë për një sistem kompleks për nxjerrjen e informacionit pasi shumica e të dhënave janë tashmë një pjesë integrale e tij. Nuk ka nevojë të ekzekutoni algoritme të njohjes së imazhit për të përcaktuar nëse ka një armik përpara - loja tashmë e njeh dhe ushqen informacionin drejtpërdrejt në procesin e vendimmarrjes. Prandaj, pjesa Sense e ciklit është shpesh shumë më e thjeshtë se pjesa Mendo dhe Vepro.
Kufizimet e lojës AI
AI ka një numër kufizimesh që duhen respektuar:
- AI nuk ka nevojë të trajnohet paraprakisht, sikur të ishte një algoritëm i mësimit të makinës. Nuk ka kuptim të shkruhet një rrjet nervor gjatë zhvillimit për të monitoruar dhjetëra mijëra lojtarë dhe për të mësuar mënyrën më të mirë për të luajtur kundër tyre. Pse? Sepse loja nuk është lëshuar dhe nuk ka lojtarë.
- Loja duhet të jetë argëtuese dhe sfiduese, kështu që agjentët nuk duhet të gjejnë qasjen më të mirë kundër njerëzve.
- Agjentët duhet të duken realistë në mënyrë që lojtarët të ndihen sikur po luajnë kundër njerëzve të vërtetë. Programi AlphaGo i tejkaloi njerëzit, por hapat e zgjedhur ishin shumë larg kuptimit tradicional të lojës. Nëse loja simulon një kundërshtar njerëzor, kjo ndjenjë nuk duhet të ekzistojë. Algoritmi duhet të ndryshohet në mënyrë që të marrë vendime të besueshme dhe jo ideale.
- AI duhet të funksionojë në kohë reale. Kjo do të thotë që algoritmi nuk mund të monopolizojë përdorimin e CPU-së për periudha të gjata kohore për të marrë vendime. Edhe 10 milisekonda është shumë e gjatë, sepse shumica e lojërave kanë nevojë vetëm për 16 deri në 33 milisekonda për të kryer të gjithë përpunimin dhe për të kaluar në kornizën tjetër grafik.
- Në mënyrë ideale, të paktën një pjesë e sistemit duhet të drejtohet nga të dhënat, në mënyrë që jo-koduesit të mund të bëjnë ndryshime dhe rregullimet të mund të ndodhin më shpejt.
Le të shohim qasjet e AI që mbulojnë të gjithë ciklin Sense/Mendo/Vepro.
Marrja e vendimeve themelore
Le të fillojmë me lojën më të thjeshtë - Pong. Objektivi: lëvizni vozitën në mënyrë që topi të kërcejë prej tij në vend që të fluturojë përtej tij. Është si tenisi, ku humbet nëse nuk godet topin. Këtu AI ka një detyrë relativisht të lehtë - të vendosë në cilin drejtim të lëvizë platformën.
Deklarata të kushtëzuara
Për inteligjencën artificiale në Pong, zgjidhja më e dukshme është të përpiqeni gjithmonë të vendosni platformën nën top.
Një algoritëm i thjeshtë për këtë, i shkruar në pseudokod:
çdo kornizë/përditësim gjatë kohës që loja po funksionon:
nëse topi është në të majtë të vozitjes:
lëvizni vozitën majtas
ndryshe nëse topi është në të djathtë të vozitës:
lëviz me vozis djathtas
Nëse platforma lëviz me shpejtësinë e topit, atëherë ky është algoritmi ideal për AI në Pong. Nuk ka nevojë të komplikoni asgjë nëse nuk ka aq shumë të dhëna dhe veprime të mundshme për agjentin.
Kjo qasje është aq e thjeshtë sa që i gjithë cikli Sense/Mendo/Vepro mezi vërehet. Por është aty:
- Pjesa e kuptimit është në dy deklarata nëse. Loja e di se ku është topi dhe ku është platforma, kështu që AI i kërkon atë informacion.
- Pjesa Think përfshihet gjithashtu në dy deklaratat nëse. Ato mishërojnë dy zgjidhje, të cilat në këtë rast janë reciprokisht ekskluzive. Si rezultat, zgjidhet një nga tre veprimet - zhvendoseni platformën në të majtë, zhvendoseni në të djathtë ose mos bëni asgjë nëse tashmë është pozicionuar saktë.
- Pjesa Act gjendet në deklaratat Move Paddle Left dhe Move Paddle Right. Në varësi të dizajnit të lojës, ata mund të lëvizin platformën në çast ose me një shpejtësi specifike.
Qasje të tilla quhen reaktive - ekziston një grup i thjeshtë rregullash (në këtë rast nëse deklaratat në kod) që reagojnë ndaj gjendjes aktuale të botës dhe ndërmarrin veprime.
Pema e vendimit
Shembulli i Pong-ut është në fakt ekuivalent me një koncept formal të AI të quajtur pemë vendimi. Algoritmi kalon përmes tij për të arritur një "gjethe" - një vendim se çfarë veprimi duhet të ndërmerret.
Le të bëjmë një diagram bllok të pemës së vendimit për algoritmin e platformës sonë:
Çdo pjesë e pemës quhet nyje - AI përdor teorinë e grafikut për të përshkruar struktura të tilla. Ekzistojnë dy lloje të nyjeve:
- Nyjet e vendimit: zgjedhja midis dy alternativave bazuar në testimin e disa kushteve, ku secila alternativë përfaqësohet si një nyje e veçantë.
- Nyjet fundore: Veprimi për të kryer që përfaqëson vendimin përfundimtar.
Algoritmi fillon nga nyja e parë (“rrënja” e pemës). Ai ose merr një vendim se në cilën nyje fëmijë të shkojë, ose ekzekuton veprimin e ruajtur në nyje dhe del.
Cili është përfitimi i të pasurit një pemë vendimi të bëjë të njëjtën punë si deklaratat if në seksionin e mëparshëm? Këtu ekziston një sistem i përgjithshëm ku çdo vendim ka vetëm një kusht dhe dy rezultate të mundshme. Kjo i lejon zhvilluesit të krijojë AI nga të dhënat që përfaqësojnë vendimet në një pemë pa pasur nevojë ta kodojnë atë. Le ta paraqesim në formë tabele:
Në anën e kodit do të merrni një sistem për leximin e vargjeve. Krijoni një nyje për secilën prej tyre, lidhni logjikën e vendimit bazuar në kolonën e dytë dhe nyjet fëmijë bazuar në kolonën e tretë dhe të katërt. Ju ende duhet të programoni kushtet dhe veprimet, por tani struktura e lojës do të jetë më komplekse. Këtu ju shtoni vendime dhe veprime shtesë, dhe më pas personalizoni të gjithë AI duke redaktuar thjesht skedarin e tekstit të përkufizimit të pemës. Më pas, ju transferoni skedarin te projektuesi i lojës, i cili mund të ndryshojë sjelljen pa e rikompiluar lojën ose pa ndryshuar kodin.
Pemët e vendimeve janë shumë të dobishme kur ndërtohen automatikisht nga një grup i madh shembujsh (për shembull, duke përdorur algoritmin ID3). Kjo i bën ata një mjet efektiv dhe me performancë të lartë për klasifikimin e situatave bazuar në të dhënat e marra. Megjithatë, ne shkojmë përtej një sistemi të thjeshtë për agjentët për të zgjedhur veprime.
Skenarët
Ne analizuam një sistem të pemës së vendimeve që përdorte kushte dhe veprime të para-krijuara. Personi që dizajnon AI mund ta organizojë pemën si të dojë, por ai ende duhet të mbështetet në koduesin që i ka programuar të gjitha. Po sikur t'i jepnim projektuesit mjetet për të krijuar kushtet ose veprimet e veta?
Në mënyrë që programuesi të mos ketë nevojë të shkruajë kod për kushtet Is Ball Left Of Paddle dhe Is Ball Right Of Paddle, ai mund të krijojë një sistem në të cilin projektuesi do të shkruajë kushtet për të kontrolluar këto vlera. Atëherë të dhënat e pemës së vendimit do të duken kështu:
Kjo është në thelb e njëjtë si në tabelën e parë, por zgjidhjet brenda vetes kanë kodin e tyre, paksa si pjesa e kushtëzuar e një deklarate if. Në anën e kodit, kjo do të lexohej në kolonën e dytë për nyjet e vendimit, por në vend që të kërkonte një kusht specifik për të ekzekutuar (Is Ball Left Of Paddle), ai vlerëson shprehjen e kushtëzuar dhe kthen në përputhje me rrethanat true ose false. Kjo bëhet duke përdorur gjuhën e shkrimit Lua ose Angelscript. Duke i përdorur ato, një zhvillues mund të marrë objekte në lojën e tij (top dhe vozis) dhe të krijojë variabla që do të jenë të disponueshme në skript (top.pozitë). Gjithashtu, gjuha e skriptimit është më e thjeshtë se C++. Nuk kërkon një fazë të plotë përpilimi, kështu që është ideale për rregullimin e shpejtë të logjikës së lojës dhe lejon "jo-koduesit" të krijojnë vetë funksionet e nevojshme.
Në shembullin e mësipërm, gjuha e skriptimit përdoret vetëm për të vlerësuar shprehjen e kushtëzuar, por mund të përdoret edhe për veprime. Për shembull, të dhënat Move Paddle Right mund të bëhen një deklaratë skripti (top.pozicion.x += 10). Kështu që veprimi të përcaktohet edhe në skript, pa qenë nevoja të programohet Move Paddle Right.
Mund të shkoni edhe më tej dhe të shkruani të gjithë pemën e vendimeve në një gjuhë skriptimi. Ky do të jetë kod në formën e deklaratave të kushtëzuara të koduara, por ato do të vendosen në skedarë të jashtëm të skriptit, domethënë ato mund të ndryshohen pa ripërpiluar të gjithë programin. Shpesh mund ta modifikoni skedarin e skriptit gjatë lojës për të testuar shpejt përgjigje të ndryshme të AI.
Përgjigja e ngjarjes
Shembujt e mësipërm janë të përsosur për Pong. Ata drejtojnë vazhdimisht ciklin Sense/Mendo/Vepro dhe veprojnë bazuar në gjendjen më të fundit të botës. Por në lojërat më komplekse ju duhet të reagoni ndaj ngjarjeve individuale dhe të mos vlerësoni gjithçka menjëherë. Pong në këtë rast është tashmë një shembull i keq. Le të zgjedhim një tjetër.
Imagjinoni një gjuajtës ku armiqtë janë të palëvizshëm derisa të zbulojnë lojtarin, pas së cilës ata veprojnë në varësi të "specializimit" të tyre: dikush do të vrapojë të "ngutet", dikush do të sulmojë nga larg. Është ende një sistem reaktiv bazë - "nëse një lojtar dallohet, bëj diçka" - por mund të ndahet logjikisht në një ngjarje të parë nga lojtari dhe një reagim (zgjidh një përgjigje dhe ekzekutoje atë).
Kjo na kthen në ciklin Sense/Mendo/Vepro. Ne mund të kodojmë një pjesë Sense që do të kontrollojë çdo kornizë nëse AI e sheh luajtësin. Nëse jo, asgjë nuk ndodh, por nëse sheh, atëherë krijohet ngjarja Player Seen. Kodi do të ketë një seksion të veçantë që thotë "kur ndodh ngjarja Player Seen, bëj" ku është përgjigja që ju nevojitet për të adresuar pjesët Think and Act. Kështu, ju do të vendosni reagime ndaj ngjarjes Player Seen: për personazhin "nxituar" - ChargeAndAttack dhe për snajperin - HideAndSnipe. Këto marrëdhënie mund të krijohen në skedarin e të dhënave për redaktim të shpejtë pa pasur nevojë të ripërpilohen. Gjuha e shkrimit mund të përdoret gjithashtu këtu.
Marrja e vendimeve të vështira
Megjithëse sistemet e thjeshta të reagimit janë shumë të fuqishëm, ka shumë situata ku ato nuk janë të mjaftueshme. Ndonjëherë ju duhet të merrni vendime të ndryshme bazuar në atë që agjenti po bën aktualisht, por është e vështirë të imagjinohet kjo si një kusht. Ndonjëherë ka shumë kushte për t'i përfaqësuar ato në mënyrë efektive në një pemë vendimi ose skenar. Ndonjëherë duhet të vlerësoni paraprakisht se si do të ndryshojë situata përpara se të vendosni për hapin tjetër. Për zgjidhjen e këtyre problemeve nevojiten qasje më të sofistikuara.
Makinë me gjendje të fundme
Makina e gjendjes së fundme ose FSM (makina e gjendjes së fundme) është një mënyrë për të thënë se agjenti ynë është aktualisht në një nga disa gjendjet e mundshme dhe se mund të kalojë nga një gjendje në tjetrën. Ka një numër të caktuar shtetesh të tilla - prandaj emri. Shembulli më i mirë nga jeta është semafori. Ka sekuenca të ndryshme dritash në vende të ndryshme, por parimi është i njëjtë - çdo gjendje përfaqëson diçka (ndalo, ec, etj.). Një semafor është vetëm në një gjendje në çdo kohë të caktuar dhe lëviz nga njëri në tjetrin bazuar në rregulla të thjeshta.
Është një histori e ngjashme me NPC-të në lojëra. Për shembull, le të marrim një roje me gjendjet e mëposhtme:
- Patrullimi.
- Duke sulmuar.
- Duke ikur.
Dhe këto kushte për ndryshimin e gjendjes së saj:
- Nëse roja e sheh armikun, ai sulmon.
- Nëse roja sulmon, por nuk e sheh më armikun, ai kthehet në patrullë.
- Nëse një roje sulmon por plagoset rëndë, ai ikën.
Ju gjithashtu mund të shkruani deklarata nëse me një variabël të gjendjes mbrojtëse dhe kontrolle të ndryshme: a ka ndonjë armik afër, cili është niveli shëndetësor i NPC, etj. Le të shtojmë disa gjendje të tjera:
- Përtacia - midis patrullave.
- Kërkimi - kur armiku i vërejtur është zhdukur.
- Gjetja e ndihmës - kur një armik dallohet, por është shumë i fortë për të luftuar i vetëm.
Zgjedhja për secilën prej tyre është e kufizuar - për shembull, roja nuk do të shkojë të kërkojë një armik të fshehur nëse ka shëndet të ulët.
Në fund të fundit, ekziston një listë e madhe e "nëse" , Kjo "mund të bëhet shumë e rëndë, kështu që ne duhet të zyrtarizojmë një metodë që na lejon të mbajmë parasysh gjendjet dhe tranzicionet midis shteteve. Për ta bërë këtë, ne marrim parasysh të gjitha gjendjet dhe nën secilin shtet shkruajmë në një listë të gjitha kalimet në shtetet e tjera, së bashku me kushtet e nevojshme për to.
Kjo është një tabelë e tranzicionit të gjendjes - një mënyrë gjithëpërfshirëse për të përfaqësuar FSM. Le të vizatojmë një diagram dhe të marrim një pasqyrë të plotë se si ndryshon sjellja e NPC.
Diagrami pasqyron thelbin e vendimmarrjes për këtë agjent bazuar në situatën aktuale. Për më tepër, çdo shigjetë tregon një kalim midis gjendjeve nëse kushti pranë tij është i vërtetë.
Çdo përditësim kontrollojmë gjendjen aktuale të agjentit, shikojmë listën e tranzicioneve dhe nëse plotësohen kushtet për kalimin, ai pranon gjendjen e re. Për shembull, çdo kornizë kontrollon nëse kohëmatësi prej 10 sekondash ka skaduar dhe nëse po, atëherë roja kalon nga gjendja e Idling në Patrolling. Në të njëjtën mënyrë, shteti sulmues kontrollon shëndetin e agjentit - nëse është i ulët, atëherë ai kalon në gjendjen e arratisjes.
Ky është trajtimi i tranzicioneve ndërmjet shteteve, por çfarë ndodh me sjelljen e lidhur me vetë shtetet? Për sa i përket zbatimit të sjelljes aktuale për një shtet të caktuar, zakonisht ekzistojnë dy lloje "hook" ku ne i caktojmë veprimet FSM-së:
- Veprimet që ne kryejmë në mënyrë periodike për gjendjen aktuale.
- Veprimet që bëjmë kur kalojmë nga një gjendje në tjetrën.
Shembuj për llojin e parë. Shteti patrullues do të lëvizë agjentin përgjatë rrugës së patrullimit çdo kornizë. Shteti sulmues do të përpiqet të inicojë një sulm çdo kornizë ose kalim në një gjendje ku kjo është e mundur.
Për llojin e dytë, merrni parasysh tranzicionin "nëse armiku është i dukshëm dhe armiku është shumë i fortë, atëherë shkoni në gjendjen "Gjeni Ndihmën". Agjenti duhet të zgjedhë se ku të shkojë për ndihmë dhe ta ruajë këtë informacion në mënyrë që shteti Gjetja e ndihmës të dijë se ku të shkojë. Pasi të gjendet ndihma, agjenti kthehet në gjendjen Sulmuese. Në këtë pikë, ai do të dëshirojë t'i tregojë aleatit për kërcënimin, kështu që mund të ndodhë veprimi NotifyFriendOfThreat.
Edhe një herë, ne mund ta shikojmë këtë sistem përmes lenteve të ciklit Sense/Mendo/Vepro. Sense mishërohet në të dhënat e përdorura nga logjika e tranzicionit. Mendoni - tranzicione të disponueshme në çdo shtet. Dhe Akti kryhet nga veprimet e kryera periodikisht brenda një shteti ose në tranzicion midis shteteve.
Ndonjëherë kushtet e tranzicionit të vazhdueshëm të votimit mund të jenë të kushtueshme. Për shembull, nëse çdo agjent kryen llogaritje komplekse në çdo kornizë për të përcaktuar nëse mund të shohë armiqtë dhe të kuptojë nëse mund të kalojë nga gjendja Patrulluese në Sulmuese, kjo do të marrë shumë kohë CPU.
Ndryshimet e rëndësishme në gjendjen e botës mund të mendohen si ngjarje që do të përpunohen ndërsa ndodhin. Në vend që FSM të kontrollojë kushtin e tranzicionit "a mund ta shohë agjenti im lojtarin?" çdo kornizë, mund të konfigurohet një sistem i veçantë për të kontrolluar më rrallë (p.sh. 5 herë në sekondë). Dhe rezultati është lëshimi i Player Seen kur kalon kontrolli.
Kjo i kalohet FSM-së, e cila tani duhet të shkojë te kushti i marrë i ngjarjes së Shikuar nga Lojtari dhe të përgjigjet në përputhje me rrethanat. Sjellja që rezulton është e njëjtë me përjashtim të një vonese pothuajse të padukshme përpara se të përgjigjeni. Por performanca është përmirësuar si rezultat i ndarjes së pjesës Sense në një pjesë të veçantë të programit.
Makina hierarkike e gjendjes së fundme
Sidoqoftë, puna me FSM të mëdha nuk është gjithmonë e përshtatshme. Nëse duam të zgjerojmë gjendjen e sulmit për të ndarë MeleeAttacking dhe RangedAttacking, do të duhet të ndryshojmë kalimet nga të gjitha gjendjet e tjera që çojnë në gjendjen Sulmuese (aktuale dhe të ardhshme).
Ju ndoshta keni vënë re se në shembullin tonë ka shumë tranzicione të kopjuara. Shumica e tranzicioneve në gjendjen e papunë janë identike me tranzicionet në gjendjen patrulluese. Do të ishte mirë të mos përsërisim veten, veçanërisht nëse shtojmë më shumë gjendje të ngjashme. Ka kuptim të grupohen Idling dhe Patrolling nën etiketën e përgjithshme të "jo luftarake", ku ekziston vetëm një grup i përbashkët i tranzicionit në shtetet luftarake. Nëse e mendojmë këtë etiketë si shtet, atëherë përtacia dhe patrullimi bëhen nënshtete. Një shembull i përdorimit të një tabele të veçantë tranzicioni për një nënshtet të ri jo luftarak:
Gjendjet kryesore:
Jashtë gjendjes luftarake:
Dhe në formën e diagramit:
Është i njëjti sistem, por me një gjendje të re jo luftarake që përfshin Idling dhe Patrolling. Me çdo gjendje që përmban një FSM me nënshtete (dhe këto nënshtete, nga ana tjetër, përmbajnë FSM-të e tyre - dhe kështu me radhë për aq kohë sa ju nevojitet), ne marrim një Makinë Hierarkike të Gjendjes së Fundit ose HFSM (makinë hierarkike të gjendjes së fundme). Duke grupuar gjendjen jo luftarake, ne premë një mori tranzicionesh të tepërta. Ne mund të bëjmë të njëjtën gjë për çdo shtet të ri me tranzicione të përbashkëta. Për shembull, nëse në të ardhmen zgjerojmë gjendjen Sulmuese në shtetet MeleeAttacking dhe MissileAttacking, ato do të jenë nënshtete që kalojnë njëra-tjetrën në bazë të distancës nga armiku dhe disponueshmërisë së municioneve. Si rezultat, sjelljet dhe nën-sjelljet komplekse mund të përfaqësohen me një minimum tranzicionesh të dyfishta.
Pema e sjelljes
Me HFSM, kombinimet komplekse të sjelljeve krijohen në një mënyrë të thjeshtë. Megjithatë, ka një vështirësi të vogël që vendimmarrja në formën e rregullave të tranzicionit është e lidhur ngushtë me gjendjen aktuale. Dhe në shumë lojëra kjo është pikërisht ajo që nevojitet. Dhe përdorimi i kujdesshëm i hierarkisë shtetërore mund të zvogëlojë numrin e përsëritjeve të tranzicionit. Por ndonjëherë ju nevojiten rregulla që funksionojnë pavarësisht se në çfarë shteti jeni, ose që zbatohen pothuajse në çdo shtet. Për shembull, nëse shëndeti i një agjenti bie në 25%, ju do të dëshironi që ai të ikë pavarësisht nëse ai ishte në luftim, boshe ose duke folur - ju do të duhet ta shtoni këtë gjendje në çdo shtet. Dhe nëse projektuesi juaj më vonë dëshiron të ndryshojë pragun e ulët të shëndetit nga 25% në 10%, atëherë kjo do të duhet të bëhet përsëri.
Në mënyrë ideale, kjo situatë kërkon një sistem në të cilin vendimet se “në çfarë gjendje të jesh” janë jashtë vetë shteteve, në mënyrë që të bëhen ndryshime vetëm në një vend dhe të mos preken kushtet e tranzicionit. Pemët e sjelljes shfaqen këtu.
Ka disa mënyra për t'i zbatuar ato, por thelbi është afërsisht i njëjtë për të gjithë dhe është i ngjashëm me një pemë vendimi: algoritmi fillon me një nyje "rrënjë" dhe pema përmban nyje që përfaqësojnë ose vendime ose veprime. Megjithatë ka disa dallime kryesore:
- Nyjet tani kthejnë një nga tre vlerat: Suksesuar (nëse puna është përfunduar), Dështoi (nëse nuk mund të niset) ose Running (nëse është ende në punë dhe nuk ka rezultat përfundimtar).
- Nuk ka më nyje vendimi për të zgjedhur midis dy alternativave. Në vend të kësaj, ato janë nyje Decorator, të cilat kanë një nyje fëmijësh. Nëse ata kanë sukses, ata ekzekutojnë nyjen e tyre të vetme të fëmijës.
- Nyjet që kryejnë veprime kthejnë një vlerë Running për të përfaqësuar veprimet që kryhen.
Ky grup i vogël nyjesh mund të kombinohet për të krijuar një numër të madh sjelljesh komplekse. Le të imagjinojmë rojen HFSM nga shembulli i mëparshëm si një pemë sjelljeje:
Me këtë strukturë nuk duhet të ketë një tranzicion të dukshëm nga shtetet përtaci/patrulluese në ato sulmuese ose në ndonjë shtet tjetër. Nëse një armik është i dukshëm dhe shëndeti i personazhit është i ulët, ekzekutimi do të ndalet në nyjen Fleeing, pavarësisht se cilës nyje ka ekzekutuar më parë - Patrolling, Idling, Attacking ose ndonjë tjetër.
Pemët e sjelljes janë komplekse - ka shumë mënyra për t'i kompozuar ato, dhe gjetja e kombinimit të duhur të dekoruesve dhe nyjeve komplekse mund të jetë sfiduese. Ka edhe pyetje se sa shpesh duhet të kontrollohet pema - a duam të kalojmë nëpër çdo pjesë të saj apo vetëm kur një nga kushtet ka ndryshuar? Si e ruajmë gjendjen që ka të bëjë me nyjet - si e dimë kur kemi qëndruar në punë për 10 sekonda, ose si e dimë se cilat nyje janë ekzekutuar herën e fundit në mënyrë që të mund ta përpunojmë sekuencën në mënyrë korrekte?
Kjo është arsyeja pse ka shumë zbatime. Për shembull, disa sisteme kanë zëvendësuar nyjet e dekoruesit me dekorues inline. Ata e rivlerësojnë pemën kur ndryshojnë kushtet e dekoruesit, ndihmojnë në bashkimin e nyjeve dhe ofrojnë përditësime periodike.
Sistemi i bazuar në shërbime
Disa lojëra kanë shumë mekanikë të ndryshëm. Është e dëshirueshme që ata të marrin të gjitha përfitimet e rregullave të thjeshta dhe të përgjithshme të tranzicionit, por jo domosdoshmërisht në formën e një peme të plotë të sjelljes. Në vend që të keni një grup të qartë zgjedhjesh ose një pemë të veprimeve të mundshme, është më e lehtë të ekzaminoni të gjitha veprimet dhe të zgjidhni atë më të përshtatshmen për momentin.
Sistemi i bazuar në shërbime do të ndihmojë vetëm me këtë. Ky është një sistem ku agjenti ka një sërë veprimesh dhe zgjedh se cilat të kryejë bazuar në dobinë relative të secilit. Ku dobia është një masë arbitrare se sa e rëndësishme ose e dëshirueshme është që agjenti të kryejë këtë veprim.
Përdorimi i llogaritur i një veprimi bazuar në gjendjen dhe mjedisin aktual, agjenti mund të kontrollojë dhe të zgjedhë gjendjen tjetër më të përshtatshme në çdo kohë. Kjo është e ngjashme me FSM, përveç rasteve kur kalimet përcaktohen nga një vlerësim për çdo gjendje të mundshme, duke përfshirë atë aktual. Ju lutemi vini re se ne zgjedhim veprimin më të dobishëm për të vazhduar (ose për të qëndruar nëse e kemi përfunduar tashmë). Për më shumë larmi, kjo mund të jetë një përzgjedhje e ekuilibruar, por e rastësishme nga një listë e vogël.
Sistemi cakton një gamë arbitrare të vlerave të shërbimeve - për shembull, nga 0 (plotësisht e padëshirueshme) në 100 (plotësisht e dëshirueshme). Çdo veprim ka një numër parametrash që ndikojnë në llogaritjen e kësaj vlere. Duke iu rikthyer shembullit tonë të kujdestarit:
Tranzicionet midis veprimeve janë të paqarta - çdo gjendje mund të ndjekë çdo tjetër. Prioritetet e veprimit gjenden në vlerat e kthyera të shërbimeve. Nëse një armik është i dukshëm dhe ai armik është i fortë dhe shëndeti i personazhit është i ulët, atëherë si Fleeing ashtu edhe FindingHelp do të kthejnë vlera të larta jo zero. Në këtë rast, FindingHelp do të jetë gjithmonë më i lartë. Po kështu, aktivitetet jo luftarake nuk kthehen kurrë më shumë se 50, kështu që ato do të jenë gjithmonë më të ulëta se ato luftarake. Ju duhet ta merrni parasysh këtë kur krijoni veprime dhe llogaritni dobinë e tyre.
Në shembullin tonë, veprimet kthejnë ose një vlerë konstante fikse ose një nga dy vlerat fikse. Një sistem më realist do të kthente një vlerësim nga një varg i vazhdueshëm vlerash. Për shembull, veprimi Fleeing kthen vlera më të larta të shërbimeve nëse shëndeti i agjentit është i ulët, dhe veprimi Sulmues kthen vlera më të ulëta të shërbimeve nëse armiku është shumë i fortë. Për shkak të kësaj, veprimi i Ikjes ka përparësi ndaj Sulmimit në çdo situatë ku agjenti mendon se nuk ka shëndet të mjaftueshëm për të mposhtur armikun. Kjo lejon që veprimet të prioritizohen bazuar në çdo numër kriteresh, duke e bërë këtë qasje më fleksibël dhe më të ndryshueshme sesa një pemë sjelljeje ose FSM.
Çdo veprim ka shumë kushte për llogaritjen e programit. Ato mund të shkruhen në gjuhën e shkrimit ose si një seri formulash matematikore. Sims, i cili simulon rutinën e përditshme të një personazhi, shton një shtresë shtesë llogaritjeje - agjenti merr një sërë "motivimesh" që ndikojnë në vlerësimet e shërbimeve. Nëse një personazh është i uritur, ai do të bëhet edhe më i uritur me kalimin e kohës dhe vlera e dobishme e veprimit EatFood do të rritet derisa personazhi ta kryejë atë, duke ulur nivelin e urisë dhe duke e kthyer vlerën EatFood në zero.
Ideja e zgjedhjes së veprimeve të bazuara në një sistem vlerësimi është mjaft e thjeshtë, kështu që një sistem i bazuar në shërbime mund të përdoret si pjesë e proceseve të vendimmarrjes së AI, në vend që të zëvendësohet plotësisht për to. Pema e vendimit mund të kërkojë një vlerësim të shërbimeve të dy nyjeve fëmijë dhe të zgjedhë atë më të lartën. Në mënyrë të ngjashme, një pemë e sjelljes mund të ketë një nyje të përbërë të Utility për të vlerësuar dobinë e veprimeve për të vendosur se cilin fëmijë të ekzekutojë.
Lëvizja dhe lundrimi
Në shembujt e mëparshëm, ne kishim një platformë që lëviznim majtas ose djathtas, dhe një roje që patrullonte ose sulmonte. Por si e trajtojmë saktësisht lëvizjen e agjentëve gjatë një periudhe kohore? Si e vendosim shpejtësinë, si i shmangim pengesat dhe si planifikojmë një rrugë kur arritja në një destinacion është më e vështirë sesa thjesht lëvizja në një vijë të drejtë? Le të shohim këtë.
Управление
Në fazën fillestare, do të supozojmë se çdo agjent ka një vlerë shpejtësie, e cila përfshin sa shpejt lëviz dhe në cilin drejtim. Mund të matet në metra për sekondë, kilometra në orë, pikselë për sekondë, etj. Duke kujtuar ciklin Sense/Think/Act, mund të imagjinojmë që pjesa Think zgjedh një shpejtësi dhe pjesa Act e zbaton atë shpejtësi tek agjenti. Zakonisht lojërat kanë një sistem fizik që e bën këtë detyrë për ju, duke mësuar vlerën e shpejtësisë së secilit objekt dhe duke e rregulluar atë. Prandaj, ju mund ta lini AI me një detyrë - të vendosni se çfarë shpejtësie duhet të ketë agjenti. Nëse e dini se ku duhet të jetë agjenti, atëherë duhet ta lëvizni atë në drejtimin e duhur me një shpejtësi të caktuar. Një ekuacion shumë i parëndësishëm:
dëshiruar_udhëtim = destinacion_pozicion – agjent_pozicion
Imagjinoni një botë 2D. Agjenti është në pikën (-2,-2), destinacioni është diku në verilindje në pikën (30, 20) dhe rruga e kërkuar që agjenti të arrijë atje është (32, 22). Le të themi se këto pozicione maten në metra - nëse marrim shpejtësinë e agjentit të jetë 5 metra për sekondë, atëherë do të shkallëzojmë vektorin tonë të zhvendosjes dhe do të marrim një shpejtësi prej përafërsisht (4.12, 2.83). Me këto parametra, agjenti do të mbërrinte në destinacionin e tij në pothuajse 8 sekonda.
Ju mund të rillogaritni vlerat në çdo kohë. Nëse agjenti do të ishte në gjysmë të rrugës drejt objektivit, lëvizja do të ishte gjysma e gjatësisë, por duke qenë se shpejtësia maksimale e agjentit është 5 m/s (e vendosëm më lart), shpejtësia do të jetë e njëjtë. Kjo gjithashtu funksionon për objektivat në lëvizje, duke i lejuar agjentit të bëjë ndryshime të vogla ndërsa lëvizin.
Por ne duam më shumë variacione - për shembull, duke rritur ngadalë shpejtësinë për të simuluar një personazh që lëviz nga qëndrimi në këmbë në vrap. E njëjta gjë mund të bëhet në fund para ndalimit. Këto veçori njihen si sjellje drejtuese, secila prej të cilave ka emra të veçantë: Kërko, Ik, Arritje, etj. Ideja është që forcat e nxitimit mund të aplikohen në shpejtësinë e agjentit, bazuar në krahasimin e pozicionit të agjentit dhe shpejtësisë aktuale me destinacionin në për të përdorur metoda të ndryshme për të lëvizur drejt qëllimit.
Çdo sjellje ka një qëllim paksa të ndryshëm. Kërkimi dhe Arritja janë mënyra për të zhvendosur një agjent në një destinacion. Shmangia e pengesave dhe ndarja rregullojnë lëvizjen e agjentit për të shmangur pengesat në rrugën drejt qëllimit. Përafrimi dhe kohezioni i mbajnë agjentët të lëvizin së bashku. Çdo numër i sjelljeve të ndryshme të drejtimit mund të përmblidhet për të prodhuar një vektor të vetëm të rrugës duke marrë parasysh të gjithë faktorët. Një agjent që përdor sjelljet Arritja, Ndarja dhe Shmangia e Pengesave për të qëndruar larg mureve dhe agjentëve të tjerë. Kjo qasje funksionon mirë në vende të hapura pa detaje të panevojshme.
Në kushte më të vështira, shtimi i sjelljeve të ndryshme funksionon më keq - për shembull, një agjent mund të ngecë në një mur për shkak të një konflikti midis Arritjes dhe Shmanjes së Pengesave. Prandaj, duhet të merrni parasysh opsionet që janë më komplekse sesa thjesht të shtoni të gjitha vlerat. Mënyra është kjo: në vend që të shtoni rezultatet e çdo sjelljeje, mund të merrni parasysh lëvizjen në drejtime të ndryshme dhe të zgjidhni opsionin më të mirë.
Megjithatë, në një mjedis kompleks me rrugë qorre dhe zgjedhje se cila rrugë të shkojmë, do të na duhet diçka edhe më e avancuar.
Gjetja e një mënyre
Sjelljet e drejtimit janë të shkëlqyera për lëvizje të thjeshta në një zonë të hapur (fushë futbolli ose arenë) ku kalimi nga A në B është një rrugë e drejtë me vetëm devijime të vogla rreth pengesave. Për rrugë komplekse, ne kemi nevojë për gjetjen e shtigjeve, që është një mënyrë për të eksploruar botën dhe për të vendosur për një rrugë përmes saj.
Më e thjeshta është të aplikoni një rrjetë në çdo katror pranë agjentit dhe të vlerësoni se cilët prej tyre lejohen të lëvizin. Nëse njëri prej tyre është një destinacion, atëherë ndiqni rrugën nga çdo shesh në atë të mëparshëm derisa të arrini në fillim. Kjo është rruga. Përndryshe, përsërisni procesin me sheshet e tjera aty pranë derisa të gjeni destinacionin tuaj ose të mbeteni pa sheshe (që do të thotë se nuk ka rrugë të mundshme). Kjo është ajo që njihet zyrtarisht si Kërkimi i Gjerësisë së Parë ose BFS (algoritmi i kërkimit të parë në gjerësi). Në çdo hap ai shikon në të gjitha drejtimet (pra gjerësia, "gjerësia"). Hapësira e kërkimit është si një front vale që lëviz derisa të arrijë vendndodhjen e dëshiruar - hapësira e kërkimit zgjerohet në çdo hap derisa të përfshihet pika e fundit, pas së cilës mund të gjurmohet përsëri në fillim.
Si rezultat, do të merrni një listë të shesheve përgjatë të cilave përpilohet rruga e dëshiruar. Kjo është rruga (pra, gjetja e rrugës) - një listë e vendeve që agjenti do të vizitojë ndërsa ndjek destinacionin.
Duke pasur parasysh se ne e dimë pozicionin e çdo katrori në botë, ne mund të përdorim sjelljet e drejtimit për të lëvizur përgjatë rrugës - nga nyja 1 në nyjen 2, pastaj nga nyja 2 në nyjen 3, e kështu me radhë. Mundësia më e thjeshtë është të drejtoheni drejt qendrës së sheshit tjetër, por një opsion edhe më i mirë është të ndaleni në mes të skajit midis sheshit aktual dhe atij të ardhshëm. Për shkak të kësaj, agjenti do të jetë në gjendje të prerë qoshet në kthesat e mprehta.
Algoritmi BFS ka gjithashtu disavantazhe - ai eksploron sa më shumë katrorë në drejtimin "të gabuar" sa në drejtimin "e duhur". Këtu hyn në lojë një algoritëm më kompleks i quajtur A* (A yll). Ai funksionon në të njëjtën mënyrë, por në vend që të shqyrtojë verbërisht katrorët e fqinjëve (pastaj fqinjët e fqinjëve, pastaj fqinjët e fqinjëve të fqinjëve, e kështu me radhë), ai i mbledh nyjet në një listë dhe i rendit ato në mënyrë që nyja tjetër e ekzaminuar të jetë gjithmonë ai që të çon në rrugën më të shkurtër. Nyjet renditen në bazë të një heuristike që merr parasysh dy gjëra: "kostoja" e një rruge hipotetike për në sheshin e dëshiruar (duke përfshirë çdo kosto udhëtimi) dhe një vlerësim se sa larg është ai shesh nga destinacioni (duke paragjykuar kërkimin në drejtimi i duhur).
Ky shembull tregon se agjenti eksploron një katror në një kohë, çdo herë duke zgjedhur atë ngjitur që është më premtuesi. Rruga që rezulton është e njëjtë me BFS, por më pak katrorë u morën parasysh në proces - gjë që ka një ndikim të madh në performancën e lojës.
Lëvizja pa rrjetë
Por shumica e lojërave nuk janë të vendosura në një rrjet dhe shpesh është e pamundur ta bësh këtë pa sakrifikuar realizmin. Duhen kompromise. Çfarë madhësie duhet të jenë katrorët? Shumë të mëdha dhe nuk do të jenë në gjendje të përfaqësojnë saktë korridoret ose kthesat e vogla, shumë të vogla dhe do të ketë shumë katrorë për të kërkuar, gjë që në fund do të marrë shumë kohë.
Gjëja e parë që duhet kuptuar është se një rrjetë na jep një grafik të nyjeve të lidhura. Algoritmet A* dhe BFS në fakt punojnë në grafikë dhe nuk kujdesen fare për rrjetën tonë. Ne mund të vendosim nyje kudo në botën e lojës: për sa kohë që ekziston një lidhje midis dy nyjeve të lidhura, si dhe midis pikave të fillimit dhe përfundimit dhe të paktën një prej nyjeve, algoritmi do të funksionojë po aq mirë si më parë. Ky shpesh quhet një sistem pikëkalimi, pasi secila nyje përfaqëson një pozicion të rëndësishëm në botë që mund të jetë pjesë e çdo numri të shtigjeve hipotetike.
Shembulli 1: një nyjë në çdo katror. Kërkimi fillon nga nyja ku ndodhet agjenti dhe përfundon në nyjen e katrorit të dëshiruar.
Shembulli 2: Një grup më i vogël nyjesh (pika udhëzuese). Kërkimi fillon në sheshin e agjentit, kalon në numrin e kërkuar të nyjeve dhe më pas vazhdon në destinacion.
Ky është një sistem plotësisht fleksibël dhe i fuqishëm. Por nevojitet një kujdes për të vendosur se ku dhe si të vendoset një pikë, përndryshe agjentët thjesht mund të mos shohin pikën më të afërt dhe nuk do të jenë në gjendje të fillojnë shtegun. Do të ishte më e lehtë nëse do të mund të vendosnim automatikisht pikat e rrugës bazuar në gjeometrinë e botës.
Këtu shfaqet rrjeta e navigimit ose navmesh (rrjeta e navigimit). Kjo është zakonisht një rrjetë 2D trekëndëshash që mbivendoset në gjeometrinë e botës - kudo ku agjenti lejohet të ecë. Secili nga trekëndëshat në rrjetë bëhet një nyje në grafik dhe ka deri në tre trekëndësha ngjitur që bëhen nyje ngjitur në grafik.
Kjo foto është një shembull nga motori Unity - ai analizoi gjeometrinë në botë dhe krijoi një navmesh (në pamjen e ekranit në blu të lehtë). Çdo shumëkëndësh në një navmesh është një zonë ku një agjent mund të qëndrojë ose të lëvizë nga një shumëkëndësh në një shumëkëndësh tjetër. Në këtë shembull, poligonet janë më të vegjël se katet në të cilat ndodhen - kjo bëhet për të marrë parasysh madhësinë e agjentit, i cili do të shtrihet përtej pozicionit të tij nominal.
Ne mund të kërkojmë një rrugë përmes kësaj rrjete, përsëri duke përdorur algoritmin A*. Kjo do të na japë një rrugë pothuajse të përsosur në botë, e cila merr parasysh të gjithë gjeometrinë dhe nuk kërkon nyje të panevojshme dhe krijimin e pikave të rrugës.
Gjetja e shtigjeve është një temë shumë e gjerë për të cilën nuk mjafton një seksion i një artikulli. Nëse dëshironi ta studioni më në detaje, atëherë kjo do t'ju ndihmojë .
Планирование
Ne kemi mësuar me gjetjen e shtigjeve se ndonjëherë nuk mjafton vetëm të zgjedhim një drejtim dhe të lëvizim - ne duhet të zgjedhim një rrugë dhe të bëjmë disa kthesa për të arritur në destinacionin tonë të dëshiruar. Mund ta përgjithësojmë këtë ide: arritja e një qëllimi nuk është vetëm hapi tjetër, por një sekuencë e tërë ku ndonjëherë duhet të shikoni përpara disa hapa për të zbuluar se cili duhet të jetë i pari. Ky quhet planifikim. Gjetja e rrugës mund të mendohet si një nga disa zgjerime të planifikimit. Për sa i përket ciklit tonë Sense/Mendo/Vepro, këtu pjesa Think planifikon pjesë të shumta të Aktit për të ardhmen.
Le të shohim shembullin e lojës Magic: The Gathering. Ne shkojmë së pari me grupin e mëposhtëm të kartave në duart tona:
- Swamp - Jep 1 mana të zezë (kartë toke).
- Pylli - jep 1 mana jeshile (kartë toke).
- Magjistari i arratisur - Kërkon 1 mana blu për të thirrur.
- Elvish Mystic - Kërkon 1 mana jeshile për t'u thirrur.
Ne i shpërfillim tre letrat e mbetura për ta bërë më të lehtë. Sipas rregullave, një lojtar lejohet të luajë 1 kartë tokësore për kthesë, ai mund të "trokisë" këtë kartë për të nxjerrë mana prej saj dhe më pas të bëjë magji (duke përfshirë thirrjen e një krijese) sipas sasisë së mana. Në këtë situatë, lojtari njerëzor di të luajë Forest, të trokasë 1 mana jeshile dhe më pas të thërrasë Elvish Mystic. Por si mund ta kuptojë këtë inteligjenca artificiale e lojës?
Planifikimi i lehtë
Qasja e parëndësishme është të provoni çdo veprim me radhë derisa të mos mbeten më të përshtatshmet. Duke parë kartat, AI sheh se çfarë mund të luajë Swamp. Dhe ai e luan atë. A ka mbetur ndonjë veprim tjetër nga kjo kthesë? Nuk mund të thërrasë as Elvish Mystic as Fugitive Wizard, pasi ata kërkojnë përkatësisht mana jeshile dhe blu për t'i thirrur, ndërsa Swamp ofron vetëm mana të zezë. Dhe ai nuk do të mund të luajë më Forest, sepse ai tashmë ka luajtur Moçal. Kështu, loja AI ndoqi rregullat, por e bëri atë keq. Mund të përmirësohet.
Planifikimi mund të gjejë një listë veprimesh që e sjellin lojën në gjendjen e dëshiruar. Ashtu si çdo shesh në një shteg kishte fqinjë (në gjetjen e shtigjeve), çdo veprim në një plan gjithashtu ka fqinjë ose pasues. Ne mund t'i kërkojmë këto veprime dhe veprime të mëvonshme derisa të arrijmë gjendjen e dëshiruar.
Në shembullin tonë, rezultati i dëshiruar është "thirrni një krijesë nëse është e mundur". Në fillim të kthesës, ne shohim vetëm dy veprime të mundshme të lejuara nga rregullat e lojës:
1. Luaj Swamp (rezultati: Swamp në lojë)
2. Luaj Forest (rezultati: Forest në lojë)
Çdo veprim i ndërmarrë mund të çojë në veprime të mëtejshme dhe të mbyllë të tjerët, përsëri në varësi të rregullave të lojës. Imagjinoni se kemi luajtur Swamp - kjo do të heqë Swamp si hapin tjetër (ne kemi luajtur tashmë), dhe kjo do të heqë gjithashtu Forest (sepse sipas rregullave ju mund të luani një kartë toke për kthesë). Pas kësaj, AI shton marrjen e 1 mana të zezë si hapin tjetër sepse nuk ka mundësi të tjera. Nëse ai shkon përpara dhe zgjedh Tap the Swamp, ai do të marrë 1 njësi mana të zezë dhe nuk do të jetë në gjendje të bëjë asgjë me të.
1. Luaj Swamp (rezultati: Swamp në lojë)
1.1 "Tap" Swamp (rezultati: Swamp "trokitur", +1 njësi mana e zezë)
Nuk ka veprime të disponueshme - FUND
2. Luaj Forest (rezultati: Forest në lojë)
Lista e veprimeve ishte e shkurtër, arritëm në një rrugë pa krye. Ne e përsërisim procesin për hapin tjetër. Ne luajmë Forest, hapim veprimin "merr 1 mana jeshile", i cili nga ana tjetër do të hapë veprimin e tretë - thërrasë Elvish Mystic.
1. Luaj Swamp (rezultati: Swamp në lojë)
1.1 "Tap" Swamp (rezultati: Swamp "trokitur", +1 njësi mana e zezë)
Nuk ka veprime të disponueshme - FUND
2. Luaj Forest (rezultati: Forest në lojë)
2.1 Pylli "Tap" (rezultati: Pylli "përgjohet", +1 njësi mana jeshile)
2.1.1 Thirr Elvish Mystic (rezultati: Elvish Mystic në lojë, -1 mana jeshile)
Nuk ka veprime të disponueshme - FUND
Më në fund, ne eksploruam të gjitha veprimet e mundshme dhe gjetëm një plan që thërret një krijesë.
Ky është një shembull shumë i thjeshtuar. Këshillohet që të zgjidhni planin më të mirë të mundshëm, në vend të çdo plani që plotëson disa kritere. Në përgjithësi është e mundur të vlerësohen planet e mundshme bazuar në rezultatin ose përfitimin e përgjithshëm të zbatimit të tyre. Ju mund t'i shënoni vetes 1 pikë për të luajtur një kartë tokësore dhe 3 pikë për të thirrur një krijesë. Luajtja e Swamp do të ishte një plan me 1 pikë. Dhe duke luajtur Forest → Prekni Forest → thirrni Elvish Mystic do të japë menjëherë 4 pikë.
Kështu funksionon planifikimi në Magic: The Gathering, por e njëjta logjikë vlen edhe në situata të tjera. Për shembull, lëvizja e një pengu për t'i krijuar hapësirë peshkopit që të lëvizë në shah. Ose mbulohuni pas një muri për të xhiruar në mënyrë të sigurt në XCOM si kjo. Në përgjithësi, ju e kuptoni idenë.
Planifikimi i përmirësuar
Ndonjëherë ka shumë veprime të mundshme për të shqyrtuar çdo opsion të mundshëm. Kthimi te shembulli me Magic: The Gathering: le të themi se në lojë dhe në dorën tuaj ka disa karta toke dhe krijesash - numri i kombinimeve të mundshme të lëvizjeve mund të jetë në dhjetëra. Ka disa zgjidhje për problemin.
Metoda e parë është zinxhiri prapa. Në vend që të provoni të gjitha kombinimet, është më mirë të filloni me rezultatin përfundimtar dhe të përpiqeni të gjeni një rrugë të drejtpërdrejtë. Në vend që të shkojmë nga rrënja e pemës në një gjethe specifike, ne lëvizim në drejtim të kundërt - nga gjethja në rrënjë. Kjo metodë është më e lehtë dhe më e shpejtë.
Nëse armiku ka 1 shëndet, mund të gjeni planin "marrëveshje 1 ose më shumë dëme". Për ta arritur këtë, duhet të plotësohen një sërë kushtesh:
1. Dëmi mund të shkaktohet nga një magji - duhet të jetë në dorë.
2. Për të bërë një magji, ju duhet mana.
3. Për të marrë mana, duhet të luani një kartë tokësore.
4. Për të luajtur një kartë tokësore, duhet ta keni në dorë.
Një mënyrë tjetër është kërkimi më i miri. Në vend që të provojmë të gjitha rrugët, ne zgjedhim atë më të përshtatshmen. Më shpesh, kjo metodë jep planin optimal pa kosto të panevojshme kërkimi. A* është një formë e kërkimit më të mirë të parë - duke ekzaminuar nga fillimi rrugët më premtuese, ai tashmë mund të gjejë rrugën më të mirë pa pasur nevojë të kontrollojë opsionet e tjera.
Një opsion interesant dhe gjithnjë e më i popullarizuar i kërkimit të parë më të mirë është Kërkimi i Pemës në Monte Carlo. Në vend që të hamendësojë se cilat plane janë më të mira se të tjerat kur zgjedh çdo veprim pasues, algoritmi zgjedh pasues të rastësishëm në çdo hap derisa të arrijë në fund (kur plani rezultoi me fitore ose humbje). Rezultati përfundimtar përdoret më pas për të rritur ose ulur peshën e opsioneve të mëparshme. Duke e përsëritur këtë proces disa herë radhazi, algoritmi jep një vlerësim të mirë se cila është lëvizja më e mirë e radhës, edhe nëse situata ndryshon (nëse armiku ndërmerr veprime për të ndërhyrë me lojtarin).
Asnjë histori rreth planifikimit në lojëra nuk do të ishte e plotë pa Planifikimin e Veprimit të Orientuar në Qëllim ose GOAP (planifikimin e veprimit të orientuar drejt qëllimit). Kjo është një metodë e përdorur dhe e diskutuar gjerësisht, por përveç disa detajeve dalluese, është në thelb metoda e zinxhirit prapa për të cilën folëm më parë. Nëse objektivi ishte "shkatërrimi i lojtarit" dhe lojtari është pas mbulesës, plani mund të ishte: shkatërroni me një granatë → merrni atë → hidheni.
Zakonisht ka disa qëllime, secili me prioritetin e vet. Nëse objektivi me prioritet më të lartë nuk mund të realizohet (asnjë kombinim i veprimeve nuk krijon një plan "vras lojtarin" sepse lojtari nuk është i dukshëm), AI do të kthehet në objektivat me prioritet më të ulët.
Trajnimi dhe përshtatja
Ne kemi thënë tashmë se AI i lojës zakonisht nuk përdor mësimin e makinerive sepse nuk është i përshtatshëm për menaxhimin e agjentëve në kohë reale. Por kjo nuk do të thotë që ju nuk mund të huazoni diçka nga kjo zonë. Ne duam një kundërshtar në gjuajtës nga i cili mund të mësojmë diçka. Për shembull, mësoni për pozicionet më të mira në hartë. Ose një kundërshtar në një lojë luftarake i cili do të bllokonte lëvizjet e kombinuara të përdorura shpesh të lojtarit, duke e motivuar atë të përdorë të tjerët. Pra, mësimi i makinës mund të jetë mjaft i dobishëm në situata të tilla.
Statistikat dhe probabilitetet
Përpara se të hyjmë në shembuj kompleksë, le të shohim se sa larg mund të shkojmë duke marrë disa matje të thjeshta dhe duke i përdorur ato për të marrë vendime. Për shembull, strategjia në kohë reale - si e përcaktojmë nëse një lojtar mund të nisë një sulm në minutat e para të lojës dhe çfarë mbrojtjeje të përgatitet kundër kësaj? Ne mund të studiojmë përvojat e kaluara të një lojtari për të kuptuar se cilat mund të jenë reagimet e ardhshme. Si fillim, ne nuk kemi të dhëna të tilla të papërpunuara, por mund t'i mbledhim ato - sa herë që AI luan kundër një njeriu, mund të regjistrojë kohën e sulmit të parë. Pas disa seancave, ne do të marrim një mesatare të kohës që do t'i duhet lojtarit për të sulmuar në të ardhmen.
Ekziston edhe një problem me vlerat mesatare: nëse një lojtar nxitoi 20 herë dhe luan ngadalë 20 herë, atëherë vlerat e kërkuara do të jenë diku në mes dhe kjo nuk do të na japë asgjë të dobishme. Një zgjidhje është të kufizoni të dhënat hyrëse - mund të merren parasysh 20 pjesët e fundit.
Një qasje e ngjashme përdoret kur vlerësohet mundësia e veprimeve të caktuara duke supozuar se preferencat e kaluara të lojtarit do të jenë të njëjta në të ardhmen. Nëse një lojtar na sulmon pesë herë me top zjarri, dy herë me rrufe dhe një herë me përleshje, është e qartë se ai preferon topin e zjarrit. Le të ekstrapolojmë dhe të shohim probabilitetin e përdorimit të armëve të ndryshme: top i zjarrit=62,5%, rrufe=25% dhe përleshje=12,5%. Lojëra jonë AI duhet të përgatitet për t'u mbrojtur nga zjarri.
Një metodë tjetër interesante është përdorimi i Klasifikuesit Naive Bayes për të studiuar sasi të mëdha të të dhënave hyrëse dhe për të klasifikuar situatën në mënyrë që AI të reagojë në mënyrën e dëshiruar. Klasifikuesit Bayesian janë më të njohur për përdorimin e tyre në filtrat e postës elektronike të padëshiruar. Atje ata ekzaminojnë fjalët, i krahasojnë ato me vendin ku ato fjalë janë shfaqur më parë (në mesazhe të padëshiruara ose jo) dhe nxjerrin përfundime në lidhje me emailet hyrëse. Ne mund të bëjmë të njëjtën gjë edhe me më pak inpute. Bazuar në të gjitha informacionet e dobishme që AI sheh (si p.sh. cilat njësi armike janë krijuar, ose cilat magji përdorin, ose cilat teknologji kanë hulumtuar), dhe rezultati përfundimtar (luftë ose paqe, nxitim ose mbrojtje, etj.) - ne do të zgjedhim sjelljen e dëshiruar të AI.
Të gjitha këto metoda trajnimi janë të mjaftueshme, por këshillohet përdorimi i tyre bazuar në të dhënat e testimit. AI do të mësojë të përshtatet me strategjitë e ndryshme që kanë përdorur testuesit tuaj. AI që përshtatet me lojtarin pas lëshimit mund të bëhet shumë e parashikueshme ose shumë e vështirë për t'u mposhtur.
Përshtatja e bazuar në vlerë
Duke pasur parasysh përmbajtjen e botës sonë të lojës dhe rregullat, ne mund të ndryshojmë grupin e vlerave që ndikojnë në vendimmarrje, në vend që thjesht të përdorim të dhënat hyrëse. Ne e bëjmë këtë:
- Lëreni AI të mbledhë të dhëna për gjendjen e botës dhe ngjarjet kryesore gjatë lojës (si më sipër).
- Le të ndryshojmë disa vlera të rëndësishme bazuar në këto të dhëna.
- Ne i zbatojmë vendimet tona bazuar në përpunimin ose vlerësimin e këtyre vlerave.
Për shembull, një agjent ka disa dhoma për të zgjedhur në një hartë gjuajtëse në vetën e parë. Çdo dhomë ka vlerën e vet, e cila përcakton se sa e dëshirueshme është të vizitohet. Inteligjenca artificiale zgjedh rastësisht në cilën dhomë të shkojë bazuar në vlerën. Agjenti më pas kujton se në cilën dhomë u vra dhe ia zvogëlon vlerën (probabilitetin që ai të kthehet atje). Në mënyrë të ngjashme për situatën e kundërt - nëse agjenti shkatërron shumë kundërshtarë, atëherë vlera e dhomës rritet.
Modeli Markov
Po sikur të përdorim të dhënat e mbledhura për të bërë parashikime? Nëse kujtojmë çdo dhomë në të cilën shohim një lojtar për një periudhë të caktuar kohe, ne do të parashikojmë se në cilën dhomë mund të shkojë lojtari. Duke gjurmuar dhe regjistruar lëvizjet e lojtarit nëpër dhoma (vlera), ne mund t'i parashikojmë ato.
Le të marrim tre dhoma: të kuqe, jeshile dhe blu. Dhe gjithashtu vëzhgimet që kemi regjistruar gjatë shikimit të seancës së lojës:
Numri i vëzhgimeve në secilën dhomë është pothuajse i barabartë - ne ende nuk e dimë se ku të bëjmë një vend të mirë për një pritë. Mbledhja e statistikave është gjithashtu e ndërlikuar nga riprodhimi i lojtarëve, të cilët shfaqen në mënyrë të barabartë në të gjithë hartën. Por të dhënat për dhomën tjetër që futen pasi shfaqen në hartë janë tashmë të dobishme.
Mund të shihet se dhoma e gjelbër u përshtatet lojtarëve - shumica e njerëzve lëvizin nga dhoma e kuqe në të, 50% e të cilëve mbeten atje më tej. Dhoma blu, përkundrazi, nuk është e njohur; pothuajse askush nuk shkon në të, dhe nëse shkon, nuk qëndrojnë gjatë.
Por të dhënat na tregojnë diçka më të rëndësishme - kur një lojtar është në një dhomë blu, dhoma tjetër në të cilën e shohim do të jetë e kuqe, jo jeshile. Edhe pse dhoma e gjelbër është më e popullarizuar se dhoma e kuqe, situata ndryshon nëse lojtari është në dhomën blu. Gjendja tjetër (dmth dhoma në të cilën do të shkojë lojtari) varet nga gjendja e mëparshme (dmth dhoma në të cilën lojtari ndodhet aktualisht). Për shkak se ne eksplorojmë varësitë, ne do të bëjmë parashikime më të sakta sesa nëse thjesht do t'i numëronim vëzhgimet në mënyrë të pavarur.
Parashikimi i një gjendjeje të ardhshme bazuar në të dhënat nga një gjendje e kaluar quhet model Markov, dhe shembuj të tillë (me dhoma) quhen zinxhirë Markov. Meqenëse modelet përfaqësojnë probabilitetin e ndryshimeve midis gjendjeve të njëpasnjëshme, ato shfaqen vizualisht si FSM me një probabilitet rreth çdo tranzicioni. Më parë, ne përdorëm FSM për të përfaqësuar gjendjen e sjelljes në të cilën ndodhej një agjent, por ky koncept shtrihet në çdo gjendje, pavarësisht nëse është i lidhur me agjentin apo jo. Në këtë rast, shtetet përfaqësojnë dhomën që zë agjenti:
Kjo është një mënyrë e thjeshtë për të përfaqësuar gjasat relative të ndryshimeve të gjendjes, duke i dhënë AI disa aftësi për të parashikuar gjendjen e ardhshme. Ju mund të parashikoni disa hapa përpara.
Nëse një lojtar është në dhomën e gjelbër, ka 50% mundësi që ai të qëndrojë atje herën tjetër që do të vëzhgohet. Por cilat janë gjasat që ai të jetë ende aty edhe më pas? Jo vetëm që ka mundësi që lojtari të mbetet në dhomën e gjelbër pas dy vëzhgimeve, por ka edhe mundësi që të largohet dhe të kthehet. Këtu është tabela e re duke marrë parasysh të dhënat e reja:
Tregon se mundësia për të parë lojtarin në dhomën e gjelbër pas dy vëzhgimeve do të jetë e barabartë me 51% - 21% se ai do të jetë nga dhoma e kuqe, 5% e tyre që lojtari do të vizitojë dhomën blu mes tyre, dhe 25% që lojtari nuk do të largohet nga dhoma e gjelbër.
Tabela është thjesht një mjet vizual - procedura kërkon vetëm shumëzimin e probabiliteteve në çdo hap. Kjo do të thotë që ju mund të shikoni larg në të ardhmen me një paralajmërim: ne supozojmë se mundësia për të hyrë në një dhomë varet tërësisht nga dhoma aktuale. Kjo quhet Prona Markov - gjendja e ardhshme varet vetëm nga e tashmja. Por kjo nuk është njëqind për qind e saktë. Lojtarët mund të ndryshojnë vendimet në varësi të faktorëve të tjerë: niveli shëndetësor ose sasia e municionit. Për shkak se ne nuk i regjistrojmë këto vlera, parashikimet tona do të jenë më pak të sakta.
N-Gramë
Po shembulli i një loje luftarake dhe parashikimi i lëvizjeve të kombinuara të lojtarit? E njëjta! Por në vend të një gjendjeje ose ngjarjeje, ne do të shqyrtojmë të gjitha sekuencat që përbëjnë një goditje të kombinuar.
Një mënyrë për ta bërë këtë është të ruani çdo hyrje (të tilla si Kick, Punch ose Block) në një buffer dhe të shkruani të gjithë bufferin si një ngjarje. Kështu që lojtari shtyp në mënyrë të përsëritur Kick, Kick, Punch për të përdorur sulmin SuperDeathFist, sistemi AI ruan të gjitha hyrjet në një tampon dhe kujton tre të fundit të përdorura në çdo hap.
(Rreshtat me shkronja të zeza janë kur lojtari fillon sulmin SuperDeathFist.)
AI do të shohë të gjitha opsionet kur lojtari zgjedh Kick, i ndjekur nga një tjetër Kick, dhe më pas vëren se hyrja tjetër është gjithmonë Punch. Kjo do t'i lejojë agjentit të parashikojë lëvizjen e kombinuar të SuperDeathFist dhe ta bllokojë atë nëse është e mundur.
Këto sekuenca ngjarjesh quhen N-gram, ku N është numri i elementeve të ruajtura. Në shembullin e mëparshëm ishte një 3-gram (trigram), që do të thotë: dy hyrjet e para përdoren për të parashikuar të tretën. Prandaj, në një 5-gram, katër hyrjet e para parashikojnë të pestën dhe kështu me radhë.
Projektuesi duhet të zgjedhë me kujdes madhësinë e N-gramëve. Një N më i vogël kërkon më pak memorie, por gjithashtu ruan më pak histori. Për shembull, një 2-gram (bigram) do të regjistrojë Kick, Kick ose Kick, Punch, por nuk do të jetë në gjendje të ruajë Kick, Kick, Punch, kështu që AI nuk do t'i përgjigjet kombinimit SuperDeathFist.
Nga ana tjetër, numrat më të mëdhenj kërkojnë më shumë memorie dhe AI do të jetë më e vështirë për t'u trajnuar pasi do të ketë shumë më tepër opsione të mundshme. Nëse do të kishit tre hyrje të mundshme të Kick, Punch ose Block, dhe ne përdornim një 10-gram, do të ishin rreth 60 mijë opsione të ndryshme.
Modeli bigram është një zinxhir i thjeshtë Markov - çdo çift i gjendjes së kaluar/gjendjes aktuale është një bigram, dhe ju mund të parashikoni gjendjen e dytë bazuar në të parën. N-gramët 3 gram dhe më të mëdhenj mund të mendohen gjithashtu si zinxhirë Markov, ku të gjithë elementët (përveç atij të fundit në gram N) së bashku formojnë gjendjen e parë dhe elementi i fundit të dytin. Shembulli i lojës luftarake tregon mundësinë e kalimit nga gjendja Kick and Kick në gjendjen Kick and Punch. Duke i trajtuar hyrjet e shumta të historisë së hyrjes si një njësi e vetme, ne në thelb po e transformojmë sekuencën e hyrjes në një pjesë të gjendjes së plotë. Kjo na jep veçorinë Markov, e cila na lejon të përdorim zinxhirët Markov për të parashikuar hyrjen e radhës dhe për të gjetur se cila lëvizje e kombinuar do të jetë më pas.
Përfundim
Ne folëm për mjetet dhe qasjet më të zakonshme në zhvillimin e inteligjencës artificiale. Ne shikuam gjithashtu situatat në të cilat ato duhet të përdoren dhe ku janë veçanërisht të dobishme.
Kjo duhet të jetë e mjaftueshme për të kuptuar bazat e lojës AI. Por, sigurisht, këto nuk janë të gjitha metodat. Më pak të njohura, por jo më pak efektive përfshijnë:
- algoritme optimizimi duke përfshirë ngjitjen në kodra, zbritjen gradient dhe algoritmet gjenetike
- algoritmet e kërkimit/planifikimit kundërshtar (krasitja minimale dhe alfa-beta)
- metodat e klasifikimit (perceptronet, rrjetet nervore dhe makinat e vektorit mbështetës)
- sistemet për përpunimin e perceptimit dhe kujtesës së agjentëve
- qasje arkitekturore ndaj AI (sistemet hibride, arkitekturat e nëngrupeve dhe mënyra të tjera të mbivendosjes së sistemeve të AI)
- mjetet e animacionit (planifikimi dhe koordinimi i lëvizjes)
- faktorët e performancës (niveli i detajeve, në çdo kohë dhe algoritmet e ndarjes kohore)
Burimet në internet mbi temën:
1. GameDev.net ka Dhe .
2. përmban shumë prezantime dhe artikuj mbi një gamë të gjerë temash që lidhen me zhvillimin e lojës AI.
3. përfshin tema nga Samiti i GDC AI, shumë prej të cilave janë të disponueshme falas.
4. Materialet e dobishme mund të gjenden gjithashtu në faqen e internetit .
5. Tommy Thompson, studiues i AI dhe zhvillues lojërash, bën video në YouTube me një shpjegim dhe studim të AI në lojërat komerciale.
Libra me temë:
1. Seria e librave Game AI Pro është një koleksion artikujsh të shkurtër që shpjegojnë se si të zbatoni veçori specifike ose si të zgjidhni probleme specifike.
2. Seria e programimit të lojërave AI Wisdom është paraardhësi i serisë Game AI Pro. Ai përmban metoda më të vjetra, por pothuajse të gjitha janë të rëndësishme edhe sot.
3. është një nga tekstet bazë për të gjithë ata që duan të kuptojnë fushën e përgjithshme të inteligjencës artificiale. Ky nuk është një libër për zhvillimin e lojërave - ai mëson bazat e AI.
Burimi: www.habr.com