Tuesday, March 26, 2013

Spelende supercomputers



De computer heeft Vier op ’n rij volledig gekraakt, schaakt beter dan de mens en wordt steeds sterker in go. En sinds kort is hij zelfs een geduchte quizkandidaat. Geen spel is meer veilig voor de brute rekenkracht van de denkende machine.

Dit artikel is gepubliceerd in KIJK 4/2011.

Het is 11 mei 1997 wanneer een totaal gebroken Garry Kasparov de pers in een New Yorkse wolkenkrabber te woord staat. Vol frustratie. Vol ongeloof. ‘Ik ben bedrogen’, denkt hij. Hij wil wegblijven van de persconferentie, maar zijn moeder heeft hem overgehaald toch te komen. Zojuist heeft de beste schaker uit de geschiedenis de kortste nederlaag uit zijn loopbaan geleden. Capitulatie na negentien zetten. En dat nog wel tegen een computer: IBM-supercomputer Deep Blue. “Ik heb op mijn emoties verloren van een niet-emotionele tegenstander”, zou hij zes jaar later zeggen in de documentaire Game Over.

‘Computers zijn domme apparaten’ had Kasparov altijd verkondigd. ‘Ze begrijpen het schaakspel niet zoals de mens het begrijpt’. Op de poster die de intellectuele tweestrijd tussen mens en machine aankondigde, keek Kasparov diep nadenkend de wereld in. Boven zijn hoofd stond de zelfverzekerde tekst: “How do you make a computer blink?” − “Hoe laat je een computer met zijn ogen knipperen?”

Precies tijdens de schaakheerschappij van Kasparov evolueerde de schaakcomputer van een amateur die verloor van elke grootmeester naar een rekenbeest dat de gemiddelde grootmeester van de tafel veegt. Alleen doet de computer dat heel anders dan de grondleggers van de kunstmatige intelligentie in de jaren vijftig van de vorige eeuw hadden gedroomd. Met brute rekenkracht in plaats van met een diep begrip van het schaakspel. Niet door briljante partijen na te spelen, niet door te vertrouwen op een jarenlang getrainde intuïtie, niet door de schoonheid van het schaakspel te doorgronden.

Checkers opgelost
Als iemand kan vertellen hoe goed computers anno 2011, veertien jaar na de tweestrijd tussen Kasparov en Deep Blue, dammen, schaken of pokeren, dan is het de Canadees Jonathan Schaeffer. Schaeffer is hoogleraar kunstmatige intelligentie aan de Universiteit van Alberta in Canada. Hij haalde de meestertitel in schaken en ontwikkelde het eerste computerprogramma dat een wereldkampioen versloeg in een serieus bordspel. In 1994 won zijn digitale geesteskind Chinook van de wereldkampioen checkers − een variant van dammen op een 8-bij-8-bord in plaats van een 10-bij-10 bord. In 2007 presenteerde Schaeffer zelfs een computerbewijs dat Chinook nooit kon verliezen. Daarmee had hij checkers gekraakt.

“Vier-op-een rij, het Afrikaanse bordspel awari en checkers zijn helemaal opgelost”, zegt Schaeffer. “In dammen en schaken geeft de computer de beste menselijke spelers goed partij. Bij de populairste bordspelen delft de computer alleen bij go nog het onderspit tegen de beste menselijke spelers. Maar in go op een 9-bij-9-bord in plaats van 19-bij-19 is de computer wel al beter dan de mens.”

Van alle bekende bordspelen is go verreweg het lastigste voor de computer. Dat ligt aan de complexiteit van het spel. “Complexiteit van een spel is een moeilijk te vatten begrip”, zegt Schaeffer, “maar de twee belangrijkste maten zijn de zoekcomplexiteit en de beslissingscomplexiteit.”

De zoekcomplexiteit staat voor het aantal verschillende geldige stellingen bij een bordspel. Op het normale 19-bij-19-bord kent go in de ordegrootte van 10^170 geldige stellingen: een 1 gevolgd door 170 nullen. Daarbij verbleekt het aantal atomen in het heelal (geschat op een 1 gevolgd door 80 nullen). De beslissingscomplexiteit geeft aan hoe moeilijk het is om de beste zet te spelen. De moeilijkste spellen hebben zowel een hoge zoekcomplexiteit als een hoge beslissingscomplexiteit. Schaken en go bijvoorbeeld. De tabel hiernaast geeft een overzicht van de complexiteit van enkele populaire spellen en ook hoe goed computers het spel beheersen.

