Nata shkova nĂ« njĂ« material interesant mbi inteligjencĂ«n artificiale nĂ« lojĂ«ra. Me shpjegime tĂ« koncepteve bazĂ« mbi AI nĂ« shembuj tĂ« thjeshtĂ«, dhe gjithashtu pĂ«rmban shumĂ« mjete dhe metoda tĂ« dobishme pĂ«r zhvillimin dhe projektimin e tij tĂ« pĂ«rshtatshĂ«m. Si, ku dhe kur t'i pĂ«rdorĂ«sh ato â gjithashtu Ă«shtĂ« aty.
Shumica e shembujve janë shkruar në pseudokod, kështu që njohuri të thella mbi programimin nuk do të nevojiten. Poshtë keni 35 faqe teksti me imazhe dhe GIF-e, kështu që përgatituni.
UPD. MĂ« vjen keq, por kam bĂ«rĂ« tashmĂ« njĂ« pĂ«rkthim tĂ« kĂ«tij artikulli nĂ« Habra. . Mund ta lexoni versionin e tij. , por pĂ«r ndonjĂ« arsye artikulli mĂ« ka shpĂ«tuar (kam pĂ«rdorur kĂ«rkimin, por diçka nuk shkoi siç duhet). Dhe duke qenĂ« se shkruaj nĂ« njĂ« blog tĂ« dedikuar zhvillimit tĂ« lojĂ«rave, vendosa tĂ« lĂ« versionin tim tĂ« pĂ«rkthimit pĂ«r ndjekĂ«sit (disa momente janĂ« formuluar ndryshe, disa â janĂ« lĂ«nĂ« qĂ«llimisht jashtĂ« sipas kĂ«shillave tĂ« zhvilluesve).
ĂfarĂ« Ă«shtĂ« inteligjenca artificiale?
Inteligjenca artificiale e lojërave përqendrohet në veprimet që një objekt duhet të kryejë, në varësi të kushteve në të cilat ndodhet. Kjo zakonisht quhet menaxhimi i "agjentëve inteligjentë", ku agjenti është një personazh loje, një mjet, një bot, dhe ndonjëherë edhe diçka më abstrakte: një grup i tërë entitetesh ose madje një civilization. Në çdo rast, kjo është diçka që duhet të shohë mjedisin e saj, të marrë vendime në përputhje me të, dhe të veprojë në përputhje me ato. Ky proces quhet cikli Sense/Think/Act (Ndjeni/Mendoni/Vepra):
- Sense: agjenti gjen ose merr informacion mbi gjërat në mjedisin e tij që mund të ndikojnë në sjelljen e tij (kërcënime në afërsi, objekte për t'u mbledhur, vende interesante për tu eksploruar).
- Think: agjenti vendos si të reagojë (vlerëson nëse është mjaft e sigurt të mbledhë objekte ose nëse duhet fillimisht të luftojë/zhvillohet).
- Act: agjenti kryen veprime për të realizuar vendimin e mëparshëm (nisi lëvizjen drejt armikut ose objektit).
- âŠtani situata ka ndryshuar pĂ«r shkak tĂ« veprimeve tĂ« personazheve, kĂ«shtu qĂ« cikli pĂ«rsĂ«ritet me informacion tĂ« ri.
AI, në përgjithësi, përqendrohet 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 interpretojnë. Zakonisht, kjo bëhet nga mësimi makinerik, i cili përpunon të dhënat hyrëse dhe u jep kuptim atyre, duke nxjerrë informacion semantik si "ka një makinë tjetër 20 hapa përpara jush". Këto quhen probleme klasifikimi.
LojĂ«rat nuk kanĂ« nevojĂ« pĂ«r njĂ« sistem tĂ« komplikuar pĂ«r tĂ« nxjerrĂ« informacion, pasi shumica e tĂ« dhĂ«nave tashmĂ« Ă«shtĂ« njĂ« pjesĂ« e pandashme e saj. Nuk ka nevojĂ« tĂ« ekzekutohen algoritme njohjeje tĂ« imazheve pĂ«r tĂ« pĂ«rcaktuar nĂ«se ka njĂ« armik pĂ«rpara â loja tashmĂ« e di dhe e transmeton informacionin direkt nĂ« procesin e vendimmarrjes. Prandaj, pjesa e ciklit Sense shpesh Ă«shtĂ« shumĂ« mĂ« e thjeshtĂ« se Think dhe Act.
Kufizimet e IA në lojëra
IA ka një sërë kufizimesh që duhet të respektohen:
- IA nuk ka nevojĂ« tĂ« trajnohet paraprakisht, siç bĂ«het me algoritmet e mĂ«simit makinerik. ĂshtĂ« pa kuptim tĂ« shkruash njĂ« rrjet nervor gjatĂ« zhvillimit pĂ«r tĂ« vĂ«zhguar dhjetĂ«ra mijĂ«ra lojtarĂ« dhe pĂ«r tĂ« studiuar mĂ«nyrĂ«n mĂ« tĂ« mirĂ« tĂ« lojĂ«s kundĂ«r tyre. Pse? Sepse loja nuk Ă«shtĂ« lĂ«shuar, dhe nuk ka lojtarĂ«.
- Loja duhet të argëtojë dhe të sfidojë, prandaj agjentët nuk duhet të gjejnë qasjen më të mirë kundër njerëzve.
- Agjentët duhet të duken realistikë, në mënyrë që lojtarët të ndihen sikur po luajnë kundër njerëzve të vërtetë. Programi AlphaGo e kaloi njeriun, por hapat e zgjedhur ishin shumë larg kuptimit tradicional të lojës. Nëse loja imiton një kundërshtar njeri, një ndjenjë e tillë nuk duhet të ekzistojë. Algoritmi duhet të ndryshohet për të marrë vendime të besueshme, e jo ideale.
- IA duhet tĂ« punojĂ« nĂ« kohĂ« reale. Kjo do tĂ« thotĂ« se algoritmi nuk mund tĂ« monopolizojĂ« pĂ«rdorimin e procesorit pĂ«r njĂ« kohĂ« tĂ« gjatĂ« pĂ«r tĂ« marrĂ« vendime. Edhe 10 milisekonda pĂ«r kĂ«tĂ« â Ă«shtĂ« shumĂ« gjatĂ«, sepse shumicĂ«s sĂ« lojĂ«rave u mjaftojnĂ« nga 16 nĂ« 33 milisekonda pĂ«r tĂ« kryer tĂ« gjithĂ« pĂ«rpunimin dhe pĂ«r t'u kaluar nĂ« kadrin e ardhshĂ«m tĂ« grafikĂ«s.
- Idealisht, ndonjë pjesë e sistemit duhet të drejtohet nga të dhënat, kështu që "not-koduesit" mund të bëjnë ndryshime, dhe që rregullimet të ndodhin më shpejt.
Le të shqyrtojmë qasje të IA që mbulojnë gjithë ciklin Sense/Think/Act.
Marrja e vendimeve bazike
TĂ« fillojmĂ« me lojĂ«n mĂ« tĂ« thjeshtĂ« â Pong. QĂ«llimi: tĂ« lĂ«vizni platformĂ«n (paddle) nĂ« mĂ«nyrĂ« qĂ« topi tĂ« riciklohet nga ajo dhe tĂ« mos kalojĂ« pĂ«rmes. Kjo Ă«shtĂ« si tenisi, nĂ« tĂ« cilin humbni nĂ«se nuk e godisni topin. KĂ«tu, AI ka njĂ« detyrĂ« relativisht tĂ« lehtĂ« â tĂ« vendosĂ« nĂ« cilĂ«n drejtim tĂ« lĂ«vizĂ« platformĂ«n.
Operatorët e kushtëzuar
Për AI në Pong, zgjidhja më e dukshme është të përpiqet gjithmonë të vendosë platformën poshtë topit.
Një algoritëm i thjeshtë për këtë, i shkruar në pseudokod:
çdo kornizë/përditësim ndërsa lojtaria është duke u luajtur:
nëse topi është në të majtë të paddle:
lëviz platformën në të majtë
ndryshe nëse topi është në të djathtë të paddle:
lëviz platformën në të djathtë
Nëse platforma lëviz me shpejtësinë e topit, atëherë ky është algoritmi ideal për AI në Pong. Nuk ka nevojë ta komplikohet, nëse të dhënat dhe veprimet e mundshme për agentin nuk janë shumë.
Ky qasje është aq e thjeshtë, saqë e gjithë cikli Sense/Think/Act është pothuajse i padukshëm. Por ai është aty:
- Pjesa Sense është në dy operatorët if. Loja di se ku është topi dhe ku është platforma, kështu që AI i referohet asaj për këtë informacion.
- Pjesa Think pĂ«rfshin gjithashtu dy operatorĂ« if. Ato pĂ«rfaqĂ«sojnĂ« dy zgjidhje, tĂ« cilat nĂ« kĂ«tĂ« rast janĂ« ekskluzive. Si rezultat, pĂ«rzgjidhet njĂ« nga tre veprimet â tĂ« lĂ«vizni platformĂ«n nĂ« tĂ« majtĂ«, tĂ« lĂ«vizni nĂ« tĂ« djathtĂ«, ose tĂ« mos bĂ«ni asgjĂ«, nĂ«se ajo tashmĂ« Ă«shtĂ« pozicionuar siç duhet.
- Pjesa Act ndodhet në operatorët Move Paddle Left dhe Move Paddle Right. Në varësi të dizajnit të lojës, ato mund të lëvizin platformën menjëherë ose me një shpejtësi të caktuar.
Qasje tĂ« tilla quhen reaguese â ka njĂ« grup tĂ« thjeshtĂ« rregullash (nĂ« kĂ«tĂ« rast operatorĂ« if nĂ« kod), tĂ« cilat reagojnĂ« ndaj gjendjes aktuale tĂ« botĂ«s dhe veprojnĂ«.
Pema e vendimeve
Shembulli i lojĂ«s Pong nĂ« fakt Ă«shtĂ« i barabartĂ« me konceptin formal tĂ« AI, tĂ« quajtur pema e vendimeve. Algoritmi kalon pĂ«rmes saj pĂ«r tĂ« arritur nĂ« «gjethe» â njĂ« vendim se cilin veprim tĂ« marrĂ«.
Të bëjmë një diagram rrjedhe për pemën e vendimeve për algoritmin tonë të platformës:
Ădo pjesĂ« e pemĂ«s quhet node (nyje) â AI pĂ«rdor teorinĂ« e grafikĂ«ve pĂ«r tĂ« pĂ«rshkruar struktura tĂ« tilla. Ka dy lloje nyjesh:
- Nyjet e vendimmarrjes: zgjedhja midis dy alternativave në bazë të kontrollit të ndonjë kushti, ku çdo alternativë përfaqësohet si një nyje e veçantë.
- Nyjet përfundimtare: veprimi për të kryer, duke përfaqësuar vendimin përfundimtar.
Algoritmi fillon me nodin e parĂ« (ârrĂ«njĂ«nâ e pemĂ«s). Ai ose merr njĂ« vendim nĂ«se tĂ« kalojĂ« nĂ« nodin fĂ«mijĂ«, ose kryen veprimin qĂ« Ă«shtĂ« ruajtur nĂ« nod, dhe pĂ«rfundon.
Cilado qoftë përfitimi, nëse pemët e vendimeve bëjnë të njëjtën punë si operatorët if në seksionin e mëparshëm? Këtu ekziston një sistem i përbashkët, ku çdo vendim ka vetëm një kusht dhe dy rezultate të mundshme. Kjo e lejon zhvilluesin të krijojë AI nga të dhënat që përfaqësojnë vendimet në pemë, duke shmangur kodimin e tij të vështirë. Le ta paraqesim në formën e një tabeli:
Në anën e kodit do të merrni një sistem për të lexuar rreshta. Krijoni një nod për secilin prej tyre, lidheni logjikën e vendimeve në bazë të kolonës së dytë dhe nodet fëmijë në bazë të kolonave të tretë dhe të katërt. Ju ende duhet të programoni kushtet dhe veprimet, por tani struktura e lojës do të jetë më e komplikuar. Në të, ju shtoni vendime dhe veprime shtesë, dhe më pas konfiguroni tërë AI-në duke redaktuar thjesht një skedë me definicionin e pemës. Pastaj e kaloni skedën dizajnerit të lojës, i cili do të jetë në gjendje të ndryshojë sjelljen pa ribashkimin e lojës dhe ndryshimin e kodit.
Pemët e vendimeve janë shumë të dobishme kur ndërtohen automatikisht mbi bazën e një grupi të madh shembujsh (p.sh. duke përdorur algoritmin ID3). Kjo i bën ato një mjet efektiv dhe të lartë në performancë për klasifikimin e situatave në bazë të të dhënave të marra. Sidoqoftë, ne po dalim jashtë një sistemi të thjeshtë për zgjedhjen e veprimeve nga agjentët.
Skenarët
Ne kemi shqyrtuar sistemin e pemĂ«ve tĂ« vendimeve, i cili pĂ«rdorte kushte dhe veprime tĂ« krijuara pĂ«rpara. Njeriu qĂ« projektan AI-nĂ« mund tĂ« organizojĂ« pemĂ«n siç dĂ«shiron, por ai ende duhet tĂ« mbĂ«shtetet tek programuesi qĂ« e ka koduar atĂ« tĂ« gjithĂ«. ĂfarĂ« nĂ«se do tĂ« mund tĂ« jepnim dizajnerit mjete pĂ«r tĂ« krijuar kushtet ose veprimet e tij tĂ« veta?
Për të mos bërë që programuesi të shkruajë kod për kushtet Is Ball Left Of Paddle dhe Is Ball Right Of Paddle, ai mund të krijojë një sistem, ku dizajneri do të regjistrojë kushtet për të kontrolluar këto vlera. Atëherë të dhënat e pemës së vendimeve do të duken kështu:
Në thelb, kjo është e njëjtë me tabelën e parë, por zgjidhjet përmbajnë kodin e tyre të brendshëm, paksa të ngjashëm me pjesën kushtore të if-operatorit. Në anën e kodit, kjo do të lexohesh në kolumnën e dytë për node-t e vendimmarrjes, por në vend që të kërkojë një kusht specifik për tu ekzekutuar (A është topi majtas nga paddle), vlerëson shprehjen kushtore dhe kthen true ose false përkatësisht. Kjo bëhet me ndihmën e gjuhëve skriptuese Lua ose Angelscript. Me ndihmën e këtyre, zhvilluesi mund të marrë objektet në lojën e tij (topi dhe paddle) dhe të krijojë variabla që do të jenë të disponueshme në skenar (topi.position). Për më tepër, gjuha e skriptimit është më e thjeshtë se C++. Ajo nuk kërkon një fazë të plotë kompilimi, duke e bërë atë ideale për rregullime të shpejta të logjikës së lojës dhe i lejon "nëbrendësit" të krijojnë vetë funksionet e nevojshme.
Në shembullin e dhënë, gjuha e skripteve përdoret vetëm për vlerësimin e shprehjes kushtore, por ajo mund të përdoret gjithashtu për veprime. Për shembull, të dhënat Move Paddle Right mund të bëhen një operator skenari (topi.position.x += 10). Kështu, që veprimi gjithashtu të përcaktohet në skenar, pa pasur nevojë për programimin e Move Paddle Right.
Mund të shkojmë edhe më larg dhe të shkruajmë plotësisht një pemë vendimmarrjeje në gjuhën e skripteve. Kjo do të ishte kod në formën e operatorëve kushtorë të programuar fort (hardcoded), por ata do të ndodheshin në skedarë të jashtëm të skriptimit, dmth mund të ndryshoheshin pa kompaktimin e tërë programit. Shpesh mund të ndryshoni skedarin e skenarit direkt në lojë, për të testuar shpejt reagimet e ndryshme të AI.
Reagimi ndaj ngjarjeve
Shembujt e mësipërm i përshtaten perfekt Pong. Ata vazhdimisht ekzekutojnë ciklin Sense/Think/Act dhe veprojnë në bazë të gjendjes së fundit të botës. Por në lojëra më të ndërlikuara, duhet të reagosh ndaj ngjarjeve të veçanta, dhe jo të vlerësosh gjithçka menjëherë. Pong, në këtë rast, nuk është më një shembull i mirë. Le të zgjidhim një tjetër.
Imagjinoni njĂ« lojĂ« qĂ«llimi, ku armiqtĂ« janĂ« tĂ« palĂ«vizur derisa tĂ« zbulojnĂ« lojtarin, pas sĂ« cilĂ«s veprojnĂ« sipas "specializimit" tĂ« tyre: dikush do tĂ« niset pĂ«r tĂ« "goditur", ndonjĂ« do tĂ« sulmojĂ« nga larg. Kjo Ă«shtĂ« ende njĂ« sistem reagues themelor â "nĂ«se lojtari Ă«shtĂ« vĂ«nĂ« re, bĂ«j diçka" â por mund tĂ« ndahet logjikisht nĂ« ngjarjen Player Seen (lojtari i zbuluar) dhe reagimin (zgjidhni njĂ« pĂ«rgjigje dhe ekzekutoni atĂ«).
Kjo na kthen nĂ« ciklin Sense/Think/Act. Mund tĂ« kodojmĂ« pjesĂ«n Sense qĂ« çdo kornizĂ« do tĂ« kontrollojĂ« â a e sheh AI lojtarin. NĂ«se jo â nuk ndodh asgjĂ«, por nĂ«se e sheh, krijohet njĂ« ngjarje Player Seen. Kodi do tĂ« ketĂ« njĂ« seksion tĂ« veçantĂ«, ku thuhet: "kur ndodh ngjarja Player Seen, bĂ«j", ku â Ă«shtĂ« reagimi qĂ« ju nevojitet pĂ«r t'u drejtuar nĂ« pjesĂ«t Think dhe Act. KĂ«shtu do tĂ« vendosni reagimet pĂ«r ngjarjen Player Seen: pĂ«r njĂ« personazh "tĂ« ngutshĂ«m" â ChargeAndAttack, dhe pĂ«r njĂ« snajper â HideAndSnipe. KĂ«to lidhje mund tĂ« krijohen nĂ« skedarin e tĂ« dhĂ«nave pĂ«r redaktim tĂ« shpejtĂ« pa nevojĂ«n pĂ«r tĂ« rifilluar kompaktimin. Dhe gjithashtu mund tĂ« pĂ«rdoren gjuhĂ«t e scripting.
Marrja e vendimeve të ndërlikuara
Ndërsa sistemet e thjeshta të reagimit janë shumë efektive, ka shumë situata kur ato janë të pamjaftueshme. Ndonjëherë është e nevojshme të pranoni vendime të ndryshme, duke u bazuar në atë që agjenti po bën në atë moment, por ta paraqitni atë si një kusht është e vështirë. Ndonjëherë ka shumë kushte për t'i paraqitur në mënyrë efektive në një pemë vendimesh ose skript. Ndonjëherë është e nevojshme të vlerësohet përpara se si do të ndryshojë situata, përpara se të merret një vendim për hapat e ardhshëm. Për të zgjidhur këto probleme, janë të nevojshme qasje më të ndërlikuara.
Makinë e Shteteve të Finit
MakinĂ« e Shteteve tĂ« Finit ose FSM (finito automat) â Ă«shtĂ« njĂ« mĂ«nyrĂ« pĂ«r tĂ« thĂ«nĂ« se agjenti ynĂ« aktualisht ndodhet nĂ« njĂ« nga disa shtete tĂ« mundshme dhe se ai mund tĂ« kalojĂ« nga njĂ«ra gjendje nĂ« tjetrĂ«n. ShumĂ« shtete janĂ« tĂ« pĂ«rcaktuara â prej andej dhe emri. NjĂ« shembull mĂ« i mirĂ« nga jeta Ă«shtĂ« sinjali i trafikut. NĂ« vende tĂ« ndryshme, sekufencat e ndryshme tĂ« dritave, por principi Ă«shtĂ« i njĂ«jtĂ« â çdo gjendje pĂ«rfaqĂ«son diçka (ndal, shko etj.). Sinjali i trafikut Ă«shtĂ« gjithmonĂ« nĂ« njĂ« gjendje nĂ« çdo moment kohor, dhe kalon nga njĂ«ra nĂ« tjetrĂ«n nĂ« bazĂ« tĂ« rregullave tĂ« thjeshta.
Me NPC-të në lojëra është një histori e ngjashme. Për shembull, le të marrim një roje me këto gjendje:
- Patrullues (Patrolling).
- Duke sulmuar (Attacking).
- Duke ikur (Fleeing).
Dhe këto kushte për ndryshimin e gjendjes së tij:
- NĂ«se roja sheh armikun, ai sulmon.
- Nëse roja sulmon, por nuk sheh më armikun, ai kthehet në patrullim.
- Nëse roja sulmon, por është rëndë i plagosur, ai ikën.
Igualmente, mund të shkruajmë if-operatorë me një variabël-stanjë roje dhe kontrollime të ndryshme: a ka ndonjë armik afër, cilat janë nivelet e shëndetit të NPC-ve, etj. Do të shtojmë disa gjendje të tjera:
- Mosveprimi (Idling) â ndĂ«rmjet patrullave.
- KĂ«rkimi (Searching) â kur armiku i parĂ« Ă«shtĂ« fshehur.
- KĂ«rkesa pĂ«r ndihmĂ« (Finding Help) â kur armiku Ă«shtĂ« parĂ«, por Ă«shtĂ« shumĂ« i fortĂ« pĂ«r t'u luftuar njĂ« me njĂ«.
Zgjedhja pĂ«r secilin prej tyre Ă«shtĂ« e kufizuar â pĂ«r shembull, rojet nuk do tĂ« shkojnĂ« tĂ« kĂ«rkojnĂ« armikun e fshehur nĂ«se kanĂ« shĂ«ndet tĂ« ulĂ«t.
Në fund të fundit, lista e madhe e "nëse <x Đž y, ĐœĐŸ ĐœĐ” z>, nuk është e nevojshme, madje, ajo jep një gabim sintaksor <p>", mund të bëhet shumë e ngarkuar, prandaj duhet të formulojmë një metodë që do të na mundësojë të mbajmë mend gjendjet dhe kalimet midis gjendjeve. Për ta bërë këtë, do të marrim parasysh të gjitha gjendjet dhe nën çdo gjendje do të regjistrojmë në një listë të gjitha kalimet në gjendje të tjera, së bashku me kushtet e nevojshme për to.
Ky Ă«shtĂ« njĂ« tabelĂ« e kalimeve tĂ« gjendjeve â njĂ« mĂ«nyrĂ« komplekse pĂ«r tĂ« paraqitur FSM. Do tĂ« vizatojmĂ« njĂ« diagram dhe do tĂ« marrim njĂ« pasqyrĂ« tĂ« plotĂ« tĂ« sjelljes sĂ« NPC-ve.
Diagrami reflekton thelbin e marrjes sĂ« vendimeve pĂ«r kĂ«tĂ« agjent nĂ« bazĂ« tĂ« situatĂ«s aktuale. Ădo shigjetĂ« tregon kalimin ndĂ«rmjet gjendjeve, nĂ«se kushte afĂ«r saj janĂ« tĂ« vĂ«rteta.
NĂ« çdo pĂ«rditĂ«sim ne kontrollojmĂ« gjendjen aktuale tĂ« agjentit, shikojmĂ« listĂ«n e kalimeve, dhe nĂ«se kushtet pĂ«r kalim janĂ« tĂ« pĂ«rmbushura, ai merr njĂ« gjendje tĂ« re. PĂ«r shembull, çdo kadĂ«r kontrollohet nĂ«se ka mbaruar njĂ« timer 10-sekondĂ«sh, dhe nĂ«se po, nga gjendja Idling, rojet kalojnĂ« nĂ« Patrullim. NĂ« tĂ« njĂ«jtĂ«n mĂ«nyrĂ«, gjendja Sulmimi kontrollon shĂ«ndetin e agjentit â nĂ«se Ă«shtĂ« i ulĂ«t, ai kalon nĂ« gjendjen Ikja.
Kjo është përpunimi i kalimeve ndërmjet gjendjeve, por si për sjelljen e lidhur me vetë gjendjet? Sa i përket implementimit të sjelljes reale për një gjendje të veçantë, zakonisht ka dy lloje «krapi», ku ne disa veprime i atribuojmë FSM:
- Veprimet që ne i kryejmë periodikisht për gjendjen aktuale.
- Veprimet që ne ndërmarrim kur kalojmë nga një gjendje në njërën tjetër.
Shembuj për llojin e parë. Gjendja Patrullimi çdo kadër do të lëvizë agjentin nëpër itinerarin e patrullimit. Gjendja Sulmimi çdo kadër do të përpiqet të fillojë një sulm ose të kalojë në gjendjen kur kjo është e mundur.
Për tipin e dytë, le të shqyrtojmë kalimin «nëse armiku është i dukshëm dhe armiku është shumë i fortë, atëherë të kalojmë në gjendjen e Gjetjes së Ndihmës. Agjenti duhet të zgjedhë se ku të shkojë për ndihmë dhe të ruajë këtë informacion, në mënyrë që gjendja e Gjetjes së Ndihmës të dijë ku të drejtohet. Sapo të gjendet ndihma, agjenti kthehet në gjendjen e Sulmit. Në këtë moment, ai do të dojë të tregojë aleatit për kërcënimin, prandaj mund të ndodhi veprimi InformoAleatinPërKërcënimin.
PĂ«rsĂ«ri, ne mund ta shohim kĂ«tĂ« sistem pĂ«rmes ciklit Ndjej/Mendoj/Veproj. Ndjeni manifestohet nĂ« tĂ« dhĂ«nat qĂ« pĂ«rdoren nga logjika e kalimit. Mendoj â kalimet qĂ« janĂ« tĂ« disponueshme nĂ« çdo gjendje. Dhe VeprojmĂ« realizohet nga veprimet qĂ« kryhen pĂ«rherĂ« brenda gjendjes ose nĂ« kalimet midis gjendjeve.
NdonjĂ«herĂ«, sondazhi i vazhdueshĂ«m i kushteve tĂ« kalimit mund tĂ« jetĂ« i kushtueshĂ«m. PĂ«r shembull, nĂ«se çdo agjent do tĂ« kryejĂ« llogaritje tĂ« komplikuara pĂ«r çdo kornizĂ« pĂ«r tĂ« pĂ«rcaktuar nĂ«se sheh armikĂ« dhe tĂ« kuptojĂ« nĂ«se mund tĂ« kalojĂ« nga gjendja e Patrullimit nĂ« Sulm â kjo do tĂ« kĂ«rkonte shumĂ« kohĂ« procesori.
Ndryshimet e rëndësishme në gjendjen e botës mund të konsiderohen si ngjarje që do të përpunohen ndërsa ndodhin. Në vend që FSM të kontrollojë kushtin e kalimit «a mundet agjenti im ta shikojë lojtarin?» çdo kornizë, është e mundur të konfigurohet një sistem i veçantë për të kryer kontrollet më rrallë (për shembull, 5 herë në sekondë). Dhe rezultati do të jetë Lojtari i Dëshmuar, kur kontrolli kalon.
Kjo i kalon në FSM, i cili tani duhet të kalojë në kushtin e përfunduar të ngjarjes Lojtari i Dëshmuar dhe të reagojë në përputhje me rrethanat. Sjellja përfundimtare është e njëjtë përveç një vonese pothuajse të padukshme përpara përgjigjes. Megjithatë, performanca është përmirësuar si rezultat i ndarjes së pjesës së Ndjenjës në një pjesë të veçantë të programit.
Makinë e kufizuar e gjendjes hierarkike
Megjithatë, punimi me FSM të mëdha nuk është gjithmonë i përshtatshëm. Po të dëshironim të zgjerojmë gjendjen e sulmit, duke e zëvendësuar atë me të veçanta MeleeAttacking (sulm a pranë) dhe RangedAttacking (sulm nga larg), do të duhet të ndryshonim kalimet nga të gjitha gjendjet e tjera që çojnë në gjendjen e Sulmit (të tanishmet dhe të ardhshmet).
Sigurisht keni vënë re se në shembullin tonë ka shumë kalime të përsëritura. Shumica e kalimeve në gjendjen Idling janë identike me kalimet në gjendjen Patrolling. Do të ishte e mençur të shmangnim përsëritjen, veçanërisht nëse do të shtojmë më shumë gjendje të ngjashme. Ka kuptim të grupojmë Idling dhe Patrolling nën një etiketë të përbashkët "jo-luftarak", ku ka vetëm një grup të përbashkët kalimesh në gjendjet luftuese. Nëse e imagjinojmë këtë etiketë si një gjendje, atëherë Idling dhe Patrolling do të bëhen nën-gjendje. Një shembull i përdorimit të një tabele kalimesh të veçantë për një nën-gjendje jo-luftarake:
Gjendjet kryesore:
Gjendja jashtë beteje:
Dhe në formën e diagramit:
Kjo është e njëjta sistem, por me një gjendje të re jo-luftarake, e cila përfshin Idling dhe Patrolling. Me çdo gjendje që përmban FSM me nën-gjendje (dhe këto nën-gjendje, nga ana e tyre, përmbajnë FSM të veta - sa herë që t'ju nevojitet), ne marrim një Hierarchical Finite State Machine ose HFSM (makinë e mbyllur hierarkike). Duke grupuar gjendjen jo-luftarake, kemi eliminuar një mori kalimesh të tepërta. E njëjta gjë mund të bëhet për çdo gjendje të re me kalime të përbashkëta. Për shembull, nëse në të ardhmen zgjerimi i gjendjes Attacking në gjendjet MeleeAttacking dhe MissileAttacking, ato do të jenë nën-gjendje, duke kaluar nga njëra tek tjetra në bazë të distancës nga armiku dhe disponueshmërisë së municionit. Në përfundim, modelet e komplikuara të sjelljes dhe nën-modelet e sjelljes mund të paraqiten me një minimum kalimesh të përsëritura.
Pema e sjelljeve
Me HFSM krijohen kombinime komplekse të sjelljeve në mënyrë të thjeshtë. Megjithatë, ka një vështirësi të vogël, që marrja e vendimeve në formën e rregullave të kalimit lidhet ngushtë me gjendjen aktuale. Dhe në shumë lojëra, kjo është pikërisht ajo që ne na nevojitet. Dallimi i kujdesshëm në përdorimin e hierarkisë së gjendjeve mund të zvogëlojë numrin e përsëritjeve gjatë kalimit. Por ndonjëherë ne kemi nevojë për rregulla që funksionojnë në mënyrë të pavarur nga gjendja në të cilën ndodhemi ose që aplikohen në pothuajse çdo gjendje. Për shembull, nëse shëndeti i agjentit ka rënë në 25%, do të dëshironit që ai të arratisej pavarësisht nga se ishte në betejë, në një gjendje pasive apo në bisedë - do të duhet të shtoni këtë kusht në çdo gjendje. Dhe nëse dizajneri juaj më vonë dëshiron të ndryshojë pragun e shëndetit të ulët nga 25% në 10%, kjo do të kërkonte përsëri punë.
Idealisht, për këtë situatë nevojitet një sistem ku vendimet "në çfarë gjendje të jemi" janë jashtë vetë gjendjeve, për të bërë ndryshime vetëm në një vend dhe për të mos prekur kushtet e kalimit. Këtu dalin pemët e sjelljes.
Ka disa mënyra për t'i zbatuar ato, por thelbi për të gjitha është pak a shumë i njëjtë dhe i ngjashëm me pemën e vendimeve: algoritmi fillon nga nyja "rrënjore", ndërsa në pemë ka nyje që përfaqësojnë ose vendime, ose veprime. Megjithatë, ka disa dallime kyçe:
- Tani nyjet kthejnë një nga tre vlera: Succeeded (nëse puna është kryer), Failed (nëse nuk mund të nisë) ose Running (nëse ajo ende po ekzekutohet dhe nuk ka një rezultat përfundimtar).
- Nuk ka më nyje vendimesh për të zgjedhur midis dy alternativave. Në vend të tyre, ka nyje Decorator, të cilat kanë vetëm një nyjë fëmijë. Nëse ato arrijnë sukses, ato ekzekutojnë nyjën e tyre të vetme fëmijë.
- Nyjet që ekzekutojnë veprime kthejnë vlerën Running për të përfaqësuar veprimet që po kryhen.
Ky grup i vogël nyjesh mund të kombinohet për të krijuar një numër të madh modelesh të komplikuara të sjelljes. Le të paraqesim HFSM-në e rojeve nga shembulli i mëparshëm si një pemë sjelljeje:
Me kĂ«tĂ« strukturĂ« nuk duhet tĂ« ketĂ« njĂ« kalim tĂ« qartĂ« nga gjendjet Idling/Patrolling nĂ« gjendjen Attacking ose nĂ« ndonjĂ« tjetĂ«r. NĂ«se armiku Ă«shtĂ« i dukshĂ«m dhe shĂ«ndeti i personazhit Ă«shtĂ« i ulĂ«t, ekzekutimi do tĂ« ndalet nĂ« nyjĂ«n Fleeing, pavarĂ«sisht se cila nyjĂ« ka ekzekutuar mĂ« parĂ« â Patrolling, Idling, Attacking, ose ndonjĂ« tjetĂ«r.
PemĂ«t e sjelljeve janĂ« komplekse â ka shumĂ« mĂ«nyra pĂ«r t'i pĂ«rbĂ«rĂ« ato, dhe gjetja e kombinimit tĂ« duhur tĂ« dekoratorĂ«ve dhe nyjeve pĂ«rbĂ«rĂ«se mund tĂ« jetĂ« problematike. Ka gjithashtu pyetje rreth frekuencĂ«s sĂ« verifikimit tĂ« pemĂ«s â ne duam ta kalojmĂ« atĂ« çdo pjesĂ«, ose vetĂ«m kur ndonjĂ« nga kushtet ndryshon? Si ta ruajmĂ« gjendjen qĂ« lidhet me nyjet â si tĂ« dimĂ« kur kemi qenĂ« nĂ« gjendjen Idling pĂ«r 10 sekonda ose si tĂ« dimĂ« cilat nyje janĂ« ekzekutuar herĂ«n e fundit, pĂ«r tĂ« pĂ«rpunuar saktĂ« sekuencĂ«n?
Kjo është arsyeja pse ekzistojnë shumë implementime. Për shembull, në disa sisteme nyjet dekorator janë zëvendësuar nga dekoratorë të integruar. Ato rishikojnë përsëri pemën kur kushtet e dekoratorit ndryshojnë, ndihmojnë në bashkimin e nyjeve dhe sigurojnë përditësime periodike.
Sistemi i bazuar në utilitet
Disa lojĂ«rash kanĂ« shumĂ« mekanika tĂ« ndryshme. ĂshtĂ« e preferueshme qĂ« ato tĂ« pĂ«rfitojnĂ« nga rregulla tĂ« thjeshta dhe tĂ« pĂ«rgjithshme kalimi, por nuk Ă«shtĂ« e domosdoshme nĂ« formĂ«n e njĂ« peme tĂ« plotĂ« sjelljeje. NĂ« vend qĂ« tĂ« kemi njĂ« grup tĂ« qartĂ« zgjedhjesh ose njĂ« pemĂ« veprimesh tĂ« mundshme, Ă«shtĂ« mĂ« e thjeshtĂ« tĂ« studiojmĂ« tĂ« gjitha veprimet dhe tĂ« zgjedhim atĂ« mĂ« tĂ« pĂ«rshtatshmen nĂ« momentin aktual.
Sistemi i bazuar nĂ« dobishmĂ«ri (utility-based system) do tĂ« ndihmojĂ« pikĂ«risht nĂ« kĂ«tĂ«. ĂshtĂ« njĂ« sistem ku agjenti ka shumĂ« veprime dhe ai vetĂ« zgjedh se cilin tĂ« kryejĂ«, duke u bazuar nĂ« dobishmĂ«rinĂ« relative tĂ« secilit. Ku dobishmĂ«ria Ă«shtĂ« njĂ« masĂ« arbitrare e kĂ«saj qĂ« Ă«shtĂ« e rĂ«ndĂ«sishme ose e dĂ«shirueshme pĂ«r agjentin.
Dobishmërinë e llogaritur të veprimit, bazuar në gjendjen aktuale dhe mjedisin, agjenti mund ta verifikojë dhe të zgjedhë gjendjen tjetër më të përshtatshme në çdo kohë. Kjo është e ngjashme me FSM, përveç se kalimet përcaktohen nga vlerësimi për çdo gjendje potenciale, duke përfshirë gjendjen aktuale. Vini re se ne zgjedhim veprimin më të dobishëm për kalim (ose qëndrojmë, nëse e kemi kryer tashmë). Për më shumë larmi, kjo mund të jetë një zgjedhje e peshuar, por rastësore nga një listë e vogël.
Sistema caktinĂ« njĂ« gamĂ« tĂ« rastĂ«sishme vlerash dobishmĂ«rie â pĂ«r shembull, nga 0 (krejtĂ«sisht e padĂ«shirueshme) deri nĂ« 100 (plotĂ«sisht e dĂ«shirueshme). Ădo veprim ka njĂ« sĂ«rĂ« parametrash qĂ« ndikojnĂ« nĂ« llogaritjen e kĂ«saj vlere. Po kthehemi nĂ« shembullin tonĂ« me rojen:
Kalimet midis veprimeve janĂ« tĂ« paqartĂ« â çdo gjendje mund tĂ« ndjekĂ« çdo tjetĂ«r. Prioritetet e veprimeve ndodhen nĂ« vlerat e kthyera tĂ« dobishmĂ«risĂ«. NĂ«se armiku Ă«shtĂ« i dukshĂ«m dhe ky armik Ă«shtĂ« i fortĂ«, dhe shĂ«ndeti i personazhit Ă«shtĂ« i ulĂ«t, atĂ«herĂ« Fleeing dhe FindingHelp do tĂ« kthejnĂ« vlera tĂ« larta tĂ« padĂ«shiruara. NĂ« kĂ«tĂ« rast, FindingHelp do tĂ« jetĂ« gjithmonĂ« mĂ« e lartĂ«. Po ashtu, veprimet jo-luftuese kurrĂ« nuk kthejnĂ« mĂ« shumĂ« se 50, kĂ«shtu qĂ« ato gjithmonĂ« do tĂ« jenĂ« mĂ« tĂ« ulĂ«ta se ato luftuese. Kjo duhet marrĂ« parasysh kur krijoni veprime dhe llogaritni dobishmĂ«rinĂ« e tyre.
Në shembullin tonë, veprimet kthejnë ose një vlerë konstante fiksuar, ose një nga dy vlera fiksuara. Një sistem më realist parashikon kthimin e një vlerës nga një gamë e vazhdueshme vlerash. Për shembull, veprimi Fleeing kthen vlera më të larta të dobishmërisë nëse shëndeti i agjentit është i ulët, ndërsa veprimi Attacking kthen vlera më të ulta nëse armiku është shumë i fortë. Për këtë arsye, veprimi Fleeing ka prioritet mbi Attacking në çdo situatë kur agjenti ndjen se nuk ka mjaft shëndet për të fituar ndaj kundërshtarit. Kjo lejon ndryshimin e prioriteteve të veprimeve në bazë të një numri kriteresh, duke e bërë këtë qasje më fleksibile dhe variative se sa një pemë sjelljeje ose FSM.
Ădo veprim ka shumĂ« kushte pĂ«r llogaritjen e programit. Ato mund tĂ« shkruhen nĂ« njĂ« gjuhĂ« skenari ose si njĂ« seri formulas matematikore. NĂ« The Sims, e cila modelon rutinĂ«n e pĂ«rditshme tĂ« karakterit, shtohet njĂ« nivel shtesĂ« llogaritjesh â agjenti merr njĂ« sĂ«rĂ« "motivacionesh" qĂ« ndikojnĂ« nĂ« vlerĂ«simet e dobishmĂ«risĂ«. NĂ«se karakteri Ă«shtĂ« i uritur, me kalimin e kohĂ«s ai do tĂ« ndjehet edhe mĂ« i uritur, dhe rezultati i dobishmĂ«risĂ« sĂ« veprimit EatFood do tĂ« rritet derisa karakteri ta kryejĂ« atĂ«, duke ulur nivelin e urisĂ«, dhe duke kthyer vlerĂ«n e EatFood nĂ« zero.
Ideja për të zgjedhur veprime bazuar në një sistem vlerësimi është mjaft e thjeshtë, prandaj sistemi i bazuar në dobishmëri mund të përdoret si një pjesë e proceseve të marrjes së vendimeve të AI, dhe jo si një zëvendësim i plotë i tyre. Pema e vendimit mund të kërkojë një vlerësim dobishmërie për dy nyje nënshkruese dhe të zgjedhë atë më të lartë. Në mënyrë të ngjashme, një pemë sjelljeje mund të ketë një nyje përbërëse Utility për të vlerësuar dobishmërinë e veprimeve për të vendosur se cili element nënshkruese të ekzekutohet.
LĂ«vizja dhe navigimi
Në shembujt e mëparshëm, kishim një platformë që e lëviznim majtas ose djathtas, dhe një roje që patrullonte ose sulmonte. Por si e trajtojmë lëvizjen e agjentit gjatë një periudhe të caktuar kohore? Si e vendosim shpejtësinë, si i shmangim pengesat, dhe si e planifikojmë rrugën, nëse është më e vështirë të arrijmë në destinacion sesa thjesht të lëvizim në një vijë të drejtpërdrejtë? Le të shqyrtojmë këtë.
Menaxhimi
NĂ« fazĂ«n fillestare, le tĂ« supozojmĂ« se çdo agjent ka njĂ« vlerĂ« shpejtĂ«sie, e cila pĂ«rfshin sa shpejt ai lĂ«viz dhe nĂ« cilin drejtim. Ajo mund tĂ« matet nĂ« metra nĂ« sekondĂ«, kilometra nĂ« orĂ«, pikse nĂ« sekondĂ« etj. Duke kujtuar ciklin Sense/Think/Act, mund tĂ« pĂ«rfytyrojmĂ« se pjesa Think zgjedh shpejtĂ«sinĂ«, ndĂ«rsa pjesa Act e aplikon kĂ«tĂ« shpejtĂ«si te agjenti. Zakonisht nĂ« lojĂ«ra ka njĂ« sistem fizik qĂ« kryen kĂ«tĂ« detyrĂ« pĂ«r ju, duke shqyrtuar vlerĂ«n e shpejtĂ«sisĂ« sĂ« çdo objekti dhe duke e rregulluar atĂ«. Prandaj, mund t'i lĂ«mĂ« AI-sĂ« njĂ« detyrĂ« â tĂ« vendosĂ« se cila shpejtĂ«si duhet tĂ« ketĂ« agjenti. NĂ«se dihet ku duhet tĂ« jetĂ« agjenti, atĂ«herĂ« duhet ta lĂ«vizim atĂ« nĂ« drejtimin e duhur me shpejtĂ«sinĂ« e vendosur. NjĂ« ekuacion shumĂ« trivial:
desired_travel = destination_position â agent_position
Imagjinoni njĂ« botĂ« 2D. Agjenti Ă«shtĂ« nĂ« pikĂ«n (-2,-2), destinacioni ndodhet diku nĂ« veri-lindje nĂ« pikĂ«n (30, 20), dhe rruga e nevojshme pĂ«r agjentin pĂ«r t'u ndodhur aty Ă«shtĂ« (32, 22). Le tĂ« supozojmĂ« se kĂ«to pozita maten nĂ« metra â nĂ«se e marrim shpejtĂ«sinĂ« e agjentit si 5 metra nĂ« sekondĂ«, ne do tĂ« bĂ«jmĂ« shkallĂ«zimin e vektorit tonĂ« tĂ« lĂ«vizjes dhe do tĂ« marrim njĂ« shpejtĂ«si tĂ« pĂ«rafĂ«rt (4.12, 2.83). Me kĂ«to parametra, agjenti do tĂ« arrinte nĂ« destinacion pas gati 8 sekondash.
Vlerat mund të rivlerësohen në çdo moment. Nëse agjenti ishte në gjysmën e rrugës drejt qëllimit, lëvizja do të ishte gjysma e gjatësi, por pasi shpejtësia maksimale e agjentit është 5 m/s (këtë e vendosëm më sipër), shpejtësia do të mbetet e njëjtë. Kjo gjithashtu funksionon për objektivat në lëvizje, duke lejuar agjentin të bëjë disa ndryshime të vogla ndërsa ato lëvizin.
Por ne duam mĂ« shumĂ« variacion â pĂ«r shembull, tĂ« rrisim ngadalĂ« shpejtĂ«sinĂ« pĂ«r tĂ« simuluar njĂ« karakter qĂ« lĂ«viz nga njĂ« gjendje qĂ«ndruese nĂ« njĂ« gjendje vrapimi. E njĂ«jta gjĂ« mund tĂ« bĂ«het nĂ« fund para ndalimit. KĂ«to karakteristika janĂ« tĂ« njohura si steering behaviours, secila prej tĂ« cilave ka emra specifikĂ«: Seek (kĂ«rkesa), Flee (ikja), Arrival (ardhja) etj. Ideja Ă«shtĂ« se forcat e shpejtimit mund tĂ« aplikohen nĂ« shpejtĂ«sinĂ« e agjentit, duke u bazuar nĂ« krahasimin e pozicionit tĂ« agjentit dhe shpejtĂ«sisĂ« aktuale me pikĂ«n e destinacionit, pĂ«r tĂ« pĂ«rdorur mĂ«nyra tĂ« ndryshme pĂ«r tĂ« arritur nĂ« qĂ«llim.
Ădo sjellje ka njĂ« qĂ«llim pak mĂ« ndryshe. Seek dhe Arrival janĂ« mĂ«nyra pĂ«r tĂ« lĂ«vizur agjentin drejt destinacionit. Obstacle Avoidance (evitimi i pengesave) dhe Separation (ndarja) rregullojnĂ« lĂ«vizjen e agjentit pĂ«r tĂ« shmangur pengesat nĂ« rrugĂ«n drejt qĂ«llimit. Alignment (pĂ«rputhja) dhe Cohesion (lidhja) mbajnĂ« agjentĂ«t sĂ« bashku gjatĂ« lĂ«vizjes. Ădo numĂ«r sjelljesh tĂ« ndryshme drejtimi mund tĂ« mblidhet pĂ«r tĂ« marrĂ« njĂ« vektor rruge duke marrĂ« parasysh tĂ« gjithĂ« faktorĂ«t. Agjenti pĂ«rdor sjelljet Arrival, Separation dhe Obstacle Avoidance pĂ«r tĂ« qĂ«ndruar larg mureve dhe agjentĂ«ve tĂ« tjerĂ«. Ky qasje funksionon mirĂ« nĂ« vende tĂ« hapura pa detaje tĂ« tepruara.
Në kushte më të vështira, mbledhja e sjelljeve të ndryshme funksionon më keq - për shembull, agjenti mund të ngecë në mur për shkak të konfliktit mes Arrival dhe Obstacle Avoidance. Prandaj, duhen shqyrtuar mundësi që janë më komplekse se thjesht mbledhja e të gjithë vlerave. Një mënyrë e tillë është: në vend që të mbledhim rezultatet e çdo sjelljeje, mund të shqyrtojmë lëvizjen në drejtime të ndryshme dhe të zgjedhim opsionin më të mirë.
Megjithatë, në një ambient të ndërlikuar me rrugë të mbyllura dhe zgjedhje për në cilën anë të shkojmë, do na nevojitet diçka edhe më të avancuar.
Kërkimi i rrugës
Steering behaviours janë ideale për lëvizjen e thjeshtë në një terren të hapur (fushë futbolli ose arenë), ku të arrish nga A në B është një rrugë e drejtpërdrejtë me deviacion të vogla përtej pengesave. Për rrugë më komplekse na nevojitet pathfinding (kërkimi i rrugës), i cili është një mënyrë për të eksploruar botën dhe për të marrë vendime mbi rrugën përmes saj.
Metoda mĂ« e thjeshtĂ« Ă«shtĂ« tĂ« vendosĂ«sh njĂ« rrjet mbi çdo katror pĂ«rreth agentit dhe tĂ« vlerĂ«sosh nĂ« cilat prej tyre Ă«shtĂ« e lejuar tĂ« lĂ«vizĂ«sh. NĂ«se ndonjĂ«ra prej tyre Ă«shtĂ« destinacioni, atĂ«herĂ« ndiqni rrugĂ«n nga çdo katror deri te i mĂ«parshmi, deri sa tĂ« arrini fillimin. Ky Ă«shtĂ« itinerari. NĂ« tĂ« kundĂ«rt, pĂ«rsĂ«ritni procesin me katrorĂ«t mĂ« tĂ« afĂ«rt derisa tĂ« gjeni destinacionin ose tĂ« mbarojnĂ« katrorĂ«t (kjo do tĂ« thotĂ« se nuk ka asnjĂ« rrugĂ« tĂ« mundshme). Kjo formalitet quhet KĂ«rkimi nĂ« GjerĂ«si ose BFS (Breadth-First Search). NĂ« çdo hap, ai shqyrton nĂ« tĂ« gjitha drejtimet (prandaj gjerĂ«sia, âbreadthâ). Hapsira kĂ«rkuese duket si njĂ« front vale qĂ« lĂ«viz, derisa tĂ« arrijĂ« vendin e kĂ«rkuar â hapesira kĂ«rkuese zgjerohet nĂ« çdo hap deri sa tĂ« arrijĂ« pikĂ«n pĂ«rfundimtare, pas sĂ« cilĂ«s mund tĂ« ndjekim rrugĂ«n deri nĂ« fillim.
Si rezultat, do tĂ« keni njĂ« listĂ« katrorĂ«sh, mbi tĂ« cilat formohet itinerari i dĂ«shiruar. Kjo Ă«shtĂ« rruga (nga kĂ«tu, pathfinding) â lista e vendeve qĂ« agjenti do tĂ« vizitojĂ«, duke ndjekur pĂ«r nĂ« destinacion.
Duke marrĂ« parasysh se ne dimĂ« pozitat e çdo katrori nĂ« botĂ«, mund tĂ« pĂ«rdorim sjelljet e manovrimeve pĂ«r tĂ« lĂ«vizur nĂ«pĂ«r rrugĂ« â nga nĂ«nkategoria 1 nĂ« nĂ«nkategorinĂ« 2, pastaj nga nĂ«nkategoria 2 nĂ« nĂ«nkategorinĂ« 3 dhe kĂ«shtu me radhĂ«. Versioni mĂ« i thjeshtĂ« Ă«shtĂ« tĂ« drejtohemi nĂ« qendĂ«r tĂ« katrorit tĂ« ardhshĂ«m, por mĂ« mirĂ« Ă«shtĂ« tĂ« ndalemi nĂ« mes tĂ« skajit midis katrorit aktual dhe atij tjetĂ«r. KĂ«shtu, agjenti do tĂ« jetĂ« nĂ« gjendje tĂ« shkurtojĂ« kĂ«ndet nĂ« kthesa tĂ« ashpra.
Algoritmi BFS ka disa disavantazhe â ai eksploron njĂ« numĂ«r tĂ« barabartĂ« katrorĂ«sh nĂ« drejtimin "e gabuar" dhe nĂ« atĂ« "tĂ« duhur". KĂ«tu paraqitet njĂ« algoritĂ«m mĂ« kompleks i quajtur A* (A star). Ai funksionon po ashtu, por nĂ« vend qĂ« tĂ« studiojĂ« verbĂ«risht katrorĂ«t fqinj (pastaj fqinjĂ«t e fqinjĂ«ve, pastaj fqinjĂ«t e fqinjĂ«ve tĂ« fqinjĂ«ve dhe kĂ«shtu me radhĂ«), ai mbledh nodet nĂ« njĂ« listĂ« dhe i rendit ato kĂ«shtu qĂ« nĂ«nkategoria qĂ« do tĂ« ekzaminon e ardhshme Ă«shtĂ« gjithmonĂ« ajo qĂ« do tĂ« çojĂ« nĂ« itinerarin mĂ« tĂ« shkurtĂ«r. Nodalet renditen nĂ« bazĂ« tĂ« heuristikĂ«s, e cila merr parasysh dy gjĂ«ra â "kostot" e itinerarit hipotetik pĂ«r nĂ« katrorin e dĂ«shiruar (duke pĂ«rfshirĂ« çdo kostum pĂ«r lĂ«vizje) dhe vlerĂ«simin se sa larg Ă«shtĂ« ky katror nga destinacioni (duke orientuar kĂ«rkimin nĂ« drejtimin e duhur).
NĂ« kĂ«tĂ« shembull tregohet se agjenti eksploron katror pĂ«r katror, duke zgjedhur çdo herĂ« fqinjin mĂ« premtues. Rruga e marrĂ« Ă«shtĂ« e njĂ«jtĂ« si me BFS, por nĂ« proces janĂ« shqyrtuar mĂ« pak katrorĂ« â dhe kjo ka rĂ«ndĂ«si tĂ« madhe pĂ«r performancĂ«n e lojĂ«s.
Lëvizja pa rrjetë
Por shumica e lojĂ«rave nuk janĂ« tĂ« rregulluara nĂ« njĂ« rrjetĂ« dhe shpesh nuk Ă«shtĂ« e mundur ta bĂ«sh atĂ« pa dĂ«mtuar realizmin. KĂ«rkohen kompromiset. Cilat duhet tĂ« jenĂ« pĂ«rmasat e katrorĂ«ve? TejshumĂ« tĂ« mĂ«dhenj â dhe ata nuk do tĂ« jenĂ« nĂ« gjendje tĂ« paraqesin nĂ« mĂ«nyrĂ« tĂ« saktĂ« korridore tĂ« vogla ose kthesa, tejet tĂ« vegjĂ«l â do tĂ« ketĂ« tepĂ«r shumĂ« katrorĂ« pĂ«r t'u kĂ«rkuar, qĂ« pĂ«rfundimisht do tĂ« marrĂ« njĂ« mori kohĂ«.
Gjithçka qĂ« duhet tĂ« kuptohet Ă«shtĂ« se rrjeta na ofron njĂ« grafik tĂ« nyjeve tĂ« lidhura. Algoritmet A* dhe BFS nĂ« fakt funksionojnĂ« mbi grafikat dhe nuk e shqetĂ«sojnĂ« fare rrjetĂ«n tonĂ«. Ne mund tĂ« vendosim nyjet kudo nĂ« botĂ«n e lojĂ«s: me lidhje ndĂ«rmjet çdo dy nyjash tĂ« lidhur, si dhe ndĂ«rmjet pikĂ«s fillestare dhe asaj pĂ«rfundimtare dhe tĂ« paktĂ«n njĂ«rit nga nyjat â algoritmi do tĂ« funksionojĂ« po aq mirĂ« si mĂ« parĂ«. Kjo shpesh quhet sistem pikash orientimi (waypoint), pasi çdo nyje pĂ«rfaqĂ«son njĂ« pozicion tĂ« rĂ«ndĂ«sishĂ«m nĂ« botĂ«, i cili mund tĂ« jetĂ« pjesĂ« e çdo numri hipotezash tĂ« mundshme.
Shembulli 1: një nyje në çdo katror. Kërkimi fillon nga nyja ku ndodhet agjenti dhe përfundon në nyjen e katrorit të nevojshëm.
Shembulli 2: një grup më i vogël nyjesh (pikash orientimi). Kërkimi fillon në katrorin me agjentin, kalon përmes një numri të nevojshëm nyjesh, dhe më pas vazhdon deri në destinacion.
Kjo është një sistem mjaft fleksibël dhe i fuqishëm. Por kërkohet ndonjë kujdes në vendosjen e mënyrave të orientimit, ndryshe agjentët mund të mos arrijnë të shohin pikën më të afërt dhe të mos jenë në gjendje të fillojnë rrugën. Do të ishte më e lehtë nëse mund të vendosnim automatikisht pikat orientuese në bazë të gjeometrisë së botës.
KĂ«tu hyn nĂ« lojĂ« vetĂ« rrjeta e navigimit ose navmesh. Kjo zakonisht Ă«shtĂ« njĂ« rrjetĂ« 2D e trekĂ«ndĂ«shave qĂ« vendoset mbi gjeometrinĂ« e botĂ«s â kudo ku agjentit i lejohet tĂ« ecĂ«. Ădo trekĂ«ndĂ«sh nĂ« rrjetĂ« bĂ«het njĂ« nyje nĂ« graf dhe ka deri nĂ« tre trekĂ«ndĂ«shat fqinj qĂ« bĂ«hen nyje fqinje nĂ« graf.
Kjo pikturĂ« Ă«shtĂ« njĂ« shembull nga motori Unity â ai analizoi gjeominĂ« nĂ« botĂ« dhe krijoi navmesh (nĂ« screenshot me ngjyrĂ« tĂ« kaltĂ«r tĂ« lehtĂ«). Ădo poligon nĂ« navmesh Ă«shtĂ« njĂ« zonĂ« ku agjenti mund tĂ« qĂ«ndrojĂ« ose tĂ« lĂ«vizĂ« nga njĂ« poligon nĂ« tjetrin. NĂ« kĂ«tĂ« shembull, poligonet janĂ« mĂ« tĂ« vogla se katet nĂ« tĂ« cilat ndodhen â kjo Ă«shtĂ« bĂ«rĂ« pĂ«r tĂ« marrĂ« parasysh dimensionet e agjentit, i cili do tĂ« kalonte pĂ«rtej vendndodhjes sĂ« tij nominale.
Ne mund të kërkojmë një rrugë përmes kësaj rrjete, duke përdorur përsëri algoritmin A*. Kjo do të na japë një rrugë praktikisht perfekte në botë, që merr parasysh gjithë gjeominë dhe nuk kërkon nyje të tepërta dhe krijimin e pikave të udhëtimit.
Gjetja e rrugës është një temë shumë e gjerë, për të cilën një seksion i vetëm artikulli nuk mjafton. Nëse dëshironi ta studioni atë më thellë, kjo do t'ju ndihmojë .
Planifikimi
Ne e kuptuam nga gjetja e rrugĂ«s se ndonjĂ«herĂ« nuk mjafton thjesht tĂ« zgjedhĂ«sh njĂ« drejtim dhe tĂ« lĂ«vizĂ«sh â ne duhet tĂ« zgjedhim njĂ« rrugĂ« dhe tĂ« bĂ«jmĂ« disa kthesa pĂ«r tĂ« arritur nĂ« destinacionin e duhur. Ne mund ta pĂ«rgjithĂ«sojmĂ« kĂ«tĂ« ide: arrijtja e qĂ«llimit nuk Ă«shtĂ« thjesht hapi tjetĂ«r, por njĂ« sekuencĂ« e tĂ«rĂ«, ku ndonjĂ«herĂ« kĂ«rkohet tĂ« shohim pĂ«rpara disa hapa pĂ«r tĂ« zbuluar si duhet tĂ« jetĂ« hapi i parĂ«. Kjo quhet planifikim. Gjetja e rrugĂ«s mund tĂ« konsiderohet si njĂ« nga disa shtesat e planifikimit. Nga perspektiva e ciklit tonĂ« Sense/Think/Act, kjo Ă«shtĂ« ajo ku pjesa Think planifikon disa pjesĂ« nga Act pĂ«r tĂ« ardhmen.
Le të analizojmë me shembullin e lojës së tavolinës Magic: The Gathering. Ne luajmë të parët me këtë set kartash në dorë:
- Swamp â ofron 1 manĂ« tĂ« zezĂ« (kartĂ« toke).
- Forest â ofron 1 manĂ« tĂ« gjelbĂ«r (kartĂ« toke).
- Fugitive Wizard â kĂ«rkon 1 manĂ« tĂ« blertĂ« pĂ«r tĂ« thirrur.
- Elvish Mystic â kĂ«rkon 1 manĂ« tĂ« gjelbĂ«r pĂ«r tĂ« thirrur.
Kartat e mbetura tre i injorojmë për ta bërë më të lehtë. Sipas rregullave, një lojtari i lejohet të luajë 1 kartë toke në hap, ai mund të "taps" këtë kartë për të nxjerrë manë, dhe pastaj të përdorë magji (përfshirë thirrjen e krijesave) sipas sasisë së manës. Në këtë situatë, lojtari-njeri e di se duhet të luajë Forest, "taps" 1 manë të gjelbër, dhe pastaj të thërrasë Elvish Mystic. Por si ta kuptojë kjo AI e lojës?
Planifikimi i thjeshtë
Qashtimi i thjeshtĂ« â tĂ« provosh çdo veprim njĂ« nga njĂ«, derisa tĂ« mos mbetet asnjĂ« i pĂ«rshtatshĂ«m. Duke parĂ« kartat, AI sheh se mund tĂ« luajĂ« Swamp. Dhe e luan. A kanĂ« mbetur veprime tĂ« tjera nĂ« kĂ«tĂ« raund? Ai nuk mund tĂ« thĂ«rrasĂ« as Elvish Mystic, as Fugitive Wizard, pasi kĂ«rkohet mana pĂ«rkatĂ«sisht e gjelbĂ«r dhe e kaltĂ«r pĂ«r thirrjen e tyre, dhe Swamp jep vetĂ«m mana tĂ« zezĂ«. Dhe ai nuk do mund tĂ« luajĂ« mĂ« Forest, sepse tashmĂ« ka luajtur Swamp. Pra, AI luajti sipas rregullave, por e bĂ«ri keq. Mund tĂ« pĂ«rmirĂ«sohet.
Planifikimi mund të gjejë një listë veprimesh që çojnë lojën në gjendjen e dëshiruar. Po ashtu, si çdo katror në rrugë kishte fqinjë (në pathfinding), çdo veprim në plan gjithashtu ka fqinjë ose pasardhës. Mund të kërkojmë këto veprime dhe veprime të ardhshme derisa të arrijmë gjendjen e dëshiruar.
Në shembullin tonë, rezultati i dëshiruar është «thirr një krijesë, nëse është e mundur». Në fillim të raundit ne shohim vetëm dy veprime të mundshme, të lejuara nga rregullat e lojës:
1. Të luajmë Swamp (rezultati: Swamp në lojë)
2. Të luajmë Forest (rezultati: Forest në lojë)
Ădo veprim i sjellĂ« mund tĂ« çojĂ« nĂ« veprime tĂ« tjera dhe tĂ« mbyllĂ« disa tĂ« tjera, pĂ«rsĂ«ri nĂ« varĂ«si tĂ« rregullave tĂ« lojĂ«s. PĂ«rfytyroni, se luajmĂ« Swamp â kjo do ta heqĂ« Swamp si hapin e ardhshĂ«m (ne tashmĂ« e kemi luajtur), gjithashtu do ta heqĂ« dhe Forest (pĂ«r shkak se sipas rregullave mund tĂ« luash njĂ« kartĂ« toke pĂ«r raund). Pas kĂ«saj, AI shton si hapin e ardhshĂ«m â marrjen e 1 manas tĂ« zezĂ«, sepse nuk ka opsione tĂ« tjera. NĂ«se ai vazhdon dhe zgjidh Tapping the Swamp, ai do tĂ« marrĂ« 1 njĂ«si mana tĂ« zezĂ« dhe nuk do tĂ« mund tĂ« bĂ«jĂ« asgjĂ« me tĂ«.
1. Të luajmë Swamp (rezultati: Swamp në lojë)
1.1 «Tapo» Swamp (rezultati: Swamp «tapohet», +1 njësi mana e zezë)
Nuk ka veprime tĂ« disponueshme â FUND
2. Të luajmë Forest (rezultati: Forest në lojë)
Lista e veprimeve doli e shkurtĂ«r, jemi nĂ« njĂ« kufi. PĂ«rsĂ«ritim procesin pĂ«r veprimin tjetĂ«r. Ne luajmĂ« Forest, hapim veprimin «merr 1 mana tĂ« gjelbĂ«r», i cili nga ana e tij do tĂ« hapĂ« njĂ« veprim tĂ« tretĂ« â thirrjen e Elvish Mystic.
1. Të luajmë Swamp (rezultati: Swamp në lojë)
1.1 «Tapo» Swamp (rezultati: Swamp «tapohet», +1 njësi mana e zezë)
Nuk ka veprime tĂ« disponueshme â FUND
2. Të luajmë Forest (rezultati: Forest në lojë)
2.1 «Tapo» Forest (rezultati: Forest «tapohet», +1 njësi mana e gjelbër)
2.1.1 Thirr Elvish Mystic (rezultati: Elvish Mystic në lojë, -1 njësi mana e gjelbër)
Nuk ka veprime tĂ« disponueshme â FUND
Më në fund, ne studiuam të gjitha veprimet e mundshme dhe gjetëm një plan për të thirrur një krijesë.
Ky Ă«shtĂ« njĂ« shembull shumĂ« i thjeshtuar. Preferohet tĂ« zgjidhni planin mĂ« tĂ« mirĂ« tĂ« mundshĂ«m, jo thjesht ndonjĂ« qĂ« plotĂ«son disa kritere. NĂ« pĂ«rgjithĂ«si, Ă«shtĂ« e mundur tĂ« vlerĂ«sohen planet e mundshme pĂ«rmes rezultatit pĂ«rfundimtar ose pĂ«rfitimit tĂ« pĂ«rgjithshĂ«m nga realizimi i tyre. Mund tĂ« merrni 1 pikĂ« pĂ«r tĂ« luajtur njĂ« kartĂ« toke dhe 3 pikĂ« pĂ«r tĂ« thirrur njĂ« krijesĂ«. TĂ« luani Swamp do tĂ« ishte njĂ« plan qĂ« jep 1 pikĂ«. NdĂ«rsa tĂ« luani Forest â Tap the Forest â thirrni Elvish Mystic do t'ju japĂ« menjĂ«herĂ« 4 pikĂ«.
Kështu funksionon planifikimi në Magic: The Gathering, por me të njëjtën logjikë kjo aplikohet edhe në situata të tjera. Për shembull, të zhvendosni një pion për të liruar hapësirë për të lëvizur një elefant në shah. Ose të strehoheni pas një muri për të shtënë në XCOM në mënyrë të sigurt. Në përgjithësi, ju kuptuat pikën.
Planifikimi i përmirësuar
NgjashĂ«m, ndonjĂ«herĂ« ka shumĂ« veprime tĂ« mundshme pĂ«r tĂ« shqyrtuar çdo variant tĂ« mundshĂ«m. Duke u kthyer te shembulli i Magic: The Gathering: supozoni se nĂ« lojĂ« keni disa karta toke dhe krijesash â numri i kombinimeve tĂ« mundshme tĂ« lĂ«vizjeve mund tĂ« arrijĂ« dhjetĂ«ra. EkzistojnĂ« disa zgjidhje pĂ«r kĂ«tĂ« problem.
MĂ«nyra e parĂ« Ă«shtĂ« backwards chaining (formimi i zinxhirit nĂ« prapavijĂ«). NĂ« vend qĂ« tĂ« shqyrtoni tĂ« gjitha kombinimet, Ă«shtĂ« mĂ« mirĂ« tĂ« filloni nga rezultati pĂ«rfundimtar dhe tĂ« provoni tĂ« gjeni njĂ« rrugĂ« tĂ« drejtpĂ«rdrejtĂ«. NĂ« vend tĂ« rrugĂ«s nga rrĂ«nja e pemĂ«s nĂ« njĂ« gjethe tĂ« caktuar, ne lĂ«vizim nĂ« drejtimin e kundĂ«rt â nga gjethe te rrĂ«nja. Kjo methode Ă«shtĂ« mĂ« e thjeshtĂ« dhe mĂ« e shpejtĂ«.
Nëse armiku ka 1 pikë shëndeti, mund të gjeni një plan "të shkaktoni 1 ose më shumë pikë dëmi". Për ta arritur këtë, duhet të përmbushni një sërë kushtesh:
1. DĂ«mi mund tĂ« shkaktohet nga njĂ« magji â ajo duhet tĂ« jetĂ« nĂ« dorĂ«.
2. PĂ«r tĂ« hedhur magjinĂ« â nevojitet mana.
3. PĂ«r tĂ« fituar mana â duhet tĂ« hedhni njĂ« kartĂ« toke.
4. PĂ«r tĂ« hedhur njĂ« kartĂ« toke â duhet ta keni atĂ« nĂ« dorĂ«.
MĂ«nyra tjetĂ«r Ă«shtĂ« best-first search (kerkimi mĂ« i mirĂ« i parĂ«). NĂ« vend qĂ« tĂ« shqyrtoni tĂ« gjitha rrugĂ«t, ne zgjedhim mĂ« tĂ« pĂ«rshtatshmen. Shpesh kjo metodĂ« jep njĂ« plan optimal pa shpenzime tĂ« tepĂ«rta pĂ«r kĂ«rkimin. A* Ă«shtĂ« njĂ« formĂ« e kerkimit mĂ« tĂ« mirĂ« tĂ« parĂ« â duke shqyrtuar rrugĂ«t mĂ« premtuese qĂ« nga fillimi, ai mund tĂ« gjejĂ« rrugĂ«n mĂ« tĂ« mirĂ« pa pasur nevojĂ« tĂ« shqyrtojĂ« opsionet e tjera.
Një variant interesant dhe gjithnjë e më i popullarizuar i kërkimit best-first është Kërkimi i Pemës së Monte Carlo. Në vend që të hamendësojë se cilat plane janë më të mirat për veprimin e ardhshëm, algoritmi zgjedh pasardhës të rastësishëm në çdo hap, derisa të arrijë fundin (kur plani çon në fitore ose humbje). Pastaj, rezultati përfundimtar përdoret për të rritur ose ulur vlerësimin "peshës" së mundësive të mëparshme. Duke e përsëritur këtë proces disa herë, algoritmi jep një vlerësim të mirë se cili hap tjetër është më i mirë, madje edhe nëse situata ndryshon (nëse kundërshtari merr masa për t'i penguar lojtarin).
NĂ« tregimin e planifikimit nĂ« lojĂ«ra, nuk mund tĂ« anashkalohet Planifikimi i Veprimeve tĂ« Orientuara ndaj QĂ«llimeve ose GOAP. Ky Ă«shtĂ« njĂ« metodĂ« e pĂ«rdorur gjerĂ«sisht dhe e diskutuar, por pĂ«rveç disa detajeve dalluese, Ă«shtĂ« nĂ« thelb njĂ« metodĂ« e zinxhirit tĂ« prapĂ«, pĂ«r tĂ« cilĂ«n folĂ«m mĂ« parĂ«. NĂ«se detyra ishte "shkatĂ«rro lojtarin", dhe lojtarit i ka qĂ«lluar pas njĂ« mbrojtjeje, plani mund tĂ« jetĂ«: shkatĂ«rro me njĂ« granatĂ« â merr atĂ« â hedh.
Zakonisht ka disa qëllime, secili me përparësinë e tij. Nëse qëllimi me përparësi më të lartë nuk mund të realizohet (nuk ka asnjë kombinim veprimesh që krijon planin "shkatërro lojtarin", sepse lojtarit nuk i shihet), AI do të kthehet te qëllimet me përparësi më të ulët.
MĂ«simi dhe adaptimi
Kemi diskutuar tashmë se AI i lojërave zakonisht nuk përdor mësimin e makinerive, sepse kjo nuk është e përshtatshme për menaxhimin e agjentëve në kohë reale. Por kjo nuk do të thotë që nuk mund të merret ndonjëherë diçka nga ky fushë. Ne duam një kundërshtar në një lojë aksionesh nga i cili mund të mësojmë ndonjë gjë. Për shembull, të mësojmë për pozitat më të mira në hartë. Ose një kundërshtar në një luftë që do të bllokonte kombinimet e zakonshme të lojtarit, duke e motivuar atë të përdorë të tjera. Pra, mësimi i makinerive në këto situata mund të jetë shumë i dobishëm.
Statistikat dhe probabilitetet
Para se kalojmĂ« nĂ« shembuj tĂ« komplikuar, le tĂ« shqyrtojmĂ« 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 mund ta pĂ«rcaktojmĂ« nĂ«se njĂ« lojtar mund tĂ« nisĂ« njĂ« sulm nĂ« minutat e para tĂ« lojĂ«s dhe çfarĂ« mbrojtjeje do tĂ« pĂ«rgatisim pĂ«r kĂ«tĂ«? Mund tĂ« studiojmĂ« pĂ«rvojĂ«n e kaluar tĂ« lojtarit pĂ«r tĂ« kuptuar se çfarĂ« mund tĂ« jetĂ« reagimi i tij nĂ« tĂ« ardhmen. SĂ« pari, na mungojnĂ« kĂ«to tĂ« dhĂ«na tĂ« plota, por ne mund t'i mbledhim ato â çdo herĂ« qĂ« AI luan kundĂ«r njĂ« njeriu, ai mund tĂ« regjistrojĂ« kohĂ«n e sulmit tĂ« parĂ«. Pas disa sesionesh, do tĂ« marrim mesataren e kohĂ«s qĂ« lojtarĂ«t do tĂ« sulmojnĂ« nĂ« tĂ« ardhmen.
Mesataret kanĂ« edhe njĂ« problem: nĂ«se njĂ« lojtar ka ârush-uarâ 20 herĂ« dhe ka luajtur ngadalĂ« 20 herĂ« tĂ« tjera, atĂ«herĂ« vlerat e nevojshme do tĂ« jenĂ« diku nĂ« mes, qĂ« nuk do na ofrojĂ« asgjĂ« tĂ« dobishme. NjĂ« nga zgjidhjet Ă«shtĂ« kufizimi i tĂ« dhĂ«nave hyrĂ«se â mund tĂ« merret parasysh vetĂ«m 20 tĂ« fundit.
Një qasje e ngjashme përdoret për të vlerësuar probabilitetin e veprimeve të caktuara, duke supozuar se preferencat e kaluara të lojtarit do të jenë të ngjashme në të ardhmen. Nëse një lojtar na sulmon pesë herë me topa zjarri, dy herë me rrufe dhe një herë me duar, është e qartë se ai preferon topin e zjarrit. Ne mund ta ekstrapolojmë dhe të shohim probabilitetin e përdorimit të armëve të ndryshme: topi i zjarrit=62.5%, rrufe=25% dhe duar-shqip=12.5%. AI ynë i lojës duhet të përgatitet për mbrojtje nga zjarri.
NjĂ« metodĂ« interesante tjetĂ«r Ă«shtĂ« tĂ« pĂ«rdorim Naive Bayes Classifier (klasifikuesi naiv 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Ă« siç duhet. Klasifikuesit Bayesian janĂ« tĂ« njohur pĂ«r pĂ«rdorimin e tyre nĂ« filtre tĂ« spamit tĂ« emailit. Aty ata analizojnĂ« fjalĂ«t, i krahasojnĂ« ato me vendet ku janĂ« shfaqur kĂ«to fjalĂ« mĂ« parĂ« (nĂ« spam apo jo) dhe nxjerrin pĂ«rfundime pĂ«r email-et hyrĂ«se. Ne mund tĂ« bĂ«jmĂ« tĂ« njĂ«jtĂ«n gjĂ« edhe me mĂ« pak tĂ« dhĂ«na hyrĂ«se. NĂ« bazĂ« tĂ« gjithĂ« informacionit tĂ« dobishĂ«m qĂ« sheh AI (p.sh., cilat njĂ«si armike janĂ« krijuar, apo cilat magji po pĂ«rdorin, apo cilat teknologji po studiojnĂ«), dhe rezultatin pĂ«rfundimtar (luftĂ« ose paqe, ârushâ ose mbrojtje, etj.) â ne do tĂ« zgjedhim comportimin e duhur tĂ« AI.
Të gjitha këto metoda të mësimit janë të mjaftueshme, por është e dëshirueshme t'i përdorim ato në bazë të të dhënave nga testimi. AI do të mësojë të adaptohet me strategjitë e ndryshme që kanë përdorur testuesit tuaj. Një AI që adaptohet me lojtarin pas lansimit mund të bëhet tepër i parashikueshëm ose, nga ana tjetër, shumë i vështirë për t'u mposhtur.
Adaptimi në bazë të vlerave
Duke marrë parasysh përmbajtjen e botës sonë loje dhe rregullat, ne mund të ndryshojmë setin e vlerave që ndikojnë në vendimmarrje, në vend që të përdorim thjesht të dhënat hyrëse. Veprojmë kështu:
- Le të mbledhë AI të dhëna rreth gjendjes së botës dhe ngjarjeve kyçe gjatë lojës (siç është përmendur më sipër).
- Do të ndryshojmë disa vlera të rëndësishme në bazë të këtyre të dhënave.
- Do të zbatojmë vendimet tona, të bazuara 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Ă« tĂ« njĂ« loje tirane nga perspektiva e parĂ«. Ădo dhomĂ« ka vlerĂ«n e saj, e cila pĂ«rcakton sa tĂ« dĂ«shiruara janĂ« pĂ«r tu vizituar. AI zgjedh rastĂ«sisht se nĂ« cilĂ«n dhomĂ« tĂ« shkojĂ«, nĂ« bazĂ« tĂ« vlerĂ«s sĂ« saj. MĂ« pas, agjenti e mban mend nĂ« cilĂ«n dhomĂ« e vranĂ« dhe ndalon vlerĂ«n e saj (probabiliteti qĂ« ai do tĂ« kthehet atje). Po ashtu nĂ« situatĂ«n e kundĂ«rt â nĂ«se agjenti shkatĂ«rron shumĂ« kundĂ«rshtarĂ«, atĂ«herĂ« vlera e dhomĂ«s rritet.
Modeli Markov
ĂfarĂ« ndodh nĂ«se ne pĂ«rdorim tĂ« dhĂ«nat e mbledhura pĂ«r parashikim? NĂ«se mbajmĂ« mend çdo dhomĂ« ku shohim lojtarin gjatĂ« njĂ« periudhe tĂ« caktuar kohore, ne do tĂ« parashikojmĂ« nĂ« cilĂ«n dhomĂ« mund tĂ« kalojĂ« lojtarin. Duke ndjekur dhe regjistruar lĂ«vizjet e lojtarit nĂ«pĂ«r dhoma (vlerat), ne mund tĂ« parashikojmĂ« ato.
Le të marim tre dhoma: të kuqe, të gjelbra dhe të blu. Po ashtu dhe vëzhgimet që kemi regjistruar gjatë shikimit të sesionit të lojës:
Numri i vĂ«zhgimeve pĂ«r secilĂ«n dhomĂ« Ă«shtĂ« pothuajse i barabartĂ« â ende nuk e dimĂ« ku tĂ« bĂ«jmĂ« njĂ« vend tĂ« mirĂ« pĂ«r tendĂ«. Grumbullimi i statistikave gjithashtu komplikohet nga rihapjet e lojtarĂ«ve, tĂ« cilĂ«t shfaqen nĂ« mĂ«nyrĂ« tĂ« barabartĂ« nĂ« tĂ« gjithĂ« hartĂ«n. Por tĂ« dhĂ«nat mbi dhomĂ«n e ardhshme, nĂ« tĂ« cilĂ«n ata hyjnĂ« pas shfaqjes nĂ« hartĂ« â tashmĂ« janĂ« tĂ« dobishme.
ĂshtĂ« evidente se dhoma e gjelbĂ«r i kĂ«naq lojtarĂ«t - shumica e njerĂ«zve nga dhoma e kuqe kalojnĂ« nĂ« tĂ«, 50% e tĂ« cilĂ«ve qĂ«ndrojnĂ« atje mĂ« tej. PĂ«rkundrazi, dhoma blu nuk gĂ«zon popullaritet, thuajse nuk vizitohet, dhe nĂ«se vizitohet, atĂ«herĂ« nuk qĂ«ndrohet aty.
Por të dhënat na tregojnë diçka më të rëndësishme - kur lojtari ndodhet në dhomën blu, dhoma tjetër ku ne do ta shohim zakonisht është e kuqe, dhe jo e gjelbër. Edhe pse dhoma e gjelbër është më popullore se ajo e kuqe, situata ndryshon nëse lojtari ndodhet në blu. Shteti tjetër (domethënë dhoma në të cilën lojtari do të kalojë) varet nga gjendja e mëparshme (domethënë dhoma në të cilën ndodhet tani lojtari). Për shkak të hulumtimit të varësive, ne do të bëjmë parashikime më të sakta sesa po të numëronim thjesht observimet në mënyrë të pavarur.
Parashikimi i gjendjes së ardhshme mbi bazën e të dhënave të gjendjes së kaluar quhet modeli Markov (Markov model), dhe ato shembuj (me dhomat) quhen zinxhirë Markov. Duke qenë se modelet përfaqësojnë probabilitetin e ndryshimeve mes gjendjeve të njëpasnjëshme, ato paraqiten vizualisht si FSM me probabilitet rreth çdo kalimi. Më parë ne kemi përdorur FSM për të përfaqësuar gjendjen e sjelljes në të cilën ndodhej agjenti, por kjo koncept bëhet e aplikueshme në çdo gjendje, pavarësisht se a është kjo e lidhur me agjentin apo jo. Në këtë rast, gjendjet përfaqësojnë dhomën që zë agjenti:
Ky është një variant i thjeshtë për të paraqitur probabilitetin relativ të ndryshimeve të gjendjeve, duke i dhënë AI një mundësi për të parashikuar gjendjen e ardhshme. Mund të parashikohet disa hapa përpara.
Nëse lojtari është në dhomën e gjelbër, ka një 50% mundësi që ai të qëndrojë atje në vëzhgimin e ardhshëm. Por cila është probabiliteti që ai të jetë ende aty edhe më vonë? Ka jo vetëm mundësinë që lojtari të mbetet në dhomën e gjelbër pas dy vëzhgimeve, por edhe një mundësi që ai ka dalë dhe është kthyer. Këtu është një tabelë e re duke marrë parasysh të dhënat e reja:
Nga kjo duket se mundësia për të parë lojtarin në dhomën e gjelbër pas dy vëzhgimeve do të jetë 51% - 21% që ai do të vijë nga dhoma e kuqe, 5% nga ata që lojtari do të vizitojë dhomën blu midis tyre, dhe 25% që lojtari nuk do të largohet nga dhoma e gjelbër fare.
Tabeli Ă«shtĂ« thjesht njĂ« mjet vizual â procedura kĂ«rkon vetĂ«m shumĂ«zimin e probabiliteteve nĂ« çdo hap. Kjo do tĂ« thotĂ« se mund tĂ« shikoni thellĂ« nĂ« tĂ« ardhmen me njĂ« rezervĂ«: ne supozojmĂ« se shansi pĂ«r tĂ« hyrĂ« nĂ« dhomĂ« varet plotĂ«sisht nga dhoma aktuale. Kjo quhet pronĂ«sia Markoviane (Markov Property) â gjendja e ardhshme varet vetĂ«m nga e tashmja. Por kjo nuk Ă«shtĂ« plotĂ«sisht e saktĂ«. LojtarĂ«t mund tĂ« ndryshojnĂ« vendimet e tyre nĂ« varĂ«si tĂ« faktorĂ«ve tĂ« tjerĂ«: niveli i shĂ«ndetit ose sasia e municioneve. Duke qenĂ« se ne nuk i regjistrojmĂ« kĂ«to vlera, parashikimet tona do tĂ« jenĂ« mĂ« pak tĂ« sakta.
N-Grams
Dhe çfarë ndodh me shembullin e luftimeve dhe parashikimin e kombo-ve të lojtarit? E njëjta gjë! Por në vend të një gjendje ose ngjarjeje, do të studiojmë tërë sekuenca, nga të cilat përbëhet kombo-shkalla.
Një nga mënyrat për ta bërë këtë është të ruani çdo input (p.sh., Kick, Punch ose Block) në një bufer dhe të regjistroni të gjithë buferin si një ngjarje. Pra, lojtari shtyp vazhdimisht Kick, Kick, Punch për të përdorur sulmin SuperDeathFist, sistemi i AI ruan të gjitha inputet në bufer dhe mban mend tre të fundit, që përdoren në çdo hap.
(Me bold janë theksuar rreshtat kur lojtari aktivizon sulmin SuperDeathFist.)
AI do të shohë të gjitha variantet kur lojtari zgjodhi Kick, më pas një tjetër Kick, dhe më pas do të vërë re se inputi i ardhshëm është gjithmonë Punch. Kjo do t'i lejojë agjentit të parashikojë kombo-sulmin SuperDeathFist dhe ta bllokojë atë, nëse është e mundur.
Këto sekuenca ngjarjesh quhen N-grama (N-grams), ku N është numri i elementeve të ruajtur. Në shembullin e mëparshëm ishte një 3-gramë (trigramë), që do të thotë: dy regjistrimet e para përdoren për të parashikuar të tretën. Pra, në një 5-gramë, katër regjistrimet e para parashikojnë të pestën dhe kështu me radhë.
Zhvilluesi duhet të zgjedhë me kujdes madhësinë e N-gramave. Një numër më i vogël N kërkon më pak kujtesë, por gjithashtu ruan një histori më të vogël. Për shembull, një 2-gramë (bigramë) do të regjistronte Kick, Kick ose Kick, Punch, por nuk do të mundte të ruante Kick, Kick, Punch, kështu që AI nuk do të reagonte ndaj kombo-sulmit SuperDeathFist.
Nga ana tjetër, numrat më të mëdhenj kërkojnë më shumë kujtesë dhe AI do të ketë më shumë vështirësi në mësim, pasi do të ketë shumë më tepër variante të mundshme. Nëse kishte tre inpute të mundshme Kick, Punch ose Block, dhe ne përdorim një 10-gramë, do të rezultonte rreth 60 mijë variante të ndryshme.
Modeli i bigramit Ă«shtĂ« njĂ« zinxhir i thjeshtĂ« Markov â çdo çift 'shteti i kaluar/shteti aktual' Ă«shtĂ« njĂ« bigram, dhe ju mund tĂ« parashikoni shtetin e dytĂ« nĂ« bazĂ« tĂ« atij tĂ« parĂ«. Trigrami dhe bigramet mĂ« tĂ« mĂ«dha gjithashtu mund tĂ« shqyrtohen si zinxhirĂ« Markov ku tĂ« gjitha elementet (pĂ«rveç elementit tĂ« fundit nĂ« N-gramĂ«) sĂ« bashku formojnĂ« shtetin e parĂ«, ndĂ«rsa elementi i fundit Ă«shtĂ« i dyti. NjĂ« shembull me luftim tregon shansin e kalimit nga shteti Kick dhe Kick nĂ« shtetin Kick dhe Punch. Duke parĂ« disa regjistra tĂ« historikut tĂ« hyrjes si njĂ« njĂ«si, ne, nĂ« thelb, transformojmĂ« sekuencĂ«n e hyrjes nĂ« pjesĂ« tĂ« njĂ« gjendjeje tĂ« tĂ«rĂ«. Kjo na jep pronĂ«n Markov qĂ« na lejon tĂ« pĂ«rdorim zinxhirĂ«t Markov pĂ«r tĂ« parashikuar hyrjen e ardhshme dhe tĂ« hamendsojmĂ« se cili do tĂ« jetĂ« lĂ«vizja tjetĂ«r e kombos.
PĂ«rfundim
Diskutuam për mjetet dhe qasjet më të zakonshme në zhvillimin e inteligjencës artificiale. Gjithashtu shqyrtuam situatat në të cilat duhet t'i aplikojmë ato dhe ku janë veçanërisht të dobishme.
Kjo duhet të jetë e mjaftueshme për të kuptuar gjërat themelore në inteligjencën artificiale të lojrave. Por, sigurisht, kjo nuk është të gjitha metodat. Disa që janë më pak popullore, por po aq efektive janë:
- algoritmet për optimizim, duke përfshirë ngjitjen në kodrina, zbritjen gradiente dhe algoritmet gjenetike
- algoritmet konkuruese të kërkimit/planifikimit (minimax dhe alfa-beta pruning)
- metodat e klasifikimit (perceptonët, rrjetet neuronale dhe makinat e dhezjes së mbështetjes)
- sistemet për përpunimin e perceptimit dhe memories së agjentëve
- qasjet arkitekturore në AI (sistemet hibride, nëngrupet e arkitekturave dhe mënyra të tjera për të mbivendosur sistemet e AI)
- mjetet e animacionit (planifikimi dhe koordinimi i lëvizjes)
- faktorët e performancës (niveli i detajeve, algoritmet e çdo kohe, dhe ndarjen e kohës)
Burimet në internet mbi temën:
1. NĂ« GameDev.net ka , si dhe .
2. ka shumë prezantime dhe artikuj mbi një gamë të gjerë lidhur me zhvillimin e AI të lojrave.
3. përfshin tema nga samiti GDC AI, shumë prej të cilave janë të disponueshme falas.
4. Materialet e dobishme gjithashtu mund të gjenden në faqen .
5. Tommy Thompson, një kërkues i AI dhe zhvillues lojërash, bën video në kanalin e YouTube me shpjegime dhe studime të AI në lojrat komerciale.
Libra mbi temën:
1. Seria e librave Game AI Pro përbën koleksione artikujsh të shkurtër që shpjegojnë si të realizoni funksione specifike ose si të zgjidhni probleme specifike.
2. Seria e AI Game Programming Wisdom â paraardhĂ«s i serisĂ« Game AI Pro. Ajo pĂ«rmban metoda mĂ« tĂ« vjetra, por pothuajse tĂ« gjitha janĂ« ende tĂ« rĂ«ndĂ«sishme edhe sot.
3. â Ă«shtĂ« njĂ« nga tekstet bazĂ« pĂ«r tĂ« gjithĂ« ata qĂ« dĂ«shirojnĂ« tĂ« kuptojnĂ« fushĂ«n e pĂ«rgjithshme tĂ« inteligjencĂ«s artificiale. Ky libĂ«r nuk ka tĂ« bĂ«jĂ« me zhvillimin e lojĂ«rave â ai mĂ«son bazat e inteligjencĂ«s artificiale.
Burimi: habr.com
