🔱 📡 👩‍✈️ Meu bot para a Copa AI AI 2019 🤚🏽 🚭 👩🏼‍🎓

Aconteceu que este campeonato foi o primeiro para mim, onde fui capaz de ocupar um lugar digno, pelo qual não tenho vergonha, então decidi escrever o artigo agora também. O caminho que eu fiz para este lugar: 1192º lugar no campeonato do 13º ano, 241º no campeonato do 17º ano, 91º no campeonato do 18º ano e, finalmente, 16º (e 5º e na caixa de areia) coloque nela.

Pensamentos gerais

Acredito que uma das principais razões para o desempenho relativamente bem-sucedido na RAIC foi uma mudança na abordagem para escrever sua estratégia.

Antes, tentei escrever imediatamente algo grande e complicado, sem etapas intermediárias, e a primeira versão só pôde ser preenchida duas semanas após o início do campeonato, mas no passado eu não conseguia colocar o tempo todo previsto e a primeira versão era preenchida somente após a final .

Tudo isso levou ao fato de que, embora outros participantes pudessem testar suas estratégias de vida, eu ainda não tinha uma solução pronta, embora ruim. Portanto, quando foi possível preencher, verificou-se que a abordagem escolhida não funcionou ou funciona mal e, como muito tempo e esforço foram investidos, não havia possibilidade radical de alterá-la.

Portanto, decidi que desta vez faria diferente. Com base na experiência de participações passadas, notei que o bot inicial, apesar de toda a sua primitividade, foi escrito de maneira bastante racional e, desenvolvendo-o, você pode adicionar e testar lentamente novos recursos e verificar imediatamente as estratégias de outros participantes. Fiquei especialmente convencido de tentar essa abordagem no artigo do ano passado da T1024.

Também decidi por mim mesmo que, quanto mais complexa a abordagem, menos eficaz ela está em minhas mãos. Por exemplo, não faz sentido usar a genética onde é possível fazer uma pesquisa exaustiva e, se houver uma opção para escolher menos opções, mas todas, ou todas, mas a genética, é melhor escolher a primeira opção. Além disso, ao ler artigos de comando, Concluí que otimizações específicas para a tarefa sempre serão mais eficazes que o algoritmo geral.

No entanto, mesmo agora eu estava três ou quatro dias atrasado, antes de conseguir preencher a primeira versão do bot, na época eles já estavam em guerra na caixa de areia.

O que eu fiz neste momento? Escrevi um simulador, cuja importância aprendi em campeonatos passados. Diferentemente do ano passado, onde o pseudocódigo do simulador estava disponível imediatamente, este ano toda a mecânica teve que ser lida na documentação. Felizmente, como compensação, a mecânica do jogo não era muito complicada e direta, então não tive problemas especiais.

Versões anteriores

Então, tendo em minhas mãos um simulador bruto, ainda que torto e pronto, a primeira coisa que fiz foi estragar as esquivas (função Dodge). Desde que decidi agir da maneira mais simples possível, as evasões foram feitas da maneira mais simples possível - verificamos o movimento em nove direções (4 axiais, 4 diagonais e permanentes) e examinamos em quais dessas direções a unidade receberá o menor dano.

O restante da funcionalidade do bot permaneceu quase completamente como o Início rápido. A designação do alvo também foi a mais primitiva possível - uma cadeia de ifs que seleciona a ação mais adequada para a unidade: para o inimigo, do inimigo, para o kit de primeiros socorros, armas, etc.

Surpreendentemente, essa abordagem, gradualmente se tornando mais complicada, mas sem alterar sua essência, permitiu que ela chegasse quase ao topo antes da primeira rodada (uma vez que o bot chegou ao segundo lugar na caixa de areia) e geralmente permaneceu em algum lugar nos dez primeiros lugares.

No entanto, isso não poderia durar para sempre, e o bot teve que ser melhorado. No entanto, não havia idéia do que e como melhorar, todas as tentativas de mudar algo na estratégia levaram ao fato de que ela estava perdendo a versão antiga. Pequenas alterações foram feitas, mas nada mais.

A falta de idéias levou ao fato de que nas rodadas 1 e 2 eu ocupei 29 e 19 vagas, respectivamente, e embora eu tenha ido à final, ficou claro que algo tinha que mudar radicalmente. Foi antes do final (e depois do final) que o maior número de mudanças significativas foi feito.

