Hola a todos, mi nombre es Olya. Hace dos semanas, otro concurso terminó en CodinGame, una competencia para programar bots para el juego. Me metí en el top 300 de la tabla de clasificación mundial, así que quiero decirte por qué los concursos son geniales y compartir mis secretos. Ivan spaceorc , quien se metió en el top 100 de la misma competencia, también compartirá secretos.
Aprenderás a competir con éxito en competencias de programación de IA de juegos.
¿Qué es CodinGame?
codingame.com es una plataforma educativa para desarrolladores de todas las edades y niveles de capacitación. Puede escribir en 26 idiomas : desde C # y Python hasta Bash y Haskell. Lo mejor es que las tareas no son aburridas e incomprensibles, sino juegos reales con una buena GUI:
Un concurso es una competencia de 10 días que se realiza una vez cada dos meses. Cualquiera puede participar, no es necesario ser finalista de ACM ICPC. Por supuesto, para llegar a lo más alto, necesita al menos comprender los algoritmos típicos de la inteligencia artificial para juegos.
Pero para pasar un par de noches con interés, el conocimiento más básico es suficiente. En cada concurso hay un código listo para leer los datos de entrada. Solo queda leer las reglas, escribir sin pretensiones si no, ¡y entrar en la batalla!
Código de kutulu
El "Código Cthulhu" es el último concurso, que tuvo lugar del 15 al 25 de junio. Para descubrir la trama y el propósito, una descripción es suficiente:
PH'NGLUI MGLW'NAFH CTHULHU R'LYEH WGAH'NAGL FHTAGN
Lo que puede mentir para siempre no está muerto en absoluto. Y la muerte muere en un misterioso eón.
Usted y su equipo de investigadores han descubierto la tumba de Cthulhu. Esta es la peor decisión en su vida, porque él no estaba listo para despertarse y ahora tiene hambre de su muerte. Pero la cripta es un verdadero laberinto, y no recuerdas dónde estaba la salida ... ¡Si todavía está allí!
Ah ... y parece que Cthulhu no estaba solo, y ahora está enviando a los Profundos por ti.
Intenta mantenerte con vida por más tiempo, pero recuerda que solo tú no durarás mucho ...
Las reglas
Diré de inmediato que en lugar de leer una descripción de texto de las reglas, puede ver un video del análisis de las reglas y tácticas básicas de Tinsane :
De lo contrario, sigue leyendo.
Mapa
En el juego, cuatro jugadores caminan sobre el mapa generado, más precisamente, el gráfico de celdas conectadas entre sí. Más en el mapa están ejecutando secuaces enemigos, cuyo objetivo es alcanzar y asustar a los jugadores.
Personajes
- El investigador es uno de los jugadores. Va en cualquier dirección en una celda. Tiene superpoderes, pero más sobre ellos más adelante.
- Vanderer es un monstruo verde. Aparece en el mapa cada 5 turnos, desde puntos previamente conocidos. Genera más de 3 a 6 movimientos, busca al jugador más cercano y comienza la búsqueda. Va solo una casilla por turno. Si no ha atrapado a nadie en N pasos, desaparece del mapa.
- Slasher: similar a la muerte con una guadaña. Aparece en lugar de un jugador cuya salud ha caído por debajo de los 200 puntos y permanece en el mapa hasta el final del juego. "Ve" a un jugador si no hay paredes entre ellos. Si en 2 movimientos el objetivo no se pierde de vista, el siguiente movimiento salta al lugar donde el jugador fue visto por última vez.
Supervivencia
Si el vagabundo o slasher entra en la celda con el jugador, el jugador pierde 20 puntos de vida. Además, los jugadores pierden una cierta cantidad de salud cada turno sin ningún motivo. Pero si hay investigadores vivos en el radio de dos células, se pierde un poco menos de salud.
Investigadores superpoderes
- PLAN: aumenta la salud en 2 puntos en 5 turnos. Si otros investigadores caen dentro del radio de acción, entonces el efecto se extiende a ellos y el creador del efecto recibe +2 de salud por cada uno. Puedes usar 2 veces por juego.
- YELL: asusta al jugador en la celda siguiente. La acción planificada para el próximo turno se convierte en ESPERA (el jugador se quedará quieto). Es útil si el vagabundo persigue al enemigo y quieres sustituirlo.
- LUZ: ilumina las celdas en un radio de 5, puede usar 3 veces por juego. Ayuda a ahuyentar a los errantes: cuando cuentan el camino hacia el objetivo más cercano, cada celda iluminada cuenta como 4.
El final del juego
Un jugador muere si su salud cae a cero. Después de 200 movimientos, los jugadores supervivientes comienzan a perder salud más rápido y el juego termina casi de inmediato.
Los desarrolladores del concurso dan las reglas a los jugadores, pero los jugadores exitosos van a Github y leen el código del árbitro .
Tácticas
Debo decir de inmediato que no comencé desde cero. El 16 de junio, Kontur celebró centros de codificación en siete ciudades , reuniones para aquellos que desean discutir el concurso y divertirse en un ambiente agradable ( foto ).
Aprobé el examen en la universidad y no llegué al centro de Ekaterimburgo, pero aproveché la bonificación de los organizadores: el kit de inicio. Está disponible en dos lenguajes: C # y TypeScript , y ya implementa toda la infraestructura: la lógica para leer el estado del juego en cada turno, así como las clases que caracterizan el juego en sí (como el estado y las posibles acciones) y algunos auxiliares (por ejemplo, un temporizador personalizado) . Pude comenzar a escribir de inmediato lo más interesante: mi cerebro bot investigador
Uno de los líderes del centro en Ekaterimburgo es Vanya Dashkevich ( spaceorc ). Lleva más de un año sentado en CodinGame, participó en siete concursos y en cinco alcanzó el top 100 mundial:
Descubrí a Vanya los detalles de la decisión, que le proporcionó el puesto 64 en la clasificación mundial, y comparé su decisión con la mía.
[1] Ven a los centros: allí puedes obtener enlaces a kits de inicio, discutir las reglas, idear tácticas y conocer gente interesante.
Que al comienzo del concurso, que al final, el algoritmo para elegir el próximo movimiento se ve igual:
- Genera todas las acciones disponibles para el bot;
- Aplicarlos al estado actual;
- Evaluar los resultados de estos movimientos;
- Elige el mejor.
Generar acciones disponibles
Ollisteka : Ya en este paso, comencé a aplicar la heurística. Me imaginé en el lugar de este investigador y decidí qué sería bueno y qué no. ¿Puedo ir a la próxima celda libre? Agrega tal movimiento. Todavía tengo un plan sin usar, y no hay ningún trotamundos o slasher cerca que me ataque el próximo turno. Añadir
De acuerdo con el mismo esquema, LIGHT y YELL cayeron en la lista de posibles acciones, pero su uso solo me bajó en la clasificación. Por lo tanto, todavía los eliminé de la implementación final.
[2] No tengas miedo de incluir fantasía: para empezar, la heurística simple y un par de operadores condicionales son suficientes.
Aplicación de trazo
El proceso de aplicar un movimiento a un estado de juego se llama simulación. La presencia de simulación le permite utilizar técnicas avanzadas de programación de IA: minimax , algoritmos genéticos , Monte Carlo Tree Search y otros.
Ollisteka : Es este paso el que se relaciona con mi "subestimulación". "Nedo", porque después de que me fui, el resto de los jugadores deberían ir, los enemigos deberían ir o reaparecer. Sin embargo, era demasiado vago para hacer una simulación completa para cuatro jugadores y una gran cantidad de enemigos con lógica no trivial. Por lo tanto, solo cambié mi salud dependiendo de si estaba solo o en grupo, y no encontré un vagabundo este turno.
spaceorc : Mi enfoque habitual últimamente ha sido dos pasos:
- llegas al escenario de cualquier manera cuando los organizadores abren todas las reglas y dejan caer la fuente del "árbitro" en Github;
- tomas al árbitro y escribes, mirándolo, una simulación.
La simulación es completa, con todos los matices, pero ineficaz. Por lo general, apuesto a la velocidad y profundidad de la búsqueda ... Pero una simulación completa le permite ejecutar muchas coincidencias localmente y comparar diferentes estrategias. Probé la simulación completa con CodinGame: predije las posiciones de los minions, sabiendo cómo cayeron los rivales (es decir, el siguiente movimiento), y descubrí las discrepancias. Cuando la simulación completa estaba lista, comencé a escribir una rápida, para hacer esto simplemente, teniendo una que funcionara.
[3] ¿Quieres llegar a la cima? Tendrás que descifrar las reglas y escribir una simulación.
Simulación de oponentes.
spaceorc : Escribió Monte Carlo Tree Search, pero jugó peor porque había muy poco tiempo para resolverlo. En general, este enfoque me llegó más o menos solo en Ultimate Tic-Tac-Toe . Los oponentes jugaron de la misma manera: simulación por movimiento más puntuación, mis movimientos, MCTS y juego hasta el final. De esta forma, fue posible simular unos 50 juegos hasta el final en 50 ms. Esto no es suficiente para MCTS, así que lo corté y volví a la idea original.
Como resultado, una simulación rápida se volvió incompleta:
- dejó de considerar a los vagabundos a más de 8 celdas de mí;
- Dejé de engendrar a los errantes, porque ya generan 5 movimientos, y esta es mi profundidad de búsqueda aproximadamente.
Debido a esto, la profundidad de búsqueda ha aumentado. También intenté simular solo movimientos (sin GRITO, LUZ, PLAN) de mis oponentes, pero resultó peor.
Función de evaluación
La función de evaluación ayuda a elegir el mejor de todos los movimientos disponibles. Toma el estado del juego en la entrada, y en la salida da un número con una estimación: cuanto más grande sea, mejor será el estado del juego para el jugador actual.
Ollisteka : Qué parámetros se incluyeron en mi evaluación:
- la salud de mi investigador;
- errantes:
- si es probable que venga aquí el próximo movimiento, entonces este es un mal movimiento;
- si estoy en la misma línea con él, entonces, cuanto más lejos de él, mejor;
- si él también se aprovecha de mí, entonces la distancia es aún más importante.
- células libres alrededor, para no encontrarse con un callejón sin salida;
- otros investigadores, que es mejor estar cerca de ellos;
- PLAN actual: si mi salud cae por debajo de 230, entonces el tratamiento es una buena idea.
En algún momento, intenté evaluar los slashers, pero cuando los quité, me subieron a un par de docenas de lugares en la tabla de clasificación. Si resolviera mejor su lógica, entonces tal vez harían más bien.
Como resultado, mi evaluación podría ser más pequeña, pero como dicen, funciona, no la toques.
spaceorc : Traté de jugar con las funciones de evaluación, pero no funcionó muy bien ... En general, algunos de los que resultaron ser significativamente más altos que yo en la tabla de clasificación no pasaron por mucho, pero obtuvieron buenas características para la evaluación. No hice frente a esto. Mi función de evaluación final incluyó:
- el número de puntos (el recorrido en el que murió + salud);
- Cuervo
- distancia a investigadores extranjeros.
[4] Experimento: cambie los coeficientes de los parámetros de la función de evaluación, agregue nuevos parámetros y elimine los antiguos.
Elegir el mejor movimiento
Ordenamos los movimientos en orden descendente, tomamos el primero, lo usamos.
Optimización
Competir por un lugar en el top 100 no es suficiente para tener una buena función de evaluación y una simulación completa. Cuanto más rápido funcione el bot, más juegos se simularán en un intervalo de tiempo. Cuantos más juegos, más probabilidades hay de que el movimiento actual sea el más óptimo. Cuanto más óptimo sea el movimiento, mayor será el lugar en la tabla de clasificación.
Ollisteka : Aproveché el hecho de que el mapa puede representarse en forma de gráfico: calculé por adelantado las longitudes de todos los caminos de celda a celda y no pasé tiempo en esto todo el tiempo.
spaceorc : En CodinGame, la simulación funcionó rápidamente, en 50 ms realizó varias decenas de miles de movimientos. Debido a que:
- Máscaras de bits y código inseguro.
- Explorer - int, wanderer - int, slasher - int.
- Todo el estado mutable cabe en 128 bytes, por lo que todo funciona muy rápidamente con él.
- La coordenada es byte, porque el mapa más grande tenía 222 celdas libres.
- La cola debe ser: var queue = stackalloc byte [255].
- Cálculo previo de caminos, distancias y otras cosas.
Lo he estado haciendo todo el tiempo últimamente, es muy bueno. Por cierto, siempre escribo muchas pruebas para tal simulación, sin las cuales simplemente no se puede depurar.
[5] Quiere competir por un lugar en el top 100: deshacerse del código ineficiente.
A qué condujo
Ollisteka : A lo largo del concurso, mi bot permaneció constantemente entre los primeros 300. En algún momento, incluso estaba en el puesto 84 en la clasificación mundial, pero luego me comprometí con una nueva versión y no regresé ¯ \ (ツ) / ¯ Habiendo terminado en el lugar 290, estoy muy feliz por tres razones:
- Este es el primer concurso en el que participé por completo, ya que durante el pasado estaba demasiado ocupado con los estudios.
- Me gustó el juego en sí: estaba claro cómo jugar y qué hacer para ganar.
- Top 15% del mundo - eso suena genial :)
Era obvio que para llegar a la cima necesita hacer una simulación completa y rápida. Pero no quería hacer esto, así que simplemente agregué parámetros a la función de evaluación y cambié las constantes mágicas.
spaceorc : Estoy bastante satisfecho con el resultado, fui al top 100 ... Pero aún así tuve que trabajar más en la función de evaluación, resultó un fuerte sesgo hacia la simulación. Y al final estoy un poco cansado, mi imaginación no fue suficiente ...
En conclusión
¡Mira CodinGame y prueba tu suerte! En julio prometen un nuevo concurso: vengan a los centros, codificaremos los bots juntos.
Enlaces utiles:
UPD Gracias dbf por el comentario: el código de Kutulu se ha subido al modo multijugador . ¡Para que pueda poner en práctica los conocimientos adquiridos en el artículo! :)