Man vs Machine: Hoe AlphaGo de heilige graal van de bordspellen wist te beheersen

Het is mei 1997. In Amerika vindt ultieme clash tussen mens en machine plaats. Nee, het gaat hier niet over The Terminator (die film kwam in 1984 al uit), maar over een potje schaak. De score na vijf rondes: één keer winst voor wereldkampioen Gary Kasparov, één keer winst voor schaakcomputer Deep Blue van IBM en drie keer gelijkspel. De zesde ronde is allesbepalend: een regerend wereldkampioen heeft tijdens een officiële wedstrijd nog nooit verloren van een computer.

De wedstrijd tussen Kasparov en Deep Blue is het iconische voorbeeld geworden van de potentie van computers en kunstmatige intelligentie. Een jaar eerder wist Kasparov een eerdere versie van Deep Blue nog met 4-2 te verslaan, maar in 1997 was de supercomputer van IBM uiteindelijk te sterk voor de wereldkampioen. Niet zo gek ook: Deep Blue kon 200 miljoen opties per seconde overwegen en waar ‘s werelds beste schaakspelers slechts een aantal verschillende stellingen tien beurten vooruit kunnen denken, weet Deep Blue voor álle mogelijke zetten hoe de stukken na tien beurten over het bord verdeeld zouden kunnen zijn.

Klassieke kunstmatige intelligentie

De allerbeste schaakspeler ter wereld bleek niet opgewassen tegen de kracht van Deep Blue: een mijlpaal. De eerste gedachte nadat Kasparov de wedstrijd verloren had, ging uit naar de impact: wat zou dit historische moment betekenen? Als computers zo goed zijn in het doorrekenen van cijfertjes, waar zouden ze ons dan allemaal mee kunnen helpen?

Deep Blue was geprogrammeerd om een simpel ‘probleem’ op te lossen: het winnen van een potje schaak. Het kende de regels van het schaakspel en kreeg een opdracht: zet de koning van de tegenstander schaakmat. Maar Deep Blue is niet slim, alleen heel sterk. De computer analyseert hoe alle stukken op het bord staan, gebruikt zijn grote rekencapaciteit om mogelijke zetten en toekomstige stellingen langs te gaan en bepaalt uiteindelijk welke zet ervoor zorgt dat de kans op winst zo groot mogelijk is.

Daarmee kun je Deep Blue niet plaatsen onder het kopje machine learning. De supercomputer is namelijk niet zelflerend. Deep Blue kreeg namelijk heel veel voorbeelden, bijvoorbeeld door een database van de eerste paar zetten van de beste spelers ter wereld. De computer is echter niet in staat om zelf tot inzichten te komen. Inzicht, strategie en patroonherkenning: wij mensen beschikken wel over dat soort kwaliteiten. 

De logische daaropvolgende vraag is dan of we kracht kunnen combineren met slimheid. Zouden we computers kunnen leren om ook een strategie te kunnen bepalen, patronen te herkennen en hem ‘inzicht’ in het spel te geven?

Let’s Go

Deze vraag vormde het uitgangspunt voor wetenschappers die onderzoek doen naar kunstmatige intelligentie. Zou een computer een mens kunnen verslaan bij een spel waarin deze menselijke vaardigheden zo belangrijk zijn? Een Chinees bordspel werd de afgelopen jaren synoniem voor deze uitdaging. Het doel zou bereikt zijn als een computer de heilige graal van de bordspellen beter wist te beheersen dan de beste mens. De uitdaging? Het Chinese bordspel Go.

Het speelveld van Go bestaat uit een bord met een raster van 19×19 lijntjes. Zwart en wit mogen om en om een steen leggen op de kruisingen van die lijntjes. Het doel van het spel is om punten te verdienen door stenen van de tegenstander te kapen en door eigen gebied af te bakenen. “Het is abstracte vorm van landje veroveren”, zegt Erik van der Werf. Hij is gepromoveerd op de toepassing van kunstmatige intelligentie voor het spel Go en daarnaast ook zelf fanatiek Go-speler. “Er bestaat wel zoiets als een beste zet”, zegt hij. “Maar wat bij Go heel erg belangrijk is, is het herkennen van patronen of vormen. Mensen zijn daar heel erg goed in.”

Want het lijkt een makkelijk te begrijpen en te beheersen spelletje, maar de complexiteit van Go zit ‘m juist in die eenvoud. Hoewel de regels simpel zijn, zijn er enorm veel mogelijke posities. En in tegenstelling tot schaak, waarbij de koning het waardevolste stuk is, is elke steen in Go evenveel punten waard. Daarbij komt kijken dat er enorm, enorm, enorm veel mogelijkheden zijn waarop het bord er gedurende een potje uit kan zien. Daardoor werkt de brute force-methode van Deep Blue, waarbij het alle mogelijke zetten berekent, met de huidige rekenkracht van computers niet. En het is ook niet praktisch om elke stelling (mogelijke positie van alle stenen op een bord na een bepaalde zet) in te programmeren. Zoals gezegd is het aantal stellingen bij Go gigantisch: er zijn meer mogelijkheden van Go-stellingen dan het aantal atomen in het universum.

