Vorige week schreef ik weer eens over de EGTBs; Endgame TableBases waarin alle stellingen met een bepaalde materiaalverhouding zodanig zijn opgeslagen dat altijd de beste zet bekend is. Hoe meer stukken, hoe meer stellingen, en al snel zijn dat er te veel voor de computer. Vrijwel alle eindspelen met zes stukken zijn nu in kaart gebracht; in
De macht van het vierspan berichtte ik over de eerste EGTB met zeven stukken.
Maar Gods algoritme voor de beginstelling kan ook van de andere kant worden benaderd - met alle stukken, maar op een kleiner bord. Voor het 3x3 bord is dat onlangs, onafhankelijk van elkaar, gedaan door de Russische wiskundige
Kirill Kryukov en een Finse Rus,
Aloril.
Een beginstelling is er op zo'n benauwd bord niet, vonden beiden. Bij Kryukov kunnen de pionnen op de eerste twee rijen staan, maar de dubbele stap bestaat niet; bij Aloril kunnen ze alleen op de tweede rij beginnen. Bij beiden promoveren ze op de derde rij; de rokade bestaat uiteraard niet.
Ieder met hun eigen regels construeerden Kryukov en Aloril Gods algoritmetje voor het 3x3 bord, dat bij Kryukov uit iets meer dan driehonderd miljoen stellingen bestaat. In ieder daarvan is de beste zet bekend; de zet die het snelst mat bereikt of dat juist het langst uitstelt - of die de remise vasthoudt.
De langste matvoering in een stelling waarin mat geforceerd kan worden, is 16 zetten: 1.Pxb1 Kxc1 2.Pc3 Lb1 3.Pxb1 Kc2 4.Pc3 Kc1 5.Pa2+ Kc2 6.Pc1 Kxc1 7.Kxb3 Kb1 8.Kc3 Kc1 9.b3P+ Kb1 10.Lb2 Ka2 11.Pa1 Kb1 12.Pc2 Ka2 13.La1 Kb1 14.Kb3 Kc1 15.Lb2+ Kb1 16.Pa3 mat. Varianten kan men op de site van Kryukov testen - iedere stelling kan daar worden opgezocht. Daar zijn ook een paar andere 'mat in 16' stellingen te vinden.
Hier overleeft de eenzame koning maar liefst 16 zetten - na Wits eerste zet is het weer mat in 16 door Zwart. Die moet dan wel twee paarden offeren, één paard halen, en ook nog eens twee dames offeren: 1.Kb3 Pa3 2.Kxa3 Tc2 3.Kb3 Kc1 4.Ka3 Db1 5.Kb3 a1P+ 6.Ka3 Da2+ 7.Kxa2 Pb3 8.Kxb3 Kb1 9.Ka3 Ka1 10.Kb3 Tc1 11.Ka3 Tb1 12.Kb3 c2 13.Ka3 c1D 14.Kb3 Dc2+ 15.Kxc2 Ka2 16.Kc3 Tc1 mat.
Hoe nu verder? Op de site van Aloril discussiëren de twee grootmeesters van het 3x3 schaak over de toekomst. Kryukov is bezig aan het 3x4 bord, en heeft daar alle EGTBs met zeven stukken, en die met acht stukken zonder pionnen al af. Aloril gelooft dat 4x4 schaak oplosbaar is, zij het met andere algoritmen en krachtiger hardware. Ook 5x5-schaak mèt een beginstelling zal zo oplosbaar zijn.
Maar het doel blijft 8x8, en 32 stukken. Is dat in theorie haalbaar? Er zijn 2.28*1046 stellingen - minder dan het aantal atomen in de aarde (9*1049), maar toch teveel. De Amerikaanse AI-deskundige Manny Rayner mailde me over zijn SF-achtige idee om een asteroide om te bouwen tot een computer met genoeg geheugen voor een database van het hele schaakspel. Aloril had dat idee ook, en
berekende in een artikel
Solving chess zelfs hoe groot die asteroide zou moeten zijn. Uitgaande van 1000 atomen per opgeslagen stelling, zou Ceres met zijn diameter van 950 kilometer al bijna tweemaal de benodigde massa hebben. Maar met slimmere algoritmen, rekent Aloril voor, zou misschien één kilo van het juiste materiaal genoeg kunnen zijn om de oplossing van het hele schaakspel te bevatten.
Toch maar weer ivoor?
© Tim Krabbé, 2005
Index AD Magazine schaakrubrieken
Bovenkant pagina |
Hoofdpagina
schaken |
Hoofdpagina
algemene site