Schaken met computers 4

In 1957 was de eerste partij van een schaakprogramma op een IBM computer tegen een menselijke schaker. Toen verloor de computer nog eenvoudig. In 1997 verloor de wereldkampioen schaken Garri Kasparov een match tegen Deep Blue met 2½ – 3½. Deep Blue en de opvolgers Fritz en Stockfish schaakten zo verschrikkelijk goed, omdat ze veel sneller en veel dieper varianten konden uitrekenen dan menselijke schakers. Ik schreef er al eerder over in Schaken met computers 2.

Eind 2017 kwam opeens AlphaZero, die door middel van Artificial Intelligence (AI) gewoon even op een middag miljoenen schaakpartijen tegen zichzelf speelde, op deze manier steeds beter ging spelen en daarna in staat was om Stockfish 8 te verpletteren in een test. Voor alle duidelijkheid: AlphaZero gebruikte geen openingen-, eindspelen- of partijen-databases om te leren schaken. Het experiment was juist om zonder (zero) kennis vooraf schaken te leren!

Het leervermogen van AlphaZero is gebaseerd op neurale netwerken. Die waren reeds in de jaren 80 uitgevonden om de neuronen van het menselijk brein te imiteren. Maar pas in deze eeuw werden computers snel genoeg om met neurale netwerken bijvoorbeeld te leren schaken.

Stockfish 8 was in 2017 de sterkste engine tot AlphaZero verscheen. Daarna volgde Leela Chess Zero (de naam zegt het al) oftewel Lc0 en ook Stockfish met een neuraal netwerk dat ze Efficiently Updatable Neural Network (NNUE) noemden. Sindsdien werd het verschil in speelsterkte tussen computers en mensen groter en zal in de toekomst nog groter worden, omdat het NNUE voortdurend wordt getraind.

De ratings van de engines: Stockfish 18 en Lc0 waren boven 3700 en die van grootmeesters zoals Magnus Carlsen, Fabio Caruana en Hikaru Nakamura waren boven 2800 oftewel 900 lager! Met de formules van Arpad Elo kun je uitrekenen dat de kans dat die grootmeesters van die engines winnen ongeveer 0,0056 is.

Nobelprijzen voor AI

AlphaZero was een onderzoeksproject van DeepMind. Bovendien was AlphaZero een soort zijproject. Het onderzoek begon met AlphaGo Zero voor go (een moeilijker spel dan schaken) en in 2017 gebruikten ze ook neurale netwerken voor schaken en shogi (Japans schaken). Zie Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm.

Daarna heeft DeepMind een veel nuttiger probleem aangepakt namelijk uitzoeken hoe je eiwitmoleculen kunt vouwen. Zie Highly accurate protein structure prediction with AlphaFold. De overeenkomst met schaken is dat er oneindig veel varianten mogelijk zijn om eiwitmoleculen te vouwen. Bij schaken leidt de ene variant tot mat en na een andere variant ga je zelf mat. In de natuur is de ene variant van een gevouwen eiwit correct, goed of gezond en een andere variant gevaarlijk, slecht, of ongezond.

De Koninklijke Zweedse Academie van Wetenschappen vond AlphaFold zo nuttig dat ze in 2024 de Nobelprijs voor scheikunde onder anderen hadden toegekend aan DeepMind. In 2024 waren er in feite twee Nobelprijzen voor AI: de Nobelprijs voor scheikunde voor bovengenoemde toepassing van AI en de Nobelprijs voor natuurkunde voor de ontwikkeling van neurale netwerken sinds de jaren 80.

AI voor iedereen

Sinds de introductie van ChatGPT in 2022 kan iedereen AI gebruiken om rapporten te schrijven, plaatjes en filmpjes te bewerken, werkstukken te maken en zo voort. ChatGPT gebruikt een neuraal netwerk dat is getraind voor taal: Large Language Model (LLM). Tegenwoordig zijn er veel meer LLM’s zoals Gemini van Google, CoPilot van Microsoft, Claude van Anthropic en die van Meta in Facebook, Instagram en WhatsApp die het voor ons nog makkelijker hebben gemaakt om AI te gebruiken.

Deskundigen wijzen op de nadelen van AI. Gebruikers nemen zonder nadenken informatie over van zo’n LLM. Het internet raakt vervuild met nog meer rare filmpjes en onzin verhalen (AI-slop). AI is slecht voor het milieu, want de datacentra met de computers voor LLM’s gebruiken ontzettend veel stroom en water. AI kost heel veel geld. Nvidia gaat $500.000.000.000 investeren in nog meer datacentra. Verantwoordelijke mensen stellen voor om AI aan banden te leggen, niet te gebruiken in wapensystemen en zo. Zelfs paus Leo XIV gaf zijn mening en heel opmerkelijk: Bill Gates van Microsoft en Dario Amodei van Anthropic. Klik op de links om meer te lezen.

