Shannon-getal: hoeveel schaakpartijen zijn er mogelijk?

Het Shannon-getal wordt vaak aangehaald om de rijkdom van het schaakspel te illustreren. Het is ook een uitstekend hulpmiddel om met machten van 10, wetenschappelijke notatie en grootteordes te werken, van de onderbouw tot de bovenbouw. Maar je moet wel weten waar het vandaan komt, wat het precies meet en wat niet.

Shannon-getal

Voorzichtige schatting, ongeveer 10¹²⁰, van het aantal mogelijke schaakpartijen, voorgesteld door de Amerikaanse wiskundige en ingenieur Claude Shannon in het artikel « Programming a Computer for Playing Chess », gepubliceerd in 1950 in het tijdschrift Philosophical Magazine.

Het Shannon-getal: waar komt de berekening vandaan?

Claude Shannon (1916-2001) staat bekend als grondlegger van de informatietheorie. In 1950 publiceerde hij een van de eerste artikelen over het programmeren van een computer om schaak te spelen. Om aan te tonen dat een machine niet zomaar alle reeksen zetten kan doorrekenen, maakte hij een snelle schatting:

1. In een typische stelling zijn er ongeveer 30 legale zetten. Dit aantal blijft grofweg constant gedurende een groot deel van de partij.
2. Een zet van wit gevolgd door een zet van zwart geeft dus ongeveer 30 × 30 = 900 mogelijkheden, die Shannon afrondt op 10³.
3. Een typische partij duurt ongeveer 40 zetten (40 zetten van wit en 40 van zwart) tot een speler opgeeft.
4. Het aantal reeksen zetten is dus ongeveer (10³)⁴⁰ = 10¹²⁰.

Shannon voegt eraan toe dat een machine die één variant per microseconde zou onderzoeken, meer dan 10⁹⁰ jaar nodig zou hebben om zijn eerste zet te berekenen. Hij concludeert dat een schaakprogramma stellingen moet kunnen evalueren en de te onderzoeken varianten moet kiezen, net zoals een menselijke speler.

Partijen en stellingen: twee verschillende getallen

Verwar het aantal partijen (reeksen zetten) niet met het aantal stellingen (opstellingen van de stukken op het bord). Eén en dezelfde stelling kan door miljoenen verschillende partijen worden bereikt.

Shannon schatte het aantal stellingen met de formule 64! / (32! × 8!² × 2!⁶), die telt op hoeveel manieren de 32 beginstukken over de 64 velden kunnen worden geplaatst; het resultaat is ongeveer 4,6 × 10⁴², wat hij afrondde tot « ongeveer 10⁴³ ». De moderne schatting van John Tromp, (4,82 ± 0,03) × 10⁴⁴ legale stellingen, is op een andere manier verkregen: door twee miljoen stellingen willekeurig te trekken uit een verzameling die men kan tellen, en vervolgens na te gaan welke daadwerkelijk in een partij kunnen voorkomen, met hulp van Peter Österlund voor de computeranalyse.

De eerste zetten: een exacte telling

Aan het begin van de partij kan men exact tellen. Wit heeft 20 mogelijke zetten (16 pionzetten en 4 paardzetten). Zwart ook. We krijgen:

Door een programma herberekende waarden vanaf de beginstelling (telling van alle legale reeksen zetten).

Na slechts twee zetten van elke kant overschrijdt men al 197 000 mogelijke reeksen. De vermenigvuldigingsfactor neemt daarna toe, omdat de stukken uitkomen en meer keuze hebben: dat rechtvaardigt de veronderstelling van ongeveer dertig zetten per stelling.

Waar komt de schatting van 10¹²³ vandaan?

In 1994 herhaalde de Nederlandse onderzoeker Victor Allis de berekening met andere uitgangspunten: ongeveer 35 mogelijke zetten per stelling en partijen van 80 halve zetten (40 zetten van elke kant). We krijgen 35⁸⁰. Om dit in een macht van 10 uit te drukken gebruiken we de decimale logaritme: 80 × log(35) ≈ 80 × 1,544 ≈ 123,5. Daaruit volgt de grootteorde van 10¹²³. De methode is precies die van Shannon, alleen de parameters veranderen, wat laat zien hoezeer het resultaat van de uitgangspunten afhangt.

Met Shannons exacte parameters is 900⁴⁰ overigens ongeveer 10¹¹⁸ en niet 10¹²⁰: het afronden van 900 naar 1000 geeft het mooie ronde getal. Voor een zo gigantische grootteorde maakt het in de praktijk geen enkel verschil.

Hoe leg je het uit in de klas

Het Shannongetal is ideaal om machten van 10 te oefenen, een onderwerp uit het eerste jaar van het secundair (4^e). Enkele ideeën:

• Het getal opschrijven: 10¹²⁰ schrijf je als een 1 gevolgd door 120 nullen. Laat de leerlingen het op het bord schrijven… en meet de tijd die daarvoor nodig is.
• Rekenen met machten: (10³)⁴⁰ = 10^{3 × 40} = 10¹²⁰ is een directe toepassing van de regel (a^m)ⁿ = a^{m × n}.
• Grootteorden vergelijken: 10¹²⁰ gedeeld door 10⁸⁰ geeft 10⁴⁰. Zelfs als elk atoom in het heelal een computer was, zou elk ervan nog 10⁴⁰ partijen moeten verwerken.
• De uitgangspunten bespreken: waarom 30 zetten per stelling? waarom 40 zetten per partij? Wat verandert er bij een partij van 60 zetten? (Antwoord: (10³)⁶⁰ = 10¹⁸⁰.)

Het aantal korrels op het schaakbord van Sissa, ongeveer 1,8 × 10¹⁹, lijkt daarnaast minuscuul: de vergelijking van beide is een goede oefening. Zie de berekening van het schaakbord van Sissa.

Kan men schaken « oplossen »?

Een spel oplossen betekent met zekerheid weten welk resultaat (overwinning voor wit, voor zwart of remise) een perfecte partij aan beide kanten oplevert. Het Shannon-getal laat zien dat dit niet kan door alle partijen na te gaan. Computers hebben echter alle stellingen met weinig stukken opgelost, dankzij eindspeltabellen. Om te weten hoe ver men met de vraag is, vroeg Le Palais des Échecs zich af of schaken ooit opgelost zal kunnen worden.

Het Shannon-getal en de andere grote getallen van het schaakbord

Het schaakbord is een kleine fabriek van grote getallen: 2⁶⁴ − 1 korrels van Sissa, meer dan 26 000 miljard gesloten paardenrondes, 92 oplossingen voor de acht dames, 204 vierkanten… Vind ze terug op onze pagina de grote puzzels van het schaakbord.