🚘 🤧 🈹 Mi bot para la Copa Rusa AI 2019 💏 ❇️ 🌄

Dio la casualidad de que este campeonato fue el primero para mí en el que pude ocupar un lugar digno, por lo que no me avergüenzo, así que decidí escribir el artículo ahora mismo. El camino que fui a este lugar: 1192 en el campeonato del año 13, 241 en el campeonato del año 17, 91 en el campeonato del año 18 y, finalmente, 16 (y 5to e en la caja de arena) coloque en eso.

Pensamientos generales

Creo que una de las principales razones del rendimiento relativamente exitoso en RAIC fue un cambio en el enfoque para escribir su estrategia.

Antes, traté de escribir inmediatamente algo grande y complicado, sin pasos intermedios, y la primera versión solo podía completarse dos semanas después del comienzo del campeonato, pero en el pasado no podía ponerla en todo el tiempo asignado y la primera versión se completaba solo después de la final .

Todo esto condujo al hecho de que, si bien otros participantes podían probar sus estrategias de vida, todavía no tenía una solución preparada, aunque fuera mala. Por lo tanto, cuando fue posible completar, resultó que el enfoque elegido no funciona o funciona mal, y dado que se invirtió mucho tiempo y esfuerzo, no fue posible cambiarlo radicalmente.

Por lo tanto, decidí que esta vez lo haría de manera diferente. Basado en la experiencia de participaciones anteriores, noté que el bot inicial, a pesar de toda su primitividad, fue escrito de manera bastante racional y, al desarrollarlo, puede agregar y probar nuevas características lentamente, y comprobar inmediatamente las estrategias de otros participantes. Especialmente estaba convencido de probar este enfoque el artículo del año pasado por T1024.

También decidí por mí mismo que cuanto más complejo es el enfoque, menos efectivo es en mis manos. Por ejemplo, no tiene sentido usar la genética donde es posible hacer una búsqueda exhaustiva, y si hay una opción para ordenar menos opciones, pero todas, o más, pero la genética, es mejor elegir la primera opción. Además, de leer artículos de Comando, Concluí que las optimizaciones específicas para la tarea siempre serán más efectivas que el algoritmo general.

Sin embargo, incluso ahora llegué tres o cuatro días tarde, antes de que pudiera completar la primera versión del bot, en ese momento lucharon en la caja de arena con poder y fuerza.

¿Qué hice en este momento? Escribí un simulador, cuya importancia aprendí de campeonatos pasados. A diferencia del año pasado, donde el pseudocódigo del simulador estaba disponible de inmediato, este año toda la mecánica tuvo que leerse de la documentación. Afortunadamente, como compensación, la mecánica del juego no era bastante complicada y directa, por lo que no tuve ningún problema especial.

Versiones tempranas

Entonces, teniendo en mis manos un simulador crudo, aunque torcido, lo primero que hice fue arruinar los esquivos (función Dodge). Como esta vez decidí actuar de la manera más simple posible, las evasiones se hicieron lo más simples posible: verificamos el movimiento en nueve direcciones (4 axiales, 4 diagonales y de pie) y observamos en cuál de estas direcciones la unidad recibirá el menor daño.

El resto de la funcionalidad del bot permaneció casi completamente como Quickstart. La designación del objetivo también fue lo más primitiva posible: una cadena de ifs que selecciona la acción más adecuada para la unidad: al enemigo, del enemigo, al botiquín de primeros auxilios, a las armas, etc.

Sorprendentemente, este enfoque, gradualmente volviéndose más complicado, pero sin cambiar su esencia, le permitió llegar casi a la cima antes de la primera ronda (una vez que el robot incluso terminó en el segundo lugar en la caja de arena) y generalmente se quedó en algún lugar alrededor de los primeros diez lugares.

Sin embargo, esto no podría durar para siempre, y el bot tuvo que ser mejorado. Sin embargo, no tenía idea de qué y cómo mejorar, todos los intentos de cambiar algo en la estrategia llevaron al hecho de que estaba perdiendo la versión anterior. Se hicieron cambios menores, pero nada más.

La falta de ideas llevó al hecho de que en las rondas 1 y 2 tomé 29 y 19 lugares respectivamente, y aunque fui a la final, quedó claro que algo tenía que cambiar radicalmente. Fue antes del final (y después del final) que se realizó el mayor número de cambios significativos.

