algorithm - pocos - juegos de estrategia para pc online

Algoritmos para la estrategia en tiempo real juego de guerra IA (4)

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

Una unidad tiene varios puntos de acción que pueden gastarse en movimiento, atacar unidades enemigas o varias acciones especiales (por ejemplo, construir nuevas unidades). 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 de su alcance. Diferentes unidades tienen diferentes costos para diferentes acciones, etc.

Algunas notas adicionales:

La salida de la IA es un "comando" para cualquier unidad dada
Los puntos de acción se asignan al comienzo de un período de tiempo, pero se pueden gastar en cualquier punto dentro del período de tiempo (esto es para permitir juegos de multijugador en tiempo real). Por lo tanto, "no hacer nada y guardar puntos de acción para más adelante" es una táctica potencialmente válida (por ejemplo, una torreta que no puede moverse en espera de que un enemigo esté dentro del alcance de tiro)
El juego se está actualizando en tiempo real, pero la IA puede obtener una instantánea constante 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 estoy esperando un comportamiento "óptimo", solo algo que obviamente no es estúpido y ofrece una diversión / desafío razonable para jugar contra

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

Es una pregunta enorme, y las otras respuestas han señalado recursos sorprendentes para examinar.

He abordado este problema en el pasado y he encontrado que el enfoque del comportamiento simple de los comportamientos complejos y emergentes es demasiado difícil de manejar para el diseño humano a menos que se lo haya abordado de forma genética / evolutiva.

En vez de eso, terminé usando capas abstractas de IA, de manera similar a como los ejércitos trabajan en la vida real. Las unidades se agruparían con unidades cercanas del mismo tiempo en escuadrones, que se agruparán con escuadrones cercanos para crear un mini batallón de clases. Se podrían usar más capas aquí (batallones de grupo en una región, etc.), pero en última instancia en la parte superior está la IA estratégica de alto nivel.

Cada capa solo 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 emitido para una sola unidad es "Ir aquí" y "disparar a este objetivo". Los comandos de nivel superior emitidos a niveles superiores serían "asegurar esta ubicación", que ese nivel procesaría y emitiría los comandos apropiados a los niveles inferiores.

La IA maestra de nivel más alto es responsable de las decisiones estratégicas de la junta directiva, como "necesitamos más ____ unidades" o "deberíamos apuntar a avanzar hacia esta ubicación".

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

Esta pregunta es enorme en su alcance. Básicamente estás preguntando cómo escribir un juego de estrategia.

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

