Inleiding computerschaak

Vincent Diepeveen

U zult ongetwijfeld al meer dan eens in uw leven kennisgemaakt hebben met computers die kunnen schaken. Enkele leden van uw vereniging houden zich zeer actief met deze tak van sport bezig. Dat het een aparte tak van sport is, geheel anders dan het zelf spelen van een partij, dat kan ondergetekende u melden. Slechts de regels en sommige openingen zijn hetzelfde.

Links Vincent Diepeveen, de auteur van dit artikel.

In dit stukje zal ik niet zozeer bij de actuele prestaties van schaakcomputers stilstaan. Dat af en toe Kasparov voor veel geld verliest van een schaakprogramma als Fritz of Genius, kunt u in geuren en kleuren in de media volgen. Graag vertel ik u hoe nu zo’n schaakprogramma denkt en wat de zwakke en sterke punten van een schaakprogramma zijn. Ook zal ik mij, tegen alle wijsheden in, wagen aan een voorspelling.

.

.

Geschiedenis

Een belangrijk vereiste voor een machine om te kunnen schaken is natuurlijk dat deze in staat is om bepaalde regels te gehoorzamen. Toen de eerste voorlopers van de moderne computer ontwikkeld werden, was het produceren van alle legale zetten in een stelling al een heel probleem. Probeert u eens een apparaat te leren dat rocheren niet legaal is na: 1.a4 b6 2.Ta3 Lb7 3.g4 Lxh1 4.h4 Pc6 5.Th3 d5 6.Th1 e6 7.Pf3 Pf6 8.Lh3 Le7.

Toen er meer geheugen beschikbaar kwam was dit probleem natuurlijk snel opgelost (meer ruimte om de regels op te schrijven!), en kon men beginnen met de verkoop van schaakcomputers. De laatste jaren echter is er een verschuiving begonnen. Verkocht men eerst een hele computer, nu verkoopt men vrijwel alleen software voor een computer, welke voor meerdere doeleinden gebruikt kan worden. Dit laatste is natuurlijk veel handiger. De schaker bepaalt dan zelf wat voor soort computer deze software op gedraaid kan worden. Ook voor de schaakprogrammeur is het een stuk makkelijker; in plaats van zich in allerlei bochten te moeten wringen om een programma op een zo goedkoop mogelijke computer werkend te krijgen, heeft de programmeur nu veel geheugen en een snelle processor(de motor van de computer) tot zijn beschikking. Vandaar dat programma’s op PC’s (met name op de tegenwoordige Pentium) stukken beter spelen dan zogenaamde ‘hardwarematige’ schaakprogramma’ s.

Een schaakprogramma schrijven

Het zal duidelijk zijn dat het lastig is om een schaakprogramma te schrijven. Al sinds enige duizenden jaren probeert men dingen te beschrijven. Als het mogelijk is om het schaakspel zo te beschrijven dat deze perfect schaakt, dan hoeft een mens dit slechts te lezen om ook perfect te kunnen schaken!

Nu zit men met betrekking tot computers met een nog ander probleem: computers zijn apparaten die snel instructies als optellen en delen kunnen uitvoeren. Apparaten zijn niet intelligent en moeten dus op een andere manier geleerd worden om te schaken dan een mens. Dat levert natuurlijk grote problemen op; in feite probeer je als programmeur schaken te leren aan een zwakzinnige, wat op zich alleen al een hele prestatie is. Vandaar de beginnende programma’s ook niet zo sterk spelen. Het duurt jaren voor een mens, die bij uitstek geschikt is om iets te leren en vervolgens het geleerde af te wegen, om redelijk te leren schaken, laat staan een programma op een computer.

De schaakprogrammeur maakt hiervoor een tekst aan met allerlei commando’s voor de computer. Deze tekst wordt geïnterpreteerd door de computer en letterlijk uitgevoerd. Een klein gedeelte van deze tekst zou kunnen zijn: VOOR VELD=A1 TOT H8: INDIEN KONING OP VELD DAN PRINT VELD; In een hokje in de computer dat de programmeur ‘VELD’ noemt wordt dan steeds een veld van het bord gestopt. Als er een koning staat, dan print (naar de printer of naar het beeldscherm) de computer deze uit. Natuurlijk zijn er talloze tekstconstructies mogelijk met een andere functionaliteit.

