Então

Meu nome, como no ano passado, é Andrei Rybalka, só que agora tenho 33 anos. E, como eu estava entre os dez primeiros, decidi compartilhar minha abordagem de escrever um bot de jogo para a Copa AI AI de 2018 novamente.

Desta vez, a tarefa era futebol. A tarefa em si lembrava o RAIC de 2014, quando era hóquei, mas a solução era completamente diferente.

Dessa vez, o mundo era tridimensional e essa tridimensionalidade era usada na íntegra. O jogo em si lembrava mais a Rocket League .

Não vou suportar a parte introdutória, é mais fácil mostrar como ela parecia. Você pode assistir aos jogos no site ou no vídeo:

Para que nossa vida não pareça muito agradável, os desenvolvedores, além do não-determinismo do mundo dos jogos, também dividiram o jogo em 100 subwoofers, que inicialmente acabaram com uma simulação precisa para a maioria dos participantes e, mais ainda, para mim, pretendendo escrever um bot em Java lento.

Além disso, devo dizer que o campeonato é dividido em rodadas, o que provavelmente seria mais correto para chamar rodadas.

Brevemente sobre o sistema de torneios

Para iniciantes, são dadas 2 semanas para o desenvolvimento. Então a primeira rodada passa. Os 300 melhores vão além.

Após a rodada, as regras do jogo mudam (especificamente, o nitro é adicionado ao jogo) e são dadas mais 2 semanas, após as quais a segunda rodada passa.

Então as regras são complicadas novamente (o terceiro jogador é adicionado), outra semana é dada e jogamos a final.

Mas este não é o fim. Após as finais, há mais uma semana, no final da qual a caixa de areia simplesmente para, e as 6 melhores nela, excluindo os vencedores das finais, também são premiadas. A diferença fundamental entre o final da área restrita e a final do campeonato é que, na área restrita, os jogos são criados em um formato aleatório, e não apenas no formato da rodada atual.

Histórias de participação

A parte técnica será menor. Para quem a história é desinteressante, você pode rolar para baixo até ficar boa.

Primeira Rodada

Ele começou, como a maioria, com uma semana de beta. Passamos muito tempo, mais de 4 horas todas as noites.
Antes de preencher a primeira versão, foram necessárias várias iterações
codificamos até começarmos a vencer a versão anterior - coletamos - consideramos a versão atual da anterior - repetimos .

Eu não estava com pressa com o primeiro preenchimento e isso aconteceu alguns dias antes da rodada. E, como até o momento meu bot não brinca com ninguém, eu não fazia ideia de que tipo de mundo eu estava e que posições no ranking eu poderia reivindicar. Quando vi que já havia vencido mais de 100 jogos seguidos sem uma única perda, me acalmei.

Em geral, a primeira derrota que tive, ao que parece, ficou em 12º lugar, no limite de tempo, e o primeiro jogo perdido consecutivo já estava entre os 10 primeiros.

Em resumo, percebi que tenho chances de entrar na segunda rodada, onde estão as 300 melhores.
Portanto, não persegui a posição e não inundei mais nada durante a rodada, mas simplesmente continuei a trabalhar.

Naquele momento, vi que ainda havia muito espaço para melhorias sem conectar o nitro (que apareceu após a 1ª rodada), então me concentrei na parte principal da estratégia, percebendo que antes da segunda rodada eu tinha mais de 2 semanas para fixar o nitro.

Segunda rodada

Na primeira semana eu estava programando ativamente, mas ainda não conectava nitro. Eu queria fazer isso na segunda semana. Mas tudo saiu de forma diferente, porque no final da primeira semana eu havia contraído pneumonia. Como não consegui programar, acabei de enviar o que era e, pode-se dizer, a participação ativa no campeonato para mim neste local terminou.

Nas próximas três semanas antes do final do campeonato, trabalhei em uma estratégia no valor de talvez 20 horas.

Como resultado, no segundo turno, meu bot, em princípio, não sabia que havia nitro no jogo, mas de alguma forma ainda ocupava o 16º lugar.

Final

Na final, um terceiro jogador foi adicionado.

