Desarrollar una IA astuta en un juego táctico basado en heurística y mutaciones.

En los juegos tácticos, la IA es muy importante. Si la IA es vista como un "idiota artificial", entonces el juego puede ser salvado por increíbles jugadores múltiples, trama, atmósfera y gráficos (esto es inexacto). La solución es obvia: hacer una buena IA, ¿cuál podría ser el problema?


En los detalles A continuación están mis pasos para construir una IA fuerte con carácter. No es súper fuerte [ 1 ], pero puede trabajar rápidamente localmente en un navegador glotón de cualquier PC medio débil. He aplicado el enfoque de sistemas expertos utilizando un conjunto de heurísticas y mutaciones. Se describen 15 pasos de transformación gradual de la IA, cada uno de los pasos se puede sentir.

Breve descripción

En un juego de navegador experimental, la IA se basa en la generación de muchos estados posibles: los resultados del movimiento actual. (Debido a los detalles y la conveniencia del juego, estos estados resultantes en el artículo se llaman escenarios de giro o estrategias de IA, según el contexto) . Entonces los escenarios del curso están mutados. Según los escenarios obtenidos, se calculan las estimaciones de "éxito". El más exitoso y realizado por un jugador de computadora.

Por ejemplo, se generan tres estrategias:

1. Corriendo frenético hacia adelante y atacando a todos los que levantan el brazo. Puntos del estado final: 37000 puntos.
2. Ataca a los arqueros desde una distancia segura, mientras el resto se esconde en las esquinas. 45000 puntos.
3. Todos se retiran, agrupan y se esconden de los enemigos. Si puedes herir a cualquier enemigo desde una distancia segura, entonces ataca. 18000 puntos.
4. En este caso, se seleccionará la segunda estrategia.

Bueno, todo parece ser estándar. En realidad no

Toda la pulpa es cómo se generan los scripts y cómo se calcula el coeficiente de valor del script. Impone en uno de ellos, y el resultado te entristecerá.

Reglas del juego

El jugador y la IA inicialmente tienen 6 unidades idénticas en las esquinas. Cada equipo se turna por turno por todas las unidades a la vez. Opciones para el progreso de cada unidad:

• omitir un movimiento;
• moverse y saltar;
• mover y atacar ( puedes y a veces necesitas atacar por tu cuenta ).

El campo de juego y la composición del equipo se generan de manera procesal ( es decir, al azar, pero con controles de permeabilidad y "tacto" aceptable ). Tipos de unidad:

1. Fighter F, unidad cuerpo a cuerpo con la mayor capacidad de supervivencia, daño y movilidad. Una especie de tanque + daño.
2. Archer A, el daño más bajo, pero el ataque está a una distancia de 1-7 en línea recta.
3. El hechicero W, muere de un solo golpe de un luchador, pero el ataque está a una distancia de 1-5 en línea recta a través de todas las unidades.

El campo de juego siempre tiene un tamaño de 10 * 10.

Posibles campos en el mapa:

• Tierra: no impone ninguna restricción.
• Muro: a través de él no puedes disparar ni pasar.
• Agua: es imposible pasar a través de ella, pero un arquero puede disparar a través de ella (un mago ardiente no puede ).

El juego está completamente determinado, es decir, no hay ningún elemento de azar en él (100% de probabilidad de golpear, no hay daño crítico, etc.). También es un juego con información completa, es decir, los rivales saben todo sobre la condición de las tropas de cada uno en un momento dado. Como en las damas.

La IA es más fuerte que un jugador de carne, pero este último en el primer nivel tiene una desventaja en forma de una unidad. El día 3, el jugador, por el contrario, tiene una desventaja de una unidad y es mucho más difícil ganar (tengo alrededor del 15% de las victorias en esta etapa). Luego viene la versión más aleatoria de Game +.


El juego fue desarrollado en JavaScript nativo: en estilos divs y css, y esta fue la solución más desafortunada posible [ 2 ]. Este es un juego de navegador. El motor no fue usado. El único objetivo del proyecto es crear un jugador de computadora fuerte "con carácter" y la capacidad de cambiarlo (cálculo de cyborgs, orcos agresivos, elfos traicioneros, zombis estúpidos).

Para reducir el "estilo de computadora" del enemigo, se aplicaron algunos trucos:

• El jugador después de su turno no espera hasta que la IA piense en su movimiento. El enemigo "inmediatamente" comienza a hacer sus movimientos ( en realidad, esto es una ilusión ).
• El jugador de la computadora también controla las unidades usando su cursor ( y esto también es una ilusión, el cursor simplemente vuela al mismo tiempo que las animaciones de las unidades ).
• La IA puede usar cebos insidiosos para forzar una pelea ( todo es justo ).

¿Y qué es tan complicado?

Al principio, puede parecer que todo es simple: simplemente puede ordenar todas las opciones de todos los movimientos y elegir la mejor. Pero muy pronto se hace evidente que todo es muy difícil.
La enumeración completa es imposible debido al efecto de explosión combinatoria [ 3 ], que consiste en el hecho de que a medida que aumenta el número de elementos que se verifican en los escenarios, la complejidad de los cálculos crece exponencialmente. A continuación, describiré lo que esto significa en mi juego en particular.

Primero porque En cada turno, las unidades del equipo van todas a la vez , luego su secuencia puede ser diferente. Y con 6 unidades en el equipo de tales combinaciones se convierte en 720 (1 * 2 * 3 * 4 * 5 * 6). Si habrá más unidades, habrá una gran cantidad de combinaciones (de 7 a 5040, de 8 a 40320 ...). Si no tiene en cuenta el resultado máximo, el jugador corre el riesgo de probar el placer en anticipación del próximo movimiento durante 5-10 minutos ( y si es persistente, la demora crecerá hasta millones de años, no todos sufrirán ). Es por esta característica que mi IA al comienzo de la batalla es menos efectiva que al final. De hecho, hacia el final, la mitad del equipo ya ha muerto.


En segundo lugar, cada unidad puede moverse a diferentes puntos del mapa . Los luchadores con un rango de movimiento de 4 pueden parecerse a 1-41 posiciones diferentes. Para los magos y arqueros con su movimiento en 3, el número posible de movimientos es 1-25. Por ejemplo, la composición del equipo puede ser: 4 luchadores, 1 mago y 1 arquero. Obtenemos el total de diferentes combinaciones de movimientos para este elemento: 41 * 41 * 41 * 41 * 25 * 25 = 1766100625. En realidad, debido a las intersecciones mutuas y el terreno infranqueable, habrá menos combinaciones, pero en una rara situación de "dispersión en el mapa" el número de combinaciones será Acércate a ese número.

En tercer lugar, cada unidad después del movimiento puede omitir un movimiento o ataque en una de las 4 direcciones. Es decir, tenemos 5 posibles acciones finales por unidad. Combinaciones totales: 5 ^ 6 = 15625.

Combinaciones totales: 720 * 1766100625 * 15625 = 19868632031250000.

Y en cada combinación válida, será necesario calcular los puntos del estado resultante. La función de evaluación incluye: emulación de movimientos, ataque, causar daño, muerte de unidades y contar los puntos de vida restantes de los sobrevivientes. Por supuesto, el número de combinaciones está exagerado, porque en condiciones reales, la variabilidad disminuirá debido a los límites y obstáculos en el mapa, pero seguirá siendo un número insoportable de combinaciones. Y todo esto sucede después de todo en un navegador normal.

Como se hace

Para resolver un problema similar, se utilizó un enfoque heurístico, cuyo algoritmo generalizado se puede describir de la siguiente manera:

1. Genere diferentes escenarios basados ​​en estrategias predefinidas (~ 20 piezas).
2. Mientras haya tiempo, mute los guiones, dejando los más rentables.
3. Al final, seleccione el escenario con la calificación más alta.
4. Realice el primer movimiento de la unidad desde el guión, pero no camine el resto. Comienza la animación del primer movimiento, y mientras se muestra la animación, continúa mejorando los guiones para las unidades restantes.
5. Repita para las unidades restantes del paso 1.

El método heurístico es un método que puede funcionar (según McConnell [ 4 ]). Más y más estricto en Wikipedia [ 5 ].

Los puntos clave en este algoritmo son: generación de escenarios, mutaciones y la evaluación correcta de la rentabilidad del estado. Cada uno de estos puntos utiliza su propia heurística local. Sin embargo, siempre que fue posible, se utilizaron algoritmos con un resultado óptimo garantizado, por ejemplo, A * para encontrar la ruta [ 6 ].

