De Econometrist

De Econometrist neemt een statistische kijk op de wereld.

Overig

Invloed van de computer op het schaakspel

Het werd in India al veel gespeeld vòòr het jaar 600 en van daaruit heeft het zich verspreid over de hele wereld. Tegenwoordig is het schaakspel overal enorm populair en het niveau waarop gespeeld wordt is dan ook sindsdien altijd gestegen. Omdat schaken geen kanselementen kent, werd al snel gespeculeerd over het perfecte potje en de mogelijkheid om de beste zetten te berekenen. De schaakcomputer ontstond daarom relatief kort na de komst van de eerste elektronische computer. Met de komst van de schaakcomputer konden zetten makkelijker en beter geanalyseerd worden en leek eindelijk vast te staan wat de beste eerste zetten waren. Gepaard met de opeenvolging van ontwikkelingen op elektronisch gebied kwamen ook veel ontwikkelingen op het vlak van de schaakcomputers. Wanneer zijn ze ontstaan, op welk niveau zitten ze in verhouding tot menselijke spelers en hoe ver kunnen ze komen?

De eerste zetten

“The Turk” is de naam van het eerste geautomatiseerde schaaksysteem. Althans, dat dachten mensen die de creatie van Wolfgang von Kempelen in 1770 zagen. Het was een pop achter een schaakbord die door een mechanisme van raderwerken leek te kunnen schaken. Geheim was echter de persoon die in de kast onder het bord verstopt zat en de pop met hendels opereerde. Hij was zeer bedreven in het schaken en won nagenoeg elke partij. Jarenlang reisde de machine rond de wereld en deed mensen geloven dat het schaakspel berekend kon worden, maar het bleek niet meer dan een goocheltruc. Deze onthulling liet de mensen achter met de vraag of het schaken ooit echt door een machine gespeeld kon worden.

Het heeft lang geduurd totdat er een wezenlijk systeem werd ontwikkeld dat echt in staat was te schaken. Er zijn echter veel theorieën geschreven en voorspellingen gedaan over de mogelijkheden van het schaken door computers. Het hield mensen niet alleen bezig omdat ze een computer wilden die kon schaken, maar het sprak tot de fantasie dat een niet-menselijk systeem een dergelijk populair spel zou kunnen spelen en zo zou kunnen “nadenken”.


Although of no practical importance, the question is of theoretical interest, and it is hoped that this problem will act as a wedge in attacking other problems of greater significance.”

Claude E. Shannon, Amerikaans wiskundige en elektrotechnicus, volgens velen vader van de informatietheorie, schreef een artikel voor het Philosophical Magazine dat in 1950 gepubliceerd werd, waarin hij technieken, formules en benodigdheden beschreef die gebruikt zouden kunnen worden om een schaakcomputer te ontwerpen. Hij stelt daarin bijvoorbeeld dat de volgende informatie ingecalculeerd moet worden om een positie te evalueren:

  1. De positie van elk stuk op het schaakbord.
  2. De kleur die aan zet is.
  3. Welke koningen en torens bewogen zijn, in verband met mogelijkheid tot rokeren.
  4. De vorige gespeelde zet, in verband met de en-passantregel
  5. Het aantal zetten sinds de laatste zet waarin er een stuk geslagen is of een pion bewogen is, in verband met de vijftig-zettenregel.

 

Ontwikkelingen van schaakcomputers

Nadat er kleine systemen gemaakt waren die simpele problemen op konden lossen zoals de tegenstander schaakmat zetten vanaf bepaalde posities in een beperkt aantal zetten, kwamen rond 1960 de eerste computers die een volledig spel konden spelen. Deze deden echter meestal een uur over één zet en wonnen zelden.  In de tien jaar daarna boekten ontwikkelaars veel vooruitgang, maar de computers bleven langzaam en het niveau bleef laag. De zetten werden op dit moment nog berekend aan de hand van vuistregels die ook door menselijke schakers gebruikt werden. Zo werd het menselijk spel nagebootst, maar dit bleek een zeer inefficiënte manier om posities en zetten te evalueren. Rond 1980 werd een andere tactiek ingezet; in plaats van het gebruik van heuristieken om zetten te vergelijken werden nu de posities na alle toegestane zetten geanalyseerd. Dit bleek veel effectiever en het computerschaak nam flinke sprongen. In 1996 versloeg de computer Deep Blue wereldkampioen Garry Kasparov in één van de zes potjes. Het was de eerste keer dat een heersend schaakkampioen verslagen werd door een schaakcomputer. In een revanchepartij in 1997 won een nieuwe versie van deze schaakcomputer de meerderheid van zes spellen tegen Kasparov en in het begin van het derde millennium wonnen (ex-)wereldkampioenen zelfs nog zelden van commerciële en dus mobiele schaakcomputers. Vanaf dit moment is het verschil in niveau tussen schaakcomputers en mensen slechts groter geworden en groeit nog steeds hard. We kunnen stellen dat schaakcomputers sneller ‘slimmer’ worden dan mensen.

 

