Googles AlphaGo verslaat professionele speler in go-bordspel

Google heeft een computerprogramma ontwikkeld dat in staat is om een professionele speler te verslaan in het bordspel go. Het programma AlphaGo versloeg de Europese kampioen van het spel, Fan Hui, vijf uit vijf keer.

Go wordt gezien als een van de meest uitdagende klassieke spellen voor kunstmatige intelligentie om te leren, vanwege de grote zoekruimte en de moeilijkheid van het bepalen van bordposities en zetten. De software werd ontwikkeld door DeepMind, een bedrijf dat Google in 2014 kocht. Hoe AlphaGo in staat was om te winnen in het complexe spel is uiteengezet in een onderzoek in Nature.

AlphaGo beschikt over twee netwerken, een ervan voorspelt de volgende zet van de tegenstander, terwijl het andere de uitkomst van verschillende zetten op het bord probeert te voorspellen. Deze netwerken worden gecombineerd met een kunstmatige-intelligentie-algoritme om vooruit te kijken in het spel op zoek naar mogelijke zetten.

AlphaGo gebruikt waardenetwerken om de bordposities op te nemen en policy networks om zijn volgende zetten te kiezen. Het programma beschikt over neurale netwerken die zijn getraind door het leren van wedstrijden die gespeeld zijn door experts en het leren van de spellen die het programma zelf speelt. Het policy network suggereert de beste zetten om te maken, terwijl de waardenetwerken de gehaalde posities evalueren. Daarna kiest AlphaGo de zet die het meest succesvol is in zijn simulaties. De zelf gespeelde spellen komen voort uit een zoekalgoritme dat gebruikmaakt van de Monte Carlo-methode, waarmee het programma duizenden spellen simuleert.

Go is een complex spel waarin twee spelers elkaar proberen te omsingelen en territorium proberen te winnen. In het spel heeft een speler op elk moment een keuze uit ongeveer 200 zetten, in vergelijking tot 20 zetten bij schaken. Hierdoor is het volgens Google-onderzoeker David Silver niet mogelijk om met brute kracht alle mogelijkheden te onderzoeken. In plaats daarvan maakt AlphaGo gebruik van een meer menselijke aanpak, waarbij de mogelijkheden worden beperkt. Hierdoor lijken de zetten meer gebaseerd op een systeem vergelijkbaar met de menselijke intuïtie.

De combinatie hiervan zorgde ervoor dat AlphaGo in staat was om de Europese go-kampioen Fan Hui vijf keer op een rij te verslaan. Ook heeft het programma een 99,8 procent succespercentage tegen andere go-programma's. In maart gaat AlphaGo het opnemen tegen een van de wereldkampioenen van Go, Lee Sedol.

Reacties (52)

Heel erg tof dat dit gelukt is. Wel is er gespeeld tegen een Europees kampioen, terwijl Go-spelers in Azie vele malen beter zijn. In maart staat er een match gepland tegen Lee Sedol. Ben benieuwd wat hier uit gaat komen!

"AlphaGo beschikt over twee netwerken, een ervan voorspelt de volgende zet van de tegenstander, terwijl de andere de uitkomst van verschillende zetten op het bord probeert te voorspellen. Deze netwerken worden gecombineerd met een kunstmatige-intelligentie-algoritme om vooruit te kijken in het spel opzoek naar mogelijke zetten."

Wat meer informatie over de netwerken:

Er zijn meerdere stappen gebruikt met convolution nets om tot het uiteindelijke spelersmodel te komen. De eerste stap is het voorspellen van eerstvolgende zetten van Go-spelers, aan de hand van games uit een database. Dit is een supervised learning model en kon aan de hand van deze dataset, goed voorspellen wat een speler zou kunnen doen.

Deze informatie hebben ze gebruikt om hun eigen "speler" te maken. Vervolgens hebben ze met reinforcement learning het model iteratief verbeterd, door partijen te laten spelen tegen vorige versies van het model.

