HET FRUITVLIEGJE VAN DE K.I.

Ik schreef hier een tijdje geleden (zie 'Schaken met God') over het eindspel KTPKPP; koning, toren en paard tegen koning en twee paarden. In het moeilijkste geval waarin dat gewonnen is, kan de sterkste partij op z'n snelst in 262 zetten mat geven. De 'eindspeldatabase'-techniek waarmee die zettenreeks wordt gevonden, knoopt achterwaarts vanuit de matstellingen alle stellingen van een eindspel zodanig aaneen dat men steeds kan zien of mat bereikbaar is en zo ja, hoe ver weg het is.
    Na dat stukje ben ik nog wat ander interessant materiaal over die techniek tegengekomen. Schaken is altijd 'het fruitvliegje van de Kunstmatige Intelligentie' geweest (al zou hier de term 'kunstmatige dommekracht' niet misstaan) maar de databasetechniek is ook toegepast op andere spelen. Met dammen is men een heel eind. De Nederlandse expert op dit gebied, Stef Keetman, is bezig met een database voor de 7-stukken eindspelen (met schaken is men bij 6); met checkers (een 8x8 dam-variant) zit de Canadees Schaeffer al op 9. En het gaat snel verder. De wet van Moore wil dat de capaciteit van computers elke anderhalf jaar verdubbelt, en al zijn de kleinste computer-onderdelen nu slechts zo'n 100 atomen groot, het eind is, aldus Keetman, niet in zicht.
    Vorig jaar deed Keetman in het blad Dammen al de onheilspellende uitspraak dat een 40-stukken-database (van de beginstelling dus) niet nodig is om het damspel geheel te kraken. 'Een eindspeldatabase met zo'n 20 tot 25 stukken zal voldoen om de beginstelling uit te analyseren', schreef hij. Immers, de computer kan ook nog altijd vóóruit rekenen. En op gegeven moment zullen de diepste beginstand-analyse en de verste eindspeldatabase elkaar bereiken. Dan zal men een dammende God hebben. 'Tegen het einde van de volgende eeuw zal het zover zijn,' zegt Keetman. Ik vrees dat hij 2099 bedoelt.
    Verschillende andere spelen zijn al met de database-techniek gekraakt: Qubic (ruimtelijk 4x4x4 boter-kaas-en-eieren), Vier-op-een rij, Go-Moku, het Molenspel. Voor het oude woestijnspel awari (of mancala, dat spel met stenen die over kuiltjes verdeeld moeten worden) is een database gemaakt voor alle eindspelen met 22 steentjes of minder. Een (éénpersoons-)spel dat zich nog verzet tegen kraking is de beroemde '15-schuifpuzzel' van Sam Loyd, de geniale Amerikaanse puzzelbedenker en schaakprobleemcomponist uit de vorige eeuw.

Waar ik de vorige keer niet aan toe kwam is dat uit die databases (nu weer van schaak-eindspelen) ook stellingen te halen zijn waarin sprake is van wederzijdse zetdwang; aan zet zijn kost een half of soms zelfs een heel punt. Zeer recent maakten Nalimov en Wirth ieder een database voor het eindspel KDDKDD; koning en twee dames tegen koning en twee dames. Dat komt een enkele keer voor in de praktijk, en het had kunnen voorkomen in Kasparovs partij tegen de wereld.
    Dit eindspel blijkt in 71 % van de gevallen gewonnen voor degene die aan zet is; niet zo verbazend als je bedenkt dat met zoveel kracht op het bord het initiatief natuurlijk veel waard is. Des te verbluffender is het dat er zelfs met dit materiaal wederzijdse zetdwangstellingen zijn; acht in totaal, spiegelingen niet meegerekend. Als auteur daarvan moet een collectief van experts worden gezien die elkaar via internet vonden: Haworth als initiatiefnemer; Nalimov, Wirth en Stiller als makers van de databases; Elkies en opnieuw Haworth als vinders en controleerders van de zetdwangstellingen. Die zijn:
1. Wit: Ka7, Da3, Dc7; Zwart: Kb1, Db5, Dh6
2. Wit: Ke2, Da4, Dc4; Zwart: Kb2, Db1, Db6
3. Wit: Kh1, Dg2, Dh2; Zwart: Ka1, Da7, Df6
4. Wit: Ka3, Da8, De3; Zwart: Kd1, Df5, Dh4
5. Wit: Kb1, Db4, De4; Zwart: Kd1, Df1, Df2
6. Wit: Kf5, Db5, Db6; Zwart: Kc1, Da1, De1
7. Wit: Ke2, Dc4, Dg2; Zwart: Kb2, Da3, Da7
 
Guy Haworth e.v.a.
Internet 1999
Die laatste is al een erg gekke, maar de allergekste is die van het diagram hieronder.
    Zowel Wit als Zwart kunnen op verschillende manieren schaak geven, maar ze zouden er hun stelling mee verslechteren. Met Wit aan zet is het remise; Zwart aan zet verliest. Als hij de afstand tot mat steeds zo groot mogelijk houdt verliest hij één dame op de twaalfde zet. De aanhalingstekens bij de zetten behoren tot Haworths speciale notatie voor database-eindspelen: '' betekent: enige zet die de winst vasthoudt en ' betekent: enige optimale zet; dat wil zeggen voor Wit een zet die de weg tot mat niet langer maakt, voor Zwart een zet die hem niet korter maakt. 1...De5+' 2.Kg4+'' Kd2' 3.Dh6+'' Kc3' 4.Dac6+' Kb3' 5.Db7+'' Kc2' 6.Dg2+ Kb3' 7.Db6+' Ka2' 8.Da6+' Kb3' 9.Df3+' Dbc3' 10.Dd1+'' Dc2' 11.Dad3+'' met damewinst, en mat op de 21ste zet.
    De vraag 'waarom?' kan hier alleen beantwoord worden met 'daarom'.
    'Het schaakspel wordt achterwaarts ontraadseld door de siliconenreus,' schreef Haworth mij. Maar zo pessimistisch als Keetman is hij niet - en hoeft hij niet te zijn: schaken is nu eenmaal complexer dan dammen. 'Heb echter geen vrees,' voegt Haworth er dan ook aan toe. 'Er zijn meer schaakstellingen dan atomen in het heelal... en voor iedere schaakstelling is gemiddeld minstens één atoom nodig om de diepte ervan vast te leggen. Het is dus onmogelijk een tabel te maken voor het gehele schaakspel.'
    Oef. We spreken hem nader over een eeuw of twee.

© Tim Krabbé, 2000

PS: Van Jack van Rijswijck uit Canada kreeg ik de volgende aanvulling op dit stuk:
"Als Ph.D. student onder Schaeffer en lid van zijn "games research group" in Edmonton heb ik nog wat informatie.
    Wat awari betreft: ik ben zelf betrokken bij een awari-project alhier (zie ook de web pagina http://www.cs.ualberta.ca/~awari). De 22-stukken database voor awari waarvan in het fruitvliegje-stukje gewag wordt gemaakt is al bijna tien jaar geleden berekend door een team aan de universiteit van Maastricht. Inmiddels zitten wij hier al op 35 stukken. Dat begint in de buurt te komen bij de beginstelling, die 48 steentjes bevat. Een awari-spelende God moet er over hooguit een jaartje zijn. Tot die tijd kan ons programma nog altijd gewoon vooruit rekenen totdat het eindspel begonnen is. Dat laatste vindt bij ons dus plaats als er "nog maar" 35 steentjes van de 48 over zijn. Het programma kan moeiteloos zo'n twintig zetten vooruit kijken, aangezien dat in awari iets gemakkelijker is dan in schaken - voor computers dan. Voor mensen is het juist moeilijker, aangezien de zetten niet-lokaal zijn: een enkele zet kan alles op het hele bord veranderen. Het behoeft weinig betoog dat menselijke awari-spelers dus, ietwat eufemistisch uitgedrukt, weinig kans meer maken tegen dit soort bruut geweld."


Index AD Magazine schaakrubrieken
Bovenkant pagina | Hoofdpagina schaken | Hoofdpagina algemene site