Eu escrevi em Java lento, e não em C ++, já que 7 em 8 pessoas são mais altas do que eu na classificação, e antes disso, meu bot geralmente entrava em tempo limite, então, com o advento do terceiro jogador, ele começou a cair em 100% dos jogos. Felizmente, os jogos na sandbox são criados em um formato aleatório, então eu automaticamente
perdeu apenas a cada terceiro jogo e, portanto, não voou muito. Parece ter caído para o 18º lugar.

Exceto pela programação, editando os coeficientes na função de avaliação e executando os testes, então pela primeira vez, após o início da doença, sentei-me no bot na noite do dia anterior à final. Ele adicionou um nitro muito simples, direcionado estritamente para cima, para que dois atacantes parassem de correr no mesmo ponto e colidissem um com o outro lá, e cortassem tudo o que pudesse para um jogo 3x3, começando pela profundidade da renderização e terminando com a precisão da simulação, apenas o bot não morreu por tempo limite.
Nesta forma, jogou o final.

No intervalo entre as metades das finais, sentei-me novamente no bot e passei algumas boas horas: na maioria das vezes, as mudanças diziam respeito à seleção dinâmica de coeficientes, interrupção precoce da genética etc. Em geral, eu estava procurando um equilíbrio entre precisão e profundidade e velocidade de erro de cálculo.
Além da luta contra a velocidade, ele fez mais algumas mudanças:

• Enviou um atacante distante (em relação à bola) para um ponto no meio entre a bola e o gol do oponente
• Corrigi um pouco o nitro (a descrição estará na parte técnica). Ainda era extremamente simples, mas se tornou muito mais eficiente.

Total, tendo executado os testes e vendo a pontuação 395: 254 em relação à versão anterior, eu me acalmei com isso. Isso me permitiu ficar em 9º lugar na final.

Sandbox Finale

Continuei doendo e não trabalhei no bot a maior parte da semana. Um dia antes do final, vi que várias pessoas enviaram versões novas, que geralmente vencem contra mim e podem jogar caixas de areia fora de prêmios. Então passei mais algumas horas.

A única grande mudança é que desenterrei minha filial no Git há três semanas, na qual fiz uma simulação do movimento do inimigo usando meu algoritmo simplificado. Naquela época, funcionou mal, mas eu lembrei disso, fiz testes, vi
que supera a versão anterior quase dobrou e inundou. No total, no momento da parada, eu estava em 10º lugar na tabela geral, o que corresponde ao 4º lugar nas finais da área restrita.

Como tudo funciona (parte técnica)

Peço desculpas antecipadamente, caso haja imprecisões na terminologia. Além disso, como escrevo de memória, é possível que em algum lugar não descreva a versão final.

Portanto, algoritmos genéticos estão no centro. O cromossomo consiste em vários genes:

• Número fracionário no intervalo -PI..PI, especificando a direção do movimento
• Um número inteiro no intervalo de 0 a 10 que especifica o número de repetições dessa ação
• Número fracionário de 0 a 1. Se o valor estiver acima de algum limite, faça um salto

O genótipo pode incluir um número diferente de cromossomos, mas de maneira que o número total de ações (incluindo repetições) seja 40.

Inicialmente, crio várias dezenas de genótipos aleatórios. A eles eu adiciono:

• A trajetória certa na bola
• Trajetórias diretas em todas as direções, apenas 10 peças com um deslocamento de 36 graus
• Um genótipo que simplesmente não faz nada (sem ele, o bot sempre roda em algum lugar, mesmo que já esteja no ponto ideal)
• Melhor genótipo do carrapato anterior

Então tudo é simulado e executado através da função de avaliação. N melhores genótipos "sobrevivem" e são clonados M vezes com mutações. Após a mutação, cada gene muda em um determinado intervalo com uma probabilidade de 10%. Bem, isso foi repetido por várias gerações.
Não há cruzamento, neste problema não vejo sentido nele.

No total, o número máximo possível de trajetórias por tick por jogador de futebol foi de cerca de 800, mas na verdade, na maioria dos casos, foi muito menor, porque em alguns casos (por exemplo, quando em um futuro próximo definitivamente não conseguiremos tocar a bola), o movimento dos jogadores foi substituído por heurísticas simples. Além disso, N, M e o número de gerações dependiam da situação no campo. Primeiro de tudo, da distância até a bola. Além disso, o erro de cálculo é interrompido antes do previsto (mas não antes da 5ª geração) se uma trajetória com uma estimativa aceitável for encontrada.