El enfoque evolutivo que utilicé no puede llamarse una genética completa [ 7 ], porque de él, usé solo mutaciones y la supervivencia de los "más fuertes", y ajusté manualmente los coeficientes de influencia de las heurísticas individuales. No se utilizaron algoritmos para la formación de poblaciones y cruces. Después de la mutación, solo uno sobrevive: un mutante o un progenitor.



No utilicé redes neuronales [ 8 ] debido a la naturaleza del problema. En primer lugar, debido a la complejidad de su implementación exitosa en un entorno en constante cambio (la aparición de nuevas mecánicas, habilidades, habilidades). En segundo lugar, debido a la complejidad en su personalización controlada (si desea realizar dos comportamientos: Suvorov rápido y Kutuzov cuidadoso [ 9 ]).

La evolución de un idiota artificial hacia la inteligencia artificial.

0) Al principio, solo se introdujeron 3 estrategias con movimientos aleatorios en la IA. { Dificultad del juego # 0 }. El puntaje de condición fue solo un número aleatorio. Y como la IA no es el único elemento de desarrollo, tuve que soportar el comportamiento de los peces locos durante bastante tiempo.

1) Luego, en el cálculo de la evaluación de la estrategia, se agregaron los controles de las unidades restantes y sus vidas con la IA y el jugador. { Dificultad del juego # 10 }. Para una unidad muerta, el equipo recibió 0 puntos. Para unos puntos X completamente sanos (por ejemplo, 100,000 para el luchador F, 70,000 para el arquero A, 85,000 para el hechicero W). Para los heridos se les cobraba el 50% del valor central, y el 50% restante en proporción a las vidas restantes del máximo. Gracias a esto, era más rentable que la IA matara a los enemigos, y si solo podía herir, entonces elegía oponentes con menos vidas, más vulnerables.

Los movimientos aleatorios se hicieron más significativos: la IA a veces devolvía.

2) Luego se agregó una estrategia de inicio más significativa:
max_agro : todos los soldados corrieron lo más cerca posible de los enemigos e intentaron infligir el mayor daño posible . { Dificultad del juego # 20 }. Una estrategia utilizó el orden de movimiento original de la unidad, la segunda fue en orden inverso.

La IA comenzó a comportarse como el idiota artificial más primitivo en los juegos tácticos. Y muy a menudo, tal IA se usa en juegos tácticos. Es popular debido a su fiabilidad y simplicidad. Este incluso puede ganar, pero muy raramente.

Así es exactamente el comportamiento de la IA en el fallido juego Master of Monsters - Disciples of Gaia, lo que hace que sea tedioso jugar en él [ 10 ].


3) Luego se agregaron estrategias que toman en cuenta el posible daño de los enemigos durante el movimiento, y eligen aquellos movimientos que condujeron al menor peligro, preferiblemente cero. { Dificultad del juego # 30 }. Y la IA se volvió inmediatamente cobarde, evitando cualquier proximidad con el enemigo: es mejor escapar que atacar y herir, ¡porque el enemigo puede dar más cambios!

Por lo tanto, la evaluación de las condiciones también comenzó a tener en cuenta el posible daño al enemigo . Los puntos de penalización por daño potencial de los enemigos comenzaron a calcularse con un coeficiente decreciente de 0.20 (el coeficiente se reconfiguraba constantemente ). Esto obligó a la IA a elegir una opción agresiva al elegir entre ataque o vuelo, ya que trajo 5 veces más puntos que el vuelo. Pero la IA aún permaneció cobarde durante mucho tiempo, porque para entrar en una situación de elección, el enemigo ya debería estar a su alcance, y la IA en sí, con tales evaluaciones, nunca se pondrá primero bajo ataque. Es decir, no irá a un acercamiento. Por supuesto, el jugador se sentirá engañado, porque la IA tiene un suministro interminable de paciencia y puede huir del peligro para siempre, forzando al jugador a la agresión.

Cabe señalar que tales cálculos de posibles daños son muy largos sin el uso de un caché. Un error de cálculo completo de una estrategia sin optimizaciones tomó inicialmente 700 milisegundos. ¡Pero tengo una limitación en el curso completo de una unidad ~ 4000 ms! Después de las optimizaciones y los cachés gastados, este tiempo disminuye a 20 milisegundos con estrategias muy similares ( desafortunadamente, el caché no se puede calcular de antemano debido al efecto de explosión combinatoria, por lo que no siempre se alcanzan los 20 ms ).

Por lo tanto, cuando introduje la tecnología de cálculo con el pronóstico de varios movimientos por delante , el tiempo de cálculo para una profundidad de solo 2 movimientos (enemigo e IA) ya tomó +700 milisegundos. En este caso, la optimización se utiliza para cortar las ramas "débiles". Si utiliza la estrategia primitiva max_agro para esto, el aumento en el tiempo fue de +30 milisegundos y el almacenamiento en caché casi no redujo esta diferencia ( porque la posición en el mapa era completamente nueva ).

Como resultado, hice 5 enfoques diferentes para el desarrollo de este enfoque, pero al final lo abandoné por completo, porque Las mutaciones con heurística dieron resultados mejores y más rápidos.

4) Las siguientes estrategias tenían como objetivo expandir la diversidad inicial de estrategias:
far_attack_and_hide : las unidades intentan atacar lo más lejos posible del enemigo y, si no atacan, se esconden de cualquier ataque.

