DEV Community

Michael Alves
Michael Alves

Posted on • Edited on

Implementando um Sistema de Ranking com Rating Elo em Ruby

Rating Elo e o filme A Rede Social

Um dos filmes que me fez querer entrar na área de tecnologia foi A Rede Social. O filme conta a história de como Mark Zuckerberg fundou o Facebook, eu descobri várias coisas legais com esse filme. A primeira delas foi que o melhor amigo do Mark era um brasileiro chamado Eduardo e esse brasileiro processou o Mark depois por ter perdido suas ações na empresa. A segunda coisa é que, antes do Facebook, dois irmãos tiveram a ideia de uma rede social para pessoas de Harvard, chamaram o Mark para desenvolver e, depois, esses dois caras também acabaram processando o Mark por plágio, Entre outras coisas, é um ótimo filme, com uma boa trilha sonora.

Nesse filme o Mark briga com a namorada, enche a cara de álcool e decide ter uma ideia bem canalha, que é hackear os Facebooks de Havard (Os Facebooks de Harvard eram diretórios digitais que consistiam em catálogos com as fotos, nomes, cursos e interesses dos calouros), pegar as imagens com os rostos das alunas e fazer um site onde ele compara qual aluna era "mais atraente" (Sim, isso foi bem bizarro e escroto). Nesse momento, ele pede ao seu amigo Eduardo para explicar qual algoritmo usar para fazer o ranking dessas garotas. Nesse caso, era o algoritmo que o Eduardo usava para ranquear os jogadores de xadrez. Daí temos a lendária cena da janela do quarto do Mark contendo a equação usada para gerar o ranking.

Tirando o fato de que essa equação foi usada para o mal, eu fiquei pensando se ela era real e por que foi usada para aquela finalidade de ranking.

Eu pedi para a IA ajustar a imagem para trazer com mais clareza a equação usada.

Apesar da imagem ter o expoente parecendo uma fração, a equação seria esta:

Pesquisando, eu descobri que isso se chama Rating Elo. Segundo a Wikipédia:

O Rating Elo é um método estatístico utilizado para calcular a força relativa entre jogadores de xadrez, inventado pelo físico americano Arpad Elo e utilizado no ranking da FIDE. O método funciona adequadamente quando utilizado da maneira que foi projetado, embora existam algumas limitações. O rating também foi adaptado para outros esportes, como, por exemplo, o tênis.

Porque usar essa equação para ranquear?

É uma boa pergunta. Vamos criar um modelo mental para visualizar melhor o problema. Digamos que temos que ranquear os melhores jogadores de xadrez.

Acredito que o modelo mental mais simples seria ranquear pelo número de vitórias.

Exemplo:

Jogador Vitórias
João 20
Maria 18
Pedro 5

À primeira vista, parece justo colocar João em primeiro lugar, já que ele possui mais vitórias.

Mas esse modelo possui um problema: ele considera apenas a quantidade de vitórias, ignorando a força dos adversários enfrentados.

Imagine que:

  • João venceu 20 partidas contra iniciantes.
  • Maria venceu 16 iniciantes e 2 mestres.
  • Pedro venceu 5 mestres.

Nesse cenário, as vitórias não possuem o mesmo valor.

Era esperado que um mestre derrotasse um iniciante, então as 20 vitórias de João trazem pouca informação sobre sua habilidade real. Por outro lado, as 5 vitórias de Pedro contra mestres são resultados muito mais difíceis e inesperados, indicando que ele provavelmente é mais forte do que seu histórico inicial sugere.

O sistema Elo foi criado para resolver exatamente esse problema: em vez de contar apenas quantas partidas cada jogador venceu, ele também considera a força dos adversários derrotados. Dessa forma, vencer um jogador forte vale mais do que vencer um jogador fraco, tornando o ranking muito mais representativo da habilidade real dos participantes.

Vamos implementar a equação 

ELO_DIVISOR = 400.00