Já em algum lugar do meio do campeonato, tentei experimentar movimentos mais inteligentes, mas todas as tentativas não tiveram êxito. A idéia inicial era escolher a direção em que a diferença entre a chance de acertar seu bot no inimigo e o inimigo no bot era máxima. Para esse experimento, passei quase todo o tempo alocado para a final, com um resultado zero.

Portanto, para os mapas finais em vários níveis, o bot acabou completamente despreparado. A cadeia de ifs produziu resultados relativamente bons em mapas de nível único das rodadas 1 e 2, mas acabou sendo inadequada para mapas de vários níveis das finais, eu também não tinha um sistema de navegação para mapas complexos, pois em mapas simples era possível gerenciar a mudança do código de inicialização.

— .

Todo o controle de disparo está na função AimHelper.

Tudo descrito abaixo implica que o alvo é a unidade inimiga visível mais próxima do bot.

Existem apenas três tipos de armas, no entanto, cada uma delas requer sua própria abordagem. É melhor disparar com mais frequência com uma metralhadora, mirar melhor com uma pistola e, em seguida, é importante atirar com um lançador de foguetes para causar mais danos ao inimigo do que a si mesmo.

Inicialmente, não havia como mirar, o bot mirava apenas no centro da unidade. Mais tarde, uma previsão do movimento da unidade foi adicionada se ela estiver em um vôo não controlado (cai ou voa do jumppad). Para fazer isso, simplesmente simulei o movimento da unidade até que a distância que a bala possa voar para N ticks se torne igual à distância da unidade.

Ao testar contra o bot inicial, ele notou seu hábito muito desagradável de saltar constantemente pequeno, e se o bot sempre apontava para o centro do inimigo, isso fazia com que a visão se movesse constantemente e a propagação aumentasse muito rapidamente ao máximo. Para contrariar, foi adicionado um código que verifica se a chance de acertar com o atual ângulo de mira é melhor ou igual à chance de acertar com um novo ângulo de mira, então não mudamos o ponto em que pretendemos e não aumentamos o spread.

Com as filmagens foi mais difícil, um dos principais problemas do bot inicial era que ele não checou se iria se tocar com uma explosão. Por alguma razão, gostei do lançador de foguetes na maioria dos três tipos de armas e, portanto, era a primeira prioridade. Era necessário ensinar o bot a não se minar.

Foi gravada a função HitChance, que dividia o setor de disparo da unidade em N raios e verificou cada raio em busca de uma colisão com um alvo. Além disso, quando atingido, o AOE da explosão foi verificado, se for um lançador de foguetes. Chance de acerto = número de acertos por raio ou explosão / número de raios.

Isso nos permitiu determinar a chance estática de atingir a nós mesmos e ao inimigo, mas não levou em conta que o próprio inimigo poderia se esquivar ativamente. Houve outros problemas, por exemplo, a função não levou em consideração os disparos aleatórios nas minas.

Isso foi o suficiente para lutar contra inimigos não tão astutos, mas contra tops que esquivam bem das balas, a função não deu nenhum resultado adequado. Era necessária uma nova abordagem.

A função HitPredict também divide o cone de disparo em N raios, mas em vez de relançar, usamos uma simulação em que uma bala é disparada em uma direção por vez e é verificado se o inimigo pode se esquivar.

Para verificar os desvios, também é usada a função Dodge, que o bot usou por si só, mas com muito tempo de simulação de corte e o número de microtics. Esse método de avaliação acabou sendo bastante preciso, mas pessimista demais. Se você o usar apenas, o bot disparará muito raramente.

Na primeira versão, a função retornou apenas a chance de acertar, de 0-1, depois foi adicionado o cálculo do valor médio de HP do alvo, bem como a chance de matar por acerto.

No final, ambas as funções trabalharam juntas. A função HitPredict foi usada até quatro vezes, uma para cada unidade. O resultado do cálculo de cada função foi convertido em velocidade, o que mostrou como é lucrativo / perigoso fotografar no momento. Valores somados. Se o valor total fosse menor que zero, o disparo foi bloqueado. Para o lançador de foguetes, era necessário que a velocidade fosse maior que zero.