Kan AI ons vervangen? Waarschijnlijk niet. Verdwijnen er banen? Ja natuurlijk, want AI kan allerlei dingen veel sneller dan mensen. Maar uiteindelijk ontstaan totaal nieuwe banen (paradox van Jevons). Maakt AI dommer? Ja, want luie studenten en luie leerlingen leren niet meer zelf nadenken, maar laten denken over aan AI. Het goede nieuws is dat wij schakers daarvan geen last hebben. Wij vinden zelf nadenken nog steeds leuk. Schaken is een denksport!

Je moet natuurlijk altijd zelf blijven nadenken. ChatGPT, CoPilot en Gemini zijn getraind met enorme hoeveelheden tekstvoorbeelden om statistische verbanden te herkennen tussen woorden, zinnen en ideeën. Ze kunnen daarmee antwoorden genereren, maar ze snappen niet wat ze doen. Ze kunnen alleen goed voorspellen wat een zinvol antwoord zou kunnen zijn, maar zo’n antwoord kan dus gewoon fout zijn!

De wiskunde achter dat geautomatiseerd leren (trainen) is nog wel te begrijpen. Maar hoe zo’n LLM uiteindelijk werkt, kunnen mensen helaas niet meer begrijpen, omdat de berekeningen die het LLM doet onnavolgbaar zijn. Te veel en te ingewikkeld.
Desondanks wil ik in dit artikel proberen uit te leggen hoe dat geautomatiseerd leren voor schaken werkt. Zonder de wiskunde, maar wel over algoritmes, evaluatiefuncties en computers programmeren.

Computers programmeren voor AI

AI is pas recent mogelijk geworden mede dankzij ongelooflijke ontwikkelingen op het gebied van de elektronica: die begon met relais en radiobuizen tijdens de Tweede Wereldoorlog gevolgd door transistoren in de jaren 60, chips sinds de jaren 70 en tegenwoordig speciale chips voor AI (zoals die van Nvidia). De snelheid van computers en de grootte van geheugens namen exponentieel toe terwijl de elektronica juist exponentieel kleiner werd (wet van Moore).

Bijzonder is dat de architectuur van computers sinds 1945 niet wezenlijk is veranderd. Menselijke rekenaars doen het op papier: twee getallen onder elkaar schrijven, optellen of aftrekken en dan de som of het verschil onder de streep opschrijven. Elektronische rekenaars oftewel computers rekenen met nullen en enen (geen stroom of wel stroom) en schrijven in een elektronisch geheugen. Ze doen dat naar aanleiding van instructies, die ook in dat elektronische geheugen staan. Zulke instructies zijn gecodeerd in de machinetaal van een specifieke computer: bereken de som of het verschil van twee getallen, schrijf de uitkomst naar een bepaalde plek in het geheugen, zoek een getal in een rij getallen, voer een serie instructies uit (of sla ze juist over) of manipuleer de nullen en enen van een getal. Dit is zo ongeveer alles wat de elektronica van een computer kan. De rest moeten we programmeren.

De kunst van computers programmeren was vroeger: een serie ontzettend slimme instructies zo efficiënt mogelijk in piepkleine elektronische geheugens proppen. Computerprogramma’s gecodeerd in machinetaal waren compact en complex. Briljante programmeurs schreven nog slimmere computerprogramma’s (zoals programmeertalen) om het programmeren te vereenvoudigen. Toen computers sneller werden en de geheugens groter, hoefden code niet meer zo compact en complex te zijn. We gebruikten standaard ontwerptechnieken en schreven code die beter leesbaar is voor andere programmeurs. Computers programmeren veranderde van een kunst in een ambacht: software enigineering.

Door AI is alles weer anders geworden. LLM’s en andere neurale netwerken zijn code, die niet zijn geschreven door menselijke programmeurs, maar door computers na eindeloos experimenteren met enorme hoeveelheden teksten, plaatjes, filmpjes of door miljoenen schaakpartijen te spelen. Het resultaat daarvan is een immense hoeveelheid, vreselijke complexe code die totaal onleesbaar is voor menselijke programmeurs. Meer hierover later in dit artikel.

Mijn persoonlijke geschiedenis met schaken en AI

De term Artificial Intelligence komt uit Amerika en werd voor het eerst gebruikt in 1955, mijn geboortejaar. De ambitie was toen al om denkende machines te maken! Maar in die tijd bestonden nog amper computers, was computers programmeren onmogelijk ingewikkeld en waren de toenmalige computers vreselijk traag. Technisch wetenschappelijk rekenwerk werd vooral gedaan door menselijke computers en vaak waren dat vrouwen. Zie bijvoorbeeld de film Hidden Figures over drie zwarte vrouwen die als computers voor de NASA werkten.

Computers programmeren werd iets eenvoudiger toen programmeertalen werden uitgevonden: FORTRAN voor technisch wetenschappelijk rekenwerk en COBOL voor administratieve automatisering. In de academische wereld van het AI-onderzoek werd LISP de belangrijkste programmeertaal. Toen ik in de jaren 70 kennis maakte met AI, bestonden verschillende dialecten van LISP om kennis mee vast te leggen in expert systemen zoals MYCIN en XCON. Vanuit Amerikaanse universiteiten werden bedrijven opgericht zoals Teknowledge en IntelliCorp om die expert systemen te maken op peperdure LISP-computers van Symbolics, LMI en Xerox. Het bouwen van expert systemen was nog mensenwerk. Knowledge enigineers interviewden experts om hun kennis te begrijpen en vervolgens te coderen. Dat was een moeizaam en daarom kostbaar proces.