De reinforcement learning stap en het spelen tegen zichzelf, maakte veel uit. Het eerste model (alleen supervised learning) won in 11% van de gevallen van Pochi (een opensource Go computerspeler) en het gecombineerde model (supervised + reinforcement) won 85% van de gevallen van Pochi. Het model maakt gebruik van Monte Carlo Tree Search (MCTS), wat in veel andere kunstmatige spelers ook toegepast wordt.

Leuke feitjes voor de tweakers:

Er zijn twee versies gemaakt: een normale AlphaGo bot en een distributed AlphaGo bot.

Specs voor de normale:
- 40 search threads, 48 CPU's en 8 GPU's

Specs voor de gedistribueerde:
- 40 search threads, 1202 CPU's en 176 GPUs.

[Reactie gewijzigd door Reynouts op 28 januari 2016 12:36]

Dat is toch tamelijk brute force? De menselijke speler 'loopt' op een broodje en een glas melk en de genoemde computers op een halve energie centrale (enigszins gechargeerd). De verhouding rekenkracht/energieverbruik is hier scheef en in het voordeel van een computer.

Ik denk dat een mens veel meer rekenkracht heeft dan de nu gebruikte CPU's en GPU's, met inderdaad in verhouding weinig vermogensbehoefte. Energieverbruik is misschien zelfs ook hoger bij mensen dan bij computers; ik denk alleen dat wij mensen veel efficiënter zijn dan computers (en dus veel meer kunnen halen uit 1 watt/u). Ik heb geen idee of er een rekenmodel bestaat dat ons (hersen)energieverbruik kan uitdrukken in Watts of Newtons b.v.

Een volwassen man wordt 2500kcal voeding geadviseerd. Dit is 10450KJ.

Een uur heeft 3600s, dus een mens gebruikt ongeveer 10450/3600 3KWH per dag.

Oftewel 10450*1000/(3600*24) = 1211 J/s= 1211W. Kan je aardig systeempje voor bouwen.

Klopt natuurlijk niet helemaal, in de benodigde voeding zit met name ook een factor beweging in. Helaas weet ik niet wat die is. Wel weet ik dat hersenen +/- 25% van de ruststofwisseling vreten. (maar ja, bij de PC tel je ook de ventilatie e.d. en niet alleen de CPU, dus je zou de gehele ruststofwisseling moeten tellen)

121Watt

Een radiator heeft een vermogen van enkele kW, als mensen een kW warmte afstralen, is centrale verwarming bijna onzinnig.

Overigens wordt energie ook in ons lichaam vooral naar warmte omgezet (ref warm lichaam/zweet bij lichamelijke inspanning). Voor architectuur hanteert men ook 100W/persoon als ontwerprichtlijn.

[Reactie gewijzigd door the_stickie op 28 januari 2016 13:53]

Oeps rekenfoutje.

Echter, je gaat voorbij aan de centrale premisse. Ik wilde de energie van lichaamsbeweging niet vol meetellen omdat dat niet echt relevant is voor GO spelen.

Het was dus een modulering van hersenen+ruststofwisseling, en een (te snelle) bierviltje berekening om daar snel een uitdrukking voor te vinden.

Ik denk niet dat energie verbruik een belangrijk punt is hier.

Een mens verschilt van een computer in de zin dat een computer niet moe wordt, niet afgeleid wordt door interne processen, een oneindige focus en concentratie heeft als het ware. Een mens kan wel moe worden, concentratie verliezen, afgeleid worden vanuit de omgeving, door eigen gedachten en emoties.

Zelfs als een mens afgeleid wordt en zich herpakt, dan moet hij veel van de zetten en analyses die hij al had uitgedacht opnieuw doen. Zelfs als dat al sneller gaat kost het tijd moeite, aandacht. Een pc kan probleemloos een taak cachen of stil leggen zonder gevaar voor verlies van bewerkingen.

Om die reden heeft AlphaGo niet gewonnen maar verloren. Want ik ga uit van de mens, met al haar menselijkheid, dus de emoties, gevoelens, beperkingen en voordelen.

Er is geen schaamte in het winnen van AlphaGo door de menselijke speler, want ik vind het getuigen van obscene krankzinnigheid om een programma op een computer als waardevoller te zien dan een mens. Wat hebben ze nu bereikt? Ze hebben bereikt dat we als soort een draai om de oren krijgen van een machine met software. Hoe maakt dat dat iemand zich beter voelt? Ik voel me er niet beter door.