Tornou-se possível atirar com mais confiança nos casos em que um aliado bloqueia o disparo ou entra no AOE de um lançador de foguetes, você pode atirar nas costas dele sabendo que o aliado terá tempo para se esquivar ou é simplesmente vantajoso atirar. Por exemplo, perderemos uma unidade, mas tiraremos duas de uma vez.

Para o lançador de foguetes, a abordagem também foi eficaz, um tiro no momento certo é muito mais eficaz do que dois tiros, quando a chance de acertar é zero. Nesta forma, o tiroteio foi na final, o que permitiu o 16º lugar.

Agora, as fichas que foram adicionadas após a final.

Objetivo preciso: se o ângulo entre a visão atual e a desejada não for muito grande, objetivamos a visão com uma taxa de dados para não aumentar a dispersão.

Ângulo de informação para a pistola: por incrível que pareça, o chip é muito simples, mas não veio à mente antes. A proibição de disparar se o fator de dispersão (dispersão / dispersão máxima) for maior que 0,6 forneceu a porcentagem de vitórias no modo 1x1 em 3: 1 contra a versão que disparou no CD de armas. A redução do fator para 0,3 forneceu a mesma porcentagem de vitórias contra a versão com o parâmetro 0,6. Assim, uma das otimizações mais simples acabou sendo uma das mais eficazes.

Visualização da operação da função HitPredict, trajetórias garantidas.

Navegação

Até o final da navegação, não havia nenhuma palavra. Um algoritmo ligeiramente aprimorado do bot inicial foi usado, e isso geralmente era suficiente.

Portanto, quando as cartas complexas acabavam, o bot passava por um momento muito difícil. Um algoritmo de pesquisa BFS urgente foi escrito com urgência, que procurava um caminho sem levar em conta sua acessibilidade física, simplesmente por blocos. Para que o bot passasse pelo caminho encontrado, várias muletas foram usadas. Tudo isso funcionou de maneira torta, e às vezes não funcionou, mas ainda assim o robô poderia de alguma forma chegar a armas e kits de primeiros socorros, e não pular no local.

Após as finais, a navegação foi significativamente melhorada e, de acordo com minhas observações, ela se comportou ainda mais eficientemente do que muitos participantes com melhores algoritmos de busca de caminho.

Princípio do trabalho: o bot pesquisa a célula mais distante no caminho dentro do quadrado 5x5, visível do centro do bot, e segue até esse ponto.

No entanto, até o fim, ele permaneceu um código incrivelmente valioso que funcionou apenas nos mapas finais e caiu sobre outros mais complexos.

Trajeto marcado verde encontrado diykstroy. O bot segue o ponto marcado com um quadrado branco.

Função de movimentação e estimativa

Antes da final, não havia nenhuma função de avaliação, em vez disso, uma cadeia de ifs era usada, que em ordem de prioridade definia o bot no alvo de acordo com as condições especificadas. Por exemplo, o primeiro foi a busca por armas, se o bot não tiver uma, e a busca por um kit de primeiros socorros, se estivermos feridos, etc.
Isso funcionou em mapas simples, embora estivesse torto, porque as prioridades mudaram muito e não levaram em consideração vários fatores adicionais.

Portanto, uma função de avaliação foi escrita.

parâmetros principais

Saúde unitária, o maior bônus.
. — , — .
— , . (1 — / . ), , . , , .
. , , .
, , , .
.
, .
.
Um grande bônus se pudermos tocar o inimigo com explosões.

Os dois últimos parâmetros não estavam na final.

Todos esses bônus são calculados para cada tick, resumidos e o valor total é medido. Além disso, existem parâmetros estimados que são calculados uma vez para cada direção.

Bônus por avançar em direção ao inimigo mais próximo.
Bônus por avançar para o kit de primeiros socorros mais próximo. Quanto menos saúde tivermos, mais forte será o bônus.
Bônus por mudar para a arma mais próxima, se não tivermos uma arma, ou por mudar para uma arma com maior prioridade que o bot.
Bônus por mudar para lootbox min se o bot tiver menos de dois deles.
Bônus por mudar para o kit de primeiros socorros mais próximo do inimigo, se estivermos mais próximos do kit de primeiros socorros do que o inimigo.
O bônus mais interessante. Foi adicionado após a final. Permite impedir que o bot inimigo seja tratado. Segundo as observações, acabou sendo bastante eficaz.

Notas

