Russian AI Cup 2018, historia 9 lugares

Entonces


Mi nombre, como el a√Īo pasado, es Andrei Rybalka, solo que esta vez tengo 33 a√Īos. Y, como estaba entre los diez primeros, decid√≠ compartir mi enfoque para escribir un bot de juego para la Copa AI rusa 2018 nuevamente.


Esta vez la tarea era f√ļtbol. La tarea en s√≠ misma recordaba un poco el RAIC 2014, cuando era hockey, pero la soluci√≥n fue completamente diferente.


Esta vez, el mundo era tridimensional y esta tridimensionalidad se utilizó por completo. El juego en sí era más una reminiscencia de la Rocket League .


No voy a aburrir la parte introductoria, es más fácil mostrar cómo se veía. Puedes ver los juegos en el sitio web o en el video:



Para que nuestra vida no parezca demasiado dulce, los desarrolladores, adem√°s del no determinismo del mundo del juego, tambi√©n dividieron el tic del juego en 100 subwoofers, que inicialmente pusieron fin a la simulaci√≥n precisa para la mayor√≠a de los participantes, y a√ļn m√°s para m√≠, con la intenci√≥n de escribir un bot en Java lento.


Además, debo decir que el campeonato se divide en rondas, lo que probablemente sería más correcto llamar rondas.


Brevemente sobre el sistema de torneos


Para empezar, se dan 2 semanas para el desarrollo. Luego pasa la primera ronda. Los 300 mejores van m√°s all√°.


Después de la ronda, las reglas del juego cambian (específicamente, se agrega nitro al juego) y se dan otras 2 semanas, después de lo cual pasa la segunda ronda.


Luego las reglas se complican nuevamente (se agrega el tercer jugador), se da otra semana y jugamos la final.


Pero este no es el final. Después de la final, hay otra semana, al final de la cual el sandbox simplemente se detiene, y también se otorgan los 6 mejores, excluyendo a los ganadores de la final. La diferencia fundamental entre el final del sandbox y el final del campeonato es que en el sandbox, los juegos se crean en un formato aleatorio, y no solo en el formato de la ronda actual.


Historias de participación


La parte técnica será más baja. Para quienes la historia no es interesante, puede desplazarse hacia abajo hasta que se vuelva buena.


Primera ronda


Comenzó, como la mayoría, con una semana de beta. Pasé mucho tiempo, más de 4 horas cada noche.
Antes de completar la primera versión, tomó varias iteraciones
codificamos hasta que comenzamos a superar la versión anterior, recopilamos, consideramos la versión actual de la anterior, repetimos .


No tenía prisa con el primer relleno y sucedió unos días antes de la ronda. Y, dado que, hasta ahora, mi bot no ha jugado con nadie, no tenía idea de en qué tipo de mundo estaba y qué posiciones en el ranking podría reclamar. Cuando vi que ya había ganado más de 100 juegos seguidos sin una sola pérdida, me tranquilicé.


En general, la primera derrota que tuve, al parecer, fue en el puesto 12, en el límite de tiempo, y el primer juego perdido en una fila ya estaba en el top 10.


En resumen, me di cuenta de que tengo posibilidades de entrar en la segunda ronda, donde van los 300 mejores.
Por lo tanto, no perseguí el puesto y no inundé nada más para la ronda, sino que simplemente continué trabajando.


En ese momento, vi que todavía había mucho espacio para mejorar sin conectar nitro (que apareció después de la primera ronda), así que me concentré en la parte principal de la estrategia, dándome cuenta de que antes de la segunda ronda habría más de 2 semanas o más y tendría tiempo para fijar el nitro.


Segunda ronda


La primera semana estaba programando activamente, pero todavía no conectaba nitro. Quería hacer esto en la segunda semana. Pero todo resultó diferente, porque al final de la primera semana había contraído neumonía. No pude programar, así que subí lo que era y, se puede decir, la participación activa en el campeonato para mí en este lugar había terminado.


Durante las siguientes 3 semanas antes del final del campeonato, trabajé en una estrategia por una cantidad de tal vez 20 horas.


Como resultado, en la segunda ronda, mi bot, en principio, no sabía que había nitro en el juego, pero de alguna manera todavía ocupó el puesto 16.


Final


En la final, se agregó un tercer jugador.


Escribí en Java lento, y no en C ++, ya que 7 de cada 8 personas son más altas que yo en la clasificación, y antes de eso mi bot a menudo caía en el tiempo de espera, por lo que con la llegada del tercer jugador, comenzó a caer en el 100% de los juegos. Afortunadamente, los juegos en el sandbox se crean en un formato aleatorio, por lo que automáticamente
perdió solo cada tercer juego y por lo tanto voló no demasiado. Parece haber caído al puesto 18.


