Como o balanceador de equipe funciona no World of Tanks Blitz

O WoT Blitz é um jogo de tiro em tanque móvel, no qual os jogadores lutam no formato 7 contra 7.
Um matchmaker, ou equilibrador, é um mecanismo que, com base na formação de jogadores que desejam entrar na batalha, forma a composição dos times.

Os tanques têm os seguintes parâmetros importantes para a criação de partidas:

• Nível. Dependendo do nível, as diferentes características dos tanques mudam (por exemplo, velocidade, penetração da armadura). No 1º nível - os tanques mais fracos, no 10º - os mais fortes.
  
• Tipo Existem 4 tipos de tanques no WoT Blitz: destruidores leves, médios, pesados ​​e tanques (artilharia autopropulsada antitanque)
  

A implementação mais simples de um casamenteiro é jogar jogadores aleatoriamente nas equipes. Mas neste caso, jogadores de níveis baixos não terão chance de causar pelo menos algum dano, e será desinteressante jogar.

Exigências

A lista de requisitos para o balanceador foi formada com base no feedback da comunidade de jogadores e é atualizada periodicamente até hoje.

No momento da redação do artigo para batalhas regulares, a lista consistia nos seguintes itens:


Desenvolver um casamenteiro, especialmente considerando esse número de restrições, é uma tarefa muito interessante. E as abordagens para sua solução podem ser bastante.

Balanceador formando um par de jogadores

Inicialmente, em tanques móveis, foi utilizado um balanceador, que ele herdou de seu irmão mais velho - os tanques de mesa. Em geral, ele trabalhou muito bem, mas teve vários problemas: primeiro, não deu garantias claras para atender aos requisitos; segundo, adicionar novos requisitos foi bastante difícil.


Início da batalha

Portanto, outro balanceador foi escrito, que funcionou de acordo com o seguinte algoritmo:

• Dividimos jogadores em grupos de acordo com o nível e o tipo de equipamento;
• Dos jogadores resultantes, formamos pares;
• Nós dispersamos pares para equipes diferentes: pegamos cada par, jogamos o primeiro jogador no primeiro time, o segundo no segundo;
• Nas equipes recebidas, fazemos o reequilíbrio final: para satisfazer a maioria dos requisitos, substituímos alguns jogadores de uma equipe por jogadores de outra equipe.

O balanceador resultante trabalhou 5 a 10 vezes mais rápido que a versão anterior e inicialmente montou equipes que atendiam a todos os requisitos naquele momento. Novas regras foram adicionadas escrevendo passes de reequilíbrio adicionais.

No começo, tudo funcionou bem. Mas com o tempo, quanto mais regras foram adicionadas, mais difícil foi escrever o reequilíbrio. Como resultado de seu trabalho, o novo reequilíbrio não deve interromper o trabalho dos anteriores. Tornou-se claro que este é o caminho para lugar nenhum.


Bug no matchmaker - uma equipe 9 contra 9 reunida

Balanceador de recozimento simulado

Na versão final, escolhemos um balanceador que funciona de acordo com o seguinte algoritmo. Todos os jogadores que clicam no botão "To Battle" caem na fila geral. Um balanceador de loop infinito faz o seguinte:

• Seleciona parâmetros de batalha aleatórios (nível de batalha aleatória (de 1 a 10), modo aleatório, mapa aleatório);
  
• Encontra na fila todos os jogadores que atendem aos critérios selecionados acima (entraram em batalha em um tanque de nível adequado, ativaram o modo selecionado, carregaram o mapa selecionado);
  
• Tentando formar equipes que atendam a todos os requisitos acima (descrição abaixo);
  
• Se fosse possível formar uma equipe, jogue esses jogadores para fora da fila de espera e a batalha começará.
  

Para formar equipes da lista de jogadores adequados, é usado o método de simulação de recozimento. Leia mais sobre o método em si aqui .


Procure um máximo global simulando o recozimento

No contexto da aplicação à formação de equipes, o algoritmo é o seguinte:

• Começa com duas equipes vazias;
  
• A cada iteração, altera aleatoriamente o estado dos comandos. Para fazer isso, execute uma das seguintes operações:
  
  
  • Adiciona um jogador aleatório da lista de jogadores adequados ao primeiro ou ao segundo time (também escolhemos um time aleatório);
    
  • Remove um jogador aleatório de um time aleatório;
    
  • Substitui um jogador aleatório da lista de jogadores adequados por um jogador existente no primeiro ou no segundo time;
    
  • Muda um jogador aleatório do primeiro time para um jogador aleatório do segundo time.
    
  
  
