Back-End

6 dez, 2016

Jogos, rankings, a Rede Social, League of Legends e Ruby?

Publicidade

Há um segmento em uma série de palestras que eu tenho apresentado no Brasil nos últimos três anos sobre o qual eu nunca escrevi aqui. Recentemente, eu publiquei sobre a maneira correta de classificar o conteúdo por “popularidade”, então eu pensei que deveria revisitar o tema.

Para começar, eu acredito que por agora a maioria das pessoas já assistiu ao filme “The Social Network” (A Rede Social). É interessante que eu ouvi muitas pessoas dizendo como esse filme os influenciou a começar suas próprias startups. Então eu estava pensando, “o que esse filme realmente ensina?”.

1

Bem, a partir do filme, aprendemos que David Fincher é um diretor fantástico, que Aaron Sorkin escreve um diálogo muito forte que é muito atraente, que Justin Timberlake faz um Sean Parker melhor do que o real, que Andrew Garfield faz um Eduardo Saverin “ok” e que Jesse Eisenberg será para sempre Mark Zuckerberg.

E é isso, não podemos aprender mais nada com o filme.

Ou podemos?

Facemesh

Uma das minhas cenas favoritas do filme é quando Zuckerberg/Eisenberg está chateado pela separação de Erica Albright, e ele começa a demolir fotos femininas dos sites de Harvard e a organizá-las em um site de troll chamado “Facemesh”, onde ele as coloca para competir. As pessoas podem votar em qual foto elas preferem e as classificam em um ranking de popularidade.

Quando Eduardo Saverin/Andrew Garfield aparece, Zuckerberg pergunta a ele:

“Wardo, eu preciso de você (…) Eu preciso do algoritmo usado para classificar os jogadores de xadrez”.

E ele vai em frente e escrever o seguinte na janela dormitório:

2

Aqui a maioria das pessoas pensaria:

pff, outra fórmula de jargão/linguagem sem nexo apenas para exibir que eles são pequenos gênios, mas é quase certo que esta fórmula sequer existe.

Só que sim, existe. E essa é a única cena no filme que ficou em minha cabeça. Para ajudá-lo, vamos inverter a imagem espelhada:

3

E esse é o “algoritmo”.

Como eu disse no meu artigo anterior, a maioria dos desenvolvedores criaria um site similar ao Facemesh adicionando campos integrais à tabela de concorrentes com a contagem de upvotes/votos favoráveis e downvotes/votos contra, e eles fariam algo bobo como isto:

score = upvotes - downvotes

Ou ainda mais bobo:

score = upvotes / (upvotes + downvotes)

E isso não funciona dessa forma, você vai obter rankings muito errados.

A demonstração

Para te mostrar o quão errado, eu criei um projeto de demonstração simples chamado elo_demo, que você pode clonar e executar sozinho.

Ele vai criar 2.000 partidas aleatórias contra 10 jogadores. Estes serão os resultados ordenados se usarmos os métodos errados de subtrair perdas de vitórias e ordenarmos através desse resultado:

   Name        Games  Wins  Losses Points (wins - losses)
 1 Kong          217   117    100     17
 2 Samus         211   110    101      9
 3 Wario         197   102     95      7
 4 Luigi         186    95     91      4
 5 Zelda         160    81     79      2
 6 Pikachu       209   105    104      1
 7 Yoshi         223   112    111      1
 8 Mario         203   101    102     -1
 9 Fox           208    95    113    -18
10 Bowser        186    82    104    -22

Agora, vamos fazer o 2º lugar Samus vencer 10 vezes seguidas contra o 3º lugar Wario; este é o novo ranking:

   Name        Games  Wins  Losses Points
 1 Samus         221   120    101     19
 2 Kong          217   117    100     17
 3 Luigi         186    95     91      4
 4 Zelda         160    81     79      2
 5 Pikachu       209   105    104      1
 6 Yoshi         223   112    111      1
 7 Mario         203   101    102     -1
 8 Wario         207   102    105     -3
 9 Fox           208    95    113    -18
10 Bowser        186    82    104    -22

Parece justo, Samus salta para o 1º lugar e Wario cai para o 8º lugar.

Agora, e se fizermos o mais fraco 10 º lugar Bowser ganhar 10 vezes do atual 2 º lugar Kong?

   Name        Games  Wins  Losses Points
 1 Samus         221   120    101     19
 2 Kong          227   117    110      7
 3 Luigi         186    95     91      4
 4 Zelda         160    81     79      2
 5 Pikachu       209   105    104      1
 6 Yoshi         223   112    111      1
 7 Mario         203   101    102     -1
 8 Wario         207   102    105     -3
 9 Bowser        196    92    104    -12