Ya en algún lugar desde la mitad del campeonato intenté experimentar con un movimiento más inteligente, pero todos los intentos no tuvieron éxito. La idea inicial era elegir la dirección donde la diferencia de la posibilidad de golpear a su bot en el enemigo y el enemigo en su bot era máxima. Para este experimento, pasé casi todo el tiempo asignado a la final, con un resultado cero.

Por lo tanto, para los mapas finales de varios niveles, el bot resultó estar completamente preparado. La cadena de ifs arrojó resultados relativamente buenos en mapas de un solo nivel de las rondas 1 y 2, pero resultó ser inadecuada para mapas de niveles múltiples de las finales, tampoco tenía un sistema de navegación para mapas complejos, ya que en mapas simples era posible pasar del código de inicio.

— .

Todo el control de disparo está en la función AimHelper.

Todo lo que se describe a continuación implica que el objetivo es la unidad enemiga visible más cercana al bot.

Solo hay tres tipos de armas, sin embargo, cada una de ellas requiere su propio enfoque. Es mejor disparar con más frecuencia desde una ametralladora, apuntar mejor con una pistola, y luego es importante disparar desde un lanzacohetes para infligir más daño al enemigo que a ti mismo.

Inicialmente, no había ningún objetivo en absoluto, el bot solo apuntaba al centro de la unidad. Más tarde, se agregó una predicción del movimiento de la unidad si está en un vuelo descontrolado (cae o vuela desde la plataforma de salto). Para hacer esto, simplemente simulé el movimiento de la unidad hasta que la distancia que la bala puede volar para N garrapatas sea igual a la distancia a la unidad.

Al probar contra el bot inicial, notó su hábito muy desagradable de saltar constantemente pequeño, y si el bot siempre apuntaba al centro del enemigo, esto hacía que la vista se moviera constantemente y la propagación aumentara rápidamente al máximo. Para contrarrestar, se agregó un código que verifica si la probabilidad de golpear con el ángulo de puntería actual es mejor o igual a la posibilidad de golpear con un nuevo ángulo de puntería, entonces no cambiamos el punto donde apuntamos y no aumentamos la extensión.

Con el disparo fue más difícil, uno de los principales problemas del bot inicial fue que no comprobó si se tocaría con una explosión. Por alguna razón, me gustó el lanzador de cohetes de la mayoría de los tres tipos de armas, y por lo tanto, era la primera prioridad. Era necesario enseñarle al bot a no debilitarse.

Se escribió la función HitChance, que dividió el sector de disparo de la unidad en rayos N, y verificó cada rayo en busca de una colisión con un objetivo. Además, cuando se golpeó, se comprobó el AOE de la explosión, si es un lanzacohetes. Posibilidad de golpear = número de golpes por rayo o explosión / número de rayos.

Esto nos permitió determinar la posibilidad estática de golpearnos a nosotros mismos y al enemigo, pero no tuvo en cuenta que el enemigo mismo podría esquivar activamente. Hubo otros problemas, por ejemplo, la función no tuvo en cuenta el disparo aleatorio a las minas.

Esto fue suficiente para luchar contra enemigos no tan astutos, pero contra las cimas que esquivan bien las balas, la función no dio ningún resultado adecuado. Se necesitaba un nuevo enfoque.

La función HitPredict también divide el cono de disparo en rayos N, pero en lugar de lanzar el rey, usamos una simulación en la que se dispara una bala a la vez en una de las direcciones y se verifica si el enemigo puede esquivar.

Para verificar las evasiones, también se usa la función Dodge, que el bot usó para sí mismo, pero con mucho tiempo de simulación cortado y la cantidad de microtics. Este método de evaluación resultó ser bastante preciso, pero demasiado pesimista. Si solo lo usas, entonces el bot dispara muy raramente.

En la primera versión, la función devolvió solo la posibilidad de golpear, de 0 a 1, luego se agregó el cálculo del valor promedio de HP del objetivo, así como la posibilidad de matar por golpe.

Al final, ambas funciones trabajaron juntas. La función HitPredict se usó hasta cuatro veces, una para cada unidad. El resultado del cálculo de cada función se convirtió en velocidad, lo que mostró cuán rentable / peligroso es disparar en este momento. Valores agregados. Si el valor total era inferior a cero, se bloqueó el disparo. Para el lanzacohetes, era necesario que la velocidad fuera mayor que cero.

