¿Qué modelo se adapta mejor a la optimización para un juego de estrategia en tiempo real?

Question

Un artículo ha estado rondando últimamente discutiendo el uso de algoritmos genéticos para optimizar las "órdenes de compilación" en StarCraft II.

http://lbrandy.com/blog/2010/11/using-genetic-algorithms-to-find-starcraft-2-build-orders/

El estado inicial de un partido StarCraft es pre-determinado y constante. Y al igual que el ajedrez, las decisiones tomadas en esta etapa inicial del partido tienen consecuencias de larga data para la capacidad de un jugador de jugar en el medio y último juego. Por lo tanto, las diversas posibilidades de apertura u "órdenes de compilación" están bajo un intenso estudio y escrutinio. Hasta la circulación del artículo anterior, la creación de órdenes de construcción asistidas por computadora probablemente no era tan popular como lo ha sido recientemente.

Mi pregunta es ... ¿Es realmente un algoritmo genético la mejor manera de modelar órdenes de fabricación de optimización?

Una orden de compilación es una secuencia de acciones. Algunas acciones tienen requisitos previos como, "Necesitas construir B antes de poder crear el edificio C, pero puedes tener el edificio A en cualquier momento". Entonces, un cromosoma puede parecerse a AABAC.

Me pregunto si un algoritmo genético realmente es la mejor manera de abordar este problema. Aunque no estoy muy familiarizado con el tema, estoy teniendo dificultades para adaptar el concepto de genes a una estructura de datos que es una secuencia de acciones. Estas no son elecciones independientes que pueden mezclarse y combinarse como una cabeza y un pie. Entonces, ¿qué valor hay para cosas como la reproducción y el cruce?

Estoy pensando que cualquier ajedrez que use la IA sería más apropiado ya que la variedad de opciones en un momento dado podría verse como un árbol en cierto modo.

Answer 1

Como señaló TaslemGuy, los algoritmos genéticos no están garantizados para ser óptimos, aunque generalmente dan buenos resultados.

Para obtener resultados óptimos, debe buscar entre todas las combinaciones posibles de acciones hasta encontrar la ruta óptima a través de la representación arborescente. Sin embargo, hacer esto para StarCraft es difícil, ya que hay muchos caminos diferentes para alcanzar un objetivo. En el ajedrez mueves un peón de e2 a e4 y luego el oponente se mueve. En StarCraft puede mover una unidad al instante xo x + 1 o x + 10 o ...

Un motor de ajedrez puede ver muchos aspectos diferentes del tablero (por ejemplo, cuántas piezas tiene y cuántas el oponente tiene), para guiar su búsqueda. Puede ignorar la mayoría de las acciones disponibles si sabe que son estrictamente peores que otras.

Para un creador acumulación fin único momento en que realmente importa. ¿Es mejor construir otro dron para obtener minerales más rápido, o es más rápido iniciar ese grupo de desove de inmediato? No es tan sencillo como con el ajedrez.

Este tipo de decisiones suceden desde el principio, por lo que tendrá que buscar en cada alternativa para llegar a una conclusión antes de poder elegir la mejor, que tomará un tiempo largo. Si tuviera que escribir una acumulación fin optimizador de mí, probablemente me trato de formular una heurística que estima el bueno (cerrar la al estado meta) el estado actual es, al igual que los motores de ajedrez hacen:

Score = a*(Buildings_and_units_done/Buildings_and_units_required) - b*Time_elapsed - c*Minerals - d*Gas + e*Drone_count - f*Supply_left 

Este

trata de mantener el marcador empatado con el porcentaje de finalización, así como StarCraft conocimiento común (mantener sus Recursos baja, construir aviones no tripulados, no construya más oferta que necesita). Las variables de a a f necesitarían ajustes, por supuesto.

Después de obtener una heurística que pueda estimar el valor de una situación, usaría Best-first search o quizás IDDFS para buscar en el árbol de las posibilidades.

Editar:

he encontrado recientemente un paper que realmente describe construir optimización orden en StarCraft, en tiempo real, incluso. Los autores utilizan depth-first search con branch and bound y heurística que estiman la cantidad mínima de esfuerzo necesario para alcanzar la meta basada en el árbol de tecnología (por ejemplo zergling necesitas una piscina de desove) y el tiempo necesario para reunir los minerales necesarios.

Answer 2

Se han llevado a cabo algunas investigaciones utilizando el refuerzo jerárquico aprendiendo a construir un orden en capas de acciones que maximiza de manera eficiente una recompensa. No he encontrado mucho código para implementar la idea, pero hay algunos artículos que describen algoritmos basados ​​en MAXQ que se han utilizado para abordar explícitamente dominios de juegos de estrategia en tiempo real, como this y this.

Answer 3