Ik kan niet eens stellen dat ik blij ben, of zou moeten zijn, of trots, want ik heb die pc niet gebouwd, de hardware er in niet ontworpen en de software niet ontwikkelt!
Je kunt misschien zeggen dat je tot hetzelfde ras behoort als degenen die deze zaken hebben gemaakt. Maar als je je trots van zo ver weg moet halen...

AlphaGo heeft verloren van de mens, want de mens moet het uitgangspunt blijven en het bouwen van dingen die aantonen dat ons lichaam en geest beperkingen hebben is volstrekt nutteloos. Het zal in de toekomst misschien mogelijk worden dat computers, software en machines in allerlei combinaties ons op alle vlakken kunnen overtreffen, maar nog blijft de mens dan superieur.

En niet alleen omdat wij in staat zijn die dingen te bouwen en op die manier zouden kunnen stellen dat wat je ook bouwt en 'beter' is dan ons, we als bouwers per definitie uitstijgen boven de machines. Maar omdat de menselijke ervaring in de wereld van moment tot moment door geen machine ooit nagebootst kan worden.

Want immers, waarom bestaat er zoiets als een 'wedstrijd'? Wat gevoel krijg je bij winst en verlies? AlphaGo zal nooit dergelijke gevoelens kennen; dus winst voor de software is niet anders dan verlies en dus wordt de winst en het verlies triviaal. Het zullen vooral de bedenkers en uitvoerders van dit project zijn die iets voelen.
Maar als winst en verlies triviaal zijn, en zelfs de bouwers in feite niet eens gewonnen hebben van de menselijke speler, waarom zou je er dan een punt van maken? De winst is betekenisloos want er is geen triomf en zelfs als een mens verliest van een mens, en teleurgesteld is, dan heeft zelfs verlies de waarde van de gevoelde emotie, die ook nuttig is om af en toe te voelen en tot wijsheid kan leiden.

Maar als je uit gaat van zuiver materiële en technische paradigma's dan zal deze overwinning je dag helemaal goed maken.

Gefeliciteerd AlphaGo Team met je verlies, nu je hebt aangetoond dat je ons ras als minderwaardig ziet en nu bewezen meent te hebben dat je via techniek dat hebt aangetoond.

Het is niet zo dat er meer of minder rekenkracht is. Vooral het adaptieve karakter van het brein nekt computers. Grote sommen berekenen is lastig, maar vooral bij situaties inschatten, subjectieve knopen doorhakken en herkenning van patronen (ook in meerdere situaties), loopt het brein over het algemeen nog wat stapjes voor op een computer.

Dat ben ik zeker met je eens. Ik denk echter dat ook wij mensen alles "berekenen". We noemen het gevoel, intuïtie, emotie misschien zelfs; stiekem denk ik dat wij ook gewoon algoritmes hebben die dit uitrekenen. Alleen heel erg snel. Je hebt alleen niet door dat je hersens alles al afgewogen hebben (alle denkbare mogelijke uitkomsten berekend). Misschien onzin maar ik vind het een leuk idee

Het "berekenen" is bij hersenen vooral gebasseerd op subjectieve afwegingen. Compleet anders dan logisch rekenen. Hoewel het overeenkomsten bevat, is het toch echt andere koek. Of het (uiteindelijk) te evenaren, of zelfs te overtreffen is door logisch rekenen, laat ik in het midden.

Nee, zo werken mensen zeer waarschijnlijk niet. We gebruiken neurale netwerken (net zoals AI, dat is afgekeken van hoe hersenen werken). Er zijn naturlijk nog een hele hoop details die we niet weten, maar een "cpu" die alle combinaties uit probeert is er zeer waarschijnlijk niet bij.