Se ha vuelto posible disparar con más confianza en los casos en que un aliado bloquea el disparo o se mete en el AOE de un lanzacohetes, puede dispararle por la espalda sabiendo que el aliado tendrá tiempo para esquivar, o simplemente es ventajoso para nosotros disparar. Por ejemplo, perderemos una unidad, pero eliminaremos dos a la vez.

Para el lanzador de cohetes, el enfoque también fue efectivo, un disparo en el momento correcto es mucho más efectivo que dos disparos, cuando la posibilidad de golpear es cero. De esta forma, el tiroteo fue en la final, y esto permitió ocupar el puesto 16.

Ahora las fichas que se agregaron después de la final.

Apuntado preciso: si el ángulo entre la vista actual y la deseada no es demasiado grande, apuntamos la vista a una velocidad de datos para no aumentar la propagación.

Ángulo de información para la pistola: por extraño que parezca, el chip es muy simple, pero no se le había ocurrido antes. La prohibición de disparar si el factor de dispersión (dispersión / dispersión máxima) es mayor a 0.6 siempre que el porcentaje de victorias en el modo 1x1 en 3: 1 contra la versión que disparó al CD de armas. Reducir el factor a 0.3 proporcionó el mismo porcentaje de victorias contra la versión con el parámetro 0.6. Por lo tanto, una de las optimizaciones más simples resultó ser una de las más efectivas.

Visualización de la operación de la función HitPredict, las trayectorias donde se garantiza el golpe están marcadas en rojo.

Navegación

Hasta el final de la navegación no había ninguna palabra en absoluto. Se utilizó un algoritmo ligeramente mejorado del bot inicial, y esto fue generalmente suficiente.

Por lo tanto, cuando se fueron las tarjetas complejas, el bot tuvo dificultades. Se escribió urgentemente un algoritmo de búsqueda BFS urgente, que buscaba una ruta sin tener en cuenta su accesibilidad física, simplemente por mosaicos. Para que el bot pase la ruta encontrada, se usaron varias muletas. Todo esto funcionó de manera muy torcida, y a veces no funcionó en absoluto, pero aún así el bot podría de alguna manera llegar a armas y botiquines de primeros auxilios, y no saltar en el acto.

Después de la final, la navegación mejoró significativamente y, según mis observaciones, se comportó de manera aún más eficiente que muchos participantes con mejores algoritmos de búsqueda de ruta.

Principio de trabajo: el bot busca la celda más alejada en el camino dentro del cuadrado de 5x5, visible desde el centro del bot, y sigue hasta este punto.

Sin embargo, hasta el final, siguió siendo un código increíblemente muleta que solo funcionó en los mapas finales y cayó en otros, más complejos.

El camino marcado verde encontró diykstroy. El bot sigue el punto marcado con un cuadrado blanco.

Función de movimiento y estimación

Antes de la final, no había una función de evaluación, en lugar de eso se usaba una cadena de ifs, que en orden de prioridad colocaba el bot en el objetivo de acuerdo con las condiciones dadas. Por ejemplo, la primera fue buscar armas si el bot no tiene una, luego buscar un botiquín de primeros auxilios si estamos heridos, etc.
Esto funcionó en mapas simples, aunque estaba torcido, porque las prioridades cambiaron muy bruscamente y no tuvieron en cuenta varios factores adicionales.

Por lo tanto, se escribió una función de evaluación.

parámetros principales

Unidad de salud, la mayor bonificación.
. — , — .
— , . (1 — / . ), , . , , .
. , , .
, , , .
.
, .
.
Una gran ventaja si podemos tocar al enemigo con autodestrucción.

Los dos últimos parámetros no estaban en la final.

Todos estos bonos se calculan para cada tic, se resumen y se promedia el valor total. Además, hay parámetros estimados que se calculan una vez para cada dirección.

Bonificación por avanzar hacia el enemigo más cercano.
Bonificación por moverse hacia el botiquín de primeros auxilios más cercano. Cuanta menos salud tengamos, más fuerte será la bonificación.
Bonificación por pasar al arma más cercana si no tenemos un arma, o por pasar a un arma con una prioridad más alta que el bot.
Bonificación por pasar a la caja de botín min si el bot tiene menos de dos.
Bonificación por pasar al botiquín de primeros auxilios más cercano al enemigo, si estamos más cerca del botiquín de primeros auxilios que el enemigo.
El bono más interesante. Fue agregado después de la final. Te permite evitar que el bot enemigo sea tratado. Según las observaciones, resultó ser bastante efectivo.

