Naar de content

AlphaGo vloert de wereldkampioen: 4-1

Twintig jaar na schaken, is de computer nu ook superieur in Go.

Google

Deskundigen hadden verwacht, dat het nog minstens tien jaar zou duren voordat een computer de menselijke wereldkampioen Go zou verslaan. Een computerprogramma dat neurale netwerken combineert met quasi-toevallig zetten en stellingen uitproberen presteert het nu al. Het is een grote sprong voorwaarts voor de kunstmatige intelligentie.

22 maart 2016

Lee Sedol, de Koreaan die al tien jaar heerst in de Go-wereld, was vooraf nog vol zelfvertrouwen. Zo verklaarde hij in een persbericht : ‘Ik heb gehoord dat AlphaGo verrassend sterk is, en nog steeds sterker wordt, maar ik vertrouw er op dat ik in ieder geval deze keer nog win’. Was dat zelfoverschatting? In oktober 2015 speelde hetzelfde programma een wedstrijd tegen de Europese kampioen Fan Hui, en won met 5-0. Sedol deed het in de match tegen AlphaGo iets beter, hij wist althans nog één partij te winnen.

Het is een doorbraak voor de computerintelligentie die herinneringen oproept aan een andere fameuze match van mens tegen computer. In 1997 speelde wereldkampioen schaken Gary Kasparov tegen IBM’s Deep Blue en verloor met 3 1/2 – 2 1/2 . Het leek voor Kasparov een zware klap, een vernedering zelfs, dat hij van een machine kon verliezen. Tot die tijd was het nog een houdbaar standpunt, dat machines niet echt iets slims konden doen, dat was maar ‘brute kracht’. De superioriteit van de mens in de nobele kunst van het schaken zou daarvan het beste voorbeeld zijn.

Een territoriaal spel

Go is het oudst bekende bordspel. Het bestond al in China rond 500 voor Christus. Nog steeds wordt het vooral in Azië gespeeld, ook professioneel. Een spel Go begint met een leeg, vierkant bord met 19 × 19 lijnen. Om de beurt plaatst elke speler een zwarte, dan wel witte steen op een kruispunt (zwart begint). Eenmaal geplaatste stenen bewegen niet meer. Doel van het spel is, zoveel mogelijk terrein en stenen van de tegenstander te veroveren door ze volledig te omringen met eigen stenen. Als een groep stenen omsingeld is, mag de tegenstander die van het bord halen en die lege plek is dan voor de rest van de partij verboden terrein. Er zijn nog een paar andere spelregels, onder meer om te voorkomen dat het spel in een herhaling van zetten terecht komt. Bijzonder aan Go is, dat een speler zijn beurt voorbij mag laten gaan. Als de strijd nog in volle gang is, zal dit zelden voorkomen, maar tegen het eind van het spel hebben spelers steeds minder mogelijkheden over om nog een gunstige steen te plaatsen. Het spel eindigt als beide spelers passen. Dan wordt van beiden het aantal omsingelde kruispunten en veroverde stenen geteld.

Menselijke speelstijl

Mensen zijn inmiddels wel wijzer; al na de match tegen Fan Hui prezen Go-deskundigen de speelstijl van AlphaGo. “Ik had grote moeite om te onderscheiden wie de mens was, en wie de machine”, zei John Diamond, president van de Britse Go-vereniging . Door de Go-gemeenschap werd met veel interesse uitgekeken naar de confrontatie tussen Sedol en AlphaGo, en het zou ‘ongeacht de uitslag’ winst voor het spel Go zijn. Dat klopt ook wel, want er is wereldwijd nog nooit zo veel belangstelling voor geweest.

Waarom deed de computer er twintig jaar langer over om Go onder de knie te krijgen dan schaken? In wezen is het simpel: Go heeft veel meer mogelijkheden dan schaken. Met schaken zijn, uitgaand van een zekere stand van de stukken op het bord, gemiddeld ongeveer 35 legale zetten mogelijk. Met Go is het aantal mogelijke zetten gemiddeld 250.

