👼🏼 🎅🏻 🌨️ Continuação da participação (e vitória) na Russian AI Cup 2019 🚩 👩🏼‍🌾 🍫

Olá pessoal, meu nome é Andrey Tokarev e, novamente , gostaria de compartilhar minha experiência de participação e vitória na Copa da AI da Rússia.

Se alguém não souber, a Russian AI Cup (doravante RAIK) é um campeonato de programação de inteligência artificial em que nós (ou melhor, nosso programa) devemos controlar um ou mais personagens (unidades) que competem entre si. Este ano, o jogo era um jogo de plataformas bidimensional, que lembra jogos de computador do início dos anos 90, e as unidades eram homens armados que deveriam matar os mesmos homens do inimigo. Você pode ler mais sobre isso no anúncio.

Desta vez, não houve reunião quando a agenda chegou para o início do RAIK, então vamos direto ao ponto.

Primeira vista

Então, eu corri as regras, tentei o jogo. A primeira impressão foi - o que fazer aqui? Como as unidades não tinham inércia, e os níveis iniciais estavam sem ciclos fechados, o inimigo sempre poderia se ater a nós, se quisesse, e se defender contra isso era impossível. E nessa situação, você entende, as possibilidades são muito limitadas. Você não esquivará de balas. Mas meus primeiros medos não se concretizaram, embora o fator do acaso fosse alto, as regras acabaram sendo bastante jogáveis.

Eu não comecei a desenvolver imediatamente, um par de dias ~~caiu um tolo~~decidiu refletir. Eu não criei nada de especial. É claro que você precisa se esquivar de balas, correr atrás de kits de primeiros socorros e, se possível, não deixar o inimigo levar um kit de primeiros socorros e tudo mais. Ainda havia um plano vago para encontrar posições estrategicamente vantajosas, e gira em torno delas, mas não estava totalmente claro como distinguir essas posições.

Começar

Aqui vamos nos. Por hábito, converto os objetos de dados no pacote de idiomas em minhas próprias estruturas de dados. Sim, leva algum tempo, mas não muito, mas tenho mais flexibilidade, trabalho em um ambiente mais familiar e, enquanto faço a conversão, é melhor começar a entender como o mundo do jogo funciona. Obviamente, não de uma só vez, mas conforme necessário. Por exemplo, não recriei as minas até que a situação política no campeonato me forçou a recorrer a medidas extremas. Copiei aproximadamente a lógica de Smartgayev, adicionando apenas uma verificação da presença de um muro entre mim e o inimigo. Eu olhei, eles parecem estar indo bem, então podemos assumir que temos um mundo de jogo.

Simulação

Agora passamos ao passatempo mais favorito de todos os participantes do RAIK: estamos escrevendo uma simulação! Depois de ler o bate-papo do campeonato, ficou claro que escrever uma simulação precisa é ruim. Então eu imediatamente pontuei por precisão. Aconteceu que, mesmo com uma simples recuperação do teto, havia uma discrepância dentro da teca. Era possível, é claro, mexer nela por vários dias e aumentar significativamente a precisão, mas, primeiro, não se sabe qual seria o lucro disso. Em segundo lugar, eu estava impaciente demais e, como sempre, queria ver o resultado o mais rápido possível. Então, decidi começar a escrever a própria estratégia e pensei em corrigir minha curva de simulação, se necessário. Em retrospectiva, devo dizer que talvez eu estivesse errado.
Vale a pena trazer imediatamente a simulação ao normal, e por isso foi necessário fazer correções até o final do campeonato, e ainda assim ela permaneceu torta.

Base estratégica

Em seguida, procedemos de acordo com o cenário padrão: geramos a sequência de ações de ~~robôs~~ unitários, simulamos uma mudança no mundo do jogo e submetemos tudo à entrada da função de avaliação (OF). Se no futebol (torneio do ano passado) era ineficaz correr atrás da bola com um número aleatório completo de jogadores (há muito pouca chance de acertar a bola, especialmente do ângulo certo), então não há esse problema. Basicamente, precisamos de uma simulação para duas coisas: esquivar-se de balas e encontrar o caminho. Alguns cenários de ação completamente aleatórios são suficientes para evitar balas. Várias dezenas de cenários também trabalharão na busca de uma maneira mais ou menos, pelo menos, em mapas não tão difíceis.

