Como fundimos a programação final do IT-Planet

Nós não somos maus, mas existem muitos erros. Desenvolvimento de inteligência artificial para o jogo "Hockey" em ~ 7 horas.

Inicialmente, o artigo foi planejado sobre as estratégias dos participantes, sobre o que eles conseguiram fazer no tempo da competição e se estavam satisfeitos com o trabalho realizado, mas, após entrevistar oito finalistas, ficou claro que nada resultaria e que era urgente mudar de direção.

O fato é que recebemos no máximo 6 palavras para perguntas de seu interesse e imediatamente ouvimos descontentamento sobre os bugs que os participantes encontraram. Apenas uma pessoa escreveu:

Não quero escrever nada negativo, acho que isso está incorreto e os próprios organizadores devem ficar tristes. Portanto, direi que a ideia da tarefa é bastante interessante, embora eu pessoalmente não goste desse formato de competição (Anna Prozorova).

Pelo título do artigo, fica claro que não ganhamos nada. E sim, somos "nós". Ao longo dos dias da competição, fiz muitos bons amigos, incluindo Anna ( odrus ), que é a coautora deste artigo. Também no último momento conversamos com Leo ( zadamantiy ) e, com sua permissão, descrevemos a participação na final.

Pessoalmente, sou membro do movimento “Um mundo livre de reclamações”, mas pendurarei minha pulseira por outro lado e vou reclamar, ainda que em quadrinhos, porque, por outro lado, essas são as condições da competição e você precisa ser um bom especialista para vencer e lidar com as falhas! Pelo contrário, não temos queixas - muito obrigado!

Sob o corte, além de descrever as regras do jogo, as regras da competição e os bugs encontrados, compartilharemos com você nossos batentes, o que encontramos pessoalmente e como resolvemos esse ou aquele problema, como nos preparamos para a competição. Talvez em algum lugar você se reconheça se participou de tais competições.

O objetivo do artigo é coletar os arquivos do concurso tanto do lado dos participantes quanto dos organizadores, cortá-los no nariz e nunca pisar no mesmo rake novamente. Esperamos que o artigo aumente o nível do próximo concurso.

1. Introdução

Algumas palavras sobre nós

Ilya

Participante anual da Copa da AI da Rússia e da Mini AI Cup desde 2017. Eu também sigo Codingame e Halite. Não tenho conquistas especiais, mas aprendi muito com os outros. Para mim, o principal não é participação, não vitória, mas dar 100% e finalmente dizer: "Fiz tudo o que pude, percebi tudo o que queria, apliquei tudo o que sabia". Eu não conheço a linguagem de programação Java. Para mim, isso já é uma prática comum da concorrência para estudar completamente a nova pilha de tecnologias.

Anna

Um aluno simples, com pouca experiência em resolver problemas algorítmicos, mas sem muita experiência em participar de olimpíadas e concursos semelhantes. Especificamente, no Planeta TI, decidi participar para testar meus conhecimentos e habilidades, ganhar experiência, me comunicar com pessoas interessantes. Ela estudou a linguagem de programação Java na universidade, mas não teve nenhuma experiência prática por muito tempo.

Leão

Ele participou de todos os tipos de seleções do ICPC, hackathons como "Build University 20.35" e "Digital Breakthrough". Bem, as pequenas coisas em algumas olimpíadas universitárias.
Consequentemente, nossa universidade geralmente enviava muitos participantes ao concurso para sql, mas este ano não foi. Me ofereceram para participar de Java, tive que lidar com uma nova linguagem para mim em pouco tempo, paralelamente à sessão. No It-planet antes disso não participou.

Descrição da Competição

Posição geral

O IT-Planet é um concurso para estudantes e jovens profissionais da área de TI, cujo objetivo é identificar e dar suporte a indivíduos capazes. Realizado anualmente desde 2007. Participar é uma chance de provar a si mesmo.

A nomeação “Programação Java” ajuda a encontrar a aplicação prática do conhecimento adquirido no processo de aprendizagem.

A primeira etapa de qualificação foi realizada à revelia e foi um teste on-line para estudantes de instituições de ensino registradas. As perguntas eram bastante complicadas e interessantes, mas, para ser sincero, a maioria continha código que poderia ser relido e executado.