Al lijkt het verschil per zet niet heel groot, dit leidt wel tot een dramatisch verschil na meerdere zetten. Na vijftien zetten zijn er al zes duizend miljard maal zoveel zettenseries mogelijk bij Go als bij schaken. Na een stuk of vijftig zetten, als de meeste schaakpartijen afgelopen zijn, gaat de modale partij Go nog een zet of honderd lang door.

Zoekboom

Voor spellen als Go, schaken en dammen kun je in principe een volledige ‘zoekboom’ opstellen, een diagram dat er uit ziet als een omgekeerde boom. Vanuit de beginstand vertakt de stam zich naar alle mogelijke stellingen die na de eerste zet ontstaan. Elk van die takken vertakt zich opnieuw naar alle mogelijke tweede zetten volgend op elke eerste zet, enzovoort. Bij schaken vertakt elke tak van de boom zich gemiddeld 35 keer per zet, bij Go 250 keer.

Als je vanuit de stam een pad volgt helemaal omlaag, tot aan het dunste twijgje, eindig je altijd bij een stelling waarin of wit, of zwart gewonnen heeft (tenzij het remise wordt, bij schaken, Go kent geen gelijkspel). In zo’n zoekboom kun je voor elke stand op het bord bepalen of dit een gewonnen stelling is voor wit of voor zwart, door de hele boomtak daaronder te doorzoeken. Dit geldt zelfs voor de beginstand, dus als een computer de volledige zoekboom voor schaken of Go kon doorzoeken, zou hij of voor de witspeler of voor de zwartspeler een altijd winnende strategie vinden (of misschien concluderen dat schaken bij optimaal spel altijd remise wordt).

Maar dat is theorie; zowel bij schaken als bij Go is de zoekboom veel en veel te groot om helemaal door te lopen. Ook over vijftig jaar zullen computers geen 3550 (ongeveer 1077, een 1 met 77 nullen) schaakstellingen kunnen doorzoeken, laat staan 250150 Go-stellingen (een 1 met 359 nullen). Overigens kan de kwantumcomputer dit misschien wel, maar het is nog onzeker of die echt te realiseren is.

Beperkte intelligentie

Toch was het vooral te danken aan het doorzoeken van een zo groot mogelijk deel van de zoekboom waardoor Deep Blue in 1997 van Kasparov won. Dat komt neer op een zo groot mogelijk aantal stellingen, zo veel mogelijk zetten vooruit op waarde schatten. De ‘intelligentie’ van de computer zat in het op waarde schatten van een stelling, maar die was heel beperkt, en voor de rest was het een kwestie van veel ‘brute kracht’. Deze aanpak is ook bij Go geprobeerd, maar dat heeft slechts programma’s opgeleverd die van beginnelingen kunnen winnen. De zoekboom vertakt zich namelijk zo snel, dat de computer niet voldoende diep kan kijken.

In een artikel in vakblad Nature van 28 januari legt het team computerwetenschappers van Google DeepMind uit, dat AlphaGo fundamenteel anders werkt. AlphaGo combineert twee heel verschillende technieken, Monte Carlo tree search (MCTS) en ‘zelflerende’ neurale netwerken.

Willekeurige twijgjes

Als een zoekboom veel te groot is om helemaal te doorzoeken, kan het verrassend effectief zijn om slechts een willekeurige fractie van alle takken te doorlopen, maar wel helemaal tot onderin de dunste twijgjes, dus tot aan de eindstand waarin wit of zwart gewonnen heeft. Eén zo’n compleet pad door de zoekboom heet een Monte Carlo roll-out (Monte Carlo verwijst naar het beroemde casino).

Als je een miljoen Monte Carlo roll-outs doet, kun je terugkijken welke beginzetten het vaakst winst voor wit (of zwart) opleverden. Vervolgens bekijk je alleen nog het deel van de zoekboom onder die beginzetten, en doet weer een miljoen roll-outs. Dan kun je terugkijken welke zetten daarna het vaakst winst voor wit opleverden, enzovoort.

Dit geeft geen garantie dat je de allerbeste zetten vindt, maar naarmate je meer roll-outs per keer doet en de procedure vaker herhaalt, zal de kwaliteit van de gevonden zetten toenemen. Dit principe werd al door eerdere Go-programma’s gebruikt, maar die speelden niet beter dan sterk amateur-niveau.