• Obtém uma estimativa do estado resultante. Para fazer isso, chama a função de avaliação. A função percorre a lista de requisitos e a violação de cada item aumenta a penalidade. Quanto mais forte o ponto for violado, maior será a penalidade. Por exemplo, a penalidade para um time 2x2 será maior que a penalidade para um time 6x6;
  
• Dependendo da mudança no valor da função estimada e da temperatura atual, determinamos a probabilidade de uma transição para um novo estado;
  
• Continuamos o processo até que a temperatura atinja o valor mínimo definido ou o valor da função de avaliação atinja zero (nesse caso, todos os requisitos são atendidos e a batalha pode ser iniciada).
  

A principal vantagem dessa abordagem: para adicionar novos requisitos, basta modificar a função de avaliação. Não há necessidade de escrever código que descreva como obter exatamente o que queremos. Basta adicionar uma regra que olhe para a equipe formada e diga se ela está bem equilibrada ou não.

Um bom exemplo de adição de tais regras são as batalhas de classificação. Nas batalhas de classificação no casamenteiro, várias novas regras apareceram ao mesmo tempo:

• As equipes devem ser equilibradas em termos de classificação (a diferença na classificação total de jogadores entre equipes não deve exceder um determinado valor);
  
• A diferença de classificação entre os jogadores deve ser mínima (jogadores da liga de bronze não devem brigar com jogadores do diamante).
  

Exemplo de perfil de jogador de Diamond League

A primeira regra é implementada modificando a função de avaliação: uma penalidade foi adicionada por exceder a diferença máxima permitida na classificação. A segunda regra é implementada alterando a função que puxa jogadores adequados da fila.

A desvantagem dessa abordagem é a velocidade lenta. Comparado com a versão anterior, a atual começou a trabalhar cerca de 10 vezes mais devagar, apesar de várias otimizações. A propósito, sobre otimização. A maior parte do servidor (exceto rede e física) do jogo é escrita em Python. O balanceador foi reescrito em C ++ e paralelo a muitos threads. Do Python, uma solicitação para formar um comando chega no código positivo. Além disso, cada um dos fluxos inicia independentemente o método de recozimento. Assim que algum segmento encontra uma solução, o restante dos segmentos interrompe o processo de pesquisa e a solução encontrada é retornada ao Python.


Tempo de espera e tamanho da fila no servidor RU (5 segundos em batalhas normais e 10 em batalhas de classificação)

À medida que o crescimento online cresceu, também aumentou a carga no balanceador. No outono, quando o servidor on-line no servidor da RU atingiu 120 mil (durante o evento Mad Games), o balanceador deixou de lidar. Como medida temporária, desativamos algumas regras, o que nos permitiu reduzir a carga. Para evitar esses problemas no futuro, distribuímos o casamenteiro.

Sistema de classificação

Os melhores jogadores da liga de diamantes, 21 de abril de 2019

Em muitos jogos MMO, além de lutas aleatórias, também existem classificações / classificações / etc. A principal idéia deste modo: os oponentes não são procurados aleatoriamente, mas adequados em habilidade. Se você é um jogador de habilidades, jogará com os mesmos jogadores de habilidade e vice-versa, se não souber jogar, será confrontado com os mesmos novatos.

No início da temporada, o jogador passa por uma série de lutas de calibração, cujos resultados determinam sua posição inicial. Então, dependendo do sucesso do jogo, o jogador sobe ou cai no ranking. O sistema de classificação em Blitz foi criado, antes de tudo, para o equilíbrio adequado. É aprimorado na habilidade dos jogadores e é praticamente independente do número de jogos disputados.

Para implementar batalhas de classificação, foi necessário resolver dois problemas ao mesmo tempo. Em primeiro lugar, era necessário escolher um sistema de classificação (por que princípio os jogadores deveriam ser classificados). Em segundo lugar, foi necessário refinar o balanceador para que ele colecionasse brigas, levando em consideração as restrições de classificação.

O principal requisito para o sistema de classificação é a capacidade de determinar com precisão o nível do jogador. Para avaliar com que precisão um ou outro sistema de classificação funciona, foi criado um simulador, na entrada da qual foram submetidos o histórico de batalhas e o sistema de classificação selecionado e, na saída, a precisão do sistema foi obtida.

A precisão foi calculada da seguinte forma:

• Todos os jogadores receberam uma classificação inicial;
  
• Com base nos resultados de cada uma das batalhas, a classificação dos jogadores participantes dessa batalha foi recalculada de acordo com o sistema selecionado;
  
• Antes de cada batalha, o sistema tentava prever qual time venceria;
  
• Como resultado, foi calculada a porcentagem de batalhas para as quais o sistema forneceu a previsão correta.
  