A segunda fase de qualificação, como a primeira, estava ausente. Destina-se a resolver problemas de programação esportiva. Foram dados dois dias para resolver 10 problemas, o que possibilitou a preparação completa para a solução de um problema específico, para o estudo do algoritmo / abordagem. No entanto, ninguém lidou com todas as tarefas. A condição de algumas tarefas mudou durante o concurso. Havia escolas nos testes.

Finais internacionais em período integral. Foi necessário escrever uma IA para o jogo "Ice Hockey". ~ 7 horas foram dadas. Aproximação devido à falta de “aprovação” do início e incompreensibilidade no almoço. O tempo era de borracha e o público não fechava, mas mais sobre isso abaixo.

Tarefa

A tarefa foi desenvolvida pelos especialistas da SimbirSoft LLC. Abaixo está o conteúdo do arquivo .pdf (com revisões mínimas para o artigo) que cada participante recebeu.

Critérios de avaliação

Também retirado de um arquivo .pdf. Somente o código da classe Algoritm será usado. O algoritmo de cada participante será executado contra todos os níveis de dificuldade, por sua vez. De acordo com os resultados da corrida, pontos serão definidos para os resultados da partida e pontos para as oportunidades implementadas no algoritmo também serão concedidos.

Corpo principal

Preparação para a competição

Ilya

Inicialmente, eles escreveram que na final haverá "Desenvolvimento industrial". Eu esperava um trabalho normal com a base, desenvolvimento da GUI. Um pedido de contabilidade, por exemplo. Com tristeza ao meio, concordei com a final, porque não estava muito feliz com o que tinha que fazer. No entanto, em 17 de setembro, chega uma carta com as regras para a final, e o seguinte é relatado aqui: “Existe um jogo 2D de computador“ Hockey ”no qual os bots de computador jogam de acordo com algum algoritmo. É necessário implementar um algoritmo na linguagem de programação Java, segundo o qual os caracteres dos participantes irão atuar “(foi escrito no site que a tarefa poderia ser alterada). Lembrei-me imediatamente da Taça da Rússia de 2014 na minha cabeça. Fiquei encantado e percebi que não foi em vão que concordei em participar.

A primeira coisa que fui mais uma vez foi ler o artigo do vencedor . Em geral, lembrei-me do que estava lá, mas nem todos os momentos eram claros. Depois fui ao site do concurso e li as regras. Eu parei com isso, porque qualquer alteração nas regras pode mudar completamente o jogo. Eu não sabia quantos físicos estariam em seu jogo, não sabia como a seleção de socos e pucks, etc. O jogo poderia ser bastante simplificado, pois nem os cantos seriam necessários. Então eu comecei a esperar ...

Esperou e esperou! Na tarde de 27 de setembro, chega uma carta sobre o webinar! 28 de setembro às 19:00. Foi um dia e hora perfeitos para mim. No entanto ... No entanto, 4 horas antes do lançamento programado, chegou outra carta com uma transferência para as 17:00! A carta de transferência chegou uma hora antes do início ... Voei o melhor que pude e fiquei atrasado por cerca de 15 minutos (não esperava que o Flash Player ainda tivesse que ser instalado).

No webinar, ele fez perguntas e obteve uma imagem geral do jogo. Havia dados suficientes, mesmo para escrever os meus e me preparar completamente. No entanto, até o último momento não ficou claro como o golpe ocorre, os desenvolvedores não divulgaram alguns pontos e, em alguns lugares, eles próprios ainda não haviam decidido até o fim.

Tendo anotado todos os itens mais valiosos, fui conversar com os membros ativos familiares da RAIC. Olá e obrigado m0rtido , DragoonXen , oreshn1k . Tendo esboçado a situação, ficou claro que é necessário codificar ifa e não pode falar sobre nenhuma simulação do mundo durante esse período. oreshn1k compartilhou o livro de bombardeios “Programming Game AI by Example”, cujo quarto capítulo falava sobre o design da IA ​​para o futebol. Gostei tanto do livro que decidi pintar para mim toda a estratégia que iria escrever na competição e esqueci completamente o prazo. O que eu ia escrever não era adequado para este concurso ...