Erik van der Werf studeerde aan de TU Delft, promoveerde in Maastricht op AI-toepassingen voor Go en schreef zelf enkele computerprogramma’s die Go kunnen spelen.

Machine learning

Daarom moet een andere manier bedacht worden om Go te beheersen. Deze manier ligt in het verlengde van de vragen die gesteld werden nadat Kasparov in 1997 genadeloos werd ingemaakt: kunnen we computers zelf leren Go te spelen? Dat is de gedachte achter machine learning: programmeurs kunnen niet alle mogelijke opties programmeren, dus leren ze de computer om zelf te reageren op een probleem dat ze tegenkomen.
Om problemen op te lossen, krijgt de computer de taak om de output te berekenen op basis van input. Die input heeft de vorm van heel veel verschillende data. Dat kan in allerlei vormen of maten aangeleverd worden: tekst in verschillende talen, afbeeldingen, grafieken, twee- of driedimensionale kaarten, tabellen, tijdlijnen… Door een algoritme te trainen met data, kan het bij de input van nieuwe data zelf een beslissing maken.

Onderzoeker Erik van der Werf haalt een groot, vierkant bord tevoorschijn en legt dat op tafel. De zwarte en witte stenen rammelen vrolijk tegen elkaar als Van der Werf de twee mandjes waar ze in zitten naast het bord plaatst. We gaan een potje Go spelen. Aangezien dit mijn eerste keer is, spelen we op een bord van 9×9 lijntjes en krijgt Van der Werf een handicap: ik mag in het begin al vijf stenen op het bord plaatsen. Dat is wel zo eerlijk.

Problemen oplossen en leermethoden

Grofweg kan er onderscheid worden gemaakt tussen twee manieren als het gaat om de problemen die door middel van machine learning zijn op te lossen: beslisproblemen en waarderingsproblemen.

Van der Werf pakt een zwarte steen uit mijn mandje. “We kunnen een computer bijvoorbeeld leren zelf het onderscheid tussen een witte en zwarte steen te maken”, zegt hij. “Het heeft eigenlijk weinig met het AlphaGo te maken: de input komt bij AlphaGo namelijk niet van een camera” En het zou bovendien zonde van de tijd zijn als AlphaGo tijdens de wedstrijden ook nog de kleuren van stenen zou moeten bepalen, maar een computer objecten leren herkennen is nu wel een mooi een praktisch voorbeeld. “Bepalen of een steen zwart of wit is lijkt een eenvoudige taak, maar voor een computer is dat nog heel wat”, zegt Van der Werf. “Hij moet een steen bijvoorbeeld ook kunnen herkennen als die maar deels zichtbaar is. En wat als er heel veel licht op deze zwarte steen valt? Mensen zouden ‘m zonder problemen toch in de categorie zwart plaatsen. Maar als je puur kijkt naar de pixels van een foto, dan zit daar nog heel veel variatie in.”

Het kiezen of een Go-steen zwart of wit is, is een beslisprobleem. Daarbij verdeelt de computer een gegeven in een bepaalde categorie: A of B, ja of nee, 0 of 1 of in dit geval zwart of wit. Als het om twee klassen gaat, heet dat binaire classificatie.

Zo’n binair beslisprobleem kent echter ook zijn beperkingen. Als ik de computer een schaakstuk voorschotel, kan die daar helemaal niets mee. Als het algoritme op die manier afgesteld is, herkent hij namelijk alleen witte en zwarte Go-stenen. In de praktijk kan dat probleem met binaire beslissingen op verschillende manieren opgelost worden. Een algoritme zou bijvoorbeeld eerst kunnen bepalen of een voorwerp een Go-steen is (de categorieën zijn dan ‘Go steen’ en ‘geen Go-steen’) en vervolgens of die steen wit of zwart is.

Van der Werf en ik hebben ondertussen een kwartier gespeeld. Ik zou willen zeggen dat ik het gevoel had dat die voorsprong van vijf stenen me een gelijke kans tegen de professional hebben gegeven, maar dat blijkt niet het geval. Van der Werf heeft al verschillende stenen van mij gekaapt door ze te omsingelen. En ik ben er nog niet achter of veel stenen naast elkaar op het midden van het bord gelijk staat aan een groot strategisch voordeel.

De tussenstand na een kwartier praten en spelen.