Onderdelen schaakprogramma

Hoe zit nu zo’n schaakprogramma in elkaar? Natuurlijk is het een goed idee om eens naar mensen te kijken: hoe spelen zij schaak? Mensen blijken gebruik te maken van:

1. kandidaatzetten: wat zijn de in aanmerking komende zetten?
2. progressive deepening: opnieuw naar een zet kijken, maar steeds langere variant doorrekenen
3. analyse then evaluate: eerst een variant doorrekenen, en na afloop van de variant je de stelling voor proberen te stellen, vervolgens een
4. evaluatie: waarde van de ontstane stelling

De volgende onderdelen zitten in de meeste programma’s:

1. Zoekproces; dit is centrale brein: controleert de volgende onderdelen.
2. ZettenGenerator; produceert (semi-)legale zetten.
3. ZettenSorteerder; zoekt de beste zetten uit de lijst en plaatst deze bovenaan.
4. MaakZet, TerugZet; voert een zet uit, respectievelijk neemt hem terug.
5. Evaluator; de waarde van de ontstane stelling. Alle voordeeltjes worden opgeteld en nadeeltjes er van afgetrokken.

Alleen mensen kunnen afwegen

Over dat zoekproces zou ik graag nog even iets kwijt: er is bijvoorbeeld wel bekend dat mensen werken met behulp van progressieve deepening etcetera, maar er is niet bekend hoe het zoekproces precies bij mensen werkt! Wel is er een algemeen woord dat de lading dekt: intelligentie. Hoe weet een mens nu wat de volgende te onderzoeken zet is? Een mens kan goed afwegingen maken, rekening houdend complexe factoren in de stelling. Een computer kan dit niet. De laatste jaren wordt hiernaar met behulp van het fenomeen ‘neurale netwerken’ wel onderzoek naar gedaan, maar deze onderzoeken zijn allemaal mislukt. Er is een revolutionair en Nobelprijs winnend fenomeen nodig om een apparaat ingewikkelde afwegingen te laten maken.

Een programma moet dus alle mogelijke zetten onderzoeken. Voordeel hierbij is meteen dat een programma dus ook geen variant zal missen. Nadeel van dat alles onderzocht moet worden is dat er niet zo diep gezocht kan worden, zoals mensen dat wel kunnen.

Superieure tactiek en planloos spelen

Wel zijn schaakprogramma’s superieur in optellen en aftrekken, kortom bewerkingen op rijen getallen. Hierdoor is het wel goed mogelijk voor schaakprogramma’s om subdoelen die nauwkeurig beschreven kunnen worden te bereiken. Het belangrijkste subdoel is natuurlijk mat. in het computergeheugen heet dit overigens geen mat, maar is het slechts het slaan van een bepaald houtje: de koning. De lezer zal thuis ongetwijfeld gemerkt hebben dat het slaan van houtjes een ware hobby is van schaakprogramma’s. Met feilloze precisie wordt opgemerkt dat een bepaald stuk op een slinkse wijze gepakt kan worden! Zelfs als het niet soms niet goed is!

Het niet kunnen maken van afwegingen is dan ook gelijk de grootste zwakte van een schaakprogramma: het is niet in staat afwegingen te maken, waardoor er dus niet een ingewikkelde strategie kan worden verzonnen. Om deze reden spelen computers soms planloos. Als er geen kenmerk in de stelling is dat de computer begrijpt, zoals een open lijn, of een zwakke pion, dan bestaat de kans dat de computer planloos zetten doet.