In 2008 versloeg computerprogramma MoGo, deels in Nederland ontwikkeld en bovendien draaiend op de Nederlandse nationale IBM-supercomputer Huygens, een internationale go-topper. De topspeler begon wel met een handicap van negen stenen, een flink nadeel. De Nederlandse informaticahoogleraar en specialist in computerspelen Jaap van den Herik zei na die winst: “Het huidige resultaat voorspelt dat een computer nog voor 2020 de beste menselijke go-speler op een 19-bij-19-bord in een reguliere match zal verslaan.”

Computerpoker
Maar dat het huidige type computer, hoeveel sneller hij de komende decennia ook wordt, spellen als schaken en go helemaal oplost zoals bij checkers, is volgens Schaeffer uitgesloten. Daarvoor is het aantal mogelijke stellingen op het bord simpelweg te groot. “Alleen wanneer er een radicaal nieuw type computer wordt uitgevonden, bijvoorbeeld een kwantumcomputer, dan zijn wellicht ook schaken en go helemaal oplosbaar.”

Schaeffer heeft de bordspelen inmiddels achter zich gelaten en zich gestort op computerpoker. “Het grote verschil met dammen en schaken is dat je bij poker niet weet welke kaarten de tegenstanders hebben”, vertelt de Canadees. “Poker is een spel van onvolledige informatie, zoals dat heet. Bovendien hoort bij poker bij elk moment dat een speler een beslissing moet nemen een waarschijnlijkheid per beslissing. Hij zou bijvoorbeeld in 90% van de gevallen moeten ‘raisen’, in 8% van de gevallen moeten ‘callen’ en in 2% moeten ‘passen’.”

Een probleem voor de computer is echter dat die kansen zelden eenvoudige, gehele getallen zijn maar decimale getallen. De kans kan een getal met vijftig of meer cijfers achter de komma zijn. En je weet niet hoeveel getallen achter de komma de computer moet meenemen om de juiste uitkomst te berekenen. Het kan zijn dat de computer een totaal andere uitkomst berekent wanneer hij 49 in plaats van 50 cijfers achter de komma meerekent. Het is eigenlijk hetzelfde als bij het vlindereffect, waarbij een klapwiekende vlinder in Tokyo een storm in Amsterdam kan veroorzaken. Maar ondanks problemen met waarschijnlijkheidsberekeningen en het typische bluffen in poker, boekt de computer ook bij dit spel flink vooruitgang.

De mens speelt anders
Waarin schuilt de kracht van de computer in spellen die toch door en voor de mens zijn gemaakt? Wat doet de computer anders dan de mens?

Het menselijk brein is een biologische, levende computer bestaande uit zo’n honderd miljard hersencellen. Elk hersencelletje is eigenlijk een computer in het klein. Ons brein is het resultaat van honderden miljoenen jaren van evolutie. Het is goed in het leren van nieuwe kennis en vaardigheden. Het is ijzersterk in het herkennen van patronen: het gezicht van je moeder, het geluid van een fietsbel. Het computerbrein is een niet-levende machine vol siliciumtransistoren. Het rekent extreem snel vergeleken met het menselijk brein; het kan enorme hoeveelheden gegevens in zijn geheugen houden en wordt nooit moe. Maar qua leervermogen en patroonherkenning kan de computer nog lang niet tippen aan de mens. Eigenlijk vullen het menselijk brein en de computer elkaar aan: waarin de een goed is, is de ander slecht en omgekeerd.

Wil de computer een kans hebben tegen de beste menselijke spelers, dan moet hij juist zijn enorme rekenkracht benutten. En wil de mens de beste computer verslaan dan moet hij juist zijn veel betere patroonherkenning benutten. Neem het voorbeeld van de schaaktweekamp tussen Kasparov en Deep Blue. Deep Blue rekende tweehonderd miljoen zetten per seconde door. Toen Kasparov werd gevraagd hoeveel zetten hij per seconde doorrekende, antwoordde hij: ‘Eén, misschien minder.’

