De Schaakcomputer

Vincent Diepeveen

Mijn dank voor de vele positieve reacties op mijn vorige twee bijdragen aan dit clubbiad. Het verplicht mij eigenlijk tot het starten van een vaste rubriek. De vraag of deze artikeltjes ook gepubliceerd mogen worden in andere clubbladen, onderstreept de behoefte die de meeste schakers hebben aan informatie over schaakprogramma’s.

Een groot probleem is namelijk de geweldige specialisatie in deze branche: kreten als forward pruning, transpositiontables zullen de meeste ‘computerexperts’ doen duizelen, laat staan anderen. Het is duidelijk dat er nog veel te vertellen valt. In deze rubriek zal ik beginnen door over mijn eigen programma te vertellen onder het genot van een koele frisdrank en op de achtergrond een leuk muziekje. Ook zal ik er mijn zeer ‘objectieve’ mening over de match Kasparov – Deep Blue er in verwerken. Ook zal ik de dubieuze positionele/strategische opzet van Deep Blue nog eens nader toelichten en vergelijken met de opzet van mijn programma.

Geboorte

Voor een student informatica die kan schaken komt natuurlijk onvermijdelijk het moment dat je nadenkt over het schrijven van een eigen schaakprogramma. Als informaticastudent kun je wat je in theorie leert dan uitstekend toepassen.

Na wat experimenten met Remy de Ruijsscher in deze richting, ben ik begonnen aan mij eigen schaakprogramma, heel origineel naar mijzelf genoemd: Diep.

Voor de historici: Diep begon zetten te produceren rond februari 1994. Echt grote prestaties verrichtte mijn programma rond die tijd nog niet. Veel tijd heb ik destijds besteed aan de stelling in diagram 1 (zie links). (De oplossing vindt u aan het einde van dit artikel.)

De eerste versie van Diep heeft voor deze stelling meer dan 3 minuten nodig. Ter vergelijking, de huidige versie heeft hiervoor 1/50 deel van een seconde nodig.

.

.

Langzaam verbeteren

Diep is heel wat verbeterd sinds de eerste versie. Zo ook mijn ideeën over hoe een schaakprogramma te schrijven. Dit komt doordat er talloze manieren zijn waarop een schaakprogramma geschreven kan worden. De manier waarop Diep geschreven wordt valt het beste te omschrijven met: “Experimenteer en behoudt het goede”.

Net voor het Nederlands Kampioenschap 1994 pluisde ik voor Diep diagram 2 (links) uit. Zwart aan zet wint materiaal. (De oplossing vindt u aan het einde van dit artikel.)

Als lezers mij in de toekomst betrappen op het feit dat ik mijzelf tegenspreek, dan komt dit doordat ik in de tussenliggende tijd door experimenten tot andere ideeën ben gekomen.