Door het zoekproces te verhelderen zult u precies begrijpen in welke stellingen een schaakprogramma de fout in gaat: in het zoekproces probeert een programma niet de beste zet te zoeken, maar kijkt een programma of andere zetten slechter zijn dan de huidige zet. Misschien zult u denken dat dit hetzelfde is, maar dat is het niet. Als er een hele boel zetten mogelijk zijn die allemaal een bepaald doel lijken na te streven, dan zal een programma grootse problemen hebben om de goede zet hieruit te pikken. Slechts als het programma ziet dat het niet oprukken van zijn vrijpion hem in de problemen brengt, zal het programma ervoor kiezen om deze op te spelen. Als een computer in de penarie zit, dan is deze dus het gevaarlijkst: doordat het berekent dat het in gevaar komt, zal het alles er aan doen om het gevaar te voorkomen. Desnoods een stuk offeren.

Een beroemd voorbeeld is de linkerdiagram (wit aan zet).

In dit diagram wint wit met 1.Pxb6. Niet dat enig programma snel wil afwikkelen naar het gewonnen pionneneindspel met Pb6 omdat het gewonnen is, maar de meeste programma’s zien dat na een andere zet wit alleen een paard overhoudt, wat remise is. Remise is gelijk aan 0, en gunstig pionneneindspel is groter dan 0.

.

.

.

Voordelen diep rekenen

Met name als het ene computerprogramma tegen het andere programma speelt is de diepte waarop een programma rekent belangrijk. Diepte wordt uitgedrukt in plies. Een ply is een halve zet, bijvoorbeeld 1.e4 e5 is 2 ply. Een programma dat op 10 ply rekent ziet in principe alle positionele varianten die mogelijk zijn binnen deze 10 ply. De tactische diepte ligt vaak nog wat dieper. De reden dat dit zo belangrijk is, is het volgende: stel dat een bepaalde variant (die verliest) je programma 10 ply kost om in te zien dat deze verliest. Als dan je programma 9 ply rekent, ben je mooi zuur. Je programma speelt de verliezende zet en je kunt huilend naar huis. Als je programma echter 10 ply of meer rekent, is dit probleem handig opgelost. Voor een winnende zet geldt hetzelfde.

Natuurlijk is het een en ander op te vangen met kennis, maar vooral voor de tactiek is het ongelooflijk handig om diep te rekenen. De laatste tijd claimen sommige programmeurs zelfs dat hun programma’s vanzelf een plan verzint, doordat het zo diep rekent. Natuurlijk wel een plan op de korte termijn. 11 ply is tenslotte maar 6 zetten. Het zal de echte fanaat dan wel niet verbazen dat programma’s erg veel moeite hebben met het goed neerzetten van stukken. Vooral in de opening wordt er door de mens al vast een plan voorbereid door stukken gelijk naar het goede veld te ontwikkelen.

Vandaar dat er veel moeite door programmeurs in gestoken wordt om hun programma’s dieper te laten rekenen. De duurste, maar wel de snelste methode om dieper te rekenen is het kopen van een snelle computer. Op computerschaaktoernooien zie je dan ook veel snelle computers, vaak de snelste computers die men kan kopen voor zijn geld. Deze maand (januari 1996) is de pentium pro 150 uit (voor schaakprogramma’s twee tot drie keer zo snel als een normale pentium 133). Deze computer zal op het eerstkomende computerschaaktoernooi dus wel veelvuldig te bezichtigen zijn.

Wat is en passant?

Om zo diep te rekenen hebben dezelfde programmeurs hun programma’s zo snel mogelijk gemaakt. Natuurlijk kun je je programma wel handiger schrijven waardoor je weer sneller bent, maar op een gegeven moment zul je, wil je nog dieper rekenen, toch kennis uit je programma moeten slopen. Het weglaten van kennis is een veel toegepaste methode, die vaak ook uit een heel praktische reden voortkomt; de programmeurs van sterke programma’s kunnen vaak van geen kant schaken; ‘minorpromotie’ en ‘en passant’ werken dan ook vaak niet in hun eerste versie van het schaakprogramma. Ook hebben zij de gewoonte tijdens het spelen van de partij niet te noteren; zij kunnen dat niet, dat moet het programma maar zien te doen. Zij zijn in eerste instantie briljante programmeurs, die het onmogelijke voor elkaar gekregen hebben: een diep rekenend schaakprogramma. Als er dan weer eens in een interview door de programmeur geclaimd wordt dat er veel kennis in hun programma’s zit, dan heeft de lezer mijn permissie om hartelijk te lachen. De programmeur bedoelt dan dat zijn programma meer kennis heeft dan hijzelf.