Naast ons op tafel staat een glas water, waar ik zo nu en dan een slok uit neem. “Dat is een mooie manier om een waarderingsprobleem uit te leggen”, zegt Van der Werf. “Bij waarderingsproblemen is de output minder discreet. Je wilt bijvoorbeeld dat een computer zelf kan zien hoeveel ml water er in het glas zit. Het berekent dan een punt op een spectrum. Afhankelijk van wat je wil weten, kan dat bijvoorbeeld ook een weersvoorspelling zijn. Of de snelheid van een auto.”

Of een probleem onder beslissen of waarderen valt, is belangrijk om te bepalen hoe je het probleem gaat aanpakken. “Dit onderscheid is alleen belangrijk voor de output die je genereert”, vertelt Van der Werf. “Alles wat daarvoor gebeurt is gewoon een berekening. Voor de generatie van de output maakt die weg ernaartoe in principe niet uit. Je kan het met elke vorm van wiskunde doen. Ik zou bijvoorbeeld ook een dobbelsteen kunnen opgooien, en aan de hand van het aantal ogen iets in een bepaalde categorie kunnen plaatsen”, lacht hij. “Dat zou dan alleen niet echt een goede manier zijn om dat te doen.”

Eerder hadden ik met Van der Werf al over het trainen van algoritmen. Je zou een algoritme dat Go-stenen als zwart of wit herkent zijn gang kunnen laten gaan, maar het is efficiënter om hem alvast wat voorbeelden te geven. Dat heet supervised learning. “Simpel gezegd houdt dat in dat er een leraar is die goede voorbeelden en slechte voorbeelden geeft”, zegt Van der Werf. Je toont het heel veel afbeeldingen van zwarte stenen en zegt: ‘Dit is een zwarte Go-steen’. Dat helpt, want de computer weet dan dat zelfs een zwarte steen die door de lichtinval bijna wit lijkt, zwart is.

Bij het tegenovergestelde, unsupervised learning, is er geen alwetende toezichthouder de van tevoren antwoorden geeft. Je kunt de computer dan wel heel veel zwarte of witte Go-stenen laten zien, maar de computer moet dan zelfstandig het onderscheid kunnen maken.

Als de computer vervolgens een nieuwe afbeelding van een Go-steen wordt getoond, moet het bepalen of dat een zwarte of witte steen is. Je kan je voorstellen dat zo’n algoritme daar veel beter in is als het van tevoren verteld wordt welke stenen zwart en welke stenen wit zijn.

Artificial neural networks

Een algoritme kan dus nooit beslissingen maken zonder een berekening uit te voeren. De uiteindelijke beslissing is vaak ook een samenhang tussen veel kleinere beslissingen. Deze structuur wordt een artificial neural network genoemd. Verschillende kunstmatige neuronen werken samen om allemaal een deel van het probleem op te lossen, bijvoorbeeld het analyseren van patronen en posities op een Go-bord. Al deze informatie geven ze door via verschillende lagen, waarna de bovenste laag uiteindelijk een concrete output geeft. Als het gaat om de beheersing van Go, zou de output een advies voor een bepaalde zet zijn.

In de onderstaande video wordt vrij eenvoudige taal uitgelegd hoe zo’n neuraal netwerk ongeveer werkt.

AlphaGo: wie niet sterk is, moet slim zijn

Tijdens ons gesprek spelen Van der Werf en ik nu al ongeveer zo’n drie kwartier. Voorlopige conclusie: ik sta hopeloos achter. Een maand eerder vond een andere gigantische clash tussen twee Go-spelers plaats. De deelnemers: de Zuid-Koreaanse topspeler Lee Se-dol en AlphaGo, de software die door DeepMind is ontwikkeld om Go te beheersen. DeepMind werd in 2014 overigens gekocht door Google.

De wedstrijd, die bestond uit vijf potjes, trok de aandacht van Go-spelers en van programmeurs over de hele wereld. Dit was dé clash tussen mens en machine: het laatste bordspel waarin het menselijk brein superieur was aan de kracht van een computer.

Het resultaat? AlphaGo wist Lee Se-dol met 4-1 te verslaan.

Hoe deed het dat? Zoals gezegd is het onmogelijk om elke mogelijke zet langs te gaan en te berekenen wat de beste kans zou zijn om te winnen. Daarom maakte AlphaGo gebruik van twee neurale netwerken die elk hun eigen taak berekenen. Het value network bepaalt de waarde van de positie van de stenen op het bord; het policy network berekent de waarschijnlijkheden van de volgende zetten: hoe hoger, hoe beter.

Dit policy network, dat gebruikt kan worden om de meest optimale zet te berekenen, werd getraind met data van zetten die experts zouden spelen. Deze manier kennen we nu ook als supervised learning. Op die manier wist AlphaGo snel en efficiënt een basis te creëren waarop het kon bouwen.

Een ander policy network werd op een andere manier getraind: door tegen zichzelf te spelen. Deze manier van leren heet reïnforcement learning. Daarbij ontdekt een computer zelf hoe het een taak, bijvoorbeeld het winnen van een potje Go, zo goed mogelijk kan uitvoeren. Een mooi voorbeeld daarvan is DQN, een ander algoritme van DeepMind, dat leerde om retro videospelletjes te spelen. In onderstaande video is te zien hoe DQN erachter komt wat de beste manier is om zijn taak (zoveel mogelijk punten scoren, en het liefst zo snel mogelijk) te voltooien is.

https://www.youtube.com/watch?v=cjpEIotvwFY&feature=youtu.be

Het algoritme leert dus van zijn eigen handelen. Het tweede policy network van AlphaGo werd gebruikt om het eerste te optimaliseren. Het doel van Go is immers niet om zetten te voorspellen, maar om het potje te winnen.

Het value network bepaalt de waarde van stellingen tijdens het spel. Dit netwerk werd weer getraind met de data die voortkwam uit het zelflerende policy network dat tegen zichzelf speelde. Daardoor kon het heel veel bordstellingen tot zich nemen, in context van het spel plaatsen en daar een waarde aan toekennen. 

Van der Werf: “AlphaGo gebruikt die twee neurale netwerken in een Monte Carlo tree-search. Stel je een willekeurige stelling op het bord voor (1). Zoals gezegd zijn er enorm veel mogelijke zetten. Als die allemaal hun eigen tak zouden krijgen, zou de onderstaande boom heel erg breed zijn.”

Wat AlphaGo doet, is het aantal vertakkingen beperken. In plaats van naar alle mogelijke zetten te kijken, beperkt het zijn rekenkracht bijvoorbeeld tot drie zetten waar het potentie in ziet (2, 7 en 8). Het value network berekent kent aan 2, 7 en 8 dan een waarde toe.

Maar dan ben je er nog niet. “Die punten vertakken natuurlijk zelf ook weer naar nieuwe bordposities, die zelf ook weer vertakken enzovoort”, zegt Van der Werf. Dat kan tientallen beurten doorgaan, maar dat kost dan weer heel veel rekenkracht. Daarom wordt het aantal takken beperkt. Vanaf dan vinden geen vertakkingen meer plaats. Het rekent bijvoorbeeld door naar hoe de stenen over twintig zetten over het bord verdeeld zouden kunnen zijn, in plaats van over tweehonderd.

Wat het policy network doet, is de waarde van de verschillende zetten berekenen. Als het value network een waarde toekent aan de bolletjes, kent het policy network een waarde toe aan de lijntjes. Om te bepalen welk van deze vertakkingen het waardevolst is (en dus welke zet het beste is), rekent hij dat helemaal terug naar de oorspronkelijke stelling: de positie van de stenen zoals die nu op het bord staan (1). Daarna kan hij besluiten welke vertakking het meest waardevol is en dus welke zet je het best kunt doen.

We zijn dan weer terug bij het onderscheid tussen waardering en beslissing. Van der Werf legt uit: “In de praktijk is het vaak waarderen tot je beslist. Bij waardering reken je een getalletje uit, je benadert iets. Op het moment dat je die getallen gebruikt om te kijken welke het hoogste is, beslis je weer. In AlphaGo zou je die berekeningen van de lijntjes en de bolletjes kunnen zien als een waarderingsprobleem. Vervolgens kijkt hij uit de selectie van vertakkingen welke uitkomst het meest waardevol is. Dan maakt het dus een beslissing.”

Voordat AlphaGo in maart 2016 Lee Se-dol wist te verslaan, speelde de software in het geheim nog tegen een andere speler: de toenmalige Europese kampioen Fan Hui. Die wedstrijd eindigde in een 5-0 overwinnen voor de computer. Bovenstaande video is door DeepMind gepubliceerd tussen de wedstrijd met Fan Hui en Lee Se-dol.

De vraag is natuurlijk hoe het nu verder moet. Terwijl ik genadeloos ben ingemaakt door Van der Werf, denken de knappe koppen van DeepMind na over hoe deze technieken gebruikt kunnen worden om problemen in de echte wereld op te lossen. Dat kan bijvoorbeeld met een vorm van semi-supervised learning, waarbij een deel van de data gelabeld is. Zo’n algoritme kan bijvoorbeeld met de medische gegevens van heel veel verschillende mensen aan de slag om verbanden te ontdekken. Deze data kan bijvoorbeeld gebruikt worden om met een wiskundig model te achterhalen wat een bepaalde ziekte zou kunnen veroorzaken, of om al in een heel vroeg stadium vast te stellen of iemand een bepaalde ziekte heeft. Kunstmatige intelligentie staat op dit moment nog in de kinderschoenen, maar als machine learning ons kan helpen op langer en gezonder te leven, kan ik daar maar een ding op zeggen: let’s go.