A parte final.
Nos capítulos anteriores ( parte 1 , parte 2 , parte sobre a GPU ), abordamos as condições do concurso, rede neural, algoritmo genético, então vamos continuar.
Mas antes de continuar, há um link para o GitHub com o código-fonte do programa em c ++ e para oferecer suporte ao título do artigo - um arquivo executável no Windows na pasta bin , que é bastante semelhante ao protetor de tela. No porão do artigo, ele organizou o “hall da fama” dos campeonatos anteriores.
Então, decidimos pela arquitetura do programa, que consiste em duas partes separadas (programas), a parte contendo apenas a rede neural e o protocolo de comunicação com o servidor do jogo dos organizadores do concurso (o próprio bot do jogo) e a parte principal, composta pelos seguintes blocos:
Brevemente sobre cada uma das partes.
Motor de física. Com base no módulo de cálculos de física das fontes oficiais, refeito para a GPU e adicionado cálculos de sensor de bot, funções de condicionamento físico e colisões de bot. O código-fonte removeu vírus e tentativas de compartilhamento de bots, dividindo a parte instável do programa. Portanto, não compartilhei meus erros.
Rede neural. Conversamos sobre isso em detalhes suficientes da última vez, inclusive sobre a implementação no código, portanto, assumirei que também há muito claro aqui, principalmente porque não houve perguntas específicas dos leitores.
Algoritmo genético. Havia lacunas na cobertura de sua implementação. Agora, é mais provável que eu o repita, mas é mais fácil repeti-lo novamente.
Lembrei-me muito do slide da apresentação. Portanto, a principal questão permaneceu: como mover a evolução? Para isso, a função Fitness foi inventada. O principal objetivo da função de condicionamento físico é a seleção de genótipos para transmissão da população atual de bots para a próxima.
Como é que a escolha da função de fitness provavelmente ficou clara. A questão da travessia permaneceu.
Existem vários métodos básicos de cruzamento, mais no link . Mas o princípio básico é a troca aleatória de genes entre genótipos parentais. Normalmente, dois pais são selecionados; também existem vários métodos para escolher pais de uma população; o link pode ser lido com mais detalhes. Embora a escolha dos pais seja feita aleatoriamente, a probabilidade de escolher um pai específico aumenta proporcionalmente à sua função de condicionamento físico.
Em seguida, a função de mutação é aplicada ao genótipo final.
No nosso caso, de tempos em tempos, o algoritmo altera um gene selecionado arbitrariamente para um gene aleatório, ou seja, um dos pesos da rede neural muda para um aleatório.
Temos uma nova população e a evolução continua até o resultado desejado. Existem vários pontos, o primeiro: quanto mais robôs na população, mais rápido o algoritmo genético encontrará a solução ideal ou convergirá para a solução (a proporção ideal de pesos na rede neural). Por exemplo, se um bot possui 1000 genes, o espaço de pesquisa se expande significativamente com uma população de 3000 bots, em comparação com uma população de 300 bots. Mas surge outro problema: se você liberar todos os 3.000 bots na arena projetada para 4 a 8 bots, provavelmente os bots nela estarão fisicamente lotados e se eles aprenderem alguma coisa, definitivamente não é um jogo no Agario. Portanto, existem duas maneiras principais de evitar a superpopulação da arena: a primeira a selecionar vários bots da população por vez e competir na arena, e tantas vezes até acumularmos estatísticas do jogo para cada bot. A segunda que o autor abordou é o lançamento de várias arenas em paralelo, digamos 50-300, tudo depende do poder de um computador em particular e, paralelamente, toda a população de bots participa de competições. A população pode ser dividida em subpopulações com suas funções e identificadores de aptidão (corresponde ao número de arenas) e depois trocar genótipos entre subpopulações. Ou imagine tudo como uma grande população de bots jogando em diferentes arenas. O autor tentou as duas opções, mas na versão de origem com uma única população de bots. O parâmetro no programa Depth é o número da arena.
Então ele contou os princípios básicos da construção de um programa. Quem quiser ver ao vivo, bem-vindo ao link para o github .
se você não conseguir iniciá-lo, um pequeno vídeo será iluminado neste momento:
Anúncio: em agosto, o mail.ru organizará outra mini copa de IA, o anúncio oficial ainda não foi visto como verdade. Mas, de acordo com informações dos telegramas do grupo, a base da competição é novamente o motor da física, algo sobre carros. Portanto, brevemente sobre os princípios de criação de um bot, aqueles que estarão interessados, é claro:
Aqui, como nosso time de futebol, é aconselhável deixar o grupo, o final é uma música separada. Deixe os finalistas escreverem sobre as vitórias, mas sobre nossa principal participação.
O mais claro e simples:
Escreva mais condições diferentes no corpo do código bot, por exemplo, se (buraco) -> pular, etc. Condições simples são eficazes no início do campeonato, então a complexidade dos bots aumentará e a vantagem de soluções condicionais desaparecerá.
E, portanto, o método mais promissor em muitos jogos estratégicos:
Método PP ( ou campos em potencial ). A ideia é linda, a busca pelo máximo ou pelo mínimo em um ambiente dinâmico. Uma grade da dimensão selecionada é construída em todo o campo de jogo ou apenas na área ao redor do bot, tudo depende do escopo do bot. Em seguida, em cada ponto nodal dessa grade, consideramos as distâncias dos objetos de interesse para nós ou, como opção, os potenciais imediatamente, eles podem ser positivos (atração, isso é interessante para o bot) e negativos (perigo para o bot). Conseqüentemente, os potenciais no ponto são resumidos e obtemos o total de potenciais em cada ponto da grade. Campo de potenciais. O bot só pode escolher o menor ou o maior potencial, dependendo da tarefa no momento. Basicamente, os campos em potencial são implementações 2D, embora o 3D pareça legal, mas haverá muitos recursos para cálculos.
O mais difícil:
As duas principais implementações são o método Brute Force ou o método Monte Carlo . Cada um deles é o tópico de um artigo separado, mas, de acordo com a sensação, são esses métodos que o levarão à final. Se é uma tese, o bot pode olhar não apenas no momento ou no passado atual, mas, se quiser, pode olhar para o futuro, um funil (cone) de possíveis resultados aparece aqui e quanto mais o bot quiser ver mais opções aparecerão. Por exemplo, no ponto de tempo Tick Zero, o bot decide ir em uma das oito direções; na etapa Tick + 1 em cada uma das oito novas coordenadas, ele tem a oportunidade de seguir novamente em oito direções, etc. é necessário levar em consideração possíveis movimentos inimigos durante esse período. Cada resultado possível dos cálculos gera um possível benefício ou dano. Com base no qual o bot faz um movimento em uma das direções. E além disso, esse cálculo nas profundezas do tempo futuro vai a cada escala. A profundidade das visualizações de movimentos é determinada pelos possíveis recursos do computador. Portanto, para recursos de computadores pequenos, surge o problema de otimizar esses cálculos.
Sobre a fonte, se houver interesse, editarei os comentários no código, enquanto o expus.
Na fonte, os sinais do Tick atual e do Tick anterior são enviados para a entrada do neurônio, tornou-se mais interessante, graças ao leitor: tongohiti pela idéia.
Para aqueles que se lembram da tese sobre a distribuição inicial de pesos na rede neural, um tópico interessante é a Inicialização do Xavire.
Obrigado pela atenção. Encontre-me nas competições de IA.
Artigos relacionados dos participantes, mas a primeira digressão :
Ela estava sentada no chão
E ordenou a pilha de letras
E como cinzas resfriadas
Peguei-os em minhas mãos e joguei-os.
Tomou folhas familiares
E foi maravilhoso que ela olhou para eles,
Como as almas parecem de cima
Sobre eles um corpo abandonado ...
Oh quanta vida havia aqui
Irreversivelmente experiente!
Oh, quantos minutos lamentáveis
Amor e alegria mortos! ..
Minha estratégia na Russian AI Cup 2017
Histórico de participação (e quase vitória) na competição anual Russian AI Cup 2016
História da Vitória na Copa AI anual da Rússia em 2015
Russian AI Cup 2014: estratégia vencedora
Medalha de ouro na Russian AI Cup 2013 - como tudo foi
O caminho para a medalha de prata na Russian AI Cup 2012