Me llamo Igor Volkov. Trabajo en una empresa de consultoría como desarrollador de Java, arquitecto, líder de equipo, gerente técnico. Diferentes roles dependiendo de las necesidades actuales del proyecto. Llamó la atención a los concursos de mail.ru durante mucho tiempo, pero resultó participar activamente solo en Paper IO.
Esta vez, los organizadores propusieron implementar una estrategia de administración de bot basada en el popular juego. Lea más sobre las reglas aquí . El código de mi estrategia se puede encontrar aquí , y ejemplos de juegos en el sitio web del campeonato .
Al principio de la competencia, como me pareció, la idea de implementación emergente más común era el uso de MCTS . Por lo tanto, pasé un poco de tiempo experimentando con este algoritmo. Y sin haber descubierto cómo usarlo de manera efectiva para resolver el problema, decidí comenzar generando muchas rutas rectangulares (con dos y luego con tres vueltas) y su evaluación posterior.
Algoritmo de estrategia
El algoritmo de alto nivel de la estrategia se puede representar mediante los siguientes 6 puntos:
- Lee el estado del mundo
- Convertir objetos de mensaje en objetos de trabajo
- Formar un conjunto de rutas rectangulares.
- Califica cada una de las rutas generadas
- Elige la mejor ruta
- Enviar equipo
Este algoritmo no ha cambiado durante la competencia. Solo se modificó el método de formación de rutas de bot y su evaluación.
La clase SimpleStrategy contiene la versión inicial de la estrategia, y la clase BestStrategy es una versión mejorada, que ocupó el segundo lugar en la competencia.
Leyendo el estado del mundo
El estado del mundo se transmite como un objeto JSON a través de STDIN . Vi en pom.xml que puedes usar la biblioteca Gson y la tarea de leer el estado del mundo se ha simplificado enormemente. Usando la biblioteca Gson, deserializó la cadena JSON leída de la secuencia de entrada estándar en una instancia de la clase Mensaje . El código está en Main.java (líneas 44-49) .
Crea objetos de trabajo
El uso de objetos de transporte en el código del programa principal generalmente no es muy conveniente y arquitectónicamente incorrecto. Por ejemplo, los organizadores, por una razón u otra, pueden cambiar el formato de los mensajes. Por lo tanto, es necesario transformar los objetos de transporte en trabajadores, que se utilizarán en el código del programa principal. Las clases Player y PlayerState conservan el estado del bot, y la clase de utilidad MessagePlayer2PlayerConverter ayuda a crear estas clases en función de los datos del mensaje de transporte. La clase Bonus contiene información sobre la bonificación de una celda en el campo de juego. El código para crear objetos de trabajo se encuentra en Main.java (líneas 61-74) .
En las primeras versiones de la estrategia ( SimpleStrategy ), la ruta se estableció usando las clases MovePlanWithScore y Move . Mover establece la dirección del movimiento y cuántas celdas debe mover el bot en esa dirección, y MovePlanWithScore contiene la ruta especificada por la matriz Mover y una estimación de esta ruta. Una matriz podría contener de uno a cuatro objetos Move . A pesar de que solo se consideran rutas rectangulares con no más de tres vueltas, de hecho, la ruta del bot se obtiene en forma de una línea discontinua. Esto se logra eligiendo una nueva mejor ruta rectangular en cada giro. La función de generación de ruta , implementada como bucles anidados, forma una lista de MovePlanWithScore para su posterior evaluación.
Tal formación de las trayectorias de los bots no fue muy efectiva en términos del desempeño de la evaluación posterior, ya que fue necesario calcular las mismas trayectorias varias veces, pero fue muy útil para comprender la mecánica del juego.
En versiones posteriores de la estrategia, BestStrategy comenzó a usar el árbol de ruta. La clase MoveNode refleja el nodo de este árbol. El árbol está completamente formado al comienzo de la estrategia. Presta atención al método init de la clase MoveNode . Es muy similar a generar rutas desde la clase SimpleStrategy . Fundamentalmente, la ruta en cuestión no es muy diferente de la primera versión.
La formación de rutas, creo, podría haberse mejorado un poco más al agregar otro giro. Pero no hubo tiempo suficiente para la optimización.
Calificación de ruta
Dondequiera que se ubicara el bot, siempre se elegía la mejor ruta que terminara en su territorio. Para evaluar la ruta, presenté dos indicadores: puntaje y riesgo. Puntaje: refleja aproximadamente el número de puntos anotados por tick del camino y riesgo: el número de ticks que no son suficientes para completar el camino (por ejemplo, debido a que el oponente puede agarrar la cola). El riesgo no apareció de inmediato. En la primera versión, si el bot repentinamente encontró en el medio del camino que no tenía tiempo para completar la ruta, "se volvió loco", ya que todos los caminos peligrosos eran igualmente malos para él. De todas las rutas consideradas, la más "segura" se selecciona con el número máximo de puntos por marca de la ruta.
Para evaluar la seguridad de la ruta, calculo la matriz de accesibilidad: para cada celda del campo de juego encuentro una marca en la que puede aparecer el bot del oponente. Primero, solo una marca, y luego agregó un cálculo de longitud de cola. Los bonos que se pueden recoger en el camino tampoco se tuvieron en cuenta en las primeras versiones de la estrategia. La clase TimeMatrixBuilder calcula matrices de garrapatas y longitudes de cola de bots rivales. Estas matrices se utilizan para evaluar el riesgo. Si mi bot está en su territorio al momento de calcular el próximo movimiento: el nivel de riesgo máximo se asigna a rutas peligrosas, si el bot ya estaba en camino en un territorio extranjero o neutral, el riesgo se evalúa como la diferencia entre los tics de la finalización de la ruta (el bot llegó a su territorio) y el tick cuando puede amenaza de peligro (por ejemplo, el bot de otra persona puede pisar la cola).
En las primeras versiones de la estrategia, el puntaje se consideraba solo en función del territorio capturado y las bonificaciones se tenían en cuenta ligeramente. Para encontrar las celdas capturadas, uso un algoritmo recursivo . Muchos concursantes se quejaron de la extrañeza y la excesiva complejidad computacional del algoritmo utilizado por los organizadores de Local Runner . Asumiré que esto se hizo intencionalmente para no dar a los participantes de la competencia soluciones preparadas.
Extraño, pero a pesar de lo primitivo de las primeras versiones de la estrategia, se mostró bastante bien: décimo lugar en el sandbox. Es cierto que en la ronda prefinal comenzó a descender rápidamente: otros participantes mejoraron sus estrategias.
Mi bot a menudo moría. En primer lugar, debido al hecho de que se estaba construyendo una ruta hacia el territorio que fue capturado por los bots rivales. El camino se alargó inesperadamente y mi bot fue atrapado por la cola. A menudo murió debido a una predicción incorrecta de la longitud de la cola y la velocidad del bot del oponente. Por ejemplo, el bot de un oponente que se desaceleraba era peligroso, ya que, en un cálculo aproximado, la estrategia suponía que ya debería haber salido de la celda, y todavía estaba allí. Para combatir estos problemas, comencé a calcular un mayor número de indicadores para cada celda del campo de juego (clases AnalyticsBuilder y CellDetails ).
Contando celdas del campo de juego
- Marca en la que el bot del oponente puede ocupar la jaula (marca en la cola)
- Marca en la que el bot del oponente puede ingresar a la celda
- La longitud de la cola al entrar en la jaula.
- Marca en la que el bot del oponente puede salir de la jaula
- Longitud de la cola al salir de la jaula
- Marque la casilla en la que el bot de un oponente puede capturar una celda
- Marca en la cual la celda puede ser el objetivo para capturar territorio
- Marca en la cual la celda puede ser golpeada con una sierra
La profundidad de la analítica está limitada a 10 movimientos. Creo que fue posible lograr una mayor profundidad al negarme a contar rivales individuales o introducir profundidad flotante, pero no hubo suficiente tiempo para la optimización. Además de AnalyticsBuilder, comenzó a usar SimpleTickMatrixBuilder si faltaba profundidad de representación para AnalyticsBuilder . BestStrategy utiliza los resultados analíticos.
La función de calificación también ha mejorado ligeramente:
- Comencé a tener en cuenta las bonificaciones: una penalización por tomar una bonificación de desaceleración y una bonificación por tomar aceleración y bonificaciones de sierra. Como resultado, el bot comenzó a evitar con éxito las bonificaciones malas y recogió las buenas en el camino.
- Comenzó a tener en cuenta el choque de cabezas. Se agregaron algunos puntos para el choque de la victoria. Cuanto más lejos sea posible una colisión, menos puntos.
- Para reducir la probabilidad del medio ambiente, agregó algunos puntos para tomar las celdas límite del oponente.
- Redujo el valor de las celdas vacías en el borde: cuanto más lejos del centro, menor es el valor. Al observar las peleas de la final, llegué a la conclusión de que por el solo hecho de capturar una celda vacía no había necesidad de acumular puntos. El valor de una celda vacía debe depender de la proximidad a grandes grupos de celdas enemigas. Desafortunadamente, en la final ya no era posible editar la estrategia.
- Se agregaron puntos por rodear la cabeza del bot del oponente. No estoy seguro si esto de alguna manera ayudó. Quizás con las estrategias más simples.
- Agregó puntos incluso para un agarre inútil en la cola (el bot del oponente logró capturar el territorio con el mismo tic en el que mi bot pisó su cola). Definitivamente no estoy seguro, pero creo que esto impidió que los bots del oponente capturaran el territorio de otra persona y que a menudo tuvieron que regresar al suyo.
- En caso de detección de posible muerte por captura, se incrementó considerablemente el costo de las celdas límite del territorio del oponente.
Depuración de estrategia
Las primeras versiones de la estrategia contenían una gran cantidad de errores tipográficos y errores: aparentemente, el resultado de la programación nocturna. Por ejemplo, en la clase Cell , el índice se consideró incorrectamente: en lugar de this.index = x * Game.sizeY + y , this.index = x * Game.width + y . Al principio traté de confiar solo en las pruebas, pero mi intuición sugirió que sin visualización y sin jugar partidos jugados previamente, sería difícil encontrar errores en el código y analizar las razones para tomar decisiones erróneas. Como resultado, apareció el visualizador DebugWindow , en el que puede ver los juegos jugados anteriormente paso a paso, así como comenzar a depurar en la marca deseada. El código no es muy bonito, escrito a toda prisa, pero me ayudó mucho al depurar. Por ejemplo, se detectó un error inmediatamente con un cálculo incorrecto del índice de celda. Muchos concursantes mostraron información de depuración en la consola, pero me pareció que no era suficiente.
Optimización
Para no perder el tiempo creando objetos y ejecutando el GC, intenté crear algunos objetos por adelantado. Estas son las celdas del campo de juego (clase Cell ). Además para cada celda vecinos identificados. Creó un árbol de posibles caminos por adelantado (clase MoveNode ).
Supuse que muchos escenarios tendrían que ser simulados, y en el proceso el estado actual se deterioraría y tendría que ser restaurado cada vez. Por lo tanto, para preservar el estado del mundo, traté de usar la mayor cantidad posible de estructuras empaquetadas. Para almacenar el territorio ocupado - BitSet (clase PlayerTerritory ). Cada celda del campo de juego está numerada, y el número de celda corresponde al número de bit en BitSet. Para almacenar la cola, utilicé BitSet junto con ArrayDeque (clase PlayerTail ).
Es cierto que no pude jugar varios escenarios debido a la falta de tiempo. Y dado que la función principal de calcular la ruta se volvió recursiva y todo el estado se podía almacenar en la pila, las últimas optimizaciones no me fueron muy útiles.
Ideas no realizadas
Al evaluar el riesgo de la ruta de mi bot, tomé en cuenta a cada oponente de forma independiente. De hecho, cada uno de los rivales también tiene miedo de morir. Por lo tanto, valdría la pena considerar esto en una evaluación de riesgos. Al menos, esto definitivamente tuvo que ser tenido en cuenta en los juegos finales.
Contabilización de la futura muerte de un oponente. A veces sucede que el bot captura el territorio del oponente, y el oponente muere inesperadamente. Es una pena, porque como resultado, solo captura celdas vacías.
Contabilizar las celdas vacías que se capturarán en el futuro cercano como una función de evaluación.
Recomendaciones y agradecimientos
Recomiendo que todos los desarrolladores participen activamente en concursos de Copas AI. Esto desarrolla el pensamiento y ayuda a través del juego a aprender nuevos algoritmos. Y como ha demostrado mi experiencia, un poco de celo es suficiente para ocupar un lugar de premio e incluso un código simple y no muy óptimo puede traer resultados.
Muchas gracias a los organizadores. A pesar de algunos problemas técnicos, la competencia resultó ser interesante. Espero con ansias el próximo!