Minha preparação inútil está disponível no quire (ordenadamente, já existem 168 tarefas. Em alguns lugares com uma descrição). Inútil para esta competição, mas em geral é uma excelente sistematização do conhecimento adquirido com o livro. Também pensei em simular o disco para descobrir sua localização depois de um tempo, encontrar o ângulo certo para o chute no gol, a lógica de transferir o disco entre os jogadores e várias coisas interessantes.

Eu já escrevi acima que sem a menor idéia de como escrever em Java, portanto, além da estratégia, comecei a estudar a sintaxe da linguagem. Isso foi ajudado por um excelente site, que venho usando há mais da primeira vez - Aprenda X em Y minutos . Depois de entrar no IntelliJ IDEA, percebi que escrever nele é exatamente o mesmo que escrever em C #.

Com essa preparação, fui a Moscou.

Anna

Quando soube do tema do final, a primeira coisa que decidi repetir foi o geoma. E para tornar tudo mais divertido e mais, fiz tudo com o Processing : observei exemplos de desenvolvedores relacionados ao movimento, calculando ângulos, velocidade e aceleração e depois pratiquei em meus pequenos esboços.

Decidi não perder tempo atualizando algumas sutilezas do Java, porque, a meu ver, a tarefa envolvia habilidades em escrever estratégias e algum conhecimento de matemática. Então decidi ler o artigo do vencedor do RAIC 2014 . O artigo foi interessante, mas não particularmente útil especificamente para este concurso, porque a física poderia diferir radicalmente e muito menos tempo seria concedido.

O webinar dos desenvolvedores foi interessante e útil, deu uma visão geral do jogo. Mas, infelizmente, eu não pude assistir completamente, porque a transmissão foi realizada usando Flash e meu laptop decidiu naquele momento jogar com a tela azul da morte.

Como resultado, pouco antes da final, eu não tinha uma estratégia definida com antecedência: era difícil planejar algo quando os detalhes da física do jogo não eram divulgados. Havia pensamentos sobre o que vale a pena prestar atenção, antes de tudo, que métodos auxiliares escrever imediatamente, mas não mais. Eu decidi que o principal antes do final era relaxar, dormir o suficiente e chegar lá de bom humor.

Leão

[Preparado] Cerca de 16 a 20 horas. Assim, considerei a geometria, com a qual, infelizmente, não estou muito em desacordo. Fórmulas e cálculos preparados com antecedência, testaram tudo. Apreciei a área da qual você pode marcar de acordo com as condições dadas pelos organizadores no webinar, depois escrevi um emulador de algumas ações e obtive como seria a área ao simular diretamente chutes de diferentes pontos e a estratégia ideal de goleiro. Como resultado, quase nada veio a calhar e eu tive que escrever muletas.

Distribuição de tempo

Ilya

Eu sempre tive problemas com a distribuição do tempo em competições e olimpíadas. Pisei em um ancinho pela terceira vez. Após o primeiro, ele disse que nunca permitiria isso. Mais uma vez, ele se sentou em uma tarefa, por muito tempo não mudou para outra.

Passei muito tempo, toda a primeira parte da competição antes do almoço, na implementação de todos os tipos de invólucros para jogadores de equipe, classes de estado, mensagens entre eles, funções internas. Em geral, realizei as tarefas que havia formado antes da competição, esquecendo completamente o conselho de participantes experientes sobre ifs de código rígido e métodos auxiliares. Ele simplesmente escreveu sem pensar no tempo.

Eu recuperei o juízo no jantar. Entendi que metade da competição havia terminado e tenho trabalho por mais 10 horas para que pelo menos algo comece a se mover. Foi decidido deixar tudo o que é e começar desde o início. Essas foram as últimas horas fascinantes da competição, quando parei de me sentir triste e ri com o comportamento dos meus bots. Muito rapidamente começou a mudar de tarefa para tarefa. Ele não vai lá - ele mudou para outro e depois voltou. Havia apenas um desejo - marcar pelo menos de alguma forma, pelo menos alguma coisa. Portanto, foi completamente esquecido sobre a limpeza do código e do POO, comentários interessantes foram deixados em alguns lugares.

Anna