Nadelen kennis

Kennis heeft natuurlijk wel een tweetal overige nadelen: de eerste is hoe leg je kennis vast in regeltjes en ten tweede wat als de kennis in deze stelling niet opgaat?

Er is geen programma in de wereld dat ooit de opening beter zal spelen dan de mens. Er zijn meer schaakstellingen mogelijk dan deeltjes in de aarde. Geen computer zal dus al die stellingen kunnen doorrekenen, en zal dus ook niet kunnen berekenen waar de stukken moeten staan. De oplossing die programmeurs hiervoor hebben bedacht is bekende theorie in de computer te stoppen. Na afloop van de opening staan, zo hoopt de programmeur dan, de stukken dan al op de goede plaats opgesteld, of is er een stelling ontstaan waarin er voor de computer evidente zetten gedaan moeten worden. De slechtste zet die een programma in een partij doet is vaak de zet nadat het openingsboek is afgelopen om deze reden. Opening is iets waar Kasparov ’toevallig’ erg goed in is.

Van 10 – 17 februari wordt er een match Kasparov – Deep Blue gespeeld (links een foto van de hersenkrakende Kasparov in diezelfde match). Het schaakprogramma Deep Blue, het troetelkind van miljardengigant IBM, wordt gesponsord met speciale hardware die tot de 10 miljard evaluaties per seconde zou halen per seconde (vergelijk dit met 50000 van Fritz3 op een pentium 100, of de 10000 van mijn programma Diep). U zult ongetwijfeld al van Deep Blue gehoord hebben. Het is namelijk de gesponsorde versie van Deep Thought II.

Al verloor Deep Blue vet van Fritz3 op het wereldkampioenschap in Hong Kong onlangs, toch verwachten de snelheidsfreaks te winnen met hun programma dat nog niet eens weet wat een slechte loper is … Zij verwachten toch te winnen daar zij met een snellere computer deelnemen. Tegen Fritz3 haalde men ‘maar pakweg 40 miljoen evaluaties’ per seconde, de turbo-versie die tegen Kasparov speelt zal dus 250x sneller zijn. De anti-Kasparov versie rekent ongeveer 4 ply meer, volgens mijn eigen berekening (log 250/log 4.0; factor 4.0 is de tijd om ongeveer 1 ply dieper te komen).

Natuurlijk is het zo dat een schaakspelletje gewonnen wordt door degene die de minste fouten maakt. Aannemende dat hij betaald wordt om te winnen, mogen we van Kasparov toch verwachten we toch dat hij geen stukken weggeeft tegen Deep Blue. Het Deep Blue team heeft op Internet al toegegeven te verwachten dat zij verloren uit de opening komen met hun programma. Zelfs het hulpje van Sherlock Holmes kan uit deze feiten al een bepaalde uitslag beredeneren.

Te verwachten problemen

Probleem is het voorstellingsvermogen van deze figuren. Zij zijn zelfs ongelooflijk slechte schakers (in het hele duurbetaalde Deep Blue team zit geen enkele schaker, al vermoed ik dat zij wel conclusies getrokken hebben uit de partij Fritz3 – Deep Blue en voor op zijn minst de opening wel een schaker zullen aantrekken), en gewend om allerlei dames weg te geven aan hun eigen programma. Zij kunnen zich niet voorstellen dat er mensen op deze aardbol rondlopen die niet in een trucje tuinen. Ik kan mij wel tenminste een tweetal personen voorstellen die dat niet doen, vandaar.

Speelsterkte in de toekomst