De vraag hoeveel 'rekenkracht' een brein heeft is een door sommige cognitie- en neurowetenschappers hevig gedebateerde vraag, met name omdat er een kleine maar significante, en vocale, groep onderzoekers bestaat die beweert dat het brein geen computer is en dus geen rekenkracht heeft. Deze onderzoekers scharen zich onder noemers als 'situated cognition' en 'embodied cognition' en proberen het brein als dynamisch systeem te beschrijven. In hoeverre dat mogelijk is, is nog onbekend, maar door deze aanpak lijkt de metafoor van 'het brein als computer' minder passend dan hij ooit was. In het artikel wordt vermeld dat deze kunstmatige go speler, 'net als een mens', de mogelijkheden voor toekomstige zetten beperkt, waardoor niet alle mogelijkheden brute-force moeten worden uitgerekend. Zonder verder het onderzoek al gelezen te hebben kan ik zeggen dat het brein, zoals de embodied cognitive scientistis dat plachten te beschrijven, ook van nature een veel beperktere ruimte met opties evalueert dan het klassieke computationalisme (waar ze met het brute force probleem zitten)..

Het is maar wat je met Brute Force bedoelt. Een Brute Force algoritme wil zeggen, alle mogelijkheden aflopen en kijken wat van alle mogelijkheden het beste is. Gewoon alles proberen. Dit is voor een spelletje Go "intractable".

Jij hebt het hier over het materiaal dat gebruikt is. Een flinke hoeveelheid aan hardware is inderdaad nodig om tot dit resultaat te komen. Je zou ook 100 man in een zaal kunnen zetten die samen mogen werken om Go te spelen tegen deze computer, dan is het misschien volgens jouw vergelijking wat beter in balans, maar ik denk dat je als groep mensen geen voordeel hebt

Een mens kan je nou eenmaal niet op de zelfde manier op schalen om grotere reken capaciteit te behalen.

Natuurlijk is het een oneerlijke vergelijking, dat is het punt ook niet. Maakt de huidige kampioenen ook echt geen slechtere spelers. Het punt is om een AI te ontwikkelen die dit soort dingen kan, het is niet zomaar een bruteforce door alle mogelijkheden af te gaan en je dus al verloren hebt voordat je begint. Daar is het spelletje Go gewoonweg te complex voor. Een zelflerend systeem die op basis van welgefundeerde 'gokken' weet te winnen, is behoorlijk knap en uiterst leerzaam.

Tsja dan nog mooi om te zien dat een echte speler het nog zo goed doet vs een computer. Zoals in de eerste reactie, straks gaat de computer het pas echt moeilijk krijgen

Ik vind dit dan ook veel toffer om te zien dan die voetbal robots, het lijkt niet eens op voetbal, een kind die kan lopen verslaat al zo'n robot.

Maar dit is echt een serieuze speler ( de robot ) en kan het tegen mensen opnemen, nja ik vind het echt ontiegelijk tof. Ondanks dat een mens niet 1202 cpu's en 176 gpu's in zijn hoofd heeft, hebben sommige wel een oerdegelijke cpu erin zitten haha

Dat is toch tamelijk brute force? De menselijke speler 'loopt' op een broodje en een glas melk en de genoemde computers op een halve energie centrale (enigszins gechargeerd). De verhouding rekenkracht/energieverbruik is hier scheef en in het voordeel van een computer.

Er zit inderdaad een hoop kracht achter, de term "brute force" is vrij relatief. Het gaat er om welk deel van mogelijkheden ook echte verder onderzocht wordt.
De naieve aanpak is om iedere mogelijke zet te proberen, en dan weer iedere mogelijke zet, net zo lang tot iemand wint, dat is echt "brute force", je probeert álle mogelijkheden. Voor Go is dat echter niet te doen, er zijn veel te veel mogelijkheden. De kunst is dus om slim te kiezen welke zetten je bekijkt en welke je overslaat. Hoe meer je kan overslaan hoe efficienter het is.

De echte brute-force aanpak zou miljarden keren meer werk doen. Deze bot is zo goed omdat er maar een heel klein deel van de zetten echt bekeken wordt. Go is echter zo complex dat zelfs een "klein deel" nog steeds om miljarden zetten gaat.

Nee dat is geen bruteforce. In een potje GO zijn er ongeveer 2*10^170 opties. Het aantal atomen in het universum is ongeveer 10^80 atomen in het (bekende) universeum. Dat betekent dat er in GO 2*10^90 keer zoveel mogelijkheden zijn in een potje GO dan het aantal atomen in het volledige bekende universum. Geen enkele computer kan dat nu bereken dmv bruteforce.

