Neuraal Schaken

door Frits Schalij

Het jaar 1997 is voor ons schakers erg belangrijk. Het is het jaar dat voor het eerst een schaakcomputer een match van de wereldkampioen won en wij mensen de hegemonie in de schaakwereld kwijt raakten. Deep Blue klopte Kasparov met 4-2. Deep Blue is een schaakprogramma dat op speciaal voor het schaken door IBM ontwikkelde hardware draait. Soortgelijke programma’s kunnen ook op gewone PC’s draaien en omdat de hardware van PC’s steeds krachtiger wordt, kan tegenwoordig een goed schaakprogramma op een simpele laptop al de wereldkampioen verslaan. Sterker nog, het programma Stockfish op een smartphone is al beter dan de wereldkampioen.

Deze schaakcomputers hebben de schaakwereld veranderd. Ik vind het zelf leuker geworden. Als ik tijdens het naspelen van een partij het grootmeesterlijk commentaar niet begrijp omdat ik denk dat er een simpele weerlegging is, leg ik dit even voor aan mijn schaakcomputer. Mijn schaakcomputer vertelt mij dan precies waarom mijn variant niet juist is. Vroeger bleef ik dagenlang met dit soort problemen rondlopen. Ook grootmeesters maken graag gebruik van schaakcomputers. Vroeger had een topspeler een heel secondantenteam om openingen voor te bereiden, tegenwoordig doet iedere schaker dit zelf op zijn laptopje. Het nadeel  is wel dat het topschaken hierdoor wat kil en zakelijk is geworden.  Schaakcomputers staan niet bekend om hun creativiteit, maar meer om hun kwaliteit geen fouten te maken. Dit weerspiegelt zich in het huidige topschaak.

Brute force

Het principe van een schaakprogramma is eenvoudig en werd al in 1949 door Shannon bedacht. In een gegeven stelling ga je alle mogelijke zetten af en na iedere zet doe je hetzelfde in de nieuwe stelling. Dit blijf je doen tot op een van te voren vastgestelde diepte. Zo krijg je een boom van zetten. De stellingen in de bladeren van deze boom ga je evalueren met behulp van schaakkennis. Dit evalueren levert een getal op; een positief getal betekent ‘wit staat beter’, een negatief getal betekent  ‘zwart staat beter’. Een evaluatie van +1.00 betekent ‘wit staat ongeveer één pion voor’. Vervolgens ga je de evaluaties van de bladeren terugrekenen naar de beginstelling. Dit doe je door iedere keer als zwart aan zet is het minimum te nemen van de evaluaties van alle zetten en als wit aan zet is het maximum. Je gaat er dan van uit dat zowel zwart als wit telkens de beste zet spelen. Dit principe van alle zetten doorrekenen heet brute force. Er zijn ook wel programma’s gebaseerd op andere principes, maar die zijn veel minder succesvol gebleken. Op de brute force aanpak zijn in de loop der jaren een groot aantal optimalisaties gekomen. Zo hoef je bijvoorbeeld niet alle zetten door te rekenen: als je van een slechte zet een weerlegging vindt hoef je niet te zoeken naar nog een weerlegging. Dit heet alpha-beta pruning. Als je alpha-beta pruning slim toepast hoef je aanzienlijk minder stellingen door te rekenen. Verder is het ook niet zinvol om een stelling te evalueren als je net in een ruil zit. Een stelling wordt pas geëvalueerd als er niets meer geslagen kan worden en niemand schaak staat. Zolang dit niet aan de hand is wordt de zettenboom uitgebreid. Optimalisaties op de brute force aanpak is een wetenschap op zich geworden. Ook de evaluaties van de stellingen is enorm verbeterd.  Steeds meer schaakkennis wordt op een steeds geavanceerdere manier gecodeerd. Dit heeft ertoe geleid dat de beste schaakprogramma’s zoals Stockfish, Houdini en Komodo, draaiend op een normale PC,  een schaakkracht van meer dan 3200 hebben. In openingen en eindspelen zijn deze schaakprogramma’s vaak minder sterk, daarom zijn ze uitgerust met een uitgebreide openingenbibliotheek die 200 jaar menselijke ervaring met schaakopeningen representeert en een eindspel database van alle eindspelen met zeven of minder stukken.

Spectaculaire revolutie

