Sic. Jaargang 6

[p. 68]

Rubrum
* Jaap van den Herik
Rijksuniversiteit Limburg/Rijksuniversiteit Leiden

Het is jammer dat schakers zo eigenwijs zijn, want nu zoeken ze allemaal op een totaal verschillende manier naar de waarheid in het spel. Natuurlijk, het komt de diversiteit ten goede, maar niet de kans op het vinden van een definitief antwoord. Het liefst had ik boven deze bijdrage, al naar gelang de uitkomst van het zoekproces, gezet; ‘1-0’, of ‘Toch Remise’, ofwel ‘Verrassend Verloren’. Nu dit nog niet kan beperk ik mij tot de huidige titel Rubrum. Dat betekent niets anders dan ‘opschrift boven een wet of onderdeel van de wet’. Oorspronkelijk werd het in rode inkt geschreven (ruber betekent rood).

[p. 69]

Wetten

Toen ik in 1980 na het Interpolistoernooi een interview had met Robert Hübner over de ontwikkelingen en mogelijkheden van het computerschaak, vertelde hij: ‘Volgens mij moet je onderzoek doen naar de krachtwetten, die bij het schaken gelden. Want schaken is natuurlijk een spel van krachten. Er bestaat op het bord tussen de wederzijdse stukken altijd een verhouding van krachten. Deze verhouding voldoet aan wetten, net als in de fysica, en naar deze wetten moet je onderzoek doen, je moet ze formuleren en omzetten in computertaal. Dat is de opgave en volgens mijn informatie is men met deze opgave nog nauwelijks begonnen. Iedereen heeft tot nu toe de “brute-force”-methode gevolgd.’ (4 oktober 1980).

En inderdaad, ook bij computerschaak-onderzoek is het boeiend om te zien hoever de diverse benaderingswijzen uit elkaar lopen. De intelligente methode wordt weggedrukt door de technologie. Maar na die constatering is het vervolgens een uitdaging om te speculeren tot waar de kracht van bruteforce dan wel zal reiken. Het is zeker dat dit veel verder is dan in de schaakwereld lange tijd voor mogelijk is gehouden.

Meningen

Het hierboven geciteerde interview maakt deel uit van een rapport ‘Interviews met de wereldtop’ (Van den Herik, 1982). Tien grootmeesters geven daarin hun mening over de toekomst van het computerschaak. Van hen is het Genna Sosonko de enige geweest die de huidige ontwikkeling in volle omvang zag aankomen en waardeerde: ‘Ik schat de kansen van de schaakcomputer bijzonder hoog, in alle opzichten. Hij wordt een veel sterker speler. Ik ben ervan overtuigd dat hij de mens gaat verslaan’ (26 augustus 1980).

Geen van de andere grootmeesters kwam ook maar in de buurt van een dergelijke stellingname. Dat is natuurlijk niet opmerkelijk, want ze hadden, zoals ze zelf vaak zeggen, geen verstand van computers. Wel opmerkelijk is dat ze zich dikwijls konden voorstellen dat een computer het niveau van 2500 tot 2550 ELO-punten zou bereiken, maar niet verder. Kortom, computers zouden nooit op het niveau van topgrootmeesters kunnen spelen. De knellende vraag is vanzelfsprekend: Waarom zou dat zo zijn? Samen met Adriaan de Groot, een van mijn gewaardeerde promotores, heb ik destijds deze meningen geïnventariseerd en geanalyseerd. Het waarom is daarbij niet beantwoord. Overigens waren wij het op dat punt onderling ook volstrekt met elkaar oneens. De Groot was wat ik nu maar noem een disbeliever, terwijl ik van mening was dat het niet lang meer zou duren alvorens

[p. 70]

ze op grootmeesterniveau zouden spelen. Hoewel de discussie nog steeds gaande is zie ik de toekomst optimistisch tegemoet.

Hoe het ook afloopt, schaken blijft een intrigerend spel, want het zal - denk ik - nooit opgelost worden in de speltheoretische zin (d.w.z. uitslag: 1-0 of remise of 0-1). Daarom denk ik ook dat mensen zich aangetrokken zullen blijven voelen tot het spel, hoewel de motivatie wellicht zal veranderen (b.v. van hartstochtelijke hobbyist naar enthousiaste onderzoeker). Zulk een rode draad over wat mensen en ‘computers’ beweegt (of bewogen heeft) om zich op het schaakspel te werpen is voor De Groot et al. (1991) aanleiding geweest om ervaringen uit vroegere onderzoeken, nl. van De Groot en Prins (omstreeks 1970), en Van den Herik en De Groot (omstreeks 1980) nog eens op een rijtje te zetten.