Hoe werkt de schaakcomputer

Voor 1980 werden schaakcomputers geprogrammeerd om het menselijk schaakspel na te bootsen. Dit werd gedaan aan de hand van vuistregels binnen het spel. De computer werd ingesteld bepaalde zetten te maken als deze zet voordeel gaf. Een zet was goed als hiermee bijvoorbeeld materiaal gewonnen kon worden of de tegenstander schaakmat gezet kon worden. Zo zou de computer in het voorbeeld hieronder de loper van f3 naar c6 zetten. De diagonaal bewegende loper zal zo door een penning van de dame aan de koning de dame kunnen slaan, een stuk met meer waarde dan de loper.  

 

 

Dit beoordeelde de heuristische computer als een sterke zet omdat er dus materiaal gewonnen werd. In deze situatie is dit natuurlijk de juiste zet, maar in lastige opstellingen deden de heuristische computers soms onder voor goede menselijke schakers, omdat sterke zetten moeilijk te vinden zijn in zulke opstellingen. In de schaakcomputers van het heden worden soms nog steeds vuistregels gebruikt, maar dit is slechts om de computer sneller te laten zetten.

 

Een andere tactiek

De basis van de hedendaagse schaakcomputer berust op een andere methode. Er wordt gekeken naar de opstelling na de zet in plaats van naar de zet zelf . Dit wordt gedaan voor elke mogelijke zet. Vanuit deze opstellingen kan weer een aantal zetten gespeeld worden en hiervoor wordt hetzelfde gedaan. De computers scannen op deze manier ver vooruit en bekijken bij welke positie ze het grootste voordeel hebben. Denk hierbij aan een voorsprong in materiaal, plaatsing van de stukken of misschien zelfs het schaakmat zetten van de tegenstander. Aan alle stukken wordt een relatieve waarde toegekend die ook afhankelijk is van de plaatsing en van de overige stukken. Krachtige schaakcomputers kunnen op deze manier makkelijk 25 zetten vooruitkijken vanaf een lastige positie. In het voorbeeld hierboven zal de moderne schaakcomputer dezelfde zet spelen, omdat na evaluatie van de posities gevonden zal worden dat na deze zet met de loper de positie van de computer het meest verbeterd zal zijn. Het kan goed vergeleken worden met een simpeler spel: boter-kaas-en-eieren.

Elke zet wordt gevolgd door een verdeling van kruisjes en rondjes. Het aantal mogelijke situaties is veel geringer dan bij schaken, maar het idee is precies hetzelfde. Voor elke mogelijke beginzet is er een beperkt aantal vervolgen van het spel. Je wilt steeds de tak kiezen die leidt tot de verdelingen die het meest in jouw voordeel zijn. Omdat bij een spel boter-kaas-en-eieren in totaal maar weinig  zetten mogelijk zijn, is het spel al snel berekend. Dat wil zeggen, het is makkelijk te vinden wat de eerste beste zet is en het beste antwoord hierop. Bij schaken is dit veel lastiger, omdat er per beurt veel meer mogelijkheden zijn en er veel meer beurten in totaal gespeeld kunnen worden.

Het aantal te evalueren posities groeit natuurlijk exponentieel per vooruitberekende zet en per stuk op het schaakbord. Daarom wordt er vooral voor de openingszetten vaak gebruik gemaakt van een tweede techniek. Dat is het direct instellen van zetten voor bepaalde posities. Door de schaakjaren heen zijn veel openingen geanalyseerd door zowel schaakcomputers als mensen en hiermee zijn bepaalde zetten als goed of slecht gemarkeerd. Deze informatie gebruikt de computer om in de openingen of vaak voorkomende posities een zet te maken zonder berekeningen te doen. Bij boter-kaas-en-eieren hoef je waarschijnlijk ook niet na te denken waar je het eerste kruisje of rondje zet omdat je hopelijk weet dat je bij de eerste zet de hoek pakt. Natuurlijk moet de computer wel telkens zoeken of de huidige positie in alle voorgeprogrammeerde posities terug te vinden is en dat kan ook tijd kosten. Een goede schaakcomputer neemt dus het beste van beide technieken, en kan zo sommige zetten weglaten binnen de evaluatie waardoor gelijk een grote vertakking wegvalt.

 