A propósito, a busca pelo caminho - é claro que nem sempre é possível contar até o fim, portanto, você precisa determinar a distância. Usando a mesma simulação, é possível calcular com mais ou menos precisão as distâncias no tempo. Mas aqui eu também simplifiquei, apenas contei as distâncias ao longo de uma grade retangular. Essa simplificação, é claro, teve algumas consequências em mapas complexos. Às vezes, minhas unidades ainda estavam confusas na busca de armas, enquanto o inimigo já estava começando a atirar. É verdade que esses incidentes foram bastante raros.

A escolha do alvo foi bastante simples: enquanto não há armas, vamos para armas, se existem armas, vamos para o inimigo e se há pouca "saúde", vamos para o armário de remédios. No caso de kits de primeiros socorros e armas, foram excluídos os objetos que estavam mais próximos do inimigo como alvo. Por alguma razão, a prioridade em armas para mim foi a primeira na máquina.

A primeira função de avaliação consistiu em dois componentes: é a saúde (não a minha, mas uma unidade) com um grande coeficiente e a distância do alvo com um pequeno coeficiente.
Essa. a rota foi escolhida em que não cai sob as balas, mas ao mesmo tempo se aproxima do alvo o mais rápido possível. É importante lembrar a melhor rota encontrada para o próximo tick, caso contrário, poderá surgir uma situação quando encontrarmos uma boa opção, mas não a apresentaremos no próximo tick.

Vamos para frente, e as primeiras melhorias

Olhando para as batalhas, ficou claro que, se o inimigo tinha uma esquiva normal, era quase impossível entrar nele a longa distância. Isso é um desperdício de balas. Então, adicionei uma condição simples para o disparo: atire apenas se o inimigo estiver a menos de 7 metros. Além disso, se a distância for muito grande, vale a pena recarregar, mesmo que apenas um marcador esteja faltando no clipe. Essas duas condições simples adicionaram bastante.

Esta foi a primeira versão que enviei. No mesmo dia, percebi que uma arma é mais lucrativa que uma metralhadora. Além disso, ele acrescentou ao OB uma outra distância do inimigo, caso o tiro não seja breve. Assim, ao recarregar, ele tentou manter distância.

O começo foi bem sucedido. Não lembro até que ponto a estratégia conseguiu subir no ranking antes da redefinição (em torno dos três primeiros cinco) e, após a redefinição, subiu com confiança.

A principal melhoria na próxima versão ocorreu devido a uma tentativa de controlar os kits de primeiros socorros. Aqui, novamente, tudo era simples: a distância entre os kits de primeiros socorros e eu e o inimigo era calculada, e se eles eram aproximadamente iguais, acreditava-se que o kit de primeiros socorros era empatado e, portanto, aquele com quem ele estava mais próximo. Isso foi levado em consideração pela função de avaliação. Essa. em teoria, a unidade tentou se posicionar de modo a obscurecer o maior número possível de kits de primeiros socorros. Em teoria, é claro, mas não na prática.

Depois disso, não enviei atualizações por um longo tempo. Para minha surpresa, a estratégia chegou primeiro ao 1º lugar, e depois saiu com mais de 100 pontos. Provavelmente todo mundo pensou que eu estava cortando algo legal, e fiquei chocado com a subida dessa estratégia miserável. Miserável, porque, bem, há um controle desajeitado dos kits de primeiros socorros, existem dois ifs para disparar, mas basicamente esse é um desvio e movimento simples, com base em uma curva de simulação.

Teste

Eu gostaria de falar sobre isso separadamente, porque o teste adequado é uma parte muito importante do desenvolvimento e muitos participantes parecem ignorar esse aspecto. O acidente é intuitivamente incompreendido pelas pessoas.

Suponha que façamos um teste e após 40 jogos vejamos uma pontuação de 27:13 a favor do novo. Foi tudo, encontramos o Graal, paramos o teste e aceitamos as mudanças. De fato, mesmo com forças iguais, há aproximadamente 2% de probabilidade de tal situação.