Zo ongeveer tussen 1975 en 1990 hield ik mij als programmeur, adviseur en zelfs knowledge enigineer bezig met schaken en AI. Ik werkte achtereenvolgens bij Hoogovens aan veel verschillende projecten en bij Lithp Systems aan expert systemen op de IBM PC. Ik mocht naar wetenschappelijke congressen over AI in binnen- en buitenland. Ik was nog jong en kon alle ontwikkelingen nog enigszins bijhouden.

Het begon voor mij allemaal in het nieuwe Rekencentrum van Hoogovens. Dat was toen een hypermodern gebouw met kantoren rond een technische ruimte met daarboven zalen met mainframe computers van Control Data, Univac en later IBM. Allemaal enorme luchtgekoelde kasten en veel apparaten om ponskaarten te verwerken. De Univac 418-III computers waren via een zaal vol enorme modems verbonden met PDP-8 en PDP-11 computers in fabrieken en kantoren elders op het terrein van de Hoogovens.

Beeldschermen met toetsenborden waren er toen nog niet! Om computers te programmeren moesten de heren programmeurs netjes schrijven op ponsconcepten. Die handgeschreven formulieren werden vervolgens door dames in het Rekencentrum ingetoetst als gaatjes in ponskaarten. Daarna werd de stapel ponskaarten gevoerd aan een computer. De computer drukte een lijst af van de ponskaarten met meestal allemaal foutboodschappen. Een bode bracht de stapel ponskaarten met de lijst terug naar de programmeur, die de fouten ging verbeteren net zo lang tot het computerprogramma helemaal goed was en de computer precies deed wat de bedoeling was.

Ik hield de computers aan de praat: ponskaarten voeren, lijsten afscheuren, tapes verwisselen, op knoppen drukken en zo voort. Daarnaast leerde ik programmeren op een Univac 418-III. Daarvan waren er twee. Een moest dag en nacht productie draaien in verbinding met fabrieken en kantoren. De andere was voor de programmeurs om op te testen en stond stand by om de productie over te nemen. In de avond- en nachtdienst kon ik die Univac 418-III gebruiken om annuïteitenhypotheken en priemgetallen uit te rekenen en spelletjes te maken zoals boter, kaas en eieren en schaken. Het boter, kaas en eieren programma werd beter naar mate je vaker tegen dat programma speelde. Het was dus al een lerend programma! Het schaakprogramma noemde ik IGM (Ik Ga Mat) en het was, voor zover ik weet, het tweede complete schaakprogramma van Nederland. Dit allemaal nog met ponskaarten, die ik in de nacht zelf moest maken en bovendien in de machinetaal van de Univac 418-III.

Pas in 1978 toen ik als programmeur gewoon overdag op een kantoor werkte, kwamen er beeldbuizen met toetsenborden, waarmee ik als programmeur zelf mijn programma’s kon intoetsen en testen op een computer die nog steeds op afstand in het Rekencentrum stond en die ik moest delen met veel andere programmeurs. In die tijd bestonden nog geen personal computers in het bedrijfsleven en niemand in Nederland gebruikte LISP-computers om expert systemen te ontwikkelen.

Ondertussen was de microprocessor chip uitgevonden, kwamen er hobbyisten die zelf computers in elkaar knutselden en ik werd in 1977 lidnummer 71 van de Hobby Computer Club (HCC). Op een AI-congres te Amsterdam in 1980 maakte ik kennis met Gerald Jay Sussman, die daar rondliep met een prototype van een LISP-microprocesor chip op zijn revers. Dat vond ik heel gaaf: LISP als machinetaal van een microprocessor!

Zo ontstond het idee om IGM opnieuw te maken met LISP, want die AI programmeertaal was beter geschikt om schaakkennis te coderen en eenvoudiger om te experimenteren dan een machinetaal zoals op de Univac 418-III. Via de HCC kon ik een Maxboard lenen met een 6800-microprocessor en ik kreeg een LISP voor de 6800 die was geprogrammeerd door Frits van der Wateren. Daarna moest ik toch nog veel 6800-machinetaal programmeren om schaken toe te voegen aan LISP.

Pas in 1981 was IGM/Lisp klaar en kon ik daadwerkelijk op een eenvoudige manier ideeën voor IGM testen. Dat was amper op tijd voor het eerste Nederlandse Kampioenschap voor schaakprogramma’s van de Computer Schaak Vereniging Nederland (CSVN). Tot een paar uur voor en tijdens het toernooi werkte ik nog aan KAANVAL. In de tijd dat de tegenstander aan zet was, moest KAANVAL advieszetten genereren, die IGM in zijn analyse zou kunnen gebruiken als IGM wel aan zet was. Een advieszet van KAANVAL moest voldoen aan: 1. dreigt schaak te geven of 2. valt een stuk aan, dat door de koning van de tegenstander teruggeslagen kan worden. KAANVAL was een primitieve manier om schaakkennis over de koningsaanval te coderen, maar werkte goed in deze partij.

