Estratégia / algoritmo para dividir equipes justas com base na história

20

Somos um grupo de pessoas jogando floorball juntos regularmente. Cada sessão começa com a difícil tarefa de dividir equipes ...

Então, o que seria melhor do que um aplicativo para escolher equipes automaticamente?

Portanto, dado um histórico de combinações de equipes e resultados e uma lista de pessoas que aparecem nessa sessão em particular, qual seria uma boa estratégia para encontrar as equipes ideais? Por ótimo, quero dizer equipes tão iguais quanto possível.

Alguma ideia?

Edit: Para deixar claro, os dados que eu tenho para basear a escolha seriam algo como isto:

[{ team1: ["playerA", "playerB", "playerC"],
   team2: ["playerD", "playerE", "playerF"],
   goals_team1: 10,
   goals_team2:  8 
 },
 { team1: ["playerD", "playerB", "playerC"],
   team2: ["playerA", "playerE", "playerG"],
   goals_team1:  2,
   goals_team2:  5
 },
 { team1: ["playerD", "playerB", "playerF"],
   team2: ["playerA", "playerE", "playerC"],
   goals_team1:  4,
   goals_team2:  2
 }]
Vegar
fonte
4
O que é floorball?
Dynamic
1
Presumo que você tenha apenas pontuações de equipe e nenhuma pontuação de contribuição individual?
Gort the Robot
1
@ Dynamic: Vou adivinhar que é outro nome para Floor Hockey - o hóquei jogado no chão do ginásio com uma pequena bola de borracha em vez de no gelo com um disco (e sem patins, é claro).
FrustratedWithFormsDesigner
2
Você pode esclarecer que a única informação a ser usada nesse algoritmo é quantas equipes vencedoras / perdedoras cada jogador esteve.
TehShrike
2
@TehShrike Para cada partida combinada, tenho informações sobre quem jogou em qual time e qual foi o resultado final. Por exemplo. {Equipe1: ["a", "b", "c"], Equipe2: ["d", "e", "f"], Pontuação: "10-5"}
Vegar

Respostas:

6

A primeira coisa a considerar, é algo casual. Não está projetando um sistema para determinar as rodadas da copa do mundo de bolas de chão. É para jogos casuais com um grupo de pessoas que gostam de um bom jogo, em vez de uma vitória desigual.

Lembro-me de algo do Google ter um gerador de chances de pebolim. Um pouco mais de trabalho foi feito nisso do que estou fazendo nisso. Procurando uma referência para isso, encontrei um artigo no SO e uma calculadora True Skill usada pela Microsoft para o xbox .

Adotando uma abordagem muito mais simplista, cada jogador obtém a pontuação da proporção de pontos que sua equipe tem no jogo. Para o jogo 1, o jogador A receberia 1,25 (10/8), enquanto o jogador D receberia 0,8 pontos (8/10). Encontre a média de todos os números e essa é a pontuação do jogador.

Para o conjunto de jogos descrito, isso fornece:

  A 1.42
  B 1.22
  C 0.72
  D 1.07
  E 1.27
  F 1.40
  G 2.50

Nesse ponto, você tem um problema semelhante ao do problema de partição com a restrição de que cada equipe precisa do mesmo número de jogadores e os valores não precisam ser exatos (mas o mais próximo possível).

Comunidade
fonte
Mesmo número de jogadores, ou tão perto como ele fica se ele aparece um número ímpar de jogadores ;-)
Vegar
Obrigado pela referência ao problema de partição ! Você é demais, @ user40980
Eric Gopak
3

Abordagem rápida e suja:

Calcule uma pontuação para cada jogador com o total de pontos do lado em que o jogador estava dividido pelo total de pontos no jogo para cada jogo em que participou. Em seguida, classifique os jogadores por pontuação. Coloque o primeiro jogador no time A. Em seguida, para cada jogador, adicione-os ao time com a menor pontuação agregada até a metade dos jogadores de um time. Todos os jogadores restantes vão para o outro time.

Gort the Robot
fonte
Essa abordagem pode funcionar, mesmo que a combinação de pessoas seja totalmente nova.
Vegar
Fazer melhor parece uma variante do problema da mochila . Os pesos também podem ser relevantes - da maneira que eu lembro, o jogador mais pesado (eu) sempre foi escolhido por último.
precisa saber é o seguinte
Esta abordagem ávido é conhecido por dar uma aproximação-3 4 / à solução óptima (Wikipedia)
Radek
3

Se você não quiser explorar o mundo inebriante dos anteriores Bayesianos (pdf) e tal, uma abordagem interessante é atribuir uma ordem total a todos os jogadores (com base na proporção de ganhos / perdas, pontos acumulados etc.) e depois dividir em equipes usando a função de paridade da seguinte maneira.

Pegue a lista ordenada de jogadores (do melhor ao pior) e separe-os em equipes Even e Odd com base no número de 1 bits em seu índice (começando em 0). Isso fornece a seguinte distribuição:

  • 0000 (melhor) - Par
  • 0001 - Estranho
  • 0010 - Estranho
  • 0011 - Even
  • 0100 - Odd
  • 0101 - Even
  • 0110 - Even
  • 0111 - Odd

... etc

A função de paridade garantirá um número igual de jogadores em cada equipe, para qualquer número par de jogadores. Ele será alternado, dando a vantagem do jogador de números ímpares a um time ou ao outro de tal maneira que os efeitos tendam a se equilibrar ao longo do tempo.

Esta função funciona melhor quando a distribuição da habilidade do jogador é plana. Na realidade, a habilidade do jogador tende a seguir a distribuição da "soma dos valores aleatórios", também conhecida como Gaussiana (embora tenha cuidado com as aplicações gerais dessa suposição em sistemas como o TruSkill).

Para compensar grandes lacunas de habilidades, você pode aplicar permutações a esta lista. Por exemplo, para contrariar um jogador de topo muito forte 0000, você pode trocar o jogador 0011 por um jogador impar de classificação mais baixa, como 0100. É aqui que as coisas ficam complicadas, mas pelo menos fornece um bom ponto de partida que não requerem uma medida precisa da habilidade absoluta, mas simplesmente uma ordem baseada na habilidade relativa.

Richard Nelson
fonte
2

Dependendo de quanto tempo você tem, inicie as primeiras sessões selecionando aleatoriamente os capitães das equipes e faça um rascunho antes de cada jogo. Acompanhe qual a escolha que um jogador escolhe. Escolhas anteriores obtêm classificações mais altas:

Round #1 = 8 pts, Round #2 = 6 pts, Round #3 = 4 pts, etc

Winning a game = 5 pts

Tudo isso dependerá do número de jogadores por equipe. O total de pontos pode precisar ser convertido para uma média diária ou de jogo, se houver uma grande discrepância na participação. Você também pode premiar uma equipe por uma maior margem de vitória.

Os jogadores que foram selecionados cedo e jogaram em um time vencedor obtêm mais pontos de poder.

Em seguida, deixe o computador fazer o desenho (seleção de equipes) equilibrando os pontos de poder de cada equipe e colocando equipes com classificações quase iguais entre si. Jogadores que são selecionados cedo, mas continuam jogando em times perdedores, cairão no ranking.

JeffO
fonte
Ótima resposta! Isso pode funcionar para a equipe média, mas algumas equipes são estratégicas. Por exemplo, se você quiser que toda a sua equipe seja defensora, terá jogadores em geral piores nas rodadas mais altas. Mas acho que não pedi canônico: P. Obrigado!
Dynamic
Essa é uma ótima maneira de começar. Nas primeiras rodadas, qualquer coisa com base na pontuação da equipe não será aplicada individualmente, pois você terá membros da equipe que jogarão juntos a cada rodada.
Gort the Robot
1

A solução mais fácil seria fornecer uma nota / peso da habilidade estimada e tentar equilibrar a pontuação de cada equipe.

A partir daí, você pode propagar uma rede bayesiana com esses valores e depois inferir para trás com base no resultado observado de cada comparação nos dados históricos que você possui.

