Imagine uma competição 1 contra 1 (não por equipes) entre robôs de IA, como o Google AI Challenge . Os vários bots recebem uma classificação ELO com base no resultado das várias partidas versus. O motivo pelo qual eu especifico os robôs de IA, pois eles podem competir 24 horas por dia, 7 dias por semana, sem levar em consideração a fadiga do jogador, a localização geográfica etc.
Dados os recursos limitados do servidor, apenas um número de sessões pode ser executado por dia. Estou procurando uma heurística (ou um algoritmo ideal) para escolher quais dois bots devem competir a seguir.
Todas as competições anteriores foram rastreadas. Com isso, quero dizer que o algoritmo tem mais com o que trabalhar do que apenas as classificações ELO.
Os casos de uso em que estou particularmente interessado:
- A competição está emparelhando aleatoriamente há algum tempo e agora quero tomar uma decisão inteligente de emparelhamento.
- A classificação Elo estabilizou e um bot é atualizado.
- As classificações da Elo estabilizaram e um novo bot é introduzido na competição.
Atualização:
preciso esclarecer. Não estou procurando um algoritmo que forneça correspondências justas. Estou procurando um algoritmo que encontre correspondências com maior probabilidade de atualizar as classificações Elo dos bots para as classificações "verdadeiras" com o menor número de correspondências.
fonte
Respostas:
Dado um sistema Elo normal, isso provavelmente não existe. Ele varia as pontuações com base na diferença entre uma pontuação esperada e a pontuação real, para que você possa ver que, se você formar pares de pessoas com a mesma habilidade, é provável que eles empatem (ou tenham 50% de chance de ganhar). não mudará, e se você juntar opostos completos, o veterano quase sempre derrotará o novato (como esperado), para que a pontuação também não mude.
A única coisa que provavelmente tornará uma pontuação do Elo menos precisa que a outra é ter jogado menos lutas. Isso significa que você deseja que eles joguem mais. Você ainda não possui nenhuma informação sobre o nível de habilidade real, portanto, o importante é fazê-lo entrar em lutas e começar a estabelecer esse nível.
Portanto, nessas condições, eu optaria por garantir que os bots jogassem o maior número possível de bots, escolhendo qualquer bot com o qual eles não tivessem competido antes e favorecendo a seleção de bots que não jogaram muito. Novos bots que ingressam no sistema devem ser favorecidos para estabelecer rapidamente seus níveis aproximados.
fonte
Sei que você já marcou uma resposta, mas, para ser honesto, é simplificado demais e realmente não aborda nenhum dos principais problemas de um sistema ELO, esteja você lidando com bots ou jogadores reais. Por exemplo, as principais considerações ao criar um sistema ELO justo / preciso seriam: número de jogadores, número de partidas, impacto relativo da habilidade (ou seja: chance) no resultado, eficiência nas partidas e quanta variação há na classificação por vitória /perda.
Em um mundo ideal, você seria capaz de combinar pessoas de habilidades iguais e, em um jogo de habilidades, elas atingiriam uma taxa de vitória de 50%. No entanto, isso pressupõe que você conhece a habilidade de todos e que o impacto do acaso é relativamente pequeno. Como você não conhece o primeiro (e não especificou o último), há várias coisas que você precisa fazer para determinar com precisão a habilidade de uma maneira eficiente e não é tão simples quanto jogar bots. muitos robôs diferentes quanto possível:
1) Você precisa configurar uma linha de base de habilidade para jogadores "novos" em uma escala de modo que eles possam subir ou descer e que a linha de base represente a média esperada em uma curva normal de sino. IE: 1250 em uma escala de 1-2500.
2) Os novos jogadores precisam jogar um certo número de jogos de "colocação", a fim de estabelecer sua classificação inicial, o que geralmente é feito em 10 a 20 jogos classificados mais fortemente que os jogos subseqüentes. IE: o ganho / perda na classificação é o dobro durante as colocações, o que seria mais tarde, a fim de incentivar a rápida separação dos jogadores.
3) Você precisa levar em consideração outros fatores nas suas partidas, como a taxa de vitórias em relação ao total de partidas, para que os jogadores em extremos da curva de habilidades sejam movidos em uma velocidade mais rápida à sua "verdadeira" habilidade, enfrentando pessoas mais acima ou abaixo sua classificação atual. IE: um jogador com uma taxa de vitória de 80% sobre um tamanho de amostra decente deve enfrentar as pessoas mais acima de sua classificação e subir a escada mais rapidamente do que alguém com uma taxa de vitória de 55% mais próxima de sua verdadeira habilidade.
4) Você precisa ter um bom entendimento de como o acaso afeta o resultado e deve levar em consideração a velocidade de criação de partidas (tempos de fila) ao determinar com quem combinar, a fim de manter a variação de habilidades razoável. Usando a escala anterior, você não deve ter um jogador de 1250 enfrentando um jogador de 2000 sob nenhuma circunstância (exceto quando os dois não tiverem classificação). Não é uma combinação justa e não permite adicionar / remover pontos com precisão do ELO.
A maneira como eu configuraria um sistema seria criar dois modificadores para um valor de ganho / perda de ponto base, um usando o resultado esperado com base na variação da classificação e outro com base na taxa de ganhos para o valor total correspondente. IE: alguém com uma classificação de 1500 que tem uma taxa de vitória de 70% que vence um jogador com classificação de 1600 ganhará mais pontos por ter uma taxa de vitória alta E por vencer um jogador com classificação mais alta.
Então, você só precisa garantir que os jogadores concluam uma amostra razoável de jogos e você terá o sistema "mais eficiente", com base em quanta chance está envolvida no "jogo" para o qual você está implementando o sistema ELO. Um jogo com chances relativamente baixas pode levar até algumas dezenas de jogos para ser preciso, um jogo com chances relativamente altas pode levar centenas ...
PS: para o registro, você não quer que pessoas com níveis de habilidade drasticamente diferentes joguem porque isso apenas dilui a precisão do sistema. Mesmo que você incline para que as partidas acima de uma certa variação tenham muito pouco impacto, isso criará problemas, porque os jogadores se sentirão não recompensados ou serão punidos excessivamente por partidas com alta variação.
editar: esqueci de abordar a parte "já classificada" da sua pergunta, mas é bem simples. Você combina as pessoas com base na classificação de habilidade mais próxima disponível na fila, porque essa é a correspondência mais equilibrada e o ganho / perda de pontos (assumindo taxas de vitória semelhantes) será o valor estático. Se os jogadores forem classificados com precisão, eles manterão a taxa de vitória de 50% e não subirão nem descerão. Se não estiverem , o jogador mais habilidoso ganhará mais do que perderá e sua classificação será atualizada.
A introdução de um novo jogador é ainda mais simples, eles começam na linha de base e são comparados aos jogadores dessa habilidade (com o aumento de ganho / perda) até que suas colocações sejam concluídas. Então, vamos supor que o ganho / perda de pontos normal por partida seja 15 sem nenhum modificador. Aqui está um exemplo de posicionamento e classificação de novos jogadores (com ganho / perda duplo):
fonte