AlphaGo, The Movie - Waarom ik ga kijken.

Op 23 april 2018 wordt in Cinéma Sphinx in Gent, als afsluiter van een reeks robot-films,  de documentaire "alphago" getoond. Alles in een bijzonder fijne samenwerking met IDLab van Ugent, GentM en het Gentse Go Genootschap. Om jullie over de streep te trekken om af te komen beloof ik bij deze plechtig om nooit meer - ook de avond zelf niet (dat wordt tong afbijten) - onderstaande riedel af te steken. De hoe en waarom van mijn passie in het samenvallende brandpunt van hobby (GO) en interesse (AI).

Lees het misschien toch eens. Maar vooral: keihard gaan kijken!

Dit is bijna net helemaal niet de kortst mogelijke versie geworden van mijn gedachten hierover. Wie enkel op zoek is naar voldoende context en goesting voor de film zelf kan beter de teaser opvissen op de pagina voor de aankondiging en tickets. Of scroll door naar de trailer een beetje verderop.
Er zijn trouwens ten overvloede wat nerderige details in dit verhaal. Die zijn natuurlijk onderwerp van uw spontane reflex: zijnde overslaan (de ene) of betweterig verbeteren (de andere). Voor het gemak van beide groepen staan ze achteraan als voetnoten verzameld.

Wat verwacht je van de documentaire.

Veel.  Spanning al zeker. Uiteraard het soort voorspelbare spanning van historische films als ‘Pompeii’ en ‘Dunkirk’: Je hoeft je niet echt af te vragen hoe het afloopt. Toch vermoed ik dat de toevoeging van menselijke emotie, persoonlijke verhaallijnen, tussenliggende overtuigingen, misvattingen, doorbraken, falingen, gemiste deadlines, en een goede klankband ook hier de onwaarschijnlijkheid van het behaalde doel in de verf zetten.

Dus ook te verwachten: dat vleugje ‘the underdog wins’ van de klassieke sportfilm. Afgezet tegen het menselijk drama: Lee Sedol, strijder voor de eer van de mensheid, de gedoodverfde winnaar en zijn gedwongen transitie naar sportieve verliezer. Geserveerd op een bedje van eindeloos respect en etalage van zijn lef, inzet, toptalent en kunnen. In dezelfde sfeer ook rolt de aftiteling straks vast over een opgebouwde piek aan optimisme heen: jubelend om wat we als mensheid kunnen bereiken. Ik weet even niet of ik het wel droog hou.

Voor mij en vele anderen zit er ongetwijfeld ook het plezier van herinnering en herbeleving van vijf keer heel vroeg opstaan in maart 2016 om de spelletjes live te volgen.  De verbazing van toen nu kunnen aanvullen met details uit een blik achter de schermen. Lekker.

Content als een spinnend katje opgerold bij de kachel. Popelend als een jonge merrie, de rug rollend in het lentefrisse gras. [*]

Wat er aan vooraf ging. 

Computerspelletjes (of computer-varianten van echte spelletjes) zijn gedroomde speeltuinen om Kunstmatige Intelligentie (kortweg AI) te kweken en te testen. De redenering vertrekt van intelligentie bekijken als het potentieel om te overleven in een wereld vol ondoorgrondelijke uitdagingen. We vinden onszelf als mens namelijk nogal wat op dat punt: We hebben toch maar mooi onze weg gevonden in een wereld waarvan de regels niet netjes vooraf in de bijsluiter zijn meegeleverd (fundamentele fysica om maar iets te noemen); we hebben als uitbreiding van de ons ingebakken overlevingsstrategie een aanzienlijk corpus aan kennis opgebouwd; we geven dat aan elkaar door terwijl we er blijven aan sleutelen.  In die visie zijn spelletjes vooral kunstmatige (vereenvoudigde) werelden waarvan we de complexiteit kunnen bepalen via de regels die er gelden. De mate van bereikte intelligentie (ie dus potentieel om te overleven) valt er ook gemakkelijk af te lezen aan de behaalde score, winst of verlies.  Voor onderzoekers dus een dubbele bonus: schaalbare complexiteit van simpel naar altijd maar reëler, én een ingebakken score waarmee je succes meet. Het zou best kunnen dat spelletjes daarom ook nuttig en populair zijn in de opvoeding van onze mensenkinderen.

Redelijk snel slaagden automaten erin de eenvoudiger prooien uit de speeldoos (boter-kaas-eieren en dammen) naar hun hand te zetten. Daar lag niemand echt wakker van. Boeiend werd het toen het spelletje in kwestie voor de mens zelf een uitdaging vormt. Toen in 1997 de IBM computer "Deep Blue" in New York (na de in 1996 mislukte eerste poging in Philadelphia) won van de toen heersende kampioen en schaaklegende Kasparov was dat niet minder dan wereldnieuws.

