25. september 2018

Glicko vs Tjukken

Jeg vil lage en optimal ranking. En ranking som best mulig forutsier hvem av to konkurrenter som kommer til å prestere best i neste konkurranse. Jeg starter med orienteringsløp for det er det jeg kan best, men når jeg har laget rankingen kan arbeidet overføres til all annen idrett som handler om å komme seg fort fra A til B, være seg langrenn eller triatlon eller skiskyting eller galopp eller hundeveddeløp eller maraton eller sekkeløp eller telemark eller alpint.

Jeg har to konkurrerende algoritmer, veldig forskjellige, og bare en kan overleve. De må møtes i kamp.


Tjukken, som jeg har klekket ut selv. Tjukken baserer seg på å først sette et mål på hvor tøff løypen og konkurransen var, og deretter vurdere løpernes prestasjoner ut fra dette. Dette er iterativt som fy, fordi vurderingen av løypene baserer seg på vurderingen av løperne som baserer seg på vurderingen av løypene som baserer seg på vurderingen av løperne, og så kjører du denne karusellen til tallene ser fine ut. 

Tjukken har stor og tung kode, den er ikke like lett og smidig som sin motstander


... Glicko. Glicko er en versjon av ELO, som brukes i sjakk, utviklet av matematikeren Glickman.  Glicko er mindre kjent men bedre enn ELO,  til forskjell fra ELO vekter den forskjellig på en løper vi vet mye om og en vi vet lite om, og den ser forskjell på en klar seier og en knepen seier. For å bruke Glicko i orienteringsløp anser jeg ethvert løp som en mengde dueller mellom to og to løpere.

Disse to algoritmene skal slåss på liv og død. Den som vinner blir den nye rankingen, den som taper må dø.

Først må vi trene opp Glicko før kampen. Den gjør det veldig bra som ranking i norsk Scrabble, hvor den er implementert av Taral Seierstad. Jeg har testet den for Wordfeud League of Honour, hvor den gjetter rett i 64% av kampene. Den slo knock.out på ligaens nåværende rankingsystem, som klarer 57%.

Det er disse sterke resultatene som gjør at jeg vil teste den på nye oppgaver. Men det er en vesensforskjell, Glicko er god i sporter hvor to og to møtes. La oss se om den kan herje når mange møtes på samme utfordring.



Hva skal Glicko gjøre med diskvalifiserte løpere. En god løper som er disket vil jo få siste plass, men fortsatt være en god løper.

Som er to problemer:

Hva skal den diskvalifiserte løperen selv få i rankingeffekt for løpet.
Hva skal løperne få for å ha slått den diskvalifiserte.

Jeg innfører to vekter for dette. "Egendisktyngde" og "andresdisktyngde", jeg skal justere dem med genetisk programmering, så vil evolusjonen vise hva som er rett å gjøre.

Dessuten må vi ha en maxkampverdi/minimum kampverdi. Slik at ekstreme resultater fra en enkeltløper, eller en feilregistrering i dataene, ikke får grenseløst stor effekt for rankingen til løperne som møter beistet.




Folk har gjort dette før meg, på formel 1. Hvor det er mye 'ikke fullført', og dermed ganske avgjørende hva man gjør med de dårlige løpene. Jeg heller mot at det riktige er å stryke disk/brutt-løpene, men jeg vil gjerne ha støtte fra AI på den teorien.

Jeg kjører dette gjennom genetisk programmering, metoden finner de beste valgene de stedene jeg er usikker. Jeg tester bare hva Glico forutsier om løpere som er ganske jevngode, for hver løper tester jeg mot de fem nærmeste konkurrentene som er dårligere, og de fen nærmeste konkurrentene som er bedre. De nivåene baserer seg på en ranking for 2018 som jeg ikke skal endre, slik at jeg kan bruke den på begge metodene.

Glicko gjetter i første runde rett i 62,8% av forsøkene. Ikke håpløst, men jeg hadde håpt på mer. Dette er verdiene den finner i de punktene jeg er usikker:

Fitness 62,86  B : 3 T 92 maxkampverdi: 3000 egendisktyngde: 0 andresdisktyngde 25

B og T er koeffisientene i glickoformelen. De er 5 og 90 for scrabble, så T er som forventet mens B overrasker. Null på egendisktyngde betyr at man ikke regner med de løpene hvor man blir disket. Det er som jeg forventet.



Vi må trimme. Finne forbedringsområder.

I blant underpresterer løpere kapitalt. Av og til betyr det at løperen tok løpet som trening. Jeg innfører variabler for det også, underpresteringlimit og egenunderprestering, som sier hvor mye rankingfall vi regner som underprestering, og hvor mye vi demper et sånt løp med.

Man ender jo med en ranking hvor det å gjøre et litt dårlig løp er mer ødeleggende for rankingen enn det å gjøre et veldig dårlig løp. Men vi får se, om det likevel gir en bedre ranking.

Fitness 62,97
B : 3 T 76
maxkampverdi: 2800 egendisktyngde: 75 andresdisktyngde 0
Egenunderprestering: 75 underpresteringlimit: 1

Det ser bedre ut, vi nærmer oss 63%. Dette er etter tjuende generasjon, og jeg holder meg med en befolkning på femti programmer som krysser hverandre. Jeg liker ikke at den har tatt inn disk-løpene i beregningen igjen. Maskinen er veldig tydelig på at B skal være 3. som er spennende, det er 5 som pleier å være standard. Den har ikke fått mulighet til å gå lavere enn 3, nå skal den få det.

Jeg lager en myk avrunding, slik at prestasjoner over max ikke blir bare satt til max, men til en verdi i nærheten av max som avhenger av hvor mye de har gått over grensa. Resultatene som kommer ut ser faktisk svakere ut.


63% er ikke profetisk nivå akkurat, en ape som kaster mynt vil jo klare 50%. Utfordringen er at løperne vi sammenligner er så like, men jeg føler at jeg må sjekke at det ikke er en feil et sted. Jeg endrer slik at alle løpere sammenlignes med alle andre i løpet. Det øker treffraten til 74%. Så det fungerer. Det er bare at testen er brutal fordi løperne som Glicko skal spå er jevngode. 

Hver test går over ni sesonger, nesten tusen løyper, maskinen gjør åttisekstusen tips som enten er rett eller feil. Treffer typisk 55000 ganger og bommer 31000.

Jeg endrer testen litt. Jeg har økt betydningen av løpere som løper i en annen løype enn de pleier, men dermed økte jeg også betydningen av en del folk som har deltatt veldig lite, så jeg demper ned disse.



Fitness 62,94  B : 2 T 76 maxkampverdi: 2950 egendisktyngde: 75 andresdisktyngde 0 Egenunderprestering: 75 underpresteringlimit: 1

Effekten er ikke magisk. Jeg liker ingen av disse tallene. B og T kryper lavt, langt under det jeg forventet, og egendisktyngde bør være null etter mitt skjønn. Pluss, den burde kunne treffe med mer enn 63%. Fitness må opp, ellers tror jeg at Tjukken kommer til å banke Glicko.


Den er så glad i underpresterings-demperen at det aner meg at den gjerne vil dempe alt, uansett, at effekten av et enkeltløp svinger rankingen for mye. Den er jo bygd for sjakk, hvor man kanskje spiller 10-12 enkeltoppgjør per turnering, men orienteringsløp kan jo fint inneholde 50 internoppgjør. Jeg innfører en sordin, pluss, jeg lar den teste B=1.

Fitness 64,15239539184269  B : 1 T 68 maxkampverdi: 3600 egendisktyngde: 50 andresdisktyngde 75 Egenunderprestering: 62 underpresteringlimit: 3  sordin: 40

Sordinen velger å redusere effekten av hvert løp ned til 40%, vi beholder mer av løpernes gamle ranking, og skulle du sett, Glicko spretter et helt prosentpoeng opp i kvalitet. 

Vi finpusser, leter nærmere rundt de tallene vi allerede har.

Fitness 64,30040088677534
B : 1 T 78
maxkampverdi: 4900 egendisktyngde: 100 andresdisktyngde 30
Egenunderprestering: 62 underpresteringlimit: 3  sordin: 40

Ser om vi kan tjene noe på å endre startrankingen og -variansen til noen som aldri har deltatt, og c, som er tidsfaktoren på foreldingen av prestasjoner. Jeg lar den jobbe hele natta, hundre generasjoner, uten at evolusjonen kommer opp med noe bedre. Mystisk mange (4) varianter gir samme fitness ned til ørtende desimal, som betyr at alle disse gjetter 55978 rett, og ingen klarer 55979. Men det er jo ikke helt uavhengig av hverandre, disse gjettingene, slik at dette tallet vil bevege seg i kvantesprang, i ordets egentlige betydning, (hopper over verdiene imellom opp til neste nivå).


Fitness 64,30040088677534
B : 1 T 78
maxkampverdi: 4925 egendisktyngde: 100 andresdisktyngde 32
Egenunderprestering: 62 underpresteringlimit: 3  sordin: 40
C: 10 startvarians : 300  startranking: 1500

Vi har hatt en del fremgang, men nå kommer jeg ikke lenger. Glicko holder samme nivå som i WLoH, tre tester der, på tre forskjellige sesonger, ga 64,2%, 64,9% og 64,6%. Det er ikke direkte sammenlignbart, det kommer jo an på hvor jevngode konkurrentene er.

Jeg har brukt dager på å trene Glicko, men jeg håper den får skikkelig juling av Tjukken. En sak er at jeg har laget Tjukken selv, fra scratch, en annen sak er at jeg er sugen på å nå et høyere nivå enn 64,3%. Det blir et spennende oppgjør.

Ingen kommentarer: