A principios de otoño, se completó la competencia para escribir bots Mini AI Cup # 3 (también conocida como Mad Cars), en la que los participantes tuvieron que pelear en autos. Los participantes discutieron mucho sobre lo que funcionará y lo que no funcionará, las ideas se expresaron y probaron desde simples ifs hasta redes neuronales de entrenamiento, pero los chicos ocuparon los primeros lugares con la llamada "simulación". Intentemos averiguar qué es, comparar soluciones para el 1er, 3er y 4to lugar y discutir otras posibles soluciones.

Descargo de responsabilidad

El artículo fue escrito en colaboración con Alexei Dichkovsky (Comandos) y Vladimir Kiselev (Valdemar) .

Para aquellos que solo quieren leer sobre las decisiones de los ganadores, les aconsejo que comiencen de inmediato con el ítem "Simulación".

Declaración del problema.

Esta vez, la mecánica del mundo era muy parecida al juego móvil Drive Ahead: a los jugadores se les dio un automóvil con un botón ubicado en él; la tarea es presionar el botón del enemigo más rápido que él. Si nadie gana en 600 ticks de juego, la carta comienza a hundirse en una pila de basura, que también puede presionar un botón. En otras palabras, debes proteger tu botón de los enemigos, el mundo que te rodea y un montón de basura (vitalmente, sí). A cada jugador se le dieron 5 vidas, el juego pasó de 5 a 9 rondas, mientras que alguien no terminó sus vidas. Cada ronda se llevó a cabo en un mapa aleatorio y automóviles, lo mismo para ambos participantes. En total había 6 cartas diferentes y 3 tipos de autos, un total de 18 combinaciones diferentes.

Cada ronda se divide en garrapatas. Una marca es un movimiento, como en el ajedrez. La única diferencia es que ambos jugadores van al mismo tiempo. Hay competiciones donde todos se turnan, o puedes hacer una acción solo una vez cada pocos movimientos y seleccionar unidades como marco .
Cada tic en el bot llega a un estado de paz y se le da la oportunidad de realizar 3 acciones: , , . Estas acciones hacen que el automóvil vaya en una de las direcciones, y si al mismo tiempo no toca las ruedas de la tierra, entonces le dan una pequeña rotación a todo el cuerpo (un poco de física arcade). Después de que ambos oponentes hayan elegido una acción, se inicia una simulación del mundo del juego, se considera un nuevo estado y se envía a los jugadores. Si alguien hizo clic en un botón, la ronda finaliza y comienza la siguiente. Todo es simple, pero hay matices.

Reglas más completas se pueden encontrar aquí . Y mira los juegos finales aquí .

Descripción general de la solución

La mayoría de las competiciones de escritura de bot son muy similares: hay un número finito de ticks (hay aproximadamente 1,500 como máximo para una ronda), hay un número finito de acciones posibles, debes elegir una secuencia de acciones para ser mejor que tus oponentes. Un poco más tarde volveremos a lo que significa ser mejor, pero por ahora descubriremos cómo lidiar con el problema principal: una gran cantidad de opciones: al principio tenemos un estado inicial, luego cada máquina puede moverse de tres maneras diferentes, que nos da 9 combinaciones diferentes para dos autos, para el movimiento 1500 será 9 ^ 1500 combinaciones diferentes ... Lo cual es un poco más de lo que nos gustaría si planeamos resolverlos durante la existencia del Universo.

Aquí llegamos a lo que es la simulación . Este no es algún tipo de algoritmo, sino simplemente una recreación de las reglas del juego con precisión suficiente o completa para que sea posible clasificar las soluciones. Por supuesto, no analizaremos todas las soluciones, sino solo una parte de ellas. Se utilizará un algoritmo de búsqueda para esto: en el árbol de estado del juego estamos buscando lo mejor para nosotros. Hay muchos algoritmos (desde minimax hasta MCTS), cada uno tiene sus propios matices. Es mejor familiarizarse con las decisiones que escribieron los participantes en competencias pasadas de IA. Esto proporcionará una comprensión básica de en qué condiciones funcionan los algoritmos y en qué no. Hay muchos enlaces para esto en un repositorio especial .