Outro exemplo, lançamos 100 jogos e aceitamos as alterações se a pontuação for 55:45 ou mais. Com uma probabilidade de 2,8%, uma versão pode jogar dessa maneira, o que na verdade deve perder com a mesma pontuação. Um par de por cento do erro pode não parecer muito grande, mas se 90% de nossas alterações não forem bem-sucedidas, isso significa que cada quarta alteração aceita não será bem-sucedida. Assim, mesmo 100 jogos ainda são um teste mais ou menos, mas menos - nada.

Obviamente, o lançamento de várias centenas de jogos pode levar um tempo indecente. Existem opções diferentes: você pode executar testes à noite, dirigir em segundo plano, alugar o horário do servidor ou acelerar a estratégia :) Minhas primeiras versões funcionaram em média, em algum lugar, por 5 segundos. para o jogo, tão sortudo com isso.

Se a estratégia for lenta, você poderá conduzir localmente versões truncadas - menos pesquisas, menos micro-ticks, por exemplo. Eu usei isso no futebol (RAIK anterior), nenhum problema foi percebido. Talvez a qualidade esteja perdida em algum lugar, mas, em qualquer caso, é mais lucrativa do que procurar alterações em 20 jogos.

Aprimoramentos

Desta vez, não vou avaliar as melhorias nos números. Em primeiro lugar, eram todos pequenos (menos de 20%) e, portanto, imprecisos. Em segundo lugar, ambíguo, ou seja, a nova versão poderia vencer com confiança a anterior e jogar pior contra os outros. E em terceiro lugar, simplesmente não me lembro deles.

, . , . , , .
. .. , , . , , -. , . , , . .
, , . , , , , , . , . , .
, ? , , . . , . .

-

Objetivamente, você precisa atirar na direção em que o tapete. a expectativa de dano é mais alta. É claro que analiticamente isso não pode ser calculado, e onde a matemática não ajuda, como sabemos, a simulação vem em socorro. Atiramos em todas as direções possíveis e tentamos desviar o inimigo de cada bala individualmente. Para cada pool, atribuímos o valor mínimo de dano que ele infligirá com precisão. No caso de uma bala convencional, é 0 ou seu dano, e no caso de um foguete, existem 3 opções.

Agora nós sabemos o tapete. esperando danos em cada direção separadamente, podemos calcular facilmente o tapete. aguarde cada direção do tiro e escolha o melhor. Seria bom usar essa função na enumeração para que a unidade esteja posicionada corretamente, mas era muito lento para chamá-la para cada cenário. Foi chamado uma vez por tick para cada unidade, e agora o tiroteio foi realizado não à distância, mas se o dano esperado exceder um determinado limite. O aumento foi significativo e, no caso da bazuca, parecia bem claro - agora a minha podia até mirar em algum lugar na parede para atingir o inimigo com uma onda de explosão.

Porém, devido ao fato de não poder inserir essa função na pesquisa, havia um problema de que as condições para o disparo na pesquisa e na realidade eram diferentes. Eu não sabia como resolver esse problema, tinha que viver com ele.

Depois disso, não houve mudanças muito significativas até o último dia em que introduzi o auto-jateamento. Ele acrescentou uma penalidade se não houvesse salto no momento em que o inimigo disparou, porque cair tornaria mais difícil se esquivar. Tentei prever o caminho do inimigo até o estojo de primeiros socorros, se ele tiver poucas vidas, e assim melhorar um pouco o controle sobre elas. Ele próprio começou a correr atrás de kits de primeiros socorros com 60% de sua saúde, em vez de 50%. Ele acrescentou a distância entre as suas no PF para que não interferissem entre si, e a bazuca não eliminaria imediatamente duas. No final, ele adicionou um mod agressivo, caso a situação não mude por muito tempo e eu perca pontos, caso contrário o meu às vezes fica preso.

resultados

Como eu disse, rapidamente chegou ao primeiro lugar no ranking. Com exceção de curtos períodos de tempo, fiquei lá até o fim. Nas rodadas, a situação foi um pouco pior: 4º lugar no primeiro, 3º no segundo. Isso indicou que joguei bem contra jogadores fortes, mas não suficientemente estável contra jogadores fracos. Isso é claramente demonstrado por um dos jogos da 2ª rodada, onde kostya200300, que estava na última posição, me venceu em 0!

Auto-detonação

