Encontré material interesante sobre la inteligencia artificial en los juegos. Con una explicación de cosas básicas sobre la IA mediante ejemplos sencillos, y en su interior hay muchas herramientas y métodos útiles para su conveniente desarrollo y diseño. También está ahí cómo, dónde y cuándo usarlos.
La mayoría de los ejemplos están escritos en pseudocódigo, por lo que no se requieren conocimientos avanzados de programación. Debajo del corte hay 35 hojas de texto con imágenes y gifs, así que prepárate.
UPD. Pido disculpas, pero ya hice mi propia traducción de este artículo sobre Habré. . Puedes leer su versión. , pero por alguna razón el artículo se me pasó por alto (utilicé la búsqueda, pero algo salió mal). Y como estoy escribiendo en un blog dedicado al desarrollo de juegos, decidí dejar mi versión de la traducción para los suscriptores (algunos puntos tienen un formato diferente, algunos se omitieron deliberadamente por consejo de los desarrolladores).
¿Qué es la IA?
La IA del juego se centra en las acciones que debe realizar un objeto en función de las condiciones en las que se encuentra. Esto se conoce comúnmente como gestión de "agentes inteligentes", donde un agente es un personaje jugador, un vehículo, un robot o, a veces, algo más abstracto: un grupo completo de entidades o incluso una civilización. En cada caso, es una cosa que debe ver su entorno, tomar decisiones en función de él y actuar de acuerdo con él. Esto se llama ciclo Sentir/Pensar/Actuar:
- El sentido: El agente encuentra o recibe información sobre cosas en su entorno que pueden influir en su comportamiento (amenazas cercanas, elementos para recolectar, lugares interesantes para explorar).
- Piensa: el agente decide cómo reaccionar (considera si es lo suficientemente seguro para recolectar objetos o si debe luchar/esconderse primero).
- Actuar: el agente realiza acciones para implementar la decisión anterior (comienza a moverse hacia el enemigo u objeto).
- ...ahora la situación ha cambiado debido a las acciones de los personajes, por lo que el ciclo se repite con nuevos datos.
La IA tiende a centrarse en la parte sensorial del ciclo. Por ejemplo, los coches autónomos toman fotografías de la carretera, las combinan con datos de radar y lidar y las interpretan. Esto generalmente se hace mediante el aprendizaje automático, que procesa los datos entrantes y les da significado, extrayendo información semántica como "hay otro automóvil 20 metros delante de usted". Estos son los llamados problemas de clasificación.
Los juegos no necesitan un sistema complejo para extraer información ya que la mayoría de los datos ya son parte integral del mismo. No es necesario ejecutar algoritmos de reconocimiento de imágenes para determinar si hay un enemigo delante: el juego ya lo sabe y aporta la información directamente al proceso de toma de decisiones. Por lo tanto, la parte Sentir del ciclo suele ser mucho más sencilla que la parte Pensar y Actuar.
Limitaciones de la IA del juego
La IA tiene una serie de limitaciones que deben observarse:
- La IA no necesita ser entrenada previamente, como si fuera un algoritmo de aprendizaje automático. No tiene sentido escribir una red neuronal durante el desarrollo para monitorear decenas de miles de jugadores y aprender la mejor manera de jugar contra ellos. ¿Por qué? Porque el juego no ha sido lanzado y no hay jugadores.
- El juego debe ser divertido y desafiante, por lo que los agentes no deberían encontrar el mejor enfoque contra las personas.
- Los agentes deben parecer realistas para que los jugadores sientan que están jugando contra personas reales. El programa AlphaGo superó a los humanos, pero los pasos elegidos estaban muy alejados de la comprensión tradicional del juego. Si el juego simula un oponente humano, este sentimiento no debería existir. Es necesario cambiar el algoritmo para que tome decisiones plausibles en lugar de ideales.
- La IA debe funcionar en tiempo real. Esto significa que el algoritmo no puede monopolizar el uso de la CPU durante largos períodos de tiempo para tomar decisiones. Incluso 10 milisegundos es demasiado, porque la mayoría de los juegos sólo necesitan entre 16 y 33 milisegundos para realizar todo el procesamiento y pasar al siguiente cuadro de gráficos.
- Idealmente, al menos parte del sistema debería basarse en datos, de modo que los no codificadores puedan realizar cambios y los ajustes se realicen más rápidamente.
Veamos los enfoques de IA que cubren todo el ciclo Sentir/Pensar/Actuar.
Tomar decisiones básicas
Comencemos con el juego más simple: Pong. Objetivo: mover la paleta para que la pelota rebote en lugar de pasar volando. Es como el tenis, donde pierdes si no golpeas la pelota. Aquí la IA tiene una tarea relativamente fácil: decidir en qué dirección mover la plataforma.
Declaraciones condicionales
Para la IA en Pong, la solución más obvia es intentar siempre colocar la plataforma debajo de la pelota.
Un algoritmo simple para esto, escrito en pseudocódigo:
cada fotograma/actualización mientras se ejecuta el juego:
si la pelota está a la izquierda de la paleta:
mover la paleta hacia la izquierda
de lo contrario, si la pelota está a la derecha de la paleta:
mover la paleta hacia la derecha
Si la plataforma se mueve a la velocidad de la pelota, entonces este es el algoritmo ideal para la IA en Pong. No hay que complicarse nada si no hay tantos datos y posibles acciones para el agente.
Este enfoque es tan simple que todo el ciclo Sentir/Pensar/Actuar apenas se nota. Pero está ahí:
- La parte Sentido está en dos declaraciones if. El juego sabe dónde está la pelota y dónde está la plataforma, por lo que la IA busca esa información.
- La parte Pensar también se incluye en las dos declaraciones if. Representan dos soluciones, que en este caso se excluyen mutuamente. Como resultado, se selecciona una de tres acciones: mover la plataforma hacia la izquierda, moverla hacia la derecha o no hacer nada si ya está colocada correctamente.
- La parte Actuar se encuentra en las declaraciones Move Paddle Left y Move Paddle Right. Dependiendo del diseño del juego, pueden mover la plataforma instantáneamente o a una velocidad específica.
Estos enfoques se denominan reactivos: hay un conjunto simple de reglas (en este caso, declaraciones en el código) que reaccionan al estado actual del mundo y toman medidas.
Árbol de decisión
El ejemplo de Pong es en realidad equivalente a un concepto formal de IA llamado árbol de decisión. El algoritmo lo recorre hasta llegar a una “hoja”, una decisión sobre qué acción tomar.
Hagamos un diagrama de bloques del árbol de decisión del algoritmo de nuestra plataforma:
Cada parte del árbol se llama nodo; la IA utiliza la teoría de grafos para describir dichas estructuras. Hay dos tipos de nodos:
- Nodos de decisión: elegir entre dos alternativas basándose en probar alguna condición, donde cada alternativa se representa como un nodo separado.
- Nodos finales: La acción a realizar que representa la decisión final.
El algoritmo comienza desde el primer nodo (la "raíz" del árbol). Toma una decisión sobre a qué nodo hijo ir o ejecuta la acción almacenada en el nodo y sale.
¿Cuál es el beneficio de que un árbol de decisión haga el mismo trabajo que las declaraciones if de la sección anterior? Aquí existe un sistema general donde cada decisión tiene solo una condición y dos resultados posibles. Esto permite al desarrollador crear IA a partir de datos que representan decisiones en un árbol sin tener que codificarlo. Presentémoslo en forma de tabla:
En el lado del código obtendrá un sistema para leer cadenas. Cree un nodo para cada uno de ellos, conecte la lógica de decisión basada en la segunda columna y los nodos secundarios según la tercera y cuarta columnas. Aún necesitas programar las condiciones y acciones, pero ahora la estructura del juego será más compleja. Aquí agrega decisiones y acciones adicionales y luego personaliza toda la IA simplemente editando el archivo de texto de definición del árbol. A continuación, transfieres el archivo al diseñador del juego, quien puede cambiar el comportamiento sin volver a compilar el juego ni cambiar el código.
Los árboles de decisión son muy útiles cuando se construyen automáticamente a partir de un gran conjunto de ejemplos (por ejemplo, utilizando el algoritmo ID3). Esto los convierte en una herramienta eficaz y de alto rendimiento para clasificar situaciones en función de los datos obtenidos. Sin embargo, vamos más allá de un simple sistema para que los agentes seleccionen acciones.
Escenarios
Analizamos un sistema de árbol de decisiones que utilizó condiciones y acciones creadas previamente. La persona que diseña la IA puede organizar el árbol como quiera, pero aún tiene que confiar en el codificador que lo programó todo. ¿Qué pasaría si pudiéramos darle al diseñador las herramientas para crear sus propias condiciones o acciones?
Para que el programador no tenga que escribir código para las condiciones Is Ball Left Of Paddle y Is Ball Right Of Paddle, puede crear un sistema en el que el diseñador escribirá condiciones para verificar estos valores. Entonces los datos del árbol de decisión se verán así:
Esto es esencialmente lo mismo que en la primera tabla, pero las soluciones dentro de sí mismas tienen su propio código, un poco como la parte condicional de una declaración if. En el lado del código, esto se leería en la segunda columna de los nodos de decisión, pero en lugar de buscar una condición específica para ejecutar (Is Ball Left Of Paddle), evalúa la expresión condicional y devuelve verdadero o falso en consecuencia. Esto se hace utilizando el lenguaje de programación Lua o Angelscript. Utilizándolos, un desarrollador puede tomar objetos de su juego (pelota y paleta) y crear variables que estarán disponibles en el script (ball.position). Además, el lenguaje de programación es más sencillo que C++. No requiere una etapa de compilación completa, por lo que es ideal para ajustar rápidamente la lógica del juego y permite a los "no codificadores" crear ellos mismos las funciones necesarias.
En el ejemplo anterior, el lenguaje de secuencias de comandos se usa solo para evaluar la expresión condicional, pero también se puede usar para acciones. Por ejemplo, los datos Move Paddle Right podrían convertirse en una declaración de script (ball.position.x += 10). Para que la acción también quede definida en el script, sin necesidad de programar Move Paddle Right.
Puede ir aún más lejos y escribir todo el árbol de decisión en un lenguaje de programación. Este será código en forma de declaraciones condicionales codificadas, pero estarán ubicadas en archivos de script externos, es decir, se pueden cambiar sin tener que volver a compilar todo el programa. A menudo puedes editar el archivo de secuencia de comandos durante el juego para probar rápidamente diferentes respuestas de la IA.
Respuesta al evento
Los ejemplos anteriores son perfectos para Pong. Ejecutan continuamente el ciclo Sentir/Pensar/Actuar y actúan en función del último estado del mundo. Pero en juegos más complejos es necesario reaccionar ante eventos individuales y no evaluar todo a la vez. El pong en este caso ya es un mal ejemplo. Elijamos otro.
Imagínese un juego de disparos en el que los enemigos permanecen inmóviles hasta que detectan al jugador, después de lo cual actúan dependiendo de su “especialización”: alguien correrá para “correr”, alguien atacará desde lejos. Sigue siendo un sistema reactivo básico: "si detectan a un jugador, haz algo", pero se puede dividir lógicamente en un evento de jugador visto y una reacción (selecciona una respuesta y ejecútala).
Esto nos devuelve al ciclo Sentir/Pensar/Actuar. Podemos codificar una parte de Sentido que verificará en cada cuadro si la IA ve al jugador. Si no, no pasa nada, pero si lo ve, se crea el evento Jugador visto. El código tendrá una sección separada que dice "cuando ocurra el evento Jugador visto, hazlo", donde está la respuesta que necesitas para abordar las partes Pensar y Actuar. Por lo tanto, configurarás reacciones al evento Player Seen: para el personaje "que corre", ChargeAndAttack, y para el francotirador, HideAndSnipe. Estas relaciones se pueden crear en el archivo de datos para editarlo rápidamente sin tener que volver a compilarlo. El lenguaje de scripting también se puede utilizar aquí.
Tomar decisiones difíciles
Aunque los sistemas de reacción simples son muy poderosos, hay muchas situaciones en las que no son suficientes. A veces es necesario tomar decisiones diferentes en función de lo que el agente esté haciendo actualmente, pero es difícil imaginar esto como una condición. A veces hay demasiadas condiciones para representarlas eficazmente en un árbol de decisiones o un guión. A veces es necesario evaluar de antemano cómo cambiará la situación antes de decidir el siguiente paso. Se necesitan enfoques más sofisticados para resolver estos problemas.
Máquina de estados finitos
La máquina de estados finitos o FSM (máquina de estados finitos) es una forma de decir que nuestro agente se encuentra actualmente en uno de varios estados posibles, y que puede pasar de un estado a otro. Hay un cierto número de estos estados, de ahí el nombre. El mejor ejemplo de la vida es un semáforo. Hay diferentes secuencias de luces en diferentes lugares, pero el principio es el mismo: cada estado representa algo (parar, caminar, etc.). Un semáforo se encuentra en un solo estado en un momento dado y pasa de uno a otro según reglas simples.
Es una historia similar con los NPC en los juegos. Por ejemplo, tomemos una guardia con los siguientes estados:
- Patrullando.
- Agresor.
- Huyendo.
Y estas condiciones para cambiar su estado:
- Si el guardia ve al enemigo, ataca.
- Si el guardia ataca pero ya no ve al enemigo, vuelve a patrullar.
- Si un guardia ataca pero resulta gravemente herido, huye.
También puedes escribir declaraciones if con una variable de estado de guardián y varias comprobaciones: si hay un enemigo cerca, cuál es el nivel de salud del NPC, etc. Agreguemos algunos estados más:
- Ociosidad - entre patrullas.
- Buscando: cuando el enemigo detectado ha desaparecido.
- Encontrar ayuda: cuando se detecta un enemigo, pero es demasiado fuerte para luchar solo.
La elección para cada uno de ellos es limitada; por ejemplo, el guardia no irá a buscar un enemigo oculto si tiene poca salud.
Después de todo, hay una lista enorme de "si" , Eso " puede volverse demasiado engorroso, por lo que debemos formalizar un método que nos permita tener en cuenta los estados y las transiciones entre estados. Para hacer esto, tenemos en cuenta todos los estados, y debajo de cada estado anotamos en una lista todas las transiciones a otros estados, junto con las condiciones necesarias para ellas.
Esta es una tabla de transición de estados: una forma integral de representar FSM. Dibujemos un diagrama y obtengamos una descripción completa de cómo cambia el comportamiento de los NPC.
El diagrama refleja la esencia de la toma de decisiones de este agente en función de la situación actual. Además, cada flecha muestra una transición entre estados si la condición al lado es verdadera.
En cada actualización verificamos el estado actual del agente, revisamos la lista de transiciones y, si se cumplen las condiciones para la transición, acepta el nuevo estado. Por ejemplo, cada cuadro verifica si el temporizador de 10 segundos ha expirado y, de ser así, el guardia pasa del estado Inactivo al estado Patrullando. De la misma manera, el estado de Ataque verifica la salud del agente; si es baja, pasa al estado de Huida.
Se trata de manejar las transiciones entre estados, pero ¿qué pasa con el comportamiento asociado con los propios estados? En términos de implementar el comportamiento real para un estado particular, normalmente existen dos tipos de "gancho" donde asignamos acciones al FSM:
- Acciones que realizamos periódicamente para el estado actual.
- Las acciones que tomamos al pasar de un estado a otro.
Ejemplos para el primer tipo. El estado Patrullando moverá al agente a lo largo de la ruta de patrulla en cada cuadro. El estado de ataque intentará iniciar un ataque en cada cuadro o realizar la transición a un estado donde esto sea posible.
Para el segundo tipo, considere la transición “si el enemigo es visible y el enemigo es demasiado fuerte, entonces vaya al estado Buscando ayuda. El agente debe elegir dónde acudir en busca de ayuda y almacenar esta información para que el estado de Búsqueda de ayuda sepa adónde ir. Una vez que encuentra ayuda, el agente vuelve al estado de Ataque. En este punto, querrá informarle al aliado sobre la amenaza, por lo que puede ocurrir la acción NotifyFriendOfThreat.
Una vez más, podemos mirar este sistema a través de la lente del ciclo Sentir/Pensar/Actuar. El sentido está incorporado en los datos utilizados por la lógica de transición. Piense: transiciones disponibles en cada estado. Y el acto se lleva a cabo mediante acciones realizadas periódicamente dentro de un estado o en las transiciones entre estados.
A veces, sondear continuamente las condiciones de transición puede resultar costoso. Por ejemplo, si cada agente realiza cálculos complejos en cada cuadro para determinar si puede ver a los enemigos y comprender si puede pasar del estado de patrulla al estado de ataque, esto requerirá mucho tiempo de CPU.
Los cambios importantes en el estado del mundo pueden considerarse como acontecimientos que se procesarán a medida que ocurran. En lugar de que el FSM verifique la condición de transición "¿puede mi agente ver al jugador?" en cada cuadro, se puede configurar un sistema separado para verificar con menos frecuencia (por ejemplo, 5 veces por segundo). Y el resultado es emitir Jugador visto cuando se pasa la verificación.
Esto se pasa al FSM, que ahora debería ir a la condición de evento recibido de jugador visto y responder en consecuencia. El comportamiento resultante es el mismo excepto por un retraso casi imperceptible antes de responder. Pero el rendimiento ha mejorado como resultado de separar la parte Sense en una parte separada del programa.
Máquina jerárquica de estados finitos
Sin embargo, trabajar con FSM de gran tamaño no siempre resulta conveniente. Si queremos expandir el estado de ataque para separar el ataque cuerpo a cuerpo y el ataque a distancia, tendremos que cambiar las transiciones de todos los demás estados que conducen al estado de ataque (actual y futuro).
Probablemente hayas notado que en nuestro ejemplo hay muchas transiciones duplicadas. La mayoría de las transiciones en el estado Inactivo son idénticas a las transiciones en el estado Patrullando. Sería bueno no repetirnos, especialmente si añadimos más estados similares. Tiene sentido agrupar los estados de ralentí y patrullaje bajo la etiqueta general de "no combate", donde sólo hay un conjunto común de transiciones a estados de combate. Si pensamos en esta etiqueta como un estado, entonces Ralentí y Patrullar se convierten en subestados. Un ejemplo del uso de una tabla de transición separada para un nuevo subestado sin combate:
Estados principales:
Estado fuera de combate:
Y en forma de diagrama:
Es el mismo sistema, pero con un nuevo estado sin combate que incluye ralentí y patrullaje. Con cada estado que contiene un FSM con subestados (y estos subestados, a su vez, contienen sus propios FSM, y así sucesivamente durante el tiempo que sea necesario), obtenemos una Máquina Jerárquica de Estados Finitos o HFSM (máquina jerárquica de estados finitos). Al agrupar el estado que no es de combate, eliminamos un montón de transiciones redundantes. Podemos hacer lo mismo con cualquier estado nuevo con transiciones comunes. Por ejemplo, si en el futuro expandimos el estado Ataque a los estados Ataque cuerpo a cuerpo y Ataque con misiles, serán subestados que realizarán una transición entre sí según la distancia al enemigo y la disponibilidad de munición. Como resultado, los comportamientos y subcomportamientos complejos se pueden representar con un mínimo de transiciones duplicadas.
árbol de comportamiento
Con HFSM se crean combinaciones complejas de comportamientos de forma sencilla. Sin embargo, existe una ligera dificultad en el sentido de que la toma de decisiones en forma de reglas de transición está estrechamente relacionada con el estado actual. Y en muchos juegos esto es exactamente lo que se necesita. Y el uso cuidadoso de la jerarquía estatal puede reducir el número de repeticiones de la transición. Pero a veces necesitas reglas que funcionen sin importar en qué estado te encuentres, o que se apliquen en casi cualquier estado. Por ejemplo, si la salud de un agente cae al 25%, querrás que huya sin importar si estaba en combate, inactivo o hablando; tendrás que agregar esta condición a cada estado. Y si su diseñador luego quiere cambiar el umbral de salud baja del 25% al 10%, deberá hacerlo nuevamente.
Idealmente, esta situación requiere un sistema en el que las decisiones sobre “en qué estado estar” estén fuera de los propios estados, para poder hacer cambios solo en un lugar y no tocar las condiciones de transición. Aquí aparecen árboles de comportamiento.
Hay varias formas de implementarlos, pero la esencia es más o menos la misma para todos y es similar a un árbol de decisión: el algoritmo comienza con un nodo "raíz" y el árbol contiene nodos que representan decisiones o acciones. Sin embargo, existen algunas diferencias clave:
- Los nodos ahora devuelven uno de tres valores: Correcto (si el trabajo se completó), Fallido (si no se puede iniciar) o En ejecución (si todavía se está ejecutando y no hay un resultado final).
- No hay más nodos de decisión para elegir entre dos alternativas. En cambio, son nodos Decoradores, que tienen un nodo hijo. Si tienen éxito, ejecutan su único nodo hijo.
- Los nodos que realizan acciones devuelven un valor en ejecución para representar las acciones que se están realizando.
Este pequeño conjunto de nodos se puede combinar para crear una gran cantidad de comportamientos complejos. Imaginemos la guardia HFSM del ejemplo anterior como un árbol de comportamiento:
Con esta estructura no debería haber una transición obvia de estados inactivos/patrullando a estados de ataque o cualquier otro estado. Si un enemigo es visible y la salud del personaje es baja, la ejecución se detendrá en el nodo Huyendo, independientemente del nodo que se estuviera ejecutando anteriormente: patrullando, inactivo, atacando o cualquier otro.
Los árboles de comportamiento son complejos: hay muchas maneras de componerlos y encontrar la combinación correcta de decoradores y nodos compuestos puede resultar un desafío. También surgen preguntas sobre la frecuencia con la que revisar el árbol: ¿queremos revisar cada parte del mismo o solo cuando una de las condiciones haya cambiado? ¿Cómo almacenamos el estado perteneciente a los nodos? ¿Cómo sabemos cuándo hemos estado inactivo durante 10 segundos o cómo sabemos qué nodos se ejecutaron la última vez para poder procesar la secuencia correctamente?
Por eso hay muchas implementaciones. Por ejemplo, algunos sistemas han reemplazado los nodos decoradores con decoradores en línea. Reevalúan el árbol cuando cambian las condiciones del decorador, ayudan a unir nodos y proporcionan actualizaciones periódicas.
Sistema basado en servicios públicos
Algunos juegos tienen muchas mecánicas diferentes. Es deseable que reciban todos los beneficios de reglas de transición simples y generales, pero no necesariamente en forma de un árbol completo de comportamiento. En lugar de tener un conjunto claro de opciones o un árbol de posibles acciones, es más fácil examinar todas las acciones y elegir la más adecuada en cada momento.
El sistema basado en utilidades ayudará precisamente con esto. Este es un sistema donde el agente tiene una variedad de acciones y elige cuáles realizar en función de la utilidad relativa de cada una. Donde la utilidad es una medida arbitraria de qué tan importante o deseable es para el agente realizar esta acción.
La utilidad calculada de una acción basada en el estado y el entorno actuales, el agente puede verificar y seleccionar el otro estado más apropiado en cualquier momento. Esto es similar a FSM, excepto que las transiciones están determinadas por una estimación para cada estado potencial, incluido el actual. Tenga en cuenta que elegimos la acción más útil para seguir adelante (o quedarnos si ya la hemos completado). Para obtener más variedad, esta podría ser una selección equilibrada pero aleatoria de una lista pequeña.
El sistema asigna un rango arbitrario de valores de utilidad, por ejemplo, de 0 (completamente indeseable) a 100 (completamente deseable). Cada acción tiene una serie de parámetros que afectan al cálculo de este valor. Volviendo a nuestro ejemplo de guardián:
Las transiciones entre acciones son ambiguas: cualquier estado puede suceder a cualquier otro. Las prioridades de acción se encuentran en los valores de utilidad devueltos. Si un enemigo es visible, y ese enemigo es fuerte, y la salud del personaje es baja, entonces tanto Huir como Encontrar ayuda devolverán valores altos distintos de cero. En este caso, FindingHelp siempre será mayor. Asimismo, las actividades que no son de combate nunca devuelven más de 50, por lo que siempre serán inferiores a las de combate. Debe tener esto en cuenta al crear acciones y calcular su utilidad.
En nuestro ejemplo, las acciones devuelven un valor constante fijo o uno de dos valores fijos. Un sistema más realista arrojaría una estimación a partir de un rango continuo de valores. Por ejemplo, la acción de Huir devuelve valores de utilidad más altos si la salud del agente es baja, y la acción de Atacar devuelve valores de utilidad más bajos si el enemigo es demasiado fuerte. Debido a esto, la acción de Huir tiene prioridad sobre Atacar en cualquier situación en la que el agente sienta que no tiene suficiente salud para derrotar al enemigo. Esto permite priorizar las acciones en función de cualquier número de criterios, lo que hace que este enfoque sea más flexible y variable que un árbol de comportamiento o FSM.
Cada acción tiene muchas condiciones para el cálculo del programa. Pueden escribirse en lenguaje de programación o como una serie de fórmulas matemáticas. Los Sims, que simula la rutina diaria de un personaje, añade una capa adicional de cálculo: el agente recibe una serie de "motivaciones" que influyen en las calificaciones de utilidad. Si un personaje tiene hambre, tendrá aún más hambre con el tiempo y el valor de utilidad de la acción EatFood aumentará hasta que el personaje la realice, reduciendo el nivel de hambre y devolviendo el valor de EatFood a cero.
La idea de seleccionar acciones basadas en un sistema de calificación es bastante simple, por lo que un sistema basado en utilidades puede usarse como parte de los procesos de toma de decisiones de IA, en lugar de como un reemplazo completo de ellos. El árbol de decisión puede solicitar una calificación de utilidad de dos nodos secundarios y seleccionar el más alto. De manera similar, un árbol de comportamiento puede tener un nodo de Utilidad compuesto para evaluar la utilidad de las acciones y decidir qué hijo ejecutar.
Movimiento y navegación
En los ejemplos anteriores teníamos una plataforma que movíamos hacia la izquierda o hacia la derecha y un guardia que patrullaba o atacaba. Pero, ¿cómo manejamos exactamente el movimiento de agentes durante un período de tiempo? ¿Cómo establecemos la velocidad, cómo evitamos obstáculos y cómo planificamos una ruta cuando llegar a un destino es más difícil que simplemente moverse en línea recta? Miremos esto.
Управление
En la etapa inicial, asumiremos que cada agente tiene un valor de velocidad, que incluye qué tan rápido se mueve y en qué dirección. Se puede medir en metros por segundo, kilómetros por hora, píxeles por segundo, etc. Recordando el ciclo Sentir/Pensar/Actuar, podemos imaginar que la parte Pensar selecciona una velocidad y la parte Actuar aplica esa velocidad al agente. Normalmente los juegos tienen un sistema de física que hace esta tarea por ti, aprendiendo el valor de velocidad de cada objeto y ajustándolo. Por lo tanto, puedes dejar a la IA con una tarea: decidir qué velocidad debe tener el agente. Si sabe dónde debe estar el agente, debe moverlo en la dirección correcta a una velocidad determinada. Una ecuación muy trivial:
viaje_deseado = posición_destino – posición_agente
Imagina un mundo 2D. El agente está en el punto (-2, -2), el destino está en algún lugar del noreste en el punto (30, 20) y el camino requerido para que el agente llegue allí es (32, 22). Digamos que estas posiciones se miden en metros: si tomamos la velocidad del agente como 5 metros por segundo, escalaremos nuestro vector de desplazamiento y obtendremos una velocidad de aproximadamente (4.12, 2.83). Con estos parámetros, el agente llegaría a su destino en casi 8 segundos.
Puedes recalcular los valores en cualquier momento. Si el agente estuviera a medio camino del objetivo, el movimiento sería la mitad de la longitud, pero como la velocidad máxima del agente es 5 m/s (lo decidimos arriba), la velocidad será la misma. Esto también funciona para objetivos en movimiento, lo que permite al agente realizar pequeños cambios a medida que se mueven.
Pero queremos más variación; por ejemplo, aumentar lentamente la velocidad para simular que un personaje pasa de estar de pie a correr. Lo mismo se puede hacer al final antes de parar. Estas características se conocen como comportamientos de dirección, cada uno de los cuales tiene nombres específicos: buscar, huir, llegar, etc. La idea es que se puedan aplicar fuerzas de aceleración a la velocidad del agente, basándose en la comparación de la posición del agente y la velocidad actual con el destino en para utilizar diferentes métodos para avanzar hacia la meta.
Cada comportamiento tiene un propósito ligeramente diferente. La búsqueda y la llegada son formas de trasladar a un agente a un destino. La evitación de obstáculos y la separación ajustan el movimiento del agente para evitar obstáculos en el camino hacia la meta. La alineación y la cohesión mantienen a los agentes avanzando juntos. Se puede sumar cualquier número de comportamientos de dirección diferentes para producir un único vector de trayectoria teniendo en cuenta todos los factores. Un agente que utiliza los comportamientos de Llegada, Separación y Evitación de Obstáculos para mantenerse alejado de las paredes y otros agentes. Este enfoque funciona bien en lugares abiertos sin detalles innecesarios.
En condiciones más difíciles, agregar diferentes comportamientos funciona peor; por ejemplo, un agente puede quedarse atrapado en una pared debido a un conflicto entre Llegada y Evitación de obstáculos. Por lo tanto, es necesario considerar opciones que sean más complejas que simplemente sumar todos los valores. La forma es la siguiente: en lugar de sumar los resultados de cada comportamiento, puedes considerar el movimiento en diferentes direcciones y elegir la mejor opción.
Sin embargo, en un entorno complejo con callejones sin salida y opciones sobre qué camino tomar, necesitaremos algo aún más avanzado.
Encontrando un camino
Los comportamientos de dirección son excelentes para movimientos simples en un área abierta (campo de fútbol o estadio) donde llegar de A a B es un camino recto con solo desvíos menores para sortear obstáculos. Para rutas complejas, necesitamos encontrar caminos, que es una forma de explorar el mundo y decidir una ruta a través de él.
La más sencilla es aplicar una cuadrícula a cada cuadrado al lado del agente y evaluar cuáles de ellos pueden moverse. Si uno de ellos es un destino, entonces sigue la ruta desde cada casilla hasta la anterior hasta llegar al inicio. Esta es la ruta. De lo contrario, repite el proceso con otros cuadrados cercanos hasta que encuentres tu destino o te quedes sin cuadrados (lo que significa que no hay ruta posible). Esto es lo que formalmente se conoce como búsqueda en amplitud o BFS (algoritmo de búsqueda en amplitud). A cada paso mira en todas direcciones (de ahí amplitud, "ancho"). El espacio de búsqueda es como un frente de onda que se mueve hasta alcanzar la ubicación deseada: el espacio de búsqueda se expande en cada paso hasta incluir el punto final, después de lo cual se puede rastrear hasta el principio.
Como resultado, recibirá una lista de plazas a lo largo de las cuales se elabora la ruta deseada. Esta es la ruta (de ahí, pathfinding): una lista de lugares que el agente visitará mientras sigue el destino.
Dado que conocemos la posición de cada cuadrado del mundo, podemos utilizar comportamientos de dirección para movernos a lo largo del camino: del nodo 1 al nodo 2, luego del nodo 2 al nodo 3, y así sucesivamente. La opción más sencilla es dirigirse hacia el centro del siguiente cuadrado, pero una opción aún mejor es detenerse en el medio del borde entre el cuadrado actual y el siguiente. Debido a esto, el agente podrá tomar atajos en curvas cerradas.
El algoritmo BFS también tiene desventajas: explora tantos cuadrados en la dirección "incorrecta" como en la dirección "correcta". Aquí es donde entra en juego un algoritmo más complejo llamado A* (A star). Funciona de la misma manera, pero en lugar de examinar ciegamente los cuadrados vecinos (luego vecinos de vecinos, luego vecinos de vecinos de vecinos, etc.), reúne los nodos en una lista y los clasifica de modo que el siguiente nodo examinado sea siempre el aquel que conduce a la ruta más corta. Los nodos se clasifican basándose en una heurística que tiene en cuenta dos cosas: el “costo” de una ruta hipotética al cuadrado deseado (incluido cualquier costo de viaje) y una estimación de qué tan lejos está ese cuadrado del destino (sesgando la búsqueda en el cuadro). dirección correcta).
Este ejemplo muestra que el agente explora un cuadrado a la vez, eligiendo cada vez el adyacente que sea más prometedor. La ruta resultante es la misma que BFS, pero se consideraron menos cuadrados en el proceso, lo que tiene un gran impacto en el rendimiento del juego.
Movimiento sin rejilla
Pero la mayoría de los juegos no están dispuestos en una cuadrícula y, a menudo, es imposible hacerlo sin sacrificar el realismo. Se necesitan compromisos. ¿Qué tamaño deben tener los cuadrados? Si son demasiado grandes, no podrán representar correctamente pequeños pasillos o curvas, si son demasiado pequeños, habrá demasiados cuadrados para buscar, lo que al final llevará mucho tiempo.
Lo primero que debemos entender es que una malla nos da una gráfica de nodos conectados. Los algoritmos A* y BFS en realidad funcionan en gráficos y no se preocupan en absoluto por nuestra malla. Podríamos colocar nodos en cualquier parte del mundo del juego: siempre que haya una conexión entre dos nodos conectados, así como entre los puntos inicial y final y al menos uno de los nodos, el algoritmo funcionará tan bien como antes. Esto a menudo se denomina sistema de puntos de ruta, ya que cada nodo representa una posición significativa en el mundo que puede ser parte de cualquier número de rutas hipotéticas.
Ejemplo 1: un nudo en cada cuadrado. La búsqueda comienza desde el nodo donde se encuentra el agente y finaliza en el nodo de la casilla deseada.
Ejemplo 2: un conjunto más pequeño de nodos (waypoints). La búsqueda comienza en la casilla del agente, pasa por el número requerido de nodos y luego continúa hasta el destino.
Este es un sistema completamente flexible y potente. Pero es necesario tener cuidado al decidir dónde y cómo colocar un punto de referencia; de lo contrario, es posible que los agentes simplemente no vean el punto más cercano y no puedan iniciar el camino. Sería más fácil si pudiéramos colocar automáticamente puntos de referencia basados en la geometría del mundo.
Aquí es donde aparece la malla de navegación o navmesh (malla de navegación). Suele ser una malla 2D de triángulos que se superpone a la geometría del mundo, dondequiera que se le permita caminar al agente. Cada uno de los triángulos de la malla se convierte en un nodo en el gráfico y tiene hasta tres triángulos adyacentes que se convierten en nodos adyacentes en el gráfico.
Esta imagen es un ejemplo del motor Unity: analizó la geometría del mundo y creó una malla de navegación (en la captura de pantalla en azul claro). Cada polígono en una malla de navegación es un área donde un agente puede permanecer o moverse de un polígono a otro. En este ejemplo, los polígonos son más pequeños que los pisos en los que están ubicados; esto se hace para tener en cuenta el tamaño del agente, que se extenderá más allá de su posición nominal.
Podemos buscar una ruta a través de esta malla, nuevamente usando el algoritmo A*. Esto nos dará una ruta casi perfecta en el mundo, que tiene en cuenta toda la geometría y no requiere nodos innecesarios ni creación de waypoints.
Pathfinding es un tema demasiado amplio para el cual una sección de un artículo no es suficiente. Si quieres estudiarlo con más detalle, esto te ayudará. .
planificación
Hemos aprendido con Pathfinding que a veces no basta con elegir una dirección y movernos: tenemos que elegir una ruta y dar algunos giros para llegar a nuestro destino deseado. Podemos generalizar esta idea: lograr una meta no es solo el siguiente paso, sino toda una secuencia donde a veces es necesario mirar hacia adelante varios pasos para saber cuál debería ser el primero. A esto se le llama planificación. Se puede considerar la búsqueda de caminos como una de varias extensiones de la planificación. En términos de nuestro ciclo Sentir/Pensar/Actuar, aquí es donde la parte Pensar planifica múltiples partes Actuar para el futuro.
Veamos el ejemplo del juego de mesa Magic: The Gathering. Vamos primero con el siguiente conjunto de cartas en nuestras manos:
- Pantano: Da 1 maná negro (carta de tierra).
- Bosque: da 1 maná verde (carta de tierra).
- Mago fugitivo: requiere 1 maná azul para convocar.
- Místico élfico: requiere 1 maná verde para convocar.
Ignoramos las tres cartas restantes para hacerlo más fácil. De acuerdo con las reglas, un jugador puede jugar 1 carta de tierra por turno, puede "tocar" esta carta para extraer maná de ella y luego lanzar hechizos (incluida la invocación de una criatura) de acuerdo con la cantidad de maná. En esta situación, el jugador humano sabe jugar Bosque, utilizar 1 maná verde y luego invocar a Elvish Mystic. Pero, ¿cómo puede la IA del juego resolver esto?
Planificación sencilla
El enfoque trivial es probar cada acción por turno hasta que no queden acciones adecuadas. Al mirar las cartas, la IA ve qué puede jugar Swamp. Y lo juega. ¿Quedan otras acciones en este turno? No puede convocar ni a Elvish Mystic ni a Fugitive Wizard, ya que requieren maná verde y azul respectivamente para convocarlos, mientras que Swamp solo proporciona maná negro. Y ya no podrá jugar en Forest, porque ya jugó en Swamp. Así, la IA del juego siguió las reglas, pero lo hizo mal. Puede ser mejorado.
En la planificación se puede encontrar una lista de acciones que llevan el juego al estado deseado. Así como cada cuadrado de un camino tenía vecinos (en Pathfinding), cada acción en un plan también tiene vecinos o sucesores. Podemos buscar estas acciones y acciones posteriores hasta llegar al estado deseado.
En nuestro ejemplo, el resultado deseado es "convocar a una criatura si es posible". Al inicio del turno, vemos sólo dos acciones posibles permitidas por las reglas del juego:
1. Juega a Swamp (resultado: Swamp en el juego)
2. Jugar al Bosque (resultado: Bosque en el juego)
Cada acción realizada puede dar lugar a otras acciones y cerrar otras, dependiendo nuevamente de las reglas del juego. Imagina que jugamos Pantano: esto eliminará Pantano como el siguiente paso (ya lo jugamos) y también eliminará Bosque (porque, de acuerdo con las reglas, puedes jugar una carta de tierra por turno). Después de esto, la IA agrega obtener 1 maná negro como siguiente paso porque no hay otras opciones. Si sigue adelante y elige Tap the Swamp, recibirá 1 unidad de maná negro y no podrá hacer nada con él.
1. Juega a Swamp (resultado: Swamp en el juego)
1.1 Pantano “Girado” (resultado: Pantano “girado”, +1 unidad de maná negro)
No hay acciones disponibles - FIN
2. Jugar al Bosque (resultado: Bosque en el juego)
La lista de acciones fue corta, llegamos a un callejón sin salida. Repetimos el proceso para el siguiente paso. Jugamos al Bosque, abrimos la acción "obtener 1 maná verde", que a su vez abrirá la tercera acción: convocar a Elvish Mystic.
1. Juega a Swamp (resultado: Swamp en el juego)
1.1 Pantano “Girado” (resultado: Pantano “girado”, +1 unidad de maná negro)
No hay acciones disponibles - FIN
2. Jugar al Bosque (resultado: Bosque en el juego)
2.1 Bosque "Girado" (resultado: Bosque "girado", +1 unidad de maná verde)
2.1.1 Invocar a Elvish Mystic (resultado: Elvish Mystic en juego, -1 maná verde)
No hay acciones disponibles - FIN
Finalmente, exploramos todas las acciones posibles y encontramos un plan que convoca a una criatura.
Este es un ejemplo muy simplificado. Es aconsejable elegir el mejor plan posible, en lugar de cualquier plan que cumpla algunos criterios. Generalmente es posible evaluar planes potenciales en función del resultado o beneficio general de su implementación. Puedes conseguir 1 punto por jugar una carta de tierra y 3 puntos por invocar una criatura. Jugar a Swamp sería un plan de 1 punto. Y jugar Bosque → Toca el bosque → convocar a Elvish Mystic te dará inmediatamente 4 puntos.
Así funciona la planificación en Magic: The Gathering, pero la misma lógica se aplica en otras situaciones. Por ejemplo, mover un peón para dejar espacio para que el alfil se mueva en el ajedrez. O cúbrete detrás de una pared para disparar de forma segura en XCOM como este. En general, entiendes la idea.
Planificación mejorada
A veces hay demasiadas acciones potenciales como para considerar todas las opciones posibles. Volviendo al ejemplo de Magic: The Gathering: digamos que en el juego y en tu mano hay varias cartas de tierra y criatura; el número de posibles combinaciones de movimientos puede ser de decenas. Hay varias soluciones al problema.
El primer método es el encadenamiento hacia atrás. En lugar de probar todas las combinaciones, es mejor empezar por el resultado final e intentar buscar una ruta directa. En lugar de ir de la raíz del árbol a una hoja específica, nos movemos en la dirección opuesta: de la hoja a la raíz. Este método es más fácil y rápido.
Si el enemigo tiene 1 salud, puedes encontrar el plan "infligir 1 o más daño". Para lograrlo se deben cumplir una serie de condiciones:
1. El daño puede ser causado por un hechizo; debe estar disponible.
2. Para lanzar un hechizo, necesitas maná.
3. Para obtener maná, debes jugar una carta de tierra.
4. Para jugar una carta de tierra, debes tenerla en tu mano.
Otra forma es la búsqueda "mejor primero". En lugar de probar todos los caminos, elegimos el más adecuado. En la mayoría de los casos, este método ofrece el plan óptimo sin costes de búsqueda innecesarios. A* es una forma de mejor primera búsqueda: al examinar las rutas más prometedoras desde el principio, ya puede encontrar la mejor ruta sin tener que comprobar otras opciones.
Una opción de búsqueda interesante y cada vez más popular es Monte Carlo Tree Search. En lugar de adivinar qué planes son mejores que otros al elegir cada acción posterior, el algoritmo elige sucesores aleatorios en cada paso hasta llegar al final (cuando el plan resultó en la victoria o la derrota). Luego, el resultado final se utiliza para aumentar o disminuir el peso de las opciones anteriores. Al repetir este proceso varias veces seguidas, el algoritmo da una buena estimación de cuál es el mejor siguiente movimiento, incluso si la situación cambia (si el enemigo toma medidas para interferir con el jugador).
Ninguna historia sobre la planificación en juegos estaría completa sin la Planificación de acción orientada a objetivos o GOAP (planificación de acción orientada a objetivos). Este es un método ampliamente utilizado y discutido, pero aparte de algunos detalles distintivos, es esencialmente el método de encadenamiento hacia atrás del que hablamos anteriormente. Si el objetivo era "destruir al jugador" y el jugador está a cubierto, el plan podría ser: destruir con una granada → conseguirla → tirarla.
Suele haber varios objetivos, cada uno con su propia prioridad. Si no se puede completar el objetivo de mayor prioridad (ninguna combinación de acciones crea un plan de "matar al jugador" porque el jugador no es visible), la IA recurrirá a objetivos de menor prioridad.
Formación y adaptación
Ya hemos dicho que la IA de los juegos no suele utilizar el aprendizaje automático porque no es adecuada para gestionar agentes en tiempo real. Pero esto no significa que no se pueda pedir prestado algo de esta zona. Queremos un oponente en un shooter del que podamos aprender algo. Por ejemplo, infórmate sobre las mejores posiciones en el mapa. O un oponente en un juego de lucha que bloquearía los movimientos combinados que usa con frecuencia el jugador, motivándolo a usar otros. Por tanto, el aprendizaje automático puede resultar muy útil en tales situaciones.
Estadísticas y probabilidades
Antes de entrar en ejemplos complejos, veamos hasta dónde podemos llegar tomando algunas medidas simples y usándolas para tomar decisiones. Por ejemplo, estrategia en tiempo real: ¿cómo determinamos si un jugador puede lanzar un ataque en los primeros minutos del juego y qué defensa preparar contra esto? Podemos estudiar las experiencias pasadas de un jugador para comprender cuáles podrían ser sus reacciones futuras. Para empezar, no tenemos esos datos sin procesar, pero podemos recopilarlos: cada vez que la IA juega contra un humano, puede registrar el momento del primer ataque. Tras unas cuantas sesiones obtendremos una media del tiempo que tardará el jugador en atacar en el futuro.
También hay un problema con los valores promedio: si un jugador se apresuró 20 veces y jugó lentamente 20 veces, entonces los valores requeridos estarán en algún punto intermedio, y esto no nos dará nada útil. Una solución es limitar los datos de entrada: se pueden tener en cuenta las últimas 20 piezas.
Se utiliza un enfoque similar al estimar la probabilidad de ciertas acciones asumiendo que las preferencias pasadas del jugador serán las mismas en el futuro. Si un jugador nos ataca cinco veces con bola de fuego, dos veces con rayo y una vez cuerpo a cuerpo, es obvio que prefiere bola de fuego. Extrapolemos y veamos la probabilidad de usar diferentes armas: bola de fuego=62,5%, rayo=25% y cuerpo a cuerpo=12,5%. La IA de nuestro juego necesita prepararse para protegerse del fuego.
Otro método interesante es utilizar el clasificador Naive Bayes para estudiar grandes cantidades de datos de entrada y clasificar la situación para que la IA reaccione de la forma deseada. Los clasificadores bayesianos son más conocidos por su uso en filtros de spam de correo electrónico. Allí examinan las palabras, las comparan con dónde han aparecido antes (en spam o no) y sacan conclusiones sobre los correos electrónicos entrantes. Podemos hacer lo mismo incluso con menos entradas. Basado en toda la información útil que ve la IA (como qué unidades enemigas se crean, qué hechizos usan o qué tecnologías investigaron) y el resultado final (guerra o paz, apresurarse o defenderse, etc.) - elegiremos el comportamiento de IA deseado.
Todos estos métodos de entrenamiento son suficientes, pero es recomendable utilizarlos basándose en datos de pruebas. La IA aprenderá a adaptarse a las diferentes estrategias que hayan utilizado tus expertos. La IA que se adapta al jugador después del lanzamiento puede volverse demasiado predecible o demasiado difícil de derrotar.
Adaptación basada en valores
Dado el contenido de nuestro mundo de juego y las reglas, podemos cambiar el conjunto de valores que influyen en la toma de decisiones, en lugar de simplemente utilizar los datos de entrada. Nosotros hacemos esto:
- Deje que la IA recopile datos sobre el estado del mundo y eventos clave durante el juego (como se muestra arriba).
- Cambiemos algunos valores importantes según estos datos.
- Implementamos nuestras decisiones en base al procesamiento o evaluación de estos valores.
Por ejemplo, un agente tiene varias salas para elegir en un mapa de disparos en primera persona. Cada habitación tiene su propio valor, que determina qué tan deseable es visitarla. La IA elige aleatoriamente a qué habitación ir en función del valor. Luego, el agente recuerda en qué habitación fue asesinado y reduce su valor (la probabilidad de que regrese allí). Lo mismo ocurre en la situación inversa: si el agente destruye a muchos oponentes, el valor de la habitación aumenta.
modelo de markov
¿Qué pasaría si usáramos los datos recopilados para hacer predicciones? Si recordamos cada habitación en la que vemos a un jugador durante un cierto período de tiempo, predeciremos a qué habitación podría ir el jugador. Al rastrear y registrar los movimientos del jugador a través de las habitaciones (valores), podemos predecirlos.
Tomemos tres habitaciones: roja, verde y azul. Y también las observaciones que registramos mientras veíamos la sesión de juego:
El número de observaciones en cada habitación es casi igual: todavía no sabemos dónde hacer un buen lugar para una emboscada. La recopilación de estadísticas también se complica por la reaparición de los jugadores, que aparecen de manera uniforme en todo el mapa. Pero los datos sobre la siguiente habitación a la que entran después de aparecer en el mapa ya son útiles.
Se puede ver que la sala verde les conviene a los jugadores: la mayoría de la gente pasa de la sala roja a ella, y el 50% de los cuales permanecen allí. La habitación azul, por el contrario, no es popular, casi nadie va a ella y, si lo hace, no se queda mucho tiempo.
Pero los datos nos dicen algo más importante: cuando un jugador está en una sala azul, la siguiente sala en la que lo veamos será roja, no verde. Aunque la sala verde es más popular que la sala roja, la situación cambia si el jugador está en la sala azul. El siguiente estado (es decir, la sala a la que irá el jugador) depende del estado anterior (es decir, la sala en la que se encuentra actualmente el jugador). Debido a que exploramos las dependencias, haremos predicciones más precisas que si simplemente contáramos las observaciones de forma independiente.
Predecir un estado futuro basándose en datos de un estado pasado se denomina modelo de Markov, y estos ejemplos (con habitaciones) se denominan cadenas de Markov. Dado que los patrones representan la probabilidad de cambios entre estados sucesivos, se muestran visualmente como FSM con una probabilidad alrededor de cada transición. Anteriormente, usábamos FSM para representar el estado de comportamiento en el que se encontraba un agente, pero este concepto se extiende a cualquier estado, ya sea que esté asociado con el agente o no. En este caso, los estados representan la habitación que ocupa el agente:
Esta es una forma sencilla de representar la probabilidad relativa de cambios de estado, lo que le da a la IA cierta capacidad para predecir el siguiente estado. Puedes anticipar varios pasos por delante.
Si un jugador está en la sala verde, hay un 50% de posibilidades de que permanezca allí la próxima vez que sea observado. Pero, ¿cuáles son las posibilidades de que siga allí incluso después? No solo existe la posibilidad de que el jugador permanezca en la sala verde después de dos observaciones, sino que también existe la posibilidad de que se haya ido y haya regresado. Aquí tenéis la nueva tabla teniendo en cuenta los nuevos datos:
Muestra que la probabilidad de ver al jugador en la sala verde después de dos observaciones será igual al 51% - 21% de que será de la sala roja, 5% de que el jugador visitará la sala azul entre ellos, y 25% que el jugador no saldrá de la sala verde.
La tabla es simplemente una herramienta visual: el procedimiento sólo requiere multiplicar las probabilidades en cada paso. Esto significa que puedes mirar hacia el futuro con una advertencia: asumimos que la posibilidad de entrar en una habitación depende completamente de la habitación actual. Esto se llama propiedad de Markov: el estado futuro depende sólo del presente. Pero esto no es XNUMX% exacto. Los jugadores pueden cambiar sus decisiones dependiendo de otros factores: nivel de salud o cantidad de munición. Como no registramos estos valores, nuestros pronósticos serán menos precisos.
N-gramos
¿Qué pasa con el ejemplo de un juego de lucha y la predicción de los movimientos combinados del jugador? ¡Lo mismo! Pero en lugar de un estado o evento, examinaremos todas las secuencias que componen un ataque combinado.
Una forma de hacer esto es almacenar cada entrada (como patada, puñetazo o bloqueo) en un búfer y escribir todo el búfer como un evento. Entonces, el jugador presiona repetidamente Kick, Kick, Punch para usar el ataque SuperDeathFist, el sistema de IA almacena todas las entradas en un búfer y recuerda las últimas tres utilizadas en cada paso.
(Las líneas en negrita son cuando el jugador lanza el ataque SuperDeathFist).
La IA verá todas las opciones cuando el jugador seleccione Patada, seguida de otra Patada, y luego notará que la siguiente entrada siempre es Puñetazo. Esto permitirá al agente predecir el movimiento combinado de SuperDeathFist y bloquearlo si es posible.
Estas secuencias de eventos se denominan N-gramas, donde N es el número de elementos almacenados. En el ejemplo anterior era un 3 gramos (trigrama), lo que significa: las dos primeras entradas se utilizan para predecir la tercera. En consecuencia, en un peso de 5 gramos, las primeras cuatro entradas predicen la quinta y así sucesivamente.
El diseñador debe elegir cuidadosamente el tamaño de N-gramos. Una N más pequeña requiere menos memoria pero también almacena menos historial. Por ejemplo, un bigram de 2 gramos grabará Kick, Kick o Kick, Punch, pero no podrá almacenar Kick, Kick, Punch, por lo que la IA no responderá al combo SuperDeathFist.
Por otro lado, números mayores requieren más memoria y la IA será más difícil de entrenar ya que habrá muchas más opciones posibles. Si tuvieras tres entradas posibles: patada, puñetazo o bloqueo, y usáramos 10 gramos, serían alrededor de 60 mil opciones diferentes.
El modelo de bigrama es una cadena de Markov simple: cada par de estado pasado/estado actual es un bigrama y se puede predecir el segundo estado basándose en el primero. Los N-gramas de 3 gramos y más grandes también se pueden considerar como cadenas de Markov, donde todos los elementos (excepto el último del N-grama) juntos forman el primer estado y el último elemento el segundo. El ejemplo del juego de lucha muestra la posibilidad de pasar del estado Patada y Patada al estado Patada y Puñetazo. Al tratar múltiples entradas del historial de entrada como una sola unidad, esencialmente estamos transformando la secuencia de entrada en parte de todo el estado. Esto nos da la propiedad de Markov, que nos permite usar cadenas de Markov para predecir la siguiente entrada y adivinar qué movimiento combinado será el siguiente.
Conclusión
Hablamos de las herramientas y enfoques más comunes en el desarrollo de la inteligencia artificial. También analizamos las situaciones en las que es necesario utilizarlos y en las que resultan especialmente útiles.
Esto debería ser suficiente para comprender los conceptos básicos de la IA de los juegos. Pero, por supuesto, estos no son todos los métodos. Menos populares, pero no menos efectivos, incluyen:
- Algoritmos de optimización que incluyen escalada de colinas, descenso de gradientes y algoritmos genéticos.
- Algoritmos contradictorios de búsqueda/programación (poda minimax y alfa-beta)
- métodos de clasificación (perceptrones, redes neuronales y máquinas de vectores de soporte)
- Sistemas para procesar la percepción y la memoria de los agentes.
- enfoques arquitectónicos de la IA (sistemas híbridos, arquitecturas de subconjuntos y otras formas de superponer sistemas de IA)
- herramientas de animación (planificación y coordinación de movimientos)
- Factores de rendimiento (nivel de detalle, en cualquier momento y algoritmos de división de tiempo)
Recursos Relacionados:
1. GameDev.net tiene y .
2. contiene muchas presentaciones y artículos sobre una amplia gama de temas relacionados con el desarrollo de la IA para juegos.
3. Incluye temas de la Cumbre de IA de GDC, muchos de los cuales están disponibles de forma gratuita.
4. También se pueden encontrar materiales útiles en el sitio web. .
5. Tommy Thompson, investigador de inteligencia artificial y desarrollador de juegos, hace videos en YouTube con una explicación y estudio de la IA en juegos comerciales.
Libros relacionados:
1. La serie de libros Game AI Pro es una colección de artículos breves que explican cómo implementar funciones específicas o cómo resolver problemas específicos.
2. La serie AI Game Programming Wisdom es la predecesora de la serie Game AI Pro. Contiene métodos más antiguos, pero casi todos son relevantes incluso hoy en día.
3. Es uno de los textos básicos para todo aquel que quiera comprender el campo general de la inteligencia artificial. Este no es un libro sobre desarrollo de juegos: enseña los conceptos básicos de la IA.
Fuente: habr.com