Het niveau van een schaakcomputer

De huidige schaakcomputers zijn vaak in te stellen op moeilijkheidsgraad. Bij een lage moeilijkheidsgraad rekent de computer simpelweg weinig zetten vooruit en bij een hogere moeilijkheidsgraad veel meer. De computer zou op laag niveau bijvoorbeeld de volgende zet kunnen spelen:

De zwarte loper slaat de pion op h2, maar nadat wit zijn pion op g2 een plek naar voren schuift is de loper gevangen en kan een paar zetten later geslagen worden. De computer berekent dat hij na het slaan van de pion twee zetten lang een pion voorstaat maar rekent niet ver genoeg vooruit en ziet dus niet dat de loper later geslagen wordt. Een sterkere schaakcomputer zou zo een fout nooit maken, maar kan ook niet oneindig ver vooruitkijken.

 

Het eindspel

Met de verbetering van gebruikte algoritmes kan een schaakcomputer verbeterd worden, maar het overgrote deel van de kracht van een schaakcomputer komt van de processoren van de machine waarop de schaakcomputer draait. Bij verbetering of toevoeging van processoren zal het aantal berekenbare zetten per seconde toenemen en hiermee ook het niveau van de schaakcomputer. Hoewel er steeds betere processoren op de markt komen, zal het nog lang duren voordat een schaakcomputer het ‘perfecte potje’ zal kunnen berekenen. In het perfecte potje is het spel van zowel zwart als wit foutloos. Om dit te berekenen zou volgens Shannon echter 10^90 jaar nodig zijn op een 1 MHz processor omdat het ofwel alle 10^120 verschillende mogelijke hele schaakspellen zou moeten kunnen vergelijken, ofwel voor 10^43 mogelijke opstelling een beste zet gereed hebben.  Omdat computers tegenwoordig vaak uitgerust zijn met processoren die duizenden malen sneller zijn dan 1 MHz, zal het zeker geen 10^90 jaar duren, maar het is onrealistisch dat we het perfecte potje ooit berekend zullen zien. Wel is bekend dat het zeer waarschijnlijk is dat het perfecte potje zal eindigen in een remise. Dit is het geval omdat uitgerekend is dat beide partijen vanaf veel eindposities een gelijkspel af kunnen dwingen. Wel zal ontwikkeling van schaakcomputers helpen bij het evalueren van zetten en opstellingen. Openingszetten kunnen nog beter gewaardeerd worden en schaakcomputers zullen sneller kunnen zetten.

 

De invloed van de computer

Een andere vraag is of het perfecte potje, als dit ooit gevonden wordt, invloed zal hebben op het schaakspel dat mensen spelen. Het antwoord hierop is nee. Dit perfecte spel zou erg lang zijn, omdat geen van beide kanten fouten zou maken. Het zou een zeer langzaam spel zijn met heel af en toe een uitwisseling tussen twee stukken van dezelfde waarde. Mochten beide spelers deze reeks zetten kunnen onthouden, dan zou er, als ze speelden om te winnen, geen reden zijn om dit specifieke spel te spelen. Wilden ze beiden spelen om een remise, dan zijn er snellere spellen om dit te verkrijgen. Zodra één van de twee spelers bij één zet afwijkt, zouden ze vanaf dit moment op eigen kracht en kennis door moeten spelen. Hetzelfde doet zich op dit moment al voor met de openingszetten. Op elk niveau binnen het schaken komt een grote verscheidenheid aan openingsreeksen voor. Op hoog niveau spelen schakers soms weloverwogen zetten die niet als beste bestempeld zijn. Deze openingen zijn daarom soms niet in de voorbereiding van de tegenspeler meegenomen, en kunnen dus tot een voorsprong leiden.

Omdat schaakcomputers op het moment al sterker zijn dan mensen, is nog diepere analyse van bepaalde zetten in bepaalde situaties de enige reden om schaakcomputers nog verder te ontwikkelen. Veel veranderingen in het menselijk schaken zullen schaakcomputers daarom niet meer brengen. Voor het schaken hoeven we computers dus niet nog sterker te maken, maar mochten computers ooit het schaakspel helemaal uitrekenen, dan kunnen we nog prima een potje schaken.


Dit artikel is geschreven door Pieter Dilg

Deel dit artikel:

By Daniele Zedda • 18 February

← PREV POST

By Daniele Zedda • 18 February

NEXT POST → 34
Share on