Si si krijon një AI për lojra: udhëzues për fillestarët

Kam hasur një material interesant mbi inteligjencën artificiale në lojëra. Me një shpjegim të gjërave bazike rreth AI në shembuj të thjeshtë, dhe gjithashtu brenda tij ka shumë mjete dhe metoda të dobishme për zhvillimin dhe projektimin e tij të lehtë. Si, ku dhe kur t'i përdorësh ato — gjithashtu përmendet.

Shumica e shembujve janë shkruar në pseudokod, kështu që njohuri të thella në programim nuk do të kenë nevojë. Në këtë udhëzues ka 35 faqe teksti me figura dhe gif-e, prandaj përgatituni.

UPD. Më vjen keq, por kam bërë tashmë përkthimin e këtij artikulli në Habra PatientZero. Mund ta lexoni versionin e tij këtu, por për ndonjë arsyesh arti nuk arriti të shohë artikullin (kam përdorur kërkimin, por diçka nuk shkoi mirë). Dhe duke qenë se shkruaj në një blog që i kushtohet zhvillimit të lojërave, vendosa të lë variantin tim të përkthimit për ndjekësit (disa momente i kam paraqitur ndryshe, disa — qëllimisht të lëna jashtë sipas këshillave të zhvilluesve).

Çfarë është AI?

IA e lojës përqendrohet në veprimet që duhet të kryejë një objekt, në përputhje me kushtet në të cilat ndodhet. Kjo zakonisht quhet menaxhimi i "agjentëve inteligjentë", ku agjenti është një karakter loje, një mjet transporti, një bot, dhe ndonjëherë edhe diçka më abstrakte: një grup i tërë entitetesh ose madje një civilizim. Në çdo rast, kjo është një entitet që duhet të perceptojë mjedisin e tij, të marrë vendime në përputhje me të dhe të veprojë sipas tyre. Kjo quhet cikli Sense/Think/Act (Percepto/Mendo/Vepro):

• Percepto: agjenti gjen ose merr informacione për 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 t'u eksploruar).
• Mendo: agjenti vendos se si të reagojë (konsideron nëse është mjaft i sigurt për të mbledhur objekte ose nëse fillimisht duhet të luftojë/fshihet).
• Vepro: agjenti kryen veprimet për të realizuar vendimin e mëparshëm (fillon lëvizjen drejt armikut ose objektit).
• …tani situata ka ndryshuar për shkak të veprimeve të karaktereve, kështu që cikli përsëritet me të dhëna të reja.

AI zakonisht përqendrohet në pjesën Sense të ciklit. Për shembull, automjetet autonome bëjnë fotografi të rrugës, i kombinojnë ato me të dhënat e radarit dhe lidarit, dhe interpretojnë. Kjo zakonisht realizohet nga mësimi në makinë, i cili përpunon të dhënat hyrëse dhe u jep atyre kuptim, duke nxjerrë informacion semantik si 'ka një automjet tjetër 20 metra përpara jush'. Këto quhen probleme klasifikimi.

Lojërat nuk kanë nevojë për një sistem kompleks për të nxjerrë informacion, pasi shumica e të dhënave tashmë janë një pjesë e pandashme e saj. Nuk ka nevojë për të ekzekutuar algoritme të njohjes së 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 AI në lojëra

AI ka një seri kufizimesh që duhet të respektohen:

• AI nuk ka nevojë të trajnohet paraprakisht, siç është një algoritëm mësimi në makinë. Nuk ka asnjë kuptim të shkruani një rrjet neuror gjatë zhvillimit për të vëzhguar dhjetëra mijëra lojtarë dhe për të studiuar mënyrën më të mirë për të luajtur përballë tyre. Pse? Sepse loja nuk është lëshuar dhe lojtarët nuk ekzistojnë.
• Lojë duhet të argëtojë dhe të sfidojë, kështu që 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 si po luajnë kundër njerëzve të vërtetë. Programi AlphaGo e tejkaloi njeriun, por hapat e zgjedhur ishin shumë larg kuptimit tradicional të lojës. Nëse loja imiton një kundërshtar njeri, ky ndjenjë nuk duhet të ekzistojë. Algoritmi duhet të ndryshohet në mënyrë që ai të marrë vendime të besueshme, jo të përsosura.
• AI duhet të funksionojë në kohë reale. Këto do të thotë se algorizmat nuk mund ta monopolizojnë përdorimin e procesorit për një periudhë të gjatë për të marrë vendime. Edhe 10 milisekonda për këtë është shumë gjatë, sepse shumicës së lojërave u nevojiten nga 16 deri në 33 milisekonda për të përfunduar gjithë përpunimin dhe për t'u kaluar në kadrin tjetër të grafikës.
• Ideale është që të paktën një pjesë e sistemit të menaxhohet nga të dhënat, në mënyrë që 'jo-koderët' të mund të bëjnë ndryshime dhe që rregullimet të ndodhin më shpejt.

Le të shqyrtojmë qasjet e AI që përfshijnë të gjithë ciklin Sense/Think/Act.

Marrja e vendimeve themelore

Të fillojmë me një lojë të thjeshtë — Pong. Qëllimi: të lëvizësh platformën (paddle) në mënyrë që topi të riciklohet prej saj dhe të mos kalojë përtej. Është si tenis, në të cilin humb kur nuk e godet topin. Këtu AI ka një detyrë relativisht të lehtë — të vendosë se në cilin drejtim të lëvizë platformën.

Operatorët conditional

Për AI në Pong ka një zgjidhje shumë të dukshme — të përpiqet gjithmonë ta vendosë platformën nën topin.

Një algoritëm i thjeshtë për këtë, i shkruar në pseudokod:

çdo kornizë/aktualizim ndërsa loja është duke u zhvilluar:
nëse topi është në të majtë të paddle-it:
lëviz paddle-in në të majtë
ndryshe nëse topi është në të djathtë të paddle-it:
lëviz paddle-in 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 është nevoja të komplikohet, nëse të dhënat dhe veprimet e mundshme për agjentin nuk janë aq shumë.

Ky qasje është kaq e thjeshtë, saqë e gjithë cikli Sense/Think/Act është thuajse i padukshëm. Por ai ekziston:

• Pjesa Sense është në dy operatorët if. Loja e di ku është topi dhe ku është platforma, kështu që AI i referohet asaj për këtë informacion.
• Pjesa Think gjithashtu është përfshirë në dy operatorë if. Ata përfaqësojnë dy zgjidhje, të cilat në këtë rast janë përjashtuese njëra-tjetrës. Si rezultat, zgjidhet një nga tre veprimet — të zhvendosësh platformën majtas, të zhvendosësh djathtas, ose të mos bësh asgjë nëse ajo është tashmë e pozicionuar siç duhet.
• Pjesa Act ndodhet në operatorët Move Paddle Left dhe Move Paddle Right. Në varësi të dizajnit të lojës, ata mund të zhvendosin platformën menjëherë ose me një shpejtësi të caktuar.

Qasje të tilla quhen reaguese — ka një set të thjeshtë rregullash (në këtë rast operatorët if në kod), të cilat reagojnë ndaj gjendjes aktuale të botës dhe veprojnë.

Pema e vendimeve

Shembulli me lojën 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 cila veprim duhen marrë.

Le të bëjmë një diagram të pemës së vendimeve për algoritmin e platformës sonë:

Çdo pjesë e pemës quhet node (nyjë) — AI përdor teorinë e grafëve për të përshkruar struktura të tilla. Ka dy lloje nyjash:

• Nodet e vendimmarrjes: zgjedhja midis dy alternativave bazuar në verifikimin e një kushti të caktuar, ku secila alternativë paraqitet si një nod i veçantë.
• Nodet përfundimtare: veprimi për të realizuar, që paraqet vendimin përfundimtar.

Algoritmi fillon nga nodi i parë ("rrënja" e pemës). Ai ose merr një vendim se në cilin nod të birësuar të kalojë, ose ekzekuton veprimin që ndodhet në nod dhe përfundon.

Cila është përparësia, nëse pema e vendimmarrjes, bën të njëjtën punë si operatorët if në seksionin e mëparshëm? Këtu ka një sistem të përbashkët, ku çdo vendim ka vetëm një kusht dhe dy rezultate të mundshme. Kjo i mundëson zhvilluesit të krijojë AI nga të dhënat që përfaqësojnë vendimet në pemë, duke shmangur kodimin e tij të fortë. Të imagjinojmë në formë tabelari:

