De mogelijke uitkomsten van een schaaktoernooi en het getal pi lijken op het eerste gezicht niet veel met elkaar te maken te hebben. We laten zien hoe je beide kunt berekenen met een Monte Carlo-simulatie, waarbij toeval een centrale rol speelt.
Toeval als hulpmiddel bij complexe berekeningen
Bij een gewone dobbelsteen zijn er zes mogelijke uitkomsten: 1, 2, 3, 4, 5 of 6. De kans op elk getal is precies één zesde. Als je de kans experimenteel wilt achterhalen om te testen of een dobbelsteen eerlijk is, kun je hem duizenden keren gooien en de afzonderlijke uitkomsten tellen.
In feite doet een Monte Carlo-simulatie precies dat: het maakt gebruik van toeval om een bepaald scenario binnen zeer korte tijd miljoenen keren op een pc te simuleren en een schatting te geven van mogelijke uitkomsten. Een bekend voorbeeld van zo’n algoritme is de Miller-Rabin-priemgetaltest, die met willekeurige getallen en duizenden herhalingen probeert priemgetallen te herkennen.
Door de centrale rol van toeval, waarvan het succes afhangt, draagt de simulatie de naam van de wijk in Monaco waar het beroemde casino staat.
Het voorbeeld van een dobbelsteenworp is voor demonstratiedoeleinden een beetje te simpel, daarom richten we ons in dit artikel eerst op een van de bekendste historische Monte Carlo-simulaties: het naaldprobleem van Buffon. Daarmee kun je het getal pi bepalen door naalden te werpen.
Daarna laten we aan de hand van het praktische voorbeeld van het onlangs gespeeld schaakkandidatentoernooi zien hoe je het hele verloop van dat toernooi in Python simuleert. Het model schatte daarbij de kansen van de latere winnaar heel goed in, ook al was de uitkomst uit de toernooisituatie nog niet zo voor de hand liggend.
Naalden over naalden
Een van de bekendste historische Monte Carlo-simulaties dient om het getal pi bij benadering te bepalen door het gooien van naalden. Daarvoor heb je alleen een of meerdere naalden tegelijk nodig en een vel papier – en een hoop geduld.
Als je geen naalden hebt, werken lucifers, spijkers of tandenstokers ook. Teken op het vel papier evenwijdige lijnen die net zo ver uit elkaar liggen als de naalden lang zijn. Herhaal dat tot je aan het einde van het vel bent gekomen en een gelinieerd vel voor je hebt liggen.
Vervolgens kun je de naald herhaaldelijk ongeveer in het midden boven het vel laten vallen. Tel daarbij alle pogingen en hoe vaak het voorwerp een van de lijnen raakt. Zodra je geen zin meer hebt om dat te doen, vermenigvuldig je het aantal pogingen met twee en deel je het resultaat door het aantal kruisingen – bij voldoende pogingen zou je dicht bij pi moeten uitkomen.
We hadden geen naalden bij de hand, maar wel een paar spijkers: in 200 pogingen hebben we 127 raakpunten geteld. Met de formule krijgen we 200 · 2 / 127 = 3,1496…, wat al heel dicht bij pi komt – we waren dus heel zorgvuldig, of hadden gewoon geluk.
Veel wiskundigen hebben het experiment ook uitgevoerd en zelfs machines gebouwd voor het perfecte toeval, die de naalden zo willekeurig mogelijk laten vallen. Een vaak aangehaald succes is het experiment van Lazzarini uit 1901, die met 3408 pogingen pi tot op de zesde decimaal bepaalde. Zijn resultaten zijn echter zeer omstreden en waarschijnlijk verzonnen (zie de link bij dit artikel).
Maar waarom kun je pi überhaupt met naalden bepalen? Daarvoor moeten we terug naar de 17e eeuw: in het oude Frankrijk vermaakte de adel zich niet zelden met kansspelen, en Georges-Louis Leclerc de Buffon was daar geen uitzondering op. Hij dacht na over de kansen bij verschillende kansspelen.
Om toegelaten te worden tot de gerenommeerde Académie Royale des Sciences in Parijs bedacht hij – geïnspireerd door een kansspel – het zogenaamde naaldprobleem. Neem een handvol naalden en laat ze vallen op een plankenvloer met parallel lopende planken: hoe groot is dan de kans dat een naald een plankrand raakt of snijdt?
De wiskunde erachter
Buffon heeft pi waarschijnlijk nooit zelf berekend aan de hand van zijn naaldexperiment, maar vond op die manier wel een formule waarmee je de kans kon berekenen (zie de link):
p = 2 · l / h · πAls je dus de lengte van de naald (l) en de afstand tussen de parallelle lijnen (h) weet, kun je de kans berekenen. Die formule geldt echter alleen voor naalden die even lang zijn als h of korter. Langere naalden kunnen meerdere lijnen tegelijk snijden, waardoor daar een andere formule voor nodig is.
In de formule komt pi voor, en het ligt voor de hand dat je door een slimme hervorming uit de berekening van de kans een berekening voor pi kunt maken. De kans p kan worden benaderd met de relatieve frequentie, die wordt berekend als p = Nc / Na, waarbij Nc het aantal raakpunten met een lijn is en Na het totale aantal pogingen.
Als je dat in de formule invult:
Nc / Na = 2 · l / h · πen die herformuleert naar pi, krijg je
π = 2 · l · Na / h · NcOmdat de lengte van de naald l en de afstand tussen de lijnen h in ons geval identiek zijn, kun je ze tegen elkaar wegstrepen en krijg je daarmee de formule waarmee je eerder pi hebt benaderd:
π = 2 · Na / NcEen ander puzzelstukje om uit te leggen waarom je met het experiment pi bij benadering kunt bepalen, is de wet van de grote getallen. Simpel gezegd houdt die wet in dat door een experiment vaak genoeg te herhalen, de verwachte kans op een gegeven moment ook daadwerkelijk bereikt wordt.
Een voorbeeld daarvan is het opgooien van een munt, waarbij de kans op kop en munt zoals bekend elk 50 procent is. Bij een kleine steekproef is het helemaal niet zo onwaarschijnlijk dat kop misschien zeven keer voorkomt en munt maar drie keer. Als je het experiment daarentegen keer op keer herhaalt, stabiliseert het aantal keer kop en munt zich geleidelijk op 50 procent.
Als je de wet van de grote getallen toepast op de formule voor het naaldexperiment en uitgaat van oneindig veel naaldworpen, zou de formule op een gegeven moment pi perfect bepalen.
Een bewijs van het naaldexperiment staat op de website van de universiteit van Marburg (zie de link).
Monte Carlo-simulatie bij schaken
Pi bij benadering berekenen is wel interessant, maar geen echt serieuze toepassing van een Monte Carlo-simulatie, want er zijn betere manieren om pi te bepalen.
Een zinvollere toepassing van zo’n simulatie is het berekenen van kansen op de uitkomst van een toernooi. Als voorbeeld dient een recnt beroemd kandidatentoernooi, dat eindigde met een verrassend dominante overwinning van de pas 20-jarige Javokhir Sindarov, die daarmee de huidige wereldkampioen Gukesh mag uitdagen.
Sindarov had een spetterende start in het kandidatentoernooi. Zelfs zo’n goede start dat onze Monte Carlo-simulatie hem halverwege het toernooi al een kans van meer dan 80 procent op de toernooizege gaf.
Het schaakvoorbeeld leent zich uitstekend voor zo’n simulatie, omdat het alle mogelijke invoergegevens levert die nodig zijn om een model voor de uitkomst van het toernooi te bouwen: de speelsterkte van de afzonderlijke spelers in de vorm van hun Elo-rating, het aantal spelers, de speelkoppels en de Elo-formule om de verwachte waarde in punten voor de uitkomst van een enkele partij te bepalen.
Om het model te verfijnen, houden we rekening met het remisepercentage en het witvoordeel dat de speler heeft die begint.
Achteraf geprogrammeerd
Het idee: voor elke partij bepaalt het toeval de uitkomst, waarbij het model rekening houdt met de verwachte waarde van de Elo-formule. Bij elke toernooidoorloop onthoudt het programma de winnaar van het toernooi en telt na een miljoen toernooisimulaties hoe vaak iedereen gewonnen heeft. Daaruit kun je de kans op de toernooizege voor elke speler berekenen.
We hebben onze Monte Carlo-simulatie in Python geïmplementeerd – de volledige code staat in een GitHub-repository (zie de link). Het model moet worden gevoed met de zojuist genoemde uitgangswaarden, te beginnen met de spelers en hun Elo-rating:
self.players = [
("Sindarov", 2745), # 0
(“Esipenko", 2698), # 1
("Bluebaum", 2698), # 2
("Wei Yi", 2754), # 3
("Praggnanandhaa", 2741), # 4
("Giri", 2753), # 5
("Caruana", 2795), # 6
("Nakamura", 2810)] # 7In totaal speelt iedereen in het kandidatentoernooi twee keer tegen iedereen – één keer met zwart en één keer met wit. Je zou de partijen willekeurig kunnen loten, maar omdat de volgorde van de tegenstanders vastligt en de resultaten uit de vorige ronden een rol spelen bij de simulatie, moet je wel of niet alle 14 ronden handmatig invoeren (fragment):
self.schedule = [
# Ronde 1
(0, 1, 1.0), (2, 3, 0.5),
(4, 5, 1.0), (6, 7, 1.0),
# Ronde 2
(1, 7, 0.5), (5, 6, 0.5),
(3, 4, 0.5), (0, 2, 0.5),
# ...Daarbij bevat schedule alle wedstrijden en uitslagen. Het programma is zo ontworpen dat je bij elke ronde met het simuleren kunt beginnen, maar daarvoor heeft het wel de uitslagen van de vorige rondes nodig om de winstkans voor de rest van het toernooi te voorspellen.
Het tupel (0, 2, 0.5) geeft aan dat Sindarov met wit tegen Blübaum speelde en dat de uitslag een remise was. Om de verwachte waarde voor de uitkomst van de partij te bepalen, heb je de eerder genoemde Elo-formule nodig:
def calculate_probability(self, elo_a, elo_b):
return 1/(1+10**((elo_b-elo_a)/400))Die geeft een waarde tussen 0 en 1 weer. Bij twee spelers die precies even sterk zijn, zal de uitkomst 0,5 zijn, dus waarschijnlijk een remise.
Je kunt het resultaat echter ook zo interpreteren dat bij 100 partijen elke partij 50 procent van de punten zou winnen. Als het verschil in speelsterkte bijvoorbeeld 100 Elo-punten bedraagt, zou je verwachten dat de hogergeplaatste speler 64 procent van de punten pakt – hij zou dus de favoriet zijn.
Aan de hand van de verwachte waarde kun je bij een ontmoeting niet alleen de kans op een bepaalde uitkomst berekenen, maar ook bepalen hoe de rating verandert bij een overwinning, een nederlaag of een gelijkspel. Voor de Monte Carlo-simulatie houden we het echter bij de uitgangs-Elo-rating van de afzonderlijke spelers, waardoor dat aspect geen rol speelt in het model.
Witvoordeel
Omdat het model miljoenen toernooien simuleert, moet het niet voor elke toernooironde de verwachtingswaarde voor elke koppeling opnieuw berekenen, want dat is inefficiënt. Alle winstkansen worden één keer berekend en komen dan terecht in win_probs:
self.win_probs = {
i: self.calculate_probability(
self.players [white][1] +
self.white_bonus,
self.players[black][1])
for i, (white, black, _) in enumerate(self.schedule) if i // 4 + 1 >= self.start_round
}De speler met de witte stukken krijgt een white_bonus van 35 Elo om rekening te houden met het voordeel van de speler die mag beginnen.
Wit wint op meesterniveau doorgaans meer partijen dan zwart. Hoe groot die ‘bonus’ precies is, is onderwerp van zeer lange discussies en varieert, afhankelijk van de bron en de gegevensverzameling, van 15 Elo tot 40 Elo.
We baseren ons hier op het werk van schaakanalist Jeff Sonas, die in 2002 honderdduizenden partijen heeft onderzocht en vaststelde dat een speler met wit ongeveer 35 Elo zwakker kan zijn en toch een verwachte puntenopbrengst van 0,5 haalt (zie de link).
Remisepercentage
Net als het witvoordeel is ook het remisepercentage een variabele waarmee je de resultaten van het model kunt aanpassen. Een algemeen remisepercentage is bij schaken moeilijk vast te stellen omdat dat afhangt van veel factoren, zoals speelsterkte, speelstijl van de spelers en het toernooiformat.
Terwijl op meesterniveau soms 50 procent van de partijen in een remise eindigt, ligt het remisepercentage in een districtsklasse met 32 procent aanzienlijk lager.
Een kandidatentoernooi is moeilijk te vergelijken met de gebruikelijke grootmeestertoernooien omdat het niveau en de voorbereidingstijd buitengewoon hoog zijn. Het remisepercentage ligt daar nog een stuk hoger. Daarom hebben we het percentage berekend op basis van de laatste met rondes werkende kandidatentoernooien sinds 2013 (jaar, aantal remises, aantal overwinningen van wit en zwart):
2013: 31 remises, 15 W, 10 Z
2014: 34 remises, 17 W, 5 Z
2016: 40 remises, 13 W, 3 Z
2018: 36 remises, 12 W, 8 Z
2020: 31 remises, 17 W, 8 Z
2022: 33 remises, 14 W, 9 Z
2024: 31 remises, 15 W, 10 Z
392 partijen, 236 remises, 156 beslist
quota: 60,2 procent remisesDaaruit volgt draw_rate = 0,6. Uit de steekproef blijkt ook het significante voordeel voor wit: bij elke iteratie van het rondetoernooi heeft wit meer partijen gewonnen dan zwart.
Partijen simuleren
De methode simulate_game() heeft het remisepercentage draw_rate en de verwachtingswaarde p nodig om een partij te simuleren. Daarbij gebruikt het, geheel volgens het Monte Carlo-systeem, willekeurige waarden: één keer om te bepalen of de partij in een remise eindigt en een tweede keer om te bepalen of zwart of wit wint.
def simulate_game(self, p):
# 40 procent van de partijen is
# beslist; 60 procent remise
if random.random() > self.draw_rate:
# wit/zwart wint
return 1.0 if random.random() < p else 0.0
return 0.5 # remiseDaarbij wordt simulate_game() uitsluitend aangeroepen door simulate_tournament(), dat een mogelijke toernooidoorloop simuleert.
Om ervoor te zorgen dat de simulatie op elk willekeurig moment van het toernooi kan worden gestart, bepaalt start_round vanaf welke ronde het model de partijen moet simuleren.
De echte resultaten uit de voorgaande rondes rekent de methode er later bij:
def simulate_tournament(self):
points = defaultdict(float)
for i, (white, black, result) in enumerate(self.schedule):
s_round = i // 4 + 1
if s_round >= self.start_round:
# nog niet gespeelde partijen
# simuleren
r = self.simulate_game(self.win_probs[i])
else:
# al gespeelde partijen
r = result
points[white] += r
points[black] += (1 - r)Aan het eind geeft simulate_tournament() de winnaar van het toernooi terug. Bij gelijke stand kiest de methode willekeurig een winnaar:
max_score = max(points.values())
leaders = [i for i in range(len(self.players)) if points[i] == max_score]
return random.choice(leaders)Voor de Monte Carlo-simulatie wordt simulate_tournament() vervolgens meerdere keren uitgevoerd en worden de afzonderlijke winnaars geteld om daaruit een winstkans voor het toernooi te berekenen.
Resultaten
Met een miljoen toernooisimulaties, een remisepercentage van 0,6 en een witvoordeel van 35 Elo geeft het programma voor aanvang van het toernooi het volgende resultaat weer:
Speler Elo Punten Kans Winst
--------------------------------------
Nakamura 2810 0,0 22,4% 224097
Caruana 2795 0,0 19,2% 191750
Wei Yi 2754 0,0 12,3% 122619
Giri 2753 0,0 12,2% 122163
Sindarov 2745 0,0 11,1% 110863
Prag. 2741 0,0 10,6% 105685
Bluebaum 2698 0,0 6,2% 61713
Esipenko 2698 0,0 6,1% 61110Het model geeft voor de eerste ronde de voorkeur aan de spelers met de hoogste Elo-ratings: Hikaru Nakamura met 2810 en Fabiano Caruana met 2795 Elo. Voor de spelers met de laagste Elo-ratings, Matthias Blübaum en Andrej Esipenko, ziet het model geen grote kansen.
Nadat Javokhir Sindarov bij de volgende zeven ronden maar liefst zes van de zeven mogelijke punten pakte en daarbij de Elo-favorieten versloeg, verandert het beeld flink. Het model schatte zijn kansen toen al op meer dan 80 procent, hoewel er nog zeven rondes te spelen waren:
Speler Elo Punten Kans Winst
--------------------------------------
Sindarov 2745 6,0 81,3% 813392
Caruana 2795 4,5 14,9% 148797
Giri 2753 3,5 1,6% 15983
Prag. 2741 3,5 1,3% 13090
Wei Yi 2754 3,0 0,5% 4572
Nakamura 2810 2,5 0,2% 2065
Bluebaum 2698 3,0 0,2% 2030
Esipenko 2698 2,0 0,0% 71Geïnspireerd door Reddit-gebruiker Thomas-PlaysChess, die tijdens het kandidatentoernooi dagelijks zijn verfijnde Monte Carlo-simulatieresultaten publiceerde, hebben we een grafiek van onze simulaties gemaakt (zie de grafiek).
Optimalisaties
Er is nog veel potentieel om het model verder te verfijnen. Tot nu toe kiest het bij een gelijke stand aan het eind van het toernooi willekeurig iemand uit, maar bij het schaken zijn er speciale tiebreak-regels zoals Sonneborn-Berger, die dan worden gebruikt.
Bovendien houdt het model geen rekening met de vorm van de spelers, dus of ze de laatste tijd Elo-punten hebben gewonnen of zelfs toernooien hebben gewonnen, of misschien een paar pijnlijke nederlagen hebben moeten incasseren.
Als extra factor zou je ook de geschiedenis van de onderlinge ontmoetingen tussen de spelers kunnen meenemen en de kans op een overwinning of het percentage remises aanpassen.
Gebruik die ideeën gerust als inspiratie om het model verder te ontwikkelen. Laat je door onze code inspireren om eigen simulaties te maken – of dat nu voor andere schaaktoernooien, andere wedstrijden of zelfs voor heel andere toepassingen is.
Kandidatentoernooi 2026: verloop
Elke ronde werd met een miljoen simulaties gesimuleerd en toont de kans na afloop van de ronde voor de rest van het toernooi. Met andere woorden: na de vijfde ronde had Caruana een kans van 27,3 procent op de toernooizege en Sindarov al 61,4 procent.
(Wilhelm Drehling en Noud van Kruysbergen)
Praat mee