Een goed voorbeeld van nieuwe ideeën is diagram 2 (zie hierboven). Daarin brengt een aftrek-aanval aan wit de beslissende klap toe. De hele variant is voor een computerprogramma 6 ply (na de laatste stille zet tellen slagzetten en schaakjes niet meer mee), zo berekende ik. Echter, een programma als Genius vindt dit soort problemen al op 3 ply diepte. Ik probeerde dus dit probleem eerder te laten vinden door mijn programma, zon 1.5 jaar geleden. Dat lukte natuurlijk wel. Gevolg was echter dat mijn programma niet meer zo diep rekende; zo’n pakweg 5 ply op een 486 (1×66. 5 ply is vertaald naar menselijke normen vrij weinig: 3 zetten voor jezelf, en 2 voor de tegenstander. Een programma dat niet zo diep rekent, ziet niet erg snel de positionele gevolgen in van de variant die het programma wil spelen.

Zo diep mogelijk rekenen

Tegenwoordig probeer ik mijn programma zo diep mogelijk te laten rekenen, maar met behulp van zo goed mogelijke kennis, waarbij de kennis niet wordt opgeofferd om dieper te rekenen. Diagram 2 wordt nu niet op 3, 4 of 5 ply opgelost, maar op de gebruikelijke diepte 6. Echter, die 6 ply worden nu stukken sneller afgelegd dan de 4 ply die mijn programma er in 1994 voor nodig had om de goede oplossing te vinden. In 1994 was 4 ply zeker 2 minuten. Nu is 6 ply in deze stelling nog geen halve minuut. Side-effect (vrij vertaald: bijverschijnsel) hiervan is dat ook positioneel beter gespeeld wordt.

Erg positief was ook de aanschaf van een snellere computer: een Pentium 100. Deze computer is pakweg 3,5 keer zo snel als mijn vorige computer (486 dx66). Het gevolg is dat er alleen al 1 ply dieper gerekend wordt door de aanschaf. Daarnaast heb ik allerlei verbeteringen in mijn programma aangebracht. Tegenwoordig is hierdoor een ingewikkeld tactisch probleem als diagram 3 een kwestie van enkele minuten:

Diagram 3, wit aan zet wint. (De oplossing vindt u aan het einde van dit artikel.)

Naar verwachting zal over een jaar dit probleem wel weer een stuk sneller worden opgelost. Er zijn drie manieren om een probleem sneller op te lossen:

1. dieper rekenen
2. speciale extensie
3. betere evaluatie

Een speciale extensie is op grond van bepaalde kenmerken de stelling dieper bekijken dan normaal het geval is. Een extensie die door bijna alle programma’s wordt gebruikt is de schaakextensie. Rekenvoorbeeld: na (vanuit de beginstelling) 1.e4 d6 2.Pf3 Pf6 3.c3 Pxe4? kan wit het stuk winnen met Da4+ en Dxe4. Da4+ is een schaakje. Een programma zonder extensies, die dit ziet na 2 ply, zal met schaakextensie dit zien op 1 ply: Da4+ is een schaakje, schaakjes worden geëxtend. En dus heeft een programma een ply minder nodig om de oplossing te vinden. Natuurlijk zult u nu denken, waarom niet alles interessante dingen extenden? Wel, extenden heeft een nadeel: ook onzin als 1.e4 d5 2.Lb5 c6 3.Lxc6 etc. wordt geëxtend. Hierdoor kan een programma minder diep rekenen.

De huidige opzet van Diep is dusdanig dat er in principe zo min mogelijk wordt geëxtend. Er wordt getracht zo diep mogelijk te rekenen.

Dieper rekenen kan door je programma slimmer te maken, bijvoorbeeld door te zorgen dat je over het algemeen meteen de beste zet bekijkt in een stelling, in plaats van eerst een domme zet. Of de meest toegepaste truc, je programma sneller maken (door het handiger op te schrijven, of door zoveel mogelijk kennis over het schaakspel weg te laten).

Ook de verbeterde evaluatie en de toegenomen kennis hebben ervoor gezorgd dat Diep stukken beter is gaan spelen. Je kunt natuurlijk alleen een leuke combinatie uithalen als je je in een gewonnen positie bevindt! De verbeteringen in mijn programma het afgelopen jaar hebben te maken met met name rekendiepte en kennis.

Momenteel geloof ik in een combinatie van kennis en rekendiepte. Dit heel anders dan de programmeurs van Deep Blue. Dezen geloven alleen maar in rekendiepte. Terwijl ik probeer juist zoveel mogelijk kennis erin te stoppen (desnoods ten koste van snelheid van mijn programma, en dus rekendiepte), is voor hen betere kennis: “Handig, maar niet de eerste prioriteit”.

Dit heeft te maken met de manier waarop ik mijn programma heb geschreven, en de manier waarop zij hun programma hebben geschreven: ik laat mijn programma als deze op n ply rekent eerst n halve zetten uitvoeren, en bekijk vervolgens de stelling heel uitgebreid. Deep Blue daarentegen heeft van te voren tabellen gemaakt, voor elk stuk een tabel met 64 velden. Voor n ply betekent dit dan n berekeningen om de evaluatie te verkrijgen: als een loper van c1 naar b2 wordt gezet dan hoeven zij slechts de score van b2-c1 bij hun evaluatie op te tellen om de nieuwe evaluatie te verkrijgen. Dit is natuurlijk een eenvoudige bewerking. Maar heeft enige nadelen, die vrij duidelijk lijken: a) er wordt geen rekening gehouden met activiteit, b) als na n ply de stelling er heel anders uitziet, dan wordt dit niet herkent door de evaluatie.

Evenwicht tussen kennis en rekenen

Dit is eigenlijk het belangrijkste verschil tussen mijn programma en de meeste andere programma’s. Programma’s als Fritz gebruiken een soort van mengvariant: positionele elementen worden uit de tabellen gehaald, zoals activiteit, mobiliteit, maar andere ‘goedkoop’ te berekenen elementen zoals vrijpionnen en koningsveiligheid, wordt over het algemeen wel pas berekend nadat de n ply is uitgevoerd.