Op 5 december 2017 is de schaakwereld opgeschrikt. DeepMind, een dochterbedrijf van Google, publiceerde een artikel waarin ze uitlegde dat ze een schaakcomputer hebben gemaakt, gebaseerd op een  totaal ander principe. Dit schaakprogramma noemen ze Alpha Zero. Alpha Zero hebben ze een match van 100 partijen laten spelen tegen Stockfish, draaiend op zeer krachtige hardware. Hun programma won met 64-36. Met wit won het programma 25 partijen en speelde 25 keer remise, met zwart won het 3 keer en speelde 47 keer remise. In het artikel staan ook 10 partijen uit deze match. Deze partijen zijn spectaculair! Ze zijn heel anders dan partijen die we gewend zijn van schaakcomputers. Vaak offert Alpha Zero in de opening één of twee pionnen of zelfs een stuk voor lange termijn compensatie. Pas in het verre eindspel blijkt de waarde van het offer. De eindspel techniek die Alpha Zero voor de dag legt is sowieso adembenemend.

Neuraal netwerk

Alpha Zero is gebaseerd op een neuraal netwerk. Neurale netwerken zijn een poging om het menselijk denken te imiteren. In onze hersenen zitten neuronen. Een neuron heeft een aantal ingangen (dendrieten) en één uitgang (axon). De uitgang van de neuron zit vast aan een aantal ingangen van andere neuronen met een verbinding (synaps). Een neuron kan vuren. Als het vuurt brengt het een lading aan bij alle andere neuronen waarvan de ingang verbonden is met de uitgang van deze neuron. De waarde van de lading hangt af van de verbinding. In een neuron worden alle ladingen verzameld en zodra de lading hoger is dan een bepaalde drempel, die voor iedere neuron weer anders is,  gaat de neuron ook vuren. Onze hersenen bestaan uit een zeer groot aantal neuronen die op complexe wijze met elkaar verbonden zijn. De ingangen van sommige neuronen zijn verbonden met zenuwuiteinden van zintuigen zoals onze ogen en oren. Deze zenuwuiteinden zorgen voor prikkels die de neuronen in werking zetten.

Een neuraal netwerk is een wiskundige abstractie van dit model. Het is een heel simpel model. De prikkels van de zintuigen worden  gerepresenteerd door een matrix, of eigenlijk door een tensor. Voor degenen die deze begrippen niet meer goed herinneren van de middelbare school: een rijtje getallen, of 1-dimensionale getallenstructuur, heet een vector. Een rechthoek van getallen, of een 2-dimensionale getallenstructuur, heet een matrix. Een balk van getallen, of een 3-dimensionale getallen structuur, heet een tensor. Een hogere dimensie getallenstructuur wordt ook een tensor genoemd. Een 0-dimensionale getallenstructuur, oftewel een enkel getal, heet in deze terminologie een scalair. De prikkels van de zintuigen worden dus gerepresenteerd door een tensor. Deze prikkels zitten met verbindingen vast aan neuronen. Een laag van neuronen wordt ook gerepresenteerd door een tensor. De overdracht van de prikkels naar de neuronen gaat met een tensor vermenigvuldiging. Een tensorvermenigvuldiging is een meerdimensionale versie van een matrixvermenigvuldiging. De coëfficiënten van de vermenigvuldigingstensor zijn de sterktes van de verbindingen van de neuronen (synapsen).   In de neuronen worden de waardes vergeleken met een drempel waarde. Als de waarde meer is wordt het één, anders nul. Na de eerste laag van neuronen komen meerdere lagen van neuronen. De overdracht gaat telkens hetzelfde: eerst een tensorvermenigvuldiging, daarna een vergelijking met een drempelwaarde.

Training

