Tornou-se uma tradição que, após as competições de programação esportiva, o vencedor ou apenas um jogador publique um artigo sobre Habré para dizer como foi bom participar da competição e como uma opção para vencê-la. Obviamente, muito pode ser extraído de seu artigo para competições futuras.
Mas acho que existem poucos artigos sobre a participação na competição atual na fase de testes beta, é claro que você não pode publicar o código de decisão, ainda não se sabe o quão boa é essa decisão e muita coisa ainda é desconhecida, porque agora, na verdade, este é apenas o começo do torneio, mas esse é o charme. O autor oferece ao leitor a chance de embarcar em um trem que parte e aproveitar uma viagem de Ano Novo ao mundo das estratégias de jogos.
Em primeiro lugar, obrigado por abrir o artigo, quero compartilhar um segredo imediatamente: esta será uma série de artigos nos quais espero abordar algoritmos genéticos e redes neurais. Enquanto isso, como já foi escrito acima, seja bem-vindo a uma viagem ao CodeBall da Copa AI da Rússia.
Link para a página de início rápido do campeonato.No link acima, o leitor poderá encontrar as regras do campeonato, as regras do jogo em si e a parte principal do aparato matemático necessário para criar o bot. Também na página de início rápido, há exemplos de bots já escritos para várias linguagens de programação, o que facilita muito o início inicial.
Vamos começar com um simples título de campeonato do CodeBall.
Uma boa combinação das palavras código e bola, quase futebol. As regras e a lógica do jogo também são semelhantes ao futebol, mas a cada rodada elas se tornam mais complicadas / portanto, tomaremos as condições iniciais dos jogos como base.
A essência do jogo, como declarado em uma música recente: os jogadores devem marcar, e o goleiro deve bater nas bolas.
Campo de jogo esquemático:
Observe que os robôs se movem no plano do piso da arena XZ, o eixo Y é responsável pela altura do objeto do jogo.
Também objetos esquemáticos do jogo (bola e bots (os organizadores os chamam de robôs))
Agora, algum texto para apoiar as imagens. O campo de jogo é um espaço tridimensional fechado, nem a bola nem os robôs podem ir além dele. Nesse espaço, existem duas áreas do “portão” quando atingidas, nas quais a bola é considerada pontuada por um dos jogadores. Para que o gol seja contado, é necessário que a bola esteja completamente atrás das linhas de gol (indicada por uma linha pontilhada na figura).
Para simplificar os cálculos de colisões (colisões) de objetos de jogo (arena, bola, bots), bots e a bola são consideradas esferas ideais (bolas), descritas pelos seguintes valores: raio da esfera, coordenada do centro da esfera, massa, velocidade. A arena também é descrita por primitivas matemáticas ideais; portanto, o cálculo da colisão é dispensado sem a participação de polígonos, o que simplifica bastante a tarefa. Se você percorrer as regras do campeonato até o fim, o leitor encontrará um programa no pseudocódigo, que é apenas responsável pelos cálculos acima. Esse pseudocódigo, após pouco esforço físico, é traduzido para a linguagem de programação de sua escolha e é bastante viável. Mas mais sobre isso mais tarde.
Algumas palavras sobre a física do mundo do jogo. Para dar credibilidade ao que está acontecendo na arena, a gravidade é introduzida, ou seja, os bots e a bola são constantemente afetados pela força da gravidade direcionada para baixo em relação ao piso da arena. As outras formas de interação física, como atrito ou velocidade angular (rotação) dos objetos, foram ignoradas pelos organizadores em favor da simplicidade da descrição do mundo físico. Ao bater nas paredes da arena, a bola perde parte de sua energia, mas isso não complica muito o mundo e é compreensível do lado de fora que não há como criar uma máquina de movimento perpétuo na forma de uma bola.
Para tornar o mundo ainda mais plausível, foi aplicado um esquema de cálculos com Ticks e Mikrotiks. Em
seu primeiro artigo, o autor abordou em detalhes o conceito de tempo de tocar teca. Nesta competição, podemos olhar para o mecanismo físico nos códigos-fonte, como ele disse, será útil para nós no futuro e descobrir que para os jogadores existem Tiques, e dentro do mecanismo tudo acontece no Mikrotik, por padrão 100 Mikrotik em um tick, o que possibilita uma precisão mais precisa descreva colisões de objetos e evite coisas desagradáveis como a falha de objetos fora da arena ou a falha de objetos um no outro, levando a erros na interação entre eles.
Nós meio que descobrimos o mundo (arena) e o tempo do jogo, vamos olhar para os objetos do jogo: bots e bola. A bola que já descobrimos pelas regras da competição é uma esfera. Para ser breve, um bot é uma bola de raio menor e massa maior, que pode receber comandos: indique a velocidade desejada (este é um vetor tridimensional que contém a direção e o comprimento ou magnitude da velocidade) e a força do salto, se o salto for atualmente aconselhável do ponto de vista a lógica do jogo. Nesta fase da competição, foi introduzida uma simplificação de que, se o bot estiver em voo (não tocar nas paredes da arena), ele não poderá executar comandos para alterar a velocidade.
Passamos ao mais difícil ou vice-versa simples, tudo depende da experiência do leitor em trabalhar com vetores tridimensionais. Descrição da localização dos objetos do jogo. Imagem de apoio
Vamos direto à botânica.
A cada tick do jogo, sua estratégia receberá os seguintes objetos:
Bola:
class Ball: x: Float
e uma lista de bots, com dados para cada bot:
class Robot: id: Int player_id: Int is_teammate: Bool
você pode ver imediatamente que é inconveniente trabalhar com esses dados, é desejável introduzir um vetor 3D de classe (objeto) e um vetor 2D de classe. Muito dependerá da linguagem de programação de sua escolha. Normalmente, essas classes já são escritas e são facilmente encontradas na Internet para a linguagem de programação desejada. O autor agora está escrevendo um bot em c ++, mas tentará se limitar ao pseudo-código. Se você introduzir classes de vetores completas, as operações de adição, subtração, multiplicação, normalização e outras operações de vetores permanecerão dentro da classe, o que simplificará bastante o trabalho na estratégia.
Há também uma classe de jogadores que indica quais robôs da lista são seus, quais são:
class Player: id: Int me: Bool
Depois de transmitir dados sobre o mundo do jogo para a entrada da sua estratégia, o mecanismo do jogo dá a você o controle e inicia um cronômetro para os cálculos; o tempo para os cálculos é limitado, em média, em cerca de 20 milissegundos para todas as ações dentro do tick. Suspeita-se que, neste momento, também inclua tempo para desserializar os dados recebidos e
serializar os dados enviados por sua estratégia ao servidor. Mas como o número de bots é 4 (seus 2 e 2 oponentes, na rodada final o número total de bots aumentará para 6), o tempo para essas operações pode ser negligenciado.
Chegou a hora das equipes.
Por exemplo, queremos dar ao bot um comando para avançar em direção à bola. Para encontrar o vetor desejado da direção da velocidade, você precisa subtrair a posição do bot da posição da bola, obtemos o vetor de direção para a bola, então ele pode ser normalizado e multiplicado pela velocidade máxima do bot das constantes do mundo. Na foto mais
Provavelmente o leitor notou no slide que os cálculos podem ser realizados para vetores 3D e 2D. Se levarmos em conta o fato de que o bot passa mais tempo no plano da arena, a simplificação dos cálculos em duas coordenadas não afetará a precisão dos cálculos para interceptar a bola. Claro, você não deve esquecer a altura da bola, mas, levando em consideração a gravidade, mais cedo ou mais tarde ela afundará no bot.
Um salto de bot é a adição de velocidade vertical (velocidade vertical), a direção do salto de bot coincidirá com a direção da velocidade atual do bot com a adição de um componente ao longo do eixo Y.
Se adicionarmos uma lógica de movimento mais complexa às palavras acima, podemos obter o seguinte comportamento dos bots:
Agora, existe uma caixa
de areia
no site onde você pode assistir aos jogos, mas nada parece se você escrever sua estratégia e seguir seus jogos. Foi experimentalmente estabelecido que mesmo a estratégia mais simples, composta por várias dezenas de linhas de código, pode funcionar muito bem.
Das formas simples de estratégias que vêm à mente, a estratégia de alocar um bot para proteger o portão, o segundo bot para criar um atacante. A principal tarefa do atacante é perseguir a bola e, se for bem-sucedido, atacar em direção ao gol do adversário. Um bot que joga como goleiro geralmente é limitado em seu movimento pelo campo e atua principalmente na área de gol. Todas essas coisas são facilmente descritas usando construções if-else do idioma escolhido. De qualquer forma, meu leitor terá que criar uma estratégia nesta fase. De acordo com os termos da competição, você não pode publicar o código fonte da estratégia. Mas acho que não é proibido discutir abordagens para projetar uma estratégia.
Parece-me que os organizadores do concurso escolheram um tópico interessante para o torneio, o único site é um pouco lento, mas espero que seja corrigido em breve.
alguns belos momentos de jogo do participante do campeonato:
Estou aguardando comentários nos comentários sobre o artigo, sobre o que falar mais detalhadamente.
No próximo artigo, tentarei descrever métodos para prever o comportamento da bola a tempo de um jogo de bots mais significativo em sua estratégia.
Enquanto isso, parabéns pelo próximo ano novo de 2019!
Para ser continuado.