Deep Blue berekent voor elke schaakstelling een getal. Dat getal hangt af van de positie van de stukken. Hij vergelijkt de getallen van alle mogelijke stellingen die hij doorrekent. De volgende zet die hij doet moet tot de hoogste waarde voor hemzelf leiden. Kasparov berekent helemaal geen getallen voor een stelling. Hij heeft dankzij patroonherkenning geleerd hoe hij soms in een oogopslag kan zien of een stelling goed of slecht is en welke zetten goed of slecht uitpakken.

Om zijn winstkans zo groot mogelijk te maken, moest Kasparov zodanige stellingen op het bord zien te krijgen, dat hij de mogelijke consequentie van een zet verder vooruit kon doorzien dan Deep Blue kon rekenen. Jonathan Schaeffer weet wel een voorbeeld: “Neem de dubbelpion: twee pionnen net achter elkaar. Kasparov heeft in zijn schaakloopbaan geleerd dat een dubbelpion een groot langetermijnnadeel is, zelfs twintig zetten later nog. Maar Deep Blue kon geen twintig zetten vooruit rekenen, maar veertien. En zelfs als de programmeurs Deep Blue hebben geïnstrueerd dat een stelling met een dubbelpion een lagere waarde heeft, dan nog begrijpt Deep Blue niet wat de gevolgen van een dubbelpion na twintig zetten kunnen zijn. De computer begrijpt geen schaakconcepten als de dubbelpion. Hij waardeert stellingen en rekent ze door precies zoals hij is geprogrammeerd.”

Dezelfde verschillen tussen mens en computer gelden ook voor alle andere spellen die de computer tegen de mens speelt.

Ook een topper in kennisquiz
In 2007 stelde IBM zich een nieuw doel in de intellectuele strijd tussen mens en machine. Een doel dat vele malen moeilijker is, maar ook vele malen meer praktische toepassingen belooft dan de schaakmatch tegen Garry Kasparov. IBM’s supercomputer Watson neemt het van 14 tot en met 16 februari op tegen de twee beste menselijke spelers in Amerika’s populairste tv-quiz Jeopardy!

Jeopardy! is een quiz waarbij mensen zo snel mogelijk kennisvragen moeten beantwoorden. Vragen van het type: “Nadat Duitsland Nederland binnenviel, vluchtte deze koningin, haar familie en haar regering naar Londen” (Goede antwoord: Wilhelmina.) De vragen zijn vaak cryptisch geformuleerd. Er kan humor in zitten of een raadsel. De computer moet niet alleen de juiste kennis paraat hebben, hij moet vooral ook de vraag zien te begrijpen. En dat is voor een computer een groot probleem omdat taal vol met vaagheden zit.

Tot kort geleden leek het voor een computer onmogelijk om die vragen juist te interpreteren en dan ook nog binnen enkele seconden het juiste antwoord te vinden. Maar in zo’n vijftig testwedstrijden eind 2010 presteerde supercomputer Watson net zo goed als enkele van de beste spelers en kwalificeerde hij zich officieel voor de quiz. Watson is niet verbonden met het internet. Alle kennis zit in zijn geheugen. Dat zijn inmiddels tientallen miljoenen documenten: encyclopedieën, handboeken, technische rapporten, websites, woordenboeken, thesauri, taxonomieën, romans, toneelstukken. In 2011 versloeg Watson de twee beste menselijke Jeopardy-spelers ruim. Een van de grootste prestaties van de kunstmatige intelligentie.

Antwoordmachine
De schaakmatch tussen Kasparov en Deep Blue leverde IBM weliswaar veel publiciteit op maar nauwelijks commerciële toepassingen. Dat moet anders worden met het Watson-project. Het bedrijf denkt binnen een paar jaar commerciële vraag-antwoordsystemen te ontwikkelen voor overheden, bedrijven, gezondheidsinstellingen en helpdesks. Wetenschappelijk en praktisch gezien is dit project veel interessanter dan het verslaan van de wereldkampioen schaken. Het sluit aan bij wereldwijde pogingen om vraag-antwoordmachines te ontwikkelen. Machines die niet zoals Google alleen maar een lange lijst documenten oplepelen, maar een antwoord kunnen geven op onze feitelijke vragen: ‘Hoe lang bestaat KIJK al?’ of ‘Hoe snel rekent het menselijk brein?’

