git.sesse.net Git - wloh/blob - www/ratings-explained.html

   1 <html>
   2   <head>
   3     <title>WLoH-rating</title>
   4     <link rel="stylesheet" href="/style" type="text/css" />
   5   </head>
   6   <body>
   7     <h1>WLoH-rating</h1>
   8
   9     <p><em>Dette er et hobbyprosjekt fra tredjepart, og ikke en offisiell del av
  10       <a href="http://wordfeud.aasmul.net/">Wordfeud Leage of Honour</a>.</em></p>
  11
  12     <p>Dette er et forsøk på å forklare hvordan <a href="/rating">ratingene</a>
  13       som brukes på denne siden regnes ut. Forklaringen er ment å være ikke-teknisk;
  14       det hjelper å ha en viss sans for matematikk, men den er med vilje skrevet
  15       uten for mange greske bokstaver og lignende.</p>
  16
  17     <h2>Modell</h2>
  18
  19     <p>Det heter seg at <cite>«alle modeller er gale, men noen er nyttige»</cite>.
  20       Modellen her er basert på at alle spillere har en spillestyrke, som er et
  21       helt vanlig tall, og det er denne vi prøver å måle ut fra resultatene vi ser.
  22       (Vi prøver altså eksplisitt <em>ikke</em> å dele ut «poeng» for å gjøre det bra,
  23       kun å estimere den ekte spillestyrken din; selv et tap kan øke ratingen din.)
  24       Vi sier at hvis Anne har spillestyrke (rating) 1550 og Bjørn har 1500,
  25       vil Anne i gjennomsnitt slå Bjørn med 50 poeng hvis de spiller.</p>
  26
  27     <p>Imidlertid er Wordfeud er et spill der tilfeldigheter spiller en viktig rolle,
  28       så det vil svinge mye fra kamp til kamp. Hvor mye er det sannsynlig at
  29       det svinger? Her kommer <a href="http://en.wikipedia.org/wiki/Normal_distribution">normalfordelingen</a>
  30       inn; de fleste har nok sett kurven for den før:</p>
  31
  32     <p style="text-align: center;"><img src="norm1" style="width: 360px; height: 354px;"></p>
  33
  34     <p>Kurven her sier rett og slett at hvis Anne og Bjørn spiller, er det mest
  35       sannsynlige at Anne vinner med 50, siden dette er ratingforskjellen deres.
  36       Men det er heller ikke helt usannsynlig at de spiller likt eller at Bjørn
  37       vinner med 100 (de to er like sannsynlige). Det er imidlertid lite trolig at
  38       Anne vinner med 300. hvor mye det svinger kan beskrives ved <em>standardavviket</em>,
  39       og det er på ca. 80 poeng for Wordfeud.</p>
  40
  41     <p>Ratingen din betyr altså bare noe i forhold til andre spillere, så det
  42       absolutte tallet er ikke så viktig i seg selv. Gjennomsnittlig spillestyrke
  43       settes i utgangspunktet til 1500 poeng; dette er et helt vilkårlig tall,
  44       men er valgt delvis ut fra tradisjon i andre ratingsystemer. Det kunne like
  45       gjerne vært 0 eller 100000 (selv om det kanskje virker litt dust at
  46       en dårlig spiller har rating 99800 og en veldig god 100200).</p>
  47
  48     <h2>Rimelighet</h2>
  49
  50     <p>Målet til ratingsystemet blir altså å prøve å måle folks spillestyrke på
  51       en global skala, til tross for tilfeldighetene. Målet vårt blir å finne
  52       den kombinasjonen av ratinger som er <em>rimeligst mulig</em>, altså stemmer
  53       best, med de observasjonene vi har gjort. På engelsk kalles dette
  54       <em>maximum likelihool estimation</em>, eller MLE.</p>
  55
  56     <p>Så, hva er rimeligst vi ser at Anne har slått Bjørn med 50 poeng og ikke
  57       har noe annen informasjon? Her er åpenbart det mest rimelige at Anne har
  58       en rating på 50 poeng over Bjørn. Når det er flere enn én kamp inne i
  59       bildet, blir det imidlertid vanskeligere å bare se ting inutitivt, og
  60       vi trenger litt mer systematikk. Matematisk kan vi bruke normalfordelingsfunksjonen
  61       igjen, men her blir bruken invertert &ndash; i stedet for at vi har
  62       en ratingforskjell og skal prøve å finne et resultat, har vi et resultat
  63       og skal finne en ratingforskjell. Vi kaller da tallet vi får ut for
  64       <em>rimelighet</em> (eng. «likelihood») og ikke sannsynlighet,
  65       selv om det er akkurat den samme formelen.</p>
  66
  67     <p>Når vi da har to eller flere kamper å basere oss på, gjør vi som man
  68       ofte gjør når man jobber med sannsynlighet: Vi antar at alle kamper er
  69       uavhengige (det du gjør på ett brett endrer ikke det som skjer på et
  70       annet), og da vil sannsynligheten for «både A og B skjedde» være lik
  71       de to sannsynlighetene ganget sammen. (Rimelighet fungerer på samme
  72       måte.) Under ser du for eksempel rimelighetskurven om man tar med
  73       at Anne ikke bare har slått Bjørn med 50 poeng, men at hun en annen
  74       gang har tapt med 80 for ham:</p>
  75
  76     <p style="text-align: center;"><img src="norm2" style="width: 360px; height: 349px;"></p>
  77
  78     <p>Her blir det rimeligste resultatet at Bjørn er litt bedre
  79       (ca. 18 poeng).</p>
  80
  81     <p>Modellen utvides til flere spillere ganske naturlig: Om Anne er
  82       50 poeng bedre enn Bjørn, og Carl har slått Anne med 30 poeng én gang,
  83       er det rimeligste at Carl er 80 poeng bedre enn Bjørn, og så videre.
  84       På denne måten kan vi si noe om antatt styrkeforhold mellom Anne
  85       og Ymgve, selv om de aldri har spilt mot hverandre unntatt svært
  86       indirekte gjennom mange andre spillere.</p>
  87
  88     <h2>Utgangsantagelse</h2>
  89
  90     <p>Et vedvarende problem i løselig sammensatte miljøer som WLoH
  91       (som man typisk ikke har i sjakk o.l.) er at ikke alle spiller
  92       mot alle i noen særlig grad; folk innenfor en divisjon/avdeling
  93       blir godt kalibrert i forhold til hverandre, men det er vanskeligere
  94       å vite hvordan divisjonene ligger an i forhold til hverandre.
  95       Man får stort sett informasjon fra å observere folk som har vært
  96       i flere divisjoner (om du f.eks. gjør det knall i 8. men blir
  97       banket i 7., er det sannsynlig at gjennomsnittsnivået i 7. er
  98       ganske mye høyere), og særlig lenger ned kan det være få av dem,
  99       ettersom disse divisjonene er befolket med for det meste nye
 100       spillere.</p>
 101
 102     <p>Dette fører til et problem med at det kan være vanskelig å
 103       finne ekte spillestyrke til relativt nye spillere. Hvis for
 104       eksempel David har banket Emma, Fredrik og Gunnar med 200 poeng
 105       nedi sin avdeling i 8. divisjon, og man antar i utgangspunktet
 106       at en gjennomsnittlig spiller er 1500 poeng, er det da rimelig
 107       at David skal ha rating 1700 (som er helt mot toppen av lista)?</p>
 108
 109     <p>De fleste vil si nei; det er ikke rimelig. Vi uttrykker dette
 110       med en <em>utgangsantagelse</em> (eller engelsk «prior») om
 111       ratingen hos folk generelt, og igjen kommer normalfordelingen inn:</p>
 112
 113     <p style="text-align: center;"><img src="norm3" style="width: 372px; height: 334px;"></p>
 114
 115     <p>Kurven her sier rett og slett at <em>det er få av de aller beste og dårligste spillerne</em>;
 116       de fleste ligger rundt 1500 noe sted. Det er rett og slett ikke veldig
 117       rimelig at en spiller ligger rundt 1700 i seg selv, og inntil det finnes
 118       data som sier noe annet (i praksis et relativt stort antall kamper med
 119       godt resultat) vil dette trekke spilleren nærmere 1500. I stor grad
 120       løser dette problemet &ndash; det er dog ingen fullstendig fiks.</p>
 121
 122     <h2>Minorization-maximization</h2>
 123
 124     <p>Målet vårt blir med andre ord å å finne den kombinasjonen av
 125       ratinger som gir størst total rimelighet for alle resultatene
 126       samt utgangsantagelsen.
 127       (Egentlig maksimaliserer man ikke total rimelighet, men logaritmen
 128       av total rimelighet, men det er bare et regnetriks, og ikke noe
 129       man trenger å tenke på; det endrer ikke resultatene på noe vis.)
 130       WLoH har i skrivende stund rundt 2000 aktive spillere og over 20000
 131       registrerte spill, så her er det ganske så mye å holde orden på,
 132       og det er vanskelig å løse dette som én stor ligning.</p>
 133
 134     <p>I stedet bruker vi en metode som på fint kalles
 135       <em>cyclic minorization-maximization</em> (syklisk MM, nært beslektet med EM-algoritmene
 136       som er i vid bruk). Den er dog ikke så fryktelig komplisert for vårt tilfelle:
 137       Først antar vi alle har rating på 1500. Så tar vi Annes rating og
 138       setter henne riktig (dvs., med maksimal rimelighet) i forhold til
 139       alle andre (for eksempel 50 poeng over Bjørns rating på 1500 hvis
 140       det er all informasjonen vi har). Så setter vi Bjørn riktig i forhold
 141       til alle andre, og så videre for alle spillere. Nå er antageligvis
 142       Anne plassert litt feil (siden Bjørn har flyttet på seg), så vi oppdaterer
 143       henne igjen, og så videre, inntil alle står på riktig plass.</p>
 144
 145     <p>Man skulle kanskje tro at man endte opp i løkker hvor man flyttet folk
 146       fram og tilbake mellom ratinger og aldri ble ferdig, men det er faktisk ikke tilfelle;
 147       siden rimeligheten alltid går opp for hvert flytt, er vi nødt til før
 148       eller siden å ende opp i en stabil situasjon. Dette går overraskende fort;
 149       vi trenger bare 60-70 runder gjennom alle spillerne (ca. 150 ms
 150       beregningstid) før vi er inne i en stabil situasjon. (Om vi har nådd
 151       et <em>globalt</em> maksimum er en annen sak, men det skal vi ikke
 152       beskjeftige oss med her.)</p>
 153
 154     <p>(Vi har enda noen parametre å optimalisere, nemlig standardavviket til
 155       hver kamp og standardavviket til utgangsantagelsen. Vi optimaliserer disse som
 156       del av MM-algoritmen, akkurat som ratingene.)</p>
 157
 158     <h2>Forbedringer og diverse</h2>
 159
 160     <p>Dette var faktisk alt. Det skal sies at det sikkert er nok å ta tak i
 161       som ikke er blitt dekket her &ndash; for eksempel kunne det være ønskelig
 162       å vite noe om <em>usikkerheten</em> i de estimerte ratingene, og dette
 163       er ikke på plass ennå. Ei heller er det egentlig tatt hensyn til variabilitet
 164       i folks prestasjoner (modellen antar at folk presterer på samme nivå hele tiden),
 165       og vi har ikke sagt noe om vekting av kamper (eldre kamper gis mindre betydning).
 166       Det er også som alltid litt tvilsomt om normalfordelingen er det aller beste
 167       valget; den er relativt enkel å regne med, hvilket har en ikke ubetydelig
 168       verdi i seg selv, men mange andre systemer har etter hvert valgt å basere seg
 169       på <a href="http://en.wikipedia.org/wiki/Logistic_distribution">logistisk fordeling</a>
 170       i stedet.</p>
 171
 172     <p>Helt til slutt må det nevnes at ratingsystemet her trekker inspirasjon fra
 173       mange lignende systemer, som
 174       <a href="http://en.wikipedia.org/wiki/Glicko_rating_system">Glicko</a>,
 175       <a href="http://remi.coulom.free.fr/Bayesian-Elo/">Bayeselo</a>,
 176       <a href="http://scrabbeller.appspot.com/index">NSFs ratingsystem</a> og
 177       ikke minst det udødelige <a href="http://en.wikipedia.org/wiki/Elo_rating_system">Elo</a>-systemet.</p>
 178   </body>
 179 </html>