10 Fox           208    95    113    -18

É aqui que você vê o quão errado esse método está. Mesmo que ele tenha perdido 10 vezes para  o jogador mais fraco, Kong ainda reina supremo no 2º lugar. E o pobre Bowser, apesar de todo o seu trabalho duro e esforço, sobe apenas uma mera posição – de 10º para 9º.

Isso é muito frustrante e, se soa injusto, é porque de fato é. Esse tipo de cálculo é errado.

Do xadrez ao League of Legends

Se você já jogou League of Legends, você provavelmente está familiarizado com algo chamado “ELO Boosts”.

4

Essa é uma maneira de aumentar o nível de sua conta por dinheiro. Eu seria fortemente contrário a isso se você pretendesse competir profissionalmente, pois é contra as regras estipuladas pela Riot.

Enfim, eu me pergunto se você já se perguntou por que ele é chamado de “ELO”.

Isso é para o professor austro-húngaro Arpad Emmerich Elo. Ele é mais conhecido por seu sistema de classificação de jogadores de xadrez. Citando a Wikipedia:

O sistema original de classificação no xadrez foi desenvolvido em 1950 por Kenneth Harkness (…). Em 1960, utilizando os dados desenvolvidos através do Sistema de Classificação Harkness, Elo desenvolveu sua própria fórmula, que tinha uma base estatística sólida e constituía uma melhoria no Sistema Harkness. O novo sistema de classificação foi aprovado e liberado por uma reunião da Federação de Xadrez dos Estados Unidos em St. Louis, em 1960. Em 1970, a FIDE, a Federação Mundial de Xadrez, concordou em adotar o Sistema de Classificação Elo. A partir de então até meados dos anos 1980, o próprio Elo fez os cálculos de classificação. Na época, a tarefa computacional era relativamente fácil porque menos de 2.000 jogadores eram classificados pela FIDE.

Seu sistema foi aperfeiçoado e evoluiu para tornar tabelas de classificação de torneios realmente justas e competitivas. Uma dessas evoluções se deu na forma do TrueSkill Ranking System da Microsoft, usado em todos os jogos do Xbox Live.

Esse “algoritmo” que Eduardo Saverin escreve na janela do dormitório de Harvard? É o Sistema de Classificação ELO!!

Eu não sei se Zuckerberg realmente implementou as equações do sistema de classificação ELO. Se o fez, essa foi a escolha correta. Mas o são Eduardo escrevendo as equações na janela provavelmente não aconteceu daquela forma, pois seria mais fácil procurar por ela no Google :-).

Demonstração do Sistema de Classificação ELO

Meu projeto de demonstração de estimação também calcula essa pontuação exata de ELO. Os cálculos são feitos pelo rubygem do elo.

A ideia é calcular a probabilidade que um jogador tem de vencer o outro jogador. Então, se um jogador forte joga contra um jogador fraco, espera-se que ele vença, e se este é o resultado, ele não vai pontuar muito e o jogador perdedor não vai cair muito também. Mas se o inesperado acontece e o forte perde, então é esperado que ele caia muito e que o jogador “mais fraco” cresça muito.

Isso tornará os torneios mais competitivos e os novos jogadores mais motivados para jogar contra os mais fortes, e também vai fazer com que fique mais difícil para o jogador mais forte manter suas posições.

Da documentação gem do elo, é assim que você o usa:

kong  = Elo::Player.new
bowser = Elo::Player.new(:rating => 1500)

game1 = kong.wins_from(bowser)
game2 = kong.loses_from(bowser)
game3 = kong.plays_draw(bowser)

game4 = kong.versus(bowser)
game4.winner = bowser

game5 = kong.versus(bowser)
game5.loser = bowser

game6 = kong.versus(bowser)
game6.draw

game7 = kong.versus(bowser)
game7.result = 1 # result is in perspective of kong, so kong wins

game8 = kong.versus(bowser, :result => 0) # bowser wins

E é assim que você avalia os resultados:

kong.rating       # => 1080
kong.pro?         # => false
kong.starter?     # => true
kong.games_played # => 8
kong.games        # => [ game1, game2, ... game8 ]

O gem tem mais tuning para além desse algoritmo original, como o fator-K para recompensar novos jogadores. Esses tipos de tunings são o que torna os jogos mais competitivos atualmente e como você evolui para os níveis de TrueSkill, mas isso está além do limite deste artigo.

