Inleiding Computerschaak, door Vincent Diepeveen.

Eerder gepubliceerd op de website van Ries van Leeuwen

U zult ongetwijfeld al meer dan eens in uw leven kennis gemaakt hebben met computers die kunnen schaken. 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. In dit stukje zal ik niet zo zeer bij de actuele prestaties van schaakcomputers of PC schaakprogramma's stilstaan. Dat af en toe Kasparov voor veel geld verliest van een schaakprogramma, 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.

Een belangrijke 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. 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 bepaald 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 tot zijn beschikking. Vandaar dat programma's op PC's stukken beter spelen dan zogenaamde "hardwarematige" schaakprogramma's.

Het zal duidelijk zijn dat het lastig is om een schaakprogramma te schrijven. 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 tot 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 als een mens. Dat levert natuurlijk grote problemen op; in feite probeer je als programmeur schaken te leren aan een beginneling, wat op zich alleen al een hele prestatie is. Vandaar dat de beginnende programma's 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 de computer.

De schaakprogrammeur maakt hiervoor een tekst aan met allerlei commando's voor de computer. De tekste wordt geïnterpreteerd door de computer en letterlijk uitgevoerd. Een klein gedeelte van deze tekst zou kunnen wezen:

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 textconstructies mogelijk met een andere functionaliteit. 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:

Kandidaatzetten: wat zijn de in aanmerking komende zetten?
Progressive deepening: opnieuw naar een zet kijken, maar steeds langere varianten doorrekenen.
Analyse Then evaluatie: Eerst een variant doorrekenen en na afloop van de variant je de stelling voor proberen te stellen.
Evaluatie: waarde van de ontstane stelling.

De volgende onderdelen zitten in de meeste programma's:

1. Zoekproces; dit is het centrale brein: controleerd de volgende onderdelen.
2. Zetten Generator; produceert (semi-)legale zetten.
3. Zetten Sorteerder; 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 een ontstane stelling. Alle voordeeltjes worden opgeteld en nadeeltjes er vanaf getrokken. Over dat zoekproces is bv wel bekend dat mensen werken met behulp van progressive deeping etc., 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 laatst jaren wordt hiernaar met behulp van het fenomeen "neurale netwerken"wel onderzoek naar gedaan, maar deze onderzoeken zijn allemaal tot nu toe 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 is dat alles onderzocht moet worden, zoals mensen wel kunnen. 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 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 heleboel zetten mogelijk zijn die allemaal een bepaald doel lijken na te streven, dan zal een programma grootste problemen hebben om de goede zet hieruit te halen. 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 problemen zit, dan is deze dus het gevaarlijkst: doordat het berekent dat het in gevaar komt, zal het er alles aan doen om het gevaar te voorkomen. Desnoods een stuk offeren. Als het ene programma tegen het andere speelt is de diepte waarop het programma rekent belangrijk.

Diepte wordt uitgedrukt in plies. Een ply is een halve zet, bv 1.e4 e5 is 2 ply. Een programma wat 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 je programma dan 9 ply rekent, gaat deze in de fout. Je Programma speelt de verliezende zet. Als je programma echter 10 ply of meer rekent, is dit probleem handig opgelost. Voor de winnende zet geldt hetzelfde. Natuurlijk is het één 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 korte termijn. 11 ply is tenslotte 6 zetten.

Het zal de echte fanaat dan wel niet verbazen dat programma's erg veel moeite hebben met het goed neerzetten van de 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 wordt gedaan 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. Om 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 voorkomt; de programmeurs van sterke programma's hebben vaak een te laag nivo. Minor promotie en 'en passant' werken dan ook vaak niet in hun eerste versie van het schaakprogramma.

Kennis heeft natuurlijk wel een tweetal nadelen: de eerste is hoe leg je kennis vast in regeltjes en ten tweede: wat als de kennis in deze stelling niet opgaat ? Geen computer zal alle 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. In het verleden was één van de zwakste punten van programma's het eindspel, doordat er vaak weinig tactiek aan te pas komt.

De laatste jaren zijn commerciële programma's enorm sterk 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 vaak al mensen kansloos zien verliezen van programma's. Pionformaties waarin de menselijke tegenstander de verste vrijpion heeft worden nog regelmatig door programma's mishandeld. Er blijft dus nog steeds ruimte voor verbetering.

Een groot probleem is hierbij de evaluator, die een keuze moet maken. De meeste topprogramma's spelen nu bijna allemaal even sterk. Tactisch zijn deze programma's bijzonder sterk. Nog altijd is het positionele spel de zwakste schakel in het programma. Een groot probleem is nl. dat alles wat een schaakprogramma kent, qua positionele kennis, van tevoren 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.