Op die dag was er gelukkig nog “Het Chinese bordspel Go” als geruststellend onbereikbaar eiland: "Dáár zijn de mensen wél nog veel beter in"; voor de onderzoekers werd het meteen de volgende te halen scalp aan de riem.

Vanwaar die magie van Go?

Go is niet alleen duizenden jaren oud, het is in een groot deel van de aziatische wereld ook vandaag ontzettend populair.  Het wordt makkelijk vergeleken met schaken (van bij ons).  Zoals het een goede vergelijking betaamt loopt die op veel punten mank. De culturele impact en positie van het spel is ginderachter vele keren groter dan wat wij, westerlingen, vermoeden op basis van het eigen schouderophalen bij de exotische buur of kennis die zijn kinderen wél naar de schaakclub stuurt.  Die stevige culturele bodem komt trouwens mee aan tafel met een flinke stempel aan etiquette-regels die rond het spel leven.

Alphago Movie Still - courtesy Google DeepMind and Roco Films Educational

Wie zoekt naar kunstmatige strategieën om dit varkentje te wassen ontdekt snel de andere mankementen in de vergelijking.  De complexiteit van Go overstijgt die van schaken met vele grootteordes.  Dat getalsmatig uitdrukken gebeurt vaak via het tellen van het totaal aantal mogelijkheden: Van Go wordt gezegd dat het spel meer mogelijke spelsituaties kent dan er atomen zijn in het universum. [1]
Maar daar begint het probleem pas. Niet alleen zijn er véél spelsituaties te overwegen, de inschatting van elk ervan "Is dit gunstig voor mij of voor de tegenstander?", is steeds onzeker.  Bizar als je het vergelijkt met schaken, want het eindresultaat in Go is absoluut duidelijker: winst of verlies zijn de enige opties; aan pyrrusoverwinningen als remise en pat doen ze niet mee. Maar alle situaties vóór 'the end game' zijn niet in een eenduidige getalwaarde te vatten.  En dat maakt het een onmogelijke zoektocht: Waar is het verborgen pad van zet en tegenzet dat je kan leiden van waar je nu bent, naar de situatie waar je wilt eindigen: winst! [2]

Je voelt zo de paradox: de go spelregels zijn eenvoudig en elegant.  Uitgelegd in de tijd nodig om alleen al de verschillende schaakstukken te herkennen. Precies die bedrieglijke eenvoud schept een virtuele wereld waarin ontzettend veel meer mogelijk is; waar meer afgeleide kennis te ontdekken is; waar de schat aan overgeleverde speel-strategieën onbewezen, dus aanvechtbaar blijven; waar nuance en balans de codewoorden zijn; waar elegantie, eenvoud, en intuïtie regeren; waar besprekingen zijn opgetrokken uit metafoor en poëzie.

Google vs Facebook

De recente geschiedschrijving van ‘de aanvallen op het kraken van Go door automaten” geeft uiteraard de grote IT bedrijven hun rol.  Zo was er begin 2016 de beloftevolle aankondiging van Facebook. Hun inzicht was om de opgedane kennis van gezichtsherkenning in te zetten om de structuren en patronen voor winst en verlies te herkennen.  Niemand wist dat ondertussen een klein bedrijfje uit Londen, slim opgekocht door Google, reeds een veel belangrijker mijlpaal in die wedstrijd had behaald.

DeepMind ging in die periode al over de lippen. Ze toonden behoorlijk indrukwekkende resultaten in een onderzoek naar een AGI.  Die afkorting laat zich lezen als een AI met ambities richting de G van Generiek. Een kunstmatig brein dat inzetbaar is los van het specifieke probleem (de virtuele wereld) waarvoor hij is ontwikkeld. Hun claim to fame: één dergelijk AGI systeem dat, na onbevangen rondlopen in de verschillende werelden van de klassieke Atari games (space invaders, pong, break out, …) zichzelf leert om te overleven in elk ervan, op niet minder dan bovenmenselijk niveau.

Dat ondertussen in november 2015 ook de Europese Go kampioen Fan Hui van een eerste versie van alphago een droge 5-0 aan de broek kreeg gesmeerd bleef onbekend tot hun wetenschappelijke paper erover verscheen begin 2016. Complete verrassing. De meest optimistische AI volgers (ik beken schuld) hadden nog net hun verwachtingshorizon bijgesteld van het gangbare ‘over tien misschien’ naar een hoopvolle ‘vijf’ jaar. De deep-mind-paper maakte die inschatting meteen onnodig conservatief.  Plots stond dit doel binnen het tijdsbestek van één of twee jaar op de agenda.