def rating_elo(rating_player_a, rating_player_b)
  rating_players_result = (rating_player_b - rating_player_a) / ELO_DIVISOR
  1 / (1 + 10**rating_players_result)
end
Enter fullscreen mode Exit fullscreen mode

Explicando cada linha, o ELO_DIVISOR é uma constante em Ruby, usada para indicar que esse valor não deve mudar.

A próxima linha é o nosso método, def rating_elo. Esse método recebe dois parâmetros, que seriam equivalentes ao RA e ao RB.

Na próxima linha (rating_players_result = (rating_player_b - rating_player_a) / ELO_DIVISOR), calculamos a expectativa de pontuação dos jogadores, ou seja, a probabilidade de o jogador A vencer o jogador B.

Exemplo de uso (copie e cole o código no console Ruby, o IRB):

ELO_DIVISOR = 400.00

def rating_elo(rating_player_a, rating_player_b)
  rating_players_result = (rating_player_b - rating_player_a) / ELO_DIVISOR
  1 / (1 + 10**rating_players_result)
end

# Criamos variáveis para definir o rating inicial de cada jogador
rating_player_a = 1500
rating_player_b = 1900

# Usamos o método para calcular a probabilidade de vitória do jogador A
result = rating_elo(rating_player_a, rating_player_b)

# Pegamos apenas duas casas decimais para facilitar o entendimento do resultado
result.round(2)
Enter fullscreen mode Exit fullscreen mode

Resultado da execução:

irb(main):027> rating_player_a = 1500
irb(main):028> rating_player_b = 1900
=> 1900
irb(main):029> result = rating_elo(rating_player_a, rating_player_b)
=> 0.09090909090909091
irb(main):030> result.round(2)
=> 0.09
irb(main):031>
Enter fullscreen mode Exit fullscreen mode

Ou seja, o nosso jogador A tem apenas 9% de chance de ganhar do jogador B. Faz sentido, pois o rating inicial dele é menor.

Se invertermos a ordem, o jogador B terá 91% de chance de vitória.

irb(main):031> result = rating_elo(rating_player_b, rating_player_a)
=> 0.9090909090909091
irb(main):032> result.round(2)
=> 0.91
irb(main):033>
Enter fullscreen mode Exit fullscreen mode

Agora precisamos usar a fórmula Elo e, após isso, calcular o novo rating depois de uma partida. Para isso, precisamos definir o quanto o rating muda ao finalizar uma partida.

Para isso, vamos usar uma constante chamada K_FACTOR. Ela é o parâmetro que controla o quanto o rating vai mudar após uma vitória ou derrota.

Eu vou definir que o nosso K_FACTOR é 90 e também vou criar uma classe para os nossos jogadores, facilitando a atualização do rating.

ELO_DIVISOR = 400.0
K_FACTOR = 90

class Player
  attr_reader :name
  attr_accessor :rating

  def initialize(name, rating)
    @name = name
    @rating = rating
  end
end
Enter fullscreen mode Exit fullscreen mode

Agora precisamos adicionar a lógica do Elo com atualização de rating. Seguindo a lógica de uma partida normal, teremos atualização para vitória, derrota e empate.

def play(player_a_name, player_b_name, score_a)
  # Busca o jogador A no hash de jogadores através do nome
  player_a = @players.fetch(player_a_name)

  # Busca o jogador B no hash de jogadores através do nome
  player_b = @players.fetch(player_b_name)

  # Calcula automaticamente o resultado do jogador B

  # Exemplos:
  # Resultado de A   Resultado de B
  # 1.0 (vitória)   0.0
  # 0.5 (empate)    0.5
  # 0.0 (derrota)   1.0
  score_b = 1.0 - score_a

  # Calcula a expectativa de pontuação de A contra B
  expected_a = rating_elo(player_a, player_b)

  # Calcula a expectativa de B
  expected_b = rating_elo(player_b, player_a)

  # Atualiza o rating dos jogadores
  player_a.rating += K_FACTOR * (score_a - expected_a)
  player_b.rating += K_FACTOR * (score_b - expected_b)
