De wiskunde achter boter kaas en eieren: 255.168 partijen ontleed

In 1969 publiceerde een onderzoeker bij Bell Labs het complete spelboek van boter kaas en eieren. Letterlijk: elk mogelijke partij, elke mogelijke zet. De getallen die eruit kwamen zijn verbluffend, en ze leggen uit waarom je nooit van een perfecte tegenstander wint.

Het wiskundige skelet van een 3×3-bord

Het bord heeft negen vakjes. Theoretisch kun je die op 9! = 362.880 manieren invullen — dat is als je geen rekening houdt met de regel dat een spel stopt zodra iemand wint. Doe je dat wel, dan vallen er veel van deze theoretische partijen af (een spel met X-X-X op de eerste rij hoeft niet door te gaan tot zet 9).

Wat overblijft, na het uitsluiten van onmogelijke en al-beslist-bij-eerdere-zet-partijen, zijn precies 255.168 unieke partijen. Dat is het volledige spelboek.

Waarom X meer wint (en wat dat zegt)

X heeft een statistisch voordeel. In de 255.168 partijen wint X bijna twee keer zo vaak als O — 51,4% versus 30,5%, met 18,1% remise. Dat klinkt als een groot voordeel, en in zekere zin is het dat ook. Een willekeurig spelende X tegen een willekeurig spelende O wint vaker simpelweg omdat X meer zetten doet (vijf om vier in een 9-zetten potje) en daardoor meer kansen op het toeval heeft.

Maar — en dit is de twist — zodra beide spelers optimaal spelen, verdwijnt het voordeel volledig. Tegen perfect spel eindigt elke partij in remise. Het statistische X-voordeel bestaat dus alleen tegen tegenstanders die de strategie nog niet kennen.

Het opgeloste spel — wat dat betekent

Boter kaas en eieren is in 1858 voor het eerst wiskundig “opgelost”, maar pas in de jaren zestig kwam er via brute-force-berekening een complete bevestiging. Een opgelost spel is een spel waarvoor we de optimale uitkomst kennen vanuit elke mogelijke startpositie. Voor tic-tac-toe is die uitkomst altijd remise bij perfect spel — voor schaak, om vergelijk te trekken, is dat nog niet bekend (en dat zal voorlopig zo blijven, want er zijn meer mogelijke schaakposities dan atomen in het waarneembare heelal).

De optimale strategie voor boter kaas en eieren staat in een eindige tabel die volledig in een paar honderd regels code past. Elke moderne smartphone berekent een onverslaanbare zet binnen één milliseconde. Dat is waarom onze “Onverslaanbaar”-AI echt onverslaanbaar is — hij speelt simpelweg de tabel af.

Hoeveel verschillende openingen heb je echt?

Op het eerste gezicht heeft X negen mogelijke openingszetten. In de praktijk zijn er — door symmetrie — slechts drie unieke openingen:

De vier hoeken zijn wiskundig identiek — een 90°-rotatie van het bord verandert niets aan de partij. Dat geldt ook voor de vier randen. Het centrum is uniek omdat het op vier winlijnen ligt (de meeste van alle vakjes).

Wat als O perfect speelt en X opent met een rand?

Dit is een van mijn favoriete demonstraties op de pabo. Open zelf met een rand, laat een student perfect tegenspelen, en zie wat gebeurt: bij drie van de vier rand-openingen verlies je in maximaal zeven zetten. Het is niet een willekeurige “kans op verlies” — het is wiskundig vastgelegd. De enige rand-opening die op remise uitkomt is degene tegenover een specifieke combinatie van O’s vervolgzetten.

Wat doe je hiermee?

Hopelijk drie dingen. Eén: als je vanavond een potje speelt, weet je dat het centrum waardevoller is dan welke hoek dan ook. Twee: als je een kind ziet openen met een rand, leg uit waarom dat zelden werkt. Drie: als je strategiespellen interessant vindt, neem dan de stap naar grotere borden — 5×5 met vier op een rij heeft een veel grotere zoekruimte en is nog niet wiskundig opgelost.

Verder lezen

• De volledige strategie-gids — centrum, forks, blokkeren, remise-tactiek
• Hoe win je boter kaas en eieren? — eerlijk antwoord op een eerlijke vraag
• Magic 15 — hetzelfde spel met cijfers, verrassende wiskundige link