Histórico do Segundo Lugar no Mini AI Cup 4: Paper IO

Meu nome é Igor Volkov. Trabalho em uma empresa de consultoria como desenvolvedor Java, arquiteto, líder de equipe, gerente técnico. Funções diferentes, dependendo das necessidades atuais do projeto. Ele chamou a atenção para as competições do mail.ru por um longo tempo, mas acabou participando ativamente apenas no Paper IO.

Desta vez, os organizadores propuseram implementar uma estratégia de gerenciamento de bots baseada no jogo popular. Leia mais sobre as regras aqui . O código da minha estratégia pode ser encontrado aqui e exemplos de jogos no site do campeonato .

No começo da competição, como me pareceu, a idéia mais comum de implementação de pop-up foi o uso do MCTS . Portanto, passei um pouco de tempo experimentando esse algoritmo. E sem ter descoberto como usá-lo efetivamente para resolver o problema, decidi começar gerando muitas rotas retangulares (com duas e depois com três curvas) e sua avaliação subsequente.

Algoritmo de Estratégia

O algoritmo de alto nível da estratégia pode ser representado pelos 6 pontos a seguir:

1. Leia o estado do mundo
2. Converter objetos de mensagem em objetos de trabalho
3. Forme um conjunto de rotas retangulares
4. Classifique cada uma das rotas geradas
5. Escolha a melhor rota
6. Enviar equipe

Este algoritmo não mudou durante a competição. Somente o método de formação de rotas bot e sua avaliação foram modificados.

A classe SimpleStrategy contém a versão inicial da estratégia e a classe BestStrategy é uma versão aprimorada, que ficou em 2º lugar na competição.

Lendo o estado do mundo

O estado do mundo é transmitido como um objeto JSON via STDIN . Vi no pom.xml que você pode usar a biblioteca Gson e a tarefa de ler o estado do mundo foi bastante simplificada. Usando a biblioteca Gson, desserializou a sequência JSON lida do fluxo de entrada padrão em uma instância da classe Message . O código está em Main.java (linhas 44-49) .

Criar objetos de trabalho

O uso de objetos de transporte no código principal do programa geralmente não é muito conveniente e está incorreto na arquitetura. Por exemplo, os organizadores, por um motivo ou outro, podem alterar o formato das mensagens. Portanto, é necessário transformar objetos de transporte em trabalhadores, que serão usados ​​no código principal do programa. As classes Player e PlayerState preservam o estado do bot e a classe de utilitário MessagePlayer2PlayerConverter ajuda a criar essas classes com base nos dados da mensagem de transporte. A classe Bonus contém informações sobre o bônus de uma célula no campo de jogo. O código para criar objetos de trabalho está localizado em Main.java (linhas 61 a 74) .

Formação de rotas

Nas primeiras versões da estratégia ( SimpleStrategy ), o caminho foi definido usando as classes MovePlanWithScore e Move . Move define a direção do movimento e quantas células o bot deve mover nessa direção, e MovePlanWithScore contém a rota especificada pela matriz Move e uma estimativa dessa rota. Uma matriz pode conter de um a quatro objetos Mover . Apesar de serem consideradas apenas rotas retangulares com no máximo três voltas, na verdade a rota do bot é obtida na forma de uma linha interrompida. Para isso, escolha uma nova melhor rota retangular em cada turno. A função de geração de rota , implementada como loops aninhados, forma uma lista do MovePlanWithScore para sua avaliação adicional.

Essa formação das trajetórias do bot não foi muito eficaz em termos de desempenho da avaliação subseqüente, pois era necessário calcular as mesmas trajetórias várias vezes, mas foi muito útil para entender a mecânica do jogo.

Nas versões posteriores da estratégia, o BestStrategy começou a usar a árvore de rotas. A classe MoveNode reflete o nó desta árvore. A árvore está totalmente formada no início da estratégia. Preste atenção ao método init da classe MoveNode . É muito semelhante à geração de rotas da classe SimpleStrategy . Fundamentalmente, a rota em questão não é muito diferente da primeira versão.

A formação de rotas, eu acho, poderia ter sido melhorada um pouco mais, adicionando outra reviravolta. Mas não havia tempo suficiente para otimização.

Classificação da rota

