--- /dev/null
+<html>
+ <head>
+ <title>WLoH-rating</title>
+ <link rel="stylesheet" href="/style" type="text/css" />
+ </head>
+ <body>
+ <h1>WLoH-rating</h1>
+
+ <p><em>Dette er et hobbyprosjekt fra tredjepart, og ikke en offisiell del av
+ <a href="http://wordfeud.aasmul.net/">Wordfeud Leage of Honour</a>.</em></p>
+
+ <p>Dette er et forsøk på å forklare hvordan <a href="/rating">ratingene</a>
+ som brukes på denne siden regnes ut. Forklaringen er ment å være ikke-teknisk;
+ det hjelper å ha en viss sans for matematikk, men den er med vilje skrevet
+ uten for mange greske bokstaver og lignende.</p>
+
+ <h2>Modell</h2>
+
+ <p>Det heter seg at <cite>«alle modeller er gale, men noen er nyttige»</cite>.
+ Modellen her er basert på at alle spillere har en spillestyrke, som er et
+ helt vanlig tall, og det er denne vi prøver å måle ut fra resultatene vi ser.
+ (Vi prøver altså eksplisitt <em>ikke</em> å dele ut «poeng» for å gjøre det bra,
+ kun å estimere den ekte spillestyrken din; selv et tap kan øke ratingen din.)
+ Vi sier at hvis Anne har spillestyrke (rating) 1550 og Bjørn har 1500,
+ vil Anne i gjennomsnitt slå Bjørn med 50 poeng hvis de spiller.</p>
+
+ <p>Imidlertid er Wordfeud er et spill der tilfeldigheter spiller en viktig rolle,
+ så det vil svinge mye fra kamp til kamp. Hvor mye er det sannsynlig at
+ det svinger? Her kommer <a href="http://en.wikipedia.org/wiki/Normal_distribution">normalfordelingen</a>
+ inn; de fleste har nok sett kurven for den før:</p>
+
+ <p style="text-align: center;"><img src="norm1" style="width: 360px; height: 354px;"></p>
+
+ <p>Kurven her sier rett og slett at hvis Anne og Bjørn spiller, er det mest
+ sannsynlige at Anne vinner med 50, siden dette er ratingforskjellen deres.
+ Men det er heller ikke helt usannsynlig at de spiller likt eller at Bjørn
+ vinner med 100 (de to er like sannsynlige). Det er imidlertid lite trolig at
+ Anne vinner med 300. hvor mye det svinger kan beskrives ved <em>standardavviket</em>,
+ og det er på ca. 80 poeng for Wordfeud.</p>
+
+ <p>Ratingen din betyr altså bare noe i forhold til andre spillere, så det
+ absolutte tallet er ikke så viktig i seg selv. Gjennomsnittlig spillestyrke
+ settes i utgangspunktet til 1500 poeng; dette er et helt vilkårlig tall,
+ men er valgt delvis ut fra tradisjon i andre ratingsystemer. Det kunne like
+ gjerne vært 0 eller 100000 (selv om det kanskje virker litt dust at
+ en dårlig spiller har rating 99800 og en veldig god 100200).</p>
+
+ <h2>Rimelighet</h2>
+
+ <p>Målet til ratingsystemet blir altså å prøve å måle folks spillestyrke på
+ en global skala, til tross for tilfeldighetene. Målet vårt blir å finne
+ den kombinasjonen av ratinger som er <em>rimeligst mulig</em>, altså stemmer
+ best, med de observasjonene vi har gjort. På engelsk kalles dette
+ <em>maximum likelihool estimation</em>, eller MLE.</p>
+
+ <p>Så, hva er rimeligst vi ser at Anne har slått Bjørn med 50 poeng og ikke
+ har noe annen informasjon? Her er åpenbart det mest rimelige at Anne har
+ en rating på 50 poeng over Bjørn. Når det er flere enn én kamp inne i
+ bildet, blir det imidlertid vanskeligere å bare se ting inutitivt, og
+ vi trenger litt mer systematikk. Matematisk kan vi bruke normalfordelingsfunksjonen
+ igjen, men her blir bruken invertert – i stedet for at vi har
+ en ratingforskjell og skal prøve å finne et resultat, har vi et resultat
+ og skal finne en ratingforskjell. Vi kaller da tallet vi får ut for
+ <em>rimelighet</em> (eng. «likelihood») og ikke sannsynlighet,
+ selv om det er akkurat den samme formelen.</p>
+
+ <p>Når vi da har to eller flere kamper å basere oss på, gjør vi som man
+ ofte gjør når man jobber med sannsynlighet: Vi antar at alle kamper er
+ uavhengige (det du gjør på ett brett endrer ikke det som skjer på et
+ annet), og da vil sannsynligheten for «både A og B skjedde» være lik
+ de to sannsynlighetene ganget sammen. (Rimelighet fungerer på samme
+ måte.) Under ser du for eksempel rimelighetskurven om man tar med
+ at Anne ikke bare har slått Bjørn med 50 poeng, men at hun en annen
+ gang har tapt med 80 for ham:</p>
+
+ <p style="text-align: center;"><img src="norm2" style="width: 360px; height: 349px;"></p>
+
+ <p>Her blir det rimeligste resultatet at Bjørn er litt bedre
+ (ca. 18 poeng).</p>
+
+ <p>Modellen utvides til flere spillere ganske naturlig: Om Anne er
+ 50 poeng bedre enn Bjørn, og Carl har slått Anne med 30 poeng én gang,
+ er det rimeligste at Carl er 80 poeng bedre enn Bjørn, og så videre.
+ På denne måten kan vi si noe om antatt styrkeforhold mellom Anne
+ og Ymgve, selv om de aldri har spilt mot hverandre unntatt svært
+ indirekte gjennom mange andre spillere.</p>
+
+ <h2>Utgangsantagelse</h2>
+
+ <p>Et vedvarende problem i løselig sammensatte miljøer som WLoH
+ (som man typisk ikke har i sjakk o.l.) er at ikke alle spiller
+ mot alle i noen særlig grad; folk innenfor en divisjon/avdeling
+ blir godt kalibrert i forhold til hverandre, men det er vanskeligere
+ å vite hvordan divisjonene ligger an i forhold til hverandre.
+ Man får stort sett informasjon fra å observere folk som har vært
+ i flere divisjoner (om du f.eks. gjør det knall i 8. men blir
+ banket i 7., er det sannsynlig at gjennomsnittsnivået i 7. er
+ ganske mye høyere), og særlig lenger ned kan det være få av dem,
+ ettersom disse divisjonene er befolket med for det meste nye
+ spillere.</p>
+
+ <p>Dette fører til et problem med at det kan være vanskelig å
+ finne ekte spillestyrke til relativt nye spillere. Hvis for
+ eksempel David har banket Emma, Fredrik og Gunnar med 200 poeng
+ nedi sin avdeling i 8. divisjon, og man antar i utgangspunktet
+ at en gjennomsnittlig spiller er 1500 poeng, er det da rimelig
+ at David skal ha rating 1700 (som er helt mot toppen av lista)?</p>
+
+ <p>De fleste vil si nei; det er ikke rimelig. Vi uttrykker dette
+ med en <em>utgangsantagelse</em> (eller engelsk «prior») om
+ ratingen hos folk generelt, og igjen kommer normalfordelingen inn:</p>
+
+ <p style="text-align: center;"><img src="norm3" style="width: 372px; height: 334px;"></p>
+
+ <p>Kurven her sier rett og slett at <em>det er få av de aller beste og dårligste spillerne</em>;
+ de fleste ligger rundt 1500 noe sted. Det er rett og slett ikke veldig
+ rimelig at en spiller ligger rundt 1700 i seg selv, og inntil det finnes
+ data som sier noe annet (i praksis et relativt stort antall kamper med
+ godt resultat) vil dette trekke spilleren nærmere 1500. I stor grad
+ løser dette problemet – det er dog ingen fullstendig fiks.</p>
+
+ <h2>Minorization-maximization</h2>
+
+ <p>Målet vårt blir med andre ord å å finne den kombinasjonen av
+ ratinger som gir størst total rimelighet for alle resultatene
+ samt utgangsantagelsen.
+ (Egentlig maksimaliserer man ikke total rimelighet, men logaritmen
+ av total rimelighet, men det er bare et regnetriks, og ikke noe
+ man trenger å tenke på; det endrer ikke resultatene på noe vis.)
+ WLoH har i skrivende stund rundt 2000 aktive spillere og over 20000
+ registrerte spill, så her er det ganske så mye å holde orden på,
+ og det er vanskelig å løse dette som én stor ligning.</p>
+
+ <p>I stedet bruker vi en metode som på fint kalles
+ <em>cyclic minorization-maximization</em> (syklisk MM, nært beslektet med EM-algoritmene
+ som er i vid bruk). Den er dog ikke så fryktelig komplisert for vårt tilfelle:
+ Først antar vi alle har rating på 1500. Så tar vi Annes rating og
+ setter henne riktig (dvs., med maksimal rimelighet) i forhold til
+ alle andre (for eksempel 50 poeng over Bjørns rating på 1500 hvis
+ det er all informasjonen vi har). Så setter vi Bjørn riktig i forhold
+ til alle andre, og så videre for alle spillere. Nå er antageligvis
+ Anne plassert litt feil (siden Bjørn har flyttet på seg), så vi oppdaterer
+ henne igjen, og så videre, inntil alle står på riktig plass.</p>
+
+ <p>Man skulle kanskje tro at man endte opp i løkker hvor man flyttet folk
+ fram og tilbake mellom ratinger og aldri ble ferdig, men det er faktisk ikke tilfelle;
+ siden rimeligheten alltid går opp for hvert flytt, er vi nødt til før
+ eller siden å ende opp i en stabil situasjon. Dette går overraskende fort;
+ vi trenger bare 60-70 runder gjennom alle spillerne (ca. tre sekunders
+ beregningstid) før vi er inne i en stabil situasjon. (Om vi har nådd
+ et <em>globalt</em> maksimum er en annen sak, men det skal vi ikke
+ beskjeftige oss med her.)</p>
+
+ <p>(Vi har enda noen parametre å optimalisere, nemlig standardavviket til
+ hver kamp og standardavviket til utgangsantagelsen. Vi optimaliserer disse som
+ del av MM-algoritmen, akkurat som ratingene.)</p>
+
+ <h2>Forbedringer og diverse</h2>
+
+ <p>Dette var faktisk alt. Det skal sies at det sikkert er nok å ta tak i
+ som ikke er blitt dekket her – for eksempel kunne det være ønskelig
+ å vite noe om <em>usikkerheten</em> i de estimerte ratingene, og dette
+ er ikke på plass ennå. Ei heller er det egentlig tatt hensyn til variabilitet
+ i folks prestasjoner (modellen antar at folk presterer på samme nivå hele tiden),
+ og vi har ikke sagt noe om vekting av kamper (eldre kamper gis mindre betydning).
+ Det er også som alltid litt tvilsomt om normalfordelingen er det aller beste
+ valget; den er relativt enkel å regne med, hvilket har en ikke ubetydelig
+ verdi i seg selv, men mange andre systemer har etter hvert valgt å basere seg
+ på <a href="http://en.wikipedia.org/wiki/Logistic_distribution">logistisk fordeling</a>
+ i stedet.</p>
+
+ <p>Helt til slutt må det nevnes at ratingsystemet her trekker inspirasjon fra
+ mange lignende systemer, som
+ <a href="http://en.wikipedia.org/wiki/Glicko_rating_system">Glicko</a>,
+ <a href="http://remi.coulom.free.fr/Bayesian-Elo/">Bayeselo</a>,
+ <a href="http://scrabbeller.appspot.com/index">NSFs ratingsystem</a> og
+ ikke minst det udødelige <a href="http://en.wikipedia.org/wiki/Elo_rating_system">Elo</a>-systemet.</p>
+ </body>
+</html>
projects / wloh / commitdiff