Het concept van neurale netwerken is al heel oud maar was nooit succesvol totdat het zo’n tien jaar geleden opeens de aandacht trok bij beeldherkenning.  Bij beeldherkenning is het de kunst om te detecteren welk voorwerp op een plaatje staat. Gecomputeriseerde beeldherkenning werkte nooit goed totdat neurale netwerken hiervoor werden ingezet. Bij neurale netwerken gaat het erom de coëfficiënten en drempelwaardes goed te kiezen. Deze waardes worden bepaald door het netwerk te trainen. Bij beeldherkenning is de input van het neurale netwerk het plaatje en de output een vector van waarschijnlijkheden, ieder getal van die vector is de waarschijnlijkheid dat het neurale netwerk “denkt” dat dit op dit plaatje een bepaald voorwerp staat.  Tijdens het trainen krijgt het neurale netwerk een groot aantal plaatjes waarbij bekend is wat er op staat. De uitkomst van het neurale netwerk wordt vergeleken met de echte uitkomst en afhankelijk van de fout worden de coëfficiënten en drempels in het netwerk aangepast. Als het netwerk goed getraind is met heel veel plaatjes kan het zelf detecteren wat op een plaatje staat, zelfs beter dan mensen kunnen. Het succes van neurale netwerken in beeldherkenning heeft een ware hype veroorzaakt. Neurale netwerken worden nu succesvol toegepast op meerdere terreinen zoals vertalen en zelfrijdende auto’s. Het concept is telkens heel simpel: maak een neuraal netwerk, train dit met heel veel data waarvan bekend is dat het correct is, en na een tijdje kan het neurale netwerk het zelf. De reden dat neurale netwerken vroeger niet succesvol waren en nu wel is dat de computers vroeger nog niet krachtig genoeg waren hiervoor. Neurale netwerken zijn nu zo belangrijk dat Google een aparte processor heeft ontworpen om tensorvermenigvuldigingen uit te voeren: de TPU (Tensor Processing Unit).

Go

Neurale netwerken worden ook in spelletjes toegepast. In 2013 kwam DeepMind met een neuraal netwerk dat het Atari spel Breakout kon spelen. Breakout is een videospel waarin je een paddle naar links en rechts kunt bewegen om een balletje in het spel te houden. Je moet met het balletje proberen balkjes aan de bovenkant van het scherm weg te spelen.

Het scherm van het Atari spel Breakout

Als input kreeg het netwerk de pixels van het scherm en het puntenaantal dat het gescoord had de output was de paddle beweging naar links of rechts. Na een paar uur trainen kon het het balletje in het spel houden en na nog een paar uur trainen “wist” het dat het een gaatje moest schieten aan de zijkanten en via dit gaatje het balletje naar de bovenkant te schieten.

In maart 2016 schokte DeepMind de wereld door met een Go programma te komen dat de wereldkampioen versloeg. Dit programma was een neuraal netwerk dat de regels van Go kende. Het was getraind met eerst veel partijen van sterke Go spelers en vervolgens door het telkens tegen zichzelf te laten spelen en afhankelijk van de uitslag de coëfficiënten aan te passen. Go is een spel dat zich goed leent voor neurale netwerken. De regels zijn eenvoudig, het spel zit vol symmetrieën (je kunt het bord draaien en spiegelen, het spel blijft hetzelfde) en zetten hebben een lokaal karakter.

Neuraal schaken

Schaken is anders. Schaakregels zijn complex, door de loop van de pionnen en rokades is er geen symmetrie en een stuk als de dame kan van één kant van het bord naar de andere kant van het bord. Bovendien zijn er sterke schaakcomputers gebaseerd op brute force die onverslaanbaar zijn.

Toch is het gebeurd. Op 5 december 2017 publiceerde DeepMind een artikel waarin ze beschreven hoe ze een neuraal netwerk hebben gemaakt dat de sterkste schaakcomputer en de sterkste Shogi computer (Japans schaken) kan verslaan. De enige schaakkennis die in het neurale netwerk zit zijn de schaakregels. De input is een representatie van een schaakstelling en een functie die uit deze representatie alle zetten genereert. De output is een vector van waarschijnlijkheden die voor iedere mogelijke zet de kans aangeeft dat dit de beste zet is en een scalair die de beoordeling van de stelling aangeeft. Dit neurale netwerk met de naam Alpha Zero  is getraind in 24 uur gebruikmakend van enkele duizenden TPU’s. Tijdens de training lieten ze het neurale netwerk telkens 4096 partijen tegen zichzelf spelen, met de resultaten van deze partijen werden de coëfficiënten en drempels aangepast. Dit herhaalden ze 700.000 keer. Na vier uur trainen was het programma al even sterk als Stockfish. De laatste uren van de training werd het slechts marginaal sterker. Het programma speelt door uitgaande van een bepaalde stelling deze stelling vaak tegen zichzelf uit te spelen. Het berekent het gemiddelde van alle verkregen uitkomsten om de beste zet te bepalen. Waar Stockfish 70.000.000 stellingen per seconde bekijkt, bekijkt Alpha Zero 80.000 stellingen per seconde. Alpha Zero boekt haar grote winst door alleen naar goede zetten te kijken.

Een geschiedenis van de schaakevolutie in vier uur

