📙 🈷️ 🐺 Continuación de la participación (y la victoria) en la Copa AI rusa 2019 👶🏽 🙆🏿 🤲🏿

Hola a todos, mi nombre es Andrey Tokarev , y nuevamente me gustaría compartir mi experiencia de participación y victoria en la Copa AI de Rusia.

Si alguien no lo sabe, la Copa AI de Rusia (en adelante RAIK) es un campeonato de programación de inteligencia artificial donde nosotros (o más bien nuestro programa) debemos controlar uno o más personajes (unidades) que compiten entre sí. Este año, el juego era un juego de plataformas bidimensional, que recordaba a los juegos de computadora de principios de los 90, y las unidades eran hombres armados que se suponía que matarían a los mismos hombres del enemigo. Puedes leer más sobre esto en el anuncio.

Esta vez no hubo reunión cuando llegó la agenda para el inicio del RAIK, así que vayamos al grano.

Primera vista

Entonces, repasé las reglas, probé el juego. La primera impresión fue: ¿qué hacer aquí? Como las unidades no tenían inercia, y los niveles iniciales no tenían ciclos cerrados, el enemigo siempre podía apegarse a nosotros si quería, y defenderse de ello era imposible. Y en esta situación, entiendes, las posibilidades son muy limitadas. No esquivarás las balas. Pero mis primeros temores no se materializaron, aunque el factor de probabilidad era alto, las reglas resultaron ser bastante jugables.

No comencé a desarrollarme de inmediato, un par de días ~~caí en ridículo~~Decidí reflexionar. No se me ocurrió nada especial. Está claro que debes esquivar las balas, correr tras los botiquines de primeros auxilios y, si es posible, no dejes que el enemigo tome un botiquín de primeros auxilios y todo eso. Todavía había un plan vago para encontrar posiciones estratégicamente ventajosas, y gira en torno a ellas, pero no estaba del todo claro cómo distinguir estas posiciones.

comienzo

Así que, aquí vamos. Por costumbre, convierto los objetos de datos en el paquete de idioma en mis propias estructuras de datos. Sí, lleva algo de tiempo, pero no mucho, pero obtengo más flexibilidad, trabajo en un entorno más familiar y, mientras convierto, es mejor comenzar a comprender cómo funciona el mundo del juego. Por supuesto, no todo a la vez, sino según sea necesario. Por ejemplo, no recreé las minas hasta que la situación política en el campeonato me obligó a recurrir a medidas extremas. Copié aproximadamente la lógica de Smartgayev, agregando solo un cheque por la presencia de un muro entre el enemigo y yo. Miré, parecen estar funcionando bien, por lo que podemos suponer que tenemos un mundo de juegos.

Simulación

Ahora procedemos al pasatiempo favorito de todos los participantes de RAIK: ¡estamos escribiendo una simulación! Después de leer el chat del campeonato, quedó claro que escribir una simulación precisa es malo. Así que inmediatamente anoté por precisión. Resultó, como sucedió, incluso con un simple rebote desde el techo, había una discrepancia dentro de la teca. Era posible, por supuesto, jugar con él durante varios días y aumentar significativamente la precisión, pero, en primer lugar, no se sabe qué beneficio sería de esto. En segundo lugar, estaba demasiado impaciente y, como siempre, quería ver el resultado lo más rápido posible. Así que decidí comenzar a escribir la estrategia en sí, y pensé que corregiría mi curva de simulación, si fuera necesario. En retrospectiva, debo decir que quizás estaba equivocado.
Valdría la pena llevar inmediatamente la simulación a la normalidad, por lo que fue necesario hacer correcciones allí hasta el final del campeonato, y aún así permaneció torcida.

Base de estrategia

Luego procedemos de acuerdo con el escenario estándar: generamos la secuencia de acciones de los ~~robots~~ unitarios, simulamos un cambio en el mundo del juego y lo sometemos todo a la entrada de la función de evaluación (OF). Si en el fútbol (el torneo del año pasado) fue ineficaz correr detrás de la pelota con un número aleatorio completo de jugadores (hay muy pocas posibilidades de golpear la pelota, especialmente desde el ángulo correcto), entonces no hay tal problema. Básicamente, necesitamos una simulación para dos cosas: esquivar balas y encontrar el camino. Unos pocos escenarios de acción completamente al azar son suficientes para evadir las balas. Varias docenas de escenarios también funcionarán para la búsqueda de una forma más o menos, al menos, en mapas no tan difíciles.

