Algoritmos para estrategia en tiempo real wargame AI

Primero debes apuntar a hacer tu juego basado en turnos en algún nivel para la IA (es decir, de alguna manera puedes modelarlo basado en turnos incluso si no está completamente basado en 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 a la IA se le permite hacer trampa y conocer cada movimiento de su oponente (haciéndolo así más fuerte) o si debe 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, que genere 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 cosa es, la función de costo será muy influenciada por lo que exactamente define el estado a ser. Cuanta más información codifique en el estado, mejor equilibrada será su IA, pero más difícil será será para que realice, 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 se puede abordar con cualquier algoritmo de su elección.

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

1. Los algoritmos evolutivos pueden funcionar bien si pones suficiente esfuerzo en ellos, pero lo harán agregue una capa de complejidad que creará espacio para errores, entre otras cosas que pueden salir mal. También requerirán cantidades extremas de ajuste de la función de acondicionamiento físico, etc. No tengo mucha experiencia trabajando con estos, pero si son algo así como redes neuronales (que creo que lo son ya que ambas son heurísticas inspiradas en modelos biológicos), rápidamente encontrará que son volubles y lejos de ser consistentes. Lo más importante, dudo que agreguen beneficios sobre la opción que describo en 3.

2. Con la función de costo y el estado definido, técnicamente sería posible aplicar gradiente decente (con la suposición de que la función de estado es diferenciable y el dominio de las variables de estado son continuas) sin embargo, esto probablemente produciría resultados inferiores, ya que la mayor debilidad del descenso del gradiente se atasca en los mínimos locales. Para dar un ejemplo, este método sería propenso a algo como atacar al enemigo siempre lo antes 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 sabe mejor.

3. Esta opción sería mi más alta recomendada: recocido simulado. El recocido simulado (IMHO) tendría todas las ventajas de 1. sin la complejidad añadida mientras que es mucho más robusto que 2. En esencia, SA es solo un paseo aleatorio entre los estados. Así que además del costo y estados tendrá que definir una forma de transición aleatoria entre 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 which 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. La información sobre SA se puede encontrar aquí con un largo lista de implementaciones genéricas en la parte inferior.

3b. (Edit Added much later) SA y las técnicas que enumeré anteriormente son técnicas de IA generales y no realmente especializadas en IA para juegos. En general, cuanto más especializado sea el algoritmo, más posibilidades tendrá de mejorar su rendimiento. No Ver Teorema de Almuerzo Gratis 2. Otra extensión de 3 es algo llamado 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 anticuados 3, pero otros han sido actualizados4.

Independientemente del método que elija al final, va a ser muy importante para romper 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 su espacio de búsqueda de estado es exponencial en el número de estas variables.