Ken Thompson was de ontwerper van de Belle schaakcomputer (“De Koning”, J.H. Donner, pp.364-367, 1987; NRC 1982) en de inspirator van de Hydra (New in Chess 2009/1). Verder bouwde hij databases voor eindspelen met 4 en 5 stukken met behulp van retrograde analyses. Zo bewees hij in 1983 tot verrassing van velen dat het eindspel van KLLKP altijd gewonnen is. Thompson heeft in de schaakwereld een revolutie ontketend. En niet alleen in die wereld. In “Ken, Unix and Games” beschrijft Dennis Ritchie (2001) hoe Thompson’s belangstelling voor spelletjes naar het beroemde Unix operating systeem leidde. In 1983 kregen Thompson en Ritchie hiervoor de Turing prijs. Zo af en toe maakte Thompson tijd vrij voor wiskunde van het simpelste soort. Op verzoek van zijn Bell Labs collega Neil Sloane bepaalde hij voor “The Encyclopedia of Integer Sequences” (1995) het aantal mogelijke schaakpartijen na n halve zetten (n=<8): a(0) = 1, a(1) = 20, a(2) = 400, 8902, 197281, 4865617, 119060679,.... , (oeis.org/classic/A006494; was eerst oeis.org/classic/A007545). De term a(0) = 1 verwijst naar de klassieke beginstand, a(1) = 20 geeft het aantal mogelijke beginzetten van wit weer en a(2) = 20*20 is het aantal manieren waarop zwart hierop kan reageren. Daarna worden de termen aanzienlijk minder overzichtelijk.
In mijn column “Schaken is Wiskunde (2)” van 15 maart 2009 heb ik, in nauwe samenwerking met Willem Broekman, een andere “simpele schaakreeks” toegelicht. Dat was de reeks die het aantal partijen dat na n halve zetten voorbij is, d.w.z. wit of zwart staat mat, weergeeft: a(1) = 0, 0, 0, 8, a(5) = 347, … (oeis.org/classic/A079485). Er zijn nog veel meer “schaakreeksen”. Zoeken op de OEIS, “The On-Line Encyclopedia of Integer Sequences” (oeis.org), leverde de volgende resultaten op: chess: 121; kings: 276; queens: 232; rooks: 85; bishops: 55; knights: 154; pawns: 19. Imposante aantallen. Een enkel voorbeeld: wat is het minimale aantal paarden dat nodig is voor het bedekken van een n x n schaakbord? Deze vraag leidt naar de reeks a(1) = 1, 4, 4, 4, 5, 8, 10, 12, 14, 16, 21, … , (oeis.org/classic/A006075). Voor een 8 x 8 bord zijn a(8) = 12 paarden nodig, zie de figuur.
Boeiend is dat “schaakreeksen” niet alleen op schaakborden maar overal op kunnen duiken. Tijdens mijn onderzoek naar de eigenschappen van de hogere orde exponentiële integralen liep ik vorig jaar twee keer een “schaakreeks” tegen het lijf. De eerste “schaakreeks” was die van het aantal manieren waarop een witte en een zwarte toren, die elkaar niet aanvallen, op een n x n schaakbord geplaatst kunnen worden: a(1) = 0, 4, 36, 144, 400, 900, 1764, … , (oeis.org/classic/A035287).
De tweede “schaakreeks” die ik tegenkwam was die van het aantal mogelijke koning zetten op een (n+1) x (n+1) schaakbord: a(0) = 0, 12, 40, 84, 144, 220, 312, … , (oeis.org/classic/A033586). Dergelijke reeksen bestaan ook voor de andere schaakstukken. Tim Krabbe heeft hier op zijn website een aardig item over (xs4all.nl/~timkr/chess2/diary_12.htm; item 221). Voor een 8 x 8 schaakbord geldt dat toren = paard + loper (896 = 336 + 560) en dat dame = toren + loper (1456 = 896 + 560) hetgeen aardig spoort met de werkelijkheid. Zie de figuur.
Uiteraard rees bij mij de vraag of ik aan de reeds bekende “schaakreeksen” er eentje toe zou kunnen voegen. Dat is gelukt. Mijn spiksplinternieuwe reeks is de “Fischer Random Chess” reeks: a(0) = 960, a(1)=18882, a(2)=371766, 8224986, 181106865, 4433072982, … , (oeis.org/classic/A157851). De eerste term a(0) = 960 geeft het aantal beginposities van het “Fischer Random Chess” weer. Als we deze 960 schaakborden naast elkaar leggen met op ieder bord een andere beginpositie dan kunnen we ons afvragen wat de som is van het aantal mogelijke beginzetten van wit op alle borden. Dit getal wordt bepaald door pion- en paardzetten én rokades! Het aantal paardzetten hangt af van waar de twee paarden op het bord staan. Als er een of twee op de hoekvelden staan neemt het aantal mogelijke pion- en paardzetten af van 20 naar 19 of 18. Rokeren in de beginstelling lijkt op het eerste gezicht onzinnig maar bij het Fischer Random Schaak is het in sommige stellingen mogelijk zoals Richard Pijl en zijn schaakmachine De Baron mij lieten weten. Met de koning op d1 en een toren op c1, hetgeen 72 keer voorkomt, en met de koning op f1 en een toren op g1, hetgeen 90 keer voorkomt, mag er volgens de Fischer Random Chess regels gerokeerd worden. Rokeren komt hier neer op het van plaats verwisselen van de koning en genoemde toren. De waarden van de a(1) en a(2) termen zijn met enige moeite met de hand te berekenen maar voor het bepalen van de waarden van a(3), a(4) en a(5) had ik de zeer gewaardeerde hulp van Richard Pijl en zijn Baron nodig (xs4all.nl/~rpijl/html/the_baron.html). Petje af voor die laatste twee.
Open vragen zijn de waarden van a(6), a(7), etc.. Ook de reeks van het totale aantal partijen dat op alle 960 borden na n halve zetten voorbij is is nog onbekend. Dit lijkt me typisch iets voor Willem Broekman om uit te zoeken en wellicht dat iemand anders (Richard?) hem bij dit monnikenwerk een handje kan helpen. Ik pas deze keer.