Segundo lugar en la historia de la Copa AI de Rusia 2018: CodeBall

Hola a todos!

Soy un estudiante de tercer año, y al comienzo de mis estudios en la universidad aprendí sobre la Copa Ai de Rusia , y más tarde la Mini Copa Ai , competiciones de inteligencia artificial, y comencé a participar activamente en ellas, mostrando buenos resultados. Esta vez, RAIC entró directamente en la sesión, por lo que nada podría detenerme :) Y hoy quiero contarles cómo logré tomar el segundo lugar.

Las reglas de la competencia se pueden encontrar en el sitio web de la competencia, así como en este artículo . Enlace a mi perfil: russianaicup.ru/profile/TonyK .

Por un lado, la tarea de este año fue similar a las tareas de años anteriores, y parecía que la solución ideológica sería muy similar a las anteriores (Agar IO y Mad Cars); después de aproximadamente una semana me aburriré y me cansaré de participar.

Por otro lado, entendí que había aprendido mucho en competencias anteriores con física y ahora puedo aplicar esta experiencia, no pisar el viejo rastrillo y, al final, mostrar un mejor resultado.

En cuanto a la visualización, decidí que tendría suficientes proyecciones en diferentes ejes, o mostraría en cierto ángulo. Pero estaba muy equivocado, y si no fuera por el visualizador mágico integrado en Local Runner, que los organizadores agregaron más tarde, tendría que tomar prestados visualizadores 3D de los amables participantes que pasaron la fase de prueba beta escribiéndolos y ponerlos en el dominio público.

Esta vez, el pseudocódigo del simulador estaba disponible, lo que igualaba las posibilidades de aquellos que sabían revertir la física y escribir un bot genial, y aquellos que no podían revertir la física, pero que también podían escribir un bot fuerte. Creo que fue una buena decisión de los organizadores.

Lo primero que hice fue reescribir el código del simulador de la documentación en C ++, y luego medí el tiempo del simulador en mi computadora anterior y en el servidor. En el segundo caso, resultó el doble de rápido, aunque esto era de esperar. Calculé cuántas veces y a qué profundidad podría simular. Inmediatamente quedó claro que uno tendría que olvidarse de la simulación honesta de 100 microtics (en el servidor, una marca de física se dividió en 100 "microtics"), y sería necesario resolver problemas con precisión en formas indirectas.

Debido al hecho de que el caparazón se organizó de tal manera que la solicitud de acción para cada robot se llama por separado en cada tic, implementé una lógica simple: en el momento en que se le solicita una acción al primer robot, el programa encuentra acciones para todos los robots, recuerda y da la acción del primero, y cuando la acción se le pide al resto de los robots, devuelve lo que recordaba.

Estaba impaciente por enviar el bot a la batalla pronto. Decidí generar trayectorias aleatorias y elegir la mejor. Al mismo tiempo, quería que el conjunto generado hiciera posible realizar algunas acciones complejas, por ejemplo, rodear la pelota desde el lado derecho y luego golpear.

Una trayectoria es un plan de acción. Inicialmente, la trayectoria fue esta:

• establecer la acción en un ángulo aleatorio;
• en un tic aleatorio de la trayectoria, cambie el ángulo a otro aleatorio;
• saltar una vez a un tic aleatorio de la trayectoria.

Tal espacio de trayectorias era una buena opción para la búsqueda aleatoria con el número de simulaciones que yo (y, probablemente, todos en ese momento) podía pagar con el simulador en bruto de la documentación. A menudo se adivinaron buenas trayectorias, y dado que se conservó la mejor trayectoria de la marca anterior, la búsqueda se extendió en el tiempo.

Todos los objetos fueron colocados en el simulador: mis robots, los robots del oponente y la pelota. La evaluación fue la más simple: la suma de las distancias desde la pelota hasta la portería enemiga en todos los puntos de la trayectoria y los grandes valores para la portería para alguien. Profundidad de simulación 200 ticks. Los enemigos se predicen a su última velocidad.



Inmediatamente agregué una acción separada para el segundo robot, así como la cancelación forzada del salto, si durante el vuelo no hubo contacto con la pelota, para no saltar en vano. Al mismo tiempo, mis robots superaron la mitad del tiempo y conocían la mejor trayectoria del otro. Ahora han comenzado los primeros goles para oponentes fuertes, que ya tenían un portero y una lógica más complicada.

Resultó que no consideré la distancia a las puertas enemigas, sino hasta el punto del centro del campo (mezclado x z ), pero esto no afectó la estrategia de ninguna manera. Es bueno que después de la corrección no haya empeorado. Esto sucede a menudo cuando escribes un bot.

Luego agregó al portero cambiando el marcador: impuso una penalización por el balón en mi mitad del campo y por el gol para mí, y también calculó la distancia del portero a mi gol. Ahora el portero se paró en la portería y noqueó la pelota. Una optimización importante fue que si el balón no está en mi mitad del campo, el 90% del tiempo se le da al atacante y el 10% del portero, de lo contrario, el 50%.

La evaluación de las trayectorias de los robots en cada punto se multiplicó por 0.9 ° de profundidad, deduje este coeficiente empíricamente, como todo el puntaje. Los valores de los coeficientes no cambiaron durante mucho tiempo según el principio de "funciona, está bien".

Comenzó a ganar los primeros puestos y a subir rápidamente en el ranking. La fase beta ha terminado.

Durante mucho tiempo no tuve ideas sobre la estrategia, las versiones fueron notables para ediciones menores, correcciones de errores (resultó que consideré la fuerza de rebote promedio como (MAX_HIT_E - MIN_HIT_E) / 2 ), y también (MAX_HIT_E - MIN_HIT_E) / 2 el simulador. El número de trayectorias que logré resolver por tick jugó un papel importante, así que me concentré en la optimización. Se quitaron los senos paranasales y las raíces cuadradas. Se agregó una velocidad cero improbable en la trayectoria antes o después de cambiar el ángulo. Puntaje ligeramente cambiado.

La versión 16 se mantuvo durante mucho tiempo en la parte superior de la tabla, pero una semana después del final de las pruebas beta, como se esperaba, muchos comenzaron a ganar .

Traté de ajustar la trayectoria con la suma de las distancias más cercanas del enemigo a la pelota, y obtuve un comportamiento muy interesante. Mis robots, cuando no podían golpear de manera rentable, a menudo comenzaron a bloquear enemigos, rompiendo sus trayectorias y evitando que corrieran hacia la pelota, a veces resultó con mucho éxito e insidiosa.

Luego, arreglé la precisión mientras saltaba. Si alguien salta sobre la marca actual, primero hacemos 1 microtik dos veces, y luego los 98 microtics restantes, y luego probé el coeficiente heurístico para compensar la pérdida de precisión en el caso cuando en algunos de los microtics se alcanza la velocidad máxima. Las mejoras fueron de gran ayuda y hubo resultados más precisos y precalculados.

También en este momento comencé a mostrar en el sitio, entre la información de depuración, el número de iteraciones que logré completar. Hubo 250 de ellos en 200 ticks, en total tuve 50,000 ticks de simulaciones durante el tiempo asignado para mi estrategia por tick.

Luego encendí las trayectorias de mutación. Esto mejoró enormemente la estrategia. En aproximadamente la mitad de todas las iteraciones, no se utilizó la nueva trayectoria, sino la mejor con valores ligeramente modificados, lo que permitió converger en algún lugar, por ejemplo, a un máximo local. Resultó ser una estrategia sólida en ese momento, que decidí dejar hasta la primera ronda, aunque todavía faltaban dos semanas para que finalizara. Pero después de un par de días dejó de dominar la cima.

Pasé un tiempo alejándome de la aleatoriedad completa, por ejemplo, intenté con una búsqueda ternaria para encontrar el ángulo en el que el robot necesita acelerar para golpear la pelota. Pero esto no siempre funcionó, y no descubrí cómo desarrollar más esta idea.

Mis robots sabían cómo saltar solo una vez por trayectoria, pero cuando estaban en el suelo y querían saltar, y luego golpear la pelota en el aire, no sabían que cuando tocas la pelota puedes saltar una segunda vez, golpeando así la pelota con fuerza, y no solo empujándolo.

Esto se solucionó, y ahora el simulador, cuando notó que alguien podía golpear la pelota con el tic actual, hizo retroceder un tic y obligó al robot a saltar con la máxima fuerza. Ahora, parado en el suelo, el robot sabía que empujaría del suelo y no solo empujaría, sino que golpearía la pelota con un segundo salto.