Por cierto, la búsqueda del camino: está claro que contar hasta el final no siempre es posible, por lo que debe poder determinar la distancia. Usando la misma simulación, uno podría calcular distancias más o menos precisas en el tiempo. Pero aquí también lo simplifiqué, solo conté las distancias a lo largo de una cuadrícula rectangular. Esta simplificación, por supuesto, tuvo algunas consecuencias en mapas complejos. A veces, mis unidades todavía estaban confundidas en la búsqueda de armas, mientras el enemigo ya comenzaba a disparar. Es cierto que estos incidentes fueron bastante raros.

La elección del objetivo fue bastante simple: si bien no hay armas, vamos a las armas, si hay armas, vamos al enemigo, y si hay poca "salud", vamos al botiquín. En el caso de los botiquines y armas de primeros auxilios, se excluyeron aquellos objetos que estaban más cerca del enemigo como objetivo. Por alguna razón, la prioridad en las armas para mí fue primero en la máquina.

La primera función de evaluación constaba de dos componentes: es la salud (no la mía, sino una unidad) con un coeficiente grande, y la distancia al objetivo con un coeficiente pequeño.
Aquellos. Se eligió la ruta en la que no cae bajo las balas, pero al mismo tiempo se acerca al objetivo lo más rápido posible. Es importante recordar la mejor ruta encontrada para el siguiente tick, de lo contrario, puede surgir una situación cuando encontremos una buena opción, pero no la dimos en el siguiente tick.

Vamos al frente, y las primeras mejoras

Al observar las batallas, estaba claro que si el enemigo tenía una evasión normal, entonces era casi imposible entrar en él desde una gran distancia. Esto es un desperdicio de balas. Así que agregué una condición simple para disparar: dispara solo si el enemigo está más cerca de 7 metros. Además, si la distancia es muy grande, entonces vale la pena recargarla, incluso si solo falta una bala en el clip. Estas dos condiciones simples agregaron bastante.

Esta fue la primera versión que envié. El mismo día, me di cuenta de que una pistola es más rentable que una ametralladora. Además, agregó al OB otra distancia al enemigo, en caso de que el disparo no sea pronto. Por lo tanto, al recargar, trató de mantener la distancia.

El comienzo fue bastante exitoso. No recuerdo cuán alto la estrategia logró subir en el ranking antes del reinicio (en algún lugar alrededor de los primeros tres cinco), y después del reinicio subió con confianza.

La mejora principal en la próxima versión se debió a un intento de controlar los botiquines de primeros auxilios. Una vez más, todo fue simple: se calculó la distancia entre los botiquines de primeros auxilios y el enemigo, y si eran aproximadamente iguales, entonces se creía que el botiquín de primeros auxilios era un sorteo y, por lo tanto, el que estaba más cerca. Esto fue tenido en cuenta por la función de evaluación. Aquellos. en teoría, la unidad trató de posicionarse para ocultar la mayor cantidad posible de botiquines de primeros auxilios. En teoría, por supuesto, pero no en la práctica.

Después de eso, no envié actualizaciones durante mucho tiempo. Para mi sorpresa, la estrategia primero alcanzó el 1er lugar, y luego aún obtuvo más de 100 puntos. Probablemente todos pensaron que estaba cortando algo genial, y me sorprendió cómo se disparó esta miserable estrategia. Miserable, porque, bueno, hay un control torpe de los botiquines de primeros auxilios, hay dos ifs para disparar, pero básicamente se trata de una simple evasión y movimiento basado en una curva de simulación.

Pruebas

Me gustaría hablar de esto por separado, porque Las pruebas adecuadas son una parte muy importante del desarrollo, y muchos participantes parecen ignorar este aspecto. Accidente es intuitivamente mal entendido por las personas.

Supongamos que ejecutamos una prueba y después de 40 juegos vemos un puntaje de 27:13 a favor del nuevo. Eso es todo, encontramos el Grial, detenemos la prueba y aceptamos los cambios. De hecho, incluso con fuerzas iguales, hay aproximadamente un 2% de probabilidad de tal situación.

