No início do outono, a competição para escrever bots Mini AI Cup # 3 (também conhecida como Mad Cars) foi concluída, na qual os participantes tiveram que lutar em carros. Os participantes discutiram muito sobre o que vai funcionar e o que não vai funcionar, idéias foram expressas e testadas desde simples ifs até o treinamento de redes neurais, mas os principais lugares foram ocupados pelos caras com a chamada "simulação". Vamos tentar descobrir o que é, comparar soluções para o 1º, 3º e 4º lugares e discutir outras soluções possíveis.

Isenção de responsabilidade

O artigo foi escrito em colaboração com Alexei Dichkovsky (Commandos) e Vladimir Kiselev (Valdemar) .

Para quem quer apenas ler sobre as decisões dos vencedores, aconselho que comece imediatamente com o item “Simulação”.

Declaração do problema

Desta vez, a mecânica do mundo era muito parecida com o jogo móvel Drive Ahead: os jogadores receberam um carro com um botão localizado; a tarefa é pressionar o botão do inimigo mais rápido do que ele. Se ninguém vence em 600 ticks de jogo, o cartão começa a afundar em uma pilha de lixo, que também pode pressionar um botão. Em outras palavras, você precisa proteger seu botão dos inimigos, do mundo ao seu redor e montes de lixo (vitalmente, sim). Cada jogador recebeu 5 vidas, o jogo passou de 5 para 9 rodadas, enquanto alguém não acabou com suas vidas. Cada rodada foi realizada em um mapa aleatório e carros, o mesmo para os dois participantes. No total, havia 6 cartas diferentes e 3 tipos de carros - um total de 18 combinações diferentes.

Cada rodada é dividida em carrapatos. Um carrapato é uma jogada, como no xadrez. A única diferença é que os dois jogadores vão ao mesmo tempo. Existem competições em que todos se revezam, ou você pode executar uma ação apenas uma vez a cada poucos movimentos e selecionar unidades como um quadro .
Cada tick para o bot chega a um estado de paz e tem a oportunidade de realizar três ações: , , . Essas ações fazem o carro seguir uma das direções e, ao mesmo tempo em que não toca nas rodas da terra, eles dão uma pequena rotação ao corpo inteiro (um pouco da física dos fliperamas). Depois que os dois oponentes escolhem uma ação, uma simulação do mundo do jogo é iniciada, um novo estado é considerado e enviado aos jogadores. Se alguém clicar em um botão, a rodada termina e a próxima começa. Tudo é simples, mas há nuances.

Regras mais completas podem ser encontradas aqui . E veja os jogos finais aqui .

Descrição geral da solução

A maioria das competições de criação de bots é muito semelhante: há um número finito de ticks (há cerca de 1.500 no máximo por uma rodada), há um número finito de ações possíveis, você precisa escolher uma sequência de ações para ser melhor que seus oponentes. Um pouco mais tarde, retornaremos ao que significa ser melhor, mas, por enquanto, descobriremos como lidar com o problema principal - um grande número de opções: no início, temos um estado inicial, então cada máquina pode se mover de três maneiras diferentes, o que nos dá 9 combinações diferentes para dois carros, pelo 1500º movimento serão 9 ^ 1500 combinações diferentes ... O que é um pouco mais do que gostaríamos se planejássemos resolvê-los durante a existência do Universo.

Aqui chegamos ao que é simulação . Este não é um tipo de algoritmo, mas simplesmente uma recriação das regras do jogo com precisão suficiente ou completa, para que seja possível classificar as soluções. Obviamente, não analisaremos todas as soluções, mas apenas parte delas. Um algoritmo de busca será usado para isso - na árvore de estados do jogo, estamos procurando o melhor para nós. Existem muitos algoritmos (do minimax ao MCTS), cada um com suas próprias nuances. É melhor se familiarizar com as decisões que os participantes das competições anteriores de IA escreveram. Isso fornecerá um entendimento básico de quais condições os algoritmos funcionam e em que condições não. Existem muitos links para isso em um repositório especial .

Ao escolher um algoritmo, você deve considerar:

prazo para 1 tick (aqui eu calculei mal este ano, mas consegui ficar em 3º lugar);
número de jogadores. Por exemplo, se houver três jogadores, será difícil usar o minimax;
precisão da simulação, como isso pode permitir a reutilização de cálculos antigos;
“Ramificação” da árvore de estados (é possível calcular todos os estados possíveis pelo menos 10 passos adiante);
bom senso - não comece a escrever o MCTS se a competição durar 4 horas.