Excepto por la programación, la edición de los coeficientes en la función de evaluación y la ejecución de las pruebas, luego, por primera vez, después del inicio de la enfermedad, me senté en el bot la noche del día anterior a la final. Agregó un nitro muy simple dirigido estrictamente hacia arriba para que dos atacantes dejaran de correr en el mismo punto y chocaran entre sí allí, y cortaran todo lo que pudieran para un juego de 3x3, comenzando desde la profundidad de renderizado y terminando con la precisión de la simulación, de modo que solo el bot no murió por tiempo de espera.
De esta forma, jugó el final.


En el intervalo entre las mitades de las finales, nuevamente me senté en el bot y pasé unas buenas horas 10. En su mayor parte, los cambios se referían a la selección dinámica de coeficientes, la interrupción temprana de la genética, etc. En general, estaba buscando un equilibrio entre la precisión y la profundidad y la velocidad de cálculo erróneo.
Adem√°s de la lucha contra la velocidad, hizo un par de cambios m√°s:


  • Envi√≥ a un atacante distante (relativo a la pelota) a un punto en el medio entre la pelota y la porter√≠a del oponente
  • Arregl√© un poco el nitro (la descripci√≥n estar√° en la parte t√©cnica). Todav√≠a era extremadamente simple, pero se volvi√≥ mucho m√°s eficiente.

Total, después de ejecutar las pruebas y ver el puntaje 395: 254 contra la versión anterior, me tranquilicé al respecto. Esto me permitió tomar el noveno lugar en la final.


Sandbox Finale


Continué doliendo y no trabajé en el bot durante la mayor parte de la semana. El día antes del final, vi que varias personas subieron versiones nuevas, que a menudo ganan contra mí y pueden arrojar cajas de arena de los premios. Así que pasé un par de horas más.


El √ļnico cambio importante es que desenterr√© mi rama en Git hace tres semanas, en la que tuve una simulaci√≥n del movimiento del enemigo usando mi algoritmo simplificado. En ese momento funcion√≥ mal, pero lo record√©, realic√© pruebas, vi
que supera a la versión anterior casi se duplicó e inundó. Total, al momento de parar, estaba en el décimo lugar en la tabla general, que corresponde al 4to en la final de la caja de arena.


Cómo funciona todo (parte técnica)


Pido disculpas por adelantado en caso de que haya imprecisiones en la terminolog√≠a. Adem√°s, escribo de memoria, por lo que es posible que en alg√ļn lugar no describa la versi√≥n final.


Entonces, los algoritmos gen√©ticos est√°n en el n√ļcleo. El cromosoma consta de varios genes:


  • N√ļmero fraccionario en el rango -PI..PI, que especifica la direcci√≥n del movimiento
  • Un entero en el rango 0..10 que especifica el n√ļmero de repeticiones de esta acci√≥n.
  • N√ļmero fraccionario de 0 a 1. Si el valor est√° por encima de alg√ļn umbral, realice un salto

El genotipo puede incluir un n√ļmero diferente de cromosomas, pero de tal manera que el n√ļmero total de acciones (incluidas las repeticiones) es 40.


Inicialmente, creo varias docenas de genotipos aleatorios. A ellos agrego:


  • La trayectoria justo en la pelota
  • Trayectorias directas en todas las direcciones, solo 10 piezas con un desplazamiento de 36 grados
  • Un genotipo que simplemente no hace nada (sin √©l, el bot siempre se ejecuta en alg√ļn lugar, incluso si ya se encuentra en el punto √≥ptimo)
  • El mejor genotipo de la marca anterior

Entonces todo se simula y se ejecuta a través de la función de evaluación. N mejores genotipos "sobreviven" y se clonan M veces con mutaciones. Tras la mutación, cada gen cambia en un rango dado con una probabilidad del 10%. Bueno, esto se ha repetido por varias generaciones.
No hay cruce, en este problema no veo ning√ļn sentido.


En total, el n√ļmero m√°ximo posible de trayectorias por tic por jugador de f√ļtbol fue de aproximadamente 800, pero de hecho, en la mayor√≠a de los casos fue mucho menor, porque En algunos casos (por ejemplo, cuando en el futuro cercano no podremos tocar la pelota), el movimiento de los jugadores fue reemplazado por una simple heur√≠stica. Adem√°s, N, M y el n√ļmero de generaciones depend√≠an de la situaci√≥n en el campo. En primer lugar, desde la distancia hasta la pelota. Adem√°s, el error de c√°lculo se interrumpe antes de lo previsto (pero no antes de la 5¬™ generaci√≥n) si se encuentra una trayectoria con una estimaci√≥n aceptable.