Otro ejemplo, lanzamos 100 juegos y aceptamos los cambios si el puntaje es 55:45 o más. Con una probabilidad del 2.8%, una versión puede jugar de esta manera, que en realidad debería perder con el mismo puntaje. Un par por ciento del error puede no parecer muy grande, pero si el 90% de nuestros cambios no tienen éxito, entonces esto significa que cada cuarto cambio aceptado no tendrá éxito. Entonces, incluso 100 juegos siguen siendo una prueba regular, pero menos, nada en absoluto.

Por supuesto, lanzar varios cientos de juegos puede llevar una cantidad indecente de tiempo. Hay diferentes opciones, puede realizar pruebas por la noche, conducir en segundo plano, alquilar tiempo de servidor o hacer que la estrategia sea rápida :) Mis primeras versiones funcionaron en promedio, en algún lugar, durante 5 segundos. al juego, que suerte con eso.

Si la estrategia es lenta, puede conducir localmente versiones truncadas: menos búsquedas, menos micro-ticks, por ejemplo. Utilicé esto en el fútbol (RAIK anterior), no se notaron problemas. Quizás la calidad se pierde en alguna parte, pero, en cualquier caso, es más rentable que buscar cambios en 20 juegos.

Mejoras

Esta vez no evaluaré las mejoras en los números. En primer lugar, todos eran pequeños (menos del 20%) y, por lo tanto, inexactos. En segundo lugar, ambiguo, es decir la nueva versión podría vencer con confianza a la anterior y jugar peor contra otros. Y en tercer lugar, simplemente no los recuerdo.

, . , . , , .
. .. , , . , , -. , . , , . .
, , . , , , , , . , . , .
, ? , , . . , . .

-

Objetivamente, debes disparar en la dirección donde está el tapete. La expectativa de daño es más alta. Está claro que analíticamente esto no se puede calcular, y donde las matemáticas no ayudan, como sabemos, la simulación viene al rescate. Disparamos en todas las direcciones posibles e intentamos esquivar al enemigo de cada bala individualmente. A cada grupo le asignamos el valor mínimo de daño que infligirá con precisión. En el caso de una bala convencional, es 0 o su daño, y en el caso de un cohete hay 3 opciones.

Ahora sabemos el tapete. esperando daños en cada dirección por separado, a partir de esto podemos calcular fácilmente el tapete. espere cada dirección de la toma y elija la mejor. Sería bueno usar esta función en la enumeración para que la unidad esté correctamente posicionada, pero fue demasiado lenta para llamarla en cada escenario. Se llamó una vez por marca para cada unidad, y ahora el disparo se realizó no por distancia, sino si el daño esperado excedía un cierto límite. El aumento fue significativo, y en el caso de la bazuca parecía bastante claro: ahora el mío incluso podía apuntar a algún lugar del muro para golpear al enemigo con una onda expansiva.

Pero debido al hecho de que no pude insertar esta función en la búsqueda, hubo un problema de que las condiciones para el disparo en la búsqueda y en realidad eran diferentes. No sabía cómo resolver este problema, tuve que vivir con él.

Después de eso, no hubo cambios muy significativos hasta el último día cuando introduje la autoexplosión. Agregó una penalización si no quedaba ningún salto en el momento en que el enemigo disparó, porque la caída haría más difícil de esquivar. Traté de predecir el camino del enemigo al botiquín de primeros auxilios, si tiene pocas vidas, y por lo tanto mejoré ligeramente el control sobre ellos. Él mismo comenzó a correr tras los botiquines de primeros auxilios del 60% de su salud, en lugar del 50%. Añadió la distancia entre los suyos en el PF para que no interfirieran entre sí, y la bazuca no eliminaría inmediatamente a dos. Al final, agregó un mod agresivo en caso de que la situación no cambie durante mucho tiempo y pierda puntos, de lo contrario el mío a veces se atasca.

resultados

Como dije, rápidamente llegué al primer lugar en el ranking. Con la excepción de cortos períodos de tiempo, me quedé allí hasta el final. En las rondas, la situación fue un poco peor: cuarto lugar en el primero, tercero en el segundo. Esto indicó que jugué bien contra jugadores fuertes, pero no lo suficientemente estable contra los débiles. Esto se demuestra claramente en uno de los juegos de la segunda ronda, donde kostya200300, que estaba en el último lugar, ¡me ganó en 0!

Auto-voladura