Macro

O goleiro corre para o ponto em frente ao centro do gol. Meus testes mostraram que é melhor para mim jogar em pé na frente do gol, e não dentro deles, como a maioria dos jogadores no topo.

A posição do ponto se desviou do centro, dependendo de vários fatores: a posição e a direção do vôo da bola, o ponto em que a bola atingiu meu objetivo, se um objetivo é planejado, a localização do oponente atacante mais próximo etc.

Se a bola estiver do lado do oponente e voar em direção ao seu objetivo, podemos optar pelo nitro.

Se meu goleiro conseguir acertar a bola mais cedo do que o atacante (mais algumas condições), o atacante ignora a bola e corre para um ponto no meio entre a bola e o gol do adversário. Passei por muitas opções, onde exatamente para ele correr. No meu caso, este funcionou melhor.

Caso contrário, se a bola estiver muito longe, o atacante corre em linha reta até o ponto de contato mais próximo da bola com o chão, no qual ele pode interceptar a bola (se não tivermos tempo para o primeiro ponto de contato, verifique o próximo, etc.)

Caso contrário (quando a bola chegar), o atacante corre para onde a função de avaliação diz a ele. Sim, e também, se o nitro estiver próximo e pudermos buscá-lo, nós o selecionaremos.

Em um jogo de 3x3, o segundo atacante tem mais chances de apontar para a bola e com menos corrida para a frente, esperando um passe do goleiro. Mas se ele ainda funcionar, outro ponto será escolhido - mais próximo da linha central.

Além disso, cada tick simulou a bola 100 ticks para a frente com 100 microtics (com cache).

Essa trajetória tem sido usada em muitos lugares. Por exemplo:

• Para determinar os pontos de toque da bola com o chão
• Para descobrir se a bola ameaça meu objetivo e se o goleiro precisa ser alternado para o modo de simulação

A mesma trajetória exata foi usada na simulação das trajetórias dos jogadores, para não contar a bola todas as vezes. Mas apenas até a primeira colisão da bola com qualquer jogador de futebol.

Aliás, escrever Footballist era preguiçoso, as palavras Player, Robot eram reservadas por estratégia,
então minha classe de wrapper foi chamada simplesmente Cara :)

Simulação

Na maioria dos casos, foi com um micrótico, mas em algumas situações mudou para o modo preciso com um grande número de microtics (no início era 100, depois foi reduzido para 50 em um jogo 2x2, porque os testes mostraram que a diferença nos resultados estava dentro da margem de erro e para 10 em 3x3, porque de outra forma voou para tempos limite).

No modo preciso, eu mudei no momento do salto ou estou tão perto da bola que é possível uma colisão no próximo tique. Além disso, havia também uma massa de pequenas muletas, hacks, otimizações, nas quais eu mesmo não entenderei.

Por exemplo, a bola voadora ainda era simulada com 1 Mikrotik, mas se após o próximo Mikrotik vi uma colisão, ele voltou à posição anterior e a simulou novamente com maior precisão.

Além disso, eu também fingia ser outros jogadores (tanto meus quanto dos outros) se eles estivessem no ar (e, portanto, sua trajetória é mais fácil de prever) ou estivessem próximos da bola. Para os oponentes, a versão final usava uma versão simplificada da minha própria estratégia de tomada de decisão, que era lançada a cada 5 ticks (na maioria das vezes, não permitia velocidade).

Ao simular cada personagem, contei a mim mesmo, a bola e outros jogadores de futebol 40 pontos à frente (meu limite no número de ações no genótipo) e depois simulei o mesmo número de pontos em apenas uma bola.

Nitro

Simples a indecente.

Na versão final, o nitro é sempre ativado, se estiver, se o jogador estiver no ar e se ele não bater na bola nos últimos tiques.

No começo, sempre direcionei nitro para cima, mas depois tentei experimentar e a opção de ir exatamente para o centro da bola funcionou melhor. Eu também tentei opções para que a direção do nitro fosse escolhida pela genética.