Macro


El portero corre hacia el punto frente al centro de la portería. Mis pruebas mostraron que es mejor para mí jugar parado frente a la portería, y no dentro de ellas, como la mayoría de los jugadores en la parte superior.


La posición del punto se desvió del centro dependiendo de varios factores: la posición y dirección del vuelo de la pelota, el punto en que la pelota golpeó mi objetivo, si se planificó un gol, la ubicación del oponente atacante más cercano, etc.


Si la pelota est√° del lado del oponente y vuela hacia su objetivo, podemos ir por nitro.


Si mi portero puede golpear la pelota antes que mi atacante (más algunas condiciones más), entonces el atacante ignora la pelota y corre hacia un punto en el medio entre la pelota y la portería del oponente. Pasé por muchas opciones, donde exactamente para él correr. En mi caso, este funcionó mejor.


De lo contrario, si la pelota está demasiado lejos, el atacante corre en línea recta hasta el punto de contacto más cercano de la pelota con el piso, en el que puede interceptar la pelota (si no tenemos tiempo para el primer punto de contacto, verifique el siguiente, etc.)


De lo contrario (cuando la pelota llega), el atacante corre hacia donde la función de evaluación le dice. Sí, y también, si el nitro se encuentra cerca y podemos recogerlo, lo seleccionamos.


En un juego de 3x3, es m√°s probable que el segundo atacante apunte a la pelota y con menos carrera hacia adelante, esperando un pase del portero. Pero si a√ļn funciona, entonces se elige otro punto, m√°s cerca de la l√≠nea central.


Además, cada tic simuló una vez la pelota 100 ticks hacia adelante con 100 microtics (con almacenamiento en caché).


Esta trayectoria ha sido utilizada en muchos lugares. Por ejemplo:


  • Para determinar los puntos de contacto de la pelota con el piso
  • Para saber si la pelota amenaza mi gol y si el portero necesita cambiar al modo de simulaci√≥n

Se utiliz√≥ la misma trayectoria exacta en la simulaci√≥n de las trayectorias de los jugadores, para no contar la pelota cada vez. Pero solo hasta la primera colisi√≥n del bal√≥n con cualquier jugador de f√ļtbol.


Por cierto, escribir Footballist era vago, las palabras Player, Robot estaban reservadas por estrategia,
entonces mi clase de contenedor simplemente se llamaba Dude :)


Simulación


En la mayoría de los casos, fue con un micrótico, pero en algunas situaciones cambió al modo preciso con una gran cantidad de micrófonos (al principio era 100, luego se redujo a 50 en un juego 2x2, porque las pruebas mostraron que la diferencia en los resultados estaba dentro del margen de error, y a 10 en 3x3, porque de lo contrario voló en tiempos de espera).


En el modo preciso, cambi√© al momento de rebotar o al estar tan cerca de la pelota que es posible una colisi√≥n en el siguiente tic. Adem√°s, tambi√©n hab√≠a una gran cantidad de peque√Īas muletas, hacks, optimizaciones, en las que yo mismo no lo entender√©.


Por ejemplo, la bola voladora todavía se simulaba con 1 Mikrotik, pero si después del siguiente Mikrotik vi que había una colisión, volvía a la posición anterior y la volvía a simular con mayor precisión.


Además, también fingí ser otros jugadores (tanto los míos como los míos) si estuvieran en el aire (y, por lo tanto, su trayectoria es más fácil de predecir), o si estuvieran cerca de la pelota. Para los oponentes, la versión final utilizaba una versión simplificada de mi propia estrategia de toma de decisiones, que se lanzaba cada 5 ticks (más a menudo no permitía la velocidad).


Al simular cada personaje, calcul√©, la pelota y otros jugadores de f√ļtbol 40 ticks por delante (mi l√≠mite en la cantidad de acciones en el genotipo) y luego simul√© la misma cantidad de ticks solo una pelota.


Nitro


Simple a indecente.


En la versi√≥n final, nitro siempre est√° activado si lo est√°, si el jugador est√° en el aire y si no ha golpeado la pelota en los √ļltimos ticks.


Al principio, siempre dirigía el nitro hacia arriba, pero luego intenté experimentar y la opción de ir exactamente al centro de la pelota funcionó mejor. También probé opciones para que la dirección del nitro fuera elegida por la genética.


Funcion√≥ mucho peor. Quiz√°s debido a la falta de profundidad de b√ļsqueda.


Función de calificación


La suma de las puntuaciones para cada tic con la atenuación del 2% por tic.