Como a maioria dos participantes, eu não estava entusiasmado com a possibilidade de auto-explosão. Isso aumentou bastante o já considerável fator aleatório. Mas estava claro que não se poderia prescindir disso. É verdade que eu realmente não queria fazer isso, e adiei até o último dia. Essa técnica é bastante simples: se estamos no chão, o inimigo está no raio da explosão e temos o suficiente (no máximo duas) minas, depois colocamos as minas e atiramos no fundo. Coloquei uma condição adicional de que, após a explosão, obtenho uma clara vantagem, ou seja, ganhe imediatamente ou mate mais oponentes do que os seus. Eu pensei que, uma vez que aspiro a um lugar alto, mudar um por um não é rentável. Bem, é como no xadrez, se você jogar para ganhar, então trocar tudo seguidamente não é rentável. Foi assim que enviei meus guerreiros dotados de habilidades kamikaze para a batalha final.

O final

Como já escrevi, a classificação fala apenas do equilíbrio de poder com os concorrentes mais próximos, e eu não tinha estabilidade contra rivais mais fracos. A esse respeito, a eliminação dos participantes para as finais teve uma bagunça para mim. Por outro lado, a disseminação massiva da ideologia terrorista no último dia introduziu uma disseminação adicional na distribuição de forças. Em suma, apesar da liderança confiante no ranking, não havia confiança na final, havia apenas esperança. Após a primeira metade da final, ficou claro que a principal luta será entre mim e Ivan Tyamgin. Eu levei a um pequeno número de pontos, enquanto o resto estava muito atrás.

Durante o intervalo, eu ~~demorei~~pegando a auto-detonação - algo foi consertado (descobriu-se que as minas não deveriam ser colocadas no topo da escada), ele acrescentou algumas contramedidas contra a detonação. E reparou a simulação, porque até agora as minhas se apegavam à esquina.

O início da segunda parte da rodada final foi bem-sucedido para mim, a diferença começou a crescer lentamente e atingiu um máximo de cerca de 20 pontos. Até relaxei um pouco e, em vez de atualizar a página de resultados a cada 3 minutos, comecei a jogar xadrez no telefone. Quando olhei novamente, a diferença já era de cerca de 7 pontos e depois rapidamente chegou ao 1º. Eu me pergunto o que eles dão para o 2º lugar? 1 hora até o fim, novamente há uma lacuna. 30 minutos, a diferença é catastroficamente reduzida. 10 minutos - apenas 3 pontos! Um minuto ... a vitória parece! Vanya perdeu para mim apenas 3 pontos. Isso está dentro da dispersão aleatória. O resto está 50 pontos ou mais atrás.

Sobre bugs engraçados

Já após a final, notei que em alguns jogos minhas unidades se comportam de maneira estranha - elas não evitam balas quando, ao que parece, elas poderiam e até, como se as capturassem especialmente. Aconteceu que durante o intervalo da final eu cometi um erro - quando foi determinado se o inimigo poderia me explodir, era necessário calcular qual dos meus estava no raio da explosão. Aqui misturei as coordenadas da minha unidade e da de outra pessoa e assumi erroneamente que a explosão ocorreria onde estou e, assim, garanti que caía no raio da explosão. A verdadeira explosão já foi considerada do ponto certo, para que na simulação o próprio inimigo pudesse explodir para longe de mim. Normalmente, apenas adicionava uma grande constante à estimativa, mas realmente não afetava nada. No entanto, se o inimigo não tinha minas suficientes para me explodir, descobriu-se que era rentável para mim pegar uma balapara que o inimigo já tivesse minas suficientes, e eu recebi o acréscimo à avaliação. Talvez tenha sido por falta de sono ou uma lata de cerveja bêbada, mas, de fato, sempre acontecem erros.

Conclusão

O jogo, embora não tão espetacular quanto o futebol, não era menos interessante do ponto de vista da estratégia. A entrada do limiar foi relativamente baixa e isso afetou favoravelmente o número de participantes. Recebi muitas emoções durante o mês do campeonato, tanto de alegria quanto de emoções, e por isso sou grato aos organizadores. Agradeço também a todos os participantes, especialmente Vanya Tyamgina, por não me deixarem entediado nas finais.

Continuação da participação (e vitória) na Russian AI Cup 2019