Wat ik wilde zeggen is dat de rekensnelheid van de computer wel veel hoger is (en het energieverbruik ook), maar dat je dan nog als computer slechts op 1 gebied concurreert met een mens. Die factor rekensnelheid van de computer is toch zoveel hoger dan wat een mens kan, dat ik het brute force noemde.

Daarnaast doet de mens zoveel meer, en dat nog steeds voor die gemiddeld 2500kCal/iets meer 10kJ per dag = 435J/uur = 0.12J/s = 0.12W. Een beetje PC pakt 100-200W en genoemde systemen een veelvoud daarvan.

Uiteraard is 'brute force' relatief. Je moet wel rekening houden dat de energie die een mens verstookt voor veel meer dan alleen het brein gebruikt wordt. De energievoorziening is daarom bijzonder efficient, en gezien wat een mens nog meer kan, zoals ook al hierboven gezegd. De computer kan misschien op deelgebieden mensen overtroeven, maar voor de rest (voorlopig of nooit) niet.

[Reactie gewijzigd door kdekker op 28 januari 2016 15:36]

In een potje GO zijn er ongeveer 2*10^170 opties

Hoe kom je aan dat getal?

Tja, maar de mens heeft 100,000,000,000 min of meer getrainde neuronen in de hersenpan. Daar moeten flink wat paralelle gigaherzen tegenover staan om een beetje te kunnen concureren...
.
Een mooie prestatie van Google!

Dat is het op dit moment. Het punt van dit soort experimenten is om aan te tonen, wat er in de toekomst mogelijk wordt.

