Era quarta-feira, havia uma reunião chata comum no trabalho. O designer coçou a orelha e o testador se enterrou no telefone. Um carro ligou do lado de fora da janela e recebi uma carta no telefone - a
Copa da AI russa de 2018 foi iniciada. Cerca de ninguém suspeitava de nada, e naquele momento eu já sabia exatamente o que faria no próximo mês e meio.
Olá pessoal, meu nome é
Andrey Tokarev e gostaria de compartilhar minha experiência de participar da
Russian AI Cup 2018 .
O que é isso
Russian AI Cup é uma competição anual de inteligência artificial realizada desde 2012. Aqui você precisa escrever um algoritmo que controla alguém ou algo, e esses alguém ou algo competem entre si. Este ano foi necessário controlar robôs jogando futebol.
Eu já tinha alguma experiência jogando em tais competições. Participei, em particular, da Russian AI Cup 2016 (sem prêmio) e da Mini AI Cup 2018 (2º lugar).
Vamos lá
Primeiro, criei minhas classes do mundo do jogo, objetos, peguei um vetor bidimensional e tridimensional de competições passadas e carreguei tudo no repositório Git. Obviamente, você pode usar objetos do pacote de idiomas, mas não há vetores, eles não podem ser modificados e, de fato, é mais conveniente usar suas próprias classes. O que não reescrevi é a classe da arena, ela me serviu como é e não havia necessidade de alterá-la.
Simulação
Aqui temos um mundo de jogo, e o que podemos fazer sobre isso?
Mas nada acontece, até que possamos simular o mundo do jogo, nem mesmo determinar se a bola voa para uma rede vazia. Então, estamos
cancelando a simulação. O código de simulação não faz parte do pacote de idiomas, é fornecido em um idioma que eu não conheço. Mas sua sintaxe C é semelhante, então copie e cole + definição das funções necessárias, e o sim está 90% pronto. Onde era necessário dominar minhas mãos, tentei fazê-lo com cuidado, pois os erros aqui podem ser caros e pegá-los não será fácil. Eu ainda consegui cometer alguns erros, mas isso me custou um pouco de sangue.
Imediatamente ficou claro que, se você usar simulação honesta (100 micro ticks), isso não é suficiente, é muito mais lucrativo calcular 100 opções com um micrótico do que uma opção com 100 microtiks. Ainda deixei 2 microtics para que a discrepância não fosse muito grande.
Noções básicas de estratégia
E assim temos um mundo de jogo e podemos simular sua mudança. Então, o que vem a seguir?
Existem abordagens diferentes. Quando há poucos movimentos possíveis e a profundidade não é muito grande, você pode executá-lo com força bruta: classifique todos os movimentos, mesmo os movimentos de retorno do oponente, eles terão seus próprios movimentos novamente ... ou seja, minimax Quando há muitos movimentos, você pode limitá-los artificialmente, por exemplo, você pode tomar direções que são múltiplos de 15 graus, pular para cada 10º tick e usar o mesmo minimax. Mas essa abordagem me parece adequada quando o resultado não é muito sensível a pequenas mudanças nos movimentos; aqui, um desvio de um grau na direção do robô levará a grandes desvios após a colisão.
O outro extremo, quando fazemos movimentos sem uma pesquisa exaustiva, é algum tipo de heurística. Essa abordagem pode ser viável, mas criar um jogador de futebol forte com heurísticas puras é muito difícil.
Mas a combinação dos dois métodos parece promissora: você pode primeiro se mover em uma direção aleatória e depois terminar o jogo com uma heurística que pode chegar até a bola e pular no momento certo. A mesma heurística combinada pode ser usada para prever os movimentos do oponente. Anteriormente, eu já usei algo semelhante na competição, e esse método mais ou menos não se mostrou ruim.
E assim escrevemos heurísticas (no jargão RAIK-ovsky, cara esperto ou apenas esperto)!
Como eu queria ver o resultado o mais rápido possível, o smartgay foi escrito às pressas e acabou sendo bastante idiota (até o código é vergonhoso). Acabei de calcular o tempo após o qual o robô poderia pegar a bola com base na velocidade atual da bola e na velocidade máxima do robô, e corri até o ponto em que a bola estaria naquele momento (colisões não foram levadas em consideração). Ele não sabia pular e nem levava em conta a altura da bola, podia correr facilmente embaixo da bola e, se a bola se afastava muito rápido, geralmente corria na direção oposta. Como o smart não foi capaz de pular, primeiro eu o fiz pular a uma distância fixa da bola, e um pouco depois a escolha do momento do pulo caiu sobre os ombros de um grande aleatório! A falta de uma escolha racional de um salto acabou sendo uma grande desvantagem, mas mais sobre isso mais tarde. Mas, em geral, um inteligente limpo não parecia ruim, e às vezes até marcou gols, embora também em seus próprios objetivos.
Em seguida, precisamos de uma função de avaliação (OF).
O OF inicial era assim: (1000 - tick) * goal + ball.z + alguma função da posição relativa do robô e da bola, de forma que ela suba até a bola, mesmo que não possa alcançá-la. Aqui, o objetivo pode ser -1,0,1, dependendo de haver um objetivo e para quem, e tick é o tick desde o início da simulação em que o objetivo ocorreu. A última é que o robô não adia constantemente o objetivo.
Agora, fazemos o robô correr em uma direção aleatória um número aleatório de tiques, depois transferimos o controle para o inteligente, que o leva à bola, em um momento aleatório, ele pula e
acerta a bola erra. Além disso, é melhor correr não para o centro da bola, mas com um deslocamento aleatório por uma pequena distância, para que o robô possa bater em um ângulo.
A simulação durou um tempo fixo de 2 segundos e, no final, o OF foi chamado. Esse cenário foi repetido várias vezes para cada robô e o melhor foi selecionado com base na classificação.
Até agora, essa estratégia tem uma séria desvantagem: ela não possui memória - tudo é calculado do zero em cada tick, o que significa que a estratégia pode ver um objetivo em um tick e não encontrá-lo no próximo. Não é esse o caso, você precisa corrigi-lo - salvamos a melhor opção encontrada para cada robô e a reutilizamos no próximo tick. Agora, agora, os robôs conhecem os assuntos um do outro, por exemplo, se o primeiro vai bater na bola, o segundo não corre atrás da bola, mas tenta dar um passe.
Goleiro
Precisamos de um goleiro. Meu goleiro era basicamente diferente do atacante, pois era ativado quando a bola se aproximava de uma certa distância do gol, caso contrário, simplesmente retornaria ao seu ponto base.
Sumário
Agora, temos uma boa estratégia básica que pode fazer tudo o que é necessário e que pode ser construído no futuro.
Talvez tudo o que foi descrito acima pareça simples e lógico, mas honestamente, no início da competição, não havia uma imagem tão clara da estratégia que aparecesse mais perto do fim, e levou duas semanas para implementá-la, e isso representa 1/3 da competição.
Um pouco sobre o teste
Com o tempo, Grails que dobram o poder do jogo ocorrerão cada vez menos, e teremos que escolher mudanças que aumentem de 10 a 20% nos objetivos. E então acontece que esses pequenos ganhos não são tão fáceis de identificar. Para um resultado completo, você precisa de centenas de gols marcados e, com uma frequência de gols de uma vez por minuto, são muitas, muitas horas de jogo. Por esse motivo, quase não testei estratégias no servidor, mas realizei longos testes locais em relação às versões anteriores. Mas mesmo testar localmente qualquer alteração por meio dia não seria muito conveniente. Portanto, apliquei um pequeno "truque" - testei estratégias truncadas. Se, por exemplo, em um servidor, eu passasse de 50 opções por robô, apenas 10 localmente, isso me permitiria executar testes em um tempo tolerável.
Aprimoramentos
A seguir, descreverei as principais melhorias e sua avaliação da seguinte forma: em quantos por cento a nova versão marca mais gols do que a antiga. I.e. se, por exemplo, um novo vence o antigo com uma pontuação de 120: 100, é + 20%; se obtiver 2 vezes mais, será + 100%.
- Seu goleiro deve vencer os gols. Se ele não conseguir, dê a ele mais tempo, aumente o número de opções para x10. + 15%
- Às vezes, quando o goleiro bate na bola, ele voa livremente e, embora tenha tempo de voltar ao seu lugar, ele já marca um gol. Imediatamente após bater na bola, tentamos devolvê-la ao seu lugar e adicionar o tique-taque ao qual ela retornou à avaliação com um pequeno coeficiente negativo. + 20%
- Um chute adicional na bola na frente do gol de outra pessoa aumenta a chance de um gol, daremos um bônus no OF por isso. + 60%
- Experimente nitro! Faltavam mais alguns dias para a primeira rodada, mas decidi testar o nitro com antecedência. Intuitivamente, pareceu-me que o nitro afetaria bastante a jogabilidade, já que em um tanque você pode pular no teto ou voar sobre o campo inteiro. Para começar, eu ensinei como usar o nitro apenas para o atacante, e mesmo assim apenas no ar, mas ainda não colecionei os pacotes. Nitro foi usado durante o vôo na direção agora aleatória agora tridimensional. O resultado foi que, para dizer o mínimo, não muito, não consegui espremer mais de + 20%, e o uso de nitro no chão não trouxe nenhum resultado. Portanto, o problema com o nitro foi temporariamente deixado de lado, embora, a partir desse momento, tentei realizar testes com o nitro ativado.
- Muito aleatoriedade! Aleatório é bom, é claro, ele às vezes dá truques nos quais você nem consegue pensar, mas por outro lado, quando há muito dele, a probabilidade de que tudo coincida é muito pequena. E eu tinha muito disso. Decidi tentar transferir o momento do salto para a base analítica. Como não havia aceleração horizontal no ar (esqueça o nitro), foi fácil calcular o momento de encontrar o robô e a bola (t1) e a altura da bola naquele momento (h1). Agora calculamos o tempo (t2) após o qual o robô estará a uma altura de h1, pule agora. Aqui obtemos uma equação quadrática, se não tiver solução ou t2 <t1, então pularemos cedo, caso contrário, pularemos.
O resultado me chocou um pouco, estragando o salto correto tanto para o atacante quanto para o goleiro, os testes mostraram + 200%, ou seja, a nova versão venceu os antigos 3 vezes em gols, o verdadeiro Graal! Era 17 de janeiro, depois de carregar a estratégia no servidor, conquistou uma classificação de mais de 200 em uma série de vitórias de 20 jogos e encabeçou a sandbox por um tempo.
- Ensinamos o goleiro a jogar. Até o meu goleiro ser ativado, ele permaneceu como um pilar. Fácil caminhada lateral: x = ball.x / 4 deu um ligeiro aumento.
- O oponente não deve ser previsto, mas assumido! Observando os jogos, notei que, muitas vezes, faço um gol depois que o goleiro bate a bola diretamente no adversário e ele marca um gol para mim em tempo real. Para acertar a bola contornando o oponente, primeiro você precisa determinar onde ele pode estar no enésimo número. Obviamente, não levaremos o nitro em consideração. Ainda pude determinar a velocidade do robô analiticamente, parece haver a interseção de dois círculos. Mas ele não conseguiu lidar com o território acessível. Bem, para o inferno com ele, somos programadores (não por educação), deixe a máquina contar para nós. Divida o plano em n direções, mova o robô em cada direção, os pontos finais serão os vértices do polígono, que determinam o alcance.
Como usá-lo? Acrescentei uma marca na qual o oponente pode tocar na bola pela primeira vez, com um bom coeficiente no OF. Como agora não é um cenário específico de ações, mas uma espécie de nuvem de alcance foi considerada para o oponente, removi os robôs do inimigo assim que eles entraram em contato com o solo.
Resultado + 40%. Além disso, essa abordagem tem duas grandes vantagens: a remoção de robôs inimigos no primeiro acelera a simulação, e isso, por sua vez, torna possível classificar mais opções, e no segundo não precisamos nos preocupar com o controle do oponente. Conclusão: lucro!
- Erros estúpidos, mas o que sem eles. Existem duas linhas no simulador oficial:
if abs(ball.position.z) > arena.depth / 2 + ball.radius: goal_scored()
Não sei quem, mas deixei a função abs () como está, mas em vão. A linha abs () (que não deve ser confundida com std :: abs ()) recebe valores inteiros, o que significa que os decimais são truncados. Na prática, isso significa que eu registrei o gol apenas quando a bola já estava a um metro atrás da linha de gol. Substitua abs () por fabs ()! Esta não é a primeira vez que este abs () falhou comigo.
- Nitro de novo. A segunda rodada estava se aproximando e não havia lugar para adiar o uso normal do nitro. Ele otimizou seu uso, levou em conta a definição de um salto, permitiu que o goleiro fosse usado e também começou a coletar deliberadamente pacotes pelo goleiro.
- Vamos voltar para a simulação. Eu já disse que 100 opções com um microtik são mais rentáveis do que uma opção com 100 microtics. Isso é verdade, mas isso não significa que, com um Mikrotik, tudo esteja bem, sem medidas adicionais as discrepâncias eram bastante graves, e isso impedia o futebol em nível profissional. Para melhorar a precisão da simulação, apliquei os seguintes métodos:
- Durante o salto, dois Mikrotik adicionais.
- Quando combinamos muitos micróticos, ao mover é mais correto usar a velocidade média, e não a velocidade final.
- Usando a pesquisa binária, encontramos a marca na qual a colisão ocorre e executamos duas sub-táticas: uma antes da colisão e a outra depois. (Eu não levei em conta a colisão da bola com uma superfície plana, a discrepância me parecia insignificante.)
- Correr por uma superfície curva ainda causava grandes discrepâncias e às vezes o goleiro errava por causa disso. Portanto, quando meu goleiro estava em uma superfície curva, usei 10 microtics.
Em média, foram obtidos cerca de 1,4 mikrotiks por tick e a precisão foi próxima do ideal. Claro, eu não estraguei essas otimizações de cada vez, mas gradualmente. Não sei o quanto eles influenciaram o poder do jogo, mas acho que isso é muito significativo.
O que temos
Graças a um grande número de melhorias significativas, a estratégia cresceu de forma constante no ranking e, antes do segundo turno, quase alcançou o marco histórico - classificação 5000 Elo, ganhando terreno com confiança em primeiro lugar.
Às vezes, você nem consegue acreditar no que combina aleatoriamente. Obrigado à comunidade anônima pela descoberta.Semana passada
Em conexão com uma margem tão boa, me permiti não buscar pequenas melhorias, mas procurar algo mais global, especialmente no que diz respeito aos jogos 3x3. No entanto, os experimentos voltados para um jogo mais em equipe, ou incutir um terceiro jogador em um papel especial, ou ensinar a sair durante o goleiro, falharam. A semana inteira foi passada quase sem sucesso. Apesar disso, alguns dias antes da final, eu ainda estava na liderança do ranking.
E agora, no último dia antes da final, eu começo a perder para um, depois outro e até um terceiro competidor. Se você não adicionar, você pode ficar sem um prêmio. Nada aconteceu durante toda a semana, o que posso fazer no último dia? O clima era - pelo menos desistir.
Ressurreição
Depois de ver alguns jogos perdidos, notei que todo mundo pula
como cabras no nitro, passa a bola no ar, mas a minha não consegue. Tentei a coisa mais simples que pode levar a esse comportamento - adicionei a altura da bola no momento do impacto com um coeficiente sólido no OF. Resultado + 50%, uau! Inspirado no resultado, comecei a distorcer os parâmetros intensamente (que negligenciei durante toda a competição), adicionei novas opções de pesquisa, adicionei controle de tempo no final, o que me permitiu usar o tempo ao máximo sem arriscar minha vida. No final do dia, resultou em + 150-200%, ou seja, a nova versão venceu a anterior quase três vezes em gols! Sim, sim, o mesmo que quase uma semana antes da final caiu em primeiro lugar e alcançou uma classificação sem precedentes de mais de 5000 na história do campeonato. No servidor, a estratégia foi testada com sucesso algumas horas antes da final. Depois disso, preparei-o para o lançamento final: asserções desabilitadas, adicionei verificações de divisão a zero, carreguei novamente no servidor e mudei para o modo de espera.
Parte final um
A primeira parte das finais aconteceu à noite. Acompanhei os resultados até adormecer e acordar de manhã cedo. Foram jogadas 3 ondas (em uma onda, cada uma joga com cada uma), perdi apenas um jogo contra o
TonyK e, como o Anton ainda perdia para outros jogadores, eu estava na liderança com uma margem de 7 pontos (2 pontos pela vitória). Uma lacuna bastante séria para 3 ondas, mas não o suficiente para relaxar.
No último dia, é claro, eu não pretendia fazer nada sério, basicamente distorci os parâmetros. Várias mudanças foram feitas, mas como tudo foi testado às pressas, eu nem tinha certeza absoluta de que o efeito era positivo. Em geral, o aumento foi de 0 a 20%. Mas Anton acrescentou significativamente e pelo menos começou a jogar não pior do que eu.
Nada a fazer, eu tive que enviar o que é, e esperar por sorte e um suprimento de pontos.
Parte final dois
Felizmente, os jogos foram classificados de modo que, a princípio, os líderes jogassem entre si, então não havia necessidade de se preocupar, o primeiro jogo foi contra o TonyK. A sorte estava do meu lado, venci a primeira luta e todos os outros jogos desta onda, enquanto TonyK perdeu mais um ponto. Uma diferença de 10 pontos para duas ondas até o final é quase impossível de jogar, agora foi possível relaxar.
Resultado final: 352 vitórias e 2 derrotas (ambas de Anton), 1º lugar com margem de 12 pontos.
Obrigado e outro lixo
Em geral, gostei muito da tarefa deste ano, foi “para mim” (a simulação é minha e a tridimensionalidade não me assusta) e as partidas foram espetaculares, acho interessante observar não apenas os participantes.
Gostaria de agradecer aos organizadores pela maravilhosa competição.
Também quero agradecer a todos os participantes, especialmente Anton Kozlovsky (
TonyK ) pela competição na final, Ivan Tyamgin (
tyamgin ) pela competição na caixa de areia e Alexey Dichkovsky (
Commandos ) por se abster de participar e, assim, aumentar minhas chances de ganhar.
Boa sorte a todos no próximo RAIK!