Uitleg (Toernooi) Performancerating (TPR)

(november 2014) Kees Pippel

Nu de definitieve ratings van de Nederlandse Dambond voor 2012 bekend zijn (KNDB) is het een goed moment om aandacht te schenken aan een onderwerp waar ik als competitieleider van Damclub IJmuiden (DCIJ) regelmatig vragen over krijg: wat betekent de toernooiprestatierating (TPR) en hoe wordt deze bepaald. Diverse organisaties administreren de speelsterkte van spelers in een ratingsysteem: voor dammers bijvoorbeeld de KNDB en de FMJD, voor schakers de FIDE, en de diverse nationale bonden.

De Performancerating is een hypothetische ratingprestatie die voortvloeit uit de selectie van een aantal gekozen partijen, bijvoorbeeld de gespeelde partijen in één competitie. Toernooimanagers als Sevilla [1] hebben functies om de performancerating (PR) te bepalen.

Toepasingen Performancerating

Het principe achter het Elo-ratingsysteem (The Elo-rating system)

d_pp
0-30.50
099-1060.64
138-1450.69
198-2060.76
279-2900.84
620-7350.99
736- +∞1.00

De aanname achter het Elo-ratingsysteem is dat kleine plusscores optelbaar zijn. Als speler A wint van speler B volgens 55% - 45 % (plusscore = 5%), En speler B wint van speler C met 55% - 45% (plusscore = 5%), dan is het redelijk om aan te nemen dat speler A wint van speler C met 60% - 40% (plusscore = 10%).

De kern van de ratingwaardering is een verband tussen de verwachte score over één of meerdere partijen tussen twee spelers en het ratingverschil van deze spelers. Dit verband tussen ratingverschil(d_p) en verwachting (p) noemen we de verwachtingsfunctie: E(x). In het standaard Elo-systeem is dit een symmetrische S-vormige figuur, tussen 0% en 100%, waarbij E(0) = 50% en E(x) + E(-x) = 1. We kunnen dit verband samenvatten in de nevenstaande tabel.

Berekening van de Elo-ratingverschiltabel

In de beginfase (1960) werden alle berekeningen uitgevoerd met potlood en papier. Een groot voordeel, de beperking dwingt tot eenvoud en essentie: simpel, maar niet te simpel. Een vereenvoudiging is de benadering van de cumulatieve Gauss-verdeling door een tabel. In The Rating of Chessplayers motiveert Elo de tabel als volgt:

8.94 Development of the Percentage Expectancy Table

The normal probabilities may be taken directly from the standard tables of the areas under the normal curve when the difference in rating is expressed as a z score. Since the standard deviation σ of the individual performances is defined as 200 points, the standard deviation σ' of the differences in performance becomes σ√2 or 282.84. The z value of a difference then is D/282.84. This z will then divide the area under the curve into two parts, the larger giving P for the higher rated player and the smaller giving P for the lower rated player.

For example, let D = 160. Then z = 160/282.84 = 0.566. The table gives .7143 and .2857 as the area of the two portions under the curve. These probabilities are rounded to two figures in table 2.11.