Onde quer que o bot estivesse localizado, a melhor rota que terminava em seu território sempre foi escolhida para ele. Para avaliar a rota, introduzi dois indicadores: pontuação e risco. Pontuação - reflete aproximadamente o número de pontos marcados por tick do caminho e risco - o número de ticks que não são suficientes para completar o caminho (por exemplo, devido ao fato de o oponente poder agarrar pela cauda). O risco não apareceu imediatamente. Na primeira versão, se o bot descobriu subitamente no meio do caminho que não tinha tempo para concluir a rota, ficou "louco", pois todos os caminhos perigosos eram igualmente ruins para ele. De todas as rotas consideradas, a mais “segura” é selecionada com o número máximo de pontos por tick do caminho.

Para avaliar a segurança da rota, calculo a matriz de acessibilidade: para cada célula do campo de jogo, encontro uma marca na qual o bot do oponente pode aparecer nela. Primeiro, apenas um carrapato, e depois adicionou um cálculo de comprimento da cauda. Os bônus que podem ser levantados ao longo do caminho também não foram levados em consideração nas primeiras versões da estratégia. A classe TimeMatrixBuilder calcula matrizes de ticks e comprimentos de cauda de bots rivais. Essas matrizes são usadas para avaliar o risco. Se meu bot estiver em seu território no momento do cálculo da próxima jogada - o nível máximo de risco é atribuído a rotas perigosas, se o bot já estiver a caminho de um território estrangeiro ou neutro, o risco será avaliado como a diferença entre os tiques da conclusão do caminho (o bot chegou ao seu território) e o tiquetaque quando puder ameaçar perigo (por exemplo, o bot de outra pessoa pode pisar no rabo).

Nas primeiras versões da estratégia, a pontuação foi considerada apenas com base no território capturado e os bônus foram levados em consideração. Para encontrar as células capturadas, eu uso um algoritmo recursivo . Muitos participantes reclamaram da estranheza e da complexidade computacional excessiva do algoritmo usado pelos organizadores da Local Runner . Assumirei que isso foi feito intencionalmente para não oferecer soluções prontas aos participantes da competição.

Estranho, mas apesar da primitividade das primeiras versões da estratégia, mostrou-se muito bem: 10º lugar na caixa de areia. Na verdade, na pré-final, ele começou a cair rapidamente: outros participantes melhoraram suas estratégias.

Meu bot morreu frequentemente. Primeiro, devido ao fato de uma rota estar sendo construída para o território capturado pelos robôs rivais. O caminho inesperadamente se alongou e meu bot foi pego pela cauda. Muitas vezes morriam devido a uma previsão incorreta do comprimento da cauda e da velocidade do bot do oponente. Por exemplo, o bot de um oponente em desaceleração era perigoso, pois em cálculo aproximado a estratégia supunha que ele já deveria ter saído da célula e ele ainda estava lá. Para combater esses problemas, comecei a calcular um número maior de indicadores para cada célula do campo de jogo (classes AnalyticsBuilder e CellDetails ).

Contando células do campo de jogo

1. Marca em que o bot do oponente pode ocupar a gaiola (marca na cauda)
2. Marque em que o bot do oponente pode entrar na célula
3. O comprimento da cauda ao entrar na gaiola
4. Marque em que o bot do oponente pode sair da gaiola
5. Comprimento da cauda ao sair da gaiola
6. Marque em que uma célula pode ser capturada pelo bot de um oponente
7. Marque em que a célula pode ser o alvo para capturar território
8. Marque em que a célula pode ser atingida com uma serra

A profundidade da análise é limitada a 10 movimentos. Eu acho que foi possível obter maior profundidade recusando contar rivais individuais ou introduzir profundidade flutuante, mas não houve tempo suficiente para otimização. Além do AnalyticsBuilder, ele começou a usar o SimpleTickMatrixBuilder se houvesse falta de profundidade de renderização para o AnalyticsBuilder . Os resultados do Analytics são usados ​​pelo BestStrategy .

A função de classificação também melhorou um pouco:

1. Comecei a considerar os bônus: uma penalidade por receber um bônus de desaceleração e um bônus por receber bônus de aceleração e serra. Como resultado, o bot começou a evitar com êxito bônus ruins e pegou bons ao longo do caminho.
2. Ele começou a levar em conta o choque de cabeças. Adicionados alguns pontos para o confronto da vitória. Quanto mais possível uma colisão, menos pontos.
3. Para reduzir a probabilidade do ambiente, ele acrescentou alguns pontos para tirar as células de fronteira do oponente.
4. Reduzido o valor de células vazias na borda: quanto mais longe do centro, menor o valor. Observando as lutas das finais, cheguei à conclusão de que, pelo fato de capturar uma célula vazia, não havia necessidade de acumular pontos. O valor de uma célula vazia deve depender da proximidade de grandes aglomerados de células inimigas. Infelizmente, na final não era mais possível editar a estratégia.
5. Adicionados pontos para cercar a cabeça de bot do oponente. Não tenho certeza se isso de alguma forma ajudou. Talvez com as estratégias mais simples.
6. Ele acrescentou pontos até mesmo para uma captura fútil pela cauda (o bot do oponente conseguiu capturar o território no mesmo tique em que meu bot pisou em seu rabo). Definitivamente, não tenho certeza, mas acho que isso impediu que os robôs do oponente capturassem o território de outra pessoa e eles geralmente precisavam voltar ao seu próprio país.
7. No caso de detecção de uma possível morte por captura, aumentou muito o custo das células de fronteira do território do oponente.

Depuração da estratégia

As primeiras versões da estratégia continham um grande número de erros de digitação: aparentemente, o resultado da programação noturna. Por exemplo, na classe Cell , o índice foi considerado incorretamente: em vez de this.index = x * Game.sizeY + y , this.index = x * Game.width + y . No começo, tentei confiar apenas nos testes, mas minha intuição sugeria que, sem visualização e sem disputar partidas jogadas anteriormente, seria difícil encontrar erros no código e analisar as razões para tomar decisões erradas. Como resultado, o visualizador DebugWindow apareceu , no qual você pode visualizar os jogos jogados anteriormente passo a passo, bem como iniciar a depuração no tick desejado. O código não é muito bonito, escrito às pressas, mas me ajudou muito na depuração. Por exemplo, um erro foi detectado imediatamente com um cálculo incorreto do índice de células. Muitos participantes exibiram informações de depuração no console, mas isso me pareceu insuficiente.

Otimização

Para não perder tempo criando objetos e executando o GC, tentei criar alguns objetos com antecedência. Estas são as células do campo de jogo (classe Cell ). Além disso, para cada célula identificada vizinhos. Criou uma árvore de possíveis caminhos com antecedência (classe MoveNode ).

Presumi que muitos cenários precisariam ser simulados e, no processo, o estado atual se deterioraria e teria que ser restaurado todas as vezes. Portanto, para preservar o estado do mundo, tentei usar o máximo possível de estruturas compactadas. Para armazenar o território ocupado - BitSet (classe PlayerTerritory ). Cada célula do campo de jogo é numerada e o número da célula corresponde ao número do bit no BitSet. Para armazenar a cauda, ​​usei o BitSet junto com o ArrayDeque (classe PlayerTail ).

É verdade que não consegui jogar vários cenários devido à falta de tempo. E como a principal função de calcular o caminho se tornou recursiva e todo o estado pôde ser armazenado na pilha, as otimizações mais recentes não foram muito úteis para mim.

Idéias não realizadas

Ao avaliar o risco da rota do meu bot, levei em consideração cada oponente de forma independente. De fato, cada um dos rivais também tem medo de morrer. Portanto, valeria a pena considerar isso em uma avaliação de risco. Pelo menos, isso definitivamente tinha que ser levado em consideração nos jogos finais.

Contabilizando a morte futura de um oponente. Às vezes acontecia que o bot captura o território do oponente, e o oponente morre inesperadamente. É uma pena, porque, como resultado, você captura apenas células vazias.

Contabilizando células vazias que serão capturadas em um futuro próximo como uma função de avaliação.

Recomendações e agradecimentos

Eu recomendo que todos os desenvolvedores participem ativamente dos concursos de AI Cups. Isso desenvolve o pensamento e ajuda no jogo a aprender novos algoritmos. E, como minha experiência demonstrou, um pouco de zelo é suficiente para ocupar um lugar premiado e até mesmo um código simples e não muito ideal pode trazer resultados.

Muito obrigado aos organizadores. Apesar de alguns problemas técnicos, a competição acabou sendo interessante. Estou ansioso para o próximo!