In de intellectuele tweestrijd met de computer heeft het menselijk brein het nadeel dat het niet (of nauwelijks?) sneller wordt. Die beperking ligt diep in de biologische architectuur. Vergeleken met de evolutie van het menselijk brein gaat de evolutie van het computerbrein veel sneller − zeker die van de hardware; in mindere mate die van de software. Computers worden elk jaar sneller en in tegenstelling tot menselijke breinen kun je computerbreinen makkelijk aan elkaar koppelen om de rekensnelheid nog verder op te voeren.

Het geheel oplossen van schaken, go, poker en bridge mag dan buiten bereik liggen, in het duel met de beste menselijke spelers is geen enkel spel meer veilig voor de computer.


[Kader:]
Computer tegen mens - Enkele historische hoogtepunten

1948 Alan Turing schrijft het eerste computerschaakprogramma.

1952 De EDSAC-computer (een van de eerste elektronische computers) wordt geprogrammeerd om boter-kaas-en-eieren te spelen.

1952 Eerste computerprogramma dat het bordspel checkers (een variant van dammen op een 8-bij-8-bord) speelt.

1959 Voor het eerst wint een checkers-computerprogramma, ontworpen bij IBM, van enkele goede menselijke spelers.

1962 Schaakprogramma van MIT-onderzoekers verslaat sommige amateurs.

1988 HiTech is het eerste schaakprogramma dat op grootmeesterniveau schaakt. Vier-op-een-rij wordt volledig opgelost.

1994 Het computerprogramma Chinook verslaat de wereldkampioen checkers, Marion Tinsley. Daarmee is Chinook het eerste computerprogramma dat wereldkampioen wordt in een door mensen ontworpen spel.

1996 Wereldkampioen schaken Gary Kasparov wint zijn eerste match over zes partijen tegen IBM-schaakcomputer Deep Blue met 4 - 2.

1997 Een verbeterde versie van Deep Blue (tweemaal zo snel en met betere algoritmen) verslaat wereldkampioen schaken Gary Kasparov in een revanchematch met 3½ - 2½. Een mijlpaal in de intellectuele strijd tussen mens en machine. Deep Blue rekent tweehonderd miljoen zetten per seconde door.

2002 John Romein en Henri Bal van de VU Amsterdam hebben het Afrikaanse bordspel Awari opgelost (ongeveer 1012 geldige stellingen).

2007 Checkers wordt volledig opgelost door computerprogramma Chinook. Een computerbewijs laat zien dat Chinook nooit kan verliezen. Checkers heeft ongeveer vijfhonderd miljard miljard (5 ×1020) geldige stellingen. Ter vergelijking: schaken heeft er naar schatting 1047.

2007 Quackle wint als eerste computerprogramma een scrabble-toernooi.

2008 Het computerprogramma MoGo, draaiend op de Nederlandse nationale IBM-supercomputer Huygens, verslaat een internationale topspeler bij het bordspel Go. De topspeler begon wel met een handicap van negen stenen. Go is rekenkundig nog complexer dan schaken. Op een 19-bij-19-bord kent Go ongeveer 2,1 ×10170 geldige stellingen.

2011 IBM’s supercomputer Watson verslaat de twee beste menselijke spelers in Amerika’s populairste kennisquiz Jeopardy!

Internet
http://ilk.uvt.nl/icga/ International Computer Games Association
www.ibmwatson.com Informatie over IBM’s supercomputer Watson en de Jeopardy-quiz
http://webdocs.cs.ualberta.ca/~chinook/ Speel checkers met Chinook
http://topdocumentaryfilms.com/game-over-kasparov-and-the-machine/ Bekijk online de volledige documentaire ‘Game Over − Kasparov and the Machine’ (2003) over de schaakmatch tussen Kasparov en Deep Blue.