Nga ana e kodit, ju do të merrni një sistem për leximin e rreshtave. Krijoni një nyjë për secilin prej tyre, lidhni logjikën e vendimmarrjes bazuar në kolonën e dytë dhe nyjat fëmijë bazuar në kolonat tre dhe katër. Ju ende duhet të programoni kushtet dhe veprimet, por tani struktura e lojës do të jetë më komplekse. Në të, ju shtoni vendime dhe veprime të tjera, pastaj konfiguroni të gjithë AI-në duke redaktuar thjesht skedarin tekstor me definimin e pemës. Më pas, transferoni skedarin te dizajneri i lojës, i cili do të jetë në gjendje të ndryshojë sjelljen pa rikompilimin e lojës dhe ndryshimin e kodit.

Pemët e vendimmarrjes janë shumë të dobishme kur ndërttohen automatikisht në bazë të një grupi të madh shembujsh (p.sh., duke përdorur algoritmin ID3). Kjo i bën ato një mjet efikas dhe me performancë të lartë për klasifikimin e situatave bazuar në të dhënat e marra. Megjithatë, ne dalim përtej një sistemi të thjeshtë për zgjedhjen e veprimeve nga agjentët.

Scenarët

Ne kemi shqyrtuar sistemin e pemës së vendimeve, i cili përdorte kushte dhe veprime të krijuara më parë. Njeriu që projektin inteligjencën artificiale mund ta organizojë pemën si të dojë, por ai ende duhet të mbështetet te programuesi që e ka programuar atë. Çfarë nëse do mund t'i ofronim dizajnerit mjete për të krijuar kushtet apo veprimet e tij të veta?

Për të shmangur 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 në të cilin dizajneri do të regjistrojë kushtet për të verifikuar 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ë si në tabelën e parë, por zgjidhjet brenda vetes kanë kodin e tyre, i cili ngjason pak me pjesën kushtore të operatorit if. Në anën e kodit, kjo do të lexohej në kolonën e dytë për nyjet e vendimit, por përveçse të kërkojë një kusht të caktuar për të ekzekutuar (A është topi majtas nga paddle), ajo vlerëson shprehjen kushtore dhe kthen true ose false përkatësisht. Kjo bëhet me gjuhët e skriptimit Lua ose Angelscript. Me to, 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. pozita). Për më tepër, gjuha e skriptimit është më e thjeshtë se C++. Ajo nuk kërkon një fazë të plotë kompilimi, prandaj është ideale për korigjimin e shpejtë të logjikës lojë dhe lejon “non-koduesit” të krijojnë funksionet e nevojshme vetë.

Në shembullin e dhënë, gjuha e skriptimit përdoret vetëm për të vlerësuar shprehjen kushtore, por 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. pozita.x += 10). Kështu, që veprimi gjithashtu të përcaktohej në skript, pa nevojën për programimin e Move Paddle Right.

Mundë të shkojmë edhe më larg dhe të shkruajmë plotësisht një pemë vendimesh në një gjuhë skenarësh. Kjo do të jetë kod në formën e operatorëve të kushtit të programuar ngusht (hardcoded), por ata do të jenë në skedarë të jashtëm skenari, domethënë mund të ndryshohen pa kompilimin e të gjithë programit. Shpesh mund të ndryshoni skedarin e skenarit pikërisht gjatë lojës për të testuar shpejt reagimet e ndryshme të AI-së.

Reagimi ndaj ngjarjeve

Shembujt më sipër përshtaten perfekt me Pong. Ata vazhdimisht drejtojnë një cikël Sense/Think/Act dhe veprojnë në bazë të gjendjes më të fundit të botës. Por në lojëra më komplekse, është e nevojshme të reagohet ndaj ngjarjeve të veçanta, dhe jo të vlerësohet gjithçka njëkohësisht. Pong në këtë rast nuk është më një shembull i mirë. Le të zgjedhim një tjetër.

Imagjinoni një lojë qëllimi, ku armiqtë qëndrojnë të palëvizur derisa të zbulojnë lojtarin, pas së cilës veprojnë në varësi të "specializimit" të tyre: dikush do të nxitojë të sulmojë, dikush tjetër do të sulmojë nga larg. Kjo është ende një sistem reagues themelor — "nëse lojtari është vërejtur, atëherë bëj diçka" — por mund të ndahet në mënyrë logjike në ngjarje që janë Vëreni Lojtarin (Player Seen) dhe reagimin (zgjidhni një përgjigje dhe realizoni atë).

Kjo na kthen te cikli Sense/Think/Act. Ne mund të kodifikojmë pjesën Sense, e cila çdo çast do të kontrolleoje — a e sheh AI lojtarin. Nëse jo — nuk ndodhin asgjë, por nëse e sheh, krijohet një ngjarje 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ë arritur në pjesët Think dhe Act. Kështu, do të konfiguroni reagimet ndaj ngjarjes Player Seen: për një karakter "të ngjitur" — ChargeAndAttack, dhe për një sniper — HideAndSnipe. Këto lidhje mund të krijohen në një skedar të dhënash për redaktim të shpejtë pa e nevojitur riparimin e kodit. Po ashtu, këtu mund të përdoret një gjuhë skenarësh.

Marrja e vendimeve të komplikuara

Sistemat e thjeshta të reagimeve janë shumë efektive, por ndodhin shumë situata ku ato nuk mjaftojnë. N sometimes duhet të marrim vendime të ndryshme në bazë të asaj që agjenti po bën në momentin aktual, por është e vështirë të paraqitet si një kusht. N sometimes ka shumë kushte për të paraqitur efektivisht në një pemë vendimesh ose skenarë. N sometimes duhet të vlerësojmë paraprakisht se si do të ndryshojë situata, përpara se të marrim një vendim për hapat e mëpasshëm. Për të zgjidhur këto probleme, janë të nevojshme qasje më të komplikuara.

Makinë gjendjeje e përfunduar

Makinë gjendjeje e përfunduar ose FSM (automati i përfunduar) është një mënyrë për të thënë se agjenti ynë aktualisht ndodhet në një nga disa gjendje të mundshme dhe se ai mund të kalojë nga një gjendje në tjetrën. Ka një numër të caktuar të këtyre gjendjeve, prandaj quhet kështu. Një shembull më i mirë nga jeta është semafori. Në vende të ndryshme ka renditje të ndryshme dritash, por principi mbetet i njëjtë - çdo gjendje paraqet diçka (ndalu, shko, etj.). Semafori është vetëm në një gjendje në çdo moment, dhe kalon nga njëra në tjetrën bazuar në rregulla të thjeshta.

Me NPC-t në lojëra ndodhet një histori e ngjashme. Për shembull, të marrim rojen me këto gjendje:

• Patrullues (Patrolling).
• Sulmues (Attacking).
• Ikës (Fleeing).

Dhe me këto kushte për të ndryshuar gjendjen e tij:

• Nëse roja sheh armikun, ai sulmon.
• Nëse roja sulmon, por nuk sheh më armikun e tij, ai kthehet në patrullim.
• Nëse roja sulmon, por është rëndë i plagosur, ai ikën.

Gjithashtu, është e mundur të shkruani if-operatorët me variablën-gjendje të rojës dhe kontrollet e ndryshme: a ka ndonjë armik në afërsi, çfarë niveli shëndeti ka NPC-ja etj. Shtojmë disa gjendje të tjera:

• Përgjegjës (Idling) — ndërmjet patrullave.
• Kërkim (Searching) — kur armiku i parë i dukshëm është fshehur.
• Kërkesa për ndihmë (Finding Help) — kur armiku është vërejtur, por është shumë i fortë për t'u përballur vetëm.

Zgjedhja për secilin prej tyre është e kufizuar — për shembull, roja nuk do të shkojë të kërkojë armikun e fshehur, nëse ka shëndet të ulët.

Në fund të fundit, një listë e madhe "nëse <x и y, но не z>, atëherë <p>" mund të bëhet shumë e rëndë, prandaj është e nevojshme të formizohet një metodë që do të na lejojë të mbajmë mend shtetet dhe kalimet midis shteteve. Për ta bërë këtë, do të marrim parasysh të gjitha shtetet dhe nën secilin shtet do të shkruajmë në listë të gjitha kalimet në shtete të tjera, së bashku me kushtet e nevojshme për to.