Voor de training bezat Alpha Zero behalve de schaakregels geen specifieke schaakkennis. Toch speelt Alpha Zero openingen die wij modern zouden noemen. In de tien gepubliceerde partijen komen drie partijen voor met een variant van het dame-Indisch die in de jaren 80 populair was en die Kasparov ook een keer speelde in een WK match tegen Karpov. Al deze openingskennis heeft Alpha Zero tijdens de eerste uren training zelf opgedaan. Het is interessant om te zien welke openingen Alpha Zero speelde tijdens de training. Als antwoord op 1.e4 “ontdekt” Alpha Zero na 1:45 uur trainen dat het Frans een goed antwoord is. Frans blijft de favoriete opening tot op 2:00 uur trainen, dan wordt het Frans vervangen door de Caro Kan. Caro Kan blijf bijna twee uur lang de eerste keuze van Alpha Zero, maar na 3 uur en 55 minuten komt het verlossende woord: het beste antwoord op 1.e4 is Berlijns. Als eerste zet speelt Alpha Zero het liefst 1.d4, maar als de tegenstander antwoordt met 1…e6 aarzelt het geen moment om 2.e4 te spelen. Achteraf heeft Alpha Zero nog een themamatch Frans gespeeld tegen Stockfish. Met wit won het 39 keer bij 11 remises. Tegen 1.d4 speelt Alpha Zero het liefst Slavisch. Ook de Engelse opening komt vaak voor in de trainingspartijen.

De partijen

De tien partijen die openbaar gemaakt zijn in het artikel van DeepMind zijn allemaal de moeite van het naspelen waard. Ze zijn gepubliceerd op meerdere schaaksites. Bijvoorbeeld chess24. Waarschijnlijk zijn deze tien partijen zorgvuldig gekozen uit de honderd gespeelde partijen. Ik kan me niet voorstellen dat ze alle honderd zo interessant zijn. Ik wil enkele stellingen uit de partijen laten zien om een idee te geven van de spelstijl van Alpha Zero.

partij 5

Deze stelling komt uit de vijfde partij. Wit heeft twee pionnen geofferd. Het kluitje zwarte stukken op de damevleugel maakt een zielige indruk. Hoe moet wit nu verder?

partij 9

Dit is partij negen. De contouren van de Franse opening zijn nog herkenbaar. De zwarte loper op b7 is blijvend slecht. Hoe realiseert wit zijn voordeel?

Partij 10

Dit is uit partij 10. Wit heeft een pion geofferd voor activiteit. Met zijn laatste zet (g6-g5) dreigt zwart het witte paard te slaan. Hoe zet wit zijn aanval voort?

partij 10

Uit dezelfde partij. Wit staat een stuk en een pion achter maar heeft het initiatief. De witte dame staat aangevallen. Hoe behoudt wit het initiatief?

partij 10

Ook weer uit partij tien. Wit staat nog steeds een stuk achter, nu met twee pionnen. Hoe zet wit de aanval voort?

De oplossingen vind je door de partijen na te spelen. Bij acht van de tien partijen zijn ook video’s op internet met uitleg over de partijen. Het is een aanrader ook deze video’s te bekijken. In de eerste twee partijen heeft Alpha Zero zwart. In de andere acht wit.

partij 1 Berlijnse verdediging. Stockfish offert een stuk voor 2 pionnen. AlphaZero offert vervolgens twee extra pionnen voor initiatief. In het eindspel van toren, twee lopers en 3 pionnen tegen toren, paard en 7 pionnen weet Stockfish geen plan te bedenken en wordt overtuigend weggespeeld.

partij 2 Berlijns.

partij 3 Dit is de computerversie van de onsterfelijke zetdwang partij. Net als de echte onsterfelijke zetdwang partij van Nimzowitsch is de opening Dame-Indisch.

partij 4 Frans. Alpha Zero realiseert voordeeltje van een onbeduidende pion.

partij 5 Onwaarschijnlijk loperoffer. Alpha Zero prefereert telkens initiatief boven materiaal. Ook een perfecte eindspeltechniek.

partij 6 (Geen video) Loperpaar tegen paardenpaar. Goed toreneindspel.

partij 7 (Geen video) Lange manoeuvreerpartij.

partij 8 zie ook de video van Daniel King. Als een mens dit had gespeeld hadden we gezegd: wat een fijn positioneel gevoel.

partij 9 Frans. Het stukoffer in het eindspel vind ik verbluffend.

Partij 10 zie ook de video van Daniel King. Je gelooft je eigen ogen niet. Dit is tegen een schaakcomputer met een rating van boven de 3200!

Voor meer artikelen zie Schaakrubriek.