Al elegir un algoritmo, debe considerar:

límite de tiempo para 1 marca (aquí calculé mal mucho este año, pero pude permanecer en el 3er lugar);
Número de jugadores. Por ejemplo, si hay tres jugadores, será difícil usar minimax;
precisión de simulación, como esto puede permitir la reutilización de cálculos antiguos;
"Ramificación" del árbol de estado (es posible calcular todos los estados posibles al menos 10 movimientos adelante);
sentido común: no comience a escribir MCTS si la competencia dura 4 horas.

En esta competencia, 1 tick dio alrededor de 10-13 ms (2 minutos para todo el juego). Durante este tiempo, el bot tuvo que leer los datos, tomar una decisión y enviar un comando para moverse. Esto fue suficiente para estimular unos 500-1000 movimientos. Iterar sobre todos los estados. El algoritmo de búsqueda más simple puede parecer una comparación de tres opciones de movimiento: "50 ticks van a la izquierda", "50 ticks van a la derecha", "50 ticks clic en detener". Y no importa cuán simple suene, no está muy lejos de la decisión del ganador.

Porque solo contamos 50 movimientos por delante, que en la mayoría de los casos no cuentan hasta el final del juego, entonces necesitamos una función de evaluación que diga cuán bueno y malo es el estado del mundo para nosotros. Muy a menudo, se basa en la heurística y en la comprensión de lo que es importante para la victoria. Por ejemplo, en la competencia rusa de la Copa AI de 2014 hubo carreras, pero podría ganar si llegara el último, si obtiene más puntos de bonificación. Por lo tanto, la función de calificación debería estimular la recolección de puntos al mismo tiempo que el movimiento rápido a lo largo de la carretera. La puntuación solo se puede calcular para el último estado de la simulación (después de 50 ticks) o como la suma de las estimaciones de los estados intermedios. A menudo, la estimación "se desvanece" a tiempo para que los estados que ocurren antes estén más influenciados. Porque no podemos predecir con seguridad al enemigo, entonces es menos probable que ocurran opciones futuras, no confiaremos en gran medida en ellas. Además, esta técnica hace que el bot sea más rápido para completar sus tareas y no posponer todo para más adelante. Pero vale la pena señalar que el bot tomará menos riesgos en aras de los beneficios posteriores.

Como vamos a predecir el estado del mundo en respuesta a nuestras acciones, necesitamos modelar de alguna manera el comportamiento de los enemigos. No hay nada complicado y hay un par de opciones comunes:

Trozo o heurístico
Se escribe una lógica simple de comportamiento donde el enemigo simplemente no hace nada, o elige acciones basadas en heurísticas simples (por ejemplo, puede usar sus primeras versiones de la estrategia o simplemente repetir el movimiento anterior del oponente).
Usa el mismo algoritmo que tú mismo
Primero intentamos encontrar las mejores acciones para el enemigo (contra nuestro mejor conjunto de acciones desde el último movimiento, o contra un trozo), y luego buscamos la mejor acción para nosotros mismos, utilizando el comportamiento que encontró el enemigo. Aquí el bot intentará resistir a los enemigos difíciles. Esta lógica no funciona bien al comienzo de la competencia, porque muchos bots siguen siendo muy débiles, y tu decisión será demasiado cautelosa con ellos.
Otros
El mismo minimax itera sobre todos los movimientos de los jugadores al mismo tiempo, y él simplemente no necesitará heurística.

Si implementa todos los pasos anteriores, lo más probable es que obtenga un bot muy bueno, especialmente si puede elegir una buena función de calificación. Pero, mirando a través de sus peleas, puedes ver que en ciertas situaciones se comporta de manera extraña. Corregir la función de evaluación para estas situaciones puede ser difícil o existe un gran riesgo de romper otra lógica. Aquí muletas y si vienen al rescate. Sí, los últimos días de la competencia a menudo se reducen a escribir muletas y ifs para corregir los defectos en cualquier condición específica. Personalmente, realmente no me gusta esta parte, pero he notado más de una vez que son las muletas en la final las que pueden afectar la disposición de los lugares entre los diez primeros, lo que significa que un no escrito puede costarle un premio (mi corazón duele cuando escribo estas palabras, yo También amo hermosos algoritmos y soluciones).

P: ¿Es posible prescindir de la simulación?
R: Sí, puede usar soluciones en heurística (árboles de decisión, un montón de ifs, etc.). Hay un buen artículo con arquitecturas de IA sobre heurística.

P: ¿Cuánto mejor es el uso de la simulación que los enfoques heurísticos?
A: Todo depende de la tarea. Por ejemplo, aquí algunas combinaciones de cartas y autos podrían codificarse con ifs y siempre ganar (o robar). Sin embargo, a menudo la simulación encuentra soluciones que son difíciles de pensar por sí mismas o difíciles de implementar heurísticas. En este concurso, cuando volteas otro auto, las soluciones en las simulaciones ponen su rueda sobre la rueda del enemigo, que apaga la bandera "en el aire", lo que significa que el enemigo no puede aplicar la rotación del cuerpo y girar sobre las ruedas. Pero la decisión no pensó en el significado de esto, solo encontró opciones donde el enemigo caería más rápido en el techo y presionaría su botón.

P: ¿Redes neuronales y RL?
R: No importa cuán popular sea esto, en las competiciones de bot tales soluciones rara vez funcionan bien. Aunque las redes neuronales no necesitan simulación, porque simplemente pueden emitir una acción basada en los parámetros de entrada del estado actual, aún necesitan aprender algo, y para esto a menudo tienen que escribir un simulador para manejar miles de juegos localmente. Personalmente, creo que tienen potencial. Quizás puedan resolver parte del problema o utilizarlo en condiciones de tiempo de respuesta muy limitado.

Nota
Con respecto al número finito de acciones posibles, vale la pena aclarar que a veces se permite ajustar "sin problemas" algún parámetro. Por ejemplo, no solo conduce hacia adelante, sino con cierto porcentaje de potencia. En este caso, la "finitud" del número de conclusiones puede lograrse fácilmente simplemente usando varios valores, por ejemplo, 0%, 25%, 50%, 75% y 100%. Muy a menudo, solo dos son suficientes: "completamente encendido" y "completamente apagado".

Simulación

En esta competencia, utilizamos el motor de física de ardilla lista para usar. Las expectativas de los organizadores eran que él es viejo, probado en el tiempo y tiene muchos envoltorios para que todos puedan incluirlo en su decisión ...

En la dura realidad, el motor produce diferentes valores cada vez, lo que dificulta el reinicio para calcular las opciones de movimientos. El problema se resolvió "de frente": se escribió un asignador de memoria en C y se copió completamente un fragmento de memoria con el estado del mundo. Tal asignador puso fin a la capacidad de escribir soluciones en lenguajes distintos de C ++ (de hecho, era posible, pero muy laborioso y un asignador aún tendría que escribirse en C). Además, la precisión de la predicción estuvo influenciada por el orden de agregar elementos al mundo del juego, que requería una copia muy precisa del código que los organizadores utilizaron para calcular los juegos. Pero él ya estaba en Python. El último aspecto destacado en el ataúd de otros lenguajes de programación fue que el motor es antiguo y contiene muchas optimizaciones que no se pueden recrear con precisión durante la competencia para obtener su propia versión recortada de la simulación física.

Como resultado, el motor, que se suponía debía dar a todos los participantes las mismas condiciones para simular movimientos, se convirtió en el obstáculo más difícil para esto. Más de 10 personas pudieron superarlo. Los primeros 7 lugares en la tabla de clasificación fueron ocupados exclusivamente por los muchachos que hicieron una simulación precisa, lo que puede servir como evidencia de su importancia en tales competiciones.