Kjo është tabela e kalimeve të gjendjeve — një mënyrë kompleks për të paraqitur FSM. Le të vizatojmë një diagram dhe të kemi një pasqyrë të plotë se si ndryshon sjellja e NPC.

Diagrami pasqyron thelbin e vendimmarrjes për këtë agent në bazë të situatës aktuale. Çdo arrow tregon kalimin ndërmjet gjendjeve, nëse kushti afër saj është i vërtetë.

Me çdo përditësim ne kontrollojmë gjendjen aktuale të agentit, shqyrtojmë listën e kalimeve, dhe nëse kushtet për kalim janë plotësuar, ai merr një gjendje të re. Për shembull, çdo kornizë kontrollet nëse 10-sekondëshi timer ka skaduar dhe nëse po, atëherë nga gjendja Idling, agjenti kalon në Patrolling. Në të njëjtën mënyrë, gjendja Attacking kontrollon shëndetin e agentit — nëse është e ulët, ai kalon në gjendjen Fleeing.

Kjo është përpunimi i kalimeve ndërmjet gjendjeve, por si lidhur me sjelljen që lidhet me vetë gjendjet? Sa i përket zbatimit të sjelljes faktike për një gjendje specifike, zakonisht ekzistojnë dy lloje "hook"-esh, ku ne i caktojmë veprimet në FSM:

• Veprimet që ne i realizojmë periodikisht për gjendjen aktuale.
• Veprimet që ne ndërmarrim kur kalojmë nga një gjendje në një tjetër.

Shembuj për llojin e parë. Shtimi Patrolling çdo kadër do të lëvizë agjentin nëpër rrugën e patrullimit. Shtimi Attacking çdo kadër do të përpiqet të fillojë një sulm ose të kalojë në një gjendje kur kjo është e mundur.

Për llojin e dytë, le të shqyrtojmë kalimin "nëse armiku është i dukshëm dhe armiku është shumë i fortë, atëherë kaloni në gjendjen Finding Help. Agjenti duhet të zgjedhë se ku të shkojë për ndihmë dhe të ruajë këtë informacion, në mënyrë që gjendja Finding Help të di ku të drejtohet. Pasi të jetë gjetur ndihma, agjenti kthehet në gjendjen Attacking. Në këtë moment, ai do të dëshirojë të tregojë aleatit për kërcënimin, prandaj mund të ndodhë veprimi NotifyFriendOfThreat.

Dhe përsëri, ne mund ta shikojmë këtë sistem përmes ciklit Sense/Think/Act. Sense shprehet në të dhënat e përdorura nga logjika e kalimit. Think – kalimet që janë të disponueshme në çdo gjendje. Ndërsa Act realizohet nga veprimet që kryhen në mënyrë periodike brenda gjendjes ose në kalimet mes gjendjeve.

Ndonjëherë, pyetjet e vazhdueshme të kushteve të kalimit mund të jenë të kushtueshme. Për shembull, nëse çdo agjent do të kryejë llogaritje komplekse çdo çast për të përcaktuar nëse sheh armiq dhe për të kuptuar nëse mund të kalojë nga gjendja Patrolling në Attacking — do të kërkojë shumë kohë procesori.

Ndryshimet e rëndësishme në gjendjen e botës mund të konsiderohen si ngjarje që do të trajtohen ndërsa shfaqen. Në vend që FSM të kontrollojë çdo çast kushtin e kalimit 'mund ta shoh agjenti lojtarin?', mund të konfigurohet një sistem i veçantë për të bërë kontrolle më pak shpesh (p.sh., 5 herë në sekondë). Rezultati do të jetë 'Player Seen' kur kontrolli kalon.

Kjo kalon në FSM, e cila tani duhet të kalojë në kushtin 'Player Seen event received' dhe të reagojë përkatësisht. Së fundmi, sjellja është e njëjtë përveç një vonese pothuajse të pandjeshme para përgjigjes. Megjithatë, performanca është përmirësuar për shkak të ndarjes së pjesës së Dijen në një pjesë të veçantë të programit.

Hierarchical finite state machine

Megjithatë, punimi me FSM të mëdha nuk është gjithmonë i lehtë. Nëse dëshirojmë të zgjasim gjendjen e sulmit duke e zëvendësuar atë me MeleeAttacking (sulmi në afërsi) dhe RangedAttacking (sulmi në distancë), do të duhet të ndryshojmë kalimet nga të gjitha gjendjet e tjera që çojnë në gjendjen Attacking (sulmi aktual dhe të ardhshëm).

Sigurisht që 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 mirë të mos përsërisnim, veçanërisht nëse shtojmë më shumë gjendje të ngjashme. Ka kuptim të grupojmë Idling dhe Patrolling nën një etiketë të përbashkët "jo-kombëtare", ku ka vetëm një grup të përbashkët kalimesh në gjendje luftarake. Nëse e imagjinoni 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 të re jo-kombëtare:

Gjendjet kryesore:


Gjendja jashtë luftimeve:


Dhe në formën e diagramit:

Kjo është e njëjta sistem, por me një gjendje të re jo-luftarake që përfshin Idling dhe Patrolling. Çdo gjendje përmban një FSM me nën-gjendje (dhe këto nën-gjendje, nga ana e tyre, përmbajnë FSM të veta — dhe kështu me radhë, sipas nevojës), duke na ofruar një Hierarchical Finite State Machine ose HFSM (makina përfundimtare hierarkike). Duke grupuar gjendjen jo-luftarake, ne eliminojmë 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 ne zgjeron gjendjen Attacking në gjendjet MeleeAttacking dhe MissileAttacking, ato do të jenë nën-gjendje që kalojnë mes njëra-tjetrës në bazë të distancës ndaj armikut dhe disponueshmërisë së municionit. Në përfundim, modelet komplekse të sjelljes dhe nën-modelet e sjelljes mund të përfaqësohen me një minimum të kalimeve të dyfishuara.

Pema e sjelljeve

Me HFSM krijohen kombinime komplekse të sjelljes në një mënyrë të thjeshtë. Megjithatë, ka një vështirësi të vogël, që marrja e vendimeve në formën e rregullave të kalimit është ngushtësisht e lidhur me gjendjen aktuale. Dhe në shumë lojëra, kjo është pikërisht ajo që nevojitet. Një përdorim i kujdesshëm i hierarkisë së gjendjeve mund të reduktojë numrin e përsëritjeve gjatë kalimit. Por ndonjëherë kërkohen rregulla që punojnë pavarësisht se në cilën gjendje jeni ose që aplikohen pothuajse në çdo gjendje. Për shembull, nëse shëndeti i agjentit bie në 25%, do të dëshironi që ai të ikë pavarësisht nëse ka qenë në luftë, është duke e kaluar kohën ose po bisedon — do t'ju duhet ta shtoni këtë kusht në çdo gjendje. Dhe nëse dizajneri juaj më vonë do të dëshirojë të ndryshojë pragun e shëndetit të ulët nga 25% në 10%, atëherë do të duhen trajtuar përsëri këto çështje.

Në përkryer, për këtë situatë, nevojitet një sistem ku vendimet «në cilën gjendje të jeni» janë jashtë vetë gjendjeve, që të bëni ndryshime vetëm në një vend dhe të mos preken kushtet e kalimit. Këtu paraqiten pemët e sjelljes.

Ka existen disa mënyra për t'i realizuar ato, por thelbi për të gjitha është më shumë i njëjtë dhe ngjason me një pemë vendimmarrjeje: algoritmi fillon nga nodi "rrënjësor", dhe në pemë ka node që përfaqësojnë ose vendime, ose veprime. Megjithatë, ka disa dallime kyçe:

• Tani nodet kthejnë një nga tre vlera: Suksesi (nëse puna është kryer), Dështimi (nëse nuk mund të fillohet) ose Duke u ekzekutuar (nëse është ende në proces dhe nuk ka rezultat përfundimtar).
• Nuk ka më node vendimesh për të zgjedhur midis dy alternativash. Në vend të tyre janë node Decorator, të cilat kanë një nod të vetëm fëmijë. Nëse ata janë të Succes, atjerë kryejnë nodin e tyre të vetëm fëmijë.
• Node që kryejnë veprime kthejnë vlerën Duke u ekzekutuar për të përfaqësuar veprimet që po kryhen.