end
Enter fullscreen mode Exit fullscreen mode

Basicamente, com o método play, nós decidimos o vencedor da partida ou se houve empate.

Exemplo de uso:

# Player A vence
ranking.play("Michael", "Angelica", 1.0)

# Empate
ranking.play("Michael", "Angelica", 0.5)

# Player A perde
ranking.play("Michael", "Angelica", 0.0)
Enter fullscreen mode Exit fullscreen mode

Por último, adicionamos um método para trazer o ranking dos jogadores ordenados.

def leaderboard
  @players.values
          .sort { |a, b| b.rating <=> a.rating }
          .each_with_index do |player, index|
    puts "#{index + 1}. #{player.name.ljust(8)} #{player.rating.round(2)}"
  end
end
Enter fullscreen mode Exit fullscreen mode

Agora adicionamos tudo em uma classe chamada Ranking e temos o código completo.

ELO_DIVISOR = 400.0
K_FACTOR = 90

class Player
  attr_reader :name
  attr_accessor :rating

  def initialize(name, rating)
    @name = name
    @rating = rating
  end
end

class Ranking
  def initialize(players)
    @players = {}

    players.each do |name, rating|
      @players[name] = Player.new(name, rating)
    end
  end

  def rating_elo(player_a, player_b)
    1.0 / (1 + 10**((player_b.rating - player_a.rating) / ELO_DIVISOR))
  end

  def play(winner_name, loser_name)
    winner = @players.fetch(winner_name)
    loser = @players.fetch(loser_name)

    expected_winner = rating_elo(winner, loser)
    expected_loser = rating_elo(loser, winner)

    winner.rating += K_FACTOR * (1 - expected_winner)
    loser.rating += K_FACTOR * (0 - expected_loser)

    puts "#{winner.name} venceu #{loser.name}"
    puts "#{winner.name}: #{winner.rating.round(2)}"
    puts "#{loser.name}: #{loser.rating.round(2)}"
  end

  def leaderboard
    @players.values
            .sort_by { |player| -player.rating }
            .each_with_index do |player, index|
      puts "#{index + 1}. #{player.name.ljust(8)} #{player.rating.round(2)}"
    end
  end

  def player(name)
    @players[name]
  end
end

ranking = Ranking.new(
  "Judit"    => 1900,
  "Angelica" => 1800,
  "Michael"  => 1600,
  "Maria"    => 1300,
  "Pedro"    => 1200,
  "Eric"     => 1100
)
Enter fullscreen mode Exit fullscreen mode

Legal, temos a equação funcionando. Agora podemos usá-la na prática para criar um pequeno sistema de ranking.

Ranqueando jogadores

Jogador Rating inicial
Judit 1900
Angelica 1800
Michael 1600
Maria 1300
Pedro 1200
Eric 1100

Esses são os nossos jogadores. Perceba que a Judit já começa com um rating inicial bem alto, provavelmente porque ela é uma boa jogadora e tem muita experiência. E temos o Eric. Vamos partir do pressuposto de que ele é um jogador promissor, porém teve poucas vitórias.

Rodada 1 — Grande surpresa

Vamos colocar o jogador Eric, último do ranking, para enfrentar o top 3 de jogadores: Judit, Angelica e Michael. E vamos dar a vitória para o Eric.

ranking.play("Eric", "Judit", 1.0)
ranking.play("Eric", "Angelica", 1.0)
ranking.play("Eric", "Michael", 1.0)
Enter fullscreen mode Exit fullscreen mode

O resultado foi:

1. Judit    1810.89
2. Angelica 1712.6
3. Michael  1522.1
4. Eric     1354.41
5. Maria    1300
6. Pedro    1200
Enter fullscreen mode Exit fullscreen mode

O que observar?

  • Eric ganha muitos pontos.
  • Judit perde muitos pontos.
  • Angelica perde muitos pontos.
  • Michael perde muitos pontos.

Por quê?