Zoals gezegd, de meeste belangrijke positionele voordeeltjes wordt bij programma’s als bijvoorbeeld Fritz, Genius, Kallisto, Wchess, Ferret uit tabellen gehaald. Positionele stellingen hebben dit soort programma’s dan ook erg veel moeite mee, terwijl ze tactisch vaak juist weer een stuk sneller zijn.

Als u een ingewikkelde (afgebroken) stelling heeft, waar tactisch niet zoveel inzit, dan is dus ook de kans groot dat na pakweg een kwartier geen van deze programma’s een positioneel betere zet zal vinden.

Verrassend is dus dat ook het Deep Blue-team deze manier gebruikt voor hun programma. Daar waar een programma als Diep altijd naarmate deze dieper rekent positioneel beter speelt, zal dieper rekenen met tabellen dit niet zo snel geven. Natuurlijk gebeurt het in de praktijk wel vaak dat programma’s die dieper rekenen beter spelen, omdat alle andere mogelijkheden duidelijk weerlegd worden.

Om deze tabel reden ben ik sinds enkele weken dan ook bijzonder pessimistisch over de kansen van enig schaakprogramma in de verre toekomst tegen Kasparov. Misschien wint een programma wel nooit op overtuigende wijze een match tegen de sterkste schaker ter wereld.

Misschien verandert mijn mening nog eens over de mogelijkheid of er ooit een programma komt dat op overtuigende wijze van alle mensen wint. Duidelijk is echter dat Kasparov nog steeds heer en meester is over de computer. Wist Kasparov de eerste partij nog te verliezen, en wel op zo’n manier dat de computer gedwongen werd te winnen (ja, je moet ten slotte aan je sponsors denken als dat 400.000 dollar per match oplevert), toch heeft Kasparov de match weer eens moeiteloos gewonnen. Natuurlijk niet nadat hij tijdens de match de sponsors weer eens om zijn vingers wist te winden door de pers een leuk verhaal te vertellen over hoe moeilijk het wel niet was om tegen het programma te spelen.

Hoewel Kasparov normaal gedurende de hele partij op zijn stoel zit, was het spelen tegen het programma zo vermoeiend dat Kasparov vaak van zijn bord wegliep. Verder heeft Kasparov niet name de eerste partijen geen gebruik gemaakt van het grootste voordeel dat een grootmeester heeft ten opzichte van de computer, namelijk de opening. Hoewel Kasparov in matches tegen Karpov en Anand altijd keihard toeslaat in de opening (al had Kasparov het tegen Anand voor het laatst bewaard), speelde Kasparov de opening, met name in de eerste partij, zoals een kleuter dat tegen de computer zou doen. Het is al regelmatig gepubliceerd dat programma’s het goed doen in open stellingen. Torens op open lijnen zetten en pionnen opeten is natuurlijk iets wat een schaakprogramma wel snapt.

Enfin, de laatste partij liet Kasparov nog even wat vuurwerk zien door de schaakcomputer op een enorm harde manier van het bord te zetten, waarmee de match met 4 – 2 door Kasparov werd gewonnen.

Op het grote computernetwerk Internet waar uitgebreid in de schaakgebieden werd gepraat over de match Kasparov – Deep Blue, werd druk gepraat over het opzettelijk cadeau geven van punten aan Deep Blue door Kasparov. Enfin we zullen het nooit weten. Kasparov heeft in mijn ogen zonder zich al te veel hoeven in te spannen (in positioneel en voorbereidend opzicht) de match naar zijn voordeel ‘toegerommeld’. Als je je niet inspant, dan is het natuurlijk goed mogelijk om tegen een tactisch sterk tegenstander wat halfjes en een puntje af te staan.

Wat dat betreft lijkt INTEL het handiger te hebben aangepakt dan IBM. Heeft IBM miljoenen uitgegeven voor deze match Kasparov – Deep Blue, INTEL laat het al sterk spelende programma Genius spelen op snellere hardware. Natuurlijk heeft Genius echter ook zo zijn problemen: al evalueert Genius meer dan Deep Blue aan het einde van de variant, toch is ook Genius positoneel grotendeels afhankelijk van tabelletjes.

De opening die een programma als Genius speelt is dan ook van groot belang. Als je van tevoren weet welke opening je programma speelt, dan stem je daar je tabellen op af. De openingen waar Genius op afgesteld is, speelt dit programma dan ook erg sterk.