De kracht van de rij

Hoewel bovenbedoeld boekje geen wetenschappelijke pretentie heeft, lijkt het bijna wel het geval indien we wetenschap beschouwen als het op een rijtje zetten van waarnemingen. Immers, het oplossen van problemen bestaat vaak uit niets anders dan het herschikken van feiten en het er op een andere manier tegen aankijken met het doel om de uiteindelijke waarheid - zo die bestaat - te vinden. In toernooibulletins kunnen we de analyses op deze manier interpreteren. Beroemd zijn in dit verband Hübners analyses; pagina's lang worden varianten gegeven, ondersteund door argumenten en verklaringen. Dit is overigens niet voldoende, want zoals Hübner (1979, p. 110) in het 2e Interpolistoernooiboek bij een 12 bladzijden lange analyse van zijn partij tegen Spasski opmerkt: ‘Toch moeten deze aantekeningen slechts beschouwd worden als een aanzet tot een volledige analyse.’ In gewone taal gesproken betekent het niets anders dan: ‘Ik heb het nog niet allemaal op een rijtje’. Gezien de complexiteit van de stelling is dat menselijk gezien ook onmogelijk. Zou een computer daarbij misschien uitkomst kunnen bieden? Voor de stellingen waar Hübner het over had voorlopig nog niet, maar voor heel veel andere stellingen wel.

Het type stelling waar we dan aan denken is het eindspel. Daar is het soms mogelijk om alles uit te tellen, een uitputtende opsomming te geven. Dit betekent dat alle mogelijke stellingen met een bepaalde stukkenconfiguratie in een lijst gezet worden, voorzien van een getal (de afstand tot het einddoel, b.v. mat of stukwinst). Met brute kracht dendert het rekenproces dan voort: uitgaande van alle matstellingen worden de mat-in-1 stellingen berekend, daarna de mat-in-2, mat-in-3 stellingen, etc., totdat er geen opvolgers meer zijn. We zeggen dan dat de maximin is bereikt. Dat is het maximum

[p. 71]

aantal zetten dat minstens nodig is om vanuit de meest ongunstige stelling in zo'n eindspel het doel te bereiken. In computertermen hebben we dan een database geconstrueerd.

Waarheid zonder wetten

Sinds Ströhlein (1970) worden zulke databases geconstrueerd. Dit is in de loop van de tijd gebeurd voor 3-stukken-eindspelen, alsook voor 4- en 5-stukken-eindspelen. Nu zijn de 6-stukken-eindspelen aan de beurt. De eerste in deze soort was Timman-Velimirović (Van den Herik et al., 1987), maar hier stonden nog 2 pionnen vast. Onlangs heeft Lewis Stiller (Baltimore, USA) met behulp van een supercomputer (een connection-machine CM-2) een database geconstrueerd voor het KRBKNN- eindspel (Toren en Loper tegen twee Paarden).

Hiermee zijn we in de klasse eindspelen gekomen waar Averbach, Chéron, Euwe of Fine geen zinnig woord meer over zeggen. En de computer? Ach, die zegt dat het maximum aantal zetten om winst te forceren vanuit de meest ongunstige stelling 223 zetten duurt. Hierbij wordt vanzelfsprekend afgezien van de 50-zettenregel.

Laten we voorlopig eens aannemen dat de computer gelijk heeft, dan zijn er twee vragen: (1) Wat doen we met de 50-zettenregel? en (2) Aan welke wetten gehoorzamen de zetten van de database? Het antwoord op de eerste vraag laat ik graag aan de FIDE over. De tweede vraag is bovendien veel interessanter. We hebben immers de situatie dat we in elke stelling de beste zet (eventueel beste zetten) weten, maar niet weten waarom dit de beste zet is (anders dan dat het de snelste weg naar het doel is). Maar mensen (grootmeesters en schaakstudenten) willen het eindspel doorgronden in termen van concepten, zoals penningen, vorken, tempo-dwang, lijnruiming, afsnijden, etc. Dit is derhalve de nieuwe uitdaging zowel voor schaaktheoretici als voor computerschaak-onderzoekers. Zou een programma zulke concepten kunnen vinden en er passend mee om kunnen gaan? Zo geschreven, lijkt het allemaal begrijpelijk, maar het besef over de moeilijkheidsgraad, breekt pas ten volle door bij het naspelen van de winstweg. In de onderstaande variant worden equi-optimale zetten tussen haakjes aangegeven.

