Historia de participación (y victoria) en la Copa AI rusa 2018 - CodeBall

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!

Source: https://habr.com/ru/post/440398/


All Articles