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