Tabel 2.11 wordt door de FIDE nog steeds gebruikt (Formula's FIDE Rating Tables 8.1b).

Wanneer we het rekenvoorbeeld van Elo toepassen op 161, dan wordt het resultaat .716, afgerond 72%. Maar in de Elo/FIDE tabel is dit 71%. Bij nader inzien blijkt dat de tabel is opgebouwd met σ = 2000 / 7 = 285,71428.

Terzijde:

In de tabel komen een beperkt aantal (onverklaarbare) afrondingsverschillen voor. De verwachting van 620 is nauwkeuriger uitgedrukt: 98,49997%. Dus eigenlijk hoort 620 bij 98%. Er zijn nog drie andere afrondingsverschillen: 54, 358, 392. Verder behoren 343 en 344 tot 89% in plaats van 88%. De verwachting van 344 is namelijk: 88,570%, afgerond 89%.

Toepassingen van de Elo-rating

Een praktische toepassing van het ratingsysteem is: als team A, bestaande uit 10 spelers, gemiddeld 150 ratingpunten meer heeft danteam B, dan zal team A volgens de ratingprognose een score realiseren van 70%, wat overeenkomt met een damscore van 14-6. Stel dat een ratingverschil 200 is. Dat is ongeveer 25% in het traject 198-206. Wanneer we dat doorvertalen naar het percentage dan is het resultaat 75,5% + (2 / 8) × 1% = 75,75%: Dit noemen we: lineaire extrapolatie. Met de huidige moderne hulpmiddelen (Excel, Calc) is het praktischer om een formule in plaats van een tabel te gebruiken, ook als deze formule ingewikkeld is.

De regel van 400 (Rule of 400)

In plaats van een tabel, kunnen we ook een lineair verband gebruiken. De 240 ratingpunten in de ratingtabel komen overeen met een plusscore van 30%. Een plusscore van 50% komt overeen met 400 punten. Een ratingsysteem gebaseerd op dit eenvoudige lineaire verband wordt ook wel de regel van 400 of algoritme of 400 in het Engels genoemd. Bijvoorbeeld: In het afgelopen SNA open toernooi (2012) heeft Georgiev 13 punten uit negen wedstrijden gescoord. Zijn plus-score ten opzichte van de 50% is (13-9) / 13. De bijbehorende ratingprestatie wordt dan ((13-9) / 9) × 400 = 177 punten. Deze prestatie is relatief ten opzichte van de gemiddelde rating van de tegenstanders. Om de prestatie op zijn waarde te kunnen schatten, moeten we uiteraard kijken naar het ratingniveau van de tegenstanders.

Het lineaire verband tussen scorepercentage en rating is: scorepercentage × 800 - 400. Dit is gelijk aan: ((scorepercentage - 50%) / 50%) × 400. Merk op dat (scorepercentage - 50%) gelijk is aan de plusscore. De plusscore is gelijk aan 0,5 × (Gewonnen partijen -/- Verloren partijen) / Aantal partijen. De formule wordt dan: ( (Gewonnen partijen -/- Verloren partijen) / Aantal partijen) × 400.

De regel, [-400, +400] = 100%, is natuurlijk niet heilig: Jeff Sonas heeft een ratingsysteem ontwikkeld op basis van [-425,+425] = 100% (Chessmetrics).

1. PR varianten

PR - Offset op gemiddelde

Het niveau van de door de tegenstander gespeelde partijen tegen Georgiev was gemiddeld 2300 ratingpunten. De performancerating van Georgiev in het SNA-toernooi wordt dan 2300 + 177 = 2477. Wat iets beter is dan zijn FMJD rating: 2445. In een ratingsysteem zal de prestatie van een speler, met een zekere vertraging (op basis van de verversingsfactoren K), doorgevoerd worden. Bij het bepalen van de performancemeting speelt dat verder geen rol.

Deze methode heet Offset op gemiddelde of Offset on Average. De methode, voorgesteld door Elo, wordt gehanteerd door KNDB, FMJD en FIDE voor het bepalen van de performancerating. Deze methode heeft de charme van de eenvoud. Maar er is ook een keerzijde: de methode is gevoelig voor uitschieters. De relatie tussen rating en verwacht resultaat is niet noodzakelijk lineair. Zwakke spelers kunnen het gemiddelde zover naar beneden trekken, dat dit niet meer gecompenseerd wordt door een overwinning tegen deze spelers. Om dit effect tegen te gaan wordt in het bepalen van de rating (niet de PR!) door de FIDE de volgende regel gehanteerd:

Rule of 400 Points

Bij het verwerken van de uitslagen in het ratingsysteem van de FIDE worden ratingverschillen groter dan 400 punten afgekapt: FIDE handbook B 02. 8.0 The working of the FIDE Rating System.

(8.54) A difference in rating of more than 400 points shall be counted for rating purposes as though it were a difference of 400 points.

De historische achtergrond van deze regel is: [4].

John Nunn, Grandmaster, mathematician: This rule was introduced for a simple reason: to prevent players losing Elo points by winning a game. If one player in a tournament is rated far below the others, then including that player can lower the average rating of your opponents by so much that your expected score is increased by more than one point. Then beating that player will leave you worse off than if you had not played him at all. This is not just an academic situation. For very strong players it could easily happen in cases where, for example, a strong tournament includes a ‘local player’ who is much weaker than the others, or in Olympiads where your first round opponent was relatively weak.

De regel wordt uitsluitend toegepast op het ratingverschil van de sterkere speler, en is een bescheiden bron van ratinginflatie.

Dit stamt uit de tijd dat de rating met de hand werd berekend op basis van gemiddelden en scorepercentage. Deze regel kan misbruikt worden door ratingpunten te sprokkelen tegen zwakkere spelers. De Nederlandse tennisbond lost dit op door winstpartijen van een sterke speler tegen een te zwakke speler niet mee te tellen. Winst en remise van de zwakkere speler tellen wel mee.

In moderne ratingsystemen wordt de rating stapsgewijs (K-factor) aangepast op basis van individuele partijen, en op basis een S-vormige asymptotische verwachtingsfunctie tussen 0 en 100%. Ratingverlies door winst of ratingwinst door verlies is onmogelijk. Daarentegen wordt de performancerating (TPR) van de FIDE bepaald op basis van de gemiddelde tegenstanderrating (Average Opponent Rating), de behaalde score, en de rating tabel. Zie: FIDE Handbook, B. Permanent Commissions, 01. International Title Regulations (Qualification Commission) , 1.48 Performancerating (Rp). Het is merkwaardig dat het voorschrift om ratingverschillen te beperken hier ontbreekt.

PR - Bijsturing per partij (game by game)

Lijst Prestatie Meting KN Schaakbond (LPR), individuele Ratingperformance Nederlandse Dambond (iRp)

In het handboek Rekenregels KNSB Ratingsysteem vinden we:

De LPR is die rating waarvoor zou gelden dat het totaal van de te verwachten scores (Wx op basis van de LPR) het totaal van de werkelijk behaalde scores het dichtst benadert. Hierbij wordt bij een 0% of 100% score één fictieve remise tegen zichzelf (Ro) toegevoegd.

In nieuwe rekenregels wordt het zo verwoord:

iRp = Prestatierating waarbij de som van de normscores tegen de individuele tegenstanders exact gelijk is aan het aantal behaalde punten. Bij een 0% of 100% score wordt een fictieve remise tegen een speler met rating Ro toegevoegd.

Er bestaat in het algemeen (zie hier voor een uitzondering) geen analytische formule om de LPR te bepalen. In plaats daarvan kunnen we een methode gebruiken die op het middelbaar onderwijs toepasselijk inklemmen wordt genoemd. Deze methode werkt uitsluitend als de te berekenen waardes begrensd zijn. Daarom worden de 0% en 100% scores geëlimineerd door voor deze spelers een fictieve remise tegen de eigen rating in te voeren. De KNDB, KNSB gebruiken de iRP, respectievelijk de LPR om extreme ratingwijzigingen te limiteren.

PR voor 0% en 100%

Als de verwachtingsfunctie lineair is, dan zullen de ratingverschillen altijd begrensd zijn. We beperken ons tot de situatie waarin de verwachtingsfunctie asymptotisch loopt tussen de 0% en 100%. De verwachtingsfunctie nadert de 0% en 100% willekeurig dichtbij, maar er is geen eindige rating met een verwachting van 0% of 100%. Als de rating door iteratie wordt bepaald dan gedraagt een onbegrensde PR zich als een zwart gat waar alle correcties in gezogen worden. De oplossing zal dan niet convergeren. Een remedie is om de PR van de 100%, 0% scores te initialiseren met +∞ en -∞ respectievelijk. Als ∞ voldoende groot wordt gekozen dan zal binnen de gegeven nauwkeurigheid, de verwachte score op basis van een oneindig verschil, gelijk zijn aan de werkelijke score. Met als gevolg dat er geen interactie plaats vindt tussen eindige en oneindige ratingwaardes.

In de FIDE tabel wordt de waarde -800, +800 getoond als notatie conventie. De toepassing is niet onomstreden, zoals uit de volgende discussie blijkt.

Fictieve remise tegen eigen rating

De aanleiding in chessbase.com: [4][5]

After seven rounds top Czech GM David Navara has scored 7.0 points, i.e. won every game. This extraordinary result is evaluated by most rating calculators as a 3241 performance. But there are problems with the arbitrary addition of a few hundred points in the case of a 100% score. After discussion with experts we have decided to implement a new algorithm in the next version of ChessBase.

De KNSB / Chess Base oplossing:

fred, when i did 0%/100% calculations, i threw a draw in with himself, and did the normal calculation. it is not as phony, gives more realistic numbers and rewards lesser rated players less than higher rated players. (eg it depends on his own rating.) anyway, i think it is a much better algorithm and since you expect an even score playing yourself, it seems well founded in theory. (Ken Thomson)

Alternatief voor een fictieve remise tegen eigen rating

Het nadeel van deze oplossing is dat er een element wordt ingebracht, namelijk de eigen rating, dat los staat van de gespeelde partijen. De speler heeft namelijk niet gespeeld tegen zichzelf.

(Zie discussie in Chess.com: Ken Thompson’s 100% / 0% performance rating is flawed)[4]

We starten met de opmerking dat een 100% rating ‘oneindig’ is. Anders gezegd: er zijn blijkbaar te weinig partijen (=n) gespeeld om een eindige rating vast te stellen. De gedachte is nu: kunnen we voor deze rating een goede ondergrens bedenken? Dat kan: we verminderen de 100% score met één remise en bepalen op basis van deze score de ondergrens.(AMcHarg in discussie Chess.com). De ontbrekende remise kunnen we waarderen als plusremise boven de gemiddelde score, benaderd door een lineair verband (raaklijn in x = 0): 100% ≈ 700 ratingpunten.

Samengevat:

De eerste term is de ondergrens van de PR. De tweede term is de PR van een plusremise.

Voorbeelden 100% score David Navara Czech Championship 2010

Toegepast op David Navara na 7 uit 7.

Fictieve remise

Offset

Gemiddelde tegenstanderrating inclusief eigen rating

Percentage inclusief extra remise

Dp uit FIDE tabel 8.1a in Handbook 02. FIDE Rating Regulations

100% Rating FIDE tabel met extra draw

2475,9

94%

444

2920

2303, 2401, 2479, 2489, 2419, 2518, 2480, 2718 (himself)

7,5 / 8

bij 94%

2476 + 444

LPRInclusief remise tegen eigen rating2949Gauss, sigma = 2000 / 7

Alternatief

Offset

Gemiddelde tegenstanderrating

Dp uit FIDE tabel 8.1a in Handbook 02. FIDE Rating Regulations

Percentage score minus één remise

Ratingwaardering voor één remise boven 50%

100% rating, alternatieve bepaling

2441,3

93%

422

50,0

2913

2303, 2401, 2479, 2489, 2419, 2518, 2480

6,5 / 7

bij 93%

350 / 7

2441 + 422 + 50

Alternatief

Bijsturing

Gemiddelde tegenstanderrating

Score minus één remise

PR

Ratingwaardering voor één remise boven 50%

100% rating, alternatieve bepaling

2441,3

6,5

2871

50

2921

 

7 - 0,5

Bijsturing

350 / 7

2871 + 50

Het resultaat van het voorstel wijkt in dit voorbeeld niet ver af van de Ken Thomson werkwijze, maar het verschil is dat de eigen rating geen rol speelt.

Zie hier voor een uitwerking van de secant methode.

PRi - De independent PR

Tot nu toe hebben we de prestatierating bepaald ten opzichte van de initiële rating van de tegenstander. De PR waartegen wordt gespeeld, blijft constant en verandert niet gedurende de bepaling van de prestatiemeting. Een alternatief is dat we de PR bepalen, niet op basis van een externe rating, maar op basis van de PR. Op deze manier wordt de PR onafhankelijk van het externe ratingsysteem. De definitie wordt dan:

De PRi is die rating waarvoor zou gelden dat het totaal van de te verwachten scores (Wx op basis van de PRi) het totaal van de werkelijk behaalde scores het dichtst benadert.

In een extern ratingsysteem zullen de ratingverschillen altijd begrensd zijn. Als we de performance berekenen over een beperkt aantal wedstrijden, kunnen onbegrensde ratingverschillen voorkomen, bijvoorbeeld in het eenvoudige geval van één wedstrijd waarin speler A wint van speler B. Het voorkomen van onbegrensde ratingverschillen maakt het berekenen van de PRi complexer dan het berekenen van de LPR.

Onbegrensde ratings en grafentheorie

Onbegrensde ratingverschillen kunnen optreden zonder 0% of 100% scores: A speelt remise tegen B, C speelt remise tegen D, A wint van C.

basics

Als speler A wint van speler B, of als speler X remise speelt tegen speler Y, dan kunnen we ons dat grafisch voorstellen in de vorm van een gerichte graaf (digraph).

Het zal duidelijk zijn dat in dit eenvoudige voorbeeld de PRi van A en B enerzijds, en X en Y anderzijds, onafhankelijk zijn van elkaar. We noemen A en B zwak verbonden (weakly connected). X en Y zijn zwak en daarnaast ook sterk verbonden (strongly connected): er loopt niet alleen een pad van X naar Y, maar ook van Y naar X. We zeggen ook: X en Y zijn verbonden via een lus, of X en Y zijn wederzijds bereikbaar door een uitslagenpad. Als A en B (A is ongelijk aan B, en A en B verbonden) niet wederzijds bereikbaar zijn, dan is het ratingverschil tussen A en B onbegrensd. Omgekeerd, als A en B wederzijds bereikbaar zijn, dan is het ratingverschil tussen A en B begrensd: A en B zijn ‘bijna’ even sterk. De maximale groep spelers die zwak / sterk verbonden met elkaar zijn, vormen een Weakly / Strongly Connected Component (WCC / SCC). Een SCC wordt ook wel een priemtoernooi genoemd (Ernst Zermelo, 1928).

Ratingsverschillen (op basis van een S-vormige verwachtingsfunctie) tussen twee spelers zijn begrensd dan en slecht dan als twee spelers tot dezelfde SCC (priemtoernooi) behoren.

Levels

Uitgaande van de uitslagengraaf van een toernooi, kunnen we een nieuwe gerichte graaf construeren, waarbij de SCC's de punten vormen van de nieuwe graaf, en de pijltjes zijn gebaseerd op de onderliggende uitslagen. De nieuwe graaf heeft geen lussen (DAG = Directed Acyclic Graph). Het ratingverschil tussen de verbonden punten in deze graaf is onbegrensd. De PRi van de punten is eenvoudig vast te stellen. Onder level verstaan we het maximaal aantal stappen naar de bodem. Een oplossing is dan: L = (level + C) × w, waarin w een voldoende groot getal is, gegeven de nauwkeurigheid waarin wij willen werken (w = ‘oneindig’). C is een ‘willekeurige’ constante die per zwak verbonden component vrij gekozen kan worden. In het voorbeeld rechts: -2.

Het bepalen van de PRi komt neer op drie stappen:

  1. Binnen alle zwak verbonden componenten: het vast stellen van de sterk samenhangende componenten, de onderliggende structuur (=quotient graph, of condensation[10]) en daarvan afgeleid de PRi-basis (L) van alle sterk samenhangende componenten, zoals we zien in de nevenstaande figuur.
  2. Binnen de sterk samenhangende componenten: het bepalen van de PRi door iteratie. De oplossing is L + PRi.
  3. Optioneel: voor één level L: het normeren van de PRi-basis ten opzichte van een extern ratingsysteem.

In rapid toernooien, met relatief weinig rondes, b.v 9, grote krachtsverschillen, en tientallen deelnemers, kunnen gecompliceerde structuren voorkomen, tot 5 á 6 verschillende niveaus.

Meer grafentheorie (WCC, SCC, Level)

Alle spelers die (zwak) verbonden zijn met elkaar via een uitslagenpad, noemen we een Weakly Connected Component (WCC). Het bepalen van de Weakly Connected Components (WCC's), de Stronly Connected Components (SCC's) en de Levels doen we op basis van een Dept First Search (DFS). Het algoritme is afkomstig van Robert Endre Tarjan. Een heldere uitleg vinden we hier [6]. De pseudocode bepaling SCC vinden we hier. Een Excel toepassing vinden we hier.

PRi uitgebreid met virtuele speler (PRiV)

Een extra fictieve remise van een speler tegen zichzelf heeft geen effect op het bepalen van de PRi. Het ratingverschil tussen een speler en zichzelf is per definitie 0. Daarom is de fictieve score gelijk aan de verwachte score. We kunnen door een kunstgreep echter afdwingen dat de groep sterk samenhangt: we voegen een virtuele speler toe. De virtuele speler speelt tegen alle andere spelers een fictieve remise. Merk op dat de volgorde van de PRi en de PRiV van elkaar kunnen verschillen: De PRi maakt geen verschil tussen één of meerdere overwinningen of nederlagen (pijltjes in de graaf) tegen spelers uit een ander level. In de PRiV speelt het aantal partijen wel een rol.

Normeren PRi met een extern ratingsysteem.

Omdat de verwachte score bepaald wordt door de ratingverschillen, is de oplossing op een constante na uniek. We kunnen de oplossing uniek maken door het gemiddelde op een bepaald niveau vast te pinnen, bijvoorbeeld op het niveau van een extern ratingsysteem. Maar gewoon 0 kan ook. De berekening van de PRi is uitsluitend afhankelijk van de gespeelde partijen. In de situatie dat spelers ongelijke tegenstanders ontmoeten, kan de PRi gebruikt worden als een eerlijk (eventueel aanvullend) criterium om de ranglijst vast te stellen. Een voordeel boven Buchholz is dat de PRi het niveau van de tegenstanders van de tegenstanders incalculeert.

Normeren betekent dat we bij de PRi een constante optellen, zodanig dat de PRi's vergeleken kunnen worden met een extern ratingsysteem.

Gemiddelde sterkte van de groep

Alle ratings in het externe ratingsysteem worden begrensd verondersteld. Stel dat speler A wedstrijden speelt tegen de spelers B1, B2. De gemiddelde sterkte van deze groep is de gemiddelde externe rating van A, B1, B2. Voor de prestatie van speler A maakt het niet uit of hij één tegenstander meerdere keren ontmoet, of dat hij meerdere tegenstanders ontmoet met dezelfde externe rating. Daarom beschouwen we van alle gespeelde partijen de bijbehorende externe rating. De externe rating die 50% scoort tegen deze verzameling van externe ratings is de ‘gemiddelde’ sterkte van de groep. Dit is bij benadering het rekenkundig gemiddelde over alle uitslagen. Dit is weer gelijk aan het gewogen gemiddelde van de externe ratings van de spelers. De weegfactor is het aantal gespeelde partijen per speler. Samengevat: de gemiddelde rating moet bepaald worden over de ratings van de gespeelde partijen, en niet over de ratings van de deelnemers.

Varianten normeren
  1. Wanneer we de PRi zouden willen gebruiken in plaats van Buchholz of Sonneborn-Berger, dan is de relatie met een extern ratingsysteem overbodig. In dat geval kunnen we normeren op gemiddelde 0.
  2. Gebruikelijk is om te normeren op basis van de gemiddelde sterkte van de groep: Gemiddelde PRi = Gemiddelde externe rating gespeelde partijen.
  3. Als er een virtuele speler is, dan kunnen we de PRi van de virtuele speler ook gelijk maken aan het groepsgemiddelde van de externe rating (of 0).
  4. Als er een speler is die, en veel heeft gespeeld, geen extreme score heeft, en een betrouwbare externe rating heeft - veel recent gespeelde partijen-, dan kan de PRi van deze speler gebruikt worden als referentie voor de normering: PRi(speler) = Externe rating(speler).

Analytische bepaling volledig rond-toernooi

Als spelers een volledig toernooi spelen, en we hanteren een lineaire verwachtingsfunctie, bv. het traject [-400, +400] rating punten = 100%, dan kan de PR eenvoudig analytisch bepaald worden:

  1. We introduceren een extra ronde waarin alle n spelers remise tegen zichzelf spelen. Deze extra remise heeft geen effect op de PRi van de spelers. In de PRi is het ratingverschil van een speler tegen zichzelf altijd 0. De verwachte score van 50% is gelijk aan de fictieve remise.
  2. Gevolg: de gemiddelde tegenstander PRi van alle spelers is gelijk aan de gemiddelde PRi van de spelersgroep. Die stellen we voor het gemak op 0.
  3. We bepalen nu voor alle spelers i de performancerating PRi = ( (Wi - Li) / n ) × 400 + 0, waarbij Wi, Li het aantal gewonnen, verloren partijen is.
  4. Indien gewenst normeren we deze rating ten opzichte van een extern ratingsysteem.

2. De verwachtingsfuncties (nog meer wiskunde)

Verwachtingsfuncties

Randvoorwaardes

Voorwaarde voor een unieke oplossing van de PRi is dat de verwachtingsfunctie continu en strikt monotoon stijgend is. In dat geval is de inverse relatie van E(x) een functie, dat wil zeggen dat er bij één scoringspercentage (p), één ratingwaarde (d_p) hoort. Tabellen (stapfunctie) voldoen niet aan de eis van continuïteit. Afgekapte functies, bv. door de Rule of 400 Points, zijn niet monotoon.

Klassiek Elo

De door Árpád Élő bedachte verwachtingsfunctie is de cumulatieve normale verdeling, of Gauss verdeling, met verwachtingswaarde μ = 0 en standaardafwijking (sigma) σ = 200 2 (=282,84). De hoek van de raaklijn in x = 0 is gelijk aan: 1 / (σ ). Het bereik van de raaklijn, de lengte van de x-as tussen 0% en 100%, is (2 × 200 × π ) = 708,98.

De Standaard verwachtingsfunctie (cumulatieve logistische verdeling)

Stel dat spelers Ar, As (onbekende) speelsterktes ur en us hebben. Deze speelsterktes zijn positief en stellen de onderlinge winst / verlieskansen voor van deze twee spelers. Dan is in het door Zermelo (1928) bedachte, en daarna vele malen opnieuw herontdekte (o.a. door Bradley-Terry, paired comparisions methods) model de kans dat speler As wint van speler Ar gelijk aan Z(ur, us) = ur / (ur + us). De kans dat speler As wint van Ar is gelijk aan us / (ur + us). Beide kansen tellen op tot 1.

We kunnen nu de kansen ur en us herschrijven als macht van de natuurlijke logaritme e. De kans dat speler As wint van speler Ar wordt dan: evr / (evr + evs). Hetgeen gelijk is aan de bekende (Verhulst) logistische formule: 1 / ( 1 + e-(vr-vs)). Een bijkomend voordeel is dat deze functie qua structuur veel eenvoudiger is dan de cumulatieve gaussverdeling. Deze verwachtingsfunctie wordt gebruikt door de USCF (United States Chess Federation).

De cumulatieve logistische verdelingsfunctie met verwachtingswaarde µ, en parameter s kan geschreven worden als:

Om deze functie de zelfde hellingshoek te geven als de klassieke Elo functie moet de x-as met een factor s = (400π ) / 4 verlengd worden. Dan wel (400 / (4 / √π )). In werkelijkheid wordt ook hier een benadering gebruikt, namelijk s = 400 / ln(10). Zodat we de verdelingsfunctie kunnen schrijven als:

Deze benadering van de gaussverdeling (ELo 1976, 8.3) is niet alleen cosmetisch, maar sluit beter aan bij de gaussverdeling (zie grafiek). Uit de voorgaande formules volgt:

De inverse functie van E(x) is:

AVG400

Ten opzichte van de asymptotische S-vormige verwachtingsfuncties zijn er een aantal voordelen te noemen:

Als de verwachtingsfunctie groter dan 100% wordt, zal er ook bij winst ratingverlies optreden. Of bij verlies ratingwinst als de verwachtingsfunctie negatief wordt. Hetgeen behoorlijk contra-intuïtief is. En strijdig met het rechtvaardigheidsgevoel. Of gewoon onacceptabel als de PR het criterium is om individuele winnaars in teamwedstrijden aan te wijzen, zoals tijdens de Schaak-olympiade. Wanneer we de PR gebruiken om in een toernooi spelers met een gelijk aantal punten een volgorde te geven, dan is dit argument minder sterk. De speler is makkelijk aan de punten gekomen, en het is terecht dat dit op de PRi een matigend effect heeft. Een groot voordeel is dat het verschil tussen minimum en maximum PRi kleiner wordt, waardoor de lineaire PRi er realistischer uitziet.

Lineair versus Asymptotisch

Als we het lineaire verband doorzetten dan zal het resultaat onder de 0% of boven de 100% uitkomen. Dit is in de damscore een onmogelijk resultaat. In principe is dit geen probleem (voor de stoutmoedige van geest): tenslotte is de wortel uit -1 ook onmogelijk. Percentages boven de 100% kunnen betekenen: speler A wint met gemak van speler B.

Wanneer twee spelers ongeveer even sterk zijn, dan is een match van 10 á 20 partijen voldoende om dit betrouwbaar vast te stellen. Maar stel dat het verschil 99.9% tegen 0,1% is. Dan zal de zwakke speler gemiddeld 500 partijen nodig hebben om één remise te scoren. We begeven ons dan in het gebied van de statistiek van de zeldzame gebeurtenissen: hoeveel soldaten verongelukken er door een trap van een paard in een bepaald tijdsinterval (Auguste Poisson).

Exotische verwachtingen

Een ‘nette’ verwachtingsfunctie voldoet aan de volgende eisen:

Tabellen + lineaire extrapolatie

Tabellen werden oorspronkelijk gebruikt om spelers de gelegenheid te geven de ratingresultaten zelf te bepalen.

3. PR berekenen

Basismethode Kees Dekker[1][5]

De (onafhankelijke) PR van speler s, kan bepaald worden als de limiet van de opeenvolgende benaderingen Ts(n), n = 0, 1,..., We starten met een willekeurige beginwaarde Ts(0), bijvoorbeeld de eigen rating of een willekeurige tegenstanderrating. Op basis Ts(0) en de tegenstanderratings berekenen we de verwachte score, zeg Wes(0). Waarbij we de volgende keuze kunnen maken:

  1. (Dependent PR) De tegenstanderratings Rk zijn vast, en veranderen niet gedurende de iteratie. Rk(n) = Rk(0). De verwachte score is een monotone functie van de eigen rating Ts. De berekende PR heeft geen effect op de berekening van de PR van de overige spelers.
  2. (Independent PR) De tegenstanderrating Rk(n) in iteratiestap (n+1) is gelijk aan de berekende PR van speler k in de vorige iteratie slag: Rk(n) = Tk(n). Het verschil van de independent PR tussen twee spelers is onafhankelijk van de initiële keuze van de tegenstanderratings R(0).

We stellen:

De onderliggende aanname is dat we de verwachtingsfunctie E(x) mogen vervangen door de raaklijn aan de verwachtingsfunctie in x = 0. De te bepalen performancerating Ts van speler s is de limiet van de volgende iteratie:

Ts(n+1) = Ts(n) + ΔTs(n)

ΔTs(n) = DeltaPercs(n) × (100% / E′(0))

Stopcriteria iteratie in Sevilla [1]

Beperken stapgrootte

Raaklijn-methodes kunnen makkelijk ontsporen. Dit kunnen we tegengaan door de stapgrootte te limiteren. Na r-rondes is de minimale (> 0%), respectievelijk maximale score (< 100%) 0,5 en r-0,5 punten, met verwachte scores: E(0,5 uit r) en E(r - 0,5 uit r). In de eerstvolgende ronde is het maximale ratingverschil: E(r - 0,5 uit r) - E(0,5 uit r). Dit is in het Elo-model ongeveer gelijk aan:

Basismethode en de independent PR

Noodzakelijke voorwaarde is dat alle te bepalen performanceratings begrensd zijn.

Tijdens het iteratie proces verandert de PRi van de tegenstanders voortdurend. Of de oplossing uniek is, en onder welke voorwaarden, is een interessante opgave. (Bij nader inzien opgelost door Ernst Zermelo in 1928)

Deze methode werkt niet bijzonder goed voor de independent PR. De convergentie in de buurt van de oplossing wordt steeds trager. De oplossingsrij kan divergeren, of oscilleren (het ping-pong effect). Divergeren/oscilleren kunnen we voorkomen door voor de versterkingsfactor 1 / E′(0) een kleinere waarde te kiezen (step-halving, ridging). Dit vertraagt dan wel weer de convergentie.

Forward substitution (uit Gauss-Seidel-iteratie)
De convergentie voor de independent PR wordt sneller (33%) als we een idee gebruiken uit de zogenaamde Gauss-Seidel iteratie: gebruik bij het bepalen van de verwachte score van speler i tegen speler k de meest recent berekende rating van speler k.

Floating point precision

Zet alle elementen van de verschilvector kleiner dan de zwevende komma nauwkeurigheid op 0.

Convergentie en verschuiving Independent PR

Tijdens het berekenen van de independent PR kan er een verschuiving optreden: T(n+1) = T(n) + c. Om bijvoorbeeld de convergentie te kunnen bepalen is het noodzakelijk de constante verschuiving te elimineren. We stellen:

Bepaling van de dependent PR (univariate, in één dimensie)

Als de PR berekend wordt tegen vaste tegenstanderratings Ri, dan is de verwachte score een monotone functie van de eigen rating. De oplossing kan dan per speler, en onafhankelijk van de overige deelnemers, bepaald worden door bisectie of de antieke secant methode.

In tegenstelling tot geavanceerdere methoden, wordt uitsluitend de verwachtingsfunctie gebruikt en niet de afgeleide van deze functie of (een benadering van) de hellingshoek in x = 0 (bv. 800). Implementatie is compact (enkele regels). Bij passende initialisatie zijn minder dan 5 iteraties nodig om een nauwkeurigheid van 1% te bereiken.

Secant iteratie

Bepaal de performancerating T van speler s als limiet van de volgende iteratie:

Zie hier voor een uitwerking van de secant-methode.

Newton-Raphson iteratie

Dit is een methode om een nulpunt van een functie f(x) van RR te bepalen door het volgende iteratie proces:

Wanneer een speler s met rating T, speelt tegen spelers met rating R = (R1, R2…), en W punten scoort, dan is de dependent PR een nulpunt van de functie f(T) = 0, waarbij f(T) gedefinieerd wordt door:

De iteratie voor speler s wordt:

De basismethode is een vereenvoudigde versie van de Newton-Raphson methode. De vereenvoudiging bestaat hieruit dat f(x(n)) / f′(x(n)) vervangen wordt door f(x(n)) / f′(0), waarbij f(x(n)) gelijk is aan W - We(x(n)) en f′(0) = (N × -E′(0)). Hierin is N het aantal gespeelde partijen. Hieruit volgt: f(x(n)) / f′(0) = (-(W - We(x(n))) / N) / E′(0).

Het algoritme is gevoelig voor de eerste keus. Twee alternatieven zijn:

Bepaling independent PR (multivariate)

De independent PR speelt zich af in n (= aantal spelers) dimensies en is complexer dan de dependent PR (Kiusalaas, hoofdstuk 4.6). Gegeven is de functie:

De independent PR T is het nulpunt van de functie f, In vector notatie:

De functie f(x), x ∈ Rn, is gedefinieerd als het verschil tussen de verwachte en werkelijke score We(x) - W. We en W zijn vectoren die de verwachte en actuele resultaten bevatten van spelers 1, 2, ...,n. In scalar notatie wordt dit een systeem van n niet-lineaire vergelijkingen:

f1(x1, … xn) = 0

fi(x1, … xn) = 0

fn(x1, … xn) = 0

Waarbij:

De Gradient Descent methode

Dit is een variant op de Newton-Raphson methode in één dimensie. In plaats van een vaste rating Rk wordt de rating van de betreffende tegenstander uit de vorige iteratieslag gebruikt.

Deze methode kan makkelijk divergeren.

De methode van Newton-Raphson (multivariate)

In deze toepassing is f een functie van n (=aantal spelers) ratingwaardes naar n verschillen tussen werkelijke en verwachte scores. De independent PR, voorgesteld als vector van n ratingwaardes, is het nulpunt van deze functie: het verschil tussen werkelijke score en verwachte score is nul voor alle spelers.

Het nulpunt van f(x) = We(x) - W is de limiet van de opeenvolgende benaderingen: x(0) = 0, x(1), x(2)...,x(n), x(n+1)

∂f1/∂x1 ......... ∂f1/∂xn

Jf(x) = ......... ∂fi/∂xi .........

∂fn/∂x1 ......... ∂fn/∂xn

Inplaats van de afgeleide kunnen we ook het differentieqoutient nemen f(x + h) - f(x-h) / 2.h. Een nadeel is dat de stapgrootte h gekozen moet worden. Een veilige keus is h = s × 0,001. Het differentie quotiënt is symmetrisch gekozen om te garanderen dat E′(x) = E′(-x).

De intuïtie achter deze benadering is:

We kunnen de matrix inversie triviaal maken door alle off-diagonaal elementen op nul te zetten. Dit is de Gradient Descent methode.

Bepalen Jacobiaans (f = We) en parametrisaties

Bovenstaande formules kunnen dan samengevat worden als:

Eigenschappen van de geparametriseerde matrix Jg

De matrix Jg (P1, P3) heeft de volgende eigenschappen:

Een stelsel lineaire vergelijkingen Ax = b, kan efficiënt opgelost worden met Krylov deelruimte methoden als de matrix A SPD is. Een voorbeeld van de constructie van de Jacobiaans en de Newton_Raphson iteratie met matrix inversie vind u hier.

Methodes zonder matrixinversie (Krylov subspace methods)

Pseudo Code Newton-Raphson Root finding

Let f: RnRn, f(x) = We(x) - W

f(x1, x2, ...xn) = ( f1(x), f2(x), ..., fn(x) )

Let ||x|| = xTx, where xT is transpose of x

Let εlimit = convergence tolerance limit in x

Let δlimit = model precision limit in f(x)

Solve f(x) = (0, 0, ..., 0)

Newton-Raphson iteration

init:

x = 0;

loop ( u=0, 1, … umax while f(x)Tf(x) > δ2limit )

Jf(x) [i,k] = ∂fi(x) / ∂xk

κ = max(Jf[i,i]) / min(Jf[i,i])

if κ > 2 × N then exit loop

δx = [Jf(x)]-1-f(x), or solve unknown δx in Jf(x) δx = -f(x)

x ← x + δx

if δxTδx ≤ ε2limit then exit loop

Solve: Ax = b, or alternatively: M-1Ax = M-1b

A = Jf, b = -f, ε = error tolerance limit

Matrix inversion by Preconditioned Conjugate Gradient method

d = search direction, r = residual, x = solution, M = Diag(A)

Minimize A-norm: ||d||A = ||dAd||

init:

x = 0; r = b - Ax; d = M-1r ; δnew, δ0 = rTd; ε = exp(-2)

loop ( t=0, 1, … tmax while δnew > ε2 × δ0 )

When preconditioned, then recalibrate d to Σd = 0

q = Ad

if dTq < -2-53 then error matrix is not positive-definite

if dTq < max(δ2limit, 2-53) then exit loop

α = δnew / dTq

x = x + αd

r = b - Ax , or cumulative r = r - αq

δold = δnew

δnew= rTM-1r

β = δnew / δoud

d = M-1r + βd

Het oplossen van een stelsel lineaire vergelijkingen door matrixinversie is niet de aangewezen, dat wil zeggen snelste manier om een oplossing te vinden. In de vorige recursieformule kunnen we de term x(n) naar links brengen, Na vermenigvuldigen van linker en rechterkant met Jf(x), ontstaat:

Als de matrix symmetrisch positief-definiet (SPD) is, dan heeft het te optimaliseren oppervlakte de vorm van een paraboolachtig kom (Shewchuk, 1994). Dit stelt ons in staat (x(n+1) - x(n)) op te lossen met bekende optimalisatiemethodes. De conjugate gradient methode (zie ook Kiusalaas, hoofdstuk 2.7) is in deze situatie een veel gebruikte methode. Binnen de hoofditeratie u = 0, 1, 2 ontstaat een subiteratie t = 0, 1, 2 waarin de delta (x(n+1) - x(n)) bepaald wordt als oplossing van een stelsel lineaire vergelijkingen, zoals hierboven aangegeven.

Zij A een matrix, en b een vector. De ruimte Kn{A, b} opgespannen door de vectoren {b, Ab, A.Ab, A.AAb ... An-1} wordt de Krylov-deelruimte genoemd. De inverse matrix A-1 is een lineaire combinatie van vectoren uit de Krylov deelruimte. Methodes op basis van Krylov deelruimtes kunnen zeer compact gerealiseerd worden, zowel qua geheugenruimte als qua coding.

Een groot voordeel is ook, dat de methode werkt als de rijen van de matrix afhankelijk zijn (de determinant = 0). Als de som van de zoekvektor (d) nul is, dan is het resultaat van de CG-iteratie met Jg (parametrisatie 3) gelijk aan de CG-iteratie met Jf. Hint: ΣRij Jf = 0, en Σ(We-W) = 0. Door de CG-iteratie direct toe te passen op de oorspronkelijke matrix Jf, wordt deze werkwijze uitermate praktisch, met name als de matrix Jf sparse is.

Als we geen precondition toepassen, dan blijft de som van alle correcties 0. Anders rekalibreren we alle actieve spelers in de de zoek-vector (d), zodanig dat Σd = 0. De ratings blijven op hun plaats en er is geen noodzaak om de ratingvector zodanig te rekalibreren dat de gemidddelde rating gedurende de iteratie constant blijft.

De Steepest Descent is de CG-iteratie met β = 0, dus zonder toepassing van zoekvector (d).

Zie hier voor een detail uitwerking van de CG-methode.

Complexiteit van de Conjugate Gradient iteratie

Als de verwachtingsfunctie lineair is, dan is één matrix inversie voldoende om de oplossing te bepalen. Deze matrix inversie beperkt zich tot één CG-stap als alle spelers elkaar evenveel ontmoeten (round robin toernooi).

Zij ω = (κ - 1) / (κ + 1), waarbij het conditiegetal κ = λmax / λmin, en λmax, λmin de maximale en minimale eigenwaarden zijn van Jf[n+1, n+1]. De convergentiesnelheid van de Steepest Descent, Conjugate Gradient iteratie is gelijk aan ω, respectievelijk ω2. Iedere CG-stap vermindert de fout ei volgens:

Voor ε kiezen we in deze procedure een klein getal groter dan 0, maar niet te klein. Geïnspireerd door de vorige formule, en uitgaande van N / 2 ronden, kiezen we:

Starten NR-iteratie

De methode kan makkelijk ontsporen als de initiële ratings niet goed worden gekozen. Een veilige aanname is: alle spelers zijn even sterk. Kies voor alle spelers het gewenste groepsgemiddelde:

Divergentie

De NR-iteratie stopt als de matrix ‘verdacht’ is, d.w.z. het aantal verwachte CG-iteratiestappen groter is dan het aantal spelers N. De iteratie divergeert zeker, ook voor kleine N, indien:

Stoppen NR-iteratie

De performancerating wordt gepubliceerd als geheel getal. Dit is het uitgangspunt van de convergentietolerantie δ. Om een oplossing te bereiken, die afgerond op gehele getallen, stabiel is, d.w.z die niet verder stijgt of daalt, moeten we de gezamenlijke fout van alle spelers beperken tot δ = 1. Hierin is:

Om de stopconditie scherper af te bakenen definiëren we:

Als de convergentie geometrisch is met factor a dan geldt:

||Pr*|| ≈ ||Pr(n+1)|| + ||ΔPr(n+1)|| / (1 - a).

De stopconditie ||e(n+1)|| < δ wordt:

0 < ||ΔPr(n+1)|| / (1-a) < δ, indien a < 1, en

0 < ||ΔPr(n+1)|| < δ, als de reeks divergeert

De convergentie snelheid van de Newton-Raphson iteratie is kwadratisch: ||e(n+1)|| ≈ ||(e(n))2||. Iedere stap wordt de exponent verdubbeld, evenals het aantal correcte decimalen. Als ||ΔPr(n+1)|| < 1, dan kan de stopconditie vereenvoudigd worden tot:

||ΔPr(n+1)|| < δ

Discussie en samenvatting

Competitie met 75 personen, 8 rondes, 442 partijen. Stop criteria: ||Pr* - Pr(n)|| < 1
Methode#Iteraties

Zermelo

Basismethode

Gradient Descent

Steepest Descent

Newton-Raphson

NR (Preconditioned)

1335

826

321

10 + 497 = 507

8 + 60 = 68

8 + 49 = 57

De convergentie van de hier besproken iteratieve procedures is notoir lastig te doorgronden, zowel wat betreft snelheid als ook stabiliteit. De voorlopige conclusie is samengevat in nevenstaande tabel. De naïeve methoden hebben soms onpraktisch veel iteraties nodig om een oplossing te bereiken. Daarentegen is de Newton-Raphson methode kwadratisch snel, meer in het bijzonder als de methode in de buurt van de oplossing komt. Als de verwachtingsfunctie lineair is (AVG400, Sonas) dan is één hoofdstap voldoende. Maar de eerlijkheid gebied te zeggen dat dit inclusief een matrix-inversie is. En de matrix inversie wordt zelfs bij een relatief gering aantal spelers, b.v. 70, al een probleem. We kunnen de matrixinversie echter vermijden door de toepassing van Krylov-methodes, bijvoorbeeld de Conjugate Gradient methode. Een bijkomend voordeel is dat de berekening zich kan beperken tot producten van vectoren, en er geen noodzaak is de onderliggende matrix expliciet op te slaan. Jf(i ,k) mag ook een functie-aanroep zijn in plaats van een referentie aan een matrixelement. Merk op dat in de CG-iteratie O(N x R) stappen nodig zijn om de nieuwe zoek richtingen (d) te vinden. Het gewicht van de CG iteratie telt even zwaar als een hoofd-operatie.

Methoden op basis van afgeleiden kunnen makkelijk ontsporen, als het startpunt niet goed wordt gekozen. De meest betrouwbare aanname is: alle spelers zijn even sterk. De update van de Zermelo-iteratie is op basis van het quotiënt tussen werkelijke score en verwachte score : Pr(n+1)= Pr(n) + ln(W / We). De convergentie wordt steeds trager naarmate de oplossing beter benaderd wordt (te vergelijken met een klepstuw in de polder). De Zermelo-procedure is met afstand de traagste. Daar staat dan weer wel tegenover dat de iteratie altijd convergeert naar één unieke oplossing. Met uitzondering van de basismethode, bestaat er geen praktijkervaring met de andere iteratiemethodes.

4. Zermelo 1928

Het artikel Die Berechnung der Turnier-Ergebnisse als ein Maximum-problem der Wahrscheinlichkeitsrechnung[7] van Ernst Zermelo mag beschouwd worden als de grondslag van de moderne ratingwaardering. Wat betreft de statistische verdeling van de speelsterktes liet Zermelo zich inspireren door de verdeling van de snelheden van de moleculen in de kinetische gastheorie, zoals blijkt uit de derde voetnoot: Dieser Ansatz ist einem insbesondere in de Gastheorie häufig angewendeten Verfahren analog. De door Zermelo afgeleide verdeling is vele malen opnieuw uitgevonden, o.a. door L.l. Thurstone (1927), Bradly, Terry, Luce (1952) en Elo.

De ambitie van Zermelo is om een methode te ontwikkelen, waarmee de spelersvolgorde bepaald kan worden, ook in het geval dat niet alle spelers dezelfde tegenstanders hebben ontmoet (unbalanced design), en verder voldoet aan alle redelijke eisen die gesteld kunnen worden en vrij is van paradoxen van de tot dan ontwikkelde methodes.

Bijvoorbeeld, het Sonneborn-Berger (Neustadtl) systeem voldoet niet aan:

Zoals eerder aangegeven, wordt aan iedere speler een positief getal toegekend. Deze getallen gedragen zich als onderlinge (relatieve) speelsterktes, waarbij de regel is dat de kans dat speler Ar wint van speler As gelijk is aan ur / (ur + us). Een toernooi wordt opgevat als een Bernouilli proces, waarbij een overwinning telt als twee successen en een remise als een succes en een mislukking. Het kernidee is:

Unser verfahren komt darauf hinaus, daß die relatieven Spielstärken, als Wahrscheinlichkeiten aufgefaßt und so bestimmt werden, daß die Wahrscheinlichkeit für das Eintreten des beobachteten Turnier-Ergebnisses eine möglichst grosse wird.

We zouden er bijvoorbeeld van uit kunnen gaan dat alle deelnemers van het WK dammen 1948 dezelfde relatieve speelsterkte ux zouden hebben. Echter gezien de score van 37 uit 40 punten van de winnaar, is dat geen erg waarschijnlijke aanname. De niet-negatieve getallen u1, ..., un, die zo gekozen zijn dat de waarschijnlijkheid van het toernooiresultaat maximaal is, zijn de door Zermelo voorgestelde volgordecriteria voor de einduitslag van een toernooi.

Verder ontwikkelt Zermelo het idee van een priemtoernooi. Ieder toernooi kan op één manier onderverdeeld worden in priemtoernooien. Voor een priemtoernooi geldt: alle spelers die niet tot het priemtoernooi behoren, hebben of alles gewonnen, of alles verloren of geen enkele partij gespeeld tegen de deelnemers van het priemtoernooi. Deze priemtoernooien C1, C2..., Cn maken of onderdeel uit van een keten C1 > C2 … > Cn, of kunnen niet met elkaar worden vergeleken. Bijzonder praktisch is het advies:

Vorher muß man sich aber erst von der Irreduzibilität des Turniers überzeigt bzw. die erforderliche Zerlegung in Primturniere vorgenommen haben.

Verder toont Zermelo voor priemtoernooien aan dat een maximale kans altijd bestaat, en op een factor na, uniek is. En dat in een rond-toernooi, bij de meest waarschijnlijke uitslag, de volgorde van de relatieve speelsterktes gelijk is aan de volgorde van de wedstrijdpunten. In de situatie dat spelers verschillende tegenstanders hebben ontmoet (unbalanced design) heeft de PR een groter oplossend vermogen. In een round-robin toernooi is de volgorde van wedstrijdpunten en PR identiek.

Tenslotte ontwikkelt Zermelo een iteratieve procedure om de gevraagde speelsterktes te berekenen, en bewijst dat de convergentie volgens een geometrische rij verloopt. Daarnaast bewijst Zermelo dat deze iteratieve procedure éénduidig convergeert in een begrensd gebied. Deze procedure is te fraai om de lezer te onthouden:

Zij ur / (ur + ut) de kans dat speler Ar wint van speler Ut. Dan geldt:

en hieruit volgt dan de iteratie voor n = 0, 1,

waarbij de iteratie stopt als de ut niet merkbaar meer veranderen. Zo afgebeeld, is er sprake van een dekpuntiteratie (fixedpoint iteration). Zermelo bewijst dat onder bepaalde voorwaarden een unieke oplossing bestaat. Terzijde: Was Zermelo op de hoogte van de contractiestelling van Banach (1922) ?

De convergentie van deze iteratie verloopt, zoals Zermelo aantoont, volgens een meetkundige rij. De convergentie van de iteratie is traag. Dit in tegenstelling tot de Newton-Raphson methode, die in de buurt van de nulpunten kwadratisch convergeert. De Zermelo methode is bijzonder geschikt als er sprake is van:

We kunnen de Elo-rating met standaard logistische functie zien als het logaritmische equivalent van de Zermelo-rating. De Elo rating kan eenvoudig afgeleid worden uit de Zermelo-rating en omgekeerd. En voordeel is dat de Elo-ratings voor de geheel reële x-as zijn gedefinieerd.

Zermelo en Newton-Raphson iteratie

De functie F(x) = We(x) - W, waarbij de verwachte score bepaald wordt door Z(x,y) = x / (x+y), kan met de Newton-Raphson methode worden opgelost. De afgeleide functies zijn:

De convergentie is even snel ,als de vergelijkbare procedure op basis van de logistische functie. Maar de NR-iteratie garandeert niet dat x(n+1) > 0 blijft. Dit moet geforceerd worden.

De afgeleiden van de logistische functie E(t,u) = 1 / (1+ e-(t-u)/s) is gelijk aan:

Met behulp van bovenstaande functies kan de de Zermelo Jacobiaan, vertaald worden naar de Jacobiaan van de logistische verwachtingsfunctie:

Zermelo-iteratie in het Elo gebied

Opmerking: de vergelijking van het iteratieproces kan ook geschreven worden als::

De door Zermelo bedachte dekpuntiteratie kan getransponeerd worden naar de Elo performanceratings (verwachtingsfunctie is logistisch). Vermenigvuldigen met( gr / er) wordt in het logaritmische gebied optellen met Ln( gr / er). De iteratie is langzamer dan de eerder besproken benadering. Verder is het een voordeel dat de Elo-ratings voor de geheel reële x-as zijn gedefinieerd, en niet alleen voor positieve getallen.

De iteratie formule is:

Voorbeeld: New York 1924 chess tournament
New-Yorker Meisterturnier 1924
#Player1234567891011PtsPR
1928
PR*
1928
PR*
Π=1
Elo
Σ=0
1Emanuel Lasker (Germany)xx½0½1111111½1½1½1111626,4027,163,84234
2José Raúl Capablanca (Cuba)½1xx½½½½01½11111½1½114½18,4018,402,60166
3Alexander Alekhine (France)½½**½½10½½½½11½½111210,7010,551,4969
4Frank Marshall (United States)½0½½½½**½101½0½111118,718,581,2134
5Richard Réti (Czechoslovakia)001001½0xx½½011110101110½7,847,751,1016
6Géza Maróczy (Hungary)00½0½½xx01½½11½110107,127,010,99-2
7Efim Bogoljubow (Soviet Union)0000½½101010xx0111½1016,406,330,90-19
8Savielly Tartakower (Poland)½000½½½100½½10xx10½0½184,724,660,66-72
9Frederick Yates (England)½000½001000001xx11½173,843,780,53-109
10Edward Lasker (United States)½0½0½½01½0½0½100xx3,443,390,48-128
11Dawid Janowski (France)00½00000000110½0½0xx52,432,390,34-189
Norm10010010

De keuze van Zermelo voor het New-York master toernooi is enigszins merkwaardig te noemen. In zijn inleiding refereert Zermelo aan abgebrochenen toernooien. Het kan haast niet anders of hij moet gedacht hebben aan het Mannheim 1914 toernooi, wat daadwerkelijk werd onderbrokendoor de 1e wereldoorlog. Op het moment dat het toernooi werd stil gelegd (de betrokkenen dachten dat het toernooi na enige weken weer hervat zou kunnen worden), leidde Alekhine met een vol punt voorsprong op Vidmar. Maar Vidmar had sterkere tegenstanders ontmoet, waaronder de nummer 2 t/m 7 van de ranglijst. Toch zou Alekhine dit toernooi ook gewonnen hebben met de Zermelo-performancerating (maar niet met AVG400!).

Zie hier voor een detailuitwerking van de Zermelo methode.

De hoogste PRi aller tijden: Piet Roozenburg in het wereldkampioenschap dammen 1948

In 1948 werd Roozenburg wereldkampioen dammen, na een imposante overwinning in een dubbel round-robin toernooi. Roozenburg scoorde 37(!!) dampunten uit 20 partijen (92,5%). In de AVG400, inclusief de remise tegen zichzelf, is dit een ratingprestatie van (+17) / 22 × 400 = 309 punten ten opzichte van het toernooigemiddelde. We schatten Henk Laros (conservatief) in op 1450, Zijn resultaat was (+2 / 22) × 400 = 36 ratingpunten boven het gemiddelde. Dit geeft een toernooigemiddelde van 1414. Dit brengt de toernooiprestatie van Roozenburg op 1723 KNDB ratingpunten.

De betrouwbaarheid van de ratings (KvN 2014)

PlayerRatingWNWe(R)P(R)σ(R)W - We> σ
Alexander Baliakin15208,0116,480,591,631,52
Roel Boomstra15377,5116,750,611,610,75
Ron Heusdens15177,0116,430,581,630,57
Pim Meurs15226,5116,510,591,63-0,01
Wouter Sipma14436,0115,220,471,660,78
Anton van Berkel14356,0115,090,461,650,91
Geert van Aalten14215,5114,860,441,650,64
Ben Provoost14745,5115,730,521,66-0,23
Auke Scholma14914,5116,010,551,65-1,51
Hein Meijer14303,5115,010,461,65-1,51
Mike Koopmanschap13753,5114,120,371,61-0,61
Jan van Dijk13542,5113,800,351,58-1,30

We nemen aan dat de score binomiaal verdeeld is. Na n partijen is de standaard afwijking σ gelijk aan: np(1-p), waarbij p de kans op succes is (We / n). We kijken nu naar het verschil van de werkelijke en verwachte scores: |W - We|. Minimaal 68% van de spelers moet binnen de tolerantie van één σ vallen. In dit voorbeeld is dit zelfs 100%. Alle spelers hebben binnen de statistische toleranties gepresteerd.

Variantie en spreiding van wedstrijdpunten

Als er geen remise mogelijk is, dan vormen de wedstrijden van de spelers een Bernoulli experiment: de uitkomst van een dobbelsteen met twee uitkomsten: succes (1) of mislukking (0). Stel nu dat er 11 keer gegooid wordt: er is maar één manier om 11 keer te slagen of te falen. De kans dat dit als gevolg van toeval optreed is niet groot. Het aantal mogelijke combinaties die optellen tot ongeveer 50% is veel groter. Maar hoeveel groter ? Het aantal combinaties om h punten te scoren in n wedstrijden is gelijk aan de coëfficiënt van xh in de polynoom (1 + 1.x)n. Deze coëfficiënten kunnen met de beroemde driehoek van Pascal berekend worden. Het principe is: het aantal mogelijkheden, C(n, h), om met een tweezijdige dobbelsteen na n partijen h punten te scoren is gelijk aan de som van:

Samengevat:

Dit probleem is door De Moivre (The Doctrine of Chances, 1756) uitgebreid naar een dobbelsteen met J mogelijkheden: "To find how many chances there are upon any number of dice, each of them of the same number of faces, to throw any given number of points". In het geval van dammen J = 3: 0, 1 en 2. De coëfficiënten van (1 + 1.x + 1.x2)n vormen de verdeling. De recurrente betrekking van de uitgebreide Pascal-De Moivre driehoek is:

De binominale verdeling loopt over [0, n]. De trinomiale verdeling is gedefinieerd over [0, 2n]. Wanneer we hiervoor corrigeren (delen door 22) dan geldt voor een eerlijke dobbelsteen -alle uitkomsten even waarschijnlijk-

de variantie van de trinomiale verdeling is een factor ((3+1)/(3-1)) / ((2+1)/(2-1)) = 2 / 3 kleiner dan de variantie van de binomiale verdeling.

We kunnen dit ook als volgt inzien: zonder remise is de variantie van een partij tussen twee even sterke spelers per definite gelijk aan (0 - μ)2 / 2 + (1 - μ)2 / 2 = 0,25 en μ = (0 + 1)/2. Inclusief remise wordt dit: (0 - μ)2 / 3 + (0,5 - μ)2 / 3 + (1 - μ)2 / 3 = 1/6 en μ = (0 + 0,5 + 1)/3. Dit is een factor 2/3 kleiner dan de variantie zonder remise.

Geldt dit resultaat ook als spelers niet even sterk zijn? Voor de verdeling van de kansen over 0, 1 2 kiezen we een geometrische verdeling, voortgebracht door p, q als volgt:

Dobbelsteen (m=3)012
Kansverdelingq2p.qp2

Hierin is p een positief getal tussen 0 en 1. We kunnen nu met meer (generating functions) of minder moeite afleiden:

Aan te tonen is dat (σ2 / 4) / (1 - Pct) × Pct) ≈ 2 / 3. De Taylorreeks ontwikkeling in x = 1 / √3 geeft:

Het verschil tussen deze verdelingen en de normale verdeling is klein, ook als n relatief klein is (11).

Top-20 FIDE-ratings van Boris Spasski tot Magnus Carlsen

performance-rating-verwachtingsfuncties

In de grafiek ziet u de verwachting van de rating van de kampioen van de FIDE-ratinglijst, tegen de ratings van de eerstvolgende 19 spelers. De overmacht van Robert Fischer is onmiskenbaar. De lijn laat de gemiddelde ratingontwikkeling zien. Duidelijk blijkt de ratinginflatie sinds 1985.

Zie ook:

Bronnen:

[1]
Toernooimanager Sevilla
[2]
Elo oddities: the tortoise and the hare
[3]
Navara wins Czech Championship with 8.5/9 points
[4]
Ken Thompson’s 100% / 0% performance rating is flawed
[5]
Elo berekening basismethode Kees Dekker, communicatie door JP Hendriks
[6]
An Improved Algorithm for Finding the Strongly Connected Components of a Directed Graph, David J. Pearce
[7]
Die Berechnung der Turnier-Ergebnisse als ein Maximum-problem der Wahrscheinlichkeitsrechnung. Mathematische Zeitschrift 29 (1929), p. 436-460, E. Zermelo
[8]
Über Preisverteilung bei Spielturnieren. Zeitschrift für Mathematik und Physik 63 (1915), S. 192, Edmund Landau
[9]
Über die Behandlung graphentheorischer Probleme unter Verwendung der Matrizenrechnung. Wiss. Z. Techn. Univer. Dresden, 10 (1961), 1313–1316, Maria Hasse
[10]
Graph Theory, Addison Wesley (1972), 199-205, Frank Harary

Excel Sheets:

Terug