Entendí que cuando se agregaban nitro y otro robot, todo se doblaría debido a la falta de iteraciones. También en diferentes lugares tuve grandes problemas con la precisión, que no sabía cómo resolver. No vi ninguna solución analítica ni ninguna forma inteligente de gestión .

Necesitaba una estrategia completamente nueva o un simulador mágico que combine precisión y velocidad, y en la etapa final me proporcionará suficientes trayectorias para repetir. No se me ocurrió una nueva estrategia (sorprendentemente), y comencé a trabajar en un simulador.

"Simulador inteligente"

Lo primero que quería tratar con precisión.

Simulé 100 Mikrotiks a la vez, aunque se produjo una colisión, o algún otro evento, en uno de estos cien Mikrotiks. Si ignora esto, los objetos colisionan más tarde que en la realidad (siempre en el centésimo microtics) y, por lo tanto, rebotan de manera diferente. Hacia el final de la trayectoria, este pequeño error puede convertirse en una gran inexactitud. Por ejemplo, creemos que la pelota golpea la portería enemiga, pero en realidad rebotará en la nuestra desde el poste.

Es fácil ver que en una situación en la que se produce una colisión en el i ésimo microtics, en lugar de contar los 100 microtics, es suficiente contar los primeros i - 1 microtics a la vez (de hecho, el paso de física se considera durante un cierto tiempo dt , y ahora este tiempo será t * (i - 1) , donde t es el tiempo correspondiente a un Mikrotik). Ahora necesita simular 1 micrótico ( dt = t ) y los restantes 100 - i microtics. Obtenemos exactamente el mismo resultado en solo tres simulaciones en lugar de cien. El único problema es que no sabemos en qué microtics se producirá la colisión.

Al estar en un tic fijo de la simulación, podemos hacer cualquier número de microtics de 1 a 100 en una simulación y ver si hay una colisión o no. En este caso, la imagen será así: al principio no hay toque, pero a partir de un cierto número de micrófonos y hasta cien hay un toque. Excepto en casos muy raros, cuando no hay contacto al principio, luego hay un toque en algún segmento de los microtics, y luego nuevamente no hay contacto.

Por lo tanto, es posible encontrar el Mikrotik en el que ocurrió la colisión utilizando una búsqueda binaria de 10 simulaciones en el peor de los casos. Y como se describió anteriormente, para tres simulaciones, puede obtener el estado del mundo a través de 100 microtics con perfecta precisión.

De hecho, hubo varios otros tipos de eventos además de una colisión, y varios podrían ocurrir durante un tic, por lo que solo el primer evento se localizó con una dicotomía, luego el segundo evento se ubicó en el sufijo restante de la dicotomía del tic, y así sucesivamente. Por lo tanto, se consideró una marca como segmentos de varias microtics por simulación, hasta que se contaron todos los eventos.

Entonces los problemas se resolvieron con precisión. Pero debido al hecho de que había 5 objetos en la simulación, y según las reglas finales, debería haber habido 7, y todos ellos a menudo se bloquearon, en promedio las dicotomías fueron llamadas con demasiada frecuencia, y esto funcionó prohibitivamente por mucho tiempo. Por lo tanto, procedí a la segunda etapa del desarrollo del simulador: optimización.

Obviamente, cuando se supera la trayectoria de uno de los robots, todos los demás objetos en los que este robot no se estrella se mueven siempre de la misma manera. Está claro que no es necesario volver a calcular sus estados con un simulador, por ejemplo, calcular colisiones pesadas con la arena.

Antes de ordenar las trayectorias para un robot en particular, es suficiente simular honestamente y recordar para los objetos restantes sus estados en todo momento, y luego simplemente tomar estos estados de la memoria. Llamamos a tales objetos estáticos, y un robot para el que se ordena la trayectoria es dinámico.