El algoritmo genético puede ser, o puede no ser, la solución óptima o no óptima. Según la complejidad del algoritmo genético, cuánta mutación existe, las formas de combinación y cómo se interpretan los cromosomas del algoritmo genético.

Por lo tanto, dependiendo de cómo se implemente su IA, los algoritmos genéticos pueden ser los mejores.

Está buscando una ÚNICA manera de implementar algoritmos genéticos, olvidando la programación genética, el uso de las matemáticas, las funciones de orden superior, etc. Los algoritmos genéticos pueden ser EXTREMADAMENTE sofisticados, y mediante el uso de sistemas de combinación inteligentes para el mestizaje, extremadamente inteligente.
Por ejemplo, las redes neuronales se optimizan con algoritmos genéticos con bastante frecuencia.

---

Buscar "Genetic Programming." Es similar, pero usa estructuras de árbol en lugar de líneas de caracteres, lo que permite interacciones más complejas que se reproducen mejor. Para cosas más complejas, generalmente funcionan mejor.

Answer 4

Este algoritmo genético solo optimiza la estrategia para una parte muy específica del juego: el orden de las primeras acciones de compilación del juego. Y también tiene un objetivo muy específico: tener tantas cucarachas lo más rápido posible.

Los únicos aspectos que influyen en este sistema parece ser (no soy un jugador de StarCraft):

• tiempo de construcción de las distintas unidades y edificios
• unidades y edificios permitidos dadas las unidades y edificios disponibles tasa de regeneración
• Larva.

Este es un problema relativamente limitado y relativamente bien definido con un gran espacio de búsqueda. Como tal, es muy adecuado para algoritmos genéticos (y bastantes otros algoritmos de optimización en eso). Un gen completo es un conjunto específico de órdenes de compilación que termina en la séptima roach. Por lo que entiendo, puedes simplemente "jugar" este gen específico para ver qué tan rápido termina, para que tengas una prueba de aptitud física muy clara. También tiene algunas restricciones interesantes en el orden de compilación, por lo que puede combinar diferentes genes un poco más inteligentes que simplemente al azar.

Un algoritmo genético utilizado de esta manera es una muy buena herramienta para encontrar un orden de construcción más óptimo para la primera etapa de un juego de Starcraft. Debido a su naturaleza aleatoria, también es bueno para encontrar una estrategia sorprendente, que podría haber sido un objetivo adicional del autor.

Para utilizar un algoritmo genético como el algoritmo en un juego de estrategia en tiempo real, debe encontrar una manera de codificar las reacciones ante situaciones en lugar de simples órdenes de compilación antiguas. Esto también implica identificar correctamente situaciones que pueden ser una tarea difícil en sí misma. Entonces tendrías que dejar que estos genes jueguen miles de juegos de Starcraft, uno contra el otro y (posiblemente) contra humanos, seleccionando y combinando ganadores (o perdedores de mayor duración). Esta es también una buena aplicación de algoritmos genéticos, pero implica resolver algunos problemas muy difíciles incluso antes de llegar a la parte del algoritmo genético.

Answer 5

Aunque no estoy muy familiarizado con el tema, me está resultando difícil familiarizarme con el concepto de genes en una estructura de datos que es una secuencia de acciones. Estas no son elecciones independientes que pueden mezclarse y combinarse como una cabeza y un pie. Entonces, ¿qué valor hay para cosas como la reproducción y el cruce?

Hmm, esa es una muy buena pregunta. Tal vez los primeros movimientos en Starcraft se puedan realizar en casi cualquier orden, ya que el contacto con el enemigo no es tan inmediato como en el Ajedrez, y por lo tanto no es tan importante recordar el orden de los primeros movimientos como es saber cuáles de los muchos movimientos están incluidos en esos primeros pocos. Pero el vínculo parece implicar lo contrario, lo que significa que los 'genes' no son del todo susceptibles de ser intercambiados, a menos que haya algo astuto en la codificación que me estoy perdiendo.

En general, y mirando el enlace que proporcionó, diría que los algoritmos genéticos no son una buena opción para esta situación, que podría ser modelada matemáticamente con precisión en algunas partes y el árbol de búsqueda ampliado en otras. Pueden ser mejores que una búsqueda exhaustiva del espacio de posibilidades, pero pueden no serlo, especialmente dado que hay múltiples poblaciones y las más pobres simplemente están desperdiciando el tiempo de procesamiento.

Sin embargo, lo que quiero decir con "una mala elección" es que es ineficiente en relación con un enfoque más apropiado; eso no quiere decir que todavía no podría producir resultados óptimos del 98% en menos de un segundo o lo que sea. En situaciones como esta donde la fuerza bruta de la computadora es útil, generalmente es más importante que hayas modelado correctamente el espacio de búsqueda que haber utilizado el algoritmo más efectivo.