Daarna ging het bergafwaarts met IGM. De 6800-computer en mijn IGM/Lisp waren te traag. De concurrenten met snellere computers haalden IGM links en rechts in. Na het 3e NK schaken voor computers in 1983 stopte ik helemaal met IGM. Bij Lithp Systems programmeerde ik nog wel in LISP, maar na 1990 nooit meer.

Expert systemen waren achteraf gezien niet de doorbraak voor AI. Het lukte niet goed om bijvoorbeeld de schaakkennis van grootmeesters te coderen. Voor zover ik weet, waren computers met een LISP-microprocessor nooit verder gekomen dan de ontwikkelingsfase. De industrie voor LISP-computers verdween helemaal. AI-deskundigen noemen deze periode de AI-winter. De periode van nu noemen ze de AI-lente!

LISP bleef wel altijd belangrijk in de academische wereld. Zo ongeveer alle belangrijke ontwikkelingen op het gebied van software enigineering zijn uitgevonden in LISP en leven voort in bijvoorbeeld de internet programmeertaal JavaScript.

Het meest succesvolle Nederlandse schaakprogramma

Voor Frans Morsch was computerschaak een combinatie van twee hobby’s: elektronica en schaken. Hij begon in 1978 met een 6502, de goedkoopste microprocessor die toen beschikbaar was, een experimenteerbord om elektronische schakelingen te maken zonder te solderen en EPROM‘s. In 1983 deed Morsch met zijn zelfgemaakte schaakcomputer mee aan het 3e NK schaken voor computers in Leiden. Zijn schaakprogramma Nona bestond uit ongeveer 4000 instructies in 6502-machinetaal, die hij in het geheugen van een EPROM had gebrand.

In het toernooiboek schreef Morsch over zijn plan van aanpak om Nona steeds beter te maken: “Enerzijds het geleidelijk en moeizaam verbeteren van het programma, anderzijds het beschikbaar komen van steeds snellere en betere chips. Volgend jaar hoop ik te kunnen spelen op een microprocessor die minstens tien keer zo snel is.” En zo geschiedde het. De 6502 was sneller dan voorgangers (zoals de 6800) en kreeg daarna nog snellere opvolgers en ondersteunende chips. Atari en Nintendo deden hetzelfde als Frans Morsch: ze gebruikten de 6502 voor hun spelcomputers. De Apple II en later de Commodore 64 waren beroemde homecomputers met een 6502.

In 1983 werd Nona vierde en in 1984 tweede op het NK schaken voor computers. Beide keren achter grote computers. Vanaf 1985 liet Nona die grote computers achter zich en werd Nederlands kampioen in 1985 en 1986. In Amsterdam 1985 deed Nona op een Apple II voor het eerst mee aan het WK schaken voor microcomputers en won in de categorie amateurs. Datzelfde jaar verscheen de Mephisto Mondial met een 2 MHz 65C02-microprocessor, Nona in 16KB ROM en 2KB RAM! Dankzij deze chips was de Mephisto Mondial relatief goedkoop en daarom heel succesvol. Daarna volgde een hele serie verbeterde opvolgers zoals de Mephisto Super Mondial (zie de foto hiernaast) en in 1992 verscheen zelfs een Oekraïense / Russische kloon.

Frans Morsch was een van die briljante programmeurs die ontzettend slimme instructies zo efficiënt mogelijk in piepkleine elektronische geheugens kon proppen. Dat had hij met Nona al bewezen. Na Nona begon Morsch aan Quest, een nieuw schaakprogramma in de machinetaal van de x86-microprocessor. De aanleiding was IBM, de grootste fabrikant van mainframe computers. IBM introduceerde in 1981 opeens de IBM PC met 4,77 MHz 8088-microprocessor en 256KB RAM. Dat was het begin van de PC-revolutie in het bedrijfsleven. Sindsdien maakt de industrie steeds snellere personal computers met steeds steeds snellere x86-microprocessoren en grotere geheugens (en in deze eeuw zelfs met meer processoren per chip). Precies wat Morsch nodig had voor Quest!

De aanpak van Frans Morsch voor Nona om “geleidelijk en moeizaam het programma te verbeteren en het beschikbaar komen van steeds snellere en betere chips” werkte ook voor Quest ontzettend goed. De concurrentie op het NK schaken voor computers in die tijd was hevig en het niveau steeg enorm. Desondanks werd Quest Nederlands kampioen in 1988, 1994 en 1999!

Ondertussen had New in Chess in 1985 de schaakpartijendatabase voor de personal computer uitgevonden. Zie Schaken met computers 1. ChessBase volgde een paar jaar later met hun schaakpartijendatabase en ze vroegen Frans Morsch of hij Quest daaraan kon toevoegen. Zo ontstond in 1991 Fritz. Eerst alleen voor MS-DOS en vanaf 1996 ook voor Windows. Morsch programmeerde de engine van Fritz 1 tot en met Fritz 13 in 2012. Al die tijd uitsluitend in x86-machinetaal. Tot op heden bestaat geen Fritz voor Apple-computers.