close_group_flee : las unidades se retiran de la batalla y se agrupan lo más cerca posible entre sí. Si puedes atacar al enemigo con seguridad al mismo tiempo, ataca.
{ Dificultad del juego # 40 }.

Esto mejoró el proceso de la batalla en sí, pero el comienzo de la batalla siempre no fue rentable para la IA: se retiraba constantemente, pero podía ser atraído hacia el ataque y asustado para que el grupo de IA se dividiera en varios grupos pequeños que podrían destruirse por separado.

5) Entonces es hora de mutaciones . { Dificultad del juego # 50 }.

El algoritmo de mutación fue muy simple:

• al iterar sobre las estrategias seleccionadas, se creó una copia de la estrategia;
• en esta copia se hizo una mutación del curso;
• si el movimiento se volvió inválido, entonces se corrigió por lo menos a uno válido de acuerdo con una de las estrategias estándar;
• se calcularon puntos de la estrategia mutada;
• si el mutante tenía más puntos, entonces el mutante reemplazó a su padre.

Al mismo tiempo, los extraños no eliminaron la estrategia y también participaron en mutaciones, porque siempre ha habido una probabilidad notable de una serie muy exitosa de mutaciones.

Al principio, se implementó el tipo de mutación más primitivo: de 1 a 3 movimientos fueron reemplazados por otros aleatorios, el orden de los movimientos se mantuvo igual. Durante una iteración de cálculos, en promedio, se crearon alrededor de 5-15 mutaciones para cada estrategia. Además, en promedio, cada quinta mutación fue más rentable y reemplazó la estrategia de los padres.

6) cebo heurístico . { Dificultad del juego # 60 }.

Esta heurística repitió la táctica con la que atraía a la IA a atacar con una unidad para matarla de una en una. Este truco también se le enseñó a la IA.

Para hacer esto, en la función de calcular puntos para el estado de la estrategia, se verifica si el estado actual corresponde a la situación del cebo:

• Solo un soldado AI puede ser atacado;
• Solo un enemigo puede atacar a una unidad rastreada;
• La unidad del jugador de la computadora debe sobrevivir después de este ataque;
• Al menos dos unidades de la computadora podrán atacar en respuesta. Cuantas más unidades de castigo, más puntos para la heurística.

El efecto resultó ser excelente: se vuelve más fácil para el jugador comenzar la batalla él mismo. Además, la mayoría de las veces, es aún más rentable para un jugador "aferrarse" a este cebo, ya que después de un ataque de retorno podrá caer sobre la IA con todo su escuadrón ( esto es si está razonablemente agrupado de antemano ). Y allí todas las decisiones tácticas locales competentes resolverán todo.


7) Entonces comenzó a llamar mi atención que los cazas AI se dispersan constantemente como cucarachas . { Dificultad del juego # 70 }. Además, los soldados podrían esconderse en una esquina o entrar en túneles estrechos, en los que la IA perdió en gran medida su efectividad para resolver posibles ataques.
Por lo tanto, se agregaron a la función de evaluación heurísticas para estimar distancias entre unidades y topografía de mapa con los siguientes supuestos:

• Cuanto más cerca estén los aliados entre sí "en promedio", mejor (las unidades comenzaron a dispersarse en diferentes partes del mapa con menos frecuencia).
• Cuanto más cerca estén los soldados de la IA de los soldados "promedio" del enemigo, mejor (necesitaba una IA ofensiva).
• Cuanto mayor sea la distancia máxima entre cualquier par de aliados, peor. Al mismo tiempo, una distancia de 4 no se penaliza, y todo lo que es mayor se penaliza exponencialmente (esto dejó de atraer a los soldados a filas vulnerables).
• Si el soldado AI no puede correr y atacar al enemigo en al menos 2 turnos, entonces debe ser multado (esto lo obliga a atacar, pero no a ponerse bajo ataque).
• Si dentro de un radio de 2 pasos del soldado hay demasiadas posiciones de bloqueo, entonces está bien (con menos frecuencia comenzaron a correr hacia túneles).
• Si un soldado está en el borde del mapa, múdelo aún más fuerte. Como resultado de esto, la maniobrabilidad de la IA aumentó considerablemente, ya que Una unidad puede correr desde un área abierta a un número mucho mayor de posiciones que desde una esquina o túnel.

8) Entonces es hora de expandir las estrategias. { Dificultad del juego # 80 }. No pude agregar una enumeración completa del posible orden de movimientos de la unidad, pero podría enumerar sus movimientos por tipo : luchador, arquero, hechicero. Por lo tanto, aparecieron estrategias para la secuencia de movimientos, de la forma W_A_F: primero todos los brujos caminan, luego todos los arqueros, luego todos los luchadores.

Por lo tanto, se agregaron 6 nuevas estrategias: W_A_F, W_F_A, A_W_F, A_F_W, F_A_W, F_W_A. No resolvieron todos los problemas, pero mejoraron significativamente la calidad del juego.

9) Tuve mutaciones, pero fueron de poca utilidad. { Dificultad del juego # 90 }. En su mayoría, mejoraron las estrategias débiles, mientras que las exitosas rara vez mejoraron. Por lo tanto, las mutaciones se modificaron y cada vez que uno de los tipos aleatorios de mutaciones funcionó:

• De 1 a 3 movimientos fueron reemplazados por otros aleatorios, el orden de los movimientos se mantuvo igual (forma antigua);
• Cambia el orden de movimiento de dos unidades aleatorias. Déjelos sin cambios, incluso si no son óptimos. Si el movimiento no puede repetirse, una de las estrategias habituales lo recrea aleatoriamente a un estado válido;
• Cambia el orden de los movimientos de dos unidades aleatorias y vuelve a contar sus movimientos. Todos los movimientos fallidos en unidades posteriores se reparan mediante estrategias convencionales aleatorias.

La introducción de estas mutaciones comenzó a compensar seriamente la imposibilidad de enumerar por completo todas las combinaciones de movimientos de unidades. Aunque, debido a su aleatoriedad, no da ninguna garantía de que se encontrará un golpe en el tiempo limitado disponible.

10) Luego, se agregaron más estrategias semi-aleatorias . { Dificultad del juego # 100 }. El orden de los movimientos se generó al azar, y los movimientos mismos se seleccionaron de acuerdo con los siguientes principios (para reducir su importancia):

• infligir el máximo daño;
• recibir el menor daño posible en respuesta;
• Acércate lo más posible a tus enemigos.

No vi una mejora notable aquí, pero el proyecto ya se ha movido a la etapa donde cada mejora conduce a efectos reproducibles menos notables.

11) Estaba cansado de los errores evidentes de la IA, cuando atacó a mis soldados mientras atacaba con su hechicero, pero al mismo tiempo hirió a sus aliados. { Dificultad del juego # 110 }. Aunque antes de eso, en realidad podía caminar con ellos y sacarlos de la línea de fuego. Por lo tanto, se creó una estrategia generada con controles manuales :

• si hay un hechicero, busca un lugar desde donde infligirá el máximo daño;
• si hay aliados en este lugar o en el camino de la huelga, recuérdenlos;
• primero, todos los aliados a quienes recuerdan van y no pueden tomar posiciones reservadas por el hechicero (es decir, despejar el camino);
• el hechicero camina;
• Las unidades restantes están caminando.

La estrategia se describe fácilmente en palabras, pero es genial para programarla.

12) Algunas veces las unidades " escaparon a los arbustos " justo antes del comienzo de las hostilidades. { Dificultad del juego # 120 }. Como resultado de esto, cuando comenzó el intercambio de ataques, una o incluso dos unidades podrían estar demasiado lejos de las operaciones militares y no ayudaron a los aliados. Si esto sucediera, entonces estaba casi garantizado que vencería a la IA. Si no sucedía, a menudo perdía. Me libré de esto introduciendo una nueva heurística para evaluar los puntos resultantes de la estrategia. Para cada unidad, se realizó una comprobación:

1. Si la unidad atacó este turno, recibió +1500 puntos.
2. Si no atacaste, se calcularon las posiciones a partir de las cuales los enemigos podrían infligir daño a los aliados. Continúe contando si hay más de 0 de tales posiciones (N> 0).
2.1. Si una unidad no puede alcanzar y atacar en cualquier posición (n = 0), recibe una penalización de -1000 puntos.
2.2. Si una unidad puede alcanzar todas las posiciones, obtiene +1200 puntos.
2.3.Si una unidad puede atacar hasta ciertas posiciones, obtiene + (n / N) * 1000 puntos.

Esto ha mejorado mucho la "cohesión" de las unidades de IA. Desafortunadamente, comenzaron a aparecer casos de "un desertor", cuando en una situación de pérdida una de las unidades heridas prefería esconderse detrás de sus camaradas en lugar de contribuir atacando al enemigo. Parecía ridículo cuando a la computadora le quedaban solo 2 unidades, y el jugador tenía 3 o más. Una heurística correctiva adicional es la siguiente regla:

IF ("   ,   " AND "    3 ") THEN "      " 

13) Al final de la introducción de las estrategias, ya habían acumulado menos de 25 piezas. { Dificultad del juego # 130 }.

Mutar a cada uno de ellos se ha vuelto demasiado costoso. Por lo tanto, se decidió eliminar los más infructuosos y dejar solo 8 piezas. Desde el principio, no quería utilizar este enfoque con la expectativa de que la mutación de los extraños pueda conducir a un excelente resultado inesperado, en lugar de solo uno bueno. Entrar en este procesamiento finalmente condujo a una mejora en el juego de IA.

14) Alrededor del comienzo todavía había una revisión interesante. Inicialmente, el valor del escenario se calculó como la diferencia en la suma de puntos:

 _ = _ - _ 