Wit: Ka7, Tb2, Lb3

Zwart: Kd3, Pc6, Pd6

Wit aan zet.

[p. 72]

Winst in (223 + 19) zetten.

De volgende variant is afkomstig van Stiller (1991).

1. Ka6 Pb4 2. Ka5 Pc6 3. Ka4 Pc4 4. Th2 Pb6 5. Ka3 Pc4 6. Ka2 Pb4 7. Ka1 Pe5 8. Kb2 Pc4 9. Kc1 Kc3 10. Ld1 Pd3 11. Kb1 Pd2 12. Ka1 Pb3 13. Ka2 Pbc5 (Pb4) 14. Ka3 (Th3 Th4 Th7 Th8) Pb4 (Pe1) 75. Th3 (Th4 Th7 Th8 Tg2) Pbd3 16. Lg4 (Lh5) Kd4 (Kc4) 17. Lf5 (Lc8) Pf2 18. Th6 (Tg3) Pfd3 19. Ka2 Ke5 (Kc3) 20. Lg6 (Lh7) Kd4 21. Kb1 Kc3 22. Lh7 Kd2 23. Th2 (Lg8) Kc3 24. Lg8 Kd4 (Pe4) 25. Kc2 Pb4 26. Kd1 Pe4 27. Le6 Ke3 28. Lf5 (Th3) Pd5 29. Kc1 (Lc8 Th4 Th8) Pd6 (Pc5) 30. Ld7 (Lg4) Kd4 31. Kb2 Pe3 (Pc4) 32. Th4 (Th5) Kd5 33. La4 Pdf5 (Pe4 Pef5) 34. Th8 Pd6 35. Th5 Kd4 36. Lc6 (Kb3 Th4) Pdc4 (Pe4) 37. Kb3 Pd2 38. Kb4 Pe4 39. La8 Pc2 40. Kb5 Pe3 (Pa3) 41. Kc6 Pf6 42. Th4 Ke5 43. Kc5 Pd7 44. Kb5 Pf6 45. Lh1 Pf5 46. Ta4 Pd6 (Pe3) 47. Kc5 Pfe4 48. Kc6 Pg3 49. Lg2 Pde4 50. Ta8 Kd4 51. Td8 Ke5 52. Td5 Kf4 53. Ta5 Pc3 54. Kc5 Pf5 55. Lc6 (Lb7 La8) Pe3 56. Kd4 (Kb4) Pe2 57. Kd3 Pc1 58. Kc3 Pe2 59. Kb4 Pf5 60. La8 Peg3 (Pd4) 61. Kc3 (Kc4) Pe4 62. Kd3 Pg5 63. Lc6 (Ld5) Pf7 64. Ta4 Ke5 65. Ta7 (Le8) P5d6 66. Ta8 (Ta6 Ta5 Ta2 Ta1 Ld7) Kf4 67. Ta4 Ke5 68. Ld7 Pb7 69. Te4 Kd6 70. Td4 Ke5 71. Lc6 Pbd6 72. Lg2 Pf5 73. Te4 Kd6 74. Ta4 Ke5 75. Lh3 Pg3 76. Tg4 Pf5 77. Te4 Kf6 78. Te1 (Ta4) P7d6 79. Te2 Kg7 (Kg5 Kf7 Kg6) 80. Te5 (Tc2) Kf6 81. Td5 (Tc5) Ke6 82. Tc5 Kf6 83. Ke2 Pd4 84. Ke3 Pe6 85. Td5 Pc4 86. Kf2 Pg7 87. Ke2 Pe6 88. Tf5 Ke7 89. Kd3 Pb2 90. Kc3 Pa4 91. Kb4 Pac5 92. Kc4 Pd7 93. Ta5 Pb6 94. Kc3 Pc5 95. Kb4 Pd3 96. Kb5 Pd5 (Pf4) 97. Lf5 P3f4

[p. 73]

