Deep Blue

In mei 1997 werd bewaarheid wat menigeen in de jaren daarvoor al voorspeld had: de op dat moment regerende wereldkampioen schaken (Gari Kasparov) werd in een match om de wereldtitel verslagen door een computer (Deep Blue). Hoewel, zoals gezegd, velen "uit het veld" dit al jaren zagen aankomen, was deze gebeurtenis voor het grote publiek een schok. Als er één intellectuele activiteit is die voor veel mensen tot de verbeelding spreekt, dan is dat toch wel schaken. En nu was de grootste denker op dat gebied verslagen door een electronisch brein. Velen zullen zich afgevraagd hebben: hoe is dit mogelijk en tot de conclusie zijn gekomen dat een computer(programma) dat in staat is de beste speler ter wereld van een moeilijk spel als schaken te overtroeven, zelf ook zeer ingewikkeld in elkaar moet zitten. Dit is echter niet het geval.

 

Lucifers

De door de programmeurs van Deep Blue gebruikte methode is niet specifiek aan schaken gebonden, maar een algemeen toepasbaar principe dat in wezen te gebruiken is bij elk type spel waarin de spelers om de beurt (gebruikmakend van bepaalde spelregels) "een zet doen". Alhoewel dus breder toepasbaar, is dit de methode die menselijke spelers min of meer automatisch gebruiken bij een spel als schaken en die kort te omschrijven is als "vooruit denken". Om het een en ander nader duidelijk te maken, nemen we het zeer eenvoudige spelletje "Lucifers" onder de loep. Bij "Lucifers" wordt, zoals de naam al aangeeft, gespeeld met een hoopje losse lucifers, waarvan de (twee) spelers, om de beurt, één of twee mogen wegnemen. De speler die genoodzaakt is de laatste lucifer op te pakken is de verliezer. Veronderstel nu dat we een computer (Deep) geprogrameerd hebben volgens de bovenstaande methode van "vooruit denken". We laten Deep "Lucifers" spelen tegen Gari, met een hoopje van drie lucifers. Deep begint. Deep gaat dan (systematisch) als volgt te werk: Er zijn twee "zetten" mogelijk, namelijk één of twee lucifers oppakken. In eerste instantie neemt Deep (in gedachte) één lucifer weg en verplaatst zich dan in de situatie van Gari. Ook Gari (zo stelt Deep zich voor) probeert eerst wat het wegnemen van één lucifer oplevert; dat blijkt winst (0-1 voor Gari). De tweede mogelijkheid, namelijk twee lucifers oppakken, resulteert in remise (½-½) want de lucifers zijn dan op zonder dat er een verliezer is aan te wijzen. Gari zal dus kiezen voor één lucifer oppakken. Deep concludeert nu dat de zet "één lucifer" uiteindelijk -1 punt oplevert. Vervolgens gaat Deep op dezelfde manier na waarin het wegpakken van twee lucifers resulteert: Deep verplaatst zich dan weer in de situatie van Gari; in dit geval resteert er maar één mogelijke zet voor Gari, namelijk de laatste lucifer wegpakken, waarmee Gari dan verloren heeft (1-0 voor Deep). Deze zet levert Deep dus 1 punt op. Omdat 1 punt meer is dan -1 punt zal Deep, na deze gedachte-exercitie, concluderen dat de zet "twee lucifers" resulteert in het winnen van dit spelletje.

 

Schaken en Lucifers

Ook een spel als schaken is op deze manier voor een computer "door te rekenen" en dat is precies wat Deep Blue die beruchte dagen in mei '97 gedaan heeft. Eerlijkheidshalve moet hier dan wel vermeld worden dat er in de praktijk een complicatie optreedt die het niet mogelijk maakt de methode ten alle tijden ten volle te benutten; en die complicatie is dat de huidige computers (ook zelfs Deep Blue) nog steeds te traag zijn om in een redelijke tijd een gegeven schaakstelling (met nog tamelijk veel stukken op het bord) met de bovenstaande methode, tot het einde toe, "door te rekenen". In het geval van "Lucifers", treedt deze situatie op als we in plaats van met een hoopje van drie, met een hoopje van zeg drie miljóén lucifers beginnen. Het systematisch aflopen van alle mogelijke zettenreeksen zoals in de vorige paragraaf is laten zien voor drie lucifers, zou in dat geval, ook met de snelste computer, zoveel tijd kosten dat de methode van "vooruit denken" dan niet meer practisch is. Dat wil zeggen, de methode is niet meer practisch als we verlangen dat elke zettenreeks tot het einde toe (ofwel tot een winnaar bekend is) wordt doorlopen. De meest voor de hand liggende variant op de methode is dan natuurlijk dat de hoeveelheid stappen in het aflopen van elke zettenreeks wordt beperkt tot een van te voren vastgelegd aantal. En dat is de variant die de programmeurs van Deep Blue ook (noodgedwongen) gebruikt hebben. In dat geval is niet meer voor elke (te beschouwen) zet direct na te gaan of ze uiteindelijk tot winst (of verlies of remise) leidt. Dergelijke zetten(reeksen) eindigen, na de vastgelegde hoeveelheid stappen, tot een spelsituatie (schaakstelling) die, over het algemeen, nog ver verwijderd is van een conclusie. En voor "conclusie" moet je dan lezen "bepaling van de winnaar". Daar draait het tenslotte om als we een computer programmeren met de genoemde variant van "vooruit denken". Want de schaakstelling waar we na de voorgeschreven hoeveelheid stappen in beland zijn, is tenslotte ontsproten aan een bepaalde zet waarvan we willen weten of die uiteindelijk tot winst dan wel verlies leidt. Zoals aangegeven, is die conclusie, over het algemeen, gegeven een schaakstelling, niet te trekken. Wat echter wel mogelijk is, is uit de gegeven stelling een waarderingscijfer af te leiden en dit dan zowel voor de wit- als de zwartspeler. Hoe hoger dit cijfer voor een speler, hoe groter de kans dat die speler (vanuit de gegeven stelling) de schaakpartij uiteindelijk zal winnen. Het ontwikkelen van een (reken)methode die aan een gegeven stelling een dergelijke waardering toekent, is echter geen sinecure. Om die reden bestond het ontwikkelingsteam van Deep Blue niet alleen uit programmeurs, maar ook uit professionele schakers. Dergelijke beroepsschakers doen in de dagelijkse schaakpraktijk tenslotte niet veel anders dan gedurende een schaakpartij de mogelijke zetten, één voor één, doordenken tot op een zekere zettendiepte, om dan vervolgens dié zet te kiezen die, volgens hun berekeningen, de meest gunstigste spelsituatie oplevert; ofwel die zet, die dié stelling oplevert waaraan de schaker de hoogste waardering toekent.

 

Kaarten en Schaken