Zo ruim bleef die inschatting wel; ze werd ook niet bijgesteld na de aankondiging van “The DeepMind Challenge Match”. Hun eerste topwedstrijd met de legendarische Lee Sedol had een duidelijk aura van jeugdige overmoed.  Dat zou volgens zowat iedereen het equivalent worden van de schaakles die Deep Blue in Philadelphia ‘96 kreeg geserveerd.  Die geruststellende gedachte werd mee gedragen door het verschil in ranking tussen Lee Sedol (9p) en Fan Hui (2p): op honderd spelletjes tegen elkaar zal de laatste er statistisch maar eentje winnen. Die onbekende alphago had nog niets bewezen.

We're not in Kansas any more.

Het is anders gelopen. In maart 2016 werd aan de Go wereld een nieuwe grootmeester geopenbaard. Strikt gezien "onbezield", maar steeds geduldig en beschikbaar, én met een schat aan nieuwe voorbeelden en achterliggende strategieën die een belangrijke revolutie in het spel beloven.  Aan de AI wereld werd getoond dat er sinds Deep Blue heel wat is veranderd: toen was de evaluatie eenvoudig: "Rekenkracht" maal "Aantal gecodeerde regels". Na een eerste tegenvaller lag winst in het vooruitzicht door beide factoren op te trekken. De complexiteit van de Go uitdaging heeft echter een andere aanpak afgedwongen, en die resulteert in een radicaal loslaten van strikt gecodeerde regels. De zoektocht nu is naar een elegant brein dat zelf ontdekt en zo evolueert naar een intuïtieve efficiëntie die zelfs belooft met immer minder rekenkracht tot de juiste conclusies te komen.  [3]

---

Nerd Alert: Voetnoten lezen op eigen risico.  Inhoudelijke suggesties en correcties welkom.

[1] Het schatten van het aantal mogelijkheden.

Schaak en Go zijn bordspellen met speelstukken, een spontane reflex is gewoon tellen hoeveel mogelijke spelsituaties (ook wel aantal bord-configuraties) er theoretisch mogelijk zijn.

• Schaak wordt op een 8 x 8 bord gespeeld met 2 x 16 stukken.
  De 32 stukken kun je op de 64 velden plaatsen op een eindig aantal mogelijke combinaties. Een bovengrens daarvan laat zich ietwat naïef berekenen als 64! / 32! ≈ 10⁵⁴
• Go wordt gespeeld op een 19 x 19 bord met zoveel stenen als er in de loop van het spel blijken nodig te zijn. (men speelt overigens op de kruisingen, niet op de velden)
  De berekening van het aantal mogelijke configuraties gaat er dan van uit dat elk van de 361 kruispunten in 3 mogelijke toestanden kan staan: wit-zwart-leeg. De schatting voor Go wordt dan 3³⁶¹ ≈ 10¹⁷², het getal dat de onderbouw levert voor de uitspraak “meer dan het aantal atomen in het universum (≈ 10⁸²)”

Bovenstaande berekeningen dienen slechts als bovengrens en eerste raming.  Ze worden meestal snel gecorrigeerd via ontdekte symmetrie en herhaling: als je bv. begrip kleur uitschakelt door zwart of wit te zien als mij vs. opponent kun je dat aantal borden al delen door 2 (wat goed is voor de één is vanzelf slecht voor de ander). Idem met links-rechts, boven-onder. (Die laatste bij schaken niet 100%). Verder zijn er terugkerende stukken: 8 pionnen, 2 paarden, 2 torens, … dat op zich zorgt voor permutaties van identieke bord-configuraties, die kunnen geschrapt worden. Tenslotte zijn er regels of afgeleide inzichten die bepaalde configuraties uitsluiten: in schaak kunnen de pionnen niet op de eigen achterste lijn uitkomen en staan de lopers altijd op een tegengesteld kleur; in Go worden gevangenen van het bord verwijderd, etc. etc.

Daarna wordt, op zoek naar meer optimisme, verder gereduceerd.  Aangezien niet elke bord-configuratie logischerwijs bereikbaar is vanuit de huidige spelsituatie is het niet nodig om in je volgende beslissing ook alle mogelijkheden te overwegen.