Funcionou muito pior. Talvez devido à falta de profundidade de pesquisa.

Função de classificação

A soma das pontuações para cada tick com atenuação de 2% por tick.

O maior peso, é claro, tinha um objetivo. Várias coisas influenciaram seu peso:

• A distância da bola ao goleiro inimigo no momento do gol (quanto mais longe, melhor)
• Coordenada Y da bola (porque no topo do gol é muito mais difícil acertar)
• A velocidade da bola ao longo do eixo Z (que é direcionado para o gol do inimigo)

Ao me atacar, tudo é exatamente o mesmo, apenas com o sinal oposto.

Além disso, para o atacante, a pontuação geral dependia de:

• Distâncias do jogador à bola (para que ele corra até a bola mesmo que não consiga acertá-lo)
• Penalidade pelo salto (saltar apenas se houver tantos pontos que excederão essa penalidade)
• Distâncias no próximo tick da simulação da bola para os adversários
• Coordenadas da bola Y (quanto maior, menor a chance do inimigo de interceptá-la)
• Cosseno do ângulo entre a direção da bola e o centro do gol inimigo
• Sinalizar se eu toquei a bola
• Bandeira, se o inimigo tocou a bola
• Bônus para a seleção de nitro

Além disso, havia um pequeno bônus por atingir um jogador inimigo. Embora de fato, tenha acontecido, mas raramente.

Para goleiro:

• Bônus por distância da bola, velocidade da bola em Z, posição da bola em Y
• Penalidade pelo salto
• Grande penalidade por encontrar a bola na área em frente ao meu gol
• A distância entre os inimigos e meus atacantes foi levada em consideração (para que a bola voasse para longe dos inimigos, mas, se possível, voasse mais perto dos meus atacantes)
• E mais algumas coisinhas.

Aprendizado de máquina

Foi apenas um pouco em um dos ramos do git como um experimento. Mas parece-me que vale a pena mencionar de qualquer maneira. Não consegui trazer isso à minha mente (e não sei ao certo o que fazia sentido).

Em geral, tentei prever com sua ajuda se o inimigo pode interceptar a bola com base nas posições e velocidades do inimigo e da bola. Planejei usar isso na função de avaliação. Penalize trajetórias possíveis de interceptar.

Mas entendi imediatamente que não podia pagar não apenas uma rede neural, mas nada sério, porque isso teria que ser feito 80 vezes por trajetória. Bem, mesmo que sejam 40 ou 20, se nem todos os ticks forem contados, mas de qualquer forma, eu não tinha reservas de tempo, então nem considerei essas opções.

Aqui está o que eu fiz:

Eu corri vários jogos com um bot modificado, nos quais, ao procurar uma trajetória, salvei dados sobre mim e a bola, bem como uma bandeira, se uma trajetória foi encontrada na qual intercepto a bola.

Eu considerei todas as coordenadas relativas ao jogador de futebol. I.e. Eu sempre o tinha na coordenada [0,0,0], então mantive apenas 10 campos: a posição relativa da bola, o vetor de velocidade da bola, o vetor de velocidade de um jogador de futebol, a bandeira de interceptação binária. Salvei o conjunto de dados apenas para a parte central do campo, porque Percebi que algoritmos simples ainda não funcionam e são responsáveis ​​por placas.

Em seguida, alimentei esse conjunto de dados DecisionTreeClassifier com max_depth = 7. A árvore treinada deu precisão, tanto quanto me lembro, da ordem de 90%.

Em seguida, exportei a árvore para um conjunto de ifs (que DecisionTree é essencialmente).

Parecia algo assim:

