Algoritmos para el juego de estrategia en tiempo real AI

Question

Estoy diseñando un juego de estrategia en tiempo real en el que la IA será responsable de controlar un gran número de unidades (posiblemente más de 1000) en un gran mapa hexagonal.

Una unidad tiene una serie de puntos de acción que pueden gastarse en movimiento, atacando unidades enemigas o realizando diversas acciones especiales (por ejemplo, construyendo unidades nuevas). Por ejemplo, un tanque con 5 puntos de acción podría gastar 3 en movimiento y luego 2 en disparar a un enemigo dentro del alcance. Diferentes unidades tienen diferentes costos para diferentes acciones, etc.

algunas notas adicionales:

• La salida de la AI es un "comando" a cualquier unidad dada
• puntos de acción se asignan al comienzo de una período de tiempo, pero puede gastarse en cualquier punto dentro del período de tiempo (esto es para permitir juegos en tiempo real en modo multijugador). Por lo tanto, "no hacer nada y guardar los puntos de acción para más tarde" es una táctica potencialmente válida (por ejemplo, una torreta que no se puede mover esperando que un enemigo entre dentro del alcance)
• El juego se actualiza en tiempo real, pero la IA puede obtener un imagen consistente del estado del juego en cualquier momento (gracias a que el estado del juego es una de las estructuras de datos persistentes de Clojure)
• No espero un comportamiento "óptimo", simplemente algo que no es obviamente estúpido y proporciona una diversión/desafío razonable para jugar contra

¿Qué se puede recomendar en términos de algoritmos/enfoques específicos que permitan el equilibrio correcto entre eficiencia y comportamiento razonablemente inteligente?

Answer 1

Primero debes intentar hacer que tu juego gire en algún nivel para la IA (es decir, puedes modelarlo por turnos aunque no sea totalmente por turnos, en RTS puedes romper intervalos discretos de tiempo en turnos). En segundo lugar, debe determinar con cuánta información debe trabajar la IA. Es decir, si la IA puede engañar y conocer cada movimiento de su oponente (lo que lo hace más fuerte) o si debería saber menos o más. En tercer lugar, debe definir una función de costo de un estado. La idea es que un costo más alto significa un peor estado para la computadora. En cuarto lugar, necesita un generador de movimiento, generando todos los estados válidos a los que la IA puede pasar desde un estado dado (esto puede ser homogéneo [independiente del estado] o heterogéneo [dependiente del estado].)

El hecho es que la función de costo estará muy influenciada por lo que usted defina exactamente para el estado. Cuanta más información codifique en el estado, mejor será el equilibrio de su inteligencia artificial, pero será más difícil de realizar, ya que tendrá que buscar exponencialmente más por cada variable de estado adicional que incluya (en una búsqueda exhaustiva)

Si proporciona una definición de estado y una función de costo, su problema se transforma en un problema general de la inteligencia artificial que puede abordarse con cualquier algoritmo de su elección.

Aquí es un resumen de lo que creo que funcionaría bien:

1. algoritmos evolutivos pueden funcionar bien si se pone suficiente esfuerzo en ellos, pero van a añadir una capa de complejidad que va a crear espacio para errores entre otras cosas que pueden salir mal También requerirán ajustes extremos de la función de acondicionamiento físico, etc. No tengo mucha experiencia trabajando con estos, pero si se parecen a las redes neuronales (que creo que son, ya que ambas son heurísticas inspiradas en modelos biológicos), rápidamente descubren que son volubles y no son consistentes. Lo que es más importante, dudo que añadan ningún beneficio a la opción que describo en 3.

2. Con la función de costo y el estado definidos, técnicamente sería posible aplicar gradiente decente (suponiendo que la función de estado es diferenciable) y el dominio de las variables de estado es continuo), sin embargo, esto probablemente arrojaría resultados inferiores, ya que la mayor debilidad del descenso del gradiente es quedarse estancada en los mínimos locales. Para dar un ejemplo, este método sería propenso a algo así como atacar al enemigo siempre tan pronto como sea posible porque hay una posibilidad no nula de aniquilarlos. Claramente, esto puede no ser un comportamiento deseable para un juego, sin embargo, gradiente decente es un método codicioso y no lo sabe mejor.

3. Esta opción sería la más recomendada: el recocido simulado. El recocido simulado tendría (IMHO) todos los beneficios de 1. sin la complejidad añadida, mientras que es mucho más robusto que 2. En esencia, SA es solo una caminata aleatoria entre los estados. Entonces, además del costo y los estados, tendrá que definir una forma de transición aleatoria entre estados. SA tampoco es propenso a estar atascado en mínimos locales, mientras que produce muy buenos resultados de manera bastante consistente. El único ajuste requerido con SA sería el cronograma de enfriamiento, que decide qué tan rápido convergerá SA. La mayor ventaja de SA que encuentro es que es conceptualmente simple y produce resultados superiores empíricamente a la mayoría de los otros métodos que he probado. Se puede encontrar información sobre SA en here con una larga lista de implementaciones genéricas en la parte inferior.