Begin jaren 90 was schaken met computers iets voor wetenschappers, programmeurs en mensen die schaakcomputers zoals de Mephisto Super Mondial leuk vonden. Daarna veroorzaakte Fritz de transitie van de hele schaakwereld naar schaken met computers. Eerst kochten vooral gewone clubschakers personal computers en Fritz om hun partijen te analyseren. Zo werd Fritz het meest succesvolle product van ChessBase. Grootmeesters volgden rond de eeuwwisseling.

In Hong Kong 1995 won Fritz 3 het 8ste WK schaken voor computers. Dat was opmerkelijk, omdat Fritz 3 op een 90 MHz Pentium-microcomputer ook grote computers zoals Deep Blue Prototype versloeg!

De opvolger van Deep Blue Prototype was Deep Blue, de supercomputer van IBM met speciale chips voor schaken, die in 1997 wereldkampioen schaken Garry Kasparov versloeg. Die overwinning was overigens niet overtuigend, maar sindsdien schaakten grootmeesters liever niet tegen computers. Zie Schaken met computers 2.

Vladimir Kramnik was de laatste wereldkampioen schaken die zich voor veel geld liet verleiden om tegen Fritz te spelen. In 2002 won Kramnik nog 2 partijen tegen Fritz 7 en werd het 4 – 4. In 2006 won Kramnik geen enkele partij en won Fritz 10 met 4 – 2. Hieronder staat de allerlaatste partij.

Schaken in bits en bytes

Zoals ik eerder in dit artikel heb uitgelegd, is een computer letterlijk een rekenaar. De elektronica kan eigenlijk uitsluitend rekenen met nullen en enen. De rest moeten we programmeren. Die nullen en enen staan in een elektronisch geheugen en noemen we bits en 8 bits noemen we een byte. Een 8 x 8 schaakbord kunnen we dus vastleggen in 8 bytes, een getal van 64 nullen en enen. Frans Morsch en ik noemen dat een bitboard. Ik zal jullie verder niet lastig vallen met alle details, maar het komt hierop neer dat we de spelregels van het schaken hebben vertaald in instructies in machinetaal die iets doen met die bits.

Vervolgens hebben we allerlei functies geprogrammeerd die nodig zijn om stellingen te analyseren: een zet doen, een zet terug nemen en een groeifunctie om een variantenboom te laten groeien in het elektronische geheugen. De groeifunctie genereert zetten, zodat de variantenboom zich verder vertakt.

Naast deze functies hebben schaakprogramma’s evaluatiefuncties nodig om stellingen te beoordelen en algoritmes om de variantenboom te analyseren. Met name de algoritmes hebben ervoor gezorgd dat computers uiteindelijk dieper konden rekenen dan menselijke schakers. Daarbij hielp het dat de snelheid van computers en de grootte van geheugens exponentieel toenamen terwijl de elektronica exponentieel kleiner werd (wet van Moore). Hoe korter de afstanden binnen de chip (nanometers!), hoe sneller de elektronen zich kunnen verplaatsen om bits aan of uit te schakelen.

Hieronder leg ik uit hoe die evaluatiefuncties en algoritmes zo ongeveer werken. Daarna kom ik terug op de neurale netwerken van moderne schaakprogramma’s zoals Lc0 en Stockfish.

Uitleg over evaluatiefuncties

Een evaluatiefunctie berekent een getal voor de stelling. Een schaakprogramma gebruikt die getallen om stellingen te vergelijken.

Het volgende plaatje laat een variantenboom zien vanuit een stelling uit een partij van de (latere) wereldkampioen Mikhail Botvinnik tegen Sergej Kaminer gespeeld in 1925. Wit is aan zet.
De getallen op het einde van de takken zijn de uitkomsten van een evaluatiefunctie zoals die is beschreven door Botvinnik in Алгоритм игры в шахматы van 1968.

Botvinnik begint met het hout te tellen: 1 voor een pion, 3 voor een loper of paard, 5 voor een toren en 9 voor een dame. Daarna alles optellen en de punten van de tegenstander aftrekken. De koning krijgt van Botvinnik 200 minus het aantal zetten tot de koning wordt geslagen, zodat mat in 1 beter is dan mat in 2, en zo voort.
Als je deze variantenboom goed bekijkt zie je bijvoorbeeld 1.g4+ Kh4 2.Lh6 Dh6: 3.Dh2+ Kg5 4.Dd2+ Sf4 en na 5.Df4:+ ef4: de uitkomst -9 oftewel wit heeft een dame verloren. Beter is natuurlijk 5.Dd8+ en daarna zie je 4 varianten met illegale zetten en de uitkomsten 196, 197, 197 en 197 oftewel zwart staat mat. Blijkbaar kon deze evaluatiefunctie het mat niet op een andere manier constateren dan door het slaan van de koning!

