Olá pessoal, meu nome é Olya. Duas semanas atrás, outro concurso terminou no CodinGame - um concurso para programar bots para o jogo. Eu entrei no top 300 da tabela de líderes mundiais, então quero dizer por que os concursos são legais e compartilhar meus segredos. Ivan spaceorc , que entrou no top 100 da mesma competição, também compartilhará segredos.
Você aprenderá como competir com sucesso em competições de programação de IA de jogos.
O que é o CodinGame?
codingame.com é uma plataforma educacional para desenvolvedores de todas as idades e níveis de treinamento. Você pode escrever em 26 idiomas : de C # e Python a Bash e Haskell. O mais legal é que as tarefas não são chatas e incompreensíveis, mas jogos reais com uma boa interface gráfica:
Um concurso é uma competição de 10 dias realizada a cada dois meses. Qualquer pessoa pode participar, não é necessário ser finalista do ACM ICPC. Obviamente, para chegar ao topo, você precisa pelo menos entender os algoritmos típicos da inteligência artificial dos jogos.
Mas, para passar algumas noites com interesse, basta o conhecimento mais básico. Em cada concurso, há um código pronto para ler os dados de entrada. Resta apenas ler as regras, escrever despretensioso se-else - e entrar em batalha!
Código de kutulu
"Código Cthulhu" é o último concurso, que ocorreu de 15 a 25 de junho. Para descobrir o enredo e o objetivo, basta uma descrição:
PH'NGLUI MGLW'NAFH CTHULHU R'LYEH WGAH'NAGL FHTAGN
O que pode mentir para sempre não está morto. E a morte morre em um misterioso aeon.
Você e sua equipe de pesquisadores descobriram o túmulo de Cthulhu. Esta é a pior decisão da sua vida, porque ele não estava pronto para acordar e agora está com fome de sua morte. Mas a cripta é um verdadeiro labirinto, e você não se lembra onde estava a saída ... Se ainda estiver lá!
Ah ... e parece que Cthulhu não estava sozinho, e agora ele está enviando os Profundos para você.
Tente permanecer vivo por mais tempo, mas lembre-se de que você sozinho não vai durar muito ...
As regras
Eu direi imediatamente que, em vez de ler uma descrição em texto das regras, você pode assistir a um vídeo da análise das regras e táticas básicas de Tinsane :
Caso contrário, continue a ler.
Mapa
No jogo, quatro jogadores andam no mapa gerado - mais precisamente, o gráfico de células conectadas umas às outras. Mais no mapa estão executando lacaios inimigos, cujo objetivo é alcançar e assustar os jogadores.
Personagens
- O pesquisador é um dos jogadores. Vai em qualquer direção em uma célula. Tem superpoderes, mas mais sobre eles mais tarde.
- Vanderer é um monstro verde. Aparece no mapa a cada 5 turnos, a partir de pontos conhecidos anteriormente. Ele gera mais de 3 a 6 movimentos, procura o jogador mais próximo e inicia a busca. Vai apenas um quadrado por turno. Se ele não pegou ninguém em N etapas, ele desaparece do mapa.
- Slasher - semelhante à Morte com uma foice. Aparece no lugar de um jogador cuja saúde caiu abaixo de 200 pontos e permanece no mapa até o final do jogo. "Vê" um jogador se não houver paredes entre eles. Se em 2 movimentos o alvo não for perdido de vista, o próximo movimento pula para o local onde o jogador foi visto pela última vez.
Sobrevivência
Se o andarilho ou slasher entrar na célula com o jogador, ele perde 20 pontos de vida. Além disso, os jogadores perdem uma certa quantidade de pontos de vida a cada turno sem motivo. Mas se houver pesquisadores vivos no raio de duas células, um pouco menos de saúde será perdida.
Superpotências de pesquisadores
- PLANO - Aumenta a saúde em 2 pontos em 5 turnos. Se outros pesquisadores estiverem dentro do raio de ação, o efeito se estenderá a eles, e o criador do efeito receberá +2 de vida para cada um. Você pode usar 2 vezes por jogo.
- YELL - assusta o jogador na próxima célula. A ação planejada para o próximo turno se torna WAIT (o jogador fica parado). É útil se o andarilho estiver perseguindo o inimigo e você quiser substituí-lo.
- LUZ - ilumina as células em um raio de 5, você pode usar 3 vezes por jogo. Ajuda a espantar os andarilhos: quando contam o caminho para o alvo mais próximo, cada célula iluminada conta como 4.
O fim do jogo
Um jogador morre se sua saúde cair para zero. Após 200 jogadas, os jogadores sobreviventes começam a perder saúde mais rapidamente, e o jogo termina quase imediatamente.
Os desenvolvedores do concurso dão as regras aos jogadores, mas jogadores bem-sucedidos vão ao Github e leem o código do árbitro .
Táticas
Devo dizer imediatamente que não comecei do zero. Em 16 de junho, Kontur realizou centros de codificação em sete cidades - reuniões para aqueles que desejam discutir o concurso e se divertir em um ambiente agradável ( foto ).
Passei no exame na universidade e não cheguei ao centro de Yekaterinburg, mas aproveitei o bônus dos organizadores - o kit inicial. Está disponível em duas linguagens - C # e TypeScript , e já implementa toda a infraestrutura: a lógica de ler o estado do jogo a cada turno, além de classes que caracterizam o jogo em si (como estado e possíveis ações) e algumas auxiliares (por exemplo, um timer personalizado) . Pude começar imediatamente a escrever a coisa mais interessante - meu cérebro bot pesquisador.
Um dos líderes do centro de Yekaterinburg é Vanya Dashkevich ( spaceorc ). Ele está no CodinGame há mais de um ano, participou de sete concursos e em cinco chegou ao top 100 do mundo:
Descobri em Vanya os detalhes da decisão, que lhe deram o 64º lugar no ranking mundial, e comparei sua decisão com a minha.
[1] Venha para os hubs: lá você pode obter links para kits iniciais, discutir as regras, criar táticas e conhecer pessoas interessantes.
Que no início do concurso, no final, o algoritmo para escolher a próxima jogada é o mesmo:
- Gere todas as ações disponíveis para o bot;
- Aplique-os ao estado atual;
- Avalie os resultados desses movimentos;
- Escolha o melhor.
Gerar ações disponíveis
Ollisteka : Já nessa etapa, comecei a aplicar heurísticas - imaginei-me no lugar desse pesquisador e decidi o que seria bom e o que não era. Posso ir para a próxima célula gratuita? Adicione tal movimento. Eu ainda tenho um plano não utilizado, e não há Wanderer ou slasher por perto que irá me atacar no próximo turno? Adicionar.
De acordo com o mesmo esquema, LIGHT e YELL entraram na lista de possíveis ações, mas o uso delas só me reduziu ainda mais na tabela de classificação. Portanto, eu ainda os removi da implementação final.
[2] Não tenha medo de incluir fantasia: para iniciantes, heurísticas simples e alguns operadores condicionais são suficientes.
Aplicação de curso
O processo de aplicação de uma mudança para um estado de jogo é chamado de simulação. A presença de simulação permite usar técnicas avançadas de programação de IA: minimax , algoritmos genéticos , Monte Carlo Tree Search e outros.
Ollisteka : É este passo que se relaciona com a minha "subimitação". "Nedo" - porque depois que eu fui, o resto dos jogadores deveria ir, os inimigos deveriam ir ou reaparecer. No entanto, fiquei com preguiça de fazer uma simulação completa para quatro jogadores e um grande número de inimigos com lógica não trivial. Portanto, mudei de saúde apenas dependendo de estar sozinho ou em grupo e não encontrei um andarilho neste turno.
spaceorc : Minha abordagem usual ultimamente tem sido duas etapas:
- você chega ao palco de qualquer maneira quando os organizadores abrem todas as regras e descartam a fonte do “árbitro” no Github;
- você pega o árbitro e escreve, olhando para ele, uma simulação.
A simulação está completa, com todas as nuances, mas ineficaz. Normalmente aposto na velocidade e profundidade da pesquisa ... Mas uma simulação completa permite que você execute muitas correspondências localmente e compare estratégias diferentes. Testei a simulação completa com o CodinGame - previ as posições dos lacaios, sabendo como os rivais caíam (isto é, o próximo passo) e descobri as discrepâncias. Quando a simulação completa estava pronta, comecei a escrever uma rápida - para fazer isso simplesmente, tendo uma funcional.
[3] Deseja chegar ao topo? Você precisará descobrir as regras e escrever uma simulação.
Simulação de oponentes
spaceorc : Escreveu o Monte Carlo Tree Search, mas foi pior porque havia muito pouco tempo para resolver. Em geral, essa abordagem veio a mim mais ou menos apenas no Ultimate Tic-Tac-Toe . Os oponentes jogaram da mesma maneira - simulação por jogada mais pontuação, meus movimentos - MCTS e jogam até o fim. Foi possível simular cerca de 50 jogos até o fim em 50 ms. Isso não é suficiente para o MCTS, então eu o recortei e voltei à idéia original.
Como resultado, uma simulação rápida ficou incompleta:
- parou de considerar os andarilhos a mais de 8 células de mim;
- parei de gerar os andarilhos, porque eles já aparecem em 5 movimentos, e essa é a minha profundidade de pesquisa aproximadamente.
Devido a isso, a profundidade da pesquisa aumentou. Eu também tentei simular apenas movimentos (sem YELL, LIGHT, PLAN) dos meus oponentes, mas ficou pior.
Função de avaliação
A função de avaliação ajuda a escolher o melhor de todos os movimentos disponíveis. Leva o estado do jogo na entrada e, na saída, fornece um número com uma estimativa - quanto maior, melhor o estado do jogo para o jogador atual.
Ollisteka : Quais parâmetros foram incluídos na minha avaliação:
- a saúde do meu pesquisador;
- andarilhos:
- se é provável que ele venha aqui na próxima jogada, então é uma péssima jogada;
- se estou na mesma linha que ele, quanto mais longe dele, melhor;
- se ele também me caça, então a distância é ainda mais importante.
- células livres ao redor, para não atingir um beco sem saída;
- outros pesquisadores, que são melhores para ficar perto;
- PLANO atual: se minha saúde cai abaixo de 230, então o tratamento é uma boa ideia.
Em algum momento, tentei avaliar as barras, mas quando as removi, fui elevado a algumas dezenas de posições na tabela de classificação. Se eu trabalhasse melhor na lógica deles, talvez eles fizessem mais bem.
Como resultado, minha avaliação pode ser menor, mas como eles dizem, funciona - não toque.
spaceorc : tentei brincar com as funções de avaliação, mas não funcionou muito bem ... Em geral, alguns daqueles que se mostraram significativamente mais altos do que eu na tabela de classificação não passaram por tanta coisa, mas criaram bons recursos para avaliação. Eu não lidei com isso. Minha função final de avaliação incluiu:
- o número de pontos (o passeio em que morreu + saúde);
- Corvo ;
- distância para pesquisadores estrangeiros.
[4] Experiência: altere os coeficientes dos parâmetros da função de avaliação, adicione novos parâmetros e exclua os antigos.
Escolhendo a melhor jogada
Classificamos os movimentos em ordem decrescente, pegamos o primeiro, usamos.
Otimização
Competir por um lugar no top cem não é suficiente para ter uma boa função de avaliação e uma simulação completa. Quanto mais rápido o bot funcionar, mais jogos serão simulados em um intervalo de tempo. Quanto mais jogos, maior a probabilidade de o movimento atual ser o melhor. Quanto mais otimizada a jogada, maior o lugar na tabela de classificação.
Ollisteka : Aproveitei o fato de que o mapa pode ser representado na forma de um gráfico - calculei antecipadamente os comprimentos de todos os caminhos de célula para célula e não gastei tempo com isso o tempo todo.
spaceorc : No CodinGame, a simulação funcionou rapidamente, em 50 ms ele fez várias dezenas de milhares de movimentos. Devido a que:
- Máscaras de bits e código não seguro.
- Explorer - int, andarilho - int, slasher - int.
- Todo estado mutável cabe em 128 bytes, então tudo funciona muito rapidamente com ele.
- A coordenada é byte, porque o mapa maior tinha 222 células livres.
- A fila deve ser - var queue = stackalloc byte [255].
- Pré-cálculo de percursos, distâncias e outras coisas.
Eu venho fazendo isso o tempo todo ultimamente, é muito bom. A propósito, eu sempre escrevo muitos testes para essa simulação, sem os quais ela simplesmente não pode ser depurada.
[5] Quer competir por um lugar no top 100 - livre-se de códigos ineficientes.
O que levou a
Ollisteka : Durante o concurso, meu bot permaneceu entre os 300 primeiros. Em algum momento, eu estava na 84ª posição no ranking mundial, mas então criei uma nova versão e não retornei ¯ \ (ツ) / ¯ Depois de terminar na 290ª posição, estou muito feliz por três razões:
- Este é o primeiro concurso em que participei, pois no passado eu estava muito ocupado com os estudos.
- Gostei do jogo em si - ficou claro como jogar e o que fazer para vencer.
- Os 15% melhores do mundo - isso parece legal :)
Era óbvio que, para chegar ao topo, é necessário fazer uma simulação completa e rápida. Mas como eu não queria fazer isso, adicionei parâmetros à função de avaliação e alterei as constantes mágicas.
spaceorc : Estou bastante satisfeito com o resultado, fui para o top 100 ... Mas ainda tinha que trabalhar mais na função de avaliação, um forte viés em direção à simulação. E eu estou cansado um pouco no final, minha imaginação não foi suficiente ...
Em conclusão
Confira CodinGame e tente sua mão! Em julho, eles prometem um novo concurso - venha para os hubs, codificaremos os bots juntos.
Links úteis:
UPD Obrigado dbf pelo comentário: Code of Kutulu foi carregado para multiplayer . Assim, você pode colocar em prática os conhecimentos adquiridos no artigo! :)