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?”.
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:
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:
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”.
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.