public static boolean predict(double dude_vel_x, double dude_vel_y, double dude_vel_z, double ball_rel_pos_x, double ball_rel_pos_y, double ball_rel_pos_z, double ball_vel_x, double ball_vel_y, double ball_vel_z) { if (ball_vel_z <= 6.4765448570251465) { if (dude_vel_y <= -6.087389945983887) { if (ball_vel_z <= -20.188323974609375) { if (dude_vel_x <= 13.032730102539062) { if (ball_rel_pos_y <= -1.1829500198364258) { return ball_vel_y <= 18.906089782714844; } else { return false; } } else { return true; } } else { // ............................ 

Nessa fase, realizei os testes, não vi nenhuma melhora e adiei o julgamento para mais tarde, que, devido às minhas aventuras, nunca chegou.

Schroedinbag

Em algum lugar após a primeira rodada, peguei esse animal raro em minha casa.

Quem não sabe, é um bug tão grande que eles encontram apenas lendo o código e, após encontrá-lo, o desenvolvedor se pergunta como o programa poderia funcionar. E no meu caso, ela também ficou no top 10.

Em geral, o problema era que um construtor era chamado na função de cópia do gene, na qual um argumento opcional foi omitido contendo o valor desse gene. Na ausência desse argumento, o valor foi selecionado aleatoriamente. Assim, ao tentar copiar um gene, em vez de copiar, ele criou uma nova instância aleatória.

De fato, em vez de genética, eu fiz uma pesquisa aleatória, porque cada marca simplesmente gerou várias centenas de caminhos aleatórios e selecionou o melhor.

Após a correção (que consiste em adicionar 2 caracteres ao código), o jogo se tornou cerca de 3 vezes melhor.

Dança ritual

Em algum momento, notei que os jogadores às vezes saltam sem motivo, estando longe da bola, apesar da penalidade.

A explicação acabou sendo tal que contei o momento do salto com uma precisão de 100 microtics. E às vezes acontecia que, exatamente no momento do salto, havia uma colisão da bola com a barra. E, dependendo da precisão do cálculo precisamente neste tick, a trajetória proposta levou a um objetivo ou não.

Grosso modo, a bola voa para o gol do adversário e bate no poste. meu jogador de futebol, correndo do outro lado do campo, simula uma trajetória sem pular (com 1 mikrotik) e vê que a bola não bate no gol.

Em seguida, outra trajetória entra, com um salto exatamente no momento em que a bola bate na barra. E como conto um tique com um salto de 100 Mikrotiks não apenas para um jogador de futebol, mas também para uma bola, o ângulo de salto calculado da bola difere do ângulo obtido no caminho com 1 microtik, e pode acontecer que a bola nessa trajetória mais precisa caia o portão.

E, portanto, é essa trajetória que será selecionada e o bot irá pular.

Em geral, realizando uma dança ritual com saltos, os jogadores namanizaram um objetivo :)

Recurso assassino

Ela não é

Teste

Eu dirigi jogos intermináveis ​​em 8 threads (4 em cada computador e laptop). Eu escolhi o número de jogos para que fosse estatisticamente significativo.

Com uma melhoria significativa na estratégia, poderia ser satisfeita com meio mil objetivos no total,
com correções menores, saiu para a noite e depois a conta chegou aos milhares.

Seleção genética de constantes

Eu tentei antes da primeira rodada. Não deu nada porque, para a genética, você precisa jogar um torneio em um grande número de jogos.

Tentei jogar 100.000 ticks, mas isso não foi suficiente. Com uma pequena diferença de força (e geralmente ao escolher constantes, esse é exatamente o caso), o vencedor por 100 mil ticks depende muito do caso. Você precisa jogar muito mais para ter certeza do vencedor. E como não podia deixar a seleção por um dia ou mais, recusei esse empreendimento.

Em conclusão

Agradecimentos tradicionais aos organizadores. A tarefa foi interessante. É uma pena que eu tenha sido forçado a perder quase metade do campeonato e realmente não fiz nada para nitro ou três jogadores.

Como resultado, até o final, observei na caixa de areia como minha estratégia vence no modo 2x2 sem nitro com uma pontuação de 13: 2 contra qualquer Mr.Smile, que ficou em 3º lugar na final, e depois de alguns jogos perde para ele o mesmo 12: 2 no modo 3x3 com nitro :)

E, claro, o vídeo do meu visualizador proprietário:

Somente você provavelmente terá que se despedir deste visualizador em futuros campeonatos.
Cada vez que estou cada vez mais convencido de que, se você está se candidatando a lugares normais, a única opção é escrever em ...

... bem, você entendeu.

Cansado de descansar na lentidão do Java e reduzir a força da estratégia para cumprir o tempo previsto.

Espero que alguém tenha encontrado algo interessante ou útil nesta minha obra com uma nota de caráter autobiográfico :)