SpawELO - um pequeno sistema gratuito de matchmaking para LAN parties
(blog.spawek.com)- Em uma LAN party de amigos que já dura 16 anos, ficou cada vez mais difícil escolher manualmente os times de Dota 2 a cada partida, então foi criado o SpawELO para automatizar essa seleção
- Por causa da diferença de habilidade e do número variável de participantes, o draft manual frequentemente gerava repetição de times parecidos e desequilíbrio quando havia um número ímpar de jogadores
- A primeira implementação usou 35 partidas anteriores e pontuações Elo para encontrar a combinação de times com a soma de pontos mais próxima, ajustando depois essas pontuações ao refletir repetidamente os resultados das partidas
- Depois de mudar para um modelo de previsão de taxa de vitória, os Elo dos jogadores passaram a ser ajustados com perda L2 e backpropagation, mas tratar todas as vitórias como 100% causou overfitting, fazendo o modelo decorar as partidas passadas
- A abordagem final trata os resultados das partidas como vitórias probabilísticas de 75% ou 95% para reduzir o overfitting e buscar um matchmaking que também funcione em formações ímpares, como 4v5
O problema da escolha de times em uma LAN party
- O grupo de amigos realiza uma LAN party pelo menos uma vez por ano há 16 anos, normalmente com duração de 4 a 5 dias, e nos horários de pico costuma ter cerca de 12 participantes
- O jogo principal é Dota 2, mas também jogam Counter-Strike, Wolfenstein: Enemy Territory, Warcraft 3 e Blobby Volley
- Os participantes chegam e vão embora em horários diferentes, e alguns até saem no meio para cuidar dos filhos, então cada partida não acontece sempre com o mesmo grupo de pessoas
- Em geral, Dota 2 é jogado em 5v5 e uma partida dura cerca de 40 minutos; jogos desequilibrados como 4v5 tendem a ficar puxados para um lado
- Dentro do grupo, há tanto pessoas que jogam Dota 2 regularmente quanto pessoas que só jogam durante a LAN party, então a diferença de habilidade é grande
As limitações do draft manual
- O método anterior normalmente colocava as duas pessoas mais habilidosas ou as duas menos experientes como líderes, que escolhiam os companheiros alternadamente, como numa aula de educação física
- A ordem de escolha funcionava assim: o primeiro líder escolhia 1 pessoa, o segundo líder escolhia 2, depois o primeiro líder escolhia 2, e no fim cada líder escolhia mais 1
- Era uma variação para reduzir a vantagem de quem escolhe primeiro
- Como a diferença de habilidade era grande, no fim acabavam surgindo com frequência times parecidos ou até os mesmos times, e a graça de fazer draft toda vez também diminuía
- A escolha manual dos times levava tempo e era trabalhosa, além de ninguém querer assumir o papel de líder
- Quando o número de pessoas não batia, o desequilíbrio entre os times ficava ainda maior
Primeira implementação: partidas anteriores e soma de Elo
- Quando a insatisfação com o processo de escolha de times aumentou na última LAN party, foi escrito rapidamente um código para automatizar isso
- Primeiro, foram reunidos dados de 35 partidas anteriores e colocados no Colab; cada partida continha a lista de jogadores do time vencedor e do time perdedor
- A ideia básica era calcular a pontuação dos jogadores com Elo rating
- Todos os jogadores começam com 1000 pontos
- Ao vencer, ganham pontos; ao perder, perdem pontos
- A taxa de vitória é calculada apenas pela diferença de Elo entre dois jogadores
- A primeira implementação simples somava 20 pontos para os jogadores vencedores e subtraía 20 pontos dos perdedores
- A composição dos times era gerada examinando todas as combinações possíveis dos jogadores solicitados e escolhendo aquela com a menor diferença na soma do Elo dos times
- No exemplo, 8 pessoas foram divididas em dois times, com um time calculado em 4100 pontos e o outro em 4080
Modelo de Elo aprimorado com cálculo iterativo
- Como passar pelas 35 partidas apenas uma vez parecia um aproveitamento ruim dos dados, os dados das partidas anteriores passaram a ser processados repetidamente várias vezes
- A atualização aprimorada do Elo não aplicava simplesmente ±20 pontos; em vez disso, usava uma estrutura em que se ganha mais ao vencer um adversário mais forte e se perde menos ao ser derrotado por um adversário mais forte
- Por exemplo, se Spawek com 1260 pontos vence Goovie com 900 pontos, ganha apenas 4,47 pontos
- Se Status com 900 pontos vence Dragon com 1100 pontos, ganha 30,38 pontos
- Como o cálculo era feito por time, e não individualmente, usava-se a soma do Elo do time vencedor e do perdedor, e os pontos de atualização eram distribuídos igualmente entre os integrantes
- Esse método também foi usado durante a própria LAN party, permitindo adicionar novos dados após cada jogo e remontar os times para o restante do evento
- Quando às vezes surgia uma partida claramente desequilibrada, era adicionada aos dados uma “partida falsa” com o vencedor esperado, e então os times eram gerados novamente
Segunda melhoria: mudança para um modelo de previsão de vitória
- A melhoria seguinte passou a tratar o Elo não como uma tabela de pontuações, mas como um modelo para prever a taxa de vitória entre times
- O modelo armazena o Elo de cada jogador e calcula a probabilidade de vitória comparando
SUM(Elo)dos dois times - Aos dados completos das partidas foi aplicada uma perda L2 simples
- Calcula-se a soma do Elo do time vencedor e do time perdedor
- Calcula-se a probabilidade de vitória
- A diferença entre a probabilidade real e a prevista é elevada ao quadrado e somada como perda
- O treinamento usou backpropagation
- Na propagação para frente, calcula-se a taxa de vitória prevista
- Com a perda e a derivada da função de taxa de vitória, calcula-se como o Elo de cada jogador afeta a perda
- Os valores de Elo são atualizados com
LEARNING_RATE = 10_000.0eITERATIONS = 10001
- Essa abordagem conseguiu reduzir a perda, mas os valores de Elo não convergiam
Resultados probabilísticos para reduzir overfitting
- O modelo no estilo ML sofria overfitting porque tratava todas as taxas reais de vitória das partidas passadas como 1.0, ou seja, vitória de 100%
- Em vez de generalizar, o modelo decorava cada partida, e em alguns casos a probabilidade prevista de vitória chegava a algo como 0.999994567526197, praticamente 1
- Como o objetivo não era codificar exatamente os resultados passados, mas montar bons times, a abordagem foi alterada para usar resultados probabilísticos em vez de vitórias e derrotas absolutas
- Após revisar melhor os registros das partidas anteriores, as partidas foram divididas em dois tipos
- Partidas equilibradas passaram a ter a taxa real de vitória do time vencedor fixada em 75%
- Partidas claramente inclinadas para um lado passaram a ter a taxa real de vitória do time vencedor fixada em 95%
- A diferença de Elo necessária para uma taxa de vitória de 75% é de cerca de 200 pontos, enquanto para 100% fica numa faixa de aproximadamente 500 pontos até infinito, o que dificulta que o modelo memorize todas as partidas
- Depois de trocar
real_probability = 1porreal_probability = game["win_probability"]nas funçõeslossebackpropagation, a perda caiu rapidamente e o Elo dos jogadores também convergiu para níveis razoáveis
Montando lineups mesmo com número ímpar de jogadores
- O novo sistema consegue prever a probabilidade de vitória e montar times mesmo com número ímpar de jogadores
- Um exemplo da primeira lineup da LAN party que começa em duas semanas é o seguinte
- team 1: Elo 2660
- team 2: Elo 2655
- A lineup de exemplo tem uma formação com 4 jogadores de um lado e 5 do outro
- team 1: Spawek, Bixkog, Bania, Goovie
- team 2: Hypys, Muhah, J, Vifon, Status
1 comentários
Comentários do Hacker News
Tenho curiosidade se alguém já usou, em jogos baseados em equipes, uma abordagem que não seja baseada em Elo/TrueSkill
Somar ou tirar a média do Elo da equipe para fazer matchmaking parece uma solução improvisada que força um modelo de matchmaking individual a caber em matchmaking de equipes
Além disso, perde-se muita informação de compatibilidade interna da equipe, como A e B jogarem juntos mais fortes do que a soma dos Elos individuais, enquanto A e C juntos ficam mais fracos
Nos esportes, mesmo que uma equipe perca, ainda podem surgir All-Stars ou MVPs ao fim da temporada; por outro lado, alguém pode estar no time campeão sem ser peça central
Em e-sports de equipe, tudo depende da vitória, então a expressão de jogadores como defensores, atacantes ou suportes de elite da liga inteira não é bem acompanhada nem reconhecida
Seria preciso acompanhar e refletir, em alguma medida, métricas avançadas, como em vários esportes. Um jogador não é o Elo em si, mas algo mais próximo de assistências por jogo, rebotes, pontos, RBIs, jardas etc.
Assim ficaria fácil ver se uma equipe precisa mais de pontuação ou mais de defesa, então o matchmaking também poderia se ajustar de forma mais natural do que “precisa de mais vencedores/perdedores”
O ponto forte do Elo é a grande quantidade de informação obtida pelo custo. O essencial é ser um único número que representa tudo
Ele não explica perfeitamente a bela diversidade da natureza, mas é próximo da abstração mais eficiente que contém 70% do que é preciso saber sobre a habilidade do adversário
Seria bom ter um vetor multidimensional de habilidade do jogador ou embeddings que contenham mais informações, além de modelos mais não lineares por cima disso
Por exemplo, em muitos jogos uma equipe normalmente precisa de um jogador de suporte, mas um único número não é suficiente para incluir essa informação no matchmaking
Por exemplo, no pebolim há jogadores que jogam tanto simples quanto duplas, e dois defensores excelentes no mesmo time podem perder para adversários mais fracos que se encaixam melhor em cada posição
Jogos em que a equipe consegue dar bastante suporte, como Counter-Strike, Apex, Overwatch e, em certa medida, Dota, também são diferentes. No Counter-Strike, um colega fraco, sem habilidade suficiente ou sem headset, pode arruinar o jogo inteiro; já no Overwatch, ele pode escolher uma classe de suporte, ficar mais atrás e esperar o resto da equipe vencer
Também existe química. Como se vê no trabalho, sinergias que surgem apenas em certas combinações, ou simples diferenças de estilo de jogo, podem mudar o resultado
Mesmo em variantes que parecem parecidas, como no bilhar, um jogador pode brilhar em uma modalidade e não se sair bem em outra
Parece que havia, ou ainda há, uma competição de sistemas de rating no Kaggle
https://www.kaggle.com/competitions/chess/discussion/107
Existem vários sistemas de rating com desempenho melhor que Elo
Para torneios, gosto do sistema suíço, que pelo que sei é popular no xadrez
[1]: https://en.wikipedia.org/wiki/Swiss-system_tournament
No formato suíço, com 6 rodadas, cerca de 40 pessoas é o máximo adequado; para convidar mais de 100, é preciso usar uma chave de eliminação após 2 derrotas. Caso contrário, o torneio leva uma semana
O melhor é o custo-benefício. Independentemente do resultado, você continua jogando durante todo o torneio e, conforme ele avança, os adversários ficam ajustados ao seu nível, então todo mundo consegue se divertir
Não sei bem como se decide quantas rodadas devem ser jogadas, mas não sei se esse detalhe é o ponto central
Pela parte de análise, comparado a um torneio eliminatório, assumindo que não haja empates, o número de rodadas necessário para determinar um vencedor claro é o mesmo que no mata-mata
A vantagem do sistema suíço é que ninguém é eliminado, e a classificação final mostra, em certa medida, a habilidade relativa de todos os participantes, não apenas do vencedor
Porém, se um jogador abrir uma vantagem grande demais, o título pode já estar decidido antes da última rodada, então nem sempre termina com um desfecho dramático
Fico me perguntando se valeria tentar o valor de Shapley
Isso é praticamente a introdução da Wikipedia, mas mesmo lendo eu não entendi bem. Fico me perguntando o que seria o excedente total de um jogo cooperativo aqui: seria algo como a quantidade de madeira coletada pela equipe em AoE?
Também não entendo como “distribuir” isso ajudaria; parece que isso deveria ser o resultado do jogo. Seria bom se alguém pudesse explicar de forma simples