Os sistemas de cálculo de classificação mais populares: winrate, Elo , Glicko , TrueSkill . Winrate é a porcentagem usual de vitórias. Elo é um sistema de classificação, originalmente criado para jogos com duas pessoas (xadrez, etc). Neste sistema, um jogador recebe / tira um certo número de pontos por vencer / perder, dependendo da classificação do oponente. O Glicko geralmente é semelhante ao Elo, mas também leva em consideração o tempo que o jogador está inativo. TrueSkill é um sistema de classificação proprietário da Microsoft, no qual cada jogador possui dois parâmetros: classificação e confiança do sistema nessa classificação.

Durante o desenvolvimento da primeira versão das batalhas de classificação, consideramos winrate e Elo (várias opções adaptadas para um jogo em equipe), bem como um sistema de pontuação simples (no qual os jogadores sempre recebiam um número fixo de pontos de classificação por vitória e eram levados para derrota).



Os melhores resultados foram mostrados pelo sistema Elo, no qual Ra é a classificação do jogador e Rb é a diferença entre a classificação total da equipe adversária e a classificação total da equipe do jogador, com exceção do próprio jogador.

As principais dificuldades que encontramos após o lançamento:

• muita variação no ranking entre jogadores;
  
• a velocidade pouco previsível em que os jogadores marcam (alcançam a liga).
  

O primeiro problema não pôde ser completamente resolvido devido ao fato de haver poucos jogadores de habilidade, eles precisam esperar muito tempo antes do início da batalha e, muitas vezes, vêem os jogadores em suas equipes mais fracos. Para atenuar o efeito, disponibilizamos batalhas de classificação apenas no horário nobre (ou seja, no momento em que o número máximo de pessoas estava jogando nos servidores).

Resolvemos o segundo problema introduzindo um fator de lentidão (ou seja, quanto mais longe o jogador está da classificação média, mais difícil é para ele subir ou descer abaixo).

Também tentamos de várias maneiras melhorar a qualidade do sistema de classificação. Nas primeiras versões, para alterar a classificação, usamos apenas informações sobre vitória / derrota. Mas temos um jogo em equipe, e nem sempre as boas ações de um jogador específico levam à vitória de todo o time. Ou seja, mesmo se o jogador jogou bem e o time perdeu, esse jogador recebeu o mesmo menos na classificação que todos os outros jogadores. Para evitar isso, começamos a tentar levar em consideração as ações individuais do jogador em batalha.

Para esses fins, tentamos usar o aprendizado de máquina: coletamos vários fatores e tentamos treinar o modelo para prever a vitória / derrota do time de acordo com as ações do jogador na batalha, e depois usar esse modelo para determinar o coeficiente de bônus de classificação (ou seja, se o time perdesse, mas o comportamento do jogador fosse semelhante) sobre o comportamento dos jogadores vencedores, dê a esses jogadores um bônus adicional).


O jogador da equipe vencedora que jogou bem recebeu +40 de classificação. E o que é ruim, apenas +10

Conseguimos construir um bom modelo que apresentasse resultados muito melhores que o atual, mas havia uma dificuldade (que muitas vezes estraga tudo em problemas de aprendizado de máquina). O modelo era bom, mas às vezes apresentava erros claramente visíveis para as pessoas. Periodicamente, havia situações em que um jogador que, do ponto de vista de uma pessoa apresentava bons resultados, recebia um bônus baixo do ponto de vista do modelo e vice-versa.

Como resultado, abandonamos o modelo ML e adotamos uma fórmula manual mais simples. Esta fórmula leva em conta apenas a experiência de combate sem levar em consideração os bônus pela vitória, x2 e outros. Dá um resultado muito decente, embora seja um pouco menor que o do modelo ML.

Conclusão

• Um balanceador baseado em um método de simulação de recozimento nos permitiu passar de uma descrição da solução (como montar a equipe) para uma descrição dos requisitos (quais condições não devem ser violadas);
  
• Nas batalhas de classificação de equipes, o sistema Elo modificado mostrou-se bem, levando em consideração as ações individuais do jogador na batalha;
  
• Nem sempre vale a pena usar métodos complexos de aprendizado de máquina (especialmente quando a interpretabilidade e a compreensibilidade do resultado por uma pessoa são importantes).
  

Continuamos a desenvolver e melhorar o balanceador. Quase derrotamos a impressão negativa do desequilíbrio de classe. Os principais problemas que nossos jogadores prestam atenção são o desequilíbrio na habilidade, turbulência e jogadores afk. Este é um desafio sério, continuamos a trabalhar em um balanceador nessas áreas.

Se você tiver alguma dúvida / sugestão sobre um balanceador no WoT Blitz, cancele a inscrição nos comentários (ou em nosso fórum ).