Toen de eerste computer de wereld kampioen schaken versloeg, was die computer ook een monster van een ding dat energie slurpt (IMB big blue uit m'n hoofd?). Nu is het een schijnbaar triviaal probleem waarvan het algoritme waarschijnlijk zelfs op een hedendaagse smartphone draait.

Bij het lezen van dit soort stukken heb ik in mijn achterhoofd: the singularity is near

Op dit moment zijn er voor het gedistribueerde model blijkbaar 1202 CPU's en 176 GPU's nodig. Als je in more's law gelooft, zou dit betekenen dat er over 20 jaar voor dezelfde berekeningen 1 of 2 CPU's nodig zijn met niet eens een halve GPU

Dit is nergens in de buurt van brute force. Ja ze gebruiken best veel hardware, maar een echte brute force aanpak zou (door de enorme search space) aan een supercomputer ter grootte van de aarde zelf nog niet genoeg hebben.

Toch wel knap, ik had eigenlijk verwacht dat deep blue van ibm dit zou doen.

De klassieke Deep Blue machine is gebasseerd op brute force algoritmes. Daarvoor zijn de mogelijkheden van Go veel te groot.

Link naar de paper die in detail de werking van het gebruikte algoritme uitlegt (het artikel zelf linkt naar nature, wat betaling vereist om de paper te lezen) : https://storage.googleapi...deepmind-mastering-go.pdf

[Reactie gewijzigd door kris_112 op 28 januari 2016 12:36]

Volgens een bericht op de Facebook pagina van de US Go Association zal aanstaande zaterdagochtend (in de nacht van vrijdag op zaterdag om 03:00 uur) op het AGA youtube channel een professionele analyse door Myungwan Kim (9p) van de partijen tussen Fan Hui en het Deepmind Go programma worden gestreamd. Tijd en plaats zelf eerst verifieren voordat je op blijft!

Het zou op dit Youtube kanaal moeten zijn.
Ook hier op Twitch komt de stream.

edit: Twitch link toegevoegd

[Reactie gewijzigd door mrtnvnl op 28 januari 2016 17:26]

Wel een erg knapte ontwikkeling, zeker gezien de complexiteit van het spel en ook dat ze niet gewoon bruteforcen.
Waar ik dan benieuwd naar ben is wat er gebeurd als je twee AlphaGo tegen elkaar laat spelen. zou het dan gemiddeld een 50-50 worden?

Neural networks zijn niet gebaseerd op kansvariabelen, dus als dat niet op een andere manier is ingebouwd zal het verloop van het potje deterministisch zijn: elk potje verloopt op exact dezelfde manier dus of wit wint altijd, of zwart wint altijd.
Dat wordt uiteraard anders op het moment dat de computer leert van de achtereenvolgende potjes en steeds zijn strategie aanpast.

Aangezien er altijd 1 AlphaGo speler begint, heeft die het voordeel van het oneven aantal, denk ik, oftwel, 1 zet meer dan de ander en dan lijkt mij gelijk spelen onmogelijk.

[Reactie gewijzigd door SkyStreaker op 28 januari 2016 12:23]

In Theorie heb je gelijk echter berkend de software niet alle mogelijkheden en boost een mens na. Een mens maakt ook fouten en een computer kan ook fouten maken.

Daarnaast is het de vraag hoe veel steppen kan de software vooruit kijken.

Door de software tegen zichzelf te laten spelen kan deze wel leren en zonder bruteforce beter worden.

Het zou idd leuk zijn om te weten wat het resultaat is als de software tegen zichzelf speelt.

Hiervoor is een regel die wit (zwart begint) een aantal punten geeft om te compenseren.

Dit klopt en daarom krijgt de Witte speler in geval van een spel zonder handicap stenen standaard een compensatie van 6.5 of zelfs 7.5 (afhankelijk van waar je speelt).

Dit was toch al in oktober 2015?

Klopt inderdaad, maar het officiele research paper is vandaag geaccepteerd voor Nature. Dus nu worden de resultaten en methoden pas breed gedeeld.

Dit was een 2p speler. In maart staat een match gepland tussen AlphaGo en Lee Sedol. Dat is een 9p-speler, daar zitten echt werelden van verschil tussen, daar word je eng van.

Niet helemaal. Dan ranks (1P t/m 9P) op proffesioneel niveau vergaar je door toernooien e.d. te winnen, je kan wel omhoog maar gaat niet meer omlaag. De Elo ratings zijn dan veel interessanter omdat die beide kanten op gaan (zie http://www.goratings.org/). Wereldwijd is Lee Sedol dan ook de nummer 5 van de sterkste spelers op professioneel niveau.

Een paar weken terug had Lee Sedol nog een toernooi partij tegen Ke Jie (de huidige nr. 1) waarvan hij 3 v/d 5 verloor. Als je die spellen bekijkt zie je werelden van verschil in sterkte met amateur spelers (details van deze toernooi finale: link).

Eindelijk een machine dat Aziaten gaat verslaan

maar is het ook even snel

AlphaGo doet zijn zetten in 5 seconden!

koreans go 300APM

Dat moeten we in maart nog zien. Dit was een Europees kampioen

Edit: maar wel een Aziaat inderdaad.

[Reactie gewijzigd door Reynouts op 28 januari 2016 13:28]

Fan Hui klinkt ook wel als een Aziatische naam toch?

Je hebt gelijk. My bad

Dit zijn mooie technieken, vet dat dit mogelijk is en dat dit nog maar het begin is. Maar aan de andere kant vind ik het toch wel een beetje eng worden.

Menselijke overlevingsdrang uit zich heel anders dan simpele Go-zetten. Althans, als het die kant op is wat jij denkt.

Mooi dat ze dit kunnen, ik ben benieuwd wie er in maart gaat winnen. Blijft Go het laatste bordspel waarin computers de mens nog niet kunnen verslaan?
In ieder geval zal de bekendheid van het spel hiermee groter worden, en hopelijk daarmee de populariteit.

In het spel heeft een speler op elk moment een keuze uit ongeveer 200 zetten, in vergelijking tot 20 zetten bij schaken. Hierdoor is het volgens Google-onderzoeker David Silver niet mogelijk om met brute kracht alle mogelijkheden te onderzoeken.

Tja... Ook bij schaken is 't al niet mogelijk met brute force alle mogelijkheden te onderzoeken. Nogal wiedes dat 't bij een ander spel, waarbij meer posities mogelijk zijn, dan ook niet gaat werken.