Como la mayoría de los participantes, no estaba entusiasmado con la posibilidad de autoexplosión. Esto aumentó en gran medida el factor aleatorio ya considerable. Pero estaba claro que uno no podría prescindir de él. Es cierto que realmente no quería hacer esto, y lo pospuse hasta el último día. Esta técnica es bastante simple, si estamos parados en el suelo, el enemigo está en un radio de explosión y tenemos suficientes (máximo dos) minas, luego colocamos minas y disparamos al fondo. Pongo una condición adicional que después de la explosión obtengo una clara ventaja, es decir gana inmediatamente o mata a más oponentes que los suyos. Pensé que, dado que aspiro a un lugar alto, cambiar uno por uno no es rentable. Bueno, es como en el ajedrez, si juegas para ganar, entonces intercambiar todo en una fila no es rentable. Así es como envié a mis guerreros dotados de habilidades kamikaze a la batalla final.

El final

Como ya escribí, la calificación solo habla del equilibrio de poder con los competidores más cercanos, y no tenía estabilidad contra rivales más débiles. En este sentido, la eliminación de los participantes a la final fue un desastre para mí. Por otro lado, la difusión masiva de la ideología terrorista en el último día introdujo una mayor difusión en la distribución de las fuerzas. En resumen, a pesar del liderazgo confiado en el ranking, no había confianza en la final, solo había esperanza. Después de la primera mitad de la final, quedó claro que la lucha principal será entre yo y Ivan Tyamgin. Llevé a un pequeño número de puntos, mientras que el resto estaba muy por detrás.

Durante el descanso, me ~~entretuve~~recogiendo la auto-detonación: algo se arregló (resultó que las minas no deberían colocarse en la parte superior de las escaleras), agregó algunas contramedidas contra la detonación. Y reparó la simulación, porque hasta ahora la mía se aferraba a la esquina.

El comienzo de la segunda parte de la ronda final fue exitoso para mí, la brecha comenzó a crecer lentamente y alcanzó un máximo de aproximadamente 20 puntos. Incluso me relajé un poco y, en lugar de actualizar la página de resultados cada 3 minutos, comencé a jugar ajedrez por teléfono. Cuando volví a mirar, la brecha ya era de unos 7 puntos y luego rápidamente rodé al 1er. Me pregunto qué dan por el segundo lugar. 1 hora para el final, de nuevo hay una brecha. 30 minutos, la brecha se reduce catastróficamente. 10 minutos - ¡solo 3 puntos! Un minuto ... parece la victoria! Vanya perdió para mí solo 3 puntos. Esto está dentro de la dispersión aleatoria. El resto tiene 50 puntos o más de retraso.

Sobre bichos graciosos

Ya después de la final, noté que en algunos juegos mis unidades se comportan de manera extraña: no evitan las balas cuando, al parecer, podrían, e incluso, como si, las atraparan especialmente. Resultó que durante el descanso en la final, cometí un error: cuando se determinó si el enemigo podía hacerme explotar, era necesario calcular cuál de los míos estaba en el radio de la explosión. Aquí mezclé las coordenadas de mi propia unidad y la de otra persona y asumí por error que la explosión ocurriría donde estoy, y así garanticé que caería en el radio de la explosión. La verdadera explosión ya se consideró desde el punto correcto, por lo que en la simulación el enemigo mismo podría explotar lejos de mí. Por lo general, solo agrega una gran constante a la estimación, pero en realidad no afectó nada. Sin embargo, si el enemigo no tenía suficientes minas para hacerme explotar, resultó que era rentable para mí atrapar una balade modo que el enemigo ya tenía suficientes minas, y obtuve la adición a la evaluación. Tal vez se debió a la falta de sueño o a una lata de cerveza borracha, pero de hecho, siempre ocurren errores.

Conclusión

El juego, aunque no fue tan espectacular como el fútbol, no fue menos interesante desde el punto de vista de la estrategia. El umbral de entrada fue relativamente bajo, y esto afectó favorablemente el número de participantes. Recibí muchas emociones durante el mes del campeonato, tanto alegría como emociones, y por esto estoy agradecido con los organizadores. También agradezco a todos los participantes, especialmente a Vanya Tyamgina, por no aburrirme en la final.

Continuación de la participación (y la victoria) en la Copa AI rusa 2019