No começo, decidi descobrir como os métodos básicos do jogo geralmente funcionam: o movimento dos jogadores de hóquei, a captura do disco, giros e passes. Passei cerca de uma hora nisso. Também estudei os dados e métodos que os jogadores de hóquei e o disco tinham. Então decidi que seria bom aprender a encontrar o ângulo entre dois objetos (em particular, entre um jogador de hóquei e um disco). Eu tive grandes dificuldades com isso: no começo, descobri o método Math.atan2 por um longo tempo e depois tentei converter os dados recebidos em um sistema de ângulos dos desenvolvedores. Com tudo isso, fiquei atormentado antes do jantar e fiquei muito chateado por ter passado muito tempo em uma pequena tarefa, embora durante o mesmo tempo eu pudesse escrever uma estratégia para pelo menos o primeiro nível.

Depois do almoço, decidi alocar tempo de maneira mais racional. Concluiu rapidamente o método com a determinação do ângulo e depois escreveu uma estratégia para o primeiro nível. Depois, passou suavemente para a estratégia do segundo nível, que aplicou no final ao terceiro. Na verdade, e seguindo a maneira como meus jogadores de hóquei se comportam estranhamente, eu o fiz até o final da final. O código acabou sendo terrível, ilegível, com um monte de ifs e copie e cole, mas mais ou menos lidou com sua tarefa: meus jogadores de hóquei marcaram gols.

Leão

Por um determinado período (7 horas, o que é incrivelmente pequeno para uma competição como essa), ele criou um algoritmo simples que foi capaz de vencer consistentemente 1-2 níveis com uma pontuação esmagadora. E então, dependendo de eventos aleatórios com um terceiro nível, o algoritmo emitiu uma pontuação de 0-2 a 6-0. Infelizmente, não foi possível olhar para o quarto nível. Ao mesmo tempo, tenho certeza de que, durante esse período, você pode escrever uma opção muito melhor, mas para isso precisa entender como funciona algum tipo de resposta, mas aqui os organizadores deram de ombros, dizendo que não entendemos por que isso é assim.

Na maioria das vezes, o tempo necessário para descobrir como e o que funciona no projeto fica enfurecido por não funcionar .equals () e dois campos .TypeOfPlayer e .PlayerType, que retornam coisas completamente diferentes. Bem, existem alguns comportamentos estranhos de jogadores que os organizadores realmente não conseguiram explicar (e não sabemos por que seu personagem está andando aqui de costas para o único time em questão, e os turnos já mencionados :)). Então, em algum momento, verifica-se que existem constantes no projeto para os tamanhos de diferentes objetos do jogo e suas posições, as quais, ao que parece, deveriam estar no material de referência inicialmente, mas não, no final, acabaram com o tempo para contá-las à mão.

Nossos batentes

Ilya

• Meu principal motivo é a terrível distribuição do tempo e a escrita fútil de abstrações supérfluas. Quando você tiver 7 horas, escreva um código incorreto e sem suporte, se quiser ganhar.
• Rofl com geoma. Ainda não sei qual ângulo deve ser adicionado e como o servidor o processa, então o% 360 está lá. Talvez 90+, talvez 180, talvez todos os 270. Eu não pensei sobre isso e coloquei em hipótese alguma ...
  
  

  double res = 180 / Math.PI * Math.acos((pp.x - tp.x) / pp.dist(tp)); return (90 + (int) res) % 360; 

• Cerca de 40 minutos antes do final da competição, decidi descobrir o jogo, que acontecia em busca do jogador mais próximo do disco. Aconteceu que o meu método squareDist da classe Paint tinha o sinal -, em vez de + entre os quadrados da diferença de coordenadas (a propósito, na tarefa de quire também). E com esse bug, considerei absolutamente todas as distâncias por várias horas ...
  
• No começo da competição, eu tinha em mente a realização de conseguir a posição de disco no futuro. Isso requer sua velocidade. Como se viu, nada útil pode ser obtido do estado do mundo (acho que é um batente de organizadores, contando com o que outros concursos dos mesmos formatos oferecem). Portanto, a mesma velocidade do disco teve que ser obtida, com base em sua posição em diferentes pontos do jogo. Passei muito tempo depurando e não entendi por que os dados são tão raros (prometidos a cada 5ms). Em geral, não consegui concluir o erro de cálculo na época, mas ~ uma hora antes do final da competição, notei um pedaço interessante de código em minha estratégia deixada pelos organizadores:
  
  

   try { Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); } 

  
  Definindo o valor para 10, recebi uma atualização muito frequente dos dados, descomentei a seção de código responsável pela obtenção da velocidade e funcionou! Cerca de 20 minutos depois, ouvi uma pergunta dos participantes dos organizadores sobre esse trecho de código, e ele explicou que isso foi feito especialmente para nós, para que fosse mais fácil o desenvolvimento. Naquele momento eu sorri, percebendo que eu não era a única que percebia isso tão tarde.