Vamos ver a classificação errada novamente:

   Name        Games  Wins  Losses Points (wins - losses)
 1 Kong          217   117    100     17
 2 Samus         211   110    101      9
 3 Wario         197   102     95      7
 4 Luigi         186    95     91      4
 5 Zelda         160    81     79      2
 6 Pikachu       209   105    104      1
 7 Yoshi         223   112    111      1
 8 Mario         203   101    102     -1
 9 Fox           208    95    113    -18
10 Bowser        186    82    104    -22

Agora, vamos ver como a classificação correta é obtida calculando a pontuação Elo usando exatamente as mesmas 2.000 partidas:

   Name        Games  Wins  Losses Points  Elo Rating
 1 Pikachu       209   105    104      1         851
 2 Zelda         160    81     79      2         847
 3 Samus         211   110    101      9         842
 4 Luigi         186    95     91      4         841
 5 Wario         197   102     95      7         824
 6 Mario         203   101    102     -1         820
 7 Yoshi         223   112    111      1         803
 8 Kong          217   117    100     17         802
 9 Bowser        186    82    104    -22         785
10 Fox           208    95    113    -18         754

Vê como é diferente? No ranking errado, Kong é considerado o mais forte, mas na classificação Elo ele é apenas o 8º lugar. E a razão é que, mesmo que ele seja o que ganhou a maioria dos jogos (217), ele também perdeu bastante (117). Alguém com menos vitórias, como Zelda em 2º lugar (160 vitórias), perdeu muito menos (81), razão pela qual ela é maior no ranking.

Agora, se a fizermos ganhar 10 partidas seguidas contra o 3º lugar Samus, esta é a nova classificação:

   Name        Games  Wins  Loses  Points  Elo Rating
 1 Zelda         170    91     79     12         904
 2 Pikachu       209   105    104      1         851
 3 Luigi         186    95     91      4         841
 4 Wario         197   102     95      7         824
 5 Mario         203   101    102     -1         820
 6 Yoshi         223   112    111      1         803
 7 Kong          217   117    100     17         802
 8 Bowser        186    82    104    -22         785
 9 Samus         221   110    111     -1         775
10 Fox           208    95    113    -18         754

Novamente, Zelda salta do 2º para o 1º lugar, e Samus cai do 3º para o 9º lugar. Por enquanto, tudo bem. Mas e sobre o cenário onde tornamos forte o 2º lugar Pikachu contra um muito mais fraco 10º lugar Fox McCloud?

   Name        Games  Wins  Loses  Points  Elo Rating
 1 Zelda         170    91     79     12         904
 2 Luigi         186    95     91      4         841
 3 Fox           218   105    113     -8         829
 4 Wario         197   102     95      7         824
 5 Mario         203   101    102     -1         820
 6 Yoshi         223   112    111      1         803
 7 Kong          217   117    100     17         802
 8 Bowser        186    82    104    -22         785
 9 Samus         221   110    111     -1         775
10 Pikachu       219   105    114     -9         766

Agora, isso é justiça: Pikachu deveria ter vencido, mas perder 10 vezes seguidas contra alguém considerado muito mais fraco faz com que ele caia do 2º lugar diretamente para o último lugar. E o noobie Fox, tendo ganhado 10 vezes contra um adversário muito mais forte, merece saltar direto para o 3º lugar.

Esse é o tipo de dinâmica que pode tornar partidas e jogos competitivos, que é exatamente o motivo pelo qual toda tabela de classificação online e todo torneio profissional usam esses tipos de algoritmos.

E tudo isso começou no xadrez, usando matemática que é conhecida desde o final dos anos 1940!!

Este é o cerne deste artigo e do meu anterior: a matemática não é nova.

Os desenvolvedores desperdiçam uma grande quantidade de tempo em competições estúpidas sobre qual língua ou ferramenta é “mais brilhante”, mas eles ignoram a matemática adequada e entregam resultados errados. Mas a matemática está por aqui há décadas, em alguns casos, há mais de um século inteiro já!

Deveríamos nos esforçar para ganhar o título de Cientistas da Computação. Há muita ciência em falta na computação hoje em dia. Concursos tolos não fazem nenhum bem ao programador.

***

Artigo traduzido com autorização do autor. Publicado originalmente em  http://www.akitaonrails.com/2016/11/01/matches-rankings-the-social-network-league-of-legends-and-ruby.