Con la excepción de un par de participantes que pudieron ingresar al interior de la ardilla listada y optimizar la copia de su estado, el resto tuvo una simulación de aproximadamente el mismo rendimiento (lo que hizo que la competencia fuera un poco más interesante, porque sabes que la lucha es por el algoritmo de decisión, no "quién cuenta más los movimientos").

Algoritmo para buscar y predecir un adversario.

A partir de este punto, comienza una descripción separada de las soluciones. Los algoritmos se describirán en nombre de su autor.

Vladimir Kiselev (Valdemar) 4to lugar

Se utilizó una búsqueda aleatoria (Monte Carlo) para buscar el espacio de la solución. El algoritmo es el siguiente:

Inicializamos el genoma, una secuencia de acciones (izquierda, derecha, parada) para 60 ticks, datos aleatorios.
Toma el mejor genoma encontrado
Cambiar aleatoriamente una de las acciones
Usando la función de evaluación obtenemos un número, un indicador de cuán bueno es el nuevo genoma
Si obtiene una mejor solución, actualice la mejor solución.
Repita nuevamente desde el paso 2

Mi simulador produjo ~ 100k simulaciones del mundo en 1 segundo, considerando que hay un promedio de ~ 12ms por tic, obtenemos 1200 acciones por tic. Es decir, en 1 tick logramos pasar por el ciclo completo unas 20 veces.

Para encontrar la solución óptima, este número de iteraciones claramente no fue suficiente. Por lo tanto, la idea con acciones de "estiramiento" se realizó: en lugar del genoma de 60 movimientos, operaremos con una cadena de 12 movimientos "estirados": creemos que cada acción dura 5 tics seguidos.
Además: al mejorar la calidad de las mutaciones al reducir la longitud del genoma, la simulación también se puede ejecutar cada 5 tics y verificar 100 genomas en lugar de 20 (para evitar caídas en el límite de tiempo, finalmente me detuve en 70).
Menos: las acciones de estiramiento pueden conducir a soluciones no óptimas (por ejemplo, balancearse sobre el parachoques, en lugar de un estante estable)

Cabe señalar las técnicas que han mejorado significativamente la calidad del algoritmo:

Llevamos a cabo la inicialización aleatoria solo en el primer tic, el resto del tiempo reutilizamos la mejor solución encontrada con un cambio de 1 movimiento (la acción en el segundo tic se desplaza al primero, etc., se agrega una acción aleatoria al final). Esto mejora en gran medida la calidad de la búsqueda, ya que de lo contrario el algoritmo "olvida" lo que iba a hacer en el último tic y produce sacudidas sin sentido en diferentes direcciones.
Al comienzo del curso, realizamos cambios más intensivos (cambiamos el genoma 2 o 3 veces en lugar de uno) con la esperanza de romper el máximo local (similitud de temperatura en el método de simulación de recocido).
La intensidad se seleccionó manualmente: las primeras 30 iteraciones hacen 3 mutaciones, las siguientes 10 por 2, luego por 1.
Muy importante es la predicción de las acciones enemigas. En detrimento del tiempo para buscar nuestra propia solución, lanzamos una búsqueda aleatoria desde el lado del oponente, a 20 iteraciones, luego 50 para nosotros, utilizando información sobre los movimientos óptimos del oponente.
La mejor decisión del oponente también se reutiliza en el siguiente movimiento con un desplazamiento. Al mismo tiempo, cuando busco una solución para el enemigo, el genoma del último movimiento se usa como mis acciones previstas.

Durante la competencia, utilizó activamente herramientas para el desarrollo local, lo que hizo posible encontrar rápidamente errores y centrarse en los puntos débiles de la estrategia:

arena local: lanzamiento de muchos partidos contra la versión anterior;
visualizador para el comportamiento de depuración;
Una secuencia de comandos para recopilar estadísticas sobre coincidencias del sitio: le permite comprender en qué mapas y máquinas se produce la derrota con mayor frecuencia.