Anna

• Assim como Ilya, eu não era capaz de alocar corretamente meu tempo desde o início: gastei muito tempo em uma tarefa pequena, embora útil, mas tive que ensinar os jogadores de hóquei a marcar gols.
• Ela matou muito tempo porque esqueceu a assinatura do método Math.atan2: primeiro vem y e depois x. Eu fiz o oposto.
• Ao escrever um método que determina se há jogadores de hóquei inimigos em um determinado trecho do caminho, cometi alguns erros, por causa dos quais os jogadores de hóquei às vezes se recusavam a se mudar para qualquer lugar.
• No geral, a competição não foi levada a sério o suficiente. Alguém poderia se preparar com mais cuidado e ser mais diligente e atencioso no final.

Leão

• As primeiras duas horas nos logs repetiram aleatoriamente as duas vezes no comando dos aliados, em vez da segunda vez no comando dos bots.

Organizador Shoals

• Poucos dados para escrever estratégias fortes e confortáveis. Tudo o que nos foi dado foram quatro métodos para controlar e posicionar os jogadores em campo. Sim, o disco também tinha seu dono. A partir das constantes, o centro do campo, o goleiro e as áreas de gol estavam acessíveis. Obrigado por isso, mas parece-nos que a seguinte lista de valores era simplesmente necessária. Nós apenas os agarramos!
  
  
  1. Velocidade dos jogadores (cada papel tinha sua própria velocidade), discos;
  2. Informações sobre como diminuir o disco;
  3. Posições iniciais dos jogadores;
  4. Tamanhos de jogadores, discos;
• No webinar, os desenvolvedores disseram claramente que não havia como obter o código fonte do servidor. Sobre alguns empacotadores, foi dito que o .exe escorregaria. A palavra "ofuscação" não piscou, mas deu a entender. De fato, temos um .jar, que se decompila em alguns segundos e não apenas as constantes e a lógica com a física do jogo que os participantes não tinham se tornam disponíveis, mas também o código-fonte para o bot do terceiro nível jogando contra nós. Infelizmente, notei isso quando cheguei em casa e ouvi sobre a descompilação após o concurso dos participantes. Eles disseram como alguém o usou durante o final. Se isso é verdade, então é muito desagradável. Nesses momentos, você começa a se arrepender de que o caminho certo é tudo.
  

  Mas, neste caso, não é muito honesto (Alexander Polishchuk boba-alex ).

  Bem, muito bem que eles usaram, já que não havia proibição nas regras, mas eles decidiram não passar pelo ofuscador, por isso fazia parte da Olimpíada (Maxim Pyankov maxzxwd ).

  
  
• Jogadores de hóquei podem desaparecer aleatoriamente do campo e não aparecer até o final do jogo. Você pode empurrar o jogador para a área de goleiro.
  
  
• Ao chamar o método move (), o jogador de hóquei poderia ter virado na direção errada. Por isso, pode ser algo como um "passeio da lua".
  
  
  Vídeo

  
  
• O método turn () distribui os jogadores visivelmente mais devagar que o método move () para um determinado ponto (há uma virada automática na direção certa). Isso acontece, via de regra, em conflito com outro jogador de hóquei. Comparação de dois métodos:
  
  
• O ângulo de reflexão é ruim. Velocidade enorme depois de quicar nas laterais (o vídeo diminuiu 4 vezes). As arruelas não precisam, mesmo que ela estivesse na meta.
  
  
  Para comparação, um exemplo de passe em ângulo reto, no qual tudo é bom com velocidade e desaceleração.
  
  
  Vídeo

  
  
