Olá pessoal!
Sou estudante do terceiro ano e, no início dos meus estudos na universidade, aprendi sobre a
Taça Ai russa e, mais tarde, a
Mini Taça Ai , competições em inteligência artificial, e comecei a participar ativamente delas, mostrando bons resultados. Desta vez, o RAIC entrou na sessão, então nada poderia me impedir :) E hoje quero lhe contar como consegui ficar em segundo lugar.
As regras da competição podem ser encontradas no site da competição e neste
artigo . Link para o meu perfil:
russianaicup.ru/profile/TonyK .
Por um lado, a tarefa deste ano foi semelhante à dos anos anteriores, e parecia que a solução ideológica seria muito semelhante às anteriores (Agar IO e Mad Cars); depois de uma semana, ficarei entediado e cansado de participar.
Por outro lado, entendi que havia aprendido muito em competições anteriores com física e agora posso aplicar essa experiência, não pisar no ancinho antigo e, no final, mostrar um resultado melhor.
Quanto à visualização, decidi que teria projeções suficientes em diferentes eixos ou exibiria em um determinado ângulo. Mas eu estava muito enganado, e se não fosse o visualizador mágico incorporado no Local Runner, que os organizadores acrescentaram mais tarde, eu teria que emprestar visualizadores 3D dos tipos de participantes que passaram a fase de testes beta escrevendo-os e colocando-os em domínio público.
Desta vez, o pseudo-código do simulador estava disponível, o que igualava as possibilidades daqueles que sabiam reverter a física e escrever um bot legal, e aqueles que não podiam reverter a física, mas que também podiam escrever um bot forte. Acho que foi uma boa decisão dos organizadores.
A primeira coisa que fiz foi reescrever o código do simulador da documentação em C ++ e depois medir o tempo do simulador no meu computador antigo e no servidor. No segundo caso, resultou duas vezes mais rápido, embora isso fosse esperado. Imaginei quantas vezes e com que profundidade eu poderia simular. Imediatamente ficou claro que seria necessário esquecer a simulação honesta de 100 microtics (no servidor, um tique de física foi dividido em 100 "microtics"), e seria necessário resolver problemas com precisão de maneira indireta.
Como o shell foi organizado de tal maneira que a solicitação de ação para cada robô é chamada separadamente em cada tick, implementei uma lógica simples: no momento em que o primeiro robô é solicitado, o programa encontra ações para todos os robôs, lembra e fornece a ação do primeiro, e quando a ação é solicitada aos outros robôs, ela devolve o que foi lembrado.
Eu estava impaciente para enviar o bot para a batalha em breve. Decidi gerar trajetórias aleatórias e escolher a melhor. Ao mesmo tempo, ele queria que o conjunto gerado tornasse possível a execução de algumas ações complexas, por exemplo, contornar a bola pelo lado direito e depois bater.
Uma trajetória é um plano de ação. Inicialmente, a trajetória foi a seguinte:
- defina a ação em um ângulo aleatório;
- em uma marca aleatória da trajetória, altere o ângulo para outra marca aleatória;
- pule uma vez para uma marca aleatória da trajetória.
Esse espaço de trajetórias era um bom ajuste para pesquisa aleatória com o número de simulações que eu (e provavelmente todo mundo naquele momento) podia pagar com o simulador bruto da documentação. Boas trajetórias foram muitas vezes adivinhadas e, como a melhor trajetória do carrapato anterior foi preservada, a pesquisa acabou se estendendo no tempo.
Todos os objetos foram colocados no simulador: meus robôs, robôs do oponente e a bola. A avaliação foi a mais simples: a soma das distâncias da bola ao gol do inimigo em todos os pontos da trajetória e os grandes valores do gol para alguém. Profundidade da simulação 200 ticks. Os inimigos são previstos na sua última velocidade.
Eu imediatamente adicionei uma ação separada para o segundo robô, bem como o cancelamento forçado do salto, se durante o vôo não houver contato com a bola, para não pular em vão. Ao mesmo tempo, meus robôs passaram mais da metade do tempo e conheciam a melhor trajetória um do outro. Agora, os primeiros
gols começaram para adversários fortes, que já tinham goleiro e uma lógica mais complicada.
Aconteceu ainda que eu não considerava a distância dos portões inimigos, mas do ponto ao lado do centro do campo (misturado
x e
z ), mas isso não afetou a estratégia de forma alguma. É bom que, após a correção, não tenha piorado. Isso geralmente acontece quando você escreve um bot.
Depois, acrescentou o goleiro, alterando o placar: ele impôs um pênalti para a bola na minha metade do campo e para o gol para mim, e também estimou a distância do goleiro ao meu gol. Agora o goleiro estava no gol e nocauteou a bola. Uma otimização importante foi que, se a bola não estiver na minha metade do campo, 90% do tempo é dado ao atacante e 10% ao goleiro, caso contrário, 50%.
A avaliação das trajetórias dos robôs em cada ponto foi multiplicada por 0,9 ^ de profundidade. Derivei esse coeficiente empiricamente, como toda a pontuação. Os valores dos coeficientes não mudaram por muito tempo no princípio de "obras, ok".
Ele começou
a ganhar os topos e subir rapidamente no ranking. A fase beta terminou.
Por um longo tempo, não tive ideias sobre a estratégia, as versões foram notáveis por pequenas edições, correções de bugs (verificou-se que considerei a força média de rebote como
(MAX_HIT_E - MIN_HIT_E) / 2 ) e também
(MAX_HIT_E - MIN_HIT_E) / 2 o simulador. Um papel importante foi desempenhado pelo número de trajetórias que eu consegui resolver por tick, então me concentrei na otimização. Seios removidos e raízes quadradas. Adicionada uma velocidade zero improvável na trajetória antes ou depois de alterar o ângulo. Pontuação ligeiramente alterada.
A 16ª versão
ficou por muito tempo no topo da tabela, mas uma semana após o final dos testes beta, como esperado, muitos começaram
a vencer .
Tentei refinar a trajetória com a soma das distâncias mais próximas do inimigo à bola e tive um comportamento muito interessante. Meus robôs, quando não podiam acertar com lucro, frequentemente começavam a bloquear os inimigos, quebrando suas trajetórias e impedindo que corressem para a bola, às vezes acontecia com muito sucesso e insidiosamente.
Em seguida, consertei a precisão ao pular. Se alguém pular no tick atual, primeiro fazemos 1 micrótico duas vezes e depois os restantes 98 micróticos. Também tentei compensar a perda de precisão com um coeficiente heurístico quando a velocidade máxima é alcançada em alguns dos micróticos. As melhorias ajudaram
bastante e houve resultados mais precisos e pré-calculados.
Também nesse momento, comecei a exibir no site entre as informações de depuração o número de iterações que consegui concluir. Havia 250 deles em 200 ticks, no total, eu tive 50.000 ticks de simulações durante o tempo alocado para minha estratégia por tick.
Então eu liguei as trajetórias de mutação. Isso melhorou bastante a estratégia. Em aproximadamente metade de todas as iterações, não foi a nova trajetória usada, mas a melhor com valores ligeiramente alterados, que possibilitou convergir em algum lugar, por exemplo, para um máximo local. Acabou sendo uma estratégia
forte na época, que eu decidi deixar até o primeiro turno, embora ainda faltassem duas semanas antes. Mas depois de alguns dias, ela deixou de dominar o topo.
Passei algum tempo me afastando da aleatoriedade completa, por exemplo, tentei, com uma pesquisa ternária, encontrar o ângulo em que o robô precisa acelerar para acertar a bola. Mas isso nem sempre funcionou, e eu não descobri como desenvolver essa idéia.
Meus robôs sabiam pular apenas uma vez por trajetória, mas quando estavam no chão e queriam pular e depois acertar a bola no ar, não sabiam que, quando você toca na bola, pode pular uma segunda vez, atingindo a bola com força e não apenas pressionando.
Isso foi corrigido, e agora o simulador, quando percebeu que alguém poderia acertar a bola no tique atual, recuou um tique e forçou o robô a pular com força máxima. Agora, parado no chão, o robô sabia que iria empurrar o chão e não apenas empurrar, mas acertaria a bola com um segundo salto.
Eu entendi que quando nitro e outro robô fossem adicionados, tudo seria dobrado por causa da falta de iterações. Também em lugares diferentes, tive grandes problemas de precisão, que não sabia como resolver. Não vi nenhuma
solução analítica ou nenhuma
maneira inteligente de gerenciamento .
Eu precisava de uma estratégia completamente nova ou de um simulador mágico que combine precisão e velocidade, e na fase final me fornecerá trajetórias suficientes para percorrer. Não criei uma nova estratégia (surpreendentemente) e comecei a trabalhar em um simulador.
"Simulador inteligente"
A primeira coisa que eu queria lidar com precisão.
Simulei 100 Mikrotiks de cada vez, embora uma colisão - ou algum outro evento - tenha ocorrido em um desses cem Mikrotiks. Se você ignorar isso, os objetos colidem mais tarde do que na realidade (sempre nos 100º micróticos) e, portanto, saltam de maneira diferente. No final da trajetória, esse pequeno erro pode se transformar em uma grande imprecisão. Por exemplo, pensamos que a bola acerta o gol do inimigo, mas, na realidade, ela bate
na nossa do poste.
É fácil ver que, em uma situação em que ocorre uma colisão nos
i ésticos microtics, em vez de contar todos os 100 microtics, basta contar os primeiros
i - 1 microtics de cada vez (na verdade, a etapa da física é considerada por um certo tempo
dt , e agora esse tempo será
t * (i - 1) , onde
t é o tempo correspondente a um Mikrotik). Agora você precisa simular 1 micrótico (
dt = t ) e os restantes
100 - i micróticos. Obtemos exatamente o mesmo resultado em apenas três simulações em vez de cem. O único problema é que não sabemos em que microtics a colisão ocorrerá.
Estando em algum tick fixo da simulação, podemos fazer qualquer número de micróticos de 1 a 100 em uma simulação e ver se há uma colisão ou não. Nesse caso, a imagem será assim: a princípio não há toque, mas a partir de um certo número de microtics e até cem há um toque. Exceto em casos muito raros, quando não há contato a princípio, há um toque em algum segmento dos micróticos e, novamente, não há toque novamente.
Portanto, é possível encontrar o Mikrotik no qual a colisão ocorreu usando uma pesquisa binária de 10 simulações no pior caso. E, como descrito anteriormente, para três simulações, você pode obter o estado do mundo através de 100 microtics com precisão perfeita.
De fato, havia vários outros tipos de eventos além de uma colisão, e vários poderiam ter ocorrido em um tick, portanto, apenas o primeiro evento estava localizado em uma dicotomia, depois o segundo evento estava localizado no sufixo restante da dicotomia do tick, e assim por diante. Assim, um carrapato foi considerado como segmento de vários micróticos por simulação, até que todos os eventos fossem contados.
Portanto, os problemas foram resolvidos com precisão. Mas, devido ao fato de haver 5 objetos na simulação, e de acordo com as regras finais, deveria haver 7, e todos eles frequentemente travavam, em média as dicotomias eram chamadas com muita frequência e isso funcionava proibitivamente por muito tempo. Portanto, passei para a segunda etapa do desenvolvimento do simulador - otimização.
Obviamente, quando a trajetória de um dos robôs termina, todos os outros objetos nos quais esse robô não colide se movem sempre da mesma forma. É claro que não é necessário recalcular seus estados com um simulador - por exemplo, calcular colisões pesadas com a arena.
Antes de ordenar as trajetórias de um robô em particular, basta simular e lembrar honestamente para os objetos restantes seus estados em todos os instantes, e simplesmente tirar esses estados da memória. Chamamos esses objetos de estáticos, e um robô para o qual a trajetória está classificada é dinâmico.
Se subitamente algum objeto dinâmico influencia (tem uma colisão) com um estático, adicionamos esse objeto estático aos dinâmicos até o final da simulação da trajetória atual. De fato, no estágio de armazenamento de estados para objetos estáticos, é criado um gráfico de influências um sobre o outro e, em seguida, é usado para transferir corretamente objetos estáticos para objetos dinâmicos. Por exemplo, um robô inimigo bate na bola e geramos um caminho em que derrubamos o robô inimigo antes que ele atinja a bola. Agora, a bola voa mais longe e, durante a simulação, quando o robô inimigo é adicionado a objetos dinâmicos, é necessário observar que a bola deve ser adicionada aos objetos dinâmicos um pouco mais tarde, no tique-taque em que o robô inimigo acertaria a bola se não interferíssemos nela . No caso geral, isso é feito recursivamente, de acordo com o gráfico de influência.
Agora, o simulador não calcula todos os objetos, mas apenas os dinâmicos, e isso, em média, é um objeto e meio em vez de sete, e dicotomias longas são usadas com muito menos frequência. Acabou muito rápido, e não precisa mais sofrer nas finais com robôs adicionais - legal!
A 26ª versão com um novo simulador e uma profundidade de simulação reduzida de 200 para 100 foi enviada para jogar no primeiro turno. Mas continha alguns bugs e não havia vantagem óbvia.
O último problema com precisão permaneceu: movimento ao longo do arredondamento da arena. Nesse caso, para obter precisão absoluta, é necessário contar honestamente 100 microtics. A solução foi surpreendentemente simples: sempre salte de todas as superfícies, exceto o piso. Sem arredondamento - não há problema.
Além disso, por algum tempo eu otimizei, fiquei desapontado e, observando jogos com estratégias mais inteligentes, peguei novas constantes de pontuação. Tornou-se muito melhor, a estratégia subiu alto no ranking e a 37ª versão alcançou o melhor resultado de todas as minhas estratégias na sandbox o tempo todo antes da final.
A partir daí, aluguei uma máquina de 32 núcleos em um serviço de nuvem para executar minhas estratégias umas contra as outras e comecei a experimentar muito com tudo em sequência. Mudou as constantes. Tentei usar minha própria estratégia para prever as ações do inimigo, mas isso não ajudou em jogos contra a minha estratégia.
Ao resolver a equação, ele aprendeu a calcular a última ação do inimigo e começou a prever seu comportamento posterior. Adicionado suporte para nitro: um ponto aleatório na superfície da esfera é selecionado para a ação. Fez muitas edições menores. Mas não houve muito progresso. No início do segundo turno, 4-5 tops estavam me conquistando
Ainda assim, não me desesperei. Tive duas melhorias que planejava implementar antes da final e esperava que elas melhorassem bastante a estratégia. Decidi não enfrentá-los até que o sandbox iniciasse de acordo com as regras finais. Em vez disso, dediquei um tempo para depurar e otimizar o que já havia sido feito para minimizar as chances de erros do mal na última semana, quando cada minuto conta.
A última semana antes do início da final.
A primeira melhoria que fiz foi essa. Nas partidas, no caso geral, a maioria dos meus problemas e qualquer outra estratégia surgem quando o oponente toma posse da bola. Ele de alguma forma bate nele, passa, em geral - controles. É impossível prever a trajetória da bola e planejar mais algumas ações lucrativas nesse caso. Resta fazer o que for até que o oponente cometa um erro e transfira o controle da bola para meus robôs. E depois disso, você deve tentar não executar ações que possam levar ao fato de que a bola estará novamente com o inimigo.
Em outras palavras, no momento de planejar a trajetória, quero levar em consideração as possíveis posições dos adversários e tentar não bater na bola lá. Decidi usar um campo potencial quadridimensional (as três primeiras dimensões são as coordenadas, o lado dos cubos é igual ao diâmetro do robô e a quarta dimensão é o tempo), o qual preencherei, gerando trajetórias inimigas aleatórias.
Mais tarde, ao avaliar a trajetória do meu robô, calculei a soma em todos os cubos que cruzavam a bola nos pontos correspondentes no tempo e multiplicado por um coeficiente que excede todos os outros valores na pontuação. Ou seja, o campo potencial foi levado em consideração com a maior prioridade após a meta. Também permitiu remover inimigos da simulação após os primeiros 30 tiques (o inimigo poderia fazer qualquer coisa durante esse tempo enquanto estava no chão, e previsões imprecisas e distantes apenas interferiam) se não estivessem no ar (parecia que ninguém estaria no ar). ar para mudar a trajetória de maneira complexa usando nitro).
Ao gerar trajetórias aleatórias para o inimigo, foi possível descobrir o tempo mínimo necessário para ele bater na bola. Este valor foi útil para resolver o problema com os primeiros pulos do meu goleiro fora do portão. Muitos gols foram marcados para mim porque meu goleiro saltou cedo e se tornou incontrolável no ar. Depois disso, o inimigo previu com facilidade como meu goleiro voaria e, se pudesse, mudou a trajetória da bola antes que meu goleiro o alcançasse. Agora cancelei o pulo do goleiro se o inimigo conseguir acertar a bola mais cedo do que meu goleiro planeja fazer.
Verificou-se que, sem danos significativos à estratégia, é possível calcular a trajetória não todos os ticks, mas através de um. Ao reduzir pela metade o tempo de execução, eu dobrei o número médio de iterações. Alguma mágica acontece aqui. Parece que, se contarmos as trajetórias de cada segundo tick e dobrar o número de iterações, o número médio de iterações não será alterado. Mas, de fato, o simulador contará dois ticks (200 microtiks) por simulação, em vez de um. E as trajetórias já terão 50, e não 100. É por isso que o número médio de iterações dobrará.
Permaneceu alguns dias antes da final. Embora minha estratégia tenha começado a sofrer menos gols devido ao bom controle de bola, não comecei a marcar melhor. Portanto, tive que motivá-la com um coeficiente quando em breve pelo objetivo de um oponente. Quanto mais rápido um gol é marcado, maior a proporção. E esse coeficiente está crescendo muito para exceder o restante da pontuação e não ter medo do campo em potencial, quando, por exemplo, restam 10 tiques antes da pontuação.
Adicionado um cálculo de onde o inimigo está enviando nitro. Isso foi feito usando força bruta com um certo passo. Além disso, o goleiro começou a reabastecer as reservas de nitro, quando nada ameaça meu objetivo.
A segunda grande melhoria foi usar o minimax. Se o uso de diferentes forças de impacto para o inimigo durante a construção de trajetórias estáticas afeta o vôo da bola, durante a busca foram consideradas as duas opções, com força de impacto máxima e mínima do inimigo, e o mínimo das estimativas.
Na final, eu tinha 7 opções de trajetórias quando o robô estava no chão:
- 2 cantos sem salto;
- 2 cantos com um salto;
- 2 ângulos com salto e velocidade nitro-codirecional;
- 2 ângulos com um salto e nitro compensa a gravidade;
- 1 esquina com salto;
- 1 ângulo com salto e velocidade nitro-codirecional;
- 1 canto com um salto e nitro compensa a gravidade (não usado devido a um bug, notado ao escrever um artigo).
e duas opções quando o robô está no ar:
- nitro para um ponto aleatório na superfície da esfera e força de impacto aleatória;
- força de impacto aleatória.
Houve competição algumas horas antes da final, mas minha estratégia foi claramente melhor. Parecia que tudo já havia sido feito, eu não dormia há mais de um dia e nada dependia de mim. Permaneceu para assistir. Duas horas antes da final, Andrei enviou seu graal recém-assado e conquistou o primeiro lugar. A história de sua participação pode ser encontrada aqui:
habr.com/en/post/440398 .
No intervalo entre as etapas da final, adicionei um campo potencial afastando a bola do meu gol, independentemente de tudo o mais, e isso, como me pareceu, me igualou a Andrei. Mas já era tarde, porque perdi 7 pontos no primeiro tempo e até 3/3 de vitórias no segundo tempo não foram suficientes.
RAIC é uma competição difícil e prêmios são dados aos participantes muito, muito difíceis. Quando um participante está no topo da mesa, para ele isso não é apenas entretenimento - é uma luta. Há muitas pequenas coisas a considerar ao escrever uma estratégia forte. Cada decisão tomada pode afetar significativamente o resultado.
O código fonte da estratégia estará disponível
aqui .