(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.
| d_p | p |
|---|---|
| 0-3 | 0.50 |
| 099-106 | 0.64 |
| 138-145 | 0.69 |
| 198-206 | 0.76 |
| 279-290 | 0.84 |
| 620-735 | 0.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.
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%.
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.
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).
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:
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.
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 fictieveremise 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.
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.
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)
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.
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 |
| LPR | Inclusief remise tegen eigen rating | 2949 | Gauss, 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.
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 ratingverschillen kunnen optreden zonder 0% of 100% scores: A speelt remise tegen B, C speelt remise tegen D, A wint van C.
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.
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:
In rapid toernooien, met relatief weinig rondes, b.v 9, grote krachtsverschillen, en tientallen deelnemers, kunnen gecompliceerde structuren voorkomen, tot 5 á 6 verschillende niveaus.
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.
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.
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.
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.
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:
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.
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 / (σ √2π). Het bereik van de raaklijn, de lengte van de x-as tussen 0% en 100%, is (2 × 200 × √π ) = 708,98.
Standaardverwachtingsfunctie (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:
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.
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).
Een ‘nette’ verwachtingsfunctie voldoet aan de volgende eisen:
Tabellen werden oorspronkelijk gebruikt om spelers de gelegenheid te geven de ratingresultaten zelf te bepalen.
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:
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)
Op basis van de raaklijnbenadering, 100% ≈ 1 / E′(0), stellen we:
ΔTs(n) = DeltaPercs(n) × (1 / E′(0))
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:
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.
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.
Zet alle elementen van de verschilvector kleiner dan de zwevende komma nauwkeurigheid op 0.
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:
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.
Bepaal de performancerating T van speler s als limiet van de volgende iteratie:
Zie hier voor een uitwerking van de secant-methode.
Dit is een methode om een nulpunt van een functie f(x) van R → R 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:
standaard) verwachtingsfunctie.
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:
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:
Deze methode is stabiel, elegant en convergeert volgens een geometrische rij. In de buurt van het nulpunt wordt de convergentie traag.
Zie hier voor een uitwerking van de Zermelo-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.
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.
Bovenstaande formules kunnen dan samengevat worden als:
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.
|
Pseudo Code Newton-Raphson Root finding Let f: Rn → Rn, 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.
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:
Terzijde: Als de verwachtingsfunctie lineair is en het toernooi is round-robin, of "n-regular bi-partite", dan wordt de oplossing in maximaal één, respectievelijk twee stappen gevonden.
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:
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:
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)|| < δ
| 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.
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:
Das Qualitätsprinzipen de daarop gebaseerde Gelbfuhs-Neustadtl-Brandisschen methode.
Independence-of-scale. Stel we verwisselen winst- en verliespartijen. Dan wordt de nieuwe volgorde exact gelijk aan de omgekeerde oorspronkelijke volgorde. De sterkste winnaar moet bij een zinvolle definitie ook de slechtste verliezer zijn. Hasse [1961][9]
Terzijde: een norm die aan de laatste eis voldoet, is: SBwinst - SBverlies of SBwinst / (SBwinst + SBverlies). Scoring with eigenvectors.
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 3).
3)Dieser Ansatz ist einem insbezondere in der Gastheorie häufig angewendete Verfahren analog.
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 derIrreduzibilitätdes Turniers überzeigt bzw. die erforderliche Zerlegung inPrimturnierevorgenommen haben.
Met een verwijzing naar de extremumstelling van Weierstrass toont Zermelo voor priemtoernooien aan dat een maximale kans altijd bestaat,
en dat dit maximum bereikt wordt als voor alle spelers het aantal verwachte overwinningen gelijk is aan het werkelijke aantal. En verder
dat de bijbehorende relatieve speelsterktes op een factor na, uniek zijn. Verder laat Zermelo zien 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.
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:
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:
| # | Player | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | Pts | PR 1928 | PR* 1928 | PR* Π=1 | Elo Σ=0 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | Emanuel Lasker (Germany) | xx | ½0 | 1½ | ½1 | 11 | 11 | 11 | ½1 | ½1 | ½1 | 11 | 16 | 26,40 | 27,16 | 3,84 | 234 | |
| 2 | José Raúl Capablanca (Cuba) | ½1 | xx | ½½ | ½½ | 01 | ½1 | 11 | 11 | 1½ | ½1 | ½1 | 14½ | 18,40 | 18,40 | 2,60 | 166 | |
| 3 | Alexander Alekhine (France) | 0½ | ½½ | ** | ½½ | 10 | 1½ | ½½ | ½½ | 11 | ½½ | 11 | 12 | 10,70 | 10,55 | 1,49 | 69 | |
| 4 | Frank Marshall (United States) | ½0 | ½½ | ½½ | ** | ½1 | 0½ | 01 | ½0 | ½1 | 1½ | 11 | 11 | 8,71 | 8,58 | 1,21 | 34 | |
| 5 | Richard Réti (Czechoslovakia) | 00 | 10 | 01 | ½0 | xx | ½½ | 01 | 11 | 10 | 10 | 11 | 10½ | 7,84 | 7,75 | 1,10 | 16 | |
| 6 | Géza Maróczy (Hungary) | 00 | ½0 | 0½ | 1½ | ½½ | xx | 01 | ½½ | 11 | ½1 | 10 | 10 | 7,12 | 7,01 | 0,99 | -2 | |
| 7 | Efim Bogoljubow (Soviet Union) | 00 | 00 | ½½ | 10 | 10 | 10 | xx | 01 | 11 | ½1 | 01 | 9½ | 6,40 | 6,33 | 0,90 | -19 | |
| 8 | Savielly Tartakower (Poland) | ½0 | 00 | ½½ | ½1 | 00 | ½½ | 10 | xx | 10 | ½0 | ½1 | 8 | 4,72 | 4,66 | 0,66 | -72 | |
| 9 | Frederick Yates (England) | ½0 | 0½ | 00 | ½0 | 01 | 00 | 00 | 01 | xx | 11 | ½1 | 7 | 3,84 | 3,78 | 0,53 | -109 | |
| 10 | Edward Lasker (United States) | ½0 | ½0 | ½½ | 0½ | 01 | ½0 | ½0 | ½1 | 00 | xx | 0½ | 6½ | 3,44 | 3,39 | 0,48 | -128 | |
| 11 | Dawid Janowski (France) | 00 | ½0 | 00 | 00 | 00 | 01 | 10 | ½0 | ½0 | 1½ | xx | 5 | 2,43 | 2,39 | 0,34 | -189 | |
| Norm | 100 | 100 | 1 | 0 |
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 onderbroken
door
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.
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.
| Player | Rating | W | N | We(R) | P(R) | σ(R) | W - We | > σ |
|---|---|---|---|---|---|---|---|---|
| Alexander Baliakin | 1520 | 8,0 | 11 | 6,48 | 0,59 | 1,63 | 1,52 | |
| Roel Boomstra | 1537 | 7,5 | 11 | 6,75 | 0,61 | 1,61 | 0,75 | |
| Ron Heusdens | 1517 | 7,0 | 11 | 6,43 | 0,58 | 1,63 | 0,57 | |
| Pim Meurs | 1522 | 6,5 | 11 | 6,51 | 0,59 | 1,63 | -0,01 | |
| Wouter Sipma | 1443 | 6,0 | 11 | 5,22 | 0,47 | 1,66 | 0,78 | |
| Anton van Berkel | 1435 | 6,0 | 11 | 5,09 | 0,46 | 1,65 | 0,91 | |
| Geert van Aalten | 1421 | 5,5 | 11 | 4,86 | 0,44 | 1,65 | 0,64 | |
| Ben Provoost | 1474 | 5,5 | 11 | 5,73 | 0,52 | 1,66 | -0,23 | |
| Auke Scholma | 1491 | 4,5 | 11 | 6,01 | 0,55 | 1,65 | -1,51 | |
| Hein Meijer | 1430 | 3,5 | 11 | 5,01 | 0,46 | 1,65 | -1,51 | |
| Mike Koopmanschap | 1375 | 3,5 | 11 | 4,12 | 0,37 | 1,61 | -0,61 | |
| Jan van Dijk | 1354 | 2,5 | 11 | 3,80 | 0,35 | 1,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.
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) | 0 | 1 | 2 |
|---|---|---|---|
| Kansverdeling | q2 | p.q | p2 |
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).
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.