• O atacante do time inimigo ficou mais próximo do centro do campo e imediatamente interceptou o disco no início da rodada (o disco que não está no centro da textura do campo também é normal).
  
  
  
• A restrição "o goleiro só pode chegar ao meio do campo a partir do gol" se aplica apenas ao nosso time, não existe essa regra para os inimigos.
• Para que os jogadores de hóquei possam executar qualquer ação, primeiro você deve aplicar o método move () a qualquer uma delas;
  
• Os organizadores no código de estratégia deixaram um tempo limite, afetando a frequência de recebimento de novos dados. Se você simplesmente excluir esse código, tudo trava. Muitos não entenderam seu propósito e nenhuma explicação foi recebida dos organizadores. Nas regras também, essa parte do código não apareceu. Muitos estavam sentados em uma poça.
  
• Um grande número de participantes teve problemas com a construção e alteração do nível da estratégia (como se viu, poucas pessoas sabiam como trabalhar com a maven'om).
  
• No webinar, os organizadores disseram que o Java usará a versão 8, mas no final, o projeto precisava de um mínimo de Java 11.
  
• Anna: depois que me sentei em um computador em funcionamento, houve problemas com a compilação devido a espaços extras no código que quebraram o nome da variável. Não é crítico, mas não muito agradável.
  
• Em alguns computadores, inicialmente não havia arquivos de tarefas ou a Internet, e as dependências foram carregadas por um longo tempo.
  
• Havia mais participantes do que o esperado. Aconteceu por causa de algum tipo de extras. Portanto, uma pessoa com 13 anos teve problemas com a busca por computadores (alguns pegaram seus laptops) e começaram o projeto do zero.
  
• O almoço não foi estritamente regulamentado. Não deram um tempo para uma refeição, não fecharam o público. Pessoas famintas têm uma hora extra para vender.
  
• Acima, na descrição do concurso, há uma subposição com os critérios de avaliação. O problema deles é o que diz sobre os pontos, mas não está escrito quanto e para quê. Como resultado, tivemos opacidade e uma falta geral de entendimento sobre o que fazer para vencer.
  

  Provavelmente seria difícil comparar os participantes de perto, pois não havia atribuições claras de pontos para os recursos, havia apenas uma lista. Os participantes poderiam implementar características diferentes, mas, apesar disso, era necessário comparar de alguma forma (romano).

Conclusão

Conclusão

Em geral, se você parar de levar o final muito a sério, foi divertido, interessante e muito complicado. Sim, tive que gastar tempo não escrevendo uma estratégia, mas para lidar com os bugs dos desenvolvedores. Mas quando você se adapta e começa a seguir as regras deles, você começa a ter algum prazer com o processo. É claro que eu gostaria que os desenvolvedores adotassem uma abordagem mais responsável para essa tarefa e levassem o assunto ao fim sem fornecer aos participantes finais material bruto e inacabado.

Também é importante notar que os vencedores deste final são grandes companheiros: em condições tão difíceis e inesperadas, eles foram capazes de se reunir, descobrir tudo e emitir uma solução de alta qualidade. Respeito a esses meninos.

Agradecimentos

Antes de mais, gostaria de agradecer aos participantes que ajudaram a escrever o artigo e gentilmente concordaram em responder às nossas perguntas. Infelizmente, devido à mudança de direção, muito material não era necessário.

Agradecimentos a Anna ( odrus ), Leo ( zadamantiy ), Alexander ( boba-alex ), Maxim ( maxzxwd ), Ivan, Roman, Anna, Anna, Donat, Alexander.

Também gostaria de agradecer aos organizadores do próprio concurso IT-Planet, os organizadores da final do concurso “Programming: Java” SimbirSoft e, em particular, o desenvolvedor Eduard, que esteve presente nas finais e ajudou os participantes na criação de problemas, para esclarecer os momentos não óbvios na lógica do jogo.

Obrigado pelo fato de a competição não ter chutado, como aconteceu com o sisharp (Alexander).

A ideia do final foi boa, também nas eliminatórias (Ivan).

PS

Enquanto escrevia um artigo, chegaram as fotos do concurso e dos protocolos, o que significa que agora podemos anunciar nossos lugares!

Ilya cantou mais - 28-32 de 33
Anna - 16
Leo - 14

Obrigado por ler até aqui!