Inicialmente, eu não tinha planos para um artigo, especialmente sobre falar em uma conferência. Mas houve uma conferência. E depois de falar sobre isso, os telespectadores fizeram perguntas para mim sobre a implementação de alguns problemas técnicos. E assim, acabou palavra por palavra - um artigo.
Gravação ao vivo abaixo do link .
Isenção de responsabilidade: este artigo é uma tentativa de responder a algumas dessas perguntas. Ficarei feliz se surgirem novas perguntas, respondendo que haverá uma oportunidade de aprender algo novo. E sim, este artigo não é de forma alguma uma tentativa de sentir o tilintar dos tubos de cobre.
E então, vamos começar desde o início desta história. Na primavera de 2018, o mail.ru anunciou um concurso de programação baseado no jogo Agairo . A essência da competição é a criação de um bot de jogo.
Regras de competição neste link . Mas para ser breve e descrever as regras com suas próprias palavras, você precisa criar um bot para jogar no Agairo. Ao mesmo tempo, um jogo popular da Internet (no sentido de ser lançado a partir do navegador), cuja essência é comer seus irmãos mais novos e fugir dos maiores. Você controla uma roda de cores em um espaço bidimensional limitado. Para criar a jogabilidade nesse espaço, além do seu círculo, existem outros círculos controlados de acordo por outros jogadores. Existem alimentos (pontos coloridos) para o crescimento, obstáculos adicionais são introduzidos na forma de "vírus", uma colisão que cria uma divisão do seu círculo em outros menores, o que complica parcialmente o processo do jogo, pois os pequenos comem os maiores e os maiores são mais seguros.
Vou dar uma foto de uma variante do jogo para competições
Além disso, por jogador, queremos dizer não o desenvolvedor do bot, mas o próprio bot.
Os organizadores da competição como um todo mantiveram o conceito original do jogo, mas adicionaram uma série de inovações. O principal deles é a restrição da revisão do bot e a introdução de uma lei física simples chamada inércia. A física está em processo de física há muito tempo; portanto, a inércia está associada não apenas a nós, mas também a quantidades como massa, velocidade e aceleração. Não precisamos de mais nada do mundo da física.
Espero que a parte literária tenha prestado atenção suficiente e que esteja na hora de passar para o componente técnico da competição e participar dela.
Isenção de responsabilidade 2: tenho certeza de que o que foi descrito abaixo pode ser mais fino, mais elegante e inteligente, mas como aconteceu.
Portanto, anote a receita e os ingredientes principais, eles não são todos novos, mas você pode adicionar o seu ao seu gosto.
Tarefa: Crie um bot que possa reproduzir o Agairo por conta própria.
A idéia principal: Use redes neurais (doravante denominadas rede neural, rede neural (NN)) como um elemento de controle do bot.
Principais ferramentas de produção: Microsoft Visual Studio e c # com uma transição suave para c ++.
Então, o mais importante para o autor é escolher ou entender seu leitor, para quem estou escrevendo, ele sabe o que são redes neurais, algoritmos genéticos e como descrever tudo isso em detalhes.
Isso é tudo, escolhi meu leitor, meu leitor sabe tudo isso, mas não tão bem para usá-lo na prática.
Portanto, ao escrever este artigo, lembrarei formas simples, como um neurônio e uma função de ativação.
Para visualização, usarei imagens desenhadas à mão, que devem ser lidas como: se você encontrar algum erro, escreva, redesenhe para as corretas.
Então, tudo está pronto para ser enviado ao caminho da construção do software do bot. Vamos começar:
Nós tomamos o ciclo, ou melhor, os organizadores da competição o prepararam para nós como um exemplo de um bot simples. Vamos aprofundar, faça o download do arquivo para o participante do concurso no repositório usando este link . Os organizadores prometeram que o servidor do concurso continuaria funcionando e, após sua conclusão, poderemos verificar essas palavras. Abrimos o arquivo e escolhemos uma linguagem de programação compreensível para nós.
A documentação da competição também descreve a tecnologia de comunicação do cliente (leia nosso bot) e do servidor de um data center que vive em algum lugar profundo. Em resumo, a comunicação passa pela linha do console, escrevendo e lendo comandos a partir dela.
A palavra mágica Serialização deve ser mencionada aqui: ela está compactando seus dados em um formato que o serializador entende e a capacidade de ler esses dados novamente no programa usando o serializador. Existem muitos serializadores, o formato seqüencial mais simples para gravar no arquivo txt também é um serializador, mas simples. O que precisamos saber sobre serializadores é que eles existem e são quase transparentes em termos de API. Os organizadores provavelmente entenderam isso e, portanto, o exemplo de seu bot contém todas as instruções necessárias para trabalhar com o serializador. No nosso caso, era JSON .
Para o bot após o serializador, o mundo do jogo parece uma matriz de dados recebidos no início do ciclo mencionado. Os dados sobre o mundo do jogo são limitados pelo servidor de acordo com o raio de visão igual aos 4 raios do bot, lembre-se de que o bot é um círculo. E o círculo ao redor do círculo é a borda externa da revisão, embora o círculo externo esteja levemente inclinado em direção ao movimento do bot em relação ao centro do bot, mas isso pode ser negligenciado no nosso caso.
E assim temos um ciclo, a medida do ciclo é Tick, quantos ciclos passaram, tantos ticks foram executados. Provavelmente não lembraremos mais deste Tick, mas ele introduzirá várias limitações e simplificações importantes: o tempo de cálculo é limitado não apenas por um único Tick, o tempo de uma iteração do ciclo, mas também pelo tempo total de cálculo, após exceder o tempo em que o servidor do jogo desconectará seu bot do gerenciamento. Marque e tempo para dar comandos ao bot. Vamos considerar um quantum de tempo de jogo, Tick é uma quantidade indivisível de tempo no mundo do jogo. Vantagens seguem a partir disso. Como o tique é igual a 1 por padrão, é mais fácil calcular velocidades, acelerações e outros valores. Em todas as fórmulas, multiplicamos por 1, em vez de usar algum tipo de tempo de curva t = 0,0015 segundos nelas. Os erros nessas operações também são mínimos.
Tudo acima é um pouco semelhante a um filme, parece que a imagem na tela é animada e comovente, mas, na verdade, são mostrados 25 quadros diferentes por segundo, e nosso cérebro apenas considera isso uma frequência suficiente para uma percepção completa da dinâmica do vídeo. Então o bot vê o mundo em intervalos de tempo. Tick é uma estrutura do mundo do jogo.
A rede neural também funcionará de acordo com os ticks.
A imagem começa a desaparecer do lado do bot:
O servidor envia os dados processados sobre o mundo para o bot-> Tick Start-> o bot recebe os dados -> processa-> envia os comandos de gerenciamento de bot para o servidor-> O servidor lê os dados-> Fim do Tick e, em seguida, em um círculo ou loop quase infinito, 45000 ticks no final o jogo é uma figura bastante substancial.
Nota importante: você pode pular o Tick e não obterá nada por isso. Existem casos de servidores em que cada Tick precisa informar algo ao servidor, para que o servidor não suspeite do bot travado no programa de controle.
O autor decidiu não tocar muito no servidor, mas preciso dizer algumas palavras sobre ele. Existe um modelo do mundo do jogo no servidor e, de acordo com ele, ele executa cálculos e ações. O programa do servidor inclui os seguintes blocos:
- cálculo de colisões de bot (processamento de colisões com os limites do mundo do jogo, quem comeu quem, bot bot ou comida de bot ou colisão com vírus, etc.)
- cálculo da física do bot (movimento do bot, mudanças na velocidade do bot de acordo com comandos ou colisões do bot que ocorreram)
- cálculos relacionados à divisão de bots ou combinação, se possível, adição de alimentos e outras funções para manter o mundo do jogo.
- e, claro, enviando e recebendo dados para bots em ticks de jogos.
Esse servidor é chamado de "comando". Ou seja, todas as ações ocorrem no lado do servidor, o que remove problemas com a sincronização de dados. O cliente (leia o bot) só recebe uma imagem pronta do mundo, como seus outros rivais, aqui a igualdade das posições dos bots é alcançada, não há prioridades e filas. Novamente, uma mudança nas coordenadas do bot ocorre no servidor, por exemplo, o bot dá um comando para mudar e somente no próximo Tick aprende suas novas coordenadas, que nem sempre coincidem com a equipe, como opção como um obstáculo na forma de uma parede do mundo do jogo.
foto do site dos organizadores
Descobrimos a leitura dos dados com o bot e o servidor de gerenciamento, agora vamos dar uma olhada nas profundezas do dispositivo bot.
Como o leitor provavelmente já entendeu, haverá poucas palavras e muito trabalho, ou vice-versa.
O bot é controlado por uma rede neural. Curto e amplo, mas não totalmente claro como.
A escolha de uma rede neural e a técnica para sua implementação.
No momento, decidimos que a rede neural para nós é uma caixa preta que possui uma entrada e uma saída.
A entrada e a saída para nós serão matrizes unidimensionais com uma dimensão de N = 16 para entrada e uma dimensão de M = 4 para saída.
Como a natureza da rede neural artificial é aproximadamente copiada da rede neural natural, seria bom aproximarmos a estrutura dos dados de entrada dos dados naturais. Na natureza, vários sensores são responsáveis por isso. Então fique com os sensores bot.
A opção a seguir foi selecionada experimentalmente (a imagem é simplificada para 8 sensores e uma rede neural 4x3, mas isso é apenas para confundir meu leitor):
O campo de visão do bot é dividido em setores iguais (possivelmente até desiguais). Cada setor fornece um sinal para uma das entradas da rede neural. Assim, se dividirmos a área ao redor do bot em 16 setores (360/12 = visão geral do setor em 22,5 graus), obteremos 16 entradas da rede neural. Normalmente, um sinal variando de -1 a 1 é aplicado à entrada de uma rede neural, portanto, será necessário normalizar os sinais de entrada.
O racionamento é, simplificado, dividindo o sinal total pelo seu valor máximo possível. É claro que é possível fazer a normalização dinâmica, ou seja, procurar o máximo de cada vez e trazer o valor do sinal à sua norma, mas definiremos o valor máximo na forma de uma constante igual ao número máximo de objetos em um setor e não o alteraremos no processo de trabalho no bot.
Os sinais podem ser positivos ou negativos, concordamos que o valor do sinal de 0 a 1 é um motivo positivo para o nosso bot (comida, comida na forma de um bot menor), um valor de sinal negativo de -1 a 0 é um motivo negativo para o bot (parede mundo do jogo, outro bot maior).
desenho
Um sinal de um setor é uma quantidade normalizada que consiste na soma de sinais individuais. Cada sinal individual, como foi dito, tem um sinal e magnitude. A magnitude do sinal é definida como uma função proporcional da distância. A distância mínima é o limite do círculo do bot de definição; a distância máxima é a borda da visibilidade do bot. Assim, se recebermos um sinal positivo de, por exemplo, alimentos que entram apenas no setor a uma distância máxima, o sinal será fraco e aumentará se o bot se aproximar dos alimentos.
Os sensores na forma de setores eram mais adequados para este caso, mas pode haver simplesmente antenas de sonda, aqui a fantasia está do seu lado. Obviamente, o autor tentou várias opções para dividir em setores de 4 para 72, mas a prática mostrou que a rede neural é treinada com sucesso em 16 setores e está pronta para controlar o bot, mesmo com quatro setores. Aqui se manifesta a flexibilidade da própria natureza da rede neural.
Finalmente, a palavra treinamento em rede neural foi falada. Mas, por enquanto, decidimos que a rede neural é uma caixa preta com entrada e saída e, como analisamos os dados de entrada, resta dizer algumas palavras sobre os dados ou sinais de saída dessa caixa, o que fazer com eles e como processá-los.
Definimos a dimensão do sinal de saída como 4. Esse número é uma manifestação do dualismo das coordenadas cartesianas e polares. O autor não esqueceu a natureza do conhecimento de seu leitor e, portanto, lembra-o com o desenho de um conhecimento já adquirido.
Assim, os desenvolvedores de servidores usaram logicamente as coordenadas polares para simular o mundo do jogo e, para os bots e seus desenvolvedores, forneceram polidamente coordenadas cartesianas. Portanto, o autor teve que escolher um lado nesse sistema de coordenadas. Para uma rede neural, um sistema de coordenadas polares contendo apenas a magnitude (comprimento de leitura) do vetor e o ângulo de seu desvio é mais compreensível. Afinal, você também entende as palavras “vire à direita” em vez de dar dois passos ao longo da ordenada e três ao longo da abcissa.
Portanto, 4 sinais de saída, são 2 sinais sobre o aumento ou diminuição do ângulo do vetor de velocidade do bot e mais 2 estão aumentando ou diminuindo a magnitude do vetor de velocidade.
Mas como o servidor do jogo pediu para dar comandos para gerenciar o bot em coordenadas cartesianas, um par de fórmulas para traduzir de coordenadas polares para coordenadas cartesianas e toda essa desgraça ficou em seus lugares (este é um pseudocódigo semelhante a c #).
float rotate1 = outputs[0]; float rotate2 = outputs[1]; float speed1 = outputs[2]; float speed2 = outputs[3]; if (rotate1 > 0.65 && rotate2 < 0.65) angle = angle + 35 * PI / 180; if (rotate1 < 0.65f && rotate2 > 0.65) angle = angle - 35 * PI / 180; if (speed1 > 0.65 && speed2 < 0.65) speed = speed + 2; if (speed1 < 0.65 && speed2 > 0.65) speed = speed - 2; dx = speed * Cos(angle); dy = speed * Sin(angle);
Os sinais estão no lugar, assim como um bot. Parece que eles lhe deram sinais de entrada, mas na saída algo não vale nada: ele se mantém ou se move aleatoriamente.
Então veio abrir a caixa preta e olhar para dentro.
Para ser continuado.
Mas antes da nova série de teasers:
O bot roxo na rede neural joga no Local Runner contra os bots padrão que os organizadores costuraram nele por padrão.