-<html>
+<?xml version="1.0" encoding="UTF-8" ?>
+<!DOCTYPE
+ html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
+ "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="no">
<head>
<title>WLoH-rating</title>
- <link rel="stylesheet" href="/style" type="text/css" />
+ <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>
+ <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>
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,
+ Vi sier at hvis Anne har spillestyrke (rating) 550 og Bjørn har 500,
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,
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 style="text-align: center;"><img src="norm1" style="width: 360px; height: 354px;" alt="Normalfordelingskurve med forventningsverdi 50" /></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>,
+ 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,
+ settes i utgangspunktet til 500 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>
<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>
+ best med de observasjonene vi har gjort. På engelsk kalles dette
+ <em>maximum likelihood 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
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 style="text-align: center;"><img src="norm2" style="width: 360px; height: 349px;" alt="Normalfordelingskurve med forventningsverdi ca. -18" /></p>
<p>Her blir det rimeligste resultatet at Bjørn er litt bedre
(ca. 18 poeng).</p>
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>
+ at en gjennomsnittlig spiller er 500 poeng, er det da rimelig
+ at David skal ha rating 700 (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 style="text-align: center;"><img src="norm3" style="width: 372px; height: 334px;" alt="Normalfordelingskurve med forventningsverdi 500" /></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
+ de fleste ligger rundt 500 noe sted. Det er rett og slett ikke veldig
+ rimelig at en spiller ligger rundt 700 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
+ godt resultat) vil dette trekke spilleren nærmere 500. I stor grad
løser dette problemet – det er dog ingen fullstendig fiks.</p>
<h2>Minorization-maximization</h2>
<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
+ Først antar vi alle har rating på 500. 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
+ alle andre (for eksempel 50 poeng over Bjørns rating på 500 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
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
+ vi trenger bare 60-70 runder gjennom alle spillerne (ca. 150 ms
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>
<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).
+ som ikke er blitt dekket her – for eksempel er det ikke beskrevet
+ hvordan man regner ut <em>usikkerheten</em> i de estimerte ratingene
+ (hvilket er passe komplekst, og basert på å invertere
+ <a href="http://en.wikipedia.org/wiki/Hessian_matrix">Hess-matrisen</a>
+ til rimelighetsfunksjonen),
+ eller hvordan modellen vekter kamper eldre kamper gis mindre betydning).</p>
+
+ <p>Hva gjelder forbedringer av selve modellen, kan det nevnes at det ikke
+ egentlig tatt hensyn til variabilitet
+ i folks prestasjoner (modellen antar at folk presterer på samme nivå hele tiden).
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
projects / wloh / blobdiff