A profundidade da simulação é de 30 ticks.
O comportamento dos robôs inimigos não é simulado. O jogo é muito dinâmico e prever adequadamente o movimento do inimigo é muito difícil e não é particularmente necessário. Poderia ser útil evitar suicídios insanos, mas nunca foi feito.
Para evitar problemas com a fuga de marcadores, se eles estiverem em campo, simulamos com uma qualidade de 100 microtics por tick (como no jogo), caso contrário, reduzimos para 5.
Você pode perceber que nenhum coeficiente de atenuação é aplicado. Talvez isso tenha sido um erro.

A opção de movimentação antiga está no MoveHelperOld, a nova opção no MoveHelper.

Meu bot (à direita) protege o kit de primeiros socorros

Minas

Sobre as minas precisam ser informadas separadamente. Se inicialmente não era um elemento de jogabilidade muito importante, era necessário extrair pontos-chave. Após o teste beta, a capacidade de explodir minas foi subitamente aumentada se elas fossem atingidas por uma bala ou explosão. Além disso, foi possível definir a mina e miná-la no mesmo carrapato.

Ou seja, se você gastar apenas dois ticks, poderá levar qualquer unidade inimiga com você. O inimigo recebeu 1000 pontos por nossa morte, mas recebemos mais de 1000 pontos de vida dele no momento da demolição por sua morte. Se você repetir isso duas vezes, poderá obter uma vitória com uma probabilidade muito alta.

A exploração acabou sendo tão forte que um participante, que ocupava o 15º lugar na classificação geral, caiu inesperadamente para o 4º na final, simplesmente devido a um kamikaze competente.

(A diferença é que, no ranking geral, existem cartas simples e complexas. Nas cartas simples, o suicídio funciona pior.)

No final, a estratégia usou minas, mas não usou a autodestruição intencional. Após a final, quando houve uma disputa por prêmios adicionais, foi adicionado o módulo TryPlantMine2, que implementa o demoman. No início, devido a erros no código, o módulo não era particularmente eficiente, mas na versão mais recente era possível consertar tudo, e a estratégia imediatamente começou a subir acentuadamente na classificação. Chegou ao ponto que ela chegou ao top 3, apesar de ter escorregado um pouco.

Princípio do trabalho: se estivermos em uma posição que permita que você coloque uma mina e possa disparar o mais tardar cinco carrapatos, simule três opções: apenas abater, colocar uma mina e atirar, duas minas e atirar. Para inimigos e aliados, simulamos o movimento usando a mesma função Dodge, verificando se eles podem pular para fora da zona de explosão antes que estejamos prontos para minar (não temos certeza do quanto era necessário). Para cada opção, verificamos como é benéfico para nós em pontos; se estivermos de preto, seremos prejudicados (dessa forma, podemos ser prejudicados mesmo sabendo que duas de nossas unidades e um inimigo morrerão, mas ainda venceremos). O efeito de se auto- prejudicar

na classificação

achados

Soluções simples geralmente podem ser mais eficazes do que as mais complexas, mas isso tem seu próprio limite. Com essa abordagem, você pode alcançar um nível bastante alto, mas depois cair na armadilha quando o potencial para melhorar a estratégia já estiver esgotado e sem mudanças radicais para aumentar a força da estratégia é impossível. Para o futuro, você deve pensar em algum tipo de opção intermediária.

Conclusão

Em geral, eu gostei deste campeonato, apesar de ser inclinado a isso, porque esta é a primeira vez que consegui tomar um lugar. No entanto, sem considerar meus sentimentos subjetivos, este ano muito foi realizado em um nível superior.

Pela primeira vez, foi possível se comunicar no Telegram com uma pessoa responsável pela parte técnica e que respondeu prontamente a todas as perguntas, pelas quais agradecemos muito.
Pela primeira vez, um visualizador interno normal estava presente no localnerner. Anteriormente, para gerar gráficos de depuração, era necessário escrever seus próprios.
Finalmente, em vez do utilitário Repeater, inconveniente e com erros, o botão "Repeat game" é adicionado na LAN.

Dos desvantagens, é claro, é uma enorme façanha com as minas.

E espero que minhas conquistas neste campeonato não sejam acidentais e que da próxima vez eu consiga pelo menos salvar um lugar, e ainda melhor para assumir uma posição mais alta (sonhar não é prejudicial).

O código bot pode ser visualizado no github: github.com/silentnox/CodeSide

Meu bot para a Copa AI AI 2019