WLoH-rating

From: Steinar H. Gunderson Date: Sun, 18 Mar 2012 19:08:37 +0000 (+0100) Subject: Add a "ratings explained" page. X-Git-Url: https://git.sesse.net/?p=wloh;a=commitdiff_plain;h=148c3248a3a3fdc5b948663ec70b5e0a66ad9566 Add a "ratings explained" page. --- diff --git a/www/norm1.png b/www/norm1.png new file mode 100644 index 0000000..75c091a Binary files /dev/null and b/www/norm1.png differ diff --git a/www/norm2.png b/www/norm2.png new file mode 100644 index 0000000..91d9232 Binary files /dev/null and b/www/norm2.png differ diff --git a/www/norm3.png b/www/norm3.png new file mode 100644 index 0000000..105537b Binary files /dev/null and b/www/norm3.png differ diff --git a/www/rating.pl b/www/rating.pl index fe97fd6..7d0a2e2 100755 --- a/www/rating.pl +++ b/www/rating.pl @@ -60,7 +60,8 @@ printf <<"EOF", $params{-3}, $match_stddev;

Modellparametre

For de som vet litt om slikt. Mer utfÃ¸rlig forklaring for begynnere kommer seinere.

For de som vet litt om slikt. Det finnes ogsÃ¥ en lengre, mer detaljert + forklaring beregnet pÃ¥ ikke-matematikere.

MLE-basert modell med Ã©n skalar (styrke) per spiller og to globale skalarer (begge standardavvik, se under), lÃ¸st med syklisk MM (minorization-maximization). Antall iterasjoner fÃ¸r konvergens: $params{-1}.

WLoH-rating

Dette er et hobbyprosjekt fra tredjepart, og ikke en offisiell del av + Wordfeud Leage of Honour.

Dette er et forsÃ¸k pÃ¥ Ã¥ forklare hvordan ratingene + 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.

Modell

Det heter seg at Â«alle modeller er gale, men noen er nyttigeÂ». + 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 ikke Ã¥ 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.

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 normalfordelingen + inn; de fleste har nok sett kurven for den fÃ¸r:

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 standardavviket, + og det er pÃ¥ ca. 80 poeng for Wordfeud.

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).

Rimelighet

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 rimeligst mulig, altsÃ¥ stemmer + best, med de observasjonene vi har gjort. PÃ¥ engelsk kalles dette + maximum likelihool estimation, eller MLE.

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 + rimelighet (eng. Â«likelihoodÂ») og ikke sannsynlighet, + selv om det er akkurat den samme formelen.

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:

Her blir det rimeligste resultatet at BjÃ¸rn er litt bedre + (ca. 18 poeng).

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.

Utgangsantagelse

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.

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)?

De fleste vil si nei; det er ikke rimelig. Vi uttrykker dette + med en utgangsantagelse (eller engelsk Â«priorÂ») om + ratingen hos folk generelt, og igjen kommer normalfordelingen inn:

Kurven her sier rett og slett at det er fÃ¥ av de aller beste og dÃ¥rligste spillerne; + 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.

Minorization-maximization

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.

I stedet bruker vi en metode som pÃ¥ fint kalles + cyclic minorization-maximization (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.

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 globalt maksimum er en annen sak, men det skal vi ikke + beskjeftige oss med her.)

(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.)

Forbedringer og diverse

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 usikkerheten 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Ã¥ logistisk fordeling + i stedet.

Helt til slutt mÃ¥ det nevnes at ratingsystemet her trekker inspirasjon fra + mange lignende systemer, som + Glicko, + Bayeselo, + NSFs ratingsystem og + ikke minst det udÃ¸delige Elo-systemet.