Como um ponto de interesse da minha parte: o Infer.NET torna isso relativamente fácil de visualizar e potencialmente implementar, e pode prever as chances de uma vitória em virtude de confrontos de equipes. Infer.NET é algo em que estou começando a entrar ultimamente.

Steven Evers
fonte
Você teria dados suficientes para ser significativo, pois provavelmente haveria apenas alguns jogos?
Gort the Robot
Eu esperava resolver isso com javascript ou ruby, mas o infer.net parece interessante de qualquer maneira.
Vegar
@StevenBurnap: Depende de quão boas / precisas suas suposições iniciais são quanto à capacidade do jogador - o que você terá que fazer para a maioria ou todos os sistemas. O benefício de usar a rede é que você poderá inferir novas pontuações para cada jogador à medida que o tempo passa para melhorar esse valor.
Steven Evers
1

Suponhamos, para fins de discussão, que você pode atribuir a cada jogador um valor inteiro e esses valores se somam, ou seja, um jogador com pontuação X é tão valioso quanto três jogadores com pontuação A, B e C, se A + B + C = X. O objetivo é então separar o grupo em duas equipes, para que ambas tenham igual valor somado.

Esta é a versão de otimização do famoso problema de PARTITION, que é NP-complete. Portanto, seu problema é para todos que sabemos que é difícil de resolver. No entanto, PARTITION é fracamente NP-completo e admite algumas estratégias de aproximação razoáveis.

Um exemplo é uma abordagem gananciosa semelhante à proposta por Steven. Essa é uma aproximação de 4/3, ou seja, a equipe mais forte nunca é mais do que cerca de 33% mais forte do que uma divisão ideal.

Observe que você provavelmente tem restrições adicionais, como você precisa de pelo menos uma quantidade fixa de jogadores por equipe. Portanto, se você colocar Michael Jordan em uma turma de pré-escolares, não poderá criar equipes quase justas com número inteiro. Esse limite inferior (constante) do tamanho da equipe não deve afetar a dureza do problema subjacente, mas pode destruir os limites de aproximação válidos para o problema geral.

Rafael
fonte
1
Você não pode acomodar muitos jogadores em uma academia. Com até 20 jogadores, supondo que você queira 10 de um lado, existem apenas 92378 combinações para verificar. Mas não são necessários muitos jogadores antes que o número de combinações torne uma pesquisa exaustiva impraticável.
Kevin cline
@kevincline: Certo. Eu assumi implicitamente que a força bruta não era uma opção (caso contrário, por que perguntar?).
Raphael
Nunca haveria mais de seis pessoas em cada equipe. Mais frequentemente quatro.
Vegar 30/05
@Vegar: Então sua pergunta é mais como explorar as pontuações das equipes para modelar o valor do jogador e menos sobre os algoritmos, certo?
Raphael
1
A menos que você consiga descobrir uma maneira de realmente classificar as pessoas exatamente pelo seu talento, a precisão do algoritmo provavelmente não é tão importante. Com o problema em mãos, temos apenas a pontuação da equipe e algumas tentativas. Qualquer classificação de jogador será uma estimativa selvagem.
Gort the Robot
0

Quão ridículo você quer ser? Você sempre pode usar regressão linear múltipla para gerar coeficientes para cada jogador com base nas pontuações de suas equipes nos jogos anteriores. Em seguida, classifique a lista e selecione.

Na realidade, provavelmente não trabalho, uma vez que não modelar a dinâmica entre os jogadores, mas vai lhe dar uma razão para brincar com R . (<- veja, eu mantive a programação relacionada)

GrandmasterB
fonte
1
Estou pensando em fazer um aplicativo para evitar uma tarefa de 2 minutos duas vezes por semana, forçando-me a gastar quase a mesma quantidade de tempo registrando resultados para cálculos futuros. Acho que sim bastante ridículo ...
Vegar
-1

Se você deseja que seu algoritmo seja razoável, algoritmos simples simplesmente não serão suficientes. Eles geralmente fornecem resultados estranhos

Você precisará usar algo como o sistema ELO ou Trueskill (embora o ELO não funcione para equipes sem modificações).

catbert
fonte
1
Isso não é verdade. Tem que haver um algoritmo que funcione.
Dynamic