Het plaatje van de variantenboom illustreert ook de werking van de groeifunctie. Bij de open rondjes vertakken zich witte zetten en bij de zwarte rondjes zwarte zetten. Bij de stellingen met blokjes is de groeifunctie niet toegepast, want daar staan geen zetten. De evaluatiefunctie is wel toegepast, want er staan uitkomsten.

De minimax-functie verwerkt vervolgens alle varianten vanaf de uitkomsten van de evaluatiefunctie terug naar de voet van de variantenboom. Maximaliseren in stellingen waar wit aan zet is en minimaliseren als zwart aan zet is. Zo kiezen schaakprogramma’s uiteindelijk een zet.

Op dit plaatje is dat misschien niet zo duidelijk, want Botvinnik laat alleen 1.g4+ zien en alle andere zetten niet. Maar in de variant na 1.g4+ Kh4 2.Lh6 Dh6: 3.Dh2+ Kg5 moet minimax kiezen uit 3 mogelijkheden: Dh6:+, f4+ en Dd2+. Na 4.Dxh6+ Kxh6 5.g5 Kxg5 6.f4+ Kxf4 is de uitkomst -5, maar volgens mij is het weggeven van nog 2 pionnen overbodig en geeft minimax -3 voor Dh6:+. Na f4+ verliest wit meteen 1 pion en geeft minimax -4 aan f4+. In de varianten na Dd2+ moet zwart kiezen tussen mat of dameverlies en geeft minimax +6 aan Dd2+. De maximale uitkomst op zet 4 is dus +6 en daarom kiest minimax voor Dd2+.

Meer geavanceerde evaluatiefuncties rekenen ook nog wat cijfers achter de komma uit: iets voor een vrijpion dicht bij zijn promotieveld, aftrek voor een paard op een hoekveld, iets voor een toren op de zevende rij, aftrek voor een dubbelpion of achtergebleven pion, iets voor een loper op een diagonaal richting de koning van de tegenstander en meer van die dingen.

Programmeurs van schaakprogramma’s hebben tussen 1957 en 2017 eindeloos geëxperimenteerd om evaluatiefuncties te verfijnen. Een belangrijk criterium voor het programmeren van verfijningen was altijd: hoe snel kunnen we het uitrekenen? Pogingen om schaakkennis van grootmeesters in een expert systeem te coderen waren al eerder gestrand. Uiteindelijk werkte het beter om met weinig schaakkennis in supersnelle evaluatiefuncties meer stellingen te beoordelen, zodat slimme algoritmes varianten dieper konden uitrekenen. Deep Blue en Fritz konden zo zelfs wereldkampioenen verslaan!

Uitleg over algoritmes

Een algoritme is een stappenplan voor een berekening. Voor een programmeur is dat een specificatie om een serie instructies voor de computer te schrijven waarmee de computer die berekening kan doen.

Hiernaast staat een illustratie van een algoritme om priemgetallen uit te rekenen. Begin met een lijst van getallen in grijs. Maak de veelvouden van 2 rood, de veelvouden van 3 groen, de veelvouden 5 blauw en zo voort.

Twee eeuwen voor Christus beschreef Eratosthenes reeds dit algoritme als een zeef voor priemgetallen!

In Schaken met computers 3 beschreef ik een iets ingewikkelder algoritme om het schaakspel in theorie op te lossen: retrograde analyse vanuit stellingen die mat of pat zijn. Dit algoritme werkt goed voor eindspelen met heel weinig stukken, maar kan in de praktijk zelfs met de snelste computers en de grootste geheugens het schaakspel niet oplossen.

Het algoritme voor retrograde analyse is heel concreet: het noteert per stelling in hoeveel zetten het mat of pat is en begint met stellingen met mat of pat in 0 zetten. Schaakprogramma’s daarentegen proberen om vanuit een willekeurige gegeven stelling alle zetten zo diep mogelijk uit te rekenen. Ze moeten zich daarbij behelpen met een evaluatiefunctie en het is meestal niet duidelijk wanneer ze precies moeten stoppen met rekenen.

Botvinnik had natuurlijk bovenstaande stelling uit Botvinnik – Kaminer 1925 bewust gekozen, omdat daarin een aantal geforceerde zetten mogelijk zijn: schaak geven, de dame aanvallen. Niet zo moeilijk om helemaal door te rekenen. De variantenboom blijft daarom nog enigszins overzichtelijk. Maar bij verreweg de meeste stellingen is dat niet het geval. Er zijn tientallen zetten mogelijk, maar je tegenstander heeft alles onder controle. Je kunt niets slaan en geen schaak geven. Bovendien heeft de tegenstander tientallen tegenzetten. Als je de varianten een beetje doorrekent, groeit de variantenboom meteen uit tot een enorme wirwar in je geheugen.

Het enige wat enigszins helpt is dat je moet weten naar welke zetten je moet kijken. Grootmeester J.H. Donner heeft dat ooit als volgt uitgelegd: “Je moet op een gegeven moment voelen dat Db6 beter is dan Df6. Slechte spelers proberen dat te berekenen, de varianten uit te tellen, maar dat is nou precies wat je in schaken nooit moet doen.” Toch is dat precies wat schaakprogramma’s juist wel doen!