Ky grup i vogël nodesh mund të mblidhet për të krijuar një numër të madh modelesh të komplikuara të sjelljes. Le të paraqesim HFSM-në e rojes nga shembulli i mëparshëm si një pemë sjelljeje:

Me këtë strukturë, nuk duhet të ketë kalime të qarta nga gjendjet Idling/Patrolling në gjendjen Attacking ose në ndonjë tjetër. Nëse armiku është në pamje dhe shëndeti i personazhit është i ulët, ekzekutimi do të ndalojë në nyjën Fleeing, pavarësisht nga cila nyje ai kishte ekzekutuar më parë — Patrolling, Idling, Attacking ose ndonjë tjetër.

Pemët e sjelljeve janë të komplikuara — ka shumë mënyra për t'i ndërtuar ato, dhe gjetja e kombinimit të duhur të dekoratorëve dhe nyjave përbërëse mund të jetë problematike. Ka gjithashtu pyetje se sa shpesh duhet të kontrollojmë pemën — duam ta kalojmë atë në çdo pjesë apo vetëm kur një nga kushtet ndryshon? Si të ruajmë gjendjen që i përket nyjeve — si të dijmë kur kemi qenë në gjendjen Idling për 10 sekonda ose si të dijmë cilat nyje janë ekzekutuar herën e kaluar, për të përpunuar saktë sekuencën?

Pikërisht për këtë arsye ekzistojnë shumë realizime. Për shembull, në disa sisteme, nyjat dekorator janë zëvendësuar nga dekoratorë të integruar. Ata rishikojnë pemën kur ndryshojnë kushtet e dekoratorëve, ndihmojnë për t'u lidhur me nyjat dhe sigurojnë përditësime periodike.

Sistemi i bazuar në utilitete

Disa lojra kanë një shumëllojshmëri mekanikash. Është e dëshirueshme që ato të përfitojnë nga rregullat e thjeshta dhe të përgjithshme të kalimit, por nuk është domosdoshmërisht në formatin e një peme të plotë të sjelljeve. Në vend që të kemi një grup të qartë zgjedhjesh ose një pemë veprimesh të mundshme, është më e lehtë të studiojmë të gjitha veprimet dhe të zgjedhim atë më të përshtatshmin në momentin e duhur.

Sistemi i bazuar në përfitim (utility-based system) është pikërisht ajo që ndihmon në këtë pasthënie. Ky është një sistem ku agjenti ka shumë veprime, dhe ai vetë zgjedh cilin të kryejë, duke u bazuar në përfitimin relativ të secilit. Ku përfitimi është një masë arbitrare e rëndësisë apo dëshirueshmërisë së kryerjes së këtij veprimi për agjentin.

Duke të përdorimit të veprimit të llogaritur në bazë të gjendjes aktuale dhe mjedisit, agjenti mund të kontrollojë dhe të zgjedhë në çdo moment gjendjen më të përshtatshme tjetër. Kjo ngjan me FSM, përveç faktit se kalimet përcaktohen nga vlerësimi për çdo gjendje të mundshme, duke përfshirë edhe atë aktuale. Vini re se ne zgjedhim veprimin më të dobishëm për të kaluar (ose qëndrojmë, nëse tashmë e kemi realizuar). Për më shumë larmi, kjo mund të jetë një zgjedhje e peshuar, por rastësore nga një listë e vogël.