El mayor peso, por supuesto, tenía un objetivo. Varias cosas influyeron en su peso:


  • La distancia desde la pelota hasta el portero enemigo en el momento del gol (cuanto m√°s lejos mejor)
  • Coordenada Y de la pelota (porque en la parte superior de la porter√≠a es mucho m√°s dif√≠cil golpear)
  • La velocidad de la pelota a lo largo del eje Z (que se dirige hacia la porter√≠a enemiga)

Al atacarme, todo es exactamente igual, solo que con el signo opuesto.


Además, para el atacante, la puntuación general dependía de:


  • Distancias del jugador a la pelota (para que corra hacia la pelota incluso si no puede golpearlo)
  • Penalizaci√≥n por el salto (saltar solo si trae tantos puntos que superar√°n esta penalizaci√≥n)
  • Distancias en el pr√≥ximo tic de la simulaci√≥n desde la pelota hasta los oponentes.
  • Coordenadas de la bola Y (cuanto m√°s alto es, menos posibilidades tiene el enemigo de interceptarlo)
  • Coseno del √°ngulo entre la direcci√≥n de la pelota y el centro de la porter√≠a enemiga.
  • Marcar si toqu√© la pelota
  • Bandera, si el enemigo toc√≥ la pelota
  • Bonificaci√≥n por la selecci√≥n de nitro

Adem√°s, hab√≠a una peque√Īa bonificaci√≥n por golpear a un jugador enemigo. Aunque, de hecho, ha sucedido, pero rara vez.


Para el portero:


  • Bonificaci√≥n por distancia a la pelota, velocidad de la pelota en Z, posici√≥n de la pelota en Y
  • Penalidad por el salto
  • Penalizaci√≥n por encontrar el bal√≥n en el √°rea frente a mi porter√≠a
  • Se tuvo en cuenta la distancia a los enemigos y a mis atacantes (para que la pelota vuele lejos de los enemigos, pero, si es posible, vuela m√°s cerca de mis atacantes)
  • Y algunas cositas m√°s.

Aprendizaje autom√°tico


Fue solo un poco en una de las ramas del git como experimento. Pero me parece digno de mencionar de todos modos. No logré recordarlo (y no estoy seguro de qué tiene sentido).


En general, traté de predecir con su ayuda si el enemigo puede interceptar la pelota en función de las posiciones y velocidades del enemigo y la pelota. Planeaba usar esto en la función de evaluación. Penalizar las trayectorias que son posibles de interceptar.


Pero comprendí de inmediato que no podía permitirme no solo una red neuronal, sino nada serio, porque esto tendría que hacerse 80 veces por trayectoria. Bueno, incluso si son 40 o 20, si no se cuenta cada tic, pero de todos modos, no tenía ninguna reserva de tiempo, por lo que ni siquiera consideré estas opciones.


Esto es lo que hice:


Ejecuté varios juegos con un bot modificado, en el que, al buscar una trayectoria, guardaba datos sobre mí y la pelota, así como una bandera, si se encontró una trayectoria en la que intercepto la pelota.


Consider√© todas las coordenadas relativas al jugador de f√ļtbol. Es decir Siempre lo tuve en la coordenada [0,0,0], as√≠ que mantuve solo 10 campos: la posici√≥n relativa de la pelota, el vector de velocidad de la pelota, el vector de velocidad del jugador de f√ļtbol, ‚Äč‚Äčla bandera de intercepci√≥n binaria. Guard√© el conjunto de datos solo para la parte central del campo, porque Me di cuenta de que los algoritmos simples a√ļn no funcionan y que representan los tableros.


Luego alimente este conjunto de datos DecisionTreeClassifier con max_depth = 7. El árbol entrenado dio una precisión, por lo que recuerdo, del orden del 90%.


Luego, exporté el árbol a un conjunto de ifs (que es esencialmente DecisionTree).


Se parecía a esto:


public static boolean predict(double dude_vel_x, double dude_vel_y, double dude_vel_z, double ball_rel_pos_x, double ball_rel_pos_y, double ball_rel_pos_z, double ball_vel_x, double ball_vel_y, double ball_vel_z) { if (ball_vel_z <= 6.4765448570251465) { if (dude_vel_y <= -6.087389945983887) { if (ball_vel_z <= -20.188323974609375) { if (dude_vel_x <= 13.032730102539062) { if (ball_rel_pos_y <= -1.1829500198364258) { return ball_vel_y <= 18.906089782714844; } else { return false; } } else { return true; } } else { // ............................ 

En esta etapa, realicé las pruebas, no vi ninguna mejora y pospuse la prueba hasta más tarde, que, debido a mis aventuras, nunca llegó.


Schroedinbag


En alg√ļn lugar despu√©s de la primera ronda, atrap√© a este extra√Īo animal en mi casa.


Quién no sabe, este es un error que solo encuentran al leer el código, y al encontrarlo, el desarrollador se pregunta cómo podría funcionar el programa. Y en mi caso, ella también se mantuvo en el top 10.


En general, el error fue que se llamó a un constructor en la función de copia del gen, en el que se omitió un argumento opcional que contenía el valor de este gen. En ausencia de este argumento, el valor se seleccionó al azar. Por lo tanto, al intentar copiar un gen, en lugar de una copia, creó una nueva instancia aleatoria.


De hecho, en lugar de la gen√©tica, tuve una b√ļsqueda aleatoria, porque cada marca simplemente generaba varios cientos de rutas aleatorias y seleccionaba la mejor.


Después de la corrección (que consiste en agregar 2 caracteres al código), el juego se volvió aproximadamente 3 veces mejor.


Baile ritual


En alg√ļn momento, not√© que los jugadores a veces rebotan sin raz√≥n, lejos de la pelota, a pesar de la penalizaci√≥n.


La explicación resultó ser tal que conté el momento del salto con una precisión de 100 microtics. Y a veces resultó que justo en el momento del salto hubo una colisión de la pelota con la barra. Y dependiendo de la precisión del cálculo precisamente en este tic, la trayectoria propuesta llevó a una meta o no.


En t√©rminos generales, la pelota vuela hacia la meta del oponente y golpea el poste. mi jugador de f√ļtbol, ‚Äč‚Äčcorriendo en el otro extremo del campo, simula una trayectoria sin salto (con 1 mikrotik) y ve que la pelota no golpea la porter√≠a.


Luego entra otra trayectoria, con un salto exactamente en el momento en que la pelota golpea la barra. Y dado que cuento una marca con un salto de 100 microtics no solo para un jugador de f√ļtbol, ‚Äč‚Äčsino tambi√©n para una pelota, el √°ngulo de rebote calculado de la pelota difiere del √°ngulo obtenido en el camino con 1 micr√≥tico, y puede suceder que la pelota en esta trayectoria m√°s precisa caiga en La puerta.


Y por lo tanto, es esta trayectoria la que se seleccionar√° y el bot saltar√°.


En general, al realizar un baile ritual con rebotes, los jugadores namanizaron un gol :)


Característica asesina


Ella no es


Prueba


Conduje juegos interminables en 8 hilos (4 en cada computadora y computadora port√°til). Eleg√≠ el n√ļmero de juegos para que fuera estad√≠sticamente significativo.


Con una mejora significativa en la estrategia podría satisfacerse con medio millar de objetivos en total,
con correcciones m√°s peque√Īas, se fueron por la noche y luego la factura fue de miles.


Selección genética de constantes.


Lo intenté antes de la primera ronda. No dio nada por la razón de que para la genética necesitas jugar un torneo de una gran cantidad de juegos.


Trat√© de jugar juegos de 100,000 ticks, pero eso no fue suficiente. Con una peque√Īa diferencia en la fuerza (y generalmente al elegir constantes, este es exactamente el caso), el ganador por 100k ticks depende demasiado del caso. Necesitas jugar mucho m√°s para estar seguro del ganador. Y no pod√≠a permitirme dejar la selecci√≥n por un d√≠a o m√°s, as√≠ que rechac√© esta aventura.


En conclusión


Tradicional gracias a los organizadores. La tarea fue interesante. Es una pena que me haya obligado a perder casi la mitad del campeonato y realmente no haya hecho nada ni por nitro ni por tres jugadores.


Como resultado, hasta el final vi en el sandbox cómo mi estrategia gana en modo 2x2 sin nitro con un puntaje de 13: 2 contra cualquier Mr.Smile, que ocupó el 3er lugar en la final, y después de algunos juegos pierde para él el mismo 12: 2 en modo 3x3 con nitro :)


Y, por supuesto, el video de mi visualizador propietario:



Solo que probablemente tendr√°s que despedirte de este visualizador en futuros campeonatos.
Cada vez estoy m√°s y m√°s convencido de que si est√°s solicitando lugares normales, la √ļnica opci√≥n es escribir ...



... bueno, entiendes el punto.


Cansado cada vez de descansar en la lentitud de Java y reducir la fuerza de la estrategia para cumplir con el tiempo asignado.


Espero que alguien haya encontrado algo interesante o √ļtil en esta obra m√≠a con una nota de car√°cter autobiogr√°fico :)

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


All Articles