Schaakprogramma’s analyseren heel systematisch alle zetten door middel van iterative deepening. Eerst alle zetten 1 zet diep en dan de stellingen beoordelen met de evaluatiefunctie. Vervolgens nogmaals alle zetten analyseren en na alle tegenzetten de stellingen beoordelen oftewel de varianten 2 zetten diep analyseren. Daarna alle varianten 3 zetten diep. En zo voort. De eerste iteraties gaan heel snel, maar met elke zet dieper duurt het doorrekenen van de varianten steeds langer. Voor elke nieuwe iteratie berekent het schaakprogramma hoeveel tijd de volgende iteratie ongeveer gaat duren en besluit eventueel om niet dieper te analyseren.

Het systematisch analyseren door een schaakprogramma is vaak gecodeerd als het recursieve negamax-algoritme. Bijzonder is dat negamax zich beperkt tot het analyseren van de zetten van 1 stelling, maar dat negamax ook wordt gebruikt om alle andere stellingen te analyseren! Voor mensen is dit wellicht verwarrend, maar computers volgen gewoon het stappenplan.

1. Begin met een gegeven stelling.
2. Maak een lijst van mogelijke zetten.
3. Speel een van die zetten op een schaakbord in het elektronische geheugen.
4. Begin opnieuw bij 1. met deze nieuwe stelling.
5. Neem de zet van 4. terug na de analyse van die nieuwe stelling en ga verder bij 4. met een andere zet.
6. De analyse van de gegeven stelling van 1. is klaar als alle zetten van de lijst van 2. zijn verwerkt.
7. Ga terug naar een vorige stelling bij stap 5.

Tussen stap 3. en 5. verwerkt de computer dus alle zetten van stap 2. In stap 4. begint de computer daadwerkelijk opnieuw met een analyse van een nieuwe stelling een zet dieper en met verwisselde kleuren. Dat is dus het begin van een analyse binnen de analyse.

De 7 stappen van negamax zijn de essentie van allerlei beslissingen die de computer moet nemen om de groei van de variantenboom te controleren en toch stellingen zo diep mogelijk te analyseren. Binnen negamax gebruikt de computer de groeifunctie, de evaluatiefunctie, minimax en alles wat ik hierboven beschreef. Voor iterative deepening bijvoorbeeld moet de computer bij stap 2. beslissen niet dieper te analyseren en dus geen zetten te genereren. Verder zou de computer bij stap 2 de lijst van zetten kunnen beperken tot geforceerde zetten (zoals Botvinnik deed). En zo voort.

Ik besef dat de uitleg over algoritmen inmiddels heel technisch is geworden, maar een modern schaakprogramma zoals Stockfish is nu eenmaal het resultaat van meer dan 70 jaar wetenschappelijk onderzoek en experimenten op het gebied van computerschaak.

Reeds tijdens de eerste AI-conferentie in Dartmouth 1956 bedacht John McCarthy een belangrijke verbetering voor minimax. Zijn Alpha-Beta-algoritme bleek even nauwkeurig te zijn als minimax en was bovendien in staat om de variantenboom drastisch te snoeien. Dat zijn dus allemaal varianten die de computer niet meer hoeft te analyseren!

Sindsdien is Alpha-Beta nog meer geoptimaliseerd in combinatie met andere technieken. De volgorde van zetten analyseren bleek heel belangrijk te zijn. Bijvoorbeeld als een pion een dame kan slaan, is het heel zinvol om die zet eerst te analyseren en daarna eventueel andere zetten helemaal niet. Dankzij iterative deepening ontdekt de computer dat en begint dan een volgende iteratie met die zet. De administratie van Killer Moves heeft een soortgelijke functie.

Frans Morsch is bij programmeurs onder andere bekend geworden door zijn optimalisatie met de Null-move. Morsch had deze techniek weliswaar niet uitgevonden, maar wel geperfectioneerd. Bij een Null-Move maakt de computer niet meteen een lijst van mogelijke zetten (stap 2. van negamax) en speelt ook geen zet, maar gaat eerst de tegenzetten analyseren! De uitkomst van de varianten na de Null-Move gebruikt Alpha-Beta vervolgens om de variantenboom extra te snoeien.

Uitleg over AI voor schaken

In het begin van dit artikel beweer ik heel stellig dat Stockfish en Lc0 nog steeds sterker worden, omdat hun Efficiently Updatable Neural Network (NNUE) voortdurend wordt getraind.

Echter Dimitri Reinderman constateerde in 2023 op schaaksite.nl dat Stockfish 15 een mat in 10 niet kon vinden terwijl Stockfish 14 dat wel deed! In 2026 vindt Stockfish 18 na lange tijd wel een mat in 33, maar toen ik de computer nog langer en nog dieper liet rekenen zag Stockfish helemaal geen mat meer.

Stockfish 8 daarentegen vond het mat in 10 binnen een halve seconde! Stockfish 8 had namelijk nog zo’n supersnelle evaluatiefunctie met weinig schaakkennis waarover ik hierboven schreef. Maar in 2017 werd Stockfish 8 dus verpletterd door AlphaZero. Toen hadden de programmeurs van Stockfish in essentie hun evaluatiefunctie weggegooid en zijn ze opnieuw begonnen met AI.