Era um resultado extremamente improvável.

Após enfrentar o top 3 e vencer, Eric subiu para a quarta posição do ranking. Ao mesmo tempo que a equação beneficia o jogador que se arrisca e enfrenta os melhores do ranking, ela também pune o jogador de alto nível que perdeu.

Vamos criar outras rodadas para elucidar os conceitos da equação.

Rodada 2 — Resultado esperado

Judit vence Pedro.

ranking.play("Judit", "Pedro", 1.0)
Enter fullscreen mode Exit fullscreen mode

Resultado:

irb(main):067> ranking.leaderboard
1. Judit    1813.49
2. Angelica 1712.6
3. Michael  1522.1
4. Eric     1354.41
5. Maria    1300
6. Pedro    1197.4
Enter fullscreen mode Exit fullscreen mode

O que observar?

  • Judit ganha poucos pontos.
  • Pedro perde poucos pontos.

Por quê?

O sistema já esperava que uma jogadora com rating 1810.89 vencesse um jogador com rating 1200.

Rodada 3 — Empate surpreendente 

ranking.play("Eric", "Judit", 0.5)
Enter fullscreen mode Exit fullscreen mode

Resultado

irb(main):069> ranking.leaderboard
1. Judit    1774.47
2. Angelica 1712.6
3. Michael  1522.1
4. Eric     1393.43
5. Maria    1300
6. Pedro    1197.4
=>
Enter fullscreen mode Exit fullscreen mode

O que observar?

  • Eric ganha pontos.
  • Judit perde pontos.

Mesmo sem vitória.

Por quê?

Empatar contra alguém muito mais forte já é melhor do que o esperado.

Conclusão

O sistema que implementamos aqui é uma versão simplificada do Rating Elo, mas já é suficiente para demonstrar o principal conceito por trás da fórmula: não basta contar vitórias e derrotas, também é necessário considerar a força dos adversários enfrentados.

Na prática, sistemas de ranking costumam ser bem mais sofisticados. Uma possível evolução seria tornar o K_FACTOR dinâmico, fazendo com que ele varie de acordo com o nível ou experiência do jogador. Jogadores novos poderiam ter um fator maior para que o sistema identificasse rapidamente sua habilidade real, enquanto jogadores mais experientes teriam um fator menor, deixando o ranking mais estável.

Outra possibilidade seria considerar o histórico de partidas do jogador. Alguém que mantém uma alta taxa de vitórias ao longo do tempo poderia receber ajustes diferentes de um jogador com desempenho inconsistente. Também poderíamos criar regras específicas para séries de vitórias, frequência de partidas ou até diferentes pesos para torneios.

O objetivo deste artigo não foi construir o sistema de ranking perfeito, mas entender a matemática por trás do Elo e implementar uma versão funcional do algoritmo. A partir daqui, existem diversas formas de aumentar a complexidade do modelo e adaptá-lo para diferentes tipos de jogos e aplicações.

Referências

Rating Elo

The Elo Rating System: A Data-Driven Approach to Ranking Competitor

Top comments (2)

Collapse
 
macchose profile image
Matheus •

Muito interessante o post 👏🏻👏🏻👏🏻

O sistema de pesos me fez lembrar um pouco o conceito de grafos ponderados onde diferentes rotas (adversários) podem impactar diretamente nos valores obtidos.

Também me fez recordar alguns jogos que experimentei à algum tempo onde existia um sistema de classificação (Elos prata, ouro, platina...). Jogar contra elos maiores te proporcionava mais pontos em vitórias e menos pontos em derrotas. Vitorias consecutivas podiam proporcionar um "salto" em sua classificação, principalmente em classificações iniciais.

Enfim, obrigado por compartilhar esse conhecimento. Tenho alguns projetos que envolvem rankings e esse conteúdo me deu um norte.

Collapse
 
michael_d_rei profile image
Michael Alves •

Que maneiro! vou estudar esse conceito de grafos ponderados, obrigado por comentar 😎