• Schaak heeft een hele resem specifieke stukken, met hun eigen gedragsregels en een behoorlijk (in de start zeker) druk bezet bord. Die drukte en regels werken beperkend. Er wordt aangenomen dat er per beurt doorgaans maar een twintigtal geldige zetten te overwegen zijn.
  Bij die overweging dien je natuurlijk vooruit te kijken: er zal een tegenzet komen en verdere reactie op reactie tot het spel eindigt. Alleen bewegen de stukken voortdurend. Dat maakt dat de invloed van de ingenomen positie niet noodzakelijk heel lang blijft duren. Er wordt aangenomen dat het volstaat om 16 zetten vooruit te denken om de impact van je zet te overwegen.
  Dit laat toe te schatten dat je op elk moment eigenlijk vanuit de huidige situatie kunt volstaan met de evaluatie van 20¹⁶ ≈ 10²¹ verschillende situaties.

• Bij Go is bij elke zet elke vrije positie inneembaar; aan het begin bij een leeg bord zijn dat er 361^(*); tegen het eind wordt dat aanzienlijk minder, maar we kunnen aan de slag met een gesteld gemiddelde van 200 mogelijke zetten per beurt.
  ( ^(*)Nee, ik weet het. Ja, dat is totaal onwaar voor de eerste zet, want de eerder genoemde symmetrie ontplooit dan zijn volle kracht en reduceert echte vrijheid tot 55 mogelijke ‘echt verschillende’ zetten, waarvan er in de praktijk maximum 35 echt overwogen worden.)
  
  De stenen bij Go blijven op hun plaats (tenzij ze gevangen genomen worden).  Daardoor, kan het stuk dat in de eerste zet gespeeld wordt zijn effect laten voelen op het einde van het spel.  Als we rekenen dat een spel vlotjes naar de 200 zetten gaat besef je snel dat zo ver vooruitdenken voor niemand haalbaar is.

De analoge berekening toont na deze redenering ook geen reductie: 200²⁰⁰ ≈ 10⁴⁶⁰. Dat zou meer zijn dan het totaal aantal borden. De berekening heeft dus teveel hoeken afgesneden (Naar mijn idee vooral het feit dat er bij elk zet in de regel enkel stenen bij komen en we evolueren naar een steeds voller bord; maar zeker ook het feit dat we de Ko regel nergens in rekening hebben gebracht: tijdens een spelletje Go kan dezelfde spelsituatie zich nl. geen twee keer voordoen).  Maar goed, de conclusie dringt zich op: Hier is geen beginnen aan.

[2] Hoe de waarde (gunstig/ongunstig) van een bord evalueren

Het woord dat in deze context al eens valt is heuristiek: de beschikbare instrumenten, door de mensen ontdekt, om methodisch, meetbaar, voorspelbaar tot het gewenste resultaat te komen.

Die berekenbaarheid, aftelbaarheid of meetbaarheid maakt een ander belangrijk verschil tussen Go en schaak

• In schaak leeft een gangbaar aangenomen waarde-rangschikking van de verschillende stukken. Het rekensommetje Σ (stuk * waarde) is dus snel gemaakt.
  Verder valt door de bewegingsregels van elk van die stukken ook na te tellen hoeveel velden ze controleren, hoeveel bewegingsvrijheid ze zelf nog hebben, … allemaal verschillende aftelbare aspecten die met een slimme gewichtsverdeling tot een zinvolle score per spelsituatie leiden.
• In Go blijven dergelijke redeneringen niet overeind.  Alle stenen zijn identiek en hebben dus een zelfde waarde. Maar gewoon het aantal tellen is jezelf bedriegen: De vorm en positie van de gemaakte omtrekken is belangrijker dan het aantal aanwezige stenen op het bord. Aan die patronen wordt tijdens het spel voortdurend gesleuteld, en de gidsende principes daarbij zijn steevast een afwegen van tegenstrijdige aspecten: speel ik nabij de rand of eerder in het centrum; ga ik de ander knippen of net mezelf verbinden; ga ik voor territorium (zekerheid) of invloed (potentieel); ben ik verspreid overal aanwezig of zoek ik consolidatie, …

Het is lastig om (formeel) uit zoveel nuance een eenduidige getalwaarde te destilleren, het spelverloop zelf (inclusief de keuzes van de tegenstander) zal bepalen welke kant van de afwegingen het meest waardevol is. Zoeken naar ‘balans’ wordt zo een basisattitude om hier te overleven. Maar die is moeilijk van eerlijke twijfel of onbeslistheid te onderscheiden. Elke ingenomen stelling kan op de korrel genomen, en ondoordacht extra verdedigen kan de zaak net kwetsbaarder maken. Kenmerkend voor dit fenomeen van onduidbare waarde-inschatting zijn de poëtische metaforen die voor de beschrijvingen van spelletjes gebruikt worden.  De verklaringen van een kenner voor een gemaakte meesterzet wordt heel vaak: “Het voelde goed”. Porbeer dat als programmeur maar eens in code om te zetten.