3b. (Edit Added later later) SA y las técnicas que enumeré anteriormente son técnicas generales de IA y no están realmente especializadas para AI para juegos. En general, cuanto más especializado es el algoritmo, más posibilidades tiene de rendir mejor. Consulte el Teorema del almuerzo gratuito 2. Otra extensión de 3 es algo llamado temple paralelo, que mejora dramáticamente el rendimiento de SA al ayudarlo a evitar óptimas locales. Algunos de los documentos originales sobre templado paralelo son bastante anticuados 3, pero otros se han actualizado 4.

Independientemente del método que elijas al final, será muy importante descomponer tu problema en estados y una función de costos como dije anteriormente. Como regla general, comenzaría con 20-50 variables de estado ya que su espacio de búsqueda de estado es exponencial en el número de estas variables.

Answer 2

Esta pregunta es amplia. Básicamente estás preguntando cómo escribir un juego de estrategia.

Hay toneladas de libros y artículos en línea para este material. Recomiendo encarecidamente la serie Game Programming Wisdom y AI Game Programming Wisdom series. En particular, la Sección 6 del primer volumen de AI Game Programming Wisdom cubre la arquitectura general, la Sección 7 cubre arquitecturas de toma de decisiones, y la Sección 8 cubre arquitecturas para géneros específicos (8.2 hace el género RTS).

Answer 3

Si lee Russell and Norvig, encontrará una gran cantidad de algoritmos para cada propósito, actualizados prácticamente con el estado de la técnica actual. Dicho esto, me sorprendió ver cuántas clases diferentes de problemas se pueden abordar con éxito con los algoritmos bayesianos.

Sin embargo, en su caso, creo que sería una mala idea que cada unidad tenga su propia red de Petri o un motor de inferencia ... solo hay mucha CPU y memoria y tiempo disponible. Por lo tanto, un enfoque diferente:

Si bien de alguna manera tal vez un chiflado, Stephen Wolfram ha demostrado que es posible programar un comportamiento notablemente complejo sobre la base de very simple rules. Él valientemente extrapola desde el Game of Life a la física cuántica y al universo entero.

De forma similar, mucha investigación sobre robots pequeños se centra en emergent behavior o swarm intelligence. Mientras que el clásico military strategy y la práctica se basan fuertemente en jerarquías, creo que un ejército de luchadores completamente desinteresados ​​e intrépidos (como se puede encontrar marchando en su computadora) podría ser notablemente efectivo si opera como clusters autoorganizados.

Este enfoque sería probablemente ajustarse un poco mejor con Erlang o del modelo de concurrencia basado en los actores de Scala que con STM de Clojure: Creo que la auto-organización y actores irían juntos extremadamente bien. Aún así, podría imaginarme corriendo a través de una lista de unidades en cada turno, y haciendo que cada unidad evalúe solo un pequeño puñado de reglas muy simples para determinar su próxima acción. Me interesaría saber si has probado este enfoque y cómo te fue.

EDITAR

Otra cosa que estaba en el fondo de mi mente, pero que se coló de nuevo mientras estaba escribiendo: Creo que se pueden obtener resultados notables de este planteamiento si se combina con genetic o programación evolutiva ; es decir, deje que sus soldados de juguete virtuales luchen entre sí mientras duerme, permítales codificar sus estrategias y mezclar, combinar y mutar su código para esas estrategias; y deje que un programa de arbitraje seleccione a los guerreros más exitosos.

He leído sobre algunos éxitos sorprendentes obtenidos con estas técnicas, con las unidades que operan en formas que nunca se le ocurriría. He oído que las IA que trabajan en estos principios han tenido que ser embaucadas intencionalmente para no frustrar a los oponentes humanos.

Answer 4

Es una cuestión enorme, y las otras respuestas han señalado los recursos increíbles a considerar.

He tratado este problema en el pasado y encontré que el enfoque del comportamiento simple-comportamiento-manifiestos-complejo/emergente es demasiado difícil de manejar para el diseño humano a menos que se lo aborde genéticamente/evolutivamente.

que terminaron en lugar de utilizar capas abstractas de AI, similar a una forma ejércitos funcionan en la vida real. Las unidades se agrupan con unidades cercanas del mismo tiempo en escuadrones, que se agrupan con escuadrones cercanos para crear un mini batallón de géneros. Aquí se pueden usar más capas (batallones de grupos en una región, etc.), pero en última instancia, en la parte superior, está la IA estratégica de alto nivel.

Cada capa sólo puede emitir comandos a las capas directamente debajo de ella. La capa debajo de ella intentará ejecutar el comando con los recursos disponibles (es decir, las capas debajo de esa capa).

Un ejemplo de un comando enviado a una sola unidad es "Vaya aquí" y "disparar a este objetivo". Los comandos de nivel superior emitidos a niveles más altos serían "asegurar esta ubicación", que ese nivel procesaría y emitiría los comandos apropiados a los niveles inferiores.

El más alto nivel de maestría AI es responsable de las decisiones muy estratégico de la placa, como "necesitamos más unidades ____", o "hay que intentar avanzar hacia este lugar".

La analogía del ejército funciona aquí; comandantes y tenientes y cadena de mando.