Als de hierboven beschreven (variant op de) methode van "vooruit denken" voor een spel als schaken zo goed werkt (Kasparov had tenslotte het nakijken) zou het dan voor een kaartspel ook zo succesvol kunnen zijn? Op het eerste gezicht lijken kaarten en schaken niet veel overeenkomsten te hebben. Ten eerste is er al het verschil dat bij schaken de spelsituatie (de schaakstelling) voor iedere speler ten alle tijden bekend is, terwijl bij een kaartspel de spelsituatie voor elke speler maar gedeeltelijk bekend is; iedere speler kent z'n eigen kaarten, maar weet niet precies (zeker in het begin van het spel niet) welke kaarten de andere spelers in de hand hebben. (In de loop van het kaartspel wordt dit overigens wel steeds duidelijker). Juist omdat bij kaarten de spelsituatie niet volledig bekend is, lijkt de methode van "vooruit denken" hier niet te gebruiken; er valt tenslotte moeilijk in zetten vooruit te denken als niet bekend is welke tegenzetten (in dit geval: tegenkaarten) de andere spelers tot hun beschikking hebben. Om die reden gaan we er even vanuit dat dat wél bekend is (iedere speler legt dan, als het ware, z'n kaarten open op tafel). In dat geval is de methode van "vooruit denken" te gebruiken, hoewel, over het algemeen, niet in z'n zuiverste vorm; d.w.z. als er nog veel kaarten in het spel zijn dan moeten we ons noodgedwongen beperken tot de variant van de methode waarin het proces van "vooruit denken" na een aantal stappen wordt afgebroken. Wat dat betreft is de situatie vergelijkbaar met het schaakverhaal uit de vorige paragraaf. Vergelijkbaar, maar met één belangrijk verschil. Waar het bij schaken heel erg lastig is om een bruikbare waarderingsmethode te ontwikkelen voor de stelling waarin het proces (aan het eind van de zettenreeks) is blijven steken, bestaat er bij kaartspelen wel een eenvoudige becijferingsmethode. Namelijk: gebruik voor iedere speler de tijdens de (afgebroken) kaartenreeks vergaarde punten als indicatie voor de waarschijnlijkheid dat die speler het spel zal winnen. Bedenk hierbij dat bij bijna alle kaartspelen de spelers tijdens het spel op een of andere manier punten vergaren, bijvoorbeeld in de vorm van gewonnen slagen. Het blijkt (relatief) vrij eenvoudig om een computer met de bovenstaande becijferingsmethode te programmeren. Maar we zijn er dan wel vanuit gegaan dat van elke speler de hand vanaf het begin al bekend is. Het zal je duidelijk zijn dat als we streven naar het ontwikkelen van een volwaardig kaartprogamma dat de werkelijke spelpraktijk zo veel mogelijk benaderd, dat dat niet acceptabel is. Hiermee lijken we dan alsnog op een dood spoor beland te zijn. Nu blijkt hier gelukkig wel een mouw aan te passen. Want, hoewel duidelijk zal zijn dat de methode zonder een van te voren bekende kaartverdeling niet bruikbaar is, is er nooit beweerd dat zo'n verdeling moet overeenstemmen met de werkelijke verdeling van de kaarten over de spelers. We kunnen het programma gewoon een willekeurige aanname laten maken omtrent de verdeling van de kaarten over de tegenspelers (de eigen hand mogen we natuurlijk wel als bekend veronderstellen). Op het eerste gezicht lijkt het "doorrekenen" van zo'n willekeurige kaartverdeling weinig zinvol, maar bedenk dan dat spelers van vlees en bloed ook aannamen maken tijdens het kaarten, simpelweg omdat niet precies bekend is wat de andere spelers op de hand hebben. Alleen is zo'n menselijke aanname niet willekeurig maar gebaseerd op waarschijnlijkheid. Om een voorbeeld te noemen: een speler die na het delen van de kaarten, zich geconfronteerd ziet met veel harten op de hand, zal aannemen dat waarschijnlijk één van de andere spelers (of zelfs meerdere) helemaal geen harten heeft. Het zou mooi zijn als we, op een of andere manier, dat waarschijnlijkheidsaspect ook in het programma konden vangen. Beschouw daartoe nogmaals het hartenvoorbeeld van zonet. Veronderstel dat we het programma met inderdaad zo'n goedgevulde hartenhand laten beginnen. Volgens de werkwijze zoals eerder gesuggereerd, genereerd het programma dan voor de tegenspelers een willekeurige kaartverdeling en rekent die dan (tot een zekere diepte) door. Nu kan het toevallig zo zijn dat bij deze willekeurige verdeling de overige spelers ook harten hebben toebedeeld gekregen. Daarmee is deze kaartverdeling dan geen goede representatie van de meest waarschijnlijke verdeling (die waar één van de tegenspelers geen harten heeft); als we het programma méérdere kaartverdelingen laten genereren (in plaats van één) dan zullen de meeste van deze verdelingen van die laatste vorm zijn en dus een hand bevatten waar geen harten in zit. Die laatste gevolgtrekking is precies wat we zochten. Door het programma méérdere verdelingen te laten genereren en die vervolgens door te rekenen, kunnen we de menselijke inschatting van de spelsituatie simuleren. Om dit nader duidelijk te maken, beschouwen we nog eenmaal het hartenvoorbeeld, maar nu gedetailleerder. Dit voorbeeld is namelijk niet uit de lucht gegrepen maar afkomstig uit de praktijk van de jasspelen, waarin zogenaamde troefkaarten een rol spelen. Als je hiermee bekend bent dan weet je waarom de eerder genoemde inschatting van de spelsituatie bij een royale hartenhand, belangrijk is; uitkomen met een hartenaas is in zo'n geval onverstandig, precies vanwege die grote waarschijnlijkheid dat één van de tegenspelers geen harten heeft en daarom vervolgens de slag zal introeven. Tot deze conclusie (beter niet uitkomen met hartenaas) zal het programma (gebruikmakend van méérdere verdelingen) ook komen en wel als volgt. We gaan uit van een vaste bedenktijd. In die tijd zal het programma de eerste kaartverdeling genereren en die dan vervolgens voor ieder van de kaarten uit de eigen hand doorrekenen tot zeg één slag diep. D.w.z. elke kaart uit de eigen hand vormt dan het begin van een serie van vier kaarten (het spelverloop over één slag) die het programma vervolgens van een waardering voorziet. Deze waardering is, zoals aangegeven, de tijdens de slag behaalde punten. Of eigenlijk, om preciezer te zijn, het verschil tussen de eigen vergaarde punten en de punten van de tegenspelers. Hieruit volgt dat als in deze eerste kaartverdeling één van de tegenspelers inderdaad geen harten heeft (maar wel troeven) dat dan de puntenwaardering voor de serie kaarten die ontspruit uit de hartenaas, een negatief getal zal zijn. En dit geldt natuurlijk voor elke volgende kaartverdeling met een dergelijke scheve hartenverdeling. Als de bedenktijd verstreken is, waarin het programma zeg 10 verdelingen heeft kunnen doorrekenen, tellen we alle 10 waarderingsaantalen voor alle kaarten uit de eigen hand bij elkaar op. De kaart waarop op deze manier de meeste punten zijn gevallen, wordt dan uiteindelijk de kaart waarmee het programma uitkomt. Juist omdat de kans groot is dat een meerderheid van de 10 beschouwde kaartverdelingen, uit een scheve hartenverdeling bestaat, volgt nu dat de hartenaas waarschijnlijk meer negatieve dan positieve waarderingsaantallen heeft vergaard en dus gesommeerd over de 10 puntenaantallen uiteindelijk op een negatief getal uitkomt als waardering. Het programma zal dus dan waarschijnlijk niet uitkomen met de hartenaas.