[2'] Halverwege laat ik hier vallen dat het concept 'pat' (onebsliste schaakwedstrijd) niet bestaat in Go. Daarmee ga ik gemakshalve voorbij aan de mogelijkheid van de zgn. "Seki": uiterst onduidelijke situaties waar beide spelers geen voordeel halen bij een volgende zet. 

[3] Het “verhaal sinds de overwinning in 2016” schetst bijzonder goed wat er ons nog te wachten staat. We zijn tenslotte al 2 jaar verder.

In de originele versie van alphago was er sprake van een samenwerking tussen twee beslissende organen (twee neurale netwerken). Het zogenaamde ‘policy network’ en het ‘value network’.  De eerste maakt een inschatting van wat gangbaar als volgende zet (of tegenzet) te overwegen valt. Als dit optimaal werkt, is het in staat om het aantal te overwegen spelsituaties aanzienlijk te reduceren.  Daarna kwam het value network aan de beurt om een effectieve waardebepaling te doen van de bereikte situaties, en aan de hand daarvan een optimaal pad te zoeken richting winst. 

Zoals aangegeven zijn de menselijke richtlijnen omtrent de waardebepaling in Go ofwel zinloos ofwel niet formeel uitdrukbaar.  Het value-network werd daarom getraind vanuit het grote niets: alphago kreeg een bord, de steentjes en de opdracht: speel wat tegen jezelf en leer daaruit wat werkt en wat niet. Dit echter niet zonder eerst het ‘policy network’ te trainen. Hiervoor werd dit deelsysteem gevoed met een grote set (honderdduizend) historische spelletjes, door mensen ooit gespeeld. Na die training ‘weet’ het systeem dus nog niet wat een goede zet is, maar heeft het voldoende leren afkijken om alvast te weten wat de meest gebruikelijke tegenzetten zijn.  Daarmee wordt de door zichzelf gespeelde leerset voor het value-network (één miljoen spelletjes groot) meteen meer 'zinvol' dan pure random pogingen.

In de zomer van 2017 kwam ‘alphagozero’ op de proppen. In de ‘zero’ variant betekent ‘zonder de suiker’ gewoon dit: we hebben het policy network, en daarmee ook de afhankelijkheid van door mensenhanden verzamelde sets om van te leren uit het systeem verwijderd.  Dit nieuwe beest leert alles zelf, helemaal from ‘first principles’ (de spelregels). Het bouwt zelfstandig een begrip van hoe de wereld van Go werkt en hoe je daarin het beste overleeft.

Twee markante opmerkingen bij de gepubliceerde resultaten zijn alvast deze:

• Men vergelijkt de prestaties van deze nieuwe variant niet langer met de prestaties van menselijke spelers (Waarom zouden we? Wie is nu de norm dacht je?) De grafiek toont enkel na hoeveel dagen training het niveau van de vorige versies werd overschreden.  Menselijke namen verschijnen daarbij als historische voetnoten: "Je weet wel, dat is het niveau van die versie die won van Fan Hui (2015), Lee Sedol(2016), of Ke Jie en 60 go-meesters (2017)".
• De nodige rekenkracht (zowel bij training als bij effectieve uitvoering) is ondertussen teruggebracht tot een fractie van wat nodig was in de eerdere generaties. De meer ontastbare “intuïtie” lijkt het meer en meer te halen van ruwe rekenkracht.

En om de schakers op het einde van dit verhaal helemaal op te beuren. In najaar 2017 was er ook de variant ‘alphazero’.  In deze nieuwe spelling is de ‘GO’ uit de naam geknipt omdat men hier de go-regels eruit en de schaak-regels erin kan pluggen.  Na vier uur trainen in schaak-land werd de maat genomen van StockFish, de heersende norm onder de schaak-computers, een AI klassieke stijl, tjokvol heuristische regels, waardebepalingen, geautomatiseerd oud menselijk inzicht. Sindsdien worden de youtube-schaak-kanalen bevolkt met analyses van de jammerlijk verloren partijen: daar kunnen we namelijk weerom écht iets van leren, want menselijke oude inzichten zijn geen onderdeel van zijn bias.

[*] Laat ons eerlijk zijn: Met +100 nerds samen in een donkere kamer… én een spelletje Go achteraf!