La parte final.
En los capítulos anteriores ( parte 1 , parte 2 , parte sobre la GPU ), tocamos las condiciones del concurso, la red neuronal, el algoritmo genético, así que continuemos.
Pero antes de continuar, hay un enlace a GitHub con el código fuente del programa c ++ y para admitir el título del artículo: un archivo ejecutable en Windows en la carpeta bin , que es bastante similar al protector de pantalla. En el sótano del artículo organizó el "salón de la fama" de campeonatos pasados.
Entonces, nos decidimos por la arquitectura del programa, que consta de dos partes separadas (programas), la parte que contiene solo la red neuronal y el protocolo de comunicación con el servidor del juego de los organizadores del concurso (el bot del juego en sí) y la parte principal, que consta de los siguientes bloques:
Brevemente sobre cada una de las partes.
Motor de física. Basado en el módulo de cálculos físicos de las fuentes oficiales, rehecho para la GPU y agregado cálculos de sensores de bot, funciones físicas, colisiones de bot. El código fuente eliminó los virus y los intentos de bot para compartir, dividiendo la parte inestable del programa. Por lo tanto, no compartí mis errores.
Red neuronal. Hablamos de ello con suficiente detalle la última vez, incluida la implementación en el código, por lo que supondré que aquí también queda claro, especialmente porque no ha habido preguntas particulares de los lectores.
Algoritmo genético. Hubo lagunas en la cobertura de su implementación. Ahora es más probable que lo repita, pero es más fácil repetirlo una vez más.
Me acordé mucho de la diapositiva de presentación. Por lo tanto, la pregunta principal permaneció: ¿cómo mover la evolución? Para esto, se inventó la función Fitness. El objetivo principal de la función fitness es la selección de genotipos para la transmisión de la población actual de bots a los siguientes.
¿Cómo es probable que la elección de la función de aptitud se haya aclarado? La cuestión del cruce se mantuvo.
Hay varios métodos básicos de cruzamiento, más en el enlace . Pero el principio básico es el intercambio aleatorio de genes entre genotipos parentales. Generalmente se seleccionan dos padres, también hay varios métodos para elegir padres de una población, el enlace se puede leer con más detalle. Aunque la elección de los padres se realiza al azar, la probabilidad de elegir un padre específico aumenta en proporción a su función de aptitud física.
A continuación, la función de mutación se aplica al genotipo terminado.
En nuestro caso, de vez en cuando, el algoritmo cambia un gen seleccionado arbitrariamente a un gen aleatorio, en otras palabras, uno de los pesos de la red neuronal cambia a uno aleatorio.
Tenemos una nueva población y la evolución continúa hasta el resultado deseado. Hay varios puntos, el primero: cuantos más bots haya en la población, más rápido el algoritmo genético encontrará la solución óptima o convergerá a la solución (la relación óptima de pesos en la red neuronal). Por ejemplo, si un bot tiene 1000 genes, entonces el espacio de búsqueda se expande significativamente con una población de 3000 bots, en comparación con una población de 300 bots. Pero surge otro problema, si liberas los 3000 bots en la arena diseñada para 4-8 bots, lo más probable es que los bots estén físicamente llenos y si aprenden algo, definitivamente no es un juego en Agario. Por lo tanto, hay dos formas principales de evitar la sobrepoblación de la arena: la primera para seleccionar varios bots de la población y competir en la arena, y tantas veces, hasta que acumulemos estadísticas de juego para cada bot. El segundo al que acudió el autor es el lanzamiento de varias arenas en paralelo, digamos 50-300, todo depende de la potencia de una computadora en particular y, en paralelo, toda la población de bots participa en competiciones. La población puede dividirse en subpoblaciones con sus funciones de aptitud e identificadores (corresponde al número de arenas), y luego intercambiar genotipos entre subpoblaciones. O imagine todo como una gran población de bots jugando en diferentes arenas. El autor probó ambas opciones, pero en la versión fuente con una sola población de bots. El parámetro en el programa Depth es el número de arena.
Entonces le dijo a los principios básicos de la construcción de un programa. Quien quiera ver en vivo, bienvenido al enlace al github .
si no puede iniciarlo, un breve video se iluminará en este momento:
Anuncio: En agosto, mail.ru organizará otra mini copa AI, el anuncio oficial aún no se ha visto la verdad. Pero según la información de los telegramas del grupo, la base de la competencia es nuevamente el motor de física, algo sobre los automóviles. Por lo tanto, brevemente sobre los principios de crear un bot, aquellos que estarán interesados, por supuesto:
Aquí, como nuestro equipo de fútbol, es recomendable dejar el grupo, el final es una canción separada. Deje que los finalistas escriban sobre las victorias, pero nuestra participación principal.
Lo más claro y simple:
Escriba condiciones más diferentes en el cuerpo del código bot, por ejemplo, if (agujero) -> salto, etc. Las condiciones simples son efectivas al comienzo del campeonato, luego la complejidad de los bots crecerá y la ventaja de las soluciones condicionales desaparecerá.
Y así, el método más prometedor en muchos juegos estratégicos:
Método PP ( o campos potenciales ). La idea es hermosa, la búsqueda del máximo o mínimo en un entorno dinámico. Una cuadrícula de la dimensión seleccionada se construye en todo el campo de juego o solo en el área alrededor del bot, todo depende del alcance del bot. A continuación, en cada punto nodal de esta cuadrícula, consideramos las distancias a los objetos que nos interesan o, como opción, los potenciales de inmediato, pueden ser positivos (atracción, esto es lo que es interesante para el bot) y negativos (peligro para el bot). En consecuencia, los potenciales en el punto se resumen y obtenemos los potenciales totales en cada punto de la cuadrícula. Campo de potenciales. Bot solo puede elegir el potencial más pequeño o más grande, dependiendo de la tarea en este momento. Básicamente, los campos potenciales son implementaciones en 2D, aunque 3D se verá genial, pero habrá muchos recursos para los cálculos.
Lo mas dificil:
Las dos implementaciones principales son el método Brute Force o el método Monte Carlo . Cada uno de ellos es el tema de un artículo separado, pero según la sensación, son estos métodos los que lo llevarán a la final. Si es una tesis, entonces el bot puede mirar no solo en el tiempo actual o en el pasado, sino que si lo desea, puede mirar hacia el futuro, aquí surge un embudo (cono) de posibles resultados y cuanto más quiera mirar el bot, más opciones aparecerán. Por ejemplo, en el punto de tiempo Tick Zero, el bot decide ir en una de las ocho direcciones, en el paso Tick + 1 en cada una de las ocho nuevas coordenadas tiene la oportunidad de ir de nuevo en ocho direcciones, etc. Es necesario tener en cuenta los posibles movimientos enemigos durante este tiempo. Cada posible resultado de los cálculos acumula un posible beneficio o daño. En función del cual el bot realiza un movimiento en una de las direcciones. Y además, tal cálculo en la profundidad del tiempo futuro va cada tic. La profundidad de las vistas de movimientos está determinada por los posibles recursos de la computadora. Por lo tanto, para recursos informáticos pequeños, surge el problema de optimizar estos cálculos.
Sobre la fuente, si hay interés, editaré los comentarios sobre el código, mientras lo expongo tal como estaba.
En la fuente, las señales del Tick actual y el Tick anterior se envían a la entrada de la neurona, se hizo más interesante, gracias al lector: tongohiti por la idea.
Para aquellos que recuerdan la tesis sobre la distribución inicial de pesos en la red neuronal, un tema interesante es la inicialización de Xavire.
Gracias por su atencion Nos vemos en las competiciones de IA.
Artículos relacionados de los participantes, pero primera digresión :
Ella estaba sentada en el suelo
Y ordené el montón de letras
Y como cenizas enfriadas
Los tomé en mis manos y los tiré.
Tomó sábanas familiares
Y fue maravilloso que ella los mirara,
Cómo se ven las almas desde arriba
Sobre ellos un cuerpo abandonado ...
Oh cuánta vida había aquí
Irreversiblemente experimentado!
Oh cuantos minutos lamentables
¡Amor y alegría asesinados! ..
Mi estrategia en la Russian AI Cup 2017
Historia de participación (y casi victoria) en la competencia anual Russian AI Cup 2016
Historia de la victoria en la Copa anual rusa de IA 2015
Russian AI Cup 2014: estrategia ganadora
Medalla de oro en la Copa AI de Rusia 2013: cómo fue todo
El camino hacia la medalla de plata en la Copa AI de Rusia 2012