Pero después de varias mejoras, recordé que esta no es la mejor solución, porque luego, para la IA, las situaciones "2 soldados versus 1 solo soldado" y "4 soldados versus 3 soldados" serán las mismas. Por lo tanto, los puntos comenzaron a calcularse como la razón:

 _ = _ / _ 

El cambio es pequeño y el resultado es muy grave. Sin modificación, el precio de un error con mayor riesgo siempre ha sido el mismo. Después del refinamiento, la IA comenzó a arriesgarse menos descuidadamente hacia el final de la batalla, y esto lo fortaleció notablemente.

Quiero señalar que todas estas mejoras se introdujeron gradualmente, aunque en el orden indicado, pero muchas de ellas fueron mejoradas, procesadas y corregidas de errores en un orden más caótico. Hubo más de 100 iteraciones reales.

Así es como juega la IA final { Dificultad del juego # 9999 }:

AI camina de inmediato, sin perder el tiempo pensando

Para acelerar los cálculos, la optimización del algoritmo se utilizó activamente en forma de particiones de bucles anidados en bucles secuenciales ( reduciendo la complejidad ) y la introducción de varias matrices con cálculos preliminares en caché ( y la posterior optimización de estos mismos cachés ). Según mis estimaciones, otras optimizaciones podrían proporcionarme un aumento doble (o incluso mayor) en la velocidad, pero esto conduciría a un aumento injustificado en los costos de tiempo y una pérdida aún mayor de legibilidad del código.

La principal tecnología de alta velocidad son los cálculos preliminares durante el tiempo de inactividad. Este método consiste en dividir el proceso en dos partes: los cálculos mismos y la animación de los resultados del cálculo:

• Los cálculos del curso de la primera unidad comienzan inmediatamente después del turno del jugador, mientras se abre una ventana que indica que comenzará el turno del oponente. Y esto es tanto como 4 segundos, que el jugador no percibe como una expectativa vacía;
• los cálculos del segundo movimiento y los movimientos posteriores comienzan cuando comienza la animación del curso de la última unidad (es decir, cuando el cursor AI solo comienza su movimiento). Y el tiempo de todas las animaciones ya es de 4.5 segundos. Aunque sería más correcto llamar a esto no el cálculo del próximo movimiento, sino la mejora de la estrategia pasada ya desarrollada y la búsqueda de una nueva, porque en cada iteración, se calculan los movimientos de todo el equipo;
• al animar movimientos de IA a unidades en movimiento, el cursor de AI vuela, lo que finge que hace clic en ellos. El cursor vuela lo más rápido posible, pero para que la comodidad de seguirlo permanezca. Además, agregar un cursor no solo permitió aumentar el margen de tiempo de cálculo de 2 segundos a 4.5, sino que también hizo que ver el progreso de la computadora fuera más cómodo para una persona;
• el tiempo de turno del jugador tampoco se desperdicia. Mientras el jugador piense, casi no se hacen cálculos, por lo que en este momento se calculan de manera intensiva los posibles cachés para el movimiento futuro del oponente de la computadora.

Para evitar que todo esto se retrase en el navegador y trabaje con un FPS bastante estable, el trabajador realiza los cálculos de forma asíncrona ( trabajadores web ) [ 11 ].

Al hacer esto, quería deshacerme de la molesta ventana de espera de "Paseos por computadora". Un dado tan desagradable se encuentra en muchos buenos juegos, por ejemplo, en Xenonauts [ 12 ]. Creo que pude hacer frente a este problema.


Por lo tanto, AI pasa siempre el mismo tiempo para pensar en su movimiento, independientemente de su complejidad. Una característica muy curiosa de este enfoque es que cuanto más fuerte sea el jugador con una computadora, más mutaciones de IA tendrán tiempo de resolver y, por lo tanto, será más fuerte, más poderosa será la computadora del jugador. Primero eliminé este efecto arreglando el tiempo de ejecución y calculando previamente la velocidad de la computadora. Sin embargo, luego eliminé esta fijación, porque propietarios de computadoras poderosas, esto les permitirá luchar con "su" computadora, en lugar de la computadora promedio.

¿Cuál es el resultado y cuáles son las desventajas?

Por lo tanto, el adversario informático resultante sabe cómo luchar dignamente y hace un buen uso de los descuidos de cualquier jugador, y no hace demasiados por su cuenta. Sin embargo, yo, conociendo todas las características de su trabajo, aunque con tensión, lo derroto casi siempre (en igualdad de condiciones). Pero me gustaría lo contrario: incluso conociendo sus características, casi siempre pierde ante él. La IA está lejos de ser ideal, porque el conjunto de heurísticas que utilizo conduce a la superposición sinérgica de "errores de mi percepción" entre sí. Estos errores son:

1. La imperfección y lo incompleto de mi propia estrategia, no conozco todas las mejores estrategias y, por lo tanto, no puedo identificarlas e implementarlas en el juego.
2. Pérdida de eficiencia (que no es tan ideal) de las heurísticas resueltas al transferirlas al código del programa. Por ejemplo, mi heurística humana: "Las unidades permanecen cerca, pero no demasiado cerca para evitar el doble daño de los magos y no quedar atrapados en pasajes estrechos". Esta heurística me ayuda a derrotar a la IA, pero cuando se la enseño a mi oponente de la computadora, tengo que traducir una descripción cualitativa en una algorítmica con estimaciones cuantitativas, y aquí es posible la pérdida de datos.
3. Conflictos mutuos entre heurísticas. Cuando hay demasiadas heurísticas, gradualmente comienzan a superponerse. Como resultado de esto, puede ocurrir una amplificación inesperada debido al doble conteo oculto o la duplicación parcial. O algún tipo de heurística dejará de influir en algo, porque su contribución está completamente bloqueada por grandes coeficientes competitivos.
4. Las limitaciones de tiempo y las mejoras paso a paso de las estrategias elegidas conducen al hecho de que el primer movimiento siempre estará menos pensado. Esto significa que un primer movimiento fallido puede bloquear los movimientos obvios más efectivos de las unidades restantes del equipo. Esto se expresa en el hecho de que el primer luchador F en lugar de alejarse puede atacar irónicamente al enemigo y luego su mago aliado W tendrá que herir al suyo para acabar con el enemigo.

Los algoritmos genéticos completos, en lugar de "emparejar a simple vista", probablemente permitirían seleccionar coeficientes más óptimos en heurística. Pero esto ya es una tarea para futuros proyectos completos: no quiero quedarme con un prototipo durante mucho tiempo. Estoy bastante satisfecho con la IA actual: es prudente, un poco insidiosa, bastante agresiva y no permitirá que el jugador se derrote seco ( en realidad, es extremadamente raro permitirlo ).

Características adicionales

Este método de implementación le permite obtener bonos adicionales en el desarrollo del juego ( en muchos aspectos desde el punto de vista del desarrollador y sus términos candentes ):

1. La aparición de nuevas mecánicas en el juego no destruirá la fuerza del jugador de la computadora, aunque lo debilitará gradualmente en comparación con el jugador. Este debilitamiento puede compensarse con la introducción de heurísticas adicionales. Para que esto no conduzca a gastos progresivos de recursos, es posible aplicar estas nuevas heurísticas solo si estas nuevas mecánicas están presentes en la batalla actual.
2. Niveles de dificultad realmente inteligentes. Ahora, básicamente, el nivel de dificultad determina qué bonificaciones recibirá un jugador de computadora como recursos ( más oro al inicio o una bonificación en la minería ) o cuánto vencerán sus soldados ( + 50% al daño ). Funciona, pero puede hacer que la IA sea un poco menos inteligente simplemente deshabilitando gradualmente algunas heurísticas a medida que disminuye la complejidad.
3. En la continuación del segundo párrafo, puedes crear diferentes razas / facciones de oponentes de la computadora : solo las estrategias agresivas funcionan para los orcos; en multitudes de zombis, solo los primitivos "corren y atacan"; y los cyborgs usan todo el poder de la IA. Gracias a este jugador antes del ataque tendrá que evaluar no solo el número de oponentes, sino también su inteligencia.

Todo esto suena prometedor, pero debes recordar que todo esto es hermoso en el papel, y en un juego real puede que simplemente no funcione, resulte poco interesante o incluso invisible para el jugador. Pero esta es una buena razón para experimentar.

Donde sentir

Puedes probar el poder de esta IA en el navegador táctico de IA. Test subject "gratis en sitios como itch.io [ 13 ]. El parámetro GET ai (valores de 0 a 140 en pasos de 10) reducirá la complejidad de la IA.

Según mis expectativas, derrotar a la IA en igualdad de condiciones será muy, muy difícil para ti. Incluso después de acostumbrarse a las reglas del juego. Recomiendo considerar este juego como un prototipo, que es esencialmente (no hay música, sonidos ni precio ).

Por favor, deje su opinión en los comentarios sobre el interés de AI, consejos y críticas sobre la posible implementación de AI utilizando diversos métodos de enseñanza. Si de repente se interesó en mi otra investigación, considere suscribirse aquí a mi cuenta.

Referencias

1. DeepMind - artículos sobre Habré .
2. Juegos HTML5: Canvas vs. SVG vs. div en stackoverflow .
3. Explosión combinatoria - Wikipedia .
4. El código perfecto de Steve McConnell es Habr .
5. Métodos heurísticos - Wikipedia .
6. A * - Juegos Red Blob .
7. El algoritmo genético. Casi lo difícil - Habr .
8. Ocho juegos increíbles con inteligencia artificial de la compañía Google - Habr .
9. Muy brevemente sobre Suvorov y Kutuzov .
10. Maestro de monstruos - Discípulos de Gaia - Revisión en IGN .
11. Una explicación detallada de JavaScript Game Loops y Timing .
12. Xenonautas y una larga pantalla de espera de IA .
13. AI retumbar táctico. Sujeto de prueba - en itch.io.