AlphaGo wist ook de derde wedstrijd tegen go-wereldkampioen Lee Sedol te winnen. Dat betekent dat Google DeepMind met zijn kunstmatige-intelligentieprogramma het merendeel van de go-potjes heeft gewonnen en de miljoen dollar aan prijzengeld in de wacht heeft gesleept.
De wedstrijd waarin de Zuid-Koreaanse go-wereldkampioen Lee het voor de derde keer opnam tegen Googles kunstmatige-intelligentieprogramma duurde uiteindelijk meer dan vier uur. "Het spijt me dat ik niet aan mensen hun verwachtingen heb kunnen voldoen," stelt Lee. Hij vindt dat hem de druk in de derde ronde te veel werd. AlphaGo bleef daarentegen goed presteren, ondanks dat zich situaties voordeden die niet eerder te zien waren in ronde 1 en 2. De miljoen dollar aan prijzengeld gaat naar verschillende goede doelen.
Ondanks het feit dat AlphaGo nu het merendeel van de go-rondes heeft gewonnen van de menselijke wereldkampioen, worden de overige twee rondes nog wel gespeeld; er is geen mercy rule. Hoewel Lee verslagen is door het deeplearningsysteem van Google DeepMind, zou de Zuid-Koreaan nog wel kunnen aantonen dat het programma in principe wel te verslaan is door een mens. Op zondag 13 en maandag 14 maart worden de laatste twee rondes gespeeld.
AlphaGo
"Elke dag moet ik mijn verhaal herschrijven, Lee had nooit verwacht dat hij als mens verslagen kon worden", zegt Leo Dorst van de Faculteit der Natuurwetenschappen, Wiskunde en Informatica van de UvA. Dorst zei dit tijdens een bijeenkomst rond de wedstrijd tussen AlphaGo en Lee Sedol, op donderdag 10 maart. Voor de tweede keer verloor Lee die donderdag van Googles deeplearningsysteem.
De wedstrijd tussen mens en machine baart veel opzien bij kenners van het op het eerste gezicht zo simpele spel dat binnen de kunstmatige intelligentie voor lange tijd als bijna niet te winnen te boek stond. "Dat is precies wat go is: simpel maar spannend. Altijd nieuw, simpel en gecompliceerd. Daarom extra leuk voor nerds", zegt Dorst tegen de collegezaal vol met voornamelijk studenten van de bèta-faculteit.
Om aan te geven wat AlphaGo presteert, vertelt Dorst hoe het bij mensen zit. "Een getalenteerd kind kan in zo'n 15 jaar tot 3 dan komen." Dan is een bepaalde rang en geeft aan hoe goed je bent. Professioneel 9 dan is het hoogst haalbare. "Het verschil tussen Fan Hui, die van AlphaGo verloor in oktober, en Lee Sedol is tien jaar lang, acht uur per dag. Lee is 33 jaar en prof sinds zijn twaalfde", zegt Dorst. "Hij is ook nog eens creatief, want hij bedenkt nieuwe openingszetten. Daarom dacht men ook dat AlphaGo er moeite mee zou hebben. Lee Sedol is veel sterker dan Fan Hui. Iedereen dacht dat de makers van AlphaGo hiermee hun eigen succes zouden ondermijnen. Dat is nu in een wat ander perspectief geplaatst."
Toch is de mens op een bepaalde manier ook in het nadeel tijdens de wedstrijd: Lee weet dat er een miljoen dollar op het spel staat en hij weet dat hij tegen een programma speelt. Ook zitten er normaal drie of vier speelvrije dagen tussen de wedstrijden. In dit geval is er slechts één dag rust. Omdat AlphaGo ook nog eens gebruikmaakt van een speelstijl die mensen normaal niet zouden toepassen, kan Lee zich minder goed voorbereiden op de volgende wedstrijd. In het eerste spel speelde Lee een wat onorthodoxe opening. Dit leek hij te doen om AlphaGo te testen. Ook maakte hij gebruik van overplay, iets wat je volgens de kenners zou doen tegen zwakke spelers.
In het tweede spel speelde Lee een zogenaamde waiting game. Als hij dat tegen mensen doet, verliezen die. "Er werd wel voorspeld dat je 10.000 gpu's nodig zou hebben om Lee's level te halen. Iedereen die dacht dat AlphaGo zou winnen werd voor gek verklaard, maar dat liep vooralsnog anders. De go-community was eerst gechoqueerd, maar na de tweede winst van AlphaGo sloeg dat om. Mensen denken nu dat AlphaGo go zal verrijken."
Dorst gaat nog even terug naar de winst van AlphaGo op Fan Hui. Fan is Europa's beste go-speler met 2 dan professioneel. Hij begon met go in 1988. Tijdens het onderzoek dat in januari gepubliceerd werd, verloor AlphaGo twee wedstrijden van Fan en won er acht. Van te voren was afgesproken dat bepaalde spelcondities niet meegeteld zouden worden. Fan deed het beter in de korte oefenpartijen, maar deze telden dus niet mee.
Er is een gerede angst voor online go, namelijk cheaters. Dit is al een groot probleem bij online schaken. Maar dat probleem heeft volgens Dorst niet te maken met het feit dat computers sterker zijn dan mensen, maar met de mens zelf.
De kunstmatige intelligentie
Go is als spel heel ingewikkeld door het enorme aantal mogelijke stellingen. "Er zijn hele studies van het spel en go-wedstrijden uit het verre verleden die nog actief bestudeerd worden", zegt Dorst. "Bij schaken is het duidelijk: je moet de koning pakken. Bij go is dat niet zo duidelijk. Het doel is minder grijpbaar. Zonder begeleiding is go voor beginners dan ook een lastig spel. Zo is overmeesteren van andere stenen niet het hoofddoel, terwijl kinderen vooral denken dat het daar wel om gaat."
"Bij go zijn feitelijk de groepen stenen en de tussenliggende gebieden de 'stukken' in het spel. Een sterke speler weet welke groep sterk of zwak is en wat de eindscore mogelijk zal worden. Bij professionals is het verschil in eindscore over het algemeen klein, iets van twee punten en dat terwijl je zo'n 180 punten per speler kunt binnenhalen op een bord met 19 bij 19 lijnen", zegt Dorst. "Bij professionals duurt een spel vaak iets van 250 zetten. Er is wel eens iemand geweest die heeft berekend dat het maximaal aantal zetten 2x10⁴⁶ kan zijn, maar dat overleeft een mens niet." Een normale wedstrijd tussen profs duurt meestal zo'n vijf uur, al wordt ook wel eens twintig uur geklokt bij een Japanse titelwedstrijd.
Go is hoe dan ook een spel van de grote getallen. Het is daarom praktisch onmogelijk voor een computer om zoals bij schaken alle mogelijke zetten vanuit een bepaalde positie van te voren te berekenen. De AlphaGo-machine maakt gebruik van verschillende machine learning-elementen. Max Welling, hoogleraar machine learning van de UvA, legt in vogelvlucht aan de hand van de in januari uitgekomen paper uit hoe AlphaGo werkt.
"Ondanks dat AlphaGo sinds de vorige keer dat de computer tegen een kampioen speelde, waarschijnlijk significant veranderd is, zal in de basis niet veel gewijzigd zijn", zegt Welling. "Voor go-spelers was het duidelijk: AlphaGo zou niet winnen. Maar de huidige status is anders."
AlphaGo maakt gebruik van vier machine learning-ingrediënten. Supervised deep learning, reinforcement learning en Monte Carlo Tree Search. Ook maakt de machine gebruik van deep convolutional networks voor het scannen van het spelbord en het herkennen van beeld.
Het leren voorspellen van data van eerdere wedstrijden, heet supervised learning. In dat geval is er een bestaande dataset waaruit voorspellingen gemaakt worden. Wordt er een verkeerde voorspelling gemaakt, dan moet het algoritme een klein beetje aangepast worden, tot de uitkomst klopt.
Het tweede proces heet reinforcement learning. Daarbij voert het neurale netwerk zelf een actie uit, zoals het plaatsen van een steen op een specifieke positie op het bord. Dan gaat het uitzoeken of het zou winnen of verliezen met die zet. Wordt er inderdaad gewonnen, dan kan de regel verbeterd worden. "Maar, dat soort acties kunnen nogal noisy zijn", zegt Welling.
Daarnaast analyseert AlphaGo spellen die mensen gedaan hebben. Hoe zou een mens reageren? Waar zou een mens een steen neerzetten? Dan is er nog een netwerk dat zelf nieuwe wedstrijden genereert. Dat zijn miljoenen games. Die dataset laat weer een ander netwerk leren en trainen. Dat laatste netwerk is niet bezig met de waarde van de steen, het kijkt naar de waarde van de positie. Daarmee traint AlphaGo zichzelf uit zowel menselijke als eigen zetten.
"Uiteindelijk komt Monte Carlo Tree Search om de hoek", zegt Welling. "Elke zet heeft een waarde. Bij schaken kun je elke mogelijke zet proberen binnen een bepaalde tijd. Dan wordt de best mogelijke zet gekozen. Bij go zijn er te veel mogelijke zetten."
Toch speelt AlphaGo soms hele spellen uit, zoals al eerder opgemerkt. Dit doet AlphaGo op 'goedkope' wijze. Als AlphaGo wint of verliest, wordt weer teruggezet bij het punt waar het begon en wordt dat steeds herhaald. De informatie die dat oplevert wordt weer teruggevoerd in de Monte Carlo-opdracht.
In vergelijking met de schaakcomputer DeepBlue maakt AlphaGo 1000 keer minder gebruik van bordevaluaties dan DeepBlue. In plaats daarvan maakt het veel meer gebruik van machine learning.
Het volledige college, inclusief slides, is te zien via de UvA-webcolleges.
Wetenschap
