Era miércoles, había una reunión aburrida ordinaria en el trabajo. El diseñador se rascó detrás de la oreja y el probador se enterró en el teléfono. Un automóvil arrancó por la ventana y recibí una carta por teléfono: comenzó la
Russian AI Cup 2018 . Casi nadie sospechaba nada, y en ese momento ya sabía exactamente lo que haría en el próximo mes y medio.
Hola a todos, mi nombre es
Andrey Tokarev y me gustaría compartir mi experiencia de participar en la
Copa AI de Rusia 2018 .
Que es esto
Russian AI Cup es una competencia anual de inteligencia artificial que se celebra desde 2012. Aquí debe escribir un algoritmo que controle a alguien o algo, y estos alguien o algo compiten entre sí. Este año fue necesario controlar robots jugando al fútbol.
Ya tenía algo de experiencia jugando en tales competiciones. Particularmente, participé en la Russian AI Cup 2016 (sin premio) y en la Mini AI Cup 2018 (segundo lugar).
Vamos
En primer lugar, creé mis clases del mundo del juego, los objetos, tomé un vector 2D y 3D de competiciones pasadas y subí todo esto al repositorio de Git. Por supuesto, puede usar objetos del paquete de idioma, pero no hay vectores, no pueden modificarse, y de hecho es más conveniente usar sus propias clases. Lo que no reescribí es la clase arena, me quedaba como estaba, y no había necesidad de cambiarla.
Simulación
Aquí tenemos un mundo de juegos, ¿y qué podemos hacer al respecto?
Pero no resulta nada, hasta que podamos simular el mundo del juego, ni siquiera determinar si la pelota vuela hacia una red vacía. Entonces estamos descartando la simulación. El código de simulación no forma parte del paquete de idiomas, se proporciona en un idioma que no conozco. Pero su sintaxis C es similar, por lo que copiar-pegar + definición de las funciones necesarias, y el sim está listo al 90%. Donde era necesario gobernar mis manos, traté de hacerlo con cuidado, ya que los errores aquí pueden ser costosos y detectarlos no será fácil. Todavía logré cometer un par de errores, pero me costó un poco de sangre.
De inmediato se hizo evidente que si usa una simulación honesta (100 micro ticks), entonces esto no es suficiente, es mucho más rentable calcular 100 opciones con un micrótico que una opción con 100 microtiks. Todavía dejé 2 microtics para que la discrepancia no fuera demasiado grande.
Conceptos básicos de estrategia
Y así tenemos un mundo de juego y podemos simular su cambio. Entonces, ¿qué sigue?
Hay diferentes enfoques. Cuando hay pocos movimientos posibles y la profundidad no es muy grande, puedes tomarlo por la fuerza bruta: clasifica todos los movimientos, incluso los movimientos de retorno del oponente, tienen sus propios movimientos nuevamente ... minimax Cuando hay muchos movimientos, puede limitarlos artificialmente, por ejemplo, puede tomar direcciones que sean múltiplos de 15 grados, saltar a cada décima marca y usar el mismo minimax. Pero este enfoque me parece adecuado cuando el resultado no es demasiado sensible a pequeños cambios en los movimientos, aquí, una desviación de un grado en la dirección del robot conducirá a grandes desviaciones después de la colisión.
El otro extremo, cuando hacemos movimientos sin una búsqueda exhaustiva, es algún tipo de heurística. Este enfoque puede ser viable, pero crear un jugador de fútbol fuerte con heurística pura es muy difícil.
Pero la combinación de los dos métodos parece prometedora: primero puede moverse en una dirección aleatoria, y luego terminar el juego con una heurística que puede correr hacia la pelota y saltar en el momento adecuado. La misma combinación heurística se puede usar para predecir los movimientos del oponente. Anteriormente, ya usé algo similar en la competencia, y este método más o menos no resultó ser malo.
¡Y entonces escribimos heurística (en jerga RAIK-ovsky, chico inteligente o simplemente inteligente)!
Como quería ver el resultado lo más rápido posible, smartgay fue escrito a toda prisa y resultó ser bastante tonto (incluso el código es vergonzoso). Simplemente calculé el tiempo después del cual el robot puede atrapar la pelota en función de la velocidad actual de la pelota y la velocidad máxima del robot, y corrí hasta el punto donde la pelota estaría en ese momento (las colisiones no se tuvieron en cuenta). No sabía cómo saltar y ni siquiera tenía en cuenta la altura de la pelota, podía correr fácilmente debajo de la pelota, y si la pelota se alejaba demasiado rápido, generalmente corría en la dirección opuesta. Como Smart no pudo saltar, primero lo hice saltar a una distancia fija de la pelota, y un poco más tarde la elección del momento del salto recayó en los hombros de un gran azar. La falta de una elección racional de un salto resultó ser un gran inconveniente, pero más sobre eso más adelante. Pero en general, un smart limpio no se veía mal, y a veces incluso marcaba goles, aunque también en sus propios goles.
A continuación, necesitamos una función de evaluación (OF).
El OF inicial se veía así: (1000 - tick) * goal + ball.z + alguna función de la posición relativa del robot y la pelota para que corra hacia la pelota incluso si no puede alcanzarla. Aquí, el objetivo puede ser -1,0,1 dependiendo de si hay un objetivo y para quién, y tick es el tick desde el comienzo de la simulación en la que tuvo lugar el objetivo. Lo último es que el robot no pospone constantemente el objetivo.
Ahora hacemos que el robot corra en una dirección aleatoria un número aleatorio de ticks, luego transferimos el control al inteligente, que lo lleva a la pelota, en un momento aleatorio salta y
golpea la bola que falla. Además, es mejor correr no hacia el centro de la pelota, sino con un cambio aleatorio por una pequeña distancia, para que el robot pueda golpear en ángulo.
La simulación duró un tiempo fijo de 2 segundos, y al final se llamó al OF. Tal escenario se repitió varias veces para cada robot y se seleccionó el mejor en función de la calificación.
Hasta ahora, esta estrategia tiene un serio inconveniente: no tiene memoria: todo se calcula desde cero en cada tic, lo que significa que la estrategia puede ver un objetivo en un tic y no encontrarlo en el siguiente. Este no es el caso, debe solucionarlo: guardamos la mejor opción encontrada para cada robot y la reutilizamos en el siguiente tic. Además, ahora los robots están al tanto de los asuntos de los demás, por ejemplo, si el primero va a golpear la pelota, el segundo no corre tras la pelota, sino que intenta hacer un pase.
Portero
Necesitamos un portero. Mi portero era básicamente diferente del atacante en que se activaba cuando la pelota se acercaba a una cierta distancia a la meta, de lo contrario simplemente volvería a su punto base.
Resumen
Ahora tenemos una buena estrategia básica que puede hacer todo lo que sea necesario y que se pueda construir en el futuro.
Quizás todo lo descrito anteriormente parece simple y lógico, pero para ser honesto al comienzo de la competencia, no había una imagen tan clara de la estrategia que parecía más cercana al final, y tomó dos semanas implementar esto, y esto es 1/3 de la competencia.
Un poco sobre pruebas
Con el tiempo, los griales que duplican el poder del juego ocurrirán cada vez menos, y tendremos que elegir cambios que den un aumento de + 10-20% en los objetivos. Y luego resulta que ganancias tan pequeñas no son tan fáciles de identificar. Para obtener un resultado completo, necesita cientos de goles marcados, y con una frecuencia de gol de una vez por minuto, esto es muchas, muchas horas de tiempo de juego. Por esta razón, casi no probé estrategias en el servidor, pero conduje pruebas locales largas contra versiones anteriores. Pero incluso probar localmente cualquier cambio durante medio día no sería muy conveniente. Por lo tanto, apliqué un pequeño "truco": probé estrategias truncadas. Si, por ejemplo, en un servidor, revisé más de 50 opciones por robot, solo 10 localmente, esto me permitió ejecutar pruebas en un tiempo tolerable.
Mejoras
A continuación, describiré las principales mejoras y su evaluación en la siguiente forma: en cuánto porcentaje la nueva versión marca más goles de los que recibe de la anterior. Es decir si, por ejemplo, uno nuevo supera al anterior con un puntaje de 120: 100 es + 20%, si obtiene 2 veces más, entonces es + 100%.
- Su portero debe vencer a los goles. Si no tiene éxito, dele más tiempo, aumente el número de opciones hasta x10. + 15%
- A veces, cuando el portero golpea la pelota, sale en vuelo libre y aunque tiene tiempo de regresar a su lugar, ya marca un gol. Inmediatamente después de golpear la pelota, tratamos de devolverla a su lugar y agregar la marca a la que regresó a la evaluación con un pequeño coeficiente negativo. + 20%
- Una patada adicional en la pelota frente a la portería de otro aumenta la posibilidad de un gol, le daremos una bonificación en el OF por esto. + 60%
- ¡Experimenta con nitro! Quedaban unos días más hasta la primera ronda, pero decidí probar nitro por adelantado. Intuitivamente, me pareció que el nitro afectaría en gran medida el juego, ya que en un tanque puedes saltar al techo o volar sobre todo el campo. Para empezar, enseñé cómo usar nitro solo para el atacante, e incluso solo en el aire, pero aún no he recogido los paquetes. Nitro se usó durante el vuelo en la dirección ahora aleatoria ahora tridimensional. El resultado fue, por decirlo suavemente, no muy, no logré exprimir más del + 20%, y el uso de nitro en el suelo no arrojó ningún resultado. Por lo tanto, el problema con nitro se dejó de lado temporalmente, aunque desde este momento traté de realizar pruebas con nitro activado.
- Demasiado aleatorismo! El azar es bueno, por supuesto, a veces da trucos en los que ni siquiera puedes pensar, pero por otro lado, cuando hay demasiado de él, la probabilidad de que todo coincida es muy pequeña. Y tuve demasiado de eso. Decidí tratar de transferir el momento del salto a la base analítica. Como no había aceleración horizontal en el aire (olvídate del nitro), fue fácil calcular el momento en que el robot y la pelota se encuentran (t1), y la altura de la pelota en ese momento (h1). Ahora calculamos el tiempo (t2) después del cual el robot estará a una altura de h1, salta ahora. Aquí obtenemos una ecuación cuadrática, si no tiene solución o t2 <t1, entonces saltamos temprano, de lo contrario saltamos.
El resultado me sorprendió un poco, atornillando el salto correcto tanto al delantero como al portero, las pruebas mostraron + 200%, es decir La nueva versión venció a los viejos 3 veces en goles, ¡el verdadero Grial! Era el 17 de enero, después de haber subido la estrategia al servidor, ganó una calificación de más de 200 en una racha ganadora de 20 juegos y encabezó el sandbox por un tiempo.
- Enseñamos al portero a jugar. Hasta que mi portero se activó, se puso de pie como un pilar. Paseo lateral fácil: x = bola.x / 4 dio un ligero aumento.
- ¡El oponente no debe ser predicho, sino asumido! Mirando a través de los juegos, noté que a menudo obtengo un gol después de que el portero golpea la pelota directamente sobre el oponente y él marca un gol para mí sobre la marcha. Para golpear la pelota sin pasar por el oponente, primero debes determinar dónde puede estar en el enésimo tic. Por supuesto, no tomaremos en cuenta el nitro. Todavía podría determinar la velocidad del robot analíticamente, parece haber una intersección de dos círculos. Pero no pudo hacer frente al territorio accesible. Bueno, al diablo con él, somos programadores (no por educación), dejemos que la máquina cuente para nosotros. Divida el plano en n direcciones, mueva el robot en cada dirección, los puntos finales serán los vértices del polígono, que determina el alcance.
¿Cómo usarlo? Agregué una marca donde el oponente puede tocar la pelota por primera vez, con un buen coeficiente en la OF. Como ahora no es un escenario específico de acciones, pero se consideró una especie de nube de alcance para el oponente, eliminé los robots del enemigo tan pronto como entraron en contacto con el suelo.
Resultado + 40%. Además, este enfoque tiene dos grandes ventajas: la eliminación de robots enemigos en el primero acelera la simulación, y esto, a su vez, permite clasificar más opciones, y en el segundo no tenemos que molestarnos con el control del oponente. Conclusión: beneficio!
- Errores estúpidos, pero qué sin ellos. Hay dos líneas en el simulador oficial:
if abs(ball.position.z) > arena.depth / 2 + ball.radius: goal_scored()
No sé quién cómo, pero dejé la función abs () como está, pero en vano. La línea abs () (que no debe confundirse con std :: abs ()) toma valores enteros, lo que significa que los decimales se truncan. En la práctica, esto significa que grabé el gol solo cuando la pelota ya estaba a un metro de la línea de gol. Reemplace abs () con fabs ()! Esta no es la primera vez que este abs () me ha fallado.
- Nitro otra vez. Se acercaba la segunda ronda y no había ningún lugar para posponer el uso normal de nitro. Optimizó su uso, tuvo en cuenta la definición de un salto, permitió que se utilizara el portero y también comenzó a recoger deliberadamente paquetes por el portero.
- Volvamos a la simulación. Ya he dicho que 100 opciones con un microtik son más rentables que una opción con 100 microtics. Esto es cierto, pero esto no significa que con un Mikrotik todo esté bien, sin medidas adicionales las discrepancias eran bastante serias, y esto impidió jugar al fútbol a nivel profesional. Para mejorar la precisión de la simulación, apliqué los siguientes métodos:
- Durante el salto, dos Mikrotik adicionales.
- Cuando combinamos una gran cantidad de microtics, al movernos es más correcto usar la velocidad promedio, y no la final.
- Usando la búsqueda binaria, encontramos el tic en el cual ocurre la colisión, y realizamos dos sub-tácticas: una antes de la colisión, la otra después. (No tomé en cuenta la colisión de la pelota con una superficie plana, allí la discrepancia me pareció insignificante).
- Correr a lo largo de una superficie curva todavía causó grandes discrepancias y, a veces, el portero falló debido a esto. Por lo tanto, cuando mi portero estaba en una superficie curva, usé 10 microtics.
En promedio, se obtuvieron alrededor de 1.4 mikrotiks por garrapata, y la precisión estuvo cerca del ideal. Por supuesto, no atornillé estas optimizaciones a la vez, sino gradualmente. No sé cuánto influyeron en el poder del juego, pero creo que eso es muy significativo.
Que tenemos
Gracias a una gran cantidad de mejoras significativas, la estrategia creció constantemente en el ranking, y antes de la segunda ronda, casi alcanzó el hito histórico: la calificación de 5000 Elo, ganando terreno con confianza en primer lugar.
A veces ni siquiera puedes creer qué combinaciones se emiten al azar. Gracias a la amable comunidad anónima por el hallazgo.La semana pasada
En relación con un margen tan bueno, me permití no perseguir pequeñas mejoras, sino buscar algo más global, especialmente con respecto a los juegos 3x3. Sin embargo, los experimentos dirigidos a un juego de equipo más, o inculcar a un tercer jugador en un papel especial, o para enseñar al portero a salir durante el fracaso, fallaron. La semana entera pasó casi en vano. A pesar de esto, un par de días antes de la final, todavía estaba a la cabeza en el ranking.
Y ahora, el último día antes de la final llegó y empiezo a perder contra uno, luego otro e incluso un tercer competidor. Si no agrega, puede quedarse sin un premio. No pasó nada en toda la semana, ¿qué puedo hacer el último día? El estado de ánimo era, al menos, rendirse.
Resurrección
Después de ver un par de juegos perdidos, noté que todos saltan
como cabras en nitro, pasan la pelota en el aire, pero la mía no puede atraparla. Intenté lo más simple que puede conducir a este comportamiento: agregué la altura de la pelota en el momento del impacto con un coeficiente sólido en el OF. Resultado + 50%, ¡guau! Inspirado por el resultado, comencé a torcer los parámetros intensamente (que descuidé durante toda la competencia), agregué nuevas opciones de búsqueda, agregué control de tiempo al final, lo que me permitió usar el tiempo al máximo sin arriesgar mi vida. Al final del día resultó + 150-200%, es decir ¡La nueva versión superó a la anterior casi tres veces en goles! Sí, sí, el mismo que casi una semana antes de la final se hundió en primer lugar y alcanzó una calificación sin precedentes de 5000+ en la historia del campeonato. En el servidor, la estrategia se probó con éxito un par de horas antes de la final. Después de eso, lo preparé para el lanzamiento final: afirmaciones deshabilitadas, agregué verificaciones de división a cero, lo cargué nuevamente en el servidor y me cambié al modo de espera.
Final primera parte
La primera parte de la final tuvo lugar por la noche. Seguí los resultados hasta que me quedé dormido, me levanté temprano en la mañana. Se jugaron 3 oleadas (en una oleada cada una con cada una), perdí solo un juego contra
TonyK , y como Anton a veces todavía perdía ante otros jugadores, estaba a la cabeza con un margen de 7 puntos (2 puntos por la victoria). Una brecha bastante seria para 3 olas, pero no lo suficiente para relajarse.
El último día, por supuesto, no tenía la intención de hacer nada serio, básicamente torcí los parámetros. Se hicieron varios cambios, pero como todo se probó rápidamente, ni siquiera estaba completamente seguro de que el efecto fuera positivo. En general, el aumento fue del 0-20%. Pero Anton agregó significativamente y al menos comenzó a jugar no peor que yo.
Nada que hacer, tuve que enviar lo que es, y esperar suerte y un suministro de puntos.
Final parte dos
Afortunadamente, los juegos se ordenaron para que al principio los líderes jugaran entre ellos, por lo que no había necesidad de preocuparse, el primer juego fue contra TonyK. La suerte estaba de mi lado, gané la primera pelea, así como todos los otros juegos en esta ola, mientras que TonyK perdió un punto más. Es casi imposible jugar una brecha de 10 puntos para dos olas hasta el final, ahora era posible relajarse.
Resultado final: 352 victorias y 2 derrotas (ambas de Anton), 1er lugar con un margen de 12 puntos.
Gracias y otra basura
En general, me gustó mucho la tarea de este año, fue "para mí" (la simulación es mía, y la tridimensionalidad no me asusta) y los partidos fueron espectaculares, creo que fue interesante ver no solo a los participantes.
Me gustaría agradecer a los organizadores por la maravillosa competencia.
También quiero agradecer a todos los participantes, especialmente a Anton Kozlovsky (
TonyK ) por la competencia en la final, Ivan Tyamgin (
tyamgin ) por la competencia en el sandbox y Alexey Dichkovsky (
Commandos ) por abstenerse de participar y así aumentar mis posibilidades de ganar.
¡Buena suerte a todos en el próximo RAIK!