Si de repente algún objeto dinámico influye (tiene una colisión) con uno estático, agregamos este objeto estático a los dinámicos hasta el final de la simulación de la trayectoria actual. De hecho, en la etapa de almacenamiento de estados para objetos estáticos, se construye un gráfico de influencias entre sí y luego se utiliza para transferir correctamente objetos estáticos a objetos dinámicos. Por ejemplo, un robot enemigo golpeó la pelota, y generamos un camino donde derribamos al robot enemigo antes de que golpee la pelota. Ahora la pelota volará más lejos, y durante la simulación, cuando se agregue el robot enemigo a los objetos dinámicos, es necesario tener en cuenta que la pelota se debe agregar a los objetos dinámicos un poco más tarde, en la marca en la que el robot enemigo golpearía la pelota si no interfiriéramos con ella. . En el caso general, esto se hace de forma recursiva de acuerdo con el gráfico de influencia.



Ahora el simulador no calcula todos los objetos, sino solo los dinámicos, y esto, en promedio, es un objeto y medio en lugar de siete, y las dicotomías largas se usan con mucha menos frecuencia. Resultó muy rápido y ya no tiene que sufrir en la final con robots adicionales, ¡genial!

La 26ª versión con un nuevo simulador y una profundidad de simulación reducida de 200 a 100 se envió a jugar en la primera ronda. Pero contenía algunos errores, y no había una ventaja obvia.

El último problema con la precisión permaneció: movimiento a lo largo del redondeo de la arena. En este caso, para lograr una precisión absoluta, es necesario contar honestamente 100 microtics. La solución fue sorprendentemente simple: saltar siempre desde todas las superficies excepto el piso. Sin redondeo, no hay problema.

Además, durante algún tiempo optimicé, debatí y, al mirar juegos con estrategias más inteligentes, recogí nuevas constantes de puntuación. Se ha vuelto mucho mejor, la estrategia se ha elevado en el ranking y la versión 37 ha logrado el mejor resultado de todas mis estrategias en el sandbox todo el tiempo antes de la final.

A partir de este momento, alquilé una máquina de 32 núcleos en un servicio en la nube para ejecutar mis estrategias entre sí, y comencé a experimentar mucho con todo en una fila. Cambió las constantes. Traté de usar mi propia estrategia para predecir las acciones del enemigo, pero esto no ayudó incluso en juegos contra mi estrategia.

Al resolver la ecuación, aprendió a calcular la última acción del enemigo y comenzó a predecir su comportamiento posterior. Se agregó soporte para nitro: se selecciona un punto aleatorio en la superficie de la esfera para la acción. Hizo muchas ediciones menores. Pero no hubo mucho progreso. Al comienzo de la segunda ronda, 4-5 tops me estaban ganando constantemente

Aún así, no me desespere. Tenía dos mejoras que planeaba implementar antes de la final, y esperaba que mejorarían enormemente la estrategia. Decidí no abordarlos hasta que el sandbox comenzara de acuerdo con las reglas finales, y en su lugar pasé un tiempo depurando y optimizando lo que ya se hizo para minimizar las posibilidades de errores malignos en la última semana, cuando cada minuto cuenta.

La última semana antes de que comenzara la final.

La primera mejora que hice fue esta. En los partidos, en el caso general, la mayoría de mis problemas, y cualquier otra estrategia surge cuando el oponente toma posesión de la pelota. De alguna manera lo golpea, pasa, en general, controles. Predecir la trayectoria de la pelota y planificar más acciones rentables en este caso es imposible, queda por hacer "lo que sea" hasta que el oponente cometa un error y transfiera el control de la pelota a mis robots. Y después de esto, debes tratar de no realizar acciones que puedan conducir al hecho de que la pelota volverá a estar con el enemigo.

En otras palabras, al momento de planificar la trayectoria, quiero tener en cuenta las posibles posiciones de los oponentes y tratar de no golpear la pelota allí. Decidí usar un campo potencial de cuatro dimensiones (las primeras tres dimensiones son las coordenadas, el lado de los cubos es igual al diámetro del robot y la cuarta dimensión es el tiempo), que completaré, generando trayectorias enemigas aleatorias.

Más tarde, al evaluar la trayectoria de mi robot, calculé la suma en todos los cubos que cruzaron la pelota en los puntos correspondientes en el tiempo, y la multipliqué por un coeficiente que supera todos los demás valores en la puntuación. Es decir, el campo potencial se tuvo en cuenta con la máxima prioridad después del objetivo. También permitió eliminar enemigos de la simulación después de los primeros 30 tics (el enemigo podía hacer cualquier cosa durante este tiempo mientras estaba en el suelo, y tales pronósticos distantes e inexactos solo interferían) si no estaban en el aire (parecía que nadie estaría en el aire aire para cambiar la trayectoria de una manera compleja usando nitro).