Vanaf 2020 gebruikt Stockfish 12 een evaluatiefunctie met het NNUE. Daardoor kreeg de evaluatiefunctie meer schaakkennis, maar werd trager met alles uitrekenen. Sindsdien kon de computer onmogelijk alle varianten 10 zetten diep van wit en 10 zetten diep van zwart doorrekenen. Althans, ik denk dat dit de verklaring is waarom Stockfish tegenwoordig niet meer het mat in 10 kan vinden.

Het mat in 10 van Jac. Haring is natuurlijk een bijzondere stelling. Voor gewone stellingen is Stockfish in de loop van de tijd wel veel beter geworden en zal in de toekomst nog beter worden! Allemaal dankzij trainen van het NNUE door AI-specialisten die dit doen op computers met speciale chips voor AI (zoals die van Nvidia). Daarnaast bestaat Fishtest die wordt gebruikt door een groep testers. Pas als de testen zijn geslaagd en Stockfish duidelijk sterker is geworden, verschijnt een nieuwe versie van Stockfish die wij schakers kunnen gebruiken op onze computers of op websites zoals lichess.org en Chess.com.

De algoritmen van Stockfish werken nog steeds zoals ik hierboven heb geprobeerd uit te leggen en zijn door mensen geprogrammeerd. De evaluatiefunctie met het NNUE is echter geprogrammeerd door AI en is in feite een immense hoeveelheid, vreselijke complexe code die totaal onleesbaar is voor menselijke programmeurs. Voor de precieze werking verwijs ik gemakshalve naar de documentatie van NNUE, want eigenlijk begrijp ik er weinig van.

De evaluatiefunctie met het NNUE is een specificatie voor een vreselijk ingewikkelde berekening met allerlei termen voor schaakkennis: waarschijnlijk die van Botvinnik (zie Uitleg over evaluatiefuncties), maar ook allerlei verfijningen voor specifieke stellingen: met een paard op 2 sprongen van de vijandelijke koning, 2 torens op een open lijn op 3 lijnen van de vijandelijke koning, de witte loper die tegen pionnen aankijkt, en zo voort. Misschien herkent het NNUE tegenwoordig de stellingen waarvan J.H. Donner zei: “Je moet op een gegeven moment voelen dat Db6 beter is dan Df6″.

Het doel van trainen van het NNUE is om de evaluatiefunctie stap voor stap te verbeteren. Dat kan betekenen dat AI bijvoorbeeld probeert om de term voor 2 torens op een open lijn minder mee te laten tellen of juist meer.

Het ultieme doel is dat de evaluatiefunctie voor alle stellingen zulke nauwkeurige uitkomsten berekent dat het eigenlijk niet meer nodig is om nog dieper te analyseren. In theorie kan Stockfish dan gewoon de zet kiezen die na 1 zet diep de hoogste waarde heeft. Uiteraard bestaat zo’n evaluatiefunctie niet, want dan was het schaakspel al opgelost.

In de praktijk moet Stockfish dus nog steeds stellingen analyseren. De uitkomsten van de evaluatiefunctie helpen daarbij om de zetten in de juiste volgorde te analyseren, zodat de computer de variantenboom flink kan snoeien en dieper kan analyseren. Tijdens het analyseren vindt de computer uitkomsten door minimax (zie Uitleg over algoritmen) die nauwkeuriger zijn dan de uitkomsten van de evaluatiefunctie.

Voor schaken geldt dat voor de meeste stellingen de variantenbomen weliswaar oneindig groot zijn en dat het onmogelijk is om alle varianten te analyseren, maar uiteindelijk zijn er toch 3 resultaten: wit wint door mat, zwart wint door mat of het is remise door pat.

Tijdens trainen van het NNUE verzamelt de computer voor alle stellingen van een schaakpartij: de uitkomsten van de evaluatiefunctie, de uitkomsten van minimax en tenslotte het resultaat van de partij. Vervolgens vergelijkt de computer alle uitkomsten met elkaar. Komen die een beetje overeen? Of zijn er grote verschillen tussen de uitkomsten van de evaluatiefunctie, minimax en het resultaat?

Indien er verschillen zijn, zal AI de evaluatiefunctie van het NNUE een klein beetje aanpassen, de training herhalen en controleren of de verschillen minder worden. Eventueel nog een paar keer herhalen. En natuurlijk niet voor een enkele schaakpartij, maar voor miljoenen partijen en miljarden stellingen.

Zo gaat dat zo ongeveer. Zal AI op deze manier ooit het schaakspel oplossen? Ik denk het niet.

Serie

De serie Schaken met computers begon in 2021 met deel 1. In 2023 volgde deel 2 en in 2025 deel 3.
In deel 4 noemde ik alleen de Nederlandse schaakprogramma’s van Frans Morsch en van mij. In deel 5 vertel ik meer over andere Nederlandse schaakprogramma’s en de Computer Schaak Vereniging Nederland.