Vaig trobar material interessant sobre la intel·ligència artificial als jocs. Amb una explicació de coses bàsiques sobre la IA utilitzant exemples senzills, i a l'interior hi ha moltes eines i mètodes útils per al seu desenvolupament i disseny convenient. Com, on i quan utilitzar-los també hi és.
La majoria dels exemples estan escrits en pseudocodi, de manera que no es requereix cap coneixement avançat de programació. Sota el tall hi ha 35 fulls de text amb imatges i gifs, així que prepara't.
UPD. Demano disculpes, però ja he fet la meva pròpia traducció d'aquest article sobre Habré . Podeu llegir la seva versió , però per alguna raó m'ha passat l'article (he fet servir la cerca, però alguna cosa ha sortit malament). I com que escric en un bloc dedicat al desenvolupament de jocs, vaig decidir deixar la meva versió de la traducció per als subscriptors (alguns punts tenen un format diferent, alguns s'han omès deliberadament per consell dels desenvolupadors).
Què és la IA?
La IA del joc se centra en quines accions ha de realitzar un objecte en funció de les condicions en què es troba. Això es coneix comunament com a gestió d'"agent intel·ligent", on un agent és un personatge jugador, un vehicle, un bot o, de vegades, quelcom més abstracte: un grup sencer d'entitats o fins i tot una civilització. En cada cas, és una cosa que ha de veure el seu entorn, prendre decisions a partir d'ell i actuar d'acord amb elles. Això s'anomena cicle Sentir/Pensar/Actuar:
- Sentit: l'agent troba o rep informació sobre coses del seu entorn que poden influir en el seu comportament (amenaces properes, elements per recollir, llocs interessants per explorar).
- Pensa: l'agent decideix com reaccionar (considera si és prou segur per recollir objectes o si s'ha de lluitar/amagar-se primer).
- Actuar: l'agent realitza accions per implementar la decisió anterior (comença a avançar cap a l'enemic o l'objecte).
- ...ara la situació ha canviat per les accions dels personatges, així que el cicle es repeteix amb noves dades.
La IA tendeix a centrar-se en la part Sense del bucle. Per exemple, els cotxes autònoms fan fotografies de la carretera, les combinen amb dades de radar i lidar i les interpreten. Normalment, això es fa mitjançant l'aprenentatge automàtic, que processa les dades entrants i els dóna significat, extreu informació semàntica com "hi ha un altre cotxe a 20 metres per davant vostre". Aquests són els anomenats problemes de classificació.
Els jocs no necessiten un sistema complex per extreure informació, ja que la majoria de les dades ja en formen part integral. No cal executar algorismes de reconeixement d'imatges per determinar si hi ha un enemic per davant: el joc ja coneix i alimenta la informació directament al procés de presa de decisions. Per tant, la part Sentit del cicle sovint és molt més senzilla que la part Pensar i actuar.
Limitacions de la IA del joc
La IA té una sèrie de limitacions que cal tenir en compte:
- La IA no necessita ser entrenada per endavant, com si es tractés d'un algorisme d'aprenentatge automàtic. No té sentit escriure una xarxa neuronal durant el desenvolupament per controlar desenes de milers de jugadors i aprendre la millor manera de jugar contra ells. Per què? Perquè el joc no s'ha llançat i no hi ha jugadors.
- El joc ha de ser divertit i desafiant, de manera que els agents no haurien de trobar el millor enfocament contra les persones.
- Els agents han de semblar realistes perquè els jugadors se sentin com si juguen contra persones reals. El programa AlphaGo va superar els humans, però els passos escollits estaven molt lluny de la comprensió tradicional del joc. Si el joc simula un oponent humà, aquest sentiment no hauria d'existir. Cal canviar l'algoritme perquè prengui decisions plausibles en lloc de les ideals.
- La IA ha de funcionar en temps real. Això vol dir que l'algoritme no pot monopolitzar l'ús de la CPU durant llargs períodes de temps per prendre decisions. Fins i tot 10 mil·lisegons són massa llargs, perquè la majoria dels jocs només necessiten entre 16 i 33 mil·lisegons per fer tot el processament i passar al següent marc gràfic.
- L'ideal és que almenys una part del sistema estigui basada en dades, de manera que els no codificadors puguin fer canvis i els ajustos es puguin produir més ràpidament.
Vegem els enfocaments d'IA que cobreixen tot el cicle Sentir/Pensar/Actuar.
Prendre decisions bàsiques
Comencem amb el joc més senzill: Pong. Objectiu: moure la paleta de manera que la pilota hi reboti en lloc de passar-hi volant. És com el tennis, on es perd si no colpeja la pilota. Aquí la IA té una tasca relativament fàcil: decidir en quina direcció moure la plataforma.
Declaracions condicionals
Per a l'IA a Pong, la solució més òbvia és intentar sempre col·locar la plataforma sota la pilota.
Un algorisme senzill per a això, escrit en pseudocodi:
cada fotograma/actualització mentre s'executa el joc:
si la pilota està a l'esquerra de la pala:
mou la paleta cap a l'esquerra
en cas contrari, si la pilota està a la dreta de la pala:
mou la paleta cap a la dreta
Si la plataforma es mou a la velocitat de la pilota, aquest és l'algoritme ideal per a la IA a Pong. No cal complicar res si no hi ha tantes dades i possibles accions per a l'agent.
Aquest enfocament és tan senzill que tot el cicle Sentir/Pensar/Actuar amb prou feines es nota. Però hi és:
- La part Sense està en dues declaracions if. El joc sap on és la pilota i on és la plataforma, de manera que l'IA busca aquesta informació.
- La part Think també s'inclou a les dues declaracions if. Encarnen dues solucions, que en aquest cas s'exclouen mútuament. Com a resultat, es selecciona una de les tres accions: moure la plataforma cap a l'esquerra, moure-la cap a la dreta o no fer res si ja està correctament posicionada.
- La part Act es troba a les declaracions Move Paddle Left i Move Paddle Right. Segons el disseny del joc, poden moure la plataforma a l'instant o a una velocitat específica.
Aquests enfocaments s'anomenen reactius: hi ha un conjunt simple de regles (en aquest cas, si les declaracions del codi) que reaccionen a l'estat actual del món i actuen.
Arbre de decisions
L'exemple de Pong és en realitat equivalent a un concepte formal d'IA anomenat arbre de decisió. L'algoritme el passa per arribar a una "fulla", una decisió sobre quina acció cal prendre.
Fem un diagrama de blocs de l'arbre de decisió per a l'algorisme de la nostra plataforma:
Cada part de l'arbre s'anomena node; la IA utilitza la teoria de grafs per descriure aquestes estructures. Hi ha dos tipus de nodes:
- Nodes de decisió: triar entre dues alternatives basant-se en provar alguna condició, on cada alternativa es representa com un node separat.
- Nodes finals: l'acció a realitzar que representa la decisió final.
L'algorisme comença des del primer node (l'"arrel" de l'arbre). O bé pren una decisió sobre a quin node fill ha d'anar, o bé executa l'acció emmagatzemada al node i surt.
Quin és l'avantatge que un arbre de decisions faci la mateixa feina que les declaracions if de la secció anterior? Aquí hi ha un sistema general on cada decisió només té una condició i dos possibles resultats. Això permet al desenvolupador crear IA a partir de dades que representen decisions en un arbre sense haver de codificar-la. Ho presentem en forma de taula:
Al costat del codi, obtindreu un sistema per llegir cadenes. Creeu un node per a cadascun d'ells, connecteu la lògica de decisió basada en la segona columna i els nodes fills en funció de la tercera i quarta columna. Encara cal programar les condicions i les accions, però ara l'estructura del joc serà més complexa. Aquí afegiu decisions i accions addicionals i, a continuació, personalitzeu tota la IA simplement editant el fitxer de text de definició de l'arbre. A continuació, transferiu el fitxer a un dissenyador de jocs, que pot canviar el comportament sense recompilar el joc ni canviar el codi.
Els arbres de decisió són molt útils quan es construeixen automàticament a partir d'un gran conjunt d'exemples (per exemple, utilitzant l'algorisme ID3). Això els converteix en una eina eficaç i d'alt rendiment per classificar situacions a partir de les dades obtingudes. Tanmateix, anem més enllà d'un simple sistema d'agents per seleccionar accions.
Escenaris
Hem analitzat un sistema d'arbre de decisions que utilitza condicions i accions pre-creades. La persona que dissenya l'IA pot organitzar l'arbre com vulgui, però encara ha de confiar en el programador que ho va programar tot. I si poguéssim donar al dissenyador les eines per crear les seves pròpies condicions o accions?
Perquè el programador no hagi d'escriure codi per a les condicions Is Ball Left Of Paddle i Is Ball Right Of Paddle, pot crear un sistema en el qual el dissenyador escriurà condicions per comprovar aquests valors. Aleshores, les dades de l'arbre de decisió seran així:
Això és essencialment el mateix que a la primera taula, però les solucions tenen el seu propi codi, una mica com la part condicional d'una instrucció if. Al costat del codi, això es llegiria a la segona columna per als nodes de decisió, però en lloc de buscar una condició específica per executar (Is Ball Left Of Paddle), avalua l'expressió condicional i retorna vertader o fals en conseqüència. Això es fa mitjançant el llenguatge de script Lua o Angelscript. Utilitzant-los, un desenvolupador pot agafar objectes del seu joc (bola i pàdel) i crear variables que estaran disponibles al guió (ball.position). A més, el llenguatge de script és més senzill que C++. No requereix una fase de compilació completa, per la qual cosa és ideal per ajustar ràpidament la lògica del joc i permet que els "no codificadors" creïn ells mateixos les funcions necessàries.
A l'exemple anterior, el llenguatge de script només s'utilitza per avaluar l'expressió condicional, però també es pot utilitzar per a accions. Per exemple, les dades Move Paddle Right podrien convertir-se en una instrucció d'script (ball.position.x += 10). De manera que l'acció també es defineix al guió, sense necessitat de programar Move Paddle Right.
Podeu anar encara més enllà i escriure tot l'arbre de decisions en un llenguatge de script. Aquest serà codi en forma de declaracions condicionals codificades en dur, però es trobaran en fitxers d'script externs, és a dir, es poden canviar sense recompilar tot el programa. Sovint podeu editar el fitxer de script durant el joc per provar ràpidament diferents respostes d'IA.
Resposta a l'esdeveniment
Els exemples anteriors són perfectes per a Pong. Executen contínuament el cicle Sentir/Pensar/Actuar i actuen en funció de l'últim estat del món. Però en jocs més complexos cal reaccionar a esdeveniments individuals i no avaluar-ho tot alhora. Pong en aquest cas ja és un mal exemple. Triem-ne un altre.
Imagineu un shooter on els enemics estan immòbils fins que detecten el jugador, després de la qual cosa actuen en funció de la seva "especialització": algú córrer a "precipitar-se", algú atacarà des de lluny. No deixa de ser un sistema reactiu bàsic: "si es detecta un jugador, fes alguna cosa", però lògicament es pot dividir en un esdeveniment de jugador vist i una reacció (selecciona una resposta i executa-la).
Això ens porta de nou al cicle Sentir/Pensar/Actuar. Podem codificar una part Sense que comprovarà cada fotograma si l'IA veu el reproductor. Si no, no passa res, però si veu, es crea l'esdeveniment Player Seen. El codi tindrà una secció separada que diu "quan es produeixi l'esdeveniment Player Seen, feu" on és la resposta que necessiteu per abordar les parts Think and Act. Així, establiràs reaccions a l'esdeveniment Player Seen: per al personatge "corrent" - ChargeAndAttack, i per al franctirador - HideAndSnipe. Aquestes relacions es poden crear al fitxer de dades per a una edició ràpida sense haver de tornar a compilar. Aquí també es pot utilitzar el llenguatge de script.
Prendre decisions difícils
Encara que els sistemes de reacció simples són molt potents, hi ha moltes situacions en què no són suficients. De vegades cal prendre decisions diferents en funció del que està fent l'agent actualment, però és difícil imaginar-ho com una condició. De vegades hi ha massa condicions per representar-les eficaçment en un arbre de decisions o un script. De vegades cal avaluar amb antelació com canviarà la situació abans de decidir el següent pas. Es necessiten enfocaments més sofisticats per resoldre aquests problemes.
Màquina d'estats finits
La màquina d'estats finits o FSM (màquina d'estats finits) és una manera de dir que el nostre agent es troba actualment en un dels diversos estats possibles i que pot passar d'un estat a un altre. Hi ha un cert nombre d'estats d'aquest tipus, d'aquí el nom. El millor exemple de la vida és un semàfor. Hi ha diferents seqüències de llums en diferents llocs, però el principi és el mateix: cada estat representa alguna cosa (aturar-se, caminar, etc.). Un semàfor només es troba en un estat en un moment donat i es mou d'un a un altre segons regles senzilles.
És una història similar amb els NPC als jocs. Per exemple, prenguem una guàrdia amb els estats següents:
- Patrullant.
- Atacant.
- Fugint.
I aquestes condicions per canviar el seu estat:
- Si el guàrdia veu l'enemic, ataca.
- Si el guàrdia ataca però ja no veu l'enemic, torna a patrullar.
- Si un guàrdia ataca però està greument ferit, fuig.
També podeu escriure declaracions if amb una variable d'estat guardià i diverses comprovacions: hi ha un enemic a prop, quin és el nivell de salut de l'NPC, etc. Afegim uns quants estats més:
- Ociositat - entre patrulles.
- Recerca: quan l'enemic detectat ha desaparegut.
- Trobar ajuda: quan es detecta un enemic, però és massa fort per lluitar sol.
L'elecció de cadascun d'ells és limitada; per exemple, el guàrdia no anirà a buscar un enemic amagat si té poca salut.
Després de tot, hi ha una llista enorme de "si" , Això " pot arribar a ser massa feixuc, per la qual cosa hem de formalitzar un mètode que ens permeti tenir presents els estats i les transicions entre estats. Per fer-ho, tenim en compte tots els estats, i sota cada estat anotem en una llista totes les transicions a altres estats, juntament amb les condicions necessàries per a ells.
Aquesta és una taula de transició d'estats: una manera integral de representar FSM. Dibuixem un diagrama i obtenim una visió general completa de com canvia el comportament dels NPC.
El diagrama reflecteix l'essència de la presa de decisions d'aquest agent en funció de la situació actual. A més, cada fletxa mostra una transició entre estats si la condició que hi ha al costat és certa.
Cada actualització comprovem l'estat actual de l'agent, mirem la llista de transicions i, si es compleixen les condicions per a la transició, accepta el nou estat. Per exemple, cada fotograma comprova si el temporitzador de 10 segons ha caducat i, si és així, el guàrdia passa de l'estat d'inactivitat a la patrulla. De la mateixa manera, l'estat d'atac comprova la salut de l'agent; si és baix, passa a l'estat de fugida.
Això és gestionar les transicions entre estats, però què passa amb el comportament associat amb els propis estats? Pel que fa a la implementació del comportament real per a un estat particular, normalment hi ha dos tipus de "ganxo" on assignem accions al FSM:
- Accions que realitzem periòdicament per a l'estat actual.
- Les accions que fem quan passem d'un estat a un altre.
Exemples per al primer tipus. L'estat de patrulla mourà l'agent al llarg de la ruta de patrulla cada fotograma. L'estat d'atac intentarà iniciar un atac cada fotograma o transició a un estat on això sigui possible.
Per al segon tipus, considereu la transició "si l'enemic és visible i l'enemic és massa fort, aneu a l'estat Trobar ajuda. L'agent ha d'escollir on buscar ajuda i emmagatzemar aquesta informació perquè l'estat Trobar ajuda sàpiga on anar. Un cop es troba ajuda, l'agent torna a l'estat d'atacant. En aquest punt, voldrà dir-li a l'aliat l'amenaça, de manera que es pot produir l'acció NotifyFriendOfThreat.
Una vegada més, podem mirar aquest sistema a través de la lent del cicle Sentir/Pensar/Actuar. El sentit s'incorpora a les dades utilitzades per la lògica de transició. Think - transicions disponibles a cada estat. I Act es porta a terme mitjançant accions realitzades periòdicament dins d'un estat o en transicions entre estats.
De vegades, l'enquesta contínua de les condicions de transició pot ser costosa. Per exemple, si cada agent realitza càlculs complexos a cada fotograma per determinar si pot veure enemics i entendre si pot passar de l'estat de patrulla a l'estat d'atac, això necessitarà molt de temps de la CPU.
Els canvis importants en l'estat del món es poden considerar com esdeveniments que es processaran a mesura que es produeixin. En lloc que l'FSM comprove la condició de transició "el meu agent pot veure el reproductor?" cada fotograma, es pot configurar un sistema independent per comprovar-ho amb menys freqüència (per exemple, 5 vegades per segon). I el resultat és emetre el jugador vist quan passi el control.
Això es passa a l'FSM, que ara hauria d'anar a la condició de rebre l'esdeveniment Player Seen i respondre en conseqüència. El comportament resultant és el mateix tret d'un retard gairebé imperceptible abans de respondre. Però el rendiment ha millorat com a resultat de separar la part Sense en una part separada del programa.
Màquina jeràrquica d'estats finits
Tanmateix, treballar amb grans FSM no sempre és convenient. Si volem ampliar l'estat d'atac per separar MeleeAttacking i RangedAttacking, haurem de canviar les transicions de tots els altres estats que porten a l'estat d'atac (actual i futur).
Probablement us heu adonat que al nostre exemple hi ha moltes transicions duplicades. La majoria de les transicions a l'estat d'inactivitat són idèntiques a les transicions a l'estat de patrulla. Estaria bé no repetir-nos, sobretot si hi afegim més estats semblants. Té sentit agrupar Idling and Patrolling sota l'etiqueta general de "no combat", on només hi ha un conjunt comú de transicions per combatre els estats. Si pensem en aquesta etiqueta com un estat, aleshores Idling i Patrolling es converteixen en subestats. Un exemple d'ús d'una taula de transició independent per a un nou subestat que no sigui combat:
Estats principals:
Estat fora de combat:
I en forma de diagrama:
És el mateix sistema, però amb un nou estat de no combat que inclou Idling i Patrolling. Amb cada estat que conté un FSM amb subestats (i aquests subestats, al seu torn, que contenen els seus propis FSM, i així successivament durant el temps que necessiteu), obtenim una màquina d'estats finits jeràrquic o HFSM (màquina d'estats finits jeràrquic). Mitjançant l'agrupació de l'estat de no combat, hem retallat un munt de transicions redundants. Podem fer el mateix per a qualsevol estat nou amb transicions comunes. Per exemple, si en el futur ampliem l'estat d'atac als estats d'atac cos a cos i atac amb míssils, seran subestats que transiran entre si en funció de la distància a l'enemic i de la disponibilitat de munició. Com a resultat, es poden representar comportaments i subconductes complexos amb un mínim de transicions duplicades.
Arbre de comportament
Amb HFSM, es creen combinacions complexes de comportaments d'una manera senzilla. Tanmateix, hi ha una lleugera dificultat perquè la presa de decisions en forma de regles de transició estigui estretament relacionada amb l'estat actual. I en molts jocs això és exactament el que es necessita. I l'ús acurat de la jerarquia estatal pot reduir el nombre de repeticions de transició. Però de vegades necessiteu regles que funcionin independentment de l'estat en què us trobeu, o que s'apliquen a gairebé qualsevol estat. Per exemple, si la salut d'un agent baixa al 25%, voldreu que fugi independentment de si estava en combat, inactiu o parlant; haureu d'afegir aquesta condició a cada estat. I si més endavant el vostre dissenyador vol canviar el llindar de salut baix del 25% al 10%, s'haurà de tornar a fer.
Idealment, aquesta situació requereix un sistema en què les decisions sobre "en quin estat estar" estiguin fora dels propis estats, per tal de fer canvis només en un lloc i no tocar les condicions de transició. Els arbres de comportament apareixen aquí.
Hi ha diverses maneres d'implementar-los, però l'essència és aproximadament la mateixa per a tots i és similar a un arbre de decisió: l'algorisme comença amb un node "arrel" i l'arbre conté nodes que representen decisions o accions. Tanmateix, hi ha algunes diferències clau:
- Ara els nodes retornen un dels tres valors: Reeixit (si el treball s'ha completat), Ha fallat (si no es pot iniciar) o En execució (si encara s'està executant i no hi ha resultat final).
- No hi ha més nodes de decisió per triar entre dues alternatives. En canvi, són nodes Decorator, que tenen un node fill. Si tenen èxit, executen el seu únic node fill.
- Els nodes que realitzen accions retornen un valor en execució per representar les accions que s'estan realitzant.
Aquest petit conjunt de nodes es pot combinar per crear un gran nombre de comportaments complexos. Imaginem el guàrdia HFSM de l'exemple anterior com un arbre de comportament:
Amb aquesta estructura no hi hauria d'haver una transició òbvia des dels estats d'inactivitat/patrulla a l'atac o cap altre estat. Si un enemic és visible i la salut del personatge és baixa, l'execució s'aturarà al node Fugida, independentment del node que estigués executant anteriorment: patrulla, ralentí, atac o qualsevol altre.
Els arbres de comportament són complexos: hi ha moltes maneres de compondre'ls i trobar la combinació adequada de decoradors i nodes compostos pot ser un repte. També hi ha preguntes sobre amb quina freqüència s'ha de comprovar l'arbre: volem revisar-ne totes les parts o només quan una de les condicions ha canviat? Com emmagatzemem l'estat relatiu als nodes: com sabem quan hem estat inactius durant 10 segons, o com sabem quins nodes s'estaven executant l'última vegada per poder processar la seqüència correctament?
Per això hi ha moltes implementacions. Per exemple, alguns sistemes han substituït els nodes decoradors per decoradors en línia. Reavaluen l'arbre quan canvien les condicions del decorador, ajuden a unir nodes i proporcionen actualitzacions periòdiques.
Sistema basat en utilitats
Alguns jocs tenen moltes mecàniques diferents. És desitjable que rebin tots els avantatges de regles de transició simples i generals, però no necessàriament en forma d'arbre de comportament complet. En lloc de tenir un conjunt clar d'opcions o un arbre de possibles accions, és més fàcil examinar totes les accions i triar la més adequada en aquest moment.
El sistema basat en utilitats ajudarà només amb això. Es tracta d'un sistema on l'agent té una varietat d'accions i tria quines ha de realitzar en funció de la utilitat relativa de cadascuna. On la utilitat és una mesura arbitrària de l'important o desitjable que és que l'agent realitzi aquesta acció.
La utilitat calculada d'una acció en funció de l'estat i l'entorn actuals, l'agent pot comprovar i seleccionar l'altre estat més adequat en qualsevol moment. Això és similar al FSM, excepte quan les transicions es determinen per una estimació per a cada estat potencial, inclòs l'actual. Tingueu en compte que triem l'acció més útil per seguir endavant (o quedar-nos si ja l'hem completat). Per obtenir més varietat, aquesta podria ser una selecció equilibrada però aleatòria d'una petita llista.
El sistema assigna un rang arbitrari de valors d'utilitat, per exemple, de 0 (completament indesitjable) a 100 (completament desitjable). Cada acció té una sèrie de paràmetres que afecten el càlcul d'aquest valor. Tornant al nostre exemple de tutor:
Les transicions entre accions són ambigües: qualsevol estat pot seguir a qualsevol altre. Les prioritats d'acció es troben als valors d'utilitat retornats. Si un enemic és visible i aquest és fort i la salut del personatge és baixa, tant Fleeing com FindingHelp retornaran valors alts diferents de zero. En aquest cas, FindingHelp sempre serà més alt. Així mateix, les activitats no de combat mai retornen més de 50, per la qual cosa sempre seran inferiors a les de combat. Cal tenir-ho en compte a l'hora de crear accions i calcular la seva utilitat.
En el nostre exemple, les accions retornen un valor constant fix o un dels dos valors fixos. Un sistema més realista retornaria una estimació a partir d'un rang continu de valors. Per exemple, l'acció Fugir retorna valors d'utilitat més alts si la salut de l'agent és baixa, i l'acció Atacar retorna valors d'utilitat més baixos si l'enemic és massa fort. Per això, l'acció de Fugir té prioritat sobre l'atac en qualsevol situació en què l'agent senti que no té prou salut per derrotar l'enemic. Això permet prioritzar les accions en funció de qualsevol nombre de criteris, fent que aquest enfocament sigui més flexible i variable que un arbre de comportament o un FSM.
Cada acció té moltes condicions per al càlcul del programa. Es poden escriure en llenguatge de guió o com una sèrie de fórmules matemàtiques. Els Sims, que simula la rutina diària d'un personatge, afegeix una capa addicional de càlcul: l'agent rep una sèrie de "motivacions" que influeixen en les puntuacions d'utilitat. Si un personatge té gana, amb el pas del temps tindrà encara més gana i el valor d'utilitat de l'acció EatFood augmentarà fins que el personatge la realitzi, reduint el nivell de gana i tornant el valor EatFood a zero.
La idea de seleccionar accions basades en un sistema de qualificació és bastant senzilla, de manera que un sistema basat en utilitats es pot utilitzar com a part dels processos de presa de decisions d'IA, en lloc de substituir-los completament. L'arbre de decisió pot demanar una qualificació d'utilitat de dos nodes fills i seleccionar-ne el més alt. De la mateixa manera, un arbre de comportament pot tenir un node d'utilitat compost per avaluar la utilitat de les accions per decidir quin fill executar.
Moviment i navegació
En els exemples anteriors, teníem una plataforma que ens movem a l'esquerra o a la dreta, i un guàrdia que patrullava o atacava. Però, com gestionem exactament el moviment dels agents durant un període de temps? Com ajustem la velocitat, com evitem els obstacles i com planifiquem una ruta quan arribar a una destinació és més difícil que moure's en línia recta? Mirem això.
Governança
En l'etapa inicial, assumirem que cada agent té un valor de velocitat, que inclou la velocitat amb què es mou i en quina direcció. Es pot mesurar en metres per segon, quilòmetres per hora, píxels per segon, etc. Recordant el bucle Sense/Think/Act, podem imaginar que la part Think selecciona una velocitat i la part Act aplica aquesta velocitat a l'agent. Normalment els jocs tenen un sistema físic que fa aquesta tasca per tu, aprenent el valor de velocitat de cada objecte i ajustant-lo. Per tant, podeu deixar l'IA amb una tasca: decidir quina velocitat hauria de tenir l'agent. Si sabeu on hauria d'estar l'agent, haureu de moure'l en la direcció correcta a una velocitat determinada. Una equació molt trivial:
viatge_desitjat = posició_destinació – posició_agent
Imagineu un món en 2D. L'agent es troba al punt (-2, -2), la destinació es troba en algun lloc del nord-est al punt (30, 20) i el camí necessari perquè l'agent hi arribi és (32, 22). Suposem que aquestes posicions es mesuren en metres: si prenem que la velocitat de l'agent és de 5 metres per segon, escalarem el nostre vector de desplaçament i obtindrem una velocitat d'aproximadament (4.12, 2.83). Amb aquests paràmetres, l'agent arribaria al seu destí en gairebé 8 segons.
Podeu tornar a calcular els valors en qualsevol moment. Si l'agent estigués a mig camí de l'objectiu, el moviment seria la meitat de la longitud, però com que la velocitat màxima de l'agent és de 5 m/s (ho vam decidir més amunt), la velocitat serà la mateixa. Això també funciona per moure objectius, permetent a l'agent fer petits canvis a mesura que es mouen.
Però volem més variació, per exemple, augmentar lentament la velocitat per simular un personatge que passa de peu a córrer. El mateix es pot fer al final abans de parar. Aquestes característiques es coneixen com a comportaments de direcció, cadascun dels quals té noms específics: Seek, Flee, Arrival, etc. La idea és que les forces d'acceleració es puguin aplicar a la velocitat de l'agent, a partir de comparar la posició de l'agent i la velocitat actual amb la destinació en per tal d'utilitzar diferents mètodes per arribar a l'objectiu.
Cada comportament té un propòsit lleugerament diferent. La recerca i l'arribada són maneres de traslladar un agent a una destinació. L'evitació i la separació d'obstacles ajusten el moviment de l'agent per evitar obstacles en el camí cap a la meta. L'alineació i la cohesió fan que els agents es moguin junts. Es pot sumar qualsevol nombre de comportaments de direcció diferents per produir un únic vector de camí tenint en compte tots els factors. Un agent que utilitza els comportaments d'arribada, separació i evitació d'obstacles per mantenir-se allunyat de les parets i d'altres agents. Aquest enfocament funciona bé en llocs oberts sense detalls innecessaris.
En condicions més difícils, l'addició de diferents comportaments funciona pitjor; per exemple, un agent pot quedar-se encallat a una paret a causa d'un conflicte entre l'arribada i l'evitació d'obstacles. Per tant, cal tenir en compte opcions que siguin més complexes que simplement afegir tots els valors. El camí és el següent: en comptes de sumar els resultats de cada comportament, podeu considerar el moviment en diferents direccions i triar la millor opció.
Tanmateix, en un entorn complex amb carrerons sense sortida i opcions sobre el camí a seguir, necessitarem alguna cosa encara més avançada.
Trobar un camí
Els comportaments de direcció són excel·lents per al moviment senzill en una àrea oberta (camp de futbol o camp) on anar d'A a B és un camí recte amb només desviaments menors al voltant d'obstacles. Per a rutes complexes, necessitem trobar el camí, que és una manera d'explorar el món i decidir una ruta per ell.
El més senzill és aplicar una quadrícula a cada quadrat al costat de l'agent i avaluar quins d'ells poden moure's. Si un d'ells és un destí, seguiu el recorregut des de cada casilla fins a l'anterior fins arribar al principi. Aquesta és la ruta. En cas contrari, repetiu el procés amb altres quadrats propers fins que trobeu el vostre destí o us quedeu sense quadrats (és a dir, no hi ha cap ruta possible). Això és el que es coneix formalment com a Breadth-First Search o BFS (algorisme de cerca d'amplada-primer). A cada pas mira en totes direccions (d'aquí l'amplada, "amplada"). L'espai de cerca és com un front d'ona que es mou fins que arriba a la ubicació desitjada: l'espai de cerca s'expandeix a cada pas fins que s'inclou el punt final, després del qual es pot rastrejar fins al principi.
Com a resultat, rebràs una llista de quadrats per on es compila la ruta desitjada. Aquest és el camí (per tant, la recerca del camí): una llista de llocs que l'agent visitarà mentre segueix la destinació.
Atès que coneixem la posició de cada quadrat del món, podem utilitzar els comportaments de direcció per moure's al llarg del camí: del node 1 al node 2, després del node 2 al node 3, i així successivament. L'opció més senzilla és dirigir-se cap al centre de la casella següent, però una opció encara millor és aturar-se al mig de la vora entre la casella actual i la següent. Per això, l'agent podrà tallar cantonades en girs pronunciats.
L'algoritme BFS també té desavantatges: explora tants quadrats en la direcció "equivocada" com en la direcció "correcta". Aquí és on entra en joc un algorisme més complex anomenat A* (estrella A). Funciona de la mateixa manera, però en comptes d'examinar cegament quadrats veïns (després veïns dels veïns, després veïns dels veïns dels veïns, etc.), recull els nodes en una llista i els ordena de manera que el següent node examinat sigui sempre el la que porta a la ruta més curta. Els nodes s'ordenen en funció d'una heurística que té en compte dues coses: el "cost" d'una ruta hipotètica fins al quadrat desitjat (inclosos els costos de viatge) i una estimació de fins a quin punt es troba aquest quadrat de la destinació (esbiaixant la cerca a la casella). direcció correcta).
Aquest exemple mostra que l'agent explora un quadrat a la vegada, cada vegada escollint el que és adjacent que és més prometedor. El camí resultant és el mateix que el BFS, però es van considerar menys quadrats en el procés, cosa que té un gran impacte en el rendiment del joc.
Moviment sense quadrícula
Però la majoria dels jocs no estan distribuïts en una graella, i sovint és impossible fer-ho sense sacrificar el realisme. Calen compromisos. Quina mida han de tenir els quadrats? Massa grans i no seran capaços de representar correctament petits passadissos o girs, massa petits i hi haurà massa caselles per buscar, la qual cosa en definitiva trigarà molt de temps.
El primer que cal entendre és que una malla ens dóna un gràfic de nodes connectats. Els algorismes A* i BFS funcionen realment en gràfics i no els importa gens la nostra malla. Podríem posar nodes a qualsevol part del món del joc: sempre que hi hagi una connexió entre dos nodes connectats, així com entre els punts inicial i final i almenys un dels nodes, l'algoritme funcionarà tan bé com abans. Sovint s'anomena sistema de waypoints, ja que cada node representa una posició significativa al món que pot formar part de qualsevol nombre de camins hipotètics.
Exemple 1: un nus a cada quadrat. La cerca comença des del node on es troba l'agent i acaba al node del quadrat desitjat.
Exemple 2: un conjunt més petit de nodes (waypoints). La cerca comença a la plaça de l'agent, passa pel nombre de nodes necessari i, a continuació, continua fins a la destinació.
Aquest és un sistema completament flexible i potent. Però cal tenir cura a l'hora de decidir on i com col·locar un waypoint, en cas contrari, els agents simplement no veuran el punt més proper i no podran iniciar el camí. Seria més fàcil si poguéssim col·locar automàticament waypoints basats en la geometria del món.
Aquí és on apareix la malla de navegació o navmesh (malla de navegació). Normalment es tracta d'una malla 2D de triangles que es superposa a la geometria del món, allà on se li permet caminar l'agent. Cadascun dels triangles de la malla es converteix en un node al gràfic i té fins a tres triangles adjacents que es converteixen en nodes adjacents al gràfic.
Aquesta imatge és un exemple del motor Unity: va analitzar la geometria del món i va crear una malla de navegació (a la captura de pantalla en blau clar). Cada polígon d'una malla de navegació és una àrea on un agent pot estar o moure's d'un polígon a un altre. En aquest exemple, els polígons són més petits que els pisos on es troben, això es fa per tenir en compte la mida de l'agent, que s'estendrà més enllà de la seva posició nominal.
Podem cercar una ruta a través d'aquesta malla, de nou utilitzant l'algorisme A*. Això ens donarà una ruta gairebé perfecta al món, que té en compte tota la geometria i no requereix nodes innecessaris i creació de waypoints.
Pathfinding és un tema massa ampli per al qual no n'hi ha prou amb una secció d'un article. Si voleu estudiar-ho amb més detall, això us ajudarà .
Paleta
Hem après amb la recerca de camins que de vegades no n'hi ha prou amb triar una direcció i moure'ns: hem d'escollir una ruta i fer uns quants girs per arribar al nostre destí desitjat. Podem generalitzar aquesta idea: assolir un objectiu no és només el següent pas, sinó tota una seqüència on de vegades cal mirar endavant diversos passos per esbrinar quin ha de ser el primer. Això s'anomena planificació. Pathfinding es pot considerar com una de les diverses extensions de la planificació. Pel que fa al nostre cicle Sentir/Pensar/Actuar, aquí és on la part Pensar planifica diverses parts d'Actuar per al futur.
Vegem l'exemple del joc de taula Magic: The Gathering. Anem primer amb el següent conjunt de cartes a les nostres mans:
- Pantà - Dóna 1 manà negre (carta de terra).
- Bosc: dóna 1 manà verd (carta de terra).
- Mag fugitiu: requereix 1 mana blau per convocar.
- Elf Mystic: requereix 1 mana verd per convocar.
Ignorem les tres cartes restants per facilitar-ho. D'acord amb les regles, un jugador pot jugar 1 carta de terra per torn, pot "tocar" aquesta carta per extreure'n mana, i després llançar encanteris (incloent-hi convocar una criatura) segons la quantitat de mana. En aquesta situació, el jugador humà sap jugar a Forest, tocar 1 manà verd i, a continuació, convocar Elfish Mystic. Però, com pot esbrinar-ho l'IA del joc?
Fàcil planificació
L'enfocament trivial és provar cada acció al seu torn fins que no en quedin d'adequades. Mirant les cartes, la IA veu què pot jugar Swamp. I ell hi juga. Queden altres accions en aquest torn? No pot convocar ni el Místic Elf ni el Mag fugitiu, ja que requereixen mana verd i blau respectivament per convocar-los, mentre que Swamp només proporciona mana negre. I ja no podrà jugar a Forest, perquè ja ha jugat a Swamp. Per tant, la IA del joc va seguir les regles, però ho va fer malament. Es pot millorar.
La planificació pot trobar una llista d'accions que porten el joc a l'estat desitjat. De la mateixa manera que cada quadrat d'un camí tenia veïns (a la recerca de camins), cada acció d'un pla també té veïns o successors. Podem buscar aquestes accions i accions posteriors fins a arribar a l'estat desitjat.
En el nostre exemple, el resultat desitjat és "convocar una criatura si és possible". Al començament del torn, només veiem dues possibles accions permeses per les regles del joc:
1. Juga a Swamp (resultat: Swamp al joc)
2. Juga al bosc (resultat: bosc al joc)
Cada acció realitzada pot conduir a més accions i tancar-ne d'altres, de nou en funció de les regles del joc. Imagineu-vos que hem jugat a Pantà: això eliminarà Pantà com a pas següent (ja l'hem jugat) i també eliminarà Bosc (perquè segons les regles podeu jugar una carta de terra per torn). Després d'això, la IA afegeix obtenir 1 mana negre com a pas següent perquè no hi ha altres opcions. Si avança i tria Tap the Swamp, rebrà 1 unitat de manà negre i no podrà fer res amb ella.
1. Juga a Swamp (resultat: Swamp al joc)
1.1 Pantà "Toc" (resultat: Pantà "Tocat", +1 unitat de manà negre)
No hi ha cap acció disponible - FIN
2. Juga al bosc (resultat: bosc al joc)
La llista d'accions era curta, vam arribar a un carreró sense sortida. Repetim el procés per al següent pas. Juguem a Forest, obrim l'acció "obté 1 manà verd", que al seu torn obrirà la tercera acció: convocar Elvish Mystic.
1. Juga a Swamp (resultat: Swamp al joc)
1.1 Pantà "Toc" (resultat: Pantà "Tocat", +1 unitat de manà negre)
No hi ha cap acció disponible - FIN
2. Juga al bosc (resultat: bosc al joc)
2.1 Bosc "Tap" (resultat: el bosc està "tacat", +1 unitat de manà verd)
2.1.1 Convocar Elf Mystic (resultat: Elvish Mystic en joc, -1 manà verd)
No hi ha cap acció disponible - FIN
Finalment, vam explorar totes les accions possibles i vam trobar un pla que convocava una criatura.
Aquest és un exemple molt simplificat. És recomanable triar el millor pla possible, en lloc de qualsevol pla que compleixi alguns criteris. En general, és possible avaluar els plans potencials en funció del resultat o el benefici general de la seva implementació. Pots anotar-te 1 punt per jugar una carta de terra i 3 punts per convocar una criatura. Jugar a Swamp seria un pla d'1 punt. I jugar a Bosc → Toca el Bosc → convocar Elf Mystic donarà immediatament 4 punts.
Així és com funciona la planificació a Magic: The Gathering, però la mateixa lògica s'aplica en altres situacions. Per exemple, moure un peó per deixar espai perquè l'alfil es mogui als escacs. O protegeu-vos darrere d'una paret per disparar amb seguretat a XCOM així. En general, entens la idea.
Planificació millorada
De vegades hi ha massa accions potencials per considerar totes les opcions possibles. Tornant a l'exemple amb Magic: The Gathering: diguem que al joc i a la teva mà hi ha diverses cartes de terra i criatura: el nombre de combinacions possibles de moviments pot ser de desenes. Hi ha diverses solucions al problema.
El primer mètode és l'encadenament cap enrere. En lloc de provar totes les combinacions, és millor començar pel resultat final i intentar trobar una ruta directa. En lloc d'anar de l'arrel de l'arbre a una fulla específica, ens movem en sentit contrari: de la fulla a l'arrel. Aquest mètode és més fàcil i ràpid.
Si l'enemic té 1 salut, podeu trobar el pla "infligir 1 o més danys". Per aconseguir-ho, s'han de complir una sèrie de condicions:
1. El dany pot ser causat per un encanteri: ha d'estar a la mà.
2. Per llançar un encanteri, necessites mana.
3. Per obtenir mana, has de jugar una carta de terra.
4. Per jugar una carta de terra, cal tenir-la a la mà.
Una altra manera és la millor primera cerca. En lloc de provar tots els camins, triem el més adequat. Molt sovint, aquest mètode ofereix el pla òptim sense costos de cerca innecessaris. A* és una forma de millor primera cerca: examinant les rutes més prometedores des del principi, ja pot trobar el millor camí sense haver de comprovar altres opcions.
Una opció de cerca interessant i cada cop més popular és la cerca de l'arbre de Monte Carlo. En lloc d'endevinar quins plans són millors que els altres a l'hora de triar cada acció posterior, l'algoritme tria successors aleatoris a cada pas fins que arriba al final (quan el pla va donar lloc a la victòria o la derrota). El resultat final s'utilitza per augmentar o disminuir el pes de les opcions anteriors. En repetir aquest procés diverses vegades seguides, l'algoritme dóna una bona estimació de quin és el millor moviment següent, fins i tot si la situació canvia (si l'enemic pren mesures per interferir amb el jugador).
Cap història sobre la planificació en els jocs estaria completa sense la planificació d'acció orientada a objectius o GOAP (planificació d'acció orientada a objectius). Aquest és un mètode àmpliament utilitzat i discutit, però a part d'uns quants detalls distintius, és essencialment el mètode d'encadenament cap enrere del qual hem parlat anteriorment. Si l'objectiu era "destruir el jugador" i el jugador està a cobert, el pla podria ser: destruir amb una granada → aconseguir-ho → llançar-lo.
Normalment hi ha diversos objectius, cadascun amb la seva pròpia prioritat. Si no es pot completar l'objectiu de màxima prioritat (cap combinació d'accions crea un pla de "matar el jugador" perquè el jugador no és visible), l'IA tornarà a reduir els objectius de prioritat més baixa.
Formació i adaptació
Ja hem dit que la IA de jocs normalment no utilitza l'aprenentatge automàtic perquè no és adequada per gestionar agents en temps real. Però això no vol dir que no es pugui demanar prestat alguna cosa d'aquesta àrea. Volem un oponent en un tirador del qual puguem aprendre alguna cosa. Per exemple, esbrineu les millors posicions al mapa. O un oponent en un joc de lluita que bloquejaria els moviments combinats d'ús freqüent del jugador, motivant-lo a utilitzar altres. Per tant, l'aprenentatge automàtic pot ser molt útil en aquestes situacions.
Estadístiques i probabilitats
Abans d'entrar en exemples complexos, anem a veure fins on podem arribar fent unes quantes mesures senzilles i utilitzant-les per prendre decisions. Per exemple, estratègia en temps real: com determinem si un jugador pot llançar un atac en els primers minuts del joc i quina defensa preparar-se per fer-ho? Podem estudiar les experiències passades d'un jugador per entendre quines poden ser les reaccions futures. Per començar, no disposem de dades tan brutes, però les podem recollir: cada vegada que l'IA juga contra un humà, pot registrar el moment del primer atac. Després d'unes quantes sessions, obtindrem una mitjana del temps que trigarà el jugador a atacar en el futur.
També hi ha un problema amb els valors mitjans: si un jugador es va precipitar 20 vegades i va jugar lentament 20 vegades, els valors requerits estaran en algun lloc intermedi, i això no ens donarà res útil. Una solució és limitar les dades d'entrada: es poden tenir en compte les últimes 20 peces.
S'utilitza un enfocament similar quan s'estima la probabilitat de determinades accions assumint que les preferències del passat del jugador seran les mateixes en el futur. Si un jugador ens ataca cinc vegades amb bola de foc, dues vegades amb llamps i una vegada amb cos a cos, és evident que prefereix la bola de foc. Extrapolem i veiem la probabilitat d'utilitzar diferents armes: bola de foc=62,5%, llamps=25% i cos a cos=12,5%. La nostra IA del joc s'ha de preparar per protegir-se del foc.
Un altre mètode interessant és utilitzar el Naive Bayes Classifier per estudiar grans quantitats de dades d'entrada i classificar la situació perquè la IA reaccioni de la manera desitjada. Els classificadors bayesians són més coneguts pel seu ús en els filtres de correu brossa. Allà examinen les paraules, les comparen amb on aquestes paraules han aparegut abans (en correu brossa o no) i treuen conclusions sobre els correus electrònics entrants. Podem fer el mateix fins i tot amb menys entrades. A partir de tota la informació útil que veu la IA (com ara quines unitats enemigues es creen, o quins encanteris fan servir, o quines tecnologies van investigar) i el resultat final (guerra o pau, pressa o defensa, etc.) - triarem el comportament d'IA desitjat.
Tots aquests mètodes d'entrenament són suficients, però s'aconsella utilitzar-los a partir de dades de proves. La IA aprendrà a adaptar-se a les diferents estratègies que han utilitzat els vostres jugadors. La IA que s'adapta al jugador després del llançament pot arribar a ser massa previsible o massa difícil de derrotar.
Adaptació basada en valors
Tenint en compte el contingut del nostre món de joc i les regles, podem canviar el conjunt de valors que influeixen en la presa de decisions, en lloc d'utilitzar simplement les dades d'entrada. Fem això:
- Deixeu que l'IA reculli dades sobre l'estat del món i els esdeveniments clau durant el joc (com a dalt).
- Canviem uns quants valors importants basats en aquestes dades.
- Implementem les nostres decisions en funció del processament o avaluació d'aquests valors.
Per exemple, un agent té diverses sales per triar en un mapa de trets en primera persona. Cada habitació té el seu propi valor, que determina com de desitjable és visitar-la. L'IA escull aleatòriament a quina habitació anar en funció del valor. Aleshores, l'agent recorda a quina habitació va ser assassinat i en redueix el valor (la probabilitat que hi torni). De la mateixa manera per a la situació inversa: si l'agent destrueix molts oponents, el valor de l'habitació augmenta.
Model de Markov
I si utilitzem les dades recollides per fer prediccions? Si recordem cada habitació on veiem un jugador durant un període de temps determinat, predirem a quina habitació podria anar el jugador. Seguint i enregistrant els moviments del jugador a través de les habitacions (valors), podem predir-los.
Prenem tres habitacions: vermella, verda i blava. I també les observacions que vam gravar mentre veiem la sessió de joc:
El nombre d'observacions a cada habitació és gairebé igual; encara no sabem on fer un bon lloc per a una emboscada. La recollida d'estadístiques també es complica amb la reaparició dels jugadors, que apareixen uniformement al mapa. Però les dades de la següent habitació a la qual entren després d'aparèixer al mapa ja són útils.
Es pot veure que la sala verda s'adapta als jugadors: la majoria de la gent passa de la sala vermella a ella, el 50% dels quals romanen allà més. La sala blava, en canvi, no és popular, gairebé ningú hi va, i si ho fan, no s'hi queden gaire.
Però les dades ens diuen alguna cosa més important: quan un jugador està en una habitació blava, la següent habitació on el veiem serà vermella, no verda. Tot i que la sala verda és més popular que la sala vermella, la situació canvia si el jugador es troba a la sala blava. El següent estat (és a dir, la sala a la qual anirà el jugador) depèn de l'estat anterior (és a dir, l'habitació on es troba actualment). Com que explorem les dependències, farem prediccions més precises que si simplement comptéssim les observacions de manera independent.
La predicció d'un estat futur a partir de dades d'un estat passat s'anomena model de Markov, i aquests exemples (amb habitacions) s'anomenen cadenes de Markov. Com que els patrons representen la probabilitat de canvis entre estats successius, es mostren visualment com a FSM amb una probabilitat al voltant de cada transició. Anteriorment, vam utilitzar FSM per representar l'estat de comportament en què es trobava un agent, però aquest concepte s'estén a qualsevol estat, tant si està associat a l'agent com si no. En aquest cas, els estats representen l'habitació que ocupa l'agent:
Aquesta és una manera senzilla de representar la probabilitat relativa de canvis d'estat, donant a l'IA una certa capacitat per predir el següent estat. Podeu preveure diversos passos per endavant.
Si un jugador es troba a la sala verda, hi ha un 50% de possibilitats que romangui allà la propera vegada que sigui observat. Però quines possibilitats hi ha que encara hi sigui fins i tot després? No només hi ha la possibilitat que el jugador es quedi a la sala verda després de dues observacions, sinó que també hi ha la possibilitat que se'n vagi i torni. Aquí teniu la nova taula tenint en compte les noves dades:
Mostra que la probabilitat de veure el jugador a la sala verda després de dues observacions serà igual al 51% - 21% que serà de la sala vermella, 5% d'elles que el jugador visiti la sala blava entre ells, i 25% que el jugador no sortirà de la sala verda.
La taula és simplement una eina visual: el procediment només requereix multiplicar les probabilitats a cada pas. Això vol dir que podeu mirar cap al futur amb una advertència: suposem que la possibilitat d'entrar a una habitació depèn completament de l'habitació actual. Això s'anomena propietat de Markov: l'estat futur només depèn del present. Però això no és XNUMX% precís. Els jugadors poden canviar les decisions en funció d'altres factors: nivell de salut o quantitat de munició. Com que no registrem aquests valors, les nostres previsions seran menys precises.
N-grams
Què passa amb l'exemple d'un joc de lluita i la predicció dels moviments combinats del jugador? El mateix! Però en lloc d'un estat o esdeveniment, examinarem les seqüències senceres que formen un atac combinat.
Una manera de fer-ho és emmagatzemar cada entrada (com ara Kick, Punch o Block) en una memòria intermèdia i escriure la memòria intermèdia sencer com a esdeveniment. Així que el jugador prem repetidament Kick, Kick, Punch per utilitzar l'atac SuperDeathFist, el sistema d'IA emmagatzema totes les entrades en un buffer i recorda les tres últimes utilitzades en cada pas.
(Les línies en negreta són quan el jugador llança l'atac SuperDeathFist.)
L'IA veurà totes les opcions quan el jugador selecciona Kick, seguit d'un altre Kick, i després notarà que la següent entrada sempre és Punch. Això permetrà a l'agent predir el moviment combinat de SuperDeathFist i bloquejar-lo si és possible.
Aquestes seqüències d'esdeveniments s'anomenen N-grams, on N és el nombre d'elements emmagatzemats. A l'exemple anterior es tractava d'un trigrama de 3 grams, que vol dir: les dues primeres entrades s'utilitzen per predir la tercera. En conseqüència, en un gram de 5, les quatre primeres entrades prediuen la cinquena i així successivament.
El dissenyador ha de triar la mida dels N-grams amb cura. Una N més petita requereix menys memòria però també emmagatzema menys historial. Per exemple, un bigram de 2 grams gravarà Kick, Kick o Kick, Punch, però no podrà emmagatzemar Kick, Kick, Punch, de manera que l'IA no respondrà al combo SuperDeathFist.
D'altra banda, els números més grans requereixen més memòria i la IA serà més difícil d'entrenar ja que hi haurà moltes més opcions possibles. Si tinguéssiu tres possibles entrades de Kick, Punch o Block, i utilitzéssim un de 10 grams, serien unes 60 mil opcions diferents.
El model de bigrama és una cadena de Markov simple: cada parell d'estat passat/estat actual és un bigrama, i podeu predir el segon estat basant-vos en el primer. Els N-grams de 3 grams i més grans també es poden considerar cadenes de Markov, on tots els elements (excepte l'últim de l'N-gram) junts formen el primer estat i l'últim element el segon. L'exemple del joc de lluita mostra la possibilitat de passar de l'estat de puntades i puntades a l'estat de puntades i cops. En tractar diverses entrades de l'historial d'entrada com una sola unitat, estem transformant essencialment la seqüència d'entrada en part de tot l'estat. Això ens dóna la propietat de Markov, que ens permet utilitzar cadenes de Markov per predir la següent entrada i endevinar quin moviment combinat serà el següent.
Conclusió
Hem parlat de les eines i enfocaments més comuns en el desenvolupament de la intel·ligència artificial. També hem analitzat les situacions en què s'han d'utilitzar i on són especialment útils.
Això hauria de ser suficient per entendre els conceptes bàsics de la IA del joc. Però, per descomptat, no tots són mètodes. Menys populars, però no menys efectius inclouen:
- algorismes d'optimització que inclouen l'escalada de turons, el descens de gradients i els algorismes genètics
- algorismes de cerca/programació adversaris (poda mínima i alfa-beta)
- mètodes de classificació (perceptrons, xarxes neuronals i màquines de vectors de suport)
- sistemes de percepció i memòria dels agents de processament
- enfocaments arquitectònics de la IA (sistemes híbrids, arquitectures de subconjunts i altres maneres de superposar sistemes d'IA)
- eines d'animació (planificació i coordinació de moviment)
- factors de rendiment (nivell de detall, en qualsevol moment i algorismes de segmentació temporal)
Recursos en línia sobre el tema:
1. GameDev.net té I .
2. conté moltes presentacions i articles sobre una àmplia gamma de temes relacionats amb el desenvolupament de l'IA de jocs.
3. inclou temes de la GDC AI Summit, molts dels quals estan disponibles de forma gratuïta.
4. També es poden trobar materials útils al web .
5. Tommy Thompson, investigador d'IA i desenvolupador de jocs, fa vídeos a YouTube amb una explicació i estudi de la IA en jocs comercials.
Llibres sobre el tema:
1. La sèrie de llibres Game AI Pro és una col·lecció d'articles breus que expliquen com implementar funcions específiques o com resoldre problemes específics.
2. La sèrie AI Game Programming Wisdom és la predecessora de la sèrie Game AI Pro. Conté mètodes més antics, però gairebé tots són rellevants fins i tot avui.
3. és un dels textos bàsics per a tothom que vulgui entendre el camp general de la intel·ligència artificial. Aquest no és un llibre sobre desenvolupament de jocs, sinó que ensenya els conceptes bàsics de la IA.
Font: www.habr.com