Neurale netwerken

Een neuraal netwerk is een netwerk van ‘cellen’, geïnspireerd door hoe zenuwcellen werken. Elke cel zet een of meer inputsignalen, volgens een aanpasbare regel, om in een outputsignaal. De input kan van buiten het netwerk komen of van andere cellen in het netwerk, en ook de output kan naar andere cellen gaan, of naar buiten. De respons van een neuraal netwerk als geheel op een bepaalde input, bijvoorbeeld een digitaal plaatje, kan ‘getraind’ worden op een gewenste uitkomst, bijvoorbeeld de output ‘dit is een gezicht’. Dat gebeurt door een groot aantal plaatjes van gezichten als input te geven, en voor elke cel de regel die het verband tussen input en output bepaalt, te optimaliseren. Het netwerk doet dit optimaliseren grotendeels zelf; de menselijke programmeur levert input en bepaalt de gewenste output, maar hij of zij zit niet zelf aan de regels voor elke cel te sleutelen. Daarom wordt een neuraal netwerk al snel een zwarte doos voor de maker; die weet niet tot in détail hoe het tot zijn beslissingen komt. Overigens wordt een neuraal netwerk meestal softwarematig op een gewone computer gesimuleerd.

Zelf-lerende neurale netwerken

Het team van Google DeepMind heeft MCTS nu naar een heel nieuw niveau gebracht, door de selectie van de zetten veel intelligenter te maken. Ze gebruikten hiervoor meerdere neurale netwerken. Ten eerste werd een neuraal netwerk getraind met een database van dertig miljoen menselijke Go-partijen, waarbij het netwerk leert om de zetten van een expert zo goed mogelijk te voorspellen.

Vervolgens speelde een ander neuraal netwerk, met de output van het eerste netwerk als input, miljoenen keren tegen zichzelf, om te leren meer in het algemeen de beste zet in een bepaalde stelling te selecteren. Tenslotte is er nog een neuraal netwerk dat, met de output van de andere netwerken als input, leert om de waarde van een stelling (gunstig voor wit/zwart) nauwkeurig in te schatten.

Al deze expertise is nu te gebruiken om de Monte Carlo tree search veel effectiever te maken. Je kiest namelijk niet meer een groot aantal blinde roll-outs, maar je kiest telkens met een grotere waarschijnlijkheid de roll-out die tot de gunstigste stellingen leidt. Maar als test liet het DeepMind-team AlphaGo tegen andere Go-programma’s spelen zonder zelfs maar één zet vooruit te kijken, dus louter door een zet te spelen die was gebaseerd op een beoordeling van de stelling door de neurale netwerken. Ook dan won AlphaGo 85 procent van alle partijen.

Slimmer

Voor de wedstrijden tegen Fan Hui en Lee Sedol bracht het team de volledige artillerie in stelling: met de kennis van de neurale netwerken werd na elke zet van de tegenstander een MCTS gedaan om de waarschijnlijk optimale tegenzet te vinden. Daarvoor moest wel een netwerk van honderden computers worden ingezet die gelijktijdig aan de MCTS rekenden.

Het resultaat is nu bekend: Sedol had weinig in te brengen tegen deze computerkracht. Maar brute kracht is het niet; neurale netwerken komen op een quasi-menselijke, ‘intuïtieve’ manier tot hun beslissingen, die ook de programmeurs niet nader kunnen analyseren. Ook bekeek AlphaGo een stuk minder stellingen per zet dan Deep Blue deed, maar het deed dat een stuk slimmer en effectiever.

Tegen een Koreaanse krant zei Sedol vlak na de wedstrijd dat hij nooit meer zo’n match wilde spelen. Maar volgens de Britse krant The Independent is Sedol al weer van gedachten veranderd, en wil hij snel een revanchematch. Hij denkt dat hij het spel van AlphaGo nu beter doorziet, en alsnog van hem kan winnen.

In ieder geval gaat deze keer het door Google beschikbaar gestelde prijzengeld van een miljoen dollar aan Sedol voorbij. Google doneert het aan diverse goede doelen en Go-organisaties.

ReactiesReageer