Sistemi cakton një gamë të rastësishme të vlerave të dobishmërisë - për shembull, nga 0 (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 vlerë. Duke u kthyer në shembullin tonë me rojen:

Kalimet e kalimit midis veprimeve janë të paqartë — çdo gjendje mund të pasojë çfarëdo tjetër. Prioritetet e veprimeve janë në vlerat e kthyera të dobishmërisë. Nëse armiku është i dukshëm dhe ky armik është i fortë, ndërsa shëndeti i karakterit është i ulët, atëherë si Fleeing ashtu edhe FindingHelp do të kthejnë vlera të larta të pafundisë. Megjithatë, FindingHelp gjithmonë do të jetë më lartë. Po ashtu, veprimet jo-luftarake kurrë nuk kthejnë më shumë se 50, kështu që ato gjithmonë do të jenë më të ulta se veprimet luftarake. Kjo duhet të merret parasysh kur krijoni veprime dhe llogaritni dobishmërinë e tyre.

Në shembullin tonë, veprimet kthejnë ose një vlerë konstante të fiksuar, ose një nga dy vlerat e fiksuara. Një sistem më realistik parashikon kthimin e një vlerës nga një gamë të vazhdueshme vlerash. Për shembull, veprimi Fleeing kthen vlera më të larta të dobisë 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 përparësi mbi Attacking në çdo situatë kur agjenti ndjen se nuk ka mjaft shëndet për të fituar mbi kundërshtarin. Kjo lejon të ndryshojnë prioriteteve të veprimeve në bazë të një numri kriteresh, duke e bërë këtë qasje më fleksibël dhe variabile 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 formulash matematikore. Në The Sims, e cila modelon rutinën ditor të personazhit, shtohet një nivel shtesë llogaritjesh — agjenti merr një sërë "motivacionesh" që ndikojnë në vlerësimet e dobishmërisë. Nëse personazhi është i uritur, me kalimin e kohës do të ketë një urie më të madhe dhe rezultati i dobishmërisë së veprimit EatFood do të rritet derisa personazhi ta përmbushë atë, duke ulur nivelin e urisë dhe duke e kthyer vlerën EatFood në zero.

Ideja e zgjedhjes së veprimeve mbi bazën e një sistemi vlerësimi është mjaft e thjeshtë, prandaj sistemi i bazuar në dobi mund të përdoret si pjesë e proceseve të vendimmarrjes së AI-së, e jo si një zëvendësim i plotë për to. Një pemë vendimmarrje mund të kërkojë një vlerësim të dobishmërisë të dy node-ve të saj fëmijë dhe të zgjedhë atë me më të lartë. Në të njëjtën mënyrë, një pemë sjelljeje mund të ketë një nod të përbërë Utility për vlerësimin e dobishmërisë së veprimeve, për të vendosur se cilin element të fëmijës të ekzekutojë.

Lëvizja dhe navigimi

Në shembujt e mëparshëm kishim një platformë që lëviznim majtas ose djathtas, dhe një roje që patrullonte ose sulmonte. Por si e trajtojmë lëvizjen e agjentit për një periudhë të caktuar kohe? Si e vendosim shpejtësinë, si shmangim pengesat, dhe si planifikojmë rrugën kur arritja në destinacion është më e komplikuar se sa thjesht të lëvizësh në vijë të drejtpërdrejtë? Le të shqyrtojmë këtë.

Menaxhimi

Në fillim, le të supozojmë se çdo agjent ka një vlerë shpejtësie, e cila përfshin sa shpejt ai lëviz dhe në çfarë drejtimi. Ajo mund të matet në metra në sekondë, kilometra në orë, pikselet në sekondë, etj. Duke e mbajtur mend ciklin Sense/Think/Act, ne mund ta imagjinojmë se një pjesë e Think zgjat shpejtësinë, ndërsa një pjesë e Act e aplikon këtë shpejtësi te agjenti. Zakonisht, në lojëra ka një sistem fizik që e bën këtë për ju, duke studiuar vlerën e shpejtësisë së çdo objekti dhe duke e rregulluar atë. Prandaj, mund t'i lëmë AI një detyrë — të vendosë se sa shpejtësi duhet të ketë agjenti. Nëse dihet se ku duhet të jetë agjenti, atëherë duhet ta zhvendosim atë në drejtimin e duhur me një shpejtësi të caktuar. Një ekuacion shumë trivial:

desired_travel = destination_position – agent_position

Imagjinoni një botë 2D. Agenti ndodhet në pikën (-2,-2), destinacioni ndodhet diku në verilindje në pikën (30, 20), dhe rruga e nevojshme për agjentin që të arrijë atje është (32, 22). Le të supozojmë se këto pozita maten në metra — nëse e konsiderojmë shpejtësinë e agentit si 5 metra në sekondë, atëherë ne do ta skaluar vektorin tonë të lëvizjes dhe do të marrim një shpejtësi afërsisht (4.12, 2.83). Me këto parametra, agjenti do të arrinte në destinacion pas pothuajse 8 sekondash.

Vlerat mund të llogariten në çdo kohë. Nëse agjenti ishte në gjysmë të rrugës drejt qëllimit, lëvizja do të ishte gjysma e gjatësi, por për shkak se shpejtësia maksimale e agentit është 5 m/s (ne e kemi vendosur këtë më lart), shpejtësia do të jetë e njëjtë. Kjo funksionon gjithashtu për qëllimet që lëvizin, duke i lejuar agentit të bëjë disa ndryshime të vogla ndërsa ato lëvizin.

Por këtë arsye, ne duam më shumë variacion — për shembull, të rritet ngadalë shpejtësia për të simuluar një karakter që lëviz nga një pozite qëndruese në një pozite vrapimi. E njëjta gjë mund të bëhet edhe në fund përpara ndalesës. Këto funksionalitete njihen si sjellje drejtimi, secila prej të cilave ka emra të veçantë: Seek (kërkim), Flee (ikje), Arrival (mbërritje) etj. Ideja është se forcat e ndryshe mund të aplikohen në shpejtësinë e agentit, duke u bazuar në krahasimin e pozicionit të agentit dhe shpejtësisë së tij aktuale me destinacionin, për të përdorur mënyra të ndryshme për të arritur qëllimin.

Çdo sjellje ka një qëllim pak të ndryshëm. Seek dhe Arrival janë mënyra për të zhvendosur agjentin drejt destinacionit. Obstacle Avoidance (shmangia e pengesave) dhe Separation (ndarje) korrigjojnë lëvizjen e agjentit për të shmangur pengesat në rrugën drejt qëllimit. Alignment (ngjashmëria) dhe Cohesion (kohezioni) e mbajnë agjentët së bashku gjatë lëvizjes. Një numër i ndryshëm sjelljesh mund të përzihen për të marrë një vektor rrugë që merr parasysh të gjitha faktorët. Një agjent që 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ë lokacione të hapura pa shumë detaje.

Në kushte më të vështira, përzierja e sjelljeve të ndryshme funksionon më keq — p.sh., agjenti mund të ngecë në mur për shkak të konfliktit midis Arrival dhe Obstacle Avoidance. Prandaj, është e nevojshme të shqyrtohen mundësitë që janë më të komplikuara se thjesht përzierja e të gjitha vlerave. Një mënyrë është: në vend të përzierjes së rezultateve të çdo sjelljeje, mund të shqyrtojmë lëvizjen në drejtime të ndryshme dhe të zgjedhim mundësinë më të mirë.

Megjithatë, në një mjedis të komplikuar me kaloje dhe zgjedhje për të shkuar në cilën drejtim, na nevojitet diçka akoma më e avancuar.

Kërkimi i rrugës

Sjelljet drejtuese janë të përshtatshme për lëvizjen e thjeshtë në terrene të hapura (si fusha futbolli ose arena), ku të arrish nga A në B është një rrugë e drejtpërdrejtë me disa devijime rreth pengesave. Për rrugë të ndërlikuara, na nevojitet gjurmimi i rrugës (pathfinding), që është një mënyrë për të eksploruar botën dhe për të marrë vendime rreth rrugës përmes saj.

Mënyra më e thjeshtë është të aplikoni një rrjet mbi çdo katror pranë agjentit dhe të vlerësoni në cilat nga ata lejohet të lëvizni. Nëse ndonjë nga ata është destinacioni, atëherë ndiqni rrugën nga çdo katror deri te ai që e ka paraprirë, deri sa të arrini fillimin. Kjo është rruga. Në të kundërt, përsëritni procesin me katrorët më të afërt derisa të gjeni destinacionin ose të përfundojnë katrorët (kjo do të thotë se nuk ka asnjë rrugë të mundshme). Kjo është ajo që formalisht njihet si Kërkimi në Gjerësi ose BFS (algoritmi i kërkimit në gjerësi). Në çdo hap ai shikon në të gjitha drejtimet (prandaj gjerësia). Hapsira e kërkimit është si një front vale që lëviz derisa të arrijë vendin e kërkuar — zona e kërkimit zgjeron në çdo hap derisa të arrijë pikën përfundimtare, pas së cilës është e mundur të ndjekim rrugën deri në fillim.

Si rezultat, do të merrni një listë katrorësh, sipas të cilëve përgatitet rruga e nevojshme. Kjo është rruga (nga këtu, pathfinding) — lista e vendeve që agjenti do të vizitojë duke ndjekur në destinacion.

Duke se të dimë pozitat e çdo katrori në botë, mund të përdorim sjelljet e drejtuara për të lëvizur në rrugë — nga nyja 1 në nyjën 2, pastaj nga nyja 2 në nyjën 3 dhe kështu me radhë. Variante më e thjeshtë është të shkohet drejt qendrës së katrorit të ardhshëm, por edhe më mirë është të ndaloni në mes të skajit midis katrorit aktual dhe atij tjetër. Për këtë arsye, agjenti do të jetë në gjendje të përdorë këndet në kthesat e thella.

Algoritmi BFS ka edhe disavantazhe — ai eksploron aq katrorë në drejtimin "e gabuar" sa në "të duhurin". Këtu paraqitet një algoritëm më të ndërlikuar të quajtur A* (A yll). Ai funksionon gjithashtu, 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 nyjet në një listë dhe i rendit ato në mënyrë që nyja e ardhshme e studiuar gjithmonë të jetë ajo që do të çojë në rrugën më të shkurtër. Nyjet renditen duke u bazuar në një heuristikë që merr parasysh dy gjëra — "kostot" e rrugës hipotike drejt katrorit të dëshiruar (duke përfshirë çdo kostot për lëvizje) dhe një vlerësim se sa larg është ky katror nga destinacioni (duke i orientuar kërkimin në drejtimin e duhur).

Ky kyç është një shembull ku agjenti eksploron një katror në njëherë, duke zgjedhur çdo herë fqinj të cilët janë më premtues. Rruga e marrë është e njëjtë me atë të BFS, por gjatë procesit janë shqyrtuar më pak katrorë — dhe kjo ka një rëndësi të madhe për performancën e lojës.

Lëvizja pa gridë

Por shumica e lojërave nuk janë të vendosura në një gridë, dhe shpesh është e pamundur të krijohet një pa dëmtuar realizmin. Nevojiten kompromise. Cilat duhet të jenë dimensionet e katrorëve? Nëse janë shumë të mëdhenj — nuk do të mund të përfaqësojnë siç duhet korridore të vogla ose kthesa, nëse janë shumë të vegjël — do të ketë tepër shumë katrorë për të kërkuar, që përfundimisht do të marrë shumë kohë.

E para që duhen kuptuar është se rrjeti na ofron një graf të lidhurish node. Algoritmet A* dhe BFS në thelb punojnë me grafiqe dhe nuk u bëjnë fare ballë rrjetit tonë. Ne mund të vendosim nodet në çdo vend të botës së lojës: me kusht që të ketë lidhje midis çdo dy node të lidhura, si dhe midis pikës fillestare dhe asaj përfundimtare e të paktën njërit prej node-ve — algoritmi do punojë po aq mirë si më parë. Kjo shpesh quhet sistem pikash udhëzimi (waypoint), pasi çdo node paraqet një pozicion të rëndësishëm në botë, që mund të jetë pjesë e çdo numri të mundshëm rrugësh.

Shembulli 1: një node në secilën katror. Kërkimi fillon nga nodi në të cilin ndodhet agjenti dhe përfundon në nodin e katrorit të kërkuar.

Shembulli 2: një grup më i vogël nodesh (piqesh udhëzimi). Kërkimi fillon në katrorin me agjentin, kalon përmes numrit të nevojshëm të nodëve dhe pastaj vazhdon deri në destinacion.

Kjo është një sistem mjaft fleksibël dhe i fuqishëm. Por kërkohet kujdes në vendimet se ku dhe si të vendosen pikët e udhëtimit, nd otherwise agentët mund të mos shohin pikën më të afërt dhe nuk do të jenë në gjendje të nisin rrugën. Do të ishte më e thjeshtë nëse do të mundnim të vendosnim automatikisht pikët e udhëtimit në bazë të gjeometrisë së botës.

Këtu hyn në lojë rrjeta e navigimit ose navmesh (në shqip, rrjeta e navigimit). Kjo zakonisht është një rrjet 2D i trekëndëshave, i cili vendoset mbi gjeometrinë e botës — kudo që agjentit i lejohet të ecë. Çdo trekëndësh në rrjet bëhet një nyje në graf dhe ka deri në tre trekëndësha ngjitur, të cilët bëhen nyje fqinjë në graf.

Kjo foto është një shembull nga motori Unity — ai analizon gjeometrinë në botë dhe krijon navmesh (në screenshot në ngjyrë të lehtë blu). Çdo poligon në navmesh është një zonë ku agjenti mund të qëndrojë ose të lëvizë nga një poligon në një tjetër. Në këtë shembull, poligonet janë më të vogla se katet ku ndodhen — kjo është bërë për të marrë parasysh përmasat e agjentit, të cilat do të dalin jashtë pozicionit të tij nominal.

Ne mund të kërkojmë një rrugë përmes këtij rrjeti, duke përdorur përsëri algoritmin A*. Kjo do t'na japë një rrugë praktikisht perfekte në botë, e cila merr parasysh të gjithë gjeometrinë dhe njëkohësisht nuk kërkon nyje të tepërta dhe krijimin e pikave udhëzuese.

Gjetja e rrugës është një temë shumë e gjerë, për të cilën nuk mjafton një seksion i vetëm të një artikulli. Nëse dëshironi ta shqyrtoni atë më në detaje, atëherë kjo ndihmëson faqja e Amit Patel.

Planifikimi

Ne e kuptuam me gjetjen 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 dëshiruar. Mund ta përmbledhim këtë ide: arritja e një qëllimi nuk është thjesht hapi i ardhshëm, por një e tërë sekuencë, ku ndonjëherë është e nevojshme të shohësh para disa hapa, për të ditur se si duhet të jetë i pari. Kjo quhet planifikim. Gjetja e rrugës mund të konsiderohet si një nga disa shtesa të planifikimit. Nga pikëpamja e ciklit tonë Sense/Think/Act, kjo është ajo ku pjesa Think planifikon disa pjesë Act për të ardhmen.

Të shohim një shembull nga loja e tavolinës Magic: The Gathering. Ne luajmë të parët me këtë grup kartash në duar:

• Mires — jep 1 manë të zezë (kartë toke).
• Pyll — jep 1 manë të gjelbër (kartë toke).
• Magjistari I Ikur — kërkon 1 manë blu për thirrje.
• Mistiku Elvish — kërkon 1 manë të gjelbër për thirrje.

Le të injorojmë tre kartat e mbetura për të thjeshtuar. Sipas rregullave, lojtari ka të drejtë të luajë 1 kartë toke për raund, ai mund të "tapi" këtë kartë për të nxjerrë nga ajo manë, dhe pastaj të përdorë spell-et (përfshirë thirrjen e krijesave) sipas sasisë së manës. Në këtë situatë, lojtari njeri di se duhet të luajë Pyllin, "tapi" 1 manë të gjelbër, dhe pastaj të thërrasë Mistikun Elvish. Por si mund ta kuptojë këtë inteligjenca artificiale e lojës?

Planifikim i thjeshtë

Qasja triviale — provoni çdo veprim një pas një, derisa të mos mbeten veprime të përshtatshme. Duke parë kartat, AI sheh se mund të luajë Mires. Dhe e luan atë. A mbeten veprime të tjera në këtë raund? Ai nuk mund të thërrasë as Mistikun Elvish, as Magjistarin I Ikur, pasi për thirrjen e tyre kërkohet respektivisht manë e gjelbër dhe e blu, ndërsa Mires ofron vetëm manë të zezë. Dhe ai nuk do të mund të luajë më Pyllin, sepse tashmë e ka luajtur Mires. Kështu, inteligjenca artificiale e lojës veproi sipas rregullave, por e bëri këtë dobët. Mund të përmirësohet.

Planifikimi mund të gjejë një listë veprimesh që e çojnë lojën në gjendjen e dëshiruar. Ashtu siç çdo katror në rrugë kishte fqinjë (në gjetjen e rrugës), çdo veprim në plan gjithashtu ka fqinjë ose pasardhës. Ne mund të kërkojmë këto veprime dhe veprime të mëtejshme 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 pranuar mund të çojë në veprime të mëtejshme dhe të mbyllë të tjera, gjithashtu sipas rregullave të lojës. Imagjinoni se luajtëm Swamp — kjo do të heqë Swamp si hapin e ardhshëm (ne e luajtëm tashmë), gjithashtu do të heqë Forest (sepse sipas rregullave mund të luhet një kartë toke për raund). Pas kësaj, AI e shton si hap të ardhshëm — fitimin e 1 manave të zeza, sepse nuk ka mundësi tjetër. Nëse vazhdon dhe zgjidh Tap the Swamp, ai do të fitojë 1 njësi manas të zeza dhe nuk do të mund të bëjë asgje me të.

1. Të luajmë Swamp (rezultati: Swamp në lojë)
1.1 «Tapping» Swamp (rezultati: Swamp «tapped», +1 njësi e manës së zezë)
Ska veprime të disponueshme – FUND
2. Të luajmë Forest (rezultati: Forest në lojë)

Lista e veprimeve doli e shkurtër, ne u bllokuam. Po përsërisim procesin për veprimin tjetër. Ne luajmë Forest, hapim veprimin «merr 1 mana të gjelbër», që nga ana e tij do të hapë veprimin e tretë — thirrjen e Elvish Mystic.

1. Të luajmë Swamp (rezultati: Swamp në lojë)
1.1 «Tapping» Swamp (rezultati: Swamp «tapped», +1 njësi e manës së zezë)
Ska veprime të disponueshme – FUND
2. Të luajmë Forest (rezultati: Forest në lojë)
2.1 «Tapping» Forest (rezultati: Forest «tapped», +1 njësi e manës së gjelbër)
2.1.1 Thirrja e Elvish Mystic (rezultati: Elvish Mystic në lojë, -1 njësi e manës së gjelbër)
Ska 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 thjeshtë. Preferohet të zgjidhni planin më të mirë të mundshëm, jo thjesht ndonjë që përputhet me disa kritere. Në përgjithësi, është e mundur të vlerësoni planet e mundshme bazuar në rezultatin përfundimtar ose në dobinë e përgjithshme nga zbatimi i tyre. Mund të merrni 1 pikë për luajtjen e kartave të tokës dhe 3 pikë për thirrjen e një krijese. Të luani Swamp do të ishte një plan që jep 1 pikë. Ndërsa të luani Forest → Tapping the Forest → thirrjen e Elvish Mystic do t'ju jepte menjëherë 4 pikë.

Kështu funksionon planifikimi në Magic: The Gathering, por e njëjta logjikë aplikohet edhe në situata të tjera. Për shembull, të lëvizësh një pjestë për të çliruar hapësirë për lëvizjet e elefantit në shah. Ose të strehohesh pas një muri për të qëlluar në siguri në XCOM. Në përgjithësi, e kuptuat thelbin.

Planifikimi i përmirësuar

N sometimes there are too many potential actions to consider every possible option. Duke u kthyer te shembulli me Magic: The Gathering: le të themi se në lojë keni disa karta toke dhe krijesash në dorë - numri i kombinimeve të mundshme të lëvizjeve mund të llogaritet në dhjetra. Ka disa zgjidhje për problemin.

Mënyra e parë është formimi i zinxhirit mbrapsht (backwards chaining). Në vend që të shqyrtojmë të gjitha kombinimet, është më mirë të nisim nga rezultati përfundimtar dhe të provojmë të gjejmë një rrugë direkte. Në vend që të lëvizim nga rrënja e pemës në një gjethe të caktuar, ne lëvizim në drejtimin e kundërt - nga gjetheja në rrënjë. Kjo metodë është më e lehtë dhe më e shpejtë.

Nëse armiku ka 1 pikë shëndeti, mund të gjejmë një plan "të japim 1 ose më shumë pikë dëmi". Për ta arritur këtë, duhet të plotësojmë një sërë kushtesh:

1. Një magji mund të shkaktojë dëme — duhet të jetë në dorë.
2. Për të luajtur një magji — nevojitet mana.
3. Për të marrë mana — duhet të luash një kartë toke.
4. Për të luajtur një kartë toke — duhet ta kesh atë në dorë.

Një mënyrë tjetër është kërkimi best-first (kërkimi më i mirë i parë). Në vend që të shqyrtojmë të gjitha rrugët, ne zgjedhim atë më të përshtatshmen. Shpesh, ky metodë ofron një plan optimal pa shpenzime të tepërta në kërkime. A* është një formë e kërkimit më të mirë të parë — duke shqyrtuar rrugët më premtuese qysh në fillim, ai mund të gjejë tashmë rrugën më të mirë pa nevojën për të kontrolluar opsionet e tjera.

Një variant interesant dhe gjithnjë e më popullor i kërkimit best-first është Kërkimi me Pemë Monte Carlo. Në vend që të parashikojë se cilat plane janë më të mira në zgjedhjen e çdo veprimi të ardhshëm, algoritmi zgjedh pasardhës të rastësishëm në çdo hap derisa të arrijë në fund (kur plani çon në fitore ose humbje). Më pas, rezultati i fundit përdoret për të rritur ose ulur vlerësimin e "pesha" të opsioneve të mëparshme. Duke e përsëritur këtë proces disa herë radhazi, algoritmi ofron një vlerësim të mirë se cili është hapi tjetër më i mirë, edhe nëse situata ndryshon (nëse kundërshtari ndërmerr masa për ta penguar lojtarin).

Në tregimin e planifikimit në lojëra nuk mund të mungojë Planifikimi i Veprimeve të Orientuara nga Qëllimi ose GOAP (planifikimi i veprimeve me qëllim). Ky është një metodë e përdorur gjerësisht dhe e diskutuar, por përveç disa detajeve dalluese, në thelb është një metodë e ndërlidhjes prapa, për të cilën folëm më parë. Nëse detyra është "të shkatërrosh lojtarin", dhe loja ndodhet pas një mbrojtjeje, plani mund të jetë: shkatërro me një grenade → merr atë → hidhe.

Zakonisht ka disa qëllime, secila me prioritetin e saj. Nëse qëllimi me prioritetin më të lartë nuk mund të arrihet (asnjë kombinim veprimesh nuk krijon planin "shkatërro lojtarin", sepse lojtari nuk është i dukshëm), AI do të kthehet te qëllimet me prioritet më të ulët.

Mësimi dhe adaptimi

Kemi përmendur se AI i lojës zakonisht nuk përdor mësimin e makinerisë, sepse kjo nuk është e përshtatshme për menaxhimin e agentëve në kohë reale. Por kjo nuk do të thotë se nuk mund të huazohet diçka nga kjo fushë. Ne duam një armik të tillë në një lojë që mund të mësojmë diçka nga ai. Për shembull, të mësojmë për pozitat më të mira në hartë. Apo një armik në një luftë që do të bllokonte kombo të përdorura shpesh nga lojtari, duke e motivuar atë të përdorë të tjera. Kështu, mësimi i makinerisë në këto situata mund të jetë shumë i dobishëm.

Statistikat dhe probabilitetet

Para se ne kalojmë në shembuj të komplikuar, 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 mund të përcaktojmë nëse një lojtar mund të fillojë një sulm në minutat e para të lojës dhe çfarë mbrojtjeje t’i përgatisim kundër kësaj? Ne mund të shqyrtojmë përvojën e kaluara të lojtarit për të kuptuar se cila mund të jetë reagimi i tij në të ardhmen. Le të fillojmë me faktin se nuk kemi të dhëna të tilla fillestare, por mund t’i mbledhim ato — çdo herë që AI luan kundër njeriut, mund të regjistrojë kohën e sulmit të parë. Pas disa seancash do të kemi një mesatare të kohës që do të sulmojë lojtarin në të ardhmen.

Mesataret kanë një problem: nëse një lojtar 20 herë ‘ka shkuar për sulm’, dhe 20 herë ka luajtur ngadalë, atëherë vlerat e nevojshme do të jenë diku në mes, dhe kjo nuk do të na japë asgjë të dobishme. Një nga zgjidhjet është kufizimi i të dhënave hyrëse — mund të merrni parasysh 20 të fundit.

Një qasje e ngjashme përdoret kur vlerësohet probabiliteti i veprimeve të caktuara, duke supozuar se preferencat e kaluara të lojtarit do të jenë të njëjta në të ardhmen. Nëse lojtari na sulmon pesë herë me zjarr, dy herë me shkëndijë dhe një herë me duar, është e qartë se ai preferon zjarrin. Ekstrapolojmë dhe shohim probabilitetin e përdorimit të armëve të ndryshme: zjarr=62.5%, shkëndijë=25% dhe duar=12.5%. Inteligjenca jonë artificiale e lojës duhet të përgatitet për t'u mbrojtur nga zjarri.

Një metodë tjetër interesante është përdorimi i Klasifikuesit Naive Bayes (klasifikuesi 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ë si duhet. Klasifikuesit Bayes janë më të njohur për përdorimin e tyre në filtrat e spam-it të email-it. Aty ata studiojnë fjalët, i krahasojnë ato me vendet ku këto fjalë janë shfaqur më parë (në spam ose jo), dhe nxjerrin përfundime për email-et hyrëse. Ne mund të bëjmë të njëjtën gjë, madje edhe me një sasi më të vogël të të dhënave hyrëse. Bazuar në gjithë informacionin e dobishëm që sheh AI (p.sh., cilat njësi armiqësore janë krijuar, ose cilat spell-e po përdorin, ose cilat teknologji po hetojnë), dhe rezultatin përfundimtar (luftë ose paqe, 'sulm' ose mbrojtje, etj.) — do të zgjedhim sjelljen e duhur për AI.

Të gjitha këto mënyra mësimi janë të mjaftueshme, por preferohet të përdoren mbi të dhënat nga testimi. AI do të mësojë të përshtatet me strategjitë e ndryshme që kanë përdorur testuesit tuaj. Një AI që përshtatet me lojtarin pas lançimit mund të bëhet shumë parashikues ose, përkundrazi, shumë i vështirë për të fituar.

Përshtatja mbi bazën e vlerave

Duke marrë parasysh përmbajtjen e botës sonë të lojës dhe rregullat, mund të ndryshojmë grupin e vlerave që ndikojnë në marrjen e vendimeve, në vend që thjesht të përdorim të dhënat hyrëse. Së pari bëjmë këtë:

• Le të mbledhë AI të dhëna mbi gjendjen e botës dhe ngjarjet kyçe gjatë lojës (siç përmendet më sipër).
• Do të ndryshojmë disa vlera të rëndësishme (value) 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ë harta lojërash me perspektivë të parë. Çdo dhomë ka vlerën e saj, e cila përcakton sa dëshirohet të vizitohet. AI përzgjidh rastësisht se në cilën dhomë të shkonte, duke u bazuar në vlerën e saj. Më pas, agjenti kujton në cilën dhomë e vranë dhe zvogëlon vlerën e saj (probabiliteti që ai të kthehet atje). E njëjta gjë ndodh në situatën e kundërt - nëse agjenti shkatërron shumë kundërshtarë, atëherë vlera e dhomës rritet.

Modeli Markov

Çfarë nëse përdorim të dhënat e mbledhura për të parashikuar? Nëse e mbajmë mend çdo dhomë ku shohim lojtarin për një periudhë të caktuar kohe, 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ë marrim tri dhoma: të kuqe, të gjelbër dhe të blu. Po ashtu, kemi vëzhgimet që kemi regjistruar gjatë shikimit të seancës së lojës:

Numri i vëzhgimeve për çdo dhomë është pothuajse i barabartë — ende nuk e dimë se ku të krijojmë një vend të mirë për përrua. Mbledhja e statistikave e vështirësohet gjithashtu nga rikthimi i lojtarëve, të cilët shfaqen në mënyrë të barabartë në të gjithë h kartu. Por të dhënat për dhomën tjetër, në të cilën hyjnë pas shfaqjes në hartë — janë tashmë të dobishme.

E dukshme 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 dhe më tej. Dhomën e kaltër, përkundrazi, nuk e përdorin popull shumë, ato shkojnë aty me shumë pak, dhe nëse shkojnë, nuk qëndrojnë.

Por data treguese ndihmon për të pranuar diçka më të rëndësishme — kur një lojtar ndodhet në dhomën blu, dhoma tjetër ku ne do ta shohim më së shumti do të jetë e kuqe, dhe jo e gjelbër. Megjithëse dhoma e gjelbër është më e njohur se sa dhoma e kuqe, situata ndryshon kur lojtarin e kemi në të kaltër. Shteti i ardhshëm (pra, dhoma në të cilën do të kalojë lojtarin) varet nga gjendja e mëparshme (domethënë, dhoma në të cilën ndodhet aktualisht lojtarin). Falë studimit të varësive, do të parashikojmë më saktë sesa nëse do të numëronim vëzhgimet krejt ndaras nga njëra-tjetra.

Parashikimi i gjendjes së ardhshme në bazë të të dhënave të gjendjes së kaluar quhet modeli Markov (Markov model), ndërsa këto shembuj (me dhoma) quhen zinxhirë Markov. Pasi modelet përfaqësojnë probabilitetin e ndryshimeve midis gjendjeve të radhitura, ato paraqiten vizualisht si FSM me probabilitetin e kaluar për çdo kalim. Më parë e përdorëm FSM për të paraqitur gjendjen e sjelljes në të cilën ndodhej agjenti, por kjo koncept është i zbatueshëm për çdo gjendje, pavarësisht nëse lidhet me agjentin apo jo. Në këtë rast, gjendjet përfaqësojnë dhomën që përshkon agjenti:

Ky është një variant i thjeshtë i paraqitjes së probabilitetit të relatueshëm 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 50% mundësi që ai të mbetet atje gjatë vëzhgimit të ardhshëm. Por cila është probabiliteti që ai të jetë ende atje edhe pas kësaj? Ka jo vetëm mundësi që lojtari të ketë mbetur në dhomën e gjelbër pas dy vëzhgimeve, por gjithashtu edhe mundësi që ai të ketë ikur dhe të jetë kthyer. Ja një tabelë e re duke marrë parasysh të dhënat e reja:

Nga kjo shihet 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 e blu mes tyre, dhe 25% që lojtari të mos largohet fare nga dhoma e gjelbër.

Tabela — një mjet vizualisht i thjeshtë — procedura kërkon vetëm shumimin e probabiliteteve në çdo hap. Kjo do të thotë se mund të shikoni larg në të ardhmen me një rezervë: supozojmë se shansi për të hyrë në një dhomë varet plotësisht nga dhoma aktuale. Kjo quhet pronësia Markoviane (Markov Property) — gjendja e ardhshme varet vetëm nga e tanishmja. Por kjo nuk është 100% 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

Po çfarë about shembulli me luftën dhe parashikimin e kombinimeve të goditjeve të lojtarit? E njëjta gjë! Por në vend të një gjendjeje ose ngjarjeje, ne do të eksplorojmë të gjithë sekuencat nga të cilat përbëhet goditja e kombinuar.

Një nga mënyrat për ta bërë këtë është të ruani çdo input (p.sh., Shkelm, Grusht ose Bllok) në një bufer dhe të regjistroni tërë buferin si një ngjarje. Pra, lojtari përsëritshëm shtyp Shkelm, Shkelm, Grusht për të përdorur sulmin SuperDeathFist, sistemi AI ruan të gjitha inputet në bufer dhe mban mend tre të fundit, të përdorura në secilin hap.

(Rresht e theksuara me bold, kur lojtari nis një sulm SuperDeathFist.)

AI do të shohë të gjitha mundësitë kur lojtari zgjodhi Kick, pasuar nga një Kick tjetër, dhe më pas vëren se hyrja e ardhshme është gjithmonë Punch. Kjo do t'i lejojë agjentit të parashikojë kombinimin 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ë ruajtura. Në shembullin e mëparshëm, ishte një 3-gramë (trigramë), që do të thotë: dy të parat përdoren për të parashikuar të tretën. Po ashtu, në një 5-gramë, katër të parat 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 memorie, por gjithashtu ruan një histori më të vogël. Për shembull, një 2-gramë (bigramë) do të regjistrojë Kick, Kick ose Kick, Punch, por nuk do të mund të ruajë Kick, Kick, Punch, prandaj AI nuk do të reagojë ndaj kombinimit SuperDeathFist.

Nga ana tjetër, numrat e mëdhenj kërkojnë më shumë memorie dhe do të jetë më e vështirë për inteligjencën artificiale të mësojë, pasi do të ketë shumë më tepër mundësi. Po të kishim tri mundësi inputi: Kick, Punch ose Block, dhe ne do të përdornim 10-grama, do të ishim rreth 60 mijë variante të ndryshme.

Modeli i bigramit është një zinxhir i thjeshtë Markov — çdo çift «gjendje e kaluar/gjendje e tanishme» është një bigram, dhe ju mund të parashikoni gjendjen e dytë në bazë të së parës. 3-gramat dhe N-gramat më të mëdha gjithashtu mund të konsiderohen si zinxhirë Markov, ku të gjitha elementet (përveç elementit të fundit në N-gram) së bashku krijojnë gjendjen e parë, dhe elementi i fundit është gjendja e dytë. Një shembull me luftimet tregon mundësinë e kalimit nga gjendja Kick dhe Kick në gjendjen Kick dhe Punch. Duke shqyrtuar disa regjistrime të historisë së inputit si një njësi, ne në thelb po transformojmë sekuencën e inputit në një pjesë të një gjendjeje të plotë. Kjo na jep një pronësi Markov, duke na lejuar të përdorim zinxhirë Markov për të parashikuar inputin e ardhshëm dhe për të qenë në gjendje të hamendsojmë se cili do të jetë hapi tjetër i kombos.

Përfundimi

Kemi biseduar për mjetet dhe qasjet më të zakonshme në zhvillimin e inteligjencës artificiale. Po ashtu, shqyrtuam situatat në të cilat ato duhet të aplikohen dhe ku janë veçanërisht të dobishme.

Kjo duhet të jetë e mjaftueshme për të kuptuar bazat e inteligjencës artificiale në lojëra. Por, sigurisht, kjo nuk është e gjitha. Disa nga metodat më pak të njohura, por po aq efektive, përfshijnë:

• algoritme për optimizim, duke përfshirë ngjitjen mbi kodra, zbritjen gradiente dhe algoritmet gjenetikë
• algoritme konkurruese për kërkimin/planifikimin (minimax dhe pastrimi alpha-beta)
• metoda klasifikimi (perceptronë, rrjete neuronale dhe makinat e mbështetjes me vektorë)
• sisteme për përpunimin e perceptimit dhe kujtesës së agjenteve
• qasje arkitekturore për inteligjencën artificiale (sisteme hibride, nëngrupe arkitekturash dhe mënyra të tjera të mbivendosjes së sistemeve të inteligjencës artificiale)
• mjete animacioni (planifikimi dhe koordinimi i lëvizjes)
• faktorët e performancës (niveli i detajit, algoritmet anytime, dhe ndarja në kohë)

Burime online për temën:

1. Në GameDev.net ka një seksion me artikuj dhe tutoriale për inteligjencën artificiale, si dhe forum.
2. AiGameDev.com ofron shumë prezantime dhe artikuj mbi një gamë të gjerë temash të lidhura me zhvillimin e inteligjencës artificiale në lojëra.
3. GDC Vault 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 AI Game Programmers Guild.
5. Tommy Thompson, studiues i AI dhe zhvillues lojrash, publikon videa në kanalin e tij në YouTube AI and Games me shpjegime dhe studime mbi AI në lojërat komerciale.

Libra në temë:

1. Seri librash Game AI Pro përbën mbledhje artikujsh të shkurtra që shpjegojnë si të implementohet funksionet e caktuar ose si të zgjidhen probleme të caktuara.

Game AI Pro: Collected Wisdom of Game AI Professionals
Game AI Pro 2: Collected Wisdom of Game AI Professionals
Game AI Pro 3: Collected Wisdom of Game AI Professionals

2. Seri AI Game Programming Wisdom — paraardhësi i serisë Game AI Pro. Ajo përmban metoda më të vjetra, por pothuajse të gjitha janë relevante edhe sot.

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

3. Artificial Intelligence: A Modern Approach — është një nga tekstet baza për të gjithë ata që dëshirojnë të kuptojnë fushën e përgjithshme të inteligjencës artificiale. Ky libër nuk është për zhvillimin e lojërave — provon bazat e AI.

Burimi: habr.com