Notas

La profundidad de simulación es de 30 ticks.
El comportamiento de los bots enemigos no es simulado. El juego es muy dinámico y predecir adecuadamente el movimiento del enemigo es muy difícil y no particularmente necesario. Podría ser útil para evitar suicidios locos, pero nunca se hizo.
Para evitar problemas al evadir las balas, si están en el campo, simulamos con una calidad de 100 microtics por tick (como en el juego), de lo contrario lo reducimos a 5.
Puede notar que no se aplica ningún coeficiente de atenuación. Quizás esto fue un error.

La opción de movimiento anterior está en MoveHelperOld, la nueva en MoveHelper.

Mi bot (a la derecha) guarda el botiquín de primeros auxilios

Minas

Sobre las minas deben contarse por separado. Si inicialmente no era un elemento de juego muy importante, se suponía que debía extraer puntos clave. Después de la prueba beta, la capacidad de explotar minas se agregó repentinamente si fueron alcanzados por una bala o una explosión. Además, fue posible establecer la mina y minarla de la misma manera.

Es decir, si gastas solo dos ticks, podrías llevarte cualquier unidad enemiga contigo. El enemigo recibió 1000 puntos por nuestra muerte, pero recibimos 1000 + su salud en el momento de la demolición por su muerte. Si repite esto dos veces, entonces podría asegurar una victoria con una probabilidad muy alta.

La hazaña resultó ser tan fuerte que un participante, que estaba en algún lugar en el lugar 15 en la calificación general, cayó inesperadamente al 4to en la final, simplemente debido a un kamikaze competente.

(La diferencia es que en la clasificación general hay cartas simples y complejas. En cartas simples, el suicidio funciona peor).

En la final, la estrategia usó minas, pero no usó la detonación intencional. Después de la final, cuando hubo una lucha por premios adicionales, se agregó el módulo TryPlantMine2, que implementa el demoman. Al principio, debido a errores en el código, el módulo no era particularmente eficiente, pero en la última versión era posible arreglar todo, y la estrategia inmediatamente comenzó a subir abruptamente la calificación. Llegó al punto de que incluso voló al top 3, aunque luego se deslizó un poco.

Principio de trabajo: si estamos en una posición que le permite poner una mina, y podemos disparar a más tardar cinco ticks, simulamos tres opciones: simplemente derribar, poner una mina y disparar, dos minas y disparar. Para los enemigos y aliados, simulamos movimiento usando la misma función Dodge, verificando si pueden saltar de la zona de explosión antes de que estemos listos para socavar (no estamos seguros de cuánto se necesitaba). Para cada opción, verificamos cuán beneficioso es para nosotros en los puntos, si estamos en negro, nos socavamos (de esta manera podemos ser socavados incluso sabiendo que dos de nuestras unidades y un enemigo morirán, pero aún así ganaremos) El efecto de auto- socavamiento

en la calificación

recomendaciones

Las soluciones simples a menudo pueden ser más efectivas que las más complejas, pero esto tiene su propio límite. Con este enfoque, puede alcanzar bastante alto, pero luego caer en la trampa cuando el potencial para mejorar la estrategia ya se ha agotado, y sin cambios radicales para aumentar la fuerza de la estrategia es imposible. Para el futuro, debe pensar en algún tipo de opción intermedia.

Conclusión

En general, me gustó este campeonato, aunque estoy predispuesto hacia él, porque esta es la primera vez que logro tomar un lugar. Sin embargo, sin siquiera considerar mis sentimientos subjetivos, este año se ha realizado mucho en un nivel superior.

Por primera vez, fue posible comunicarse en Telegram con una persona responsable de la parte técnica y que respondió rápidamente a todas las preguntas, por lo que muchas gracias a él.
Por primera vez, un visualizador incorporado normal estaba presente en el localranner. Anteriormente, para generar gráficos de depuración, tenía que escribir los suyos.
Finalmente, en lugar de la herramienta de repetición inconveniente y con errores, se agrega el botón "Repetir juego" en la LAN.

De las desventajas, por supuesto, es una gran hazaña con las minas.

Y espero que mis logros en este campeonato no sean accidentales y que la próxima vez pueda al menos salvar un lugar, y aún mejor, tomar una posición más alta (soñar no es dañino).

El código bot se puede ver en el github: github.com/silentnox/CodeSide

Mi bot para la Copa Rusa AI 2019