Dit ‘afstellen’, is iets waar ik al helemaal niet aan toegekomen ben. De opening is dan ook een ondergeschoven kindje. Verder is een groot gedeelte van de rating van de wereld- top programma’s verkregen door simpelweg duizenden testpartijen te spelen. Als er dan een ongelooflijke krukkezet wordt afgeleverd (vaak in het eindspel), dan wordt deze verbeterd. Testpartijen spelen kosten tijd en minimaal twee computers. Dit terwijl ik slechts één snelle computer tot mijn beschikking heb.

De vraag die altijd gesteld wordt

Hoe sterk speelt nu mijn programma? Door het ontberen van al deze testpartijen is de rating van Diep moeilijk in te schatten. Tijdens het Nederlands Kampioenschap 1994 behaalde mijn programma een gedeeld 12/13e plaats, met een score van 3 uit 11 (16 deelnemers totaal). Voor een eerste keer was dat niet onverdienstelijk, vooral als u weet dat ik toen op een langzame computer (486 dx66) draaide terwijl vrijwel alle andere deelnemers over een snellere computer beschikten (P90/P100). Ook ontbeerde mijn programma een aantal zaken: hashtables, denken in de tijd van de tegenstander. Dit is niet te onderschatten: als een programma gemiddeld 70% van de zetten van de tegenstander goedgokt, hier vanuit gaat, en dan in de tijd van de tegenstander verder denkt, dan scheelt dat al bijna een factor 2.

Op het NK 1995 (november) waren al deze details een stuk beter geregeld. De hardware: P90, denken in de tijd van de tegenstander en goedwerkende hashtables. Hierdoor werd een stuk dieper gerekend. Daarnaast was Diep kwalitatief en kwantitatief een stuk verbeterd. Meer kennis en betere kennis over het schaak spel.

Dit resulteerde op het Nederlands Kampioenschap in een verdienstelijke 8e plaats met 6 uit 11. Diep verloor van alle sterke programma’s en won van alle amateurs.

Op grond van het resultaat daar zou ik mijn programma 2100 willen geven. Echter, dat is natuurlijk een computerrating en zegt niets over prestaties tegen mensen. De huidige tests geven aan dat Diep positioneel op de 2345 computerrating en de 2240 tactische rating zit.

Dit is natuurlijk niet waar voor partijen: partijen tegen andere programma’s heb ik nauwelijks gespeeld, dus er zullen nog wel een heleboel eenvoudige stellingen zijn waarin een ongelooflijk stupide zet gedaan wordt. Voor komende zomer/voorjaar staat op het programma om de ‘details’ binnen Diep beter te regelen, en te voorkomen dat het programma kromme zetten speelt in normale stellingen. Met details bedoel ik met name het openingsboek, en de gebruikersinterface. Met kromme zetten bedoel ik ook het voorkomen dat door kromme zetten een stelling ontstaat als de volgende, waarin een computerprogramma met zwart speelde en een menselijke speler met wit.

Diagram 4, wit aan zet wint op spectaculaire wijze. (De oplossing vindt u aan het einde van dit artikel.)

Dat openingsboek heeft overigens momenteel topprioriteit: begin april wordt er het mens-computer toernooi in Den Haag gehouden. Dat is op dit moment over één maand. De verwachtingen zijn niet erg hoog: Diep heeft mazzel nodig dat hij niet in een stelling terecht komt waarin hij niet weet wat te doen en dus maar een ongelooflijke krukke zet doet. Wat dat betreft kan er van alles gebeuren. Een topgrootmeester als Judith Polgar wordt keihard van het bord getrapt als deze een klein tactisch kansje weggeeft, terwijl een ervaren computerbestrijder als Bert Kieboom genadeloos Diep aan de kant kan schuiven indien er geen grap uit te halen valt.

Oplossingen:
Diagram 1: 1.Pe7+ Pxe7 2.Dg3+ Dxg3 3.Lxf7 mat.
Diagram 2: 1… Lxg2 2.Kxg2 Lxc3 3.bxc3 Pd5 4.Dxc4 Pxe3 5.Kf2 Pxc4.
Diagram 3: 1.g6!! hxg6 2.Ta1! Dg2 3.Tg1 Dxd5 4.Tg4+ Kc5 5.Tg5 Dxg5 6.Pe4+ Kd4 7.Pxg5.
Diagram 4: 1.hxg6!! Txe6 2.Lxe6! h7xg6 3.Ph4 De7 4.Pxg6 Dxe6 5.Th8 mat.