Al generar trayectorias aleatorias para el enemigo, fue posible averiguar el tiempo mínimo que le tomó golpear la pelota. Este valor fue útil para resolver el problema con los primeros saltos de mi portero fuera de la puerta. Me marcaron muchos goles porque mi portero saltó temprano y se volvió incontrolable en el aire. Después de eso, el enemigo predijo fácilmente cómo volaría mi portero y, si podía, cambió la trayectoria del balón antes de que mi portero lo alcanzara. Ahora cancelé el salto del portero si el enemigo puede golpear la pelota antes de lo que planea hacer mi portero.



Resultó que, sin un daño significativo a la estrategia, es posible calcular la trayectoria no con cada tic, sino a través de una. Al reducir a la mitad el tiempo de ejecución, dupliqué el número promedio de iteraciones. Un poco de magia sucede aquí. Parece que si contamos las trayectorias de cada segundo tic y duplicamos el número de iteraciones, entonces el número promedio de iteraciones no cambiará. Pero, de hecho, el simulador contará dos ticks (200 microtiks) por simulación en lugar de uno. Y las trayectorias ya serán 50, no 100 de profundidad, por eso el número promedio de iteraciones se duplicará.

Permaneció un par de días antes de la final. Aunque mi estrategia comenzó a conceder menos goles debido al buen control del balón, no comencé a anotar mejor. Por lo tanto, tuve que motivarla con un coeficiente cuando pronto para el gol de un oponente. Cuanto más rápido se marque un gol, mayor será la proporción. Y este coeficiente está creciendo mucho para superar el resto de la puntuación y no tener miedo del campo potencial, cuando, por ejemplo, quedan 10 marcas antes de la puntuación.

Se agregó un cálculo de dónde el enemigo está enviando nitro. Esto se hizo usando la fuerza bruta con un cierto paso. Además, el portero comenzó a reponer las reservas de nitro, cuando nada amenaza mi objetivo.

La segunda mejora importante fue usar minimax. Si el uso de diferentes fuerzas de impacto para el enemigo durante la construcción de trayectorias estáticas afecta el vuelo de la pelota, entonces durante la búsqueda se consideraron ambas opciones, con la fuerza de impacto máxima y mínima del enemigo, y se tomó el mínimo de las estimaciones.

En la final, tuve 7 opciones para trayectorias cuando el robot estaba en el suelo:

• 2 esquinas sin salto;
• 2 esquinas con un salto;
• 2 ángulos con salto y velocidad nitro codireccional;
• 2 ángulos con un salto y nitro compensa la gravedad;
• 1 esquina con un salto;
• 1 ángulo con salto y velocidad nitro codireccional;
• 1 esquina con un salto y nitro compensa la gravedad (no se usa debido a un error, se nota al escribir un artículo).

y dos opciones cuando el robot está en el aire:

• nitro a un punto aleatorio en la superficie de la esfera y fuerza de impacto aleatorio;
• Fuerza de impacto aleatorio.

Hubo competencia unas horas antes de la final, pero mi estrategia fue claramente mejor. Parecía que todo ya estaba hecho, que no había dormido más de un día y que nada dependía de mí. Quedaba por ver. Dos horas antes de la final, Andrei envió su grial recién horneado y ganó con éxito el primer lugar. La historia de su participación se puede encontrar aquí: habr.com/en/post/440398 .

En el intervalo entre las etapas de la final, agregué un campo potencial empujando el balón lejos de mi objetivo, independientemente de todo lo demás, y esto, como me pareció, me igualaba con Andrei. Pero ya era tarde, porque perdí 7 puntos en la primera mitad, e incluso 3/3 victorias en la segunda mitad no fueron suficientes.

RAIC es una competencia difícil y se otorgan premios a los participantes muy, muy difícil. Cuando un participante está en la cima de la mesa, para él esto no es solo entretenimiento, es una lucha. Hay muchas cosas pequeñas a tener en cuenta al escribir una estrategia sólida. Cada decisión tomada puede afectar significativamente el resultado.

El código fuente de la estrategia estará disponible aquí .