Vraag 4Schaakprogramma’s

Het schaakspel is een eeuwenoud bordspel waarbij twee spelers om en om een schaakstuk mogen verzetten. Hierbij heeft de ene speler witte schaakstukken en de andere zwarte schaakstukken. De speler met de witte stukken begint. De spelregels van het schaakspel zijn relatief eenvoudig. Toch lukt het al eeuwen niet om een winnende strategie te vinden. In deze opgave laten we de spelregels verder buiten beschouwing. De opeenvolging van zetten tijdens een schaakspel noemen we het spelverloop . Een belangrijke oorzaak waardoor een winnende strategie nog niet is gevonden, is het grote aantal verschillende spelverlopen dat voor kan komen. De Amerikaanse wiskundige Claude Shannon beschreef dit in 1950 als eerste in zijn publicatie 'Programming a Computer for Playing Chess' . In zijn publicatie deed Shannon een ruwe schatting van het aantal mogelijke spelverlopen met 10 zetten. Bij deze schatting nam hij aan dat iedere keer dat een speler een schaakstuk verzet er 30 mogelijke spelverlopen ontstaan. De schatting van Shannon bleek veel te hoog. Als bijvoorbeeld wit en zwart beide 5 keer een schaakstuk verzetten, zijn er in werkelijkheid 6,93 × 10 13 verschillende spelverlopen mogelijk met deze 10 zetten.

Al jaren wordt er ook tegen schaakprogramma’s geschaakt. Maar zelfs een schaakprogramma kan niet alle mogelijke spelverlopen tot aan het eind van het spel doorrekenen. Daarom rekenen schaakprogramma’s een aantal zetten vooruit en beslissen op basis daarvan steeds wat de beste zet is. Hoe goed een schaakprogramma is in het berekenen van de beste zetten en hoeveel zetten het vooruit kan rekenen bepaalt de speelsterkte van het schaakprogramma. De speelsterkte wordt uitgedrukt in een geheel getal. In de periode 1985-1995 nam de speelsterkte van het sterkste schaakprogramma lineair toe. Zie figuur 1. figuur 1 Het bedrijf IBM haalde in 1996 het nieuws met het inmiddels legendarische schaakprogramma Deep Blue . Dit schaakprogramma had in dat jaar een speelsterkte van 2853 en had daarmee volgens kenners jaren voorsprong op andere schaakprogramma’s.

Een ander bekend schaakprogramma is Stockfish . Dit had op 1 januari 2009 een speelsterkte van 3097. Door constante verbeteringen aan Stockfish nam de speelsterkte daarna (bij benadering) lineair toe met 39 per jaar. Begin 2010 kwam de Vlaamse programmeur Robert Houdart met het schaakprogramma Houdini . Dit was op dat moment het sterkste schaakprogramma ter wereld. Houdart bleef in de jaren erna verbeteringen aan zijn schaakprogramma aanbrengen, waardoor de speelsterkte in de eerste jaren toenam volgens de formule: R = 92,1 · log( t + 1) + 3190 H Hierin is R de speelsterkte van Houdini en t de tijd in jaren met t = 0 op H 1 januari 2010. De speelsterkte van Houdini nam in de jaren na 2010 langzamer toe dan die van Stockfish. Daardoor was Stockfish na enkele jaren weer het betere schaakprogramma.

Door een slimme nieuwe techniek slaagde Houdart erin de speelsterkte van zijn schaakprogramma enorm te verbeteren. Hierdoor was op 1 januari 2016 de speelsterkte van Houdini 121 punten hoger dan op basis van de formule voor R verwacht mocht worden. Daarna nam de H speelsterkte weer veel langzamer toe tot 3433 op 1 januari 2019. Deze ontwikkeling is schematisch weergegeven in figuur 2. figuur 2 Met behulp van bovenstaande gegevens kan voor het deel van de grafiek vanaf 2016 een formule worden opgesteld van de vorm R = a · log( t + 1) + c met t de tijd in jaren met t = 0 op 1 januari 2016 .

Stel deze formule op. Geef a in één decimaal en c als een geheel getal.