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 :)