Primero, debe tratar de hacer que su juego se base en algún nivel para la IA (es decir, de alguna manera puede modelarlo por turnos incluso si no está completamente basado en turnos, en RTS puede ser capaz de dividir intervalos discretos de tiempo en turnos. ) Segundo, debes determinar con cuánta información debe trabajar la IA. Es decir, si se permite que la IA haga trampa y conozca cada movimiento de su oponente (por lo tanto, lo haga 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 estado peor para la computadora. Cuarto, usted necesita un generador de movimientos, generando todos los estados válidos a los que la IA puede hacer la transición desde un estado dado (esto puede ser homogéneo [independiente del estado] o heterogéneo [dependiente del estado].)

La cuestión es que la función de costo estará muy influenciada por lo que usted define exactamente como estado. Cuanta más información codifique en el estado, mejor equilibrada estará su IA, pero más difícil será para ella, 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 un estado y una función de costo, su problema se transforma en un problema general en IA que puede abordarse con cualquier algoritmo de su elección.

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

Los algoritmos evolutivos pueden funcionar bien si pones suficiente esfuerzo en ellos, pero agregarán una capa de complejidad que creará espacio para errores entre otras cosas que pueden salir mal. También requerirán cantidades extremas de ajustes de la función de aptitud, etc. No tengo mucha experiencia trabajando con estos, pero si se parecen a redes neuronales (que creo que son ya que ambas son heurísticas inspiradas en modelos biológicos), rápidamente Encuentra que son volubles y lejos de ser consistentes. Lo más importante es que dudo que agreguen algún beneficio sobre la opción que describo en 3.
Con la función de costo y el estado definidos, técnicamente sería posible que usted aplique 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 de pendiente de gradiente se está atascando en mínimos locales. Para dar un ejemplo, este método sería propenso a atacar al enemigo siempre lo antes posible, ya que existe una posibilidad diferente de aniquilarlo. Claramente, esto puede no ser un comportamiento deseable para un juego, sin embargo, el gradiente decente es un método codicioso y no se conoce mejor.
Esta opción sería la más recomendada: recocido simulado. El recocido simulado tendría (IMHO) todos los beneficios de 1. sin la complejidad agregada y mucho más robusto que 2. En esencia, SA es solo un paseo aleatorio entre los estados. Entonces, además del costo y los estados, tendrá que definir una manera de hacer una transición aleatoria entre los estados. SA tampoco es propenso a quedarse atascado en mínimos locales, mientras que produce muy buenos resultados de manera bastante consistente. El único ajuste requerido con SA sería el programa de enfriamiento, que decide qué tan rápido convergirá SA. La mayor ventaja de SA que encuentro es que es conceptualmente simple y produce resultados empíricos superiores a la mayoría de los otros métodos que he probado. La información sobre SA se puede encontrar here con una larga lista de implementaciones genéricas en la parte inferior.

3b. ( Edición agregada mucho más tarde ) SA y las técnicas que enumeré anteriormente son técnicas generales de inteligencia artificial y no están realmente especializadas en inteligencia artificial para juegos. En general, cuanto más especializado sea el algoritmo, más posibilidades tendrá de obtener mejores resultados. Ver No Teorema de almuerzo gratis 2 . Otra extensión de 3 es algo que se llama templado paralelo que mejora dramáticamente el rendimiento de SA al ayudarlo a evitar los óptimos locales. Algunos de los documentos originales sobre el templado paralelo son bastante antiguos, pero otros se han actualizado 4 .

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

Si lees a Russell y Norvig , encontrarás una gran cantidad de algoritmos para cada propósito, actualizados al estado actual de la técnica. Dicho esto, me sorprendió la cantidad de problemas que pueden abordarse con éxito mediante el uso de algoritmos bayesianos.

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

Aunque en algunos aspectos tal vez sea un chiflado, Stephen Wolfram ha demostrado que es posible programar un comportamiento notablemente complejo sobre la base de reglas muy simples . Él valientemente extrapola del Juego de la Vida a la física cuántica y al universo entero.

Del mismo modo, una gran cantidad de investigaciones sobre robots pequeños se centra en el comportamiento emergente o en la inteligencia de enjambres . Si bien la estrategia y la práctica militares clásicas se basan en gran medida en las jerarquías, creo que un ejército de luchadores completamente intrépidos e intrépidos (como se puede encontrar marchando en su computadora) podría ser notablemente efectivo si funciona como agrupaciones autoorganizadas.

Este enfoque probablemente encajaría un poco mejor con el modelo de concurrencia basado en actores de Erlang o Scala que con el STM de Clojure: Creo que la autoorganización y los actores irían muy bien juntos. Aún así, podría imaginar correr una lista de unidades en cada turno, y hacer que cada unidad evalúe solo un puñado de reglas muy simples para determinar su próxima acción. Me gustaría mucho saber si has intentado este enfoque, ¡y cómo te fue!

EDITAR

Algo más estaba en el fondo de mi mente, pero se me escapó de nuevo mientras escribía: creo que puede obtener resultados notables con este enfoque si lo combina con genetic programación genetic o evolutiva; es decir, deja que tus soldados de juguete virtual se peleen entre sí mientras duermes, deja que codifiquen sus estrategias y mezclen, combinen y muten su código para esas estrategias; y deja que un programa de arbitraje seleccione a los guerreros más exitosos.

He leído sobre algunos éxitos sorprendentes logrados con estas técnicas, con unidades que funcionan de una manera que nunca habríamos pensado. He escuchado que las IA que trabajan en estos principios tuvieron que ser intencionalmente para no frustrar a los oponentes humanos.