In het verleden was een van de zwakste punten van programma’s het eindspel, doordat er vaak weinig tactiek aan te pas komt. De laatste jaren zijn de commerciële programma’s enorm sterker geworden in het eindspel. Niet alleen is er veel gedaan aan het eindspel door programmeurs, maar ook is de diepte waarop nu gerekend wordt in het eindspel belangrijk. Doordat er minder stukken op het bord staan, en de computers tegenwoordig meer geheugen hebben wordt er met name in de eindspelen enorm diep gerekend. In eindspelen met eenvoudige pionnenformaties heb ik al vaak mensen kansloos zien verliezen van programma’s. Pionformaties waarin de menselijke tegenstander de verste vrijpion heeft worden nog steeds door programma’s mishandeld. Er blijft dus nog steeds ruimte voor verbetering. Een groot probleem is hierbij de evaluator, deze telt alle voordeeltjes en nadeeltjes bij elkaar op. Als er één nadeel of voordeel overheerst zal een programma de pointe totaal missen; het kent een te klein gewicht, toe aan het voordeeltje, vooropgesteld dat het programma rekening houdt met het voordeeltje.

De laatste twee jaar zijn er een groot aantal programma’s erg sterk gaan spelen. Zij spelen allemaal ongeveer op hetzelfde niveau. Tactisch zijn deze programma’s ongelooflijk sterk. Als je de vooruit gang in hardware echter vergeet, dan is de vooruitgang van de programma’s aan de top eigenlijk helemaal niet zo groot. Wel komen er een heleboel programma’s aan diezelfde top. Ik vermoed dat dit komt doordat speelsterkte grotendeels veroorzaakt wordt door het zwakste punt in het spel. Het huidige zwakke punt is positioneel spel. Heel anders dan als Karpov aan een toernooi meedoet, is het bij computerkampioenschappen vaak een loterij tussen de sterkste programma’s wie er kampioen wordt.

Positioneel zwakke programma’s zullen wel van een heleboel mensen winnen die een wending op de korte duur (dus pakweg zo’n 0 – 10 ply) missen, maar tegen mensen die het tactisch weten droog te houden zullen zij verliezen, ongeacht de menselijke elo-rating van de tegenstander (het kan best zo zijn dat een 1400 speler wint van Fritz, en een 2600 speler verliest! Hoe vaak zie je echter een 2600 speler verliezen van een 1400 speler?). Om dan te verbeteren zullen ze toch op een of andere wijze kennis over het schaakspel moeten gebruiken in de evaluator.

Het huidige probleem is dat het voor programmeurs al lastig genoeg is om een programma te schrijven dat zo diep rekent. Voorbeeld: de eerste versie van mijn programma rekende met veel moeite ongeveer 3 ply. Mijn huidige versie rekent ongeveer 8 ply. Een programma als Schach (1 van de allersnelste programma ter wereld op een pentium) rekent 11 ply.

Toch verwacht ik dat in de toekomst de programma’s zich boven de menselijke spelers zullen nestelen qua algemene speelsterkte. Ik vermoed dat dit echter een stuk langer zal duren dan de optimisten, die data als 2000 of 2010 noemen, verwachten. Ik zie het als het bouwen van een toren die uit blokken bestaat. de eerste paar blokken kun je nog boven op elkaar stapelen om snel hoog te komen, maar op een gegeven moment zul je de piramide vorm moeten hanteren om bovenaan te komen. Een programma zal een stevige hoeveelheid schaakkennis nodig hebben als basis. Dat kostte de Egyptenaren al heel veel tijd en moeite!

Een groot probleem is namelijk dat alles wat een schaakprogramma kent, qua positionele kennis, van te voren is vastgelegd door de programmeur. Als er dan in een stelling een bepaald soort kennis het belangrijkst is, dan zal een schaakprogrammeur dit met de hand moeten ingeven aan zijn programma. Vandaar dat schaakprogramma’s de laatste tijd een trucje gebruiken om trucs op te lossen. Bijvoorbeeld het programma Genius3 of Fritz3 geven, als dan de zelflerende functie aanstaat, aan zetten die door de gebruiker zijn gespeeld in een bewaarde partij meer punten, waardoor zij graag deze zet willen spelen. Hierdoor lijkt het alsof deze programma’s razendsnel op bepaalde ideeën komen.

Problemen treden echter op als de gebruiker een niet direct materiaal verliezende zet, die wel verkeerd is, invoert als oplossing van een probleem. Met name Genius zal dan graag de verkeerde zet spelen en dus een eb van 0 halen op de test…