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 |
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 |