mortido
Contar cada 5 ticks parece arriesgado, especialmente si el enemigo se está alejando de las opciones que predice. Por otro lado, en este mundo de juego por 5 ticks, no pasó mucho.
Además, en mi decisión, sin embargo, agregué combinaciones aleatorias en cada tic, pero definitivamente no diré cómo esto afectó la decisión.

Comandos:
Cambiar un par de acciones con tantas simulaciones no parece muy significativo, porque ocurren muy pocos cambios en una sola acción. Pero cuando extiendes una acción a 5 tics de significado, parece volverse más.
Tampoco me gusta la idea en sí misma: tomamos el mejor conjunto e intentamos editarlo en algún lugar al principio. Parece ilógico que cambiar las primeras marcas dejará las siguientes al menos relativamente adecuadas.

Alexander Kiselev (mortido) 3er lugar

Armado con artículos de ganadores de otras competiciones, decidí usar el algoritmo genético. Resultó, sin embargo, algo similar a una búsqueda aleatoria o incluso una imitación de recocido, pero más sobre eso más adelante.

Codificamos la solución con una matriz de 40 números, donde -1, 0 y 1 corresponden a los movimientos , y .

Al comienzo de cada ronda, calculé la cantidad de tiempo que ya había gastado en todo el juego, conté un nuevo límite de tiempo basado en cuántas rondas más quedarían, y cada ronda supuse que eran 1200 ticks. T.O. Inicialmente, traté de pasar no más de 11 ms por turno, pero podía "caminar" un poco al final si las rondas anteriores eran más rápidas que 1200 ticks.

Valdemar:
Curiosamente, este chip empeoró el juego para mí. Resultó que siempre es mejor gastar 20-30 ms que 11 primero y 60 al final

Un tercio de este tiempo estaba buscando el mejor movimiento del enemigo, el resto fue para calcular mi propia decisión. Al buscar un movimiento para el enemigo, mi comportamiento fue modelado como el mejor del último movimiento, cambiado por 1 tic. Es decir como si siguiera actuando de acuerdo con el plan elaborado en el último tic, y él está tratando de resistirse a mí.

La búsqueda de la solución en sí fue la misma tanto para él como para el oponente:

Tomamos la decisión del último movimiento y lo cambiamos por 1 movimiento (que ya hemos hecho)
Probamos a la población de soluciones aleatorias hasta que lo llenemos todo
Simulamos todas las decisiones y establecemos la aptitud utilizando la función de evaluación. Recordamos lo mejor.
Si bien hay tiempo para los cálculos
1. Sugerencia, siempre agregue 1 mutación de la mejor solución actual a la población, recuérdelo si es mejor
2. Mientras haya un lugar en la nueva población y no se haya excedido el tiempo para los cálculos (puede ir al piso de una población poblada)
  1. Tomamos dos individuos diferentes y nos vamos con la mejor forma física: mamá
  2. Tomamos dos individuos diferentes y nos vamos con la mejor forma física: papá (no debe coincidir con mamá)
  3. Cruzarlos
  4. Mutar si RND <
  5. Simulamos una solución y la recordamos, si es la mejor.

Como resultado, devolveremos la secuencia de acciones que se considera óptima. El primer movimiento en él se envía como una acción bot. Desafortunadamente, hubo un serio inconveniente en mi plan, ya que el número de simulaciones que se pueden hacer en un tic era muy pequeño (incluso debido a la larga función de evaluación), luego en el servidor de competencia se realizaron 4 puntos solo 1 vez, y para el enemigo no se realizó en absoluto. Esto hizo que el algoritmo se pareciera más a una búsqueda aleatoria o un recocido simulado (ya que logramos mutar la solución 1 vez desde el último movimiento). Ya era demasiado tarde para cambiar algo, y logramos mantener el 3er lugar.

Es importante implementar los algoritmos para cruzar, mutar y generar soluciones aleatorias iniciales, ya que depende de qué decisiones se probarán, y una decisión aleatoria completa no es tan buena como podría parecer a primera vista (funcionará, pero se necesitarán muchas más opciones).

En la versión final, se generaron decisiones aleatorias en segmentos, que excluyeron las soluciones "espasmódicas" en un solo lugar:

Equipo aleatorio seleccionado
Para toda la longitud de la solución (40 movimientos)
1. Escribimos el comando actual en la celda
2. Con una probabilidad del 10% cambiamos el equipo actual a un azar

Según una tecnología similar, también se produjo una mutación: un segmento aleatorio de la solución se reemplazó con un comando aleatorio. El cruce se llevó a cabo eligiendo el punto en el que se tomó la decisión de 1 padre y después del 2 °.

Me gustó que usáramos todo el tiempo disponible para encontrar la mejor solución. No es un gran problema si la solución no es la mejor, podemos mejorarla en el siguiente paso, porque la optimización resulta ser "borrosa" a tiempo. , . , - , . ,

Valdemar:
1 , , .

Commandos:
— - .
— , . , … , . " ”. -.

(Commandos) 1

( ), n m . 3^2=9 . m + n 40 .

 |----------- n  -----------|---------- m  --------| |   ...   |   ...   |

: , , . ( ).

n m , . , .

, ( , ):
- , , , .
- , , . . . , , , .
- . ; ( ).
n m . , .1, , . - ( ) , — , ;
. , — . , ( ).

Valdemar:
, 2 . . , .

mortido:
! , . . , 2 , 40-60 . , 3 .
n + m == const ?

. n + m != const , . , . - .

(Valdemar) 4

, . , ( , , ..) [0..1].
. : , .
, , : , .

, :

— 70 180 ( : ).
, .
0..500
— [2pi, pi/4] [0, 1]
— , ( ), ( , , )
— , , , .
, , .
— . .
Y — .

, 2 , .

“” ,
“ ” , , .

mortido:
, .. , .

Commandos:
, . -

(mortido) 3

, chipmunk. . , , , , . .

3 .

, ( , , ):

. , , ( , );
, — , ; , 1 ;
;
( , );
( “+”, “-”);
- ( “+”, “-”); , , , ;
30 , , ( );
, .

, , (, , )

Valdemar:
. , “ , , ” , ( ..) .

, , . .

Commandos:
, , “”… ? , “” .

(Commandos) 1

SquaredWheelsBuggy , .. , . Buggy , , ( /).
:

;
; — , , 1 0; .. ;
. ; 10 ( );
( , );
(, );
— - , ;
/ ; , — ; .

1-5 , . 2 “ ”.

Valdemar:
, . , .

mortido:
, 10 .

IF'

(Valdemar) 4

, if'. 3 , , . , , -.
: , “” — , - , ( , ) — .

. , .
— , .
. “ ” .
, , .
, , .

, : . , , if' .

mortido:
, . .

Commandos:
if'. , , … , , .

(mortido) 3

- .

3 . . . “”, . , , .

, “” . . , , , - . . , , .. .

, , , , , . … . - — , ( , ).

Valdemar:
, . . “” , if'. , — .

, + . , .

Commandos:
… , - — , , . , , .

(Commandos) 1

. (, , ). ( ) /.

pill carcass map , , ( ). island map, , .

island hole buggy. / , , ( ). — . , , . SquaredWheelBuggy . , , , . , … , , .

(Pill map, Bus) , ( / 100% ).

pill hubble map. , ( ), . .

— , ...

, . , . ( ).

Valdemar:
, — . , .

mortido:
, “” .

Valdemar:
. , . ( ) .
. “”, , , , :)
, mailru , .

mortido:
: , … , , ( ). , 3 , , … .

Commandos:
- , . , , , . … . — , .
— ++. . , . 1 -.

, . , . , , .

Mail.Ru Group .