Nesta competição, 1 tick deu 10-13ms (2 minutos para o jogo inteiro). Durante esse período, o bot teve que ler os dados, tomar uma decisão e enviar um comando para se mover. Isso foi suficiente para estimular cerca de 500-1000 movimentos. Iterar sobre todos os estados. O algoritmo de pesquisa mais simples pode parecer uma comparação de três opções de movimento: "50 ticks vão para a esquerda", "50 ticks vão para a direita", "50 ticks clicam em parar". E, por mais simples que pareça, não está muito longe da decisão do vencedor.

Porque contamos apenas 50 movimentos à frente, o que na maioria dos casos não conta até o final do jogo, precisamos de uma função de avaliação que diga como é bom e ruim o estado do mundo para nós. Na maioria das vezes, ele se baseia em heurísticas e na compreensão do que é importante para a vitória. Por exemplo, na competição da Copa da AI russa de 2014, havia corridas, mas você poderia ganhar se chegasse por último, se obtiver mais pontos de bônus. Portanto, a função de classificação deve estimular a coleta de pontos ao mesmo tempo que o movimento rápido ao longo da rodovia. A pontuação só pode ser calculada para o último estado da simulação (após 50 ticks) ou como a soma das estimativas dos estados intermediários. Freqüentemente, a estimativa "diminui" no tempo, para que os estados que ocorrem mais cedo sejam mais influenciados. Porque não podemos com certeza prever o inimigo, então é menos provável que opções futuras aconteçam, não dependeremos muito delas. Além disso, essa técnica torna o bot mais rápido para concluir suas tarefas e não adiar tudo para mais tarde. Mas vale a pena notar que o bot correrá menos riscos por causa dos benefícios subsequentes.

Como vamos prever o estado do mundo em resposta às nossas ações, precisamos modelar o comportamento dos inimigos. Não há nada complicado e existem algumas opções comuns:

Esboço ou heurística
Uma lógica simples de comportamento é escrita onde o inimigo simplesmente não faz nada ou escolhe ações com base em heurísticas simples (por exemplo, você pode usar suas primeiras versões da estratégia ou simplesmente repetir o movimento anterior do oponente).
Use o mesmo algoritmo que você mesmo
Primeiro, tentamos encontrar as melhores ações para o inimigo (contra o nosso melhor conjunto de ações desde o último movimento ou contra um esboço) e depois procuramos a melhor ação para nós mesmos, usando o comportamento que o inimigo encontrou. Aqui o bot tentará resistir a inimigos complicados. Essa lógica não funciona bem no início da competição, porque muitos bots ainda são muito fracos e sua decisão será muito cautelosa com eles.
Outros
O mesmo minimax repete todos os movimentos dos jogadores ao mesmo tempo, e ele simplesmente não precisará de heurísticas.

Se você implementar todas as etapas acima, provavelmente obterá um bot muito bom, especialmente se você conseguir uma boa função de classificação. Mas, olhando através de suas lutas, você pode ver que em certas situações ele se comporta de maneira estranha. A correção da função de avaliação para essas situações pode ser difícil ou existe um grande risco de quebrar outra lógica. Aqui muletas e ifs vêm em socorro. Sim, os últimos dias da competição geralmente se resumem a escrever muletas e ifs para corrigir as falhas em quaisquer condições específicas. Pessoalmente, eu realmente não gosto dessa parte, mas notei mais de uma vez que são muletas nas finais que podem afetar a organização dos lugares entre os dez primeiros, o que significa que um não-escrito se pode custar um prêmio (meu coração dói quando escrevo essas palavras, Eu também amo belos algoritmos e soluções).

P: É possível fazer sem simulação?
R: Sim, você pode usar soluções em heurísticas (árvores de decisão, vários ifs etc.). Há um bom artigo com arquiteturas de IA sobre heurísticas.

P: Quanto melhor o uso da simulação do que as abordagens heurísticas?
A: Tudo depende da tarefa. Por exemplo, aqui algumas combinações de cartas e carros podem ser codificadas com ifs e sempre vencer (ou empatar). No entanto, muitas vezes a simulação encontra soluções difíceis de pensar por si mesmo ou difíceis de implementar heurísticas. Nesta competição, quando você vira outra máquina, as decisões nas simulações colocam sua roda na roda do inimigo, que apaga a bandeira "no ar", o que significa que o inimigo não pode aplicar a rotação do corpo e voltar as rodas. Mas a decisão não pensou no significado disso, apenas encontrou opções em que o inimigo cairia mais rápido no telhado e pressionaria o botão dele.

P: Redes neurais e RL?
R: Por mais popular que seja, nas competições de bot essas soluções raramente têm bom desempenho. Embora as redes neurais não precisem de simulação, porque eles podem simplesmente emitir uma ação com base nos parâmetros de entrada do estado atual, ainda precisam aprender alguma coisa e, para isso, muitas vezes precisam criar um simulador para conduzir milhares de jogos localmente. Pessoalmente, acredito que eles têm potencial. Talvez eles possam resolver parte do problema ou usá-lo em condições de tempo de resposta muito limitado.

Nota
Em relação ao número finito de ações possíveis, vale esclarecer que às vezes é permitido "suavemente" ajustar algum parâmetro. Por exemplo, não apenas avance, mas com alguma porcentagem de energia. Nesse caso, a “finitude” do número de conclusões pode ser facilmente alcançada simplesmente usando vários valores, por exemplo, 0%, 25%, 50%, 75% e 100%. Na maioria das vezes, apenas dois são suficientes: "totalmente ligado" e "completamente desligado".

Simulação

Nesta competição, usamos o mecanismo físico de esquilo pronto. As expectativas dos organizadores eram de que ele era velho, testado pelo tempo e tem muitos invólucros para que todos possam incluí-lo em sua decisão ...

Na dura realidade, o mecanismo produzia valores diferentes a cada vez, o que dificultava o reinício para calcular as opções de movimentos. O problema foi resolvido "de frente" - um alocador de memória foi escrito em C e um pedaço de memória com o estado do mundo foi completamente copiado. Esse alocador pôs fim à capacidade de escrever soluções em idiomas diferentes do C ++ (na verdade, era possível, mas com muito trabalho e um alocador ainda teria que ser escrito em C). Além disso, a precisão da previsão foi influenciada pela ordem de adicionar elementos ao mundo do jogo, o que exigiu uma cópia muito precisa do código que os organizadores usavam para calcular os jogos. Mas ele já estava em Python. O último destaque no caixão de outras linguagens de programação foi que o mecanismo é antigo e contém muitas otimizações que não podem ser recriadas com precisão durante a competição para obter sua própria versão reduzida da simulação de física.

Como resultado, o mecanismo, que deveria dar a todos os participantes condições iguais para simular movimentos, tornou-se o obstáculo mais difícil para isso. Mais de 10 pessoas foram capazes de superá-lo.Os primeiros 7 lugares na tabela de classificação foram ocupados exclusivamente pelos caras que fizeram a simulação exata, o que pode servir como prova de sua importância em tais competições.

Com exceção de alguns participantes que foram capazes de entrar no esquilo e otimizar a cópia de seu estado, o resto teve uma simulação de aproximadamente o mesmo desempenho (o que tornou a competição um pouco mais interessante, porque você sabe que a luta é pelo algoritmo de decisão, não "quem conta mais os movimentos").

Algoritmo para pesquisar e prever um adversário

A partir deste ponto, uma descrição separada das soluções começa. Os algoritmos serão descritos em nome de seu autor.

Vladimir Kiselev (Valdemar) 4º lugar

Uma pesquisa aleatória (Monte Carlo) foi usada para pesquisar o espaço da solução. O algoritmo é o seguinte:

Inicializamos o genoma - uma sequência de ações (esquerda, direita, parada) para 60 ticks - dados aleatórios.
Pegue o melhor genoma encontrado
Alterar aleatoriamente uma das ações
Usando a função de avaliação, obtemos um número - um indicador de quão bom é o novo genoma
Se você obtiver uma solução melhor, atualize a melhor solução.
Repita novamente da etapa 2

Meu simulador produziu ~ 100k simulações do mundo em 1 segundo, considerando que há uma média de ~ 12ms por tick, obtemos 1200 ações por tick. Ou seja, em 1 tick, conseguimos realizar o ciclo completo cerca de 20 vezes.

Para encontrar a solução ideal, esse número de iterações claramente não foi suficiente. Portanto, a idéia com ações de “alongamento” foi implementada: em vez de um genoma de 60 movimentos, operaremos com uma cadeia de 12 movimentos “alongados” - acreditamos que cada ação dura 5 tiques seguidos.
Mais: Melhorando a qualidade das mutações reduzindo o comprimento do genoma, a simulação também pode ser executada a cada 5 carrapatos e checar 100 genomas em vez de 20 (para evitar quedas no limite de tempo, eventualmente interrompido aos 70).
Menos: ações de alongamento podem levar a soluções não ideais (por exemplo, girar no para-choque, em vez de um rack estável)

Deve-se notar as técnicas que melhoraram significativamente a qualidade do algoritmo:

Realizamos a inicialização aleatória apenas no primeiro tick, e no restante do tempo reutilizamos a melhor solução encontrada com um turno de 1 movimento (a ação no 2º tick é deslocada para o 1º, etc., uma ação aleatória é adicionada ao final). Isso melhora muito a qualidade da pesquisa, porque, caso contrário, o algoritmo "esquece" o que ele faria no último tique e faz solavancos sem sentido em direções diferentes.
No início do curso, fazemos alterações mais intensivas (alteramos o genoma 2 ou 3 vezes em vez de uma) na esperança de quebrar o máximo local (semelhança de temperatura no método de simulação do recozimento).
A intensidade foi selecionada manualmente: as primeiras 30 iterações produzem 3 mutações, as próximas 10 por 2 e depois 1.
Muito importante é a previsão de ações inimigas. Em detrimento do tempo para procurar nossa própria solução, lançamos uma pesquisa aleatória do lado do oponente, com 20 iterações e depois 50 para nós mesmos, usando informações sobre os movimentos ideais do oponente.
A melhor decisão do oponente também é reutilizada no próximo lance com um deslocamento. Ao mesmo tempo, ao procurar uma solução para o inimigo, o genoma do último movimento é usado como minhas ações pretendidas.

Durante a competição, ele usou ativamente ferramentas para o desenvolvimento local, o que tornou possível encontrar rapidamente erros e se concentrar nos pontos fracos da estratégia:

arena local - lançamento de muitas partidas contra a versão anterior;
visualizador para comportamento de depuração;
um script para coletar estatísticas sobre correspondências do site - permite entender em quais mapas e máquinas a derrota ocorre com mais frequência.

mortido:
Contar a cada 5 ticks parece arriscado, especialmente se o inimigo estiver se afastando das opções que você previu. Por outro lado, neste mundo de jogo por 5 ticks, não aconteceu muita coisa.
Além disso, na minha decisão, adicionei combinações aleatórias a cada tick, mas definitivamente não vou dizer como isso afetou a decisão.

Comandos:
Alterar algumas ações com um número tão grande de simulações não parece muito significativo, porque poucas mudanças ocorrem em uma ação. Mas quando você estica uma ação para 5 pontos de significado, ela parece se tornar mais.
Também não gosto da ideia em si - pegamos o melhor conjunto e tentamos editá-lo em algum lugar no começo. Parece ilógico que a mudança dos primeiros ticks deixe os subsequentes pelo menos relativamente adequados.

Alexander Kiselev (mortido) 3º lugar

Armado com artigos de vencedores de outras competições, decidi usar o algoritmo genético. Aconteceu, no entanto, algo semelhante a uma pesquisa aleatória ou mesmo uma imitação de recozimento, mas mais sobre isso mais tarde.

Codificamos a solução com uma matriz de 40 números, onde -1, 0 e 1 correspondem aos movimentos , e .

No início de cada rodada, calculei quanto tempo já havia gasto durante todo o jogo, contei um novo limite de tempo com base em quantas rodadas ainda haveriam, e cada rodada que presumi ter 1200 ticks. T.O. Inicialmente, tentei gastar não mais do que 11ms por turno, mas poderia "andar um pouco" no final se as rodadas anteriores fossem mais rápidas que 1200 ticks.

Valdemar:
Curiosamente, esse chip piorou o jogo para mim. Verificou-se que é sempre melhor gastar 20-30ms do que 11 primeiro e 60 no final

Um terço desse tempo, eu estava procurando a melhor jogada do inimigo, o resto foi calculado por minha própria decisão. Ao procurar uma jogada para o inimigo, meu comportamento foi modelado como o melhor da última jogada, alterado em 1 ponto. I.e. como se eu continuasse a agir de acordo com o plano elaborado no último tick, e ele estivesse tentando resistir a mim.

A busca pela solução em si foi a mesma para ela e para o oponente:

Tomamos a decisão da última jogada e a alteramos em 1 jogada (o que já fizemos)
Provamos para a população de soluções aleatórias até preenchermos tudo
Simulamos todas as decisões e ajustamos a adequação usando a função de avaliação. Lembramos o melhor.
Enquanto houver tempo para cálculos
1. Dica, sempre adicione 1 mutação da melhor solução atual à população, lembre-se se for melhor
2. Contanto que haja um lugar na nova população e o tempo para cálculos não tenha sido excedido (você pode ir no chão de uma população povoada)
  1. Tomamos dois indivíduos diferentes e saímos com a melhor forma - mãe
  2. Tomamos dois indivíduos diferentes e saímos com o melhor condicionamento físico - pai (não deve coincidir com a mãe)
  3. Atravessá-los
  4. RND < se RND <
  5. Simulamos uma solução e lembramos, se é a melhor

Como resultado, retornaremos a sequência de ações que é considerada ideal. O primeiro movimento é enviado como uma ação de bot. Infelizmente, houve uma séria desvantagem no meu plano, pois o número de simulações que podem ser feitas em um tick foi muito pequeno (inclusive devido à longa função de avaliação); no servidor da competição, 4 pontos foram realizados apenas 1 vez e, para o inimigo, não foi realizado. Isso tornou o algoritmo mais parecido com uma pesquisa aleatória ou um recozimento simulado (desde que conseguimos alterar a solução 1 vez desde a última jogada). Já era tarde demais para mudar alguma coisa, e conseguimos manter o 3º lugar.

É importante implementar os algoritmos de cruzamento, mutação e geração de soluções aleatórias iniciais, pois depende de quais decisões serão testadas e uma aleatória completa não é tão boa quanto parece à primeira vista (funcionará, mas serão necessárias muito mais opções).

Na versão final, decisões aleatórias foram geradas em segmentos, que excluíram soluções "repuxas" em um só lugar:

Equipe aleatória selecionada
Durante todo o comprimento da solução (40 movimentos)
1. Escrevemos o comando atual na célula
2. Com uma probabilidade de 10%, mudamos a equipe atual para uma aleatória

De acordo com uma tecnologia semelhante, também ocorreu uma mutação - um segmento aleatório da solução foi substituído por um comando aleatório. O cruzamento ocorreu escolhendo o ponto em que a decisão foi tomada de um dos pais e depois do segundo.

Gostei que usássemos todo o tempo disponível para encontrar a melhor solução. Não é grande coisa se a solução não é a melhor - podemos melhorá-la no próximo tick, porque a otimização acaba sendo "borrada" a tempo. , . , - , . ,

Valdemar:
1 , , .

Commandos:
— - .
— , . , … , . " ”. -.

(Commandos) 1

( ), n m . 3^2=9 . m + n 40 .

 |----------- n  -----------|---------- m  --------| |   ...   |   ...   |

: , , . ( ).

n m , . , .

, ( , ):
- , , , .
- , , . . . , , , .
- . ; ( ).
n m . , .1, , . - ( ) , — , ;
. , — . , ( ).

Valdemar:
, 2 . . , .

mortido:
! , . . , 2 , 40-60 . , 3 .
n + m == const ?

. n + m != const , . , . - .

(Valdemar) 4

, . , ( , , ..) [0..1].
. : , .
, , : , .

, :

— 70 180 ( : ).
, .
0..500
— [2pi, pi/4] [0, 1]
— , ( ), ( , , )
— , , , .
, , .
— . .
Y — .

, 2 , .

“” ,
“ ” , , .

mortido:
, .. , .

Commandos:
, . -

(mortido) 3

, chipmunk. . , , , , . .

3 .

, ( , , ):

. , , ( , );
, — , ; , 1 ;
;
( , );
( “+”, “-”);
- ( “+”, “-”); , , , ;
30 , , ( );
, .

, , (, , )

Valdemar:
. , “ , , ” , ( ..) .

, , . .

Commandos:
, , “”… ? , “” .

(Commandos) 1

SquaredWheelsBuggy , .. , . Buggy , , ( /).
:

;
; — , , 1 0; .. ;
. ; 10 ( );
( , );
(, );
— - , ;
/ ; , — ; .

1-5 , . 2 “ ”.

Valdemar:
, . , .

mortido:
, 10 .

IF'

(Valdemar) 4

, if'. 3 , , . , , -.
: , “” — , - , ( , ) — .

. , .
— , .
. “ ” .
, , .
, , .

, : . , , if' .

mortido:
, . .

Commandos:
if'. , , … , , .

(mortido) 3

- .

3 . . . “”, . , , .

, “” . . , , , - . . , , .. .

, , , , , . … . - — , ( , ).

Valdemar:
, . . “” , if'. , — .

, + . , .

Commandos:
… , - — , , . , , .

(Commandos) 1

. (, , ). ( ) /.

pill carcass map , , ( ). island map, , .

island hole buggy. / , , ( ). — . , , . SquaredWheelBuggy . , , , . , … , , .

(Pill map, Bus) , ( / 100% ).

pill hubble map. , ( ), . .

— , ...

, . , . ( ).

Valdemar:
, — . , .

mortido:
, “” .

Valdemar:
. , . ( ) .
. “”, , , , :)
, mailru , .

mortido:
: , … , , ( ). , 3 , , … .

Commandos:
- , . , , , . … . — , .
— ++. . , . 1 -.

, . , . , , .

Mail.Ru Group .

Valdemar
mortido