98. Kc6 Kf6 99. Lb1 Pe3 100. Ta6 (Ta8) Pe2 101. Kd7 Ke5 102. Te6 Kf4 103. Te4 Kf3 104. Te8 Pg3 (Kf4) 105. Ke6 (Kd6 Tf8 Td8) Pef1 106. Lc2 (Kd5 Td8) Kf4 107. Tf8 (Td8 Ta8) Ke3 108. Td8 Ph2 109. Ta8 (Kd5) Pgf1 (Pf3) 110. Ta3 (Ld1 Kd5) Kf4 111. Ld1 Pd2 112. Kd5 Phf1 113. Kd4 Pg3 114. Ta4 Pde4 115. Kd5 Ke3 116. Ke5 Kd2 117. Lh5 Pc5 118. Ta2 Ke3 119. Lg6 Pd7 120. Kd6 Pf6 121. Ta3 (Ke6) Kf4 122. Ta4 (Ke6) Kg5 123. Ld3 Pg4 124. La6 (Ke6) Pf5 125. Ke6 Pg7 126. Kf7 (Kd5) Pf5 127. Le2 Pgh6 128. Ke6 Pg3 129. Ld1 Pgf5 130. Tb4 Pe3 (Pg3) 131. Lf3 Pef5 (Pf1) 132. Lg2 Pg7 (Pe3) 133. Kd5 Ph5 134. Tb5 Kf4 135. Ke6 Pg3 136. Tb4 Kg5 137. Lh3 Pe2 (Kg6) 138. Ke5 Pg3 139. Ta4 (Kd5) Pe2 (Pf7) 140. Le6 Pg3 141. Ld7 Pf7 142. Kd4 Pd6 143. Lh3 Pdf5 144. Ke5 Ph6 145. Ta5 Kh4 146. Lg2 Kg5 147. La8 Pg4 148. Ke6 Kf4 149. Ta3 Ph2 150. Lb7 Pe2 151. Ta4 Ke3 152. Te4 Kf2 153. Kd6 Pf3 154. Te8 Ped4 155. Kc5 Kg3 156. Le4 Pe2 157. Lc2 Pf4 (Pd4 Kf2) 158. Kc4 Kf2 159. La4 Pg6 160. Kd5 (Kd3) Pg5 161. Kd4 Pf4 162. Lc6 Pf3 163. Ke4 Pe6 164. Te7 Pc5 165. Kd5 Pb3 166. Le8 Pbd2 167. Lh5 Kg3 (Kg2)

168. Te3 Kf2 169. Td3 Ke2 170. Tc3 Kf2 171. Lg4 Kg2 (Ke2) 172. Td3 (Ke6) Kf2 173. Ke6 Ke2 174. Ta3 Kf2 175. Kf5 Pd4 176. Kg5 Pf1 (Pe2) 177. Td3 Pe2 178. Tf3 Ke1 179. Lh5 Pd4 180. Ta3 Pe2 181. Ta7 (Ta8) Pfg3 182. Lg6 Kd2 183. Tb7 (Td7 Kg4) Ke3 184. Kg4 Pf1 185. Th7 Pd2 186. Te7 Kf2 187. Ld3 Pc1 788. La6 Pdb3 189. Kf4 Pc5 190. Lb5 P1d3 191. Kf5 Pb4 192. Te8 Kf3 193. Le2 Kf2 194. Lh5 (Ld1) Kg3 195. Te3 Kf2 196. Te2 Kg3 197. Td2 Pc6 198. Td6 (Td1) Pb4 199. Ke5 Pbd3 200. Kd4 Pf4 201. Lf7 Pcd3 202. Ta6 Pf2 203. Ta3 (Le8) Kh4 204. Ke3 P2h3 205. Lb3 Kg5 (Kg4) 206. Ke4 Kh4 207. La4 Ph5 208. Lc2 Pg7 (Pf6) 209. Lb3 Ph5 (Pg5 Kg5 Kg4) 210. Ta4 Kg5 211. Kf3 Pg1 212. Kf2 Ph3 213. Kg2 P3f4 214. Kf3 Ph3 215. Ta5 Kh6 216. Ta6 Kg5 217. Le6 (Lf7) P3f4 218. Ta5 Kh6 (Kf6 Kg6) 219. Lf7 Pg6 220. Ta6 (Kg4) Phf4 221. Kg4 Kg7 222. Le8 Kh7 223. Lxg6 Pxg6

en het eindspel Toren tegen Paard is vanaf de 223e zet gewonnen in 19 zetten.

De computerresultaten geven aan dat het KRBKNN-eindspel in 96% van de gevallen gewonnen is (hierbij meegeteld alle stellingen waarin zwart schaak staat, ja schaakwereld en computerschaakwereld kijken totaal anders tegen de zaken aan). De database bevat meer dan 6 miljard stellingen. Derhalve ligt de uitdaging in het reduceren ervan: het opsporen van de gemeenschappelijke kenmerken.

[p. 74]

Waarheid met wetten

Natuurlijk heeft Hübner gelijk als hij stelt dat het om de wetten gaat. Dat was ook de stellingname van Sosonko (1984) toen hij zich uit het groot-meestertoernooi in Amsterdam terugtrok vanwege een zijns inziens incorrecte toepassing van het Zwitserse systeem. De wetten waren overtreden en dat kan niet. Afgezien van de discussie die toen volgde over de pure indeling op grond van regels, ging het er tevens om of een computer zou kunnen inspelen op speciale (regel-gebonden!) indelingen voor het behalen van grootmeesternormen en meesternormen. Mijn stelling was destijds dat (1) een computerprogramma feilloos de indeling volgens het Zwitserse systeem zou kunnen uitvoeren en (2) dat intelligente technieken het mogelijk zouden maken rekening te houden met het hebben van (groot)meesternormen volgens van te voren vastgestelde vuistregels. Toch was deze stelling niet zo gemakkelijk te bewijzen. Het maken van een feilloos programma gaf bijvoorbeeld problemen bij de 13e ronde in een toernooi van 150 deelnemers (Van den Herik, 1988). Een poging om bedoelde vuistregels te verwezenlijken in een programma bleef vervolgens achterwege. Zou het allemaal toch te hoog gegrepen zijn?

Neen, volhardend onderzoek en een paar slimme ideeën hebben ook op dit gebied aangetoond dat computerprogramma's tot veel in staat zijn. In augustus 1991 heeft Norbert J.A. Jansen (Erasmus Universiteit Rotterdam) in een doctoraal scriptie aangegeven dat het Zwitserse systeem op een geheel andere manier benaderd moet worden. (Voor insiders: transformeer het indelingsprobleem naar het gewogen matching probleem en pas het algoritme van Lawler (1976) toe, dat heeft een polynomiale orde, O(n³), in plaats van een exponentiële.) De aanpak van Norbert Jansen maakt tevens de verwezenlijking van speciale regels (zoals aan regels gebonden gunstige indelingen in de laatste twee ronden) mogelijk.

Hoewel in 1984 menigeen niet blij was met het optreden van Sosonko, wil ik hem hierbij graag bedanken: ‘Genna, je gedrag was een waarschuwing voor wedstrijdleiders, een onaangename verrassing voor de andere deelnemers, maar ook een aansporing voor wetenschappelijke onderzoekers. Derhalve alsnog bedankt voor je impliciete suggesties.’

Ubi Caissa, ibi Computer

De rode draad door deze bijdrage wordt gevormd door Ubi Caissa, ibi Computer (waar het schaakspel is, daar is de computer). Sinds 1950 zijn ze onlosmakelijk met elkaar verbonden, maar het heeft tot 1980 geduurd alvorens de schaakwereld notitie nam van computers. En pas sinds kort

[p. 75]

worden zij voor vol aangezien. Ik ben benieuwd welke wetten computers over tien jaar ontdekt hebben.

Referenties

A.D. de Groot, D. Hartmann, H.J. van den Herik, F. Medendorp en L. Prins (1991). Mens en Computer achter het Schaakbord. Van Spijk, Venlo (in bewerking).

H.J. van den Herik (1982). Interviews klasse 3: de wereldtop. Rapport Wiskunde en informatica, Technische Hogeschool Delft.

H.J. van den Herik, I.S. Herschberg and N. Nakad (1987). A Six-Men-Endgame Database: KRP(a2)KbBP(a3). ICCA Journal, Vol. 6, No.4, pp. 163-180.

H.J. van den Herik (1988). ZORBA nog niet in OHRA. Schakend Nederland, Jrg. 95, No. 9, pp. 38-39.

R. Hübner (1979). Hübner-Spasski. 2e Interpolis schaaktoernooi 1978 (red. W.F. Andriessen), pp. 110-121.

N.J.A. Jansen (1991). Reduktie van het Zwitserse systeem op rating naar het Gewogen Matching probleem. Erasmus Universiteit Rotterdam.

Lawler (1976). Combinatorial optimization: Networks and Matroids. Halt, Rinehart and Winston, New York.

G. Sosonko (1984). Open brief. New in Chess Magazine, Vol. 1, No.1, pp. 16-17.

L. Stiller (1991). Some results from a massively parallel retrograde analysis. ICCA Journal, Vol. 14, No. 3.

T. Ströhlein (1970). Untersuchungen über kombinatorische Spiele. Dissertation, Fakultät für Allgemeine Wissenschaften der Technischen Hochschule München.