Alpha Go

AlphaGo  är ett go -spel utvecklat av Google DeepMind 2015. AlphaGo var det första programmet i världen att vinna en match utan handikapp mot en professionell Go-spelare på en standard 19×19 , och denna seger markerade ett viktigt genombrott inom artificiell intelligens, eftersom de flesta specialister på artificiell intelligens trodde att ett sådant program inte kommer att skapas före 2020-2025 . I mars 2016 vann programmet med 4-1 mot Li Sedol , ett 9:e dan (högst rankade) proffs, under en historisk match som rapporterades mycket i pressen [1] . Efter att ha vunnit matchen tilldelade Korea Paduk Association AlphaGo en " hedersnionde dan " för programmets "uppriktiga ansträngningar" för att bemästra spelet [2] .

AlphaGos seger över Lee Sedol jämförs ofta med schackmatchen 1997 mellan programmet Deep Blue och Garry Kasparov , där IBM- programmets seger över den regerande mästaren blev en symbolisk startpunkt för en ny era där datorer överträffade människor i schack [ 3] . Till skillnad från Deep Blue är AlphaGo ett program som inte är knutet till specifik hårdvara . Dessutom är AlphaGo baserad på de allmänna principerna för maskininlärning och använder praktiskt taget inte (till skillnad från schackprogram) vare sig algoritmer eller utvärderingsfunktioner som är specifika för spelet Go. När författarna utvecklade AlphaGo använde författarna bara den mest elementära teorin om spelet Go, programmet nådde en hög nivå av spel och lärde sig från proffsspel . Således kan dess maskininlärningsmetoder användas inom andra tillämpningsområden för artificiell intelligens. Framför allt planerar utvecklingsteamet att tillämpa erfarenheterna som fick när de skrev AlphaGo för att skapa ett medicinskt diagnostiksystem .

AlphaGo kombinerar tekniken som gav det stora genombrottet i kraften hos Go-program 2007-2012 ( Monte Carlo-metoden för trädsökning ) och de senaste framstegen inom maskininlärning , nämligen djupinlärning med neurala nätverk på flera nivåer .

Historik

Enligt en av författarna till AlphaGo, David Silver , började arbetet med programmet 2014 med en undersökning av hur nya metoder för djupinlärning skulle fungera i Go [4] .

För att mäta styrkan i deras program höll författarna en turnering mellan AlphaGo och den bästa gratis och kommersiella Go-mjukvaran ( Crazy Stone , Zen , Pachi , Fuego ), som använde Monte Carlo-metoden och GNU Go , som var den bästa gratis programvaran före Monte Carlo-metoden. Som ett resultat vann den enda datorversionen av AlphaGo 494 av 495 matcher [5] .

Matcha med Fan Hui

I oktober 2015 besegrade AlphaGo den trefaldiga Europamästaren Fan Hui (andra professionella dan) i en match på fem matcher med poängen 5–0. Det här är första gången i historien som en dator har besegrat ett proffs i ett jämnt spel. Detta tillkännagavs offentligt i januari 2016 efter publiceringen av papper [6] i Nature [7] [8] . För varje spel fick spelarna en timme och 3 byoyomi på 30 sekunder.

Efter sitt nederlag uppgav Fan Hui att tack vare den här matchen började han spela bättre och började se de delar av spelet som han inte hade lagt märke till tidigare; i mars 2016 hade Fan Huis globala ranking stigit med cirka 300 positioner [9] .

Nedan är ett exempel på ett spel där AlphaGo spelade svart. Fan Hui avgick efter 165 drag [5] .

19
arton
17
16
femton
fjorton
13
12
elva
tio
9
åtta
7
6
5
fyra
3
2
ett
De första 99 dragen (96 av 10)
19
arton
17
16
femton
fjorton
13
12
elva
tio
9
åtta
7
6
5
fyra
3
2
ett
Rör sig 100-165.

Efter matchen med Fan Hui började AlphaGo-programmet att spela mycket bättre (dess Elo-betyg , beräknat av spelen i olika versioner av programmet med varandra, ökade med 1500 poäng och översteg 4500). Den nya versionen kunde slå den gamla och ge ett försprång på 3-4 stenar [10] .

AlphaGo mot Lee Sedol match

Från 9 mars till 15 mars 2016 spelades en AlphaGo-match med Lee Sedol (9:e dan) [7] i Seoul, Sydkorea . 5 matcher spelades. För varje spel fick spelarna 2 timmar och 3 byoyomi under en minut. Prisfonden uppgick till 1 miljon dollar. Spelen streamades live på YouTube [11] .

Vid tiden för matchen hade Lee Sedol det näst högsta antalet vunna världsmästerskap [12] . Även om det inte finns någon enskild officiell internationell metod för att rangordna Go-spelare, rankar vissa källor Lee Sedol som den fjärde spelaren i världen vid tiden för en match [13] [14] .

AlphaGo vann matchen med 4-1. Lee Sedol har kapitulerat i fyra av fem matcher. AlphaGo, som spelade svart, förlorade i den fjärde matchen efter 180 drag. Enligt utvecklarna av programmet ger AlphaGo upp när det uppskattar sannolikheten att vinna mindre än 20 % [15] .

Enligt experter var AlphaGo under matchen med Li Sedol betydligt starkare och bjöd på ett svårare spel än under matchen med Fan Hui [16] . Lee Sedol sa under en presskonferens att hans nederlag är "Lee Sedols nederlag" och inte "mänsklighetens nederlag" [17] .

Inofficiella spel i slutet av 2016/början av 2017

Den 29 december 2016, på Tygem go-servern, började det nya kontot " Master " spela spel med go-proffs, den 1 januari 2017 bytte han till FoxGo go-servern. Den 4 januari 2017 bekräftade DeepMind att en uppdaterad version av AlphaGo [18] [19] spelade för Master och ett tidigare Magister-konto . AlphaGo vann alla 60 spelade matcher (30 på varje server) [20] . I slutet av alla spel twittrade DeepMinds medgrundare Demis Hassabis : "Ser fram emot officiella fullständiga Go-matcher senare under 2017, i samarbete med Go-organisationer och experter" [18] [19] .

Master spelade 10 matcher om dagen och fångade snabbt många spelares uppmärksamhet på Tygem-servern med sina exceptionella färdigheter. Många misstänkte snabbt att detta var en AI-spelare, eftersom det antingen inte fanns några pauser mellan spelen eller så varade de väldigt lite. Mästarens motståndare var världsmästare som Ke Jie , Pak Jong-hwan , Yuta Iyama , To Jiaxi , Mi Yuting, Shi Yue, Chen Yaoe , Li Qincheng, Gu Li , Chang Hao , Tang Weixing, Fan Tingyu , Zhou Ruiyang , Jiang Weijie , Zhou Junxun , Kim Jisok , Kang Dong Yoon , Park Yong Hoon , Won Sungjin ; förutom dem, nationella mästare och silvermedaljörer i världsmästerskapen: Lian Xiao, Tan Xiao , Meng Tailing, Dan Yifei, Huang Yunsong, Yang Dingxin , Xing Jinso, Cho Hansyn , An Sunjun. Alla utom en av de 60 matcherna var snabba med tre 20- eller 30-sekunders byoyomi, bara i matchen mot Nie Weiping föreslog mästaren att öka byoyomi till en minut på grund av den senares höga ålder. Efter 59 vinnande spel avslöjade mästaren i en chatt att han drevs av Dr. Aya Huan från DeepMind [21] .

AlphaGo- programmeraren David Silver senare att till skillnad från tidigare versioner av AlphaGo, den version som spelade "Master" förlitade sig mer på att lära sig medan han lekte med sig själv än att lära sig av professionella spelares spel, dessutom använde denna version tio gånger mindre beräkningar och tränade i en vecka istället för månader som versionen som spelade med Lee Sedol [22] .

The Future of Go Summit

Den 23-27 maj 2017, i den kinesiska staden Wuzhen , hölls ett toppmöte om Gos framtid, där bland annat AlphaGo höll flera demonstrationsspel [23] och vann alla:

Pensionering

Efter att toppmötet om Gos framtid avslutades meddelade DeepMind-grundaren Demis Hassabis att AlphaGo lämnar Go, och det kommer inte att bli fler matcher i framtiden. Dessutom har DeepMind inga planer på att släppa en offentlig version av AlphaGo [24] .

AlphaGo Zero

I oktober 2017 tillkännagav DeepMind en ännu starkare version av AlphaGo, AlphaGo Zero. Det nya neurala nätverket tränades för att spela Go från grunden, " tabula rasa ", genom att spela med sig själv (utan att lära sig av spel som spelas av människor, vilket var fallet i tidigare versioner av AlphaGo). På bara 21 dagars självinlärning nådde systemet AlphaGo Master nivå av spelkraft och överträffade den sedan. På den 40:e dagen, efter att ha nått överlägsenheten av mer än 300 poäng av elo .

Jämförelse av AlphaGo-versioner

Versioner Hårdvara [25] Elo betyg 1 Tändstickor
AlphaGo fläkt 176 GPU , [26] distribuerad datoranvändning 3144 [27] 5:0 Match AlphaGo - Fan Hui
Alpha Go Lee 48 TPU , [26] distribuerad beräkning 3739 [27] 4-1 AlphaGo mot Lee Sedol match
AlphaGo Master 4 TPU:er [26] v2, en maskin 4858 [27] 60:0 mot professionella go-spelare;

The Future of Go Summit ;
3:0 Match AlphaGo - Ke Jie

AlphaGo Zero (40 block) 4 TPU:er [26] v2, en maskin 5185 [27] 100:0 mot AlphaGo Lee

89:11 mot AlphaGo Master

AlphaZero (20 block) 4 TPU v2, en maskin 5018 [28] 60:40 mot AlphaGo Zero (20 block) 2
Anmärkningar:

[1] Som jämförelse hade Ke Jies bästa mänskliga go-spelare ett elobetyg på 3670 i oktober 2017 [29] . [2] AlphaZeros betyg (20 block) är lägre än för AlphaGo Zero (40 block), i en testmatch besegrade AlphaZero AlphaGo Zero med en poäng på 60:40 pga. där jämfördes versioner av det neurala nätverket med lika många block.

Betydelse

Innan AlphaGo skapades var Go ett av få traditionella spel som en människa kunde spela bättre än en dator [30] .

Go är mycket svårare än schack på grund av det större antalet möjliga positioner. För det första är det som regel fler lagliga drag på varje position i Go än i schack. För det andra, ett Go-spel varar i genomsnitt fler drag. Dessa två egenskaper gör Go mycket svårt för traditionella AI -metoder som alfa-beta-beskärning [8] [31] .

En annan svårighet med Go jämfört med schack och många andra logiska spel är att skapa en utvärderingsfunktion som jämför en godtycklig position med en viss bedömning: för vilken sida denna position är mer lönsam och hur mycket (eller positionen är lika). AlphaGo använder 2 neurala nätverk, varav ett är specialiserat på positionsuppskattning. Således kan den villkorligt kallas en analog till utvärderingsfunktionen i schack [32] .

Av dessa skäl, till och med nästan tjugo år efter att Deep Blue -datorn först slog världsmästaren Kasparov 1997, har de starkaste Go-programmen bara nått amatören 5 dan och kunde inte slå proffset på helpension [8] [33] [34] . De bästa prestationerna för artificiell intelligens i Go var segrarna för Zen -programmet , som kördes på ett kluster av fyra datorer, mot den 9-dan proffs Masaki Takemiya två gånger med ett handikapp på fem och fyra stenar 2012 [35] , samt segern för Crazy Stone- programmet över Yoshio Ishida (9:e professionella dan) med ett handikapp med fyra stenar 2013 [36] .

Att skapa ett program som spelar Go well har varit en stötesten i utvecklingen av artificiell intelligens [1] . Fram till 2015 trodde de flesta experter på artificiell intelligens att ett program som kan besegra världsmästaren i Go inte skulle skapas under åtminstone de kommande fem åren [37] , och många av dem antog att det skulle ta minst tio år [38] [39] [40] [41] . Även efter AlphaGos seger över Fan Hui förutspådde många experter att AlphaGo skulle förlora mot Li Sedol [42] .

Efter matchen med Lee Sedol tillkännagav den sydkoreanska regeringen en investering på 1 biljon won (863 miljoner USD ) i forskning om artificiell intelligens under de kommande fem åren [43] .

Praktisk tillämpning

Metoderna som utvecklats för att spela AlphaGo kan tillämpas på andra områden av artificiell intelligens, i synnerhet för medicinsk diagnostik [44] . Enligt DeepMind-grundaren Demis Hassabis har DeepMind ingått ett avtal med UK National Health Service för att undersöka möjligheten att använda artificiell intelligens för att analysera medicinska data [45] [46] . För detta grundades divisionen DeepMind Health .

AlphaGo-enhet

Grundläggande principer

En väsentlig egenskap hos AlphaGo är att den använder allmänna algoritmer som är praktiskt taget oberoende av funktionerna i spelet Go [47] . AlphaGo-algoritmen innehåller bara de grundläggande principerna för spelet, med vilka alla nybörjare börjar studera spelet, som att räkna antalet gratispoäng ( dame ) för en grupp av stenar, och analysera möjligheten att fånga stenar med hjälp av "stegen" "( shicho ) teknik. Resten lärde sig AlphaGo av sig själv genom att analysera en databas med 160 000 spel med vanliga metoder som kan användas inom andra områden av artificiell intelligens [48] . I detta skiljer sig AlphaGo från system som Deep Blue , en superdator  i schack [4] . När man skrev algoritmen för Deep Blue användes avancerad schackteori. Så, till exempel, använde Deep Blue 8000 anpassningsbara funktioner för att uppskatta positionen, Deep Blue hade ett enormt bibliotek med öppningar [49] . AlphaGo är ett program som kan köras på vilken hårdvara som helst (även om det använde en processor designad specifikt för maskininlärning ) och vars principer kan användas inom andra områden. Den använder inte öppningsbiblioteket och kommer inte direkt åt någon databas med drag under spelet (men använder bara ett neuralt nätverk som tränats på ett stort antal spel). Utvecklarna av programmet vet inte själva hur AlphaGo utvärderar positionen, dess rörelser är ett uppkomstfenomen [50] . Dessutom designades Deep Blue med ett mål i åtanke: att vinna en schackmatch mot Garry Kasparov [4] [51] . AlphaGo var inte specifikt tränad för att spela mot Lee Sedol [17] [52] , dessutom innehöll inte AlphaGos träningsdatabas Lee Sedols spel [53] , och under matchen ändrades inte AlphaGos program eller anpassade sig till Lee Sedols spelstil [ 54] .

Den främsta innovationen med AlphaGo är användningen av djupinlärning  , en teknik som framgångsrikt har tillämpats för mönsterigenkänning (till exempel för att söka efter bilder i Google Images ) [55] . AlphaGo använder nämligen neurala nätverk som tränats på ett stort antal professionella spel, som kan förutsäga vilket drag en professionell kommer att göra i en viss position. Självspelade spel förbättrade de neurala nätverken ytterligare. Bara detta gjorde det möjligt för AlphaGo att spela på nivån för de bästa datorprogrammen 2015: utan uppräkning av alternativ, genom att bara använda ett neuralt nätverk för att välja ett drag, kunde programmet slå Pachi (ett program som spelade på nivån en amatörsekund dan ) [56] .

Liksom de bästa tidigare Go-programmen använder AlphaGo även Monte Carlo-metoden för trädsökning (MCST) [56] . Kärnan i denna metod (namngiven i analogi med Monte Carlo-metoden i beräkningsmatematik ) är att för att uppskatta positionen spelar programmet slumpmässigt med sig själv många gånger, varje gång för att spelet tar slut. Sedan väljer han draget med det högsta antalet vinster.

Teknik före AlphaGo

Allmänna tillvägagångssätt för spel med perfekt information

Go är ett spel med fullständig information . Teoretiskt, för alla spel med perfekt information, finns det en optimal strategi. För att hitta den optimala strategin måste vi gå igenom hela spelträdet . Till exempel 2007 löste Chinook- programmet fullständigt engelska utkast [57] på detta sätt . Men för de flesta spel är denna metod opraktisk eftersom storleken på trädet kan vara mycket stort. Det kan uppskattas som , där  är graden av förgrening av spelträdet (det vill säga det ungefärliga antalet möjliga drag i varje position), och  är spelträdets djup (det vill säga den ungefärliga längden på spelet) . För Go while för schack Uppräkningen kan förkortas med två tekniker.

För det första kan djupet på sökningen minskas med utvärderingsfunktionen : istället för att betrakta spelet till slutet kan du uppskatta mellanpositionen med hjälp av heuristik . Detta tillvägagångssätt fungerade bra i spel som schack , där en dator kunde spela bättre än en människa. Detta tillvägagångssätt var dock inte tillräckligt för Go på grund av spelets enorma komplexitet.

Ett annat tillvägagångssätt är att minska graden av förgrening av det visade trädet genom att kassera några drag. En sådan metod är Monte Carlo-metoden, som gjorde det möjligt för datorer att spela spel som backgammon bättre än människor .

Monte Carlo-metod för trädsökning

Monte Carlo-metoden för trädsökning i sin enklaste form är följande. Först väljs alla möjliga drag från den aktuella positionen, och sedan spelas ett stort antal slumpmässiga spel för varje drag. En tur poängsätts som förhållandet mellan vinster och förluster för slumpmässiga spel som börjar på den tur. Samtidigt beror sannolikheten för att välja ett eller annat drag också på den aktuella bedömningen av positionen: de positioner där vinsten inträffade oftare väljs med högre sannolikhet. En sådan strategi tenderar asymptotiskt till den optimala. Med detta tillvägagångssätt kunde AlphaGos föregångare nå nivån som en svag amatör.

För att förbättra denna algoritm användes funktioner för att förutsäga det mest sannolika nästa draget. Före AlphaGo användes linjära utvärderingsfunktioner och funktioner härledda från grunda policyer . Detta tillvägagångssätt tillät mig att nå nivån av en stark amatör.

Deep learning

AlphaGo arbetar med neurala nätverk , en teknik som framgångsrikt har använts för mönsterigenkänning . Ett stort genombrott inom detta område kom från användningen av flerlagers konvolutionella neurala nätverk och en speciell teknik för att träna dem - djupinlärning . Konvolutionella neurala nätverk består av flera lager av neuroner. Varje nivå får en matris med siffror som inmatning, kombinerar dem med vissa vikter och, med hjälp av en icke-linjär aktiveringsfunktion , producerar en uppsättning siffror som utdata, som skickas till nästa nivå. Vid mönsterigenkänning matas bilden till den första nivån och den sista nivån ger resultatet. Neurala nätverk tränas på ett stort antal bilder och justerar ständigt vikterna som används för att beräkna resultatet. Som ett resultat kommer det neurala nätverket till en konfiguration som kan känna igen liknande bilder själv. Denna process är omöjlig att förutsäga, så det är svårt att säga hur det neurala nätverket "tänker", men grovt sett motsvarar utsignalerna på mellannivåerna olika möjliga klassificeringar [55] [58] .

Med denna teknik har stora framsteg gjorts inom mönsterigenkänning , särskilt inom ansiktsigenkänning . Det har också använts av DeepMind för att skapa artificiell intelligens som kan lära sig att spela ett videospel på egen hand på en Atari 2600 videospelkonsol , med skärmvideo som indata [59] .

AlphaGo-algoritmen

Positionsrepresentation

AlphaGo använder konvolutionella neurala nätverk för att utvärdera en position eller förutsäga nästa drag. Precis som en bild matas till ett neuralt nätverk under mönsterigenkänning, matar AlphaGo en position till neurala nätverk. Varje position representeras som en skiktad bild , där varje lager representerar beskrivningar av de enkla egenskaperna för varje objekt på tavlan. Följande enkla egenskaper används: färgen på stenen, antalet fria poäng ( dame ) för en given grupp av stenar (om det inte finns fler än 8), ta stenar, möjligheten att gå till denna punkt, om detta sten sattes nyligen. Den enda icke-triviala egenskapen som används är om en given grupp är hotad av att fångas in i en stege ( shicho ). Totalt 48 binära egenskaper används (egenskaper uttryckta som ett heltal representeras med en enhetlig kod ). Således representeras varje position som en tabell med bitar [60] .

Strategiskt nätverk

För att inte ta hänsyn till helt dåliga drag, och därigenom minska graden av förgrening vid sökning, använder AlphaGo strategiska nätverk [61] ( engelska  policy networks ) – neurala nätverk som hjälper till att välja ett bra drag.

Ett av dessa nätverk ( SL-policynätverk ) kan förutsäga det steg som en professionell skulle göra i en given position. Detta är ett 13-nivås neuralt nätverk som erhålls genom övervakad inlärning (SL ) på 30 miljoner positioner tagna från 160 tusen spel som spelas på KGS -servern av spelare från 6 till 9 dan. Utbildning ägde rum under fyra veckor på 50 GPU :er ; stokastisk gradientnedstigning användes som en inlärningsalgoritm för maximal sannolikhetssökning [ 62] . Det resulterande neurala nätverket beräknade en sannolikhetsfördelning bland alla möjliga rörelser i en given position (representerad som beskrivits ovan ). Som ett resultat kunde det neurala nätverket korrekt förutsäga rörelsen som personen valde i 57 % av testsituationerna (används inte i träning). Som jämförelse var det bästa resultatet före AlphaGo 44%. Även en liten ökning av noggrannheten i förutsägelser ökar spelets styrka avsevärt.  

Ett strategiskt nätverk kan spela Go själv, varje gång det väljer ett slumpmässigt drag med en beräknad sannolikhet.

Förbättrat strategiskt nätverk

Det strategiska nätverket förbättrades med förstärkningsinlärning ( RL ) :  Nätverket förbättrades nämligen hela tiden genom att spela med ett av de nätverk som erhölls tidigare. Samtidigt valdes varje gång ett slumpmässigt nätverk bland de som erhållits tidigare för att undvika omträning (situationer då programmet väljer det bästa draget, förutsatt att motståndaren använder samma strategi, men kan spela dåligt mot en annan motståndare). Resultatet blev ett strategiskt nätverk ( RL policy network ) som överträffade det ursprungliga nätverket i 80 % av spelen.

Det visade sig att det resulterande strategiska nätverket, som varken använde utvärderingsfunktionen eller uppräkningen av alternativ, kunde vinna 85 % av spelen mot det starkaste öppna programmet vid den tiden, Pachi . Som jämförelse, innan dess, det bästa programmet som spelade utan att använda en sökning av alternativ, men bara ett konvolutionellt neuralt nätverk, slog Pachi 11% av spelen. Således kunde AlphaGo, utan uppräkning av alternativ, nå ungefär nivån för den tredje amatören, enligt författarna till programmet [63] .

Snabbt strategiskt nätverk

För att simulera spelet som krävs i Monte Carlo-metoden (se nedan ) använder AlphaGo en snabbare men mindre exakt version av det strategiska nätverket ( utrullningspolicy ), som får ett svar på bara 2 µs. Detta snabba nätverk förutsäger en persons rörelse med 30 % sannolikhet [64] , medan det förbättrade strategiska nätverket ger ett svar på samma utrustning på 3 ms med 57 % sannolikhet.

Utvärderingsnätverk

AlphaGo använde ett värdenätverk [ 61] för att minska sökdjupet .  Detta neurala nätverk uppskattar sannolikheten att vinna i en given position. Detta nätverk är resultatet av utbildning på 30 miljoner positioner som erhållits genom att spela det förbättrade strategiska nätverket med sig själv. Samtidigt valdes inte mer än en position från varje spel (för att undvika omskolning på grund av likheten mellan positioner i ett spel). För var och en av dessa positioner uppskattades sannolikheten att vinna med hjälp av Monte Carlo-metoden: en turnering med många spel arrangerades, där det förbättrade strategiska nätverket som byggdes i föregående steg spelade med sig självt, med start från denna position. Därefter tränades poängnätverket på denna data. Utbildningen tog en vecka på 50 GPU:er . Resultatet blev ett nätverk som kunde förutsäga sannolikheten att vinna för varje position, samtidigt som man använde 15 000 gånger mindre beräkning än Monte Carlo-metoden.

Trädsökning

AlphaGo räknar upp alternativen med Monte Carlo-metoden för att söka i trädet enligt följande. AlphaGo bygger ett partiellt spelträd , med start från den aktuella positionen, och gör många simuleringar av spelet. För varje drag registreras en poäng i trädet, som på ett speciellt sätt beror på poängen för draget som erhållits med hjälp av de strategiska och utvärderings nätverken, på resultatet av slumpmässiga spel i tidigare simuleringar, och på antalet tidigare simuleringar som valde detta drag (ju oftare ju tidigare detta drag, desto lägre poäng så att programmet tar hänsyn till fler olika drag).

I början av varje simulering väljer AlphaGo ett drag i det redan byggda trädet, med högst poäng. När simuleringen når en position som inte finns i trädet, läggs den positionen till trädet, tillsammans med alla drag som är tillåtna i den positionen, som utvärderas med hjälp av det strategiska nätet . Vidare, som i Monte Carlo-metoden, simuleras spelet till slutet utan förgrening. I denna simulering väljs varje drag slumpmässigt med en sannolikhet som erhålls med hjälp av ett snabbt strategiskt nätverk .

I slutet av simuleringen, beroende på resultatet, uppdateras flyttuppskattningarna i det konstruerade trädet. Således startar varje simulering från den aktuella spelpositionen, når slutet, och som ett resultat av en simulering avslöjas en position i det aktuella trädet.

Författarna till programmet fann att det i detta skede är mer lönsamt att inte använda det förbättrade strategiska nätverket , utan det ursprungliga ( SL- policynätverket ) . Enligt författarna beror detta på att professionella spelare väljer mer olika rörelser än det förbättrade nätverket, vilket gör att programmet kan överväga fler alternativ. Det förbättrade strategiska nätverket används alltså inte under spelet, men dess användning är avgörande för att bygga utvärderingsnätverket när programmet lär sig genom att leka med sig själv.

Hårdvara

AlphaGo utbildades under flera veckor på 50 grafikprocessorer med hjälp av Google Cloud -plattformen värd i USA [62] [65] .

AlphaGo har testats på datorsystem med varierande antal processorer och grafikprocessorer som körs parallellt eller distribuerade . I varje fall gavs 2 sekunder per drag. Betygen som uppnås samtidigt, beräknade på grundval av resultaten av spel med varandra enligt Elo-systemet , presenteras i tabellen: [66]

Datoranvändning Utförandetrådar
_		 Antal CPU:er Antal GPU:er Elo-betyg
Parallell 40 48 ett 2181
Parallell 40 48 2 2738
Parallell 40 48 fyra 2850
Parallell 40 48 åtta 2890
Distribuerad 12 428 64 2937
Distribuerad 24 764 112 3079
Distribuerad 40 1202 176 3140
Distribuerad 64 1920 280 3168

Den version som slog Fan Hui i oktober 2015 körde på 1202 processorer och 176 GPU:er [67] .

I ett spel med Lee Sedol i mars 2016 använde AlphaGo 1920 processorer och 280 GPU:er som kördes på ett distribuerat nätverk [68] .

I maj 2016 meddelade Google att AlphaGo använde TPU , en processor utvecklad av Google speciellt för maskininlärning [69] [70] .

I matchen mot Ke Jie i maj 2017 använde den nya versionen av AlphaGo endast en dator på Google Cloud med en TPU-processor, det vill säga ungefär 10 gånger mindre datorkraft än vad som användes i matchen med Lee Sedol [71] .

Spelstil

Toby Manning, domaren i AlphaGos match med Fan Hui, beskrev AlphaGos spelstil som konservativ snarare än aggressiv [72] . Enligt DeepMinds vd Demis Hassabis försöker AlphaGo öka sannolikheten att vinna, inte poänggapet [4] .

Professionella spelare noterade att några av AlphaGos drag, som från början verkade vara felaktiga, visade sig vara strategiskt viktiga vid närmare granskning [73] .

Nie Weiping (Pro 9:e Dan, Kina ) föreslog efter det första spelet med Li Sedol att AlphaGo spelade på 6:e eller 7:e dannivån i fuseki och 13-15 dan i chuban [74] .

I den tredje delen fann man att AlphaGo kunde kontrollera situationen under ko-fighting , som tidigare hade ansetts vara en betydande svaghet i de flesta Go-program [75] .

Vissa recensenter har beskrivit AlphaGos buggar som ledde till förlusten i spel 4 som typiska buggar för ett Monte Carlo-program [76] . Demis Hassabis uppgav att dessa misstag kommer att analyseras noggrant, och att AlphaGo uppenbarligen inte känner till några av de klassiska tesuji och gör taktiska misstag [77] . Därefter sa Aya Huan (en av AlphaGo-utvecklarna som satte stenarna bakom AlphaGo) att skribentteamet hade två antaganden om orsakerna till dessa fel: antingen hade AlphaGo helt enkelt inte tillräckligt med visningsdjup för att analysera situationen; eller Lee Sedols 78:e drag var så ovanligt (kommentatorerna kallade det "gudomligt" [76] ) att programmet inte stötte på sådana situationer under självinlärning, som ett resultat av det visade sig dess utvärderande funktion (se ovan ) i denna situation vara svag. I vilket fall som helst, enligt Aya Huang, spelar den nya versionen av AlphaGo redan i det här läget korrekt. Samtidigt gjorde laget inget speciellt, AlphaGo själv, som ett resultat av träning, slutade göra sådana misstag [78] .

Efter matchen uppgav Lee Sedol att han blev slagen psykiskt, men inte alls tekniskt [79] . Programmet visade en förmåga till kreativa lösningar, vilket överraskade många spelare (till exempel drag nummer 37 i det andra spelet ); vissa drag motsäger den klassiska teorin om Go, men de bevisade sin effektivitet i matchen, några proffs började använda dessa fynd i sina spel [50] .

Liknande system

Facebook utvecklar också ett Go-spel, Darkforest , som också är baserat på maskininlärning och trädsökning [72] [80] . I början av 2016 visade Darkforest ett starkt spel mot andra datorer, men kunde inte slå proffset [81] . När det gäller styrka är Darkforest rankad på nivån Crazy Stone och Zen [82] program .

Den 1 mars 2016 tillkännagav utvecklarna av Zen-programmet (Yoji Ojima och Hideki Kato), DWANGO och University of Tokyo Deep Learning Research Group (som skapade Ponanza -programmet för att spela shogi som besegrar en person) en gemensamt projekt "Deep Zen Go Project" , med målet att besegra AlphaGo inom 6-12 månader. Japan Go Association lovade att stödja projektet [83] . I november 2016 förlorade Deep Zen Go med 2-1 mot Japans mest dekorerade spelare Cho Chikun [84] [85] .

Litteratur

  • Silver D., Huang A., Maddison CJ, Guez A., Sifre L., van den Driessche G., Schrittwieser J., Antonoglou I., Panneershelvam V., Lanctot M., Dieleman S., Grewe D., Nham J., Kalchbrenner N., Sutskever I., Lillicrap T., Leach M., Kavukcuoglu K., Graepel T. & Hassabis D. Bemästra spelet Go med djupa neurala nätverk och trädsökning  (engelska)  // Nature. - 2016. - 28 januari ( vol. 529 , iss. 7587 ). - s. 484-489 . — ISSN 0028-0836 . - doi : 10.1038/nature16961 . Arkiverad från originalet den 24 september 2019.

Se även

Anteckningar

  1. ↑ 1 2 Metz C. Varför det sista spelet mellan AlphaGo och Lee Sedol är en så stor sak för mänskligheten  . // Wired News (14 mars 2016). Hämtad 10 november 2016. Arkiverad från originalet 22 december 2016.
  2. ↑ Googles AlphaGo får "gudomlig" Go-  rankning . // The Straits Times (15 mars 2016). Hämtad 10 november 2016. Arkiverad från originalet 7 oktober 2016.
  3. ↑ Artificiell intelligens: Googles AlphaGo slår Go-mästaren Lee Se-dol . // BBC News (12 mars 2016). Hämtad 12 juli 2016. Arkiverad från originalet 26 augusti 2016.
  4. ↑ 1 2 3 4 Ribeiro J. AlphaGos ovanliga drag bevisar dess AI-förmåga, säger experter . // PC World (14 mars 2016). Hämtad 12 juli 2016. Arkiverad från originalet 17 juli 2016.
  5. ↑ 1 2 Silver et al., 2016 , sid. 488.
  6. ↑ Silver et al., 2016 .
  7. ↑ 1 2 Artificiell intelligens slår en professionell Go-spelare för första gången . // Meduza. Datum för åtkomst: 27 januari 2016. Arkiverad från originalet 4 februari 2016.
  8. ↑ 1 2 3 Forskningsblogg: AlphaGo: Bemästra det uråldriga spelet Go med maskininlärning . // Google Research Blog (27 januari 2016). Datum för åtkomst: 28 januari 2016. Arkiverad från originalet 1 februari 2016.
  9. ↑ Metz C. Sorgen och skönheten i att se Googles AI Play Go . // Wired News (11 mars 2016). Arkiverad från originalet den 7 november 2017.
  10. ↑ Huang A. Alpha Go: Combining Deep Neural Networks with Tree Search // Keynote Lecture CG2016 Conference på YouTube , med start kl. 35:56
  11. ↑ Demis Hassabis på Twitter . // Twitter. Hämtad 14 februari 2016. Arkiverad från originalet 27 juli 2019.
  12. ↑ Borowiec S. Googles AI-maskin mot världsmästare i 'Go': allt du behöver veta . // The Guardian (9 mars 2016). Hämtad 15 mars 2016. Arkiverad från originalet 15 mars 2016.
  13. ↑ Coulom R. . Betygslista 2016-01-01 . Arkiverad från originalet den 18 mars 2016.
  14. ↑ Ji-yoon L. Korean Go-mästare bevisar att mänsklig intuition fortfarande är kraftfull i Go (länk ej tillgänglig) . // The Korean Herald/ANN (14 mars 2016). Hämtad 15 mars 2016. Arkiverad från originalet 12 april 2016. 
  15. ↑ Metz C. Go Grandmaster Lee Sedol tar tröstvinst mot Googles AI . // Wired News (13 mars 2016). Hämtad 29 mars 2016. Arkiverad från originalet 17 november 2017.
  16. ↑ Ribeiro J. Googles AlphaGo AI-program starkt men inte perfekt, säger den besegrade sydkoreanska Go-spelaren . // PC World (12 mars 2016). Hämtad 13 mars 2016. Arkiverad från originalet 13 mars 2016.
  17. ↑ 1 2 Sung-vunna Y. Lee Se-dol visar AlphaGo beatable . // The Korea Times (13 november 2016). Hämtad 15 mars 2016. Arkiverad från originalet 14 mars 2016.
  18. ↑ 1 2 Hassabis D. Demis Hassabis på Twitter: "Excited to share a update on #AlphaGo!" . // Demis Hassabis Twitter - konto (4 januari 2017). Hämtad 4 januari 2017. Arkiverad från originalet 15 februari 2019.
  19. ↑ 1 2 Gibney E. Google avslöjar hemligt test av AI-bot för att slå topp Go-spelare . // Nature (4 januari 2017). Hämtad 4 januari 2017. Arkiverad från originalet 5 januari 2017.
  20. ↑ Ett annat spel slutade oavgjort eftersom en mänsklig spelare kopplades bort från servern på grund av nätverksproblem. Men resultatet räknades inte på FoxGo-servern, eftersom frånkopplingen inträffade i början av spelet.
  21. ↑ 横扫中日韩棋手斩获59胜的Master发话：我是阿尔法狗. // 澎湃新闻 (4 januari 2017). Hämtad 5 januari 2017. Arkiverad från originalet 30 september 2020.
  22. ↑ The Future of Go Summit, Match One: Ke Jie & AlphaGo på YouTube , med start 5:58:50 (23 maj 2017)
  23. ↑ Utforska Gos mysterier med AlphaGo och Kinas bästa spelare (10 april 2017). Hämtad 10 april 2017. Arkiverad från originalet 11 april 2017.
  24. ↑ AlphaGo drar sig tillbaka från konkurrenskraftiga Go efter att ha besegrat världsettan med 3-0 - The Verge . Hämtad 4 juni 2017. Arkiverad från originalet 7 juni 2017.
  25. ↑ 【柯洁战败解密】AlphaGo Master最新架构和算法，谷歌云与TPU拆解 (kinesiska) . Sohu (24 maj 2017). Hämtad 1 juni 2017. Arkiverad från originalet 17 september 2017.
  26. ↑ 1 2 3 4 AlphaGo Zero: Lär dig från grunden . DeepMind officiella webbplats (18 oktober 2017). Hämtad 19 oktober 2017. Arkiverad från originalet 19 oktober 2017.
  27. ↑ 1 2 3 4 Silver, David; Schrittwieser, Julian; Simonyan, Karen; Antonoglou, Ioannis; Huang, Aja; Guez, Arthur; Hubert, Thomas; Baker, Lucas; Lai, Matthew; Bolton, Adrian; Chen, Yutian; Lillicrap, Timothy; Fläkt, Hui; Sifre, Laurent; Driessche, George van den; Graepel, Thore; Hassabis, Demis. Att bemästra spelet Go utan mänsklig kunskap  (engelska)  // Nature  : journal. - 2017. - 19 oktober ( vol. 550 , nr 7676 ). - s. 354-359 . — ISSN 0028-0836 . - doi : 10.1038/nature24270 . Mall:Stängd åtkomst
  28. ↑ En allmän förstärkningsalgoritm som behärskar schack, shogi och gå igenom självspel | vetenskap . Hämtad 16 februari 2021. Arkiverad från originalet 8 mars 2021.
  29. ↑ Betyg av Go-spelare . Hämtad 12 juli 2016. Arkiverad från originalet 1 april 2017.
  30. ↑ Levinovitz A. Mysteriet med Go, det uråldriga spelet som datorer fortfarande inte kan  vinna . // Trådbundna nyheter . Datum för åtkomst: 30 januari 2016. Arkiverad från originalet 31 januari 2016.
  31. ↑ Schraudolph NN, Dayan P., Sejnowski TJ Temporell skillnadsinlärning av positionsutvärdering i spelet Go. // Framsteg inom neurala informationsbehandlingssystem. - 1994. - S. 817.
  32. ↑ Demis Hassabis How Artificial Intelligence (AI) Works DeepMind (Voice Hello Robots) på YouTube , med start 6:50
  33. ↑ Google uppnår AI-genombrott genom att slå Go-mästaren . // BBC News (27 januari 2016). Hämtad 12 juli 2016. Arkiverad från originalet 30 januari 2016.
  34. ↑ Mullen J. Computer vinner storvinst mot människor i antika spelet Go . // CNN (28 januari 2016). Arkiverad från originalet den 5 februari 2016.
  35. ↑ Ormerod D. Zen dator Go-programmet slår Takemiya Masaki med bara 4 stenar! (inte tillgänglig länk) . // Go Game Guru. Datum för åtkomst: 28 januari 2016. Arkiverad från originalet 1 februari 2016. 
  36. ↑ Cambier A. Le Corps sans limits  (franska) . — Press Univ. Septentrion, 2016. - S. 100. - 146 sid. — ISBN 9782757414859 .
  37. ↑ Gershgorn D. Googles AlphaGo slår världsmästaren i tredje matchen för att vinna hela serien . // Populärvetenskap (12 mars 2016). Hämtad 13 november 2016. Arkiverad från originalet 16 december 2016.
  38. ↑ Hoffman W. Elon Musk säger att Google Deepminds Go Victory är ett 10-årigt hopp för AI . // Invers (9 mars 2016). Hämtad 12 mars 2016. Arkiverad från originalet 12 mars 2016.
  39. ↑ Silver et al., 2016 , sid. 484.
  40. ↑ Google DeepMind-dator AlphaGo sveper mänsklig mästare i Go-matcher . // CBC News (12 mars 2016). Hämtad 13 mars 2016. Arkiverad från originalet 13 mars 2016.
  41. ↑ Yan S. En Google-dator som vann över världens "Go"-mästare . // CNN Money (12 mars 2016). Hämtad 13 mars 2016. Arkiverad från originalet 13 mars 2016.
  42. ↑ Borowiec S., Lien T. AlphaGo slår mänskliga Go-mästare som milstolpe för artificiell intelligens . // Los Angeles Times (12 mars 2016). Hämtad 13 mars 2016. Arkiverad från originalet 12 mars 2016.
  43. ↑ Zastrow M. Sydkorea basunerar ut AI-fond på 860 miljoner dollar efter AlphaGo "chock"  //  Nature News. - 2016. - 18 mars. - doi : 10.1038/nature.2016.19595 .
  44. ↑ Zhang Z. När läkare träffar AlphaGo: potentiell tillämpning av maskininlärning i klinisk medicin  // Annals of Translational Medicine. — 2016-03-01. - T. 4 , nej. 6 . — ISSN 2305-5839 . - doi : 10.21037/atm.2016.03.25 .
  45. ↑ Byford S. DeepMinds grundare Demis Hassabis om hur AI kommer att forma framtiden . // The Verge (10 mars 2016). Hämtad 12 juli 2016. Arkiverad från originalet 11 juli 2016.
  46. ↑ AlphaGo kan forma framtiden för sjukvård (länk ej tillgänglig) . // Den medicinska framtidsforskaren (5 april 2016). Hämtad 12 juli 2016. Arkiverad från originalet 14 juli 2016. 
  47. ↑ Man vs. maskin: Googles AI för att ta sig an stormästaren i det gamla kinesiska brädspelet  (engelska) . // ABC News (8 mars 2016). Hämtad 12 juli 2016. Arkiverad från originalet 15 juni 2016.
  48. ↑ Silver et al., 2016 , Metoder, sid. 489.
  49. ↑ Arlazarov V. L. Algoritmer för schackprogram . // acm.mipt.ru. Hämtad 12 juli 2016. Arkiverad från originalet 9 oktober 2016.
  50. ↑ 1 2 Metz C. Googles AI vinner avgörande andra match i match med Go Grandmaster . // Wired News (10 mars 2016). Hämtad 12 mars 2016. Arkiverad från originalet 11 mars 2016.
  51. ↑ Silver N. Signalen och bruset: Varför så många förutsägelser misslyckas - men vissa gör det inte . — Penguin, 2012-09-27. — 449 sid. - S. 195. - ISBN 9781101595954 .
  52. ↑ Match 3 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo på YouTube , med start 22:30
  53. ↑ Match 4 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo på YouTube , med start 6:09:35
  54. ↑ Google AlphaGo och maskininlärning (Alphago Korean Press Briefing 2 av 2) på YouTube
  55. ↑ 1 2 Maas D. Hur AlphaGo fungerar  . // Maas Digital (28 januari 2016). Hämtad 29 september 2016. Arkiverad från originalet 5 oktober 2016.
  56. ↑ 1 2 Burger C. Google DeepMinds AlphaGo: Hur det fungerar . // Om personalisering och data (16 mars 2016). Hämtad 1 november 2016. Arkiverad från originalet 1 november 2016.
  57. ↑ Schaeffer J., Burch N., Björnsson Y., Kishimoto A., Müller M., Lake R., Lu P., Sutphen S. Checkers is Solved // Science . - 2007. - T. 317, nr 5844. - P. 1518–22. - doi : 10.1126/science.1144079 . — PMID 17641166 .
  58. ↑ Convolutional Neural Networks (LeNet) - DeepLearning 0.1-dokumentation (inte tillgänglig länk) . // DeepLearning 0.1 (LISA Lab). Hämtad 31 augusti 2013. Arkiverad från originalet 28 december 2017. 
  59. ↑ Clark L. DeepMinds AI är nu ett Atari-spelproffs . // Wired Storbritannien. Hämtad 1 november 2016. Arkiverad från originalet 21 maj 2016.
  60. ↑ Silver et al., 2016 , Metoder.
  61. ↑ 1 2 Chernikov A. Chronicles of Go-4. Efter matchen . // Computer Review (18 mars 2016). Tillträdesdatum: 6 juni 2016. Arkiverad från originalet 2 augusti 2016.
  62. ↑ 1 2 Huang A. Alpha Go: Combining Deep Neural Networks with Tree Search // Keynote Lecture CG2016 Conference på YouTube , start kl 27:00
  63. ↑ Huang A. Alpha Go: Combining Deep Neural Networks with Tree Search // Keynote Lecture CG2016 Conference på YouTube , med start kl. 27:45
  64. ↑ En Nature - artikel ( Silver et al., 2016 Arkiverad 24 september 2019 på Wayback Machine ) hävdade att AlphaGos strategiska nätverk förutspådde en persons flytt med en sannolikhet på 24 %, men senare uppgav en av författarna, Aya Huan, att detta uppgifter felaktiga. Se Huang A. Alpha Go: Combining Deep Neural Networks with Tree Search // Keynote Lecture CG2016-konferens på YouTube med start kl. 34:45
  65. ↑ 李世乭：即使Alpha Go得到升级也一样能赢 (kinesiska) . // JoongAng Ilbo (23 februari 2016). Hämtad 7 juni 2016. Arkiverad från originalet 4 mars 2016.
  66. ↑ Silver et al., 2016 , Tabell 8.
  67. ↑ Silver et al., 2016 , Tabell 6.
  68. ↑ Showdown: Vinn eller förlora, ett datorprograms tävling mot en professionell Go-spelare är en annan milstolpe inom AI  . // The Economist (12 mars 2016). Hämtad 28 september 2017. Arkiverad från originalet 14 augusti 2017.
  69. ↑ McMillan R. Google spelar inte spel med nytt chip . // Wall Street Journal (18 maj 2016). Hämtad 26 juni 2016. Arkiverad från originalet 29 juni 2016.
  70. ↑ Jouppi N. Google överladdar maskininlärningsuppgifter med TPU-anpassat chip  . // Google Cloud Platform Blog (18 maj 2016). Hämtad 26 juni 2016. Arkiverad från originalet 18 maj 2016.
  71. ↑ The Future of Go Summit, Match One: Ke Jie & AlphaGo på YouTube , med start 06:03:10 (23 maj 2017)
  72. ↑ 1 2 Gibney E. Google AI-algoritm behärskar uråldriga spel Go . // Naturnyheter & Kommentar (27 januari 2016). Hämtad 3 februari 2016. Arkiverad från originalet 2 maj 2019.
  73. ↑ Lee Sedol förväntar sig "inte lätt" spel med AlphaGo i 3:e Go-matchen . // Shanghai Daily (10 mars 2016). Hämtad 10 mars 2016. Arkiverad från originalet 11 mars 2016.
  74. ↑ Nie Weiping 9d: "AlphaGo är ett 6-7 dan-proffs i början; 13d mitt i spelet; 15d slutspel" . // Reddit (15 mars 2016). Hämtad 13 september 2016. Arkiverad från originalet 1 juli 2016.
  75. ↑ Byford S. AlphaGo slår Lee Se-dol igen för att ta Google DeepMind Challenge-serien . // The Verge (Vox Media) (12 mars 2016). Hämtad 12 mars 2016. Arkiverad från originalet 13 mars 2016.
  76. ↑ 1 2 Ormerod D. Lee Sedol besegrar AlphaGo i mästerlig comeback - Game 4  ( nedlänk  ) . // Go Game Guru (13 mars 2016). Tillträdesdatum: 4 november 2016. Arkiverad från originalet 16 november 2016.
  77. ↑ Tanguy C. The Go Files: AI-dator avslutar 4-1 seger mot mänsklig  mästare . // Natur (15 mars 2016). Hämtad 13 september 2016. Arkiverad från originalet 17 september 2016.
  78. ↑ Huang A. Alpha Go: Combining Deep Neural Networks with Tree Search // Keynote Lecture CG2016 Conference på YouTube , med start kl. 37:28
  79. ↑ Audureau, W. Jeu de go: pour Lee Sedol, la victoire de la machine est moins tactique que psychologique  (franska) . // Le Monde (15 mars 2016). Hämtad 13 juni 2016. Arkiverad från originalet 16 mars 2016.
  80. ↑ Tian Y., Zhu Y. Better Computer Go Player with Neural Network and Long-term Prediction // ICLR 2016. - 2016. - 29 februari. - arXiv : 1511.06410v3 .
  81. ↑ HAL 90210 No Go: Facebook misslyckas med att förstöra Googles stora AI-dag  ( 28 januari 2016). Hämtad 1 februari 2016. Arkiverad från originalet 15 mars 2016.
  82. ↑ Hassabis D. Strachey föreläsning . // Den nya livestreamen. Hämtad 17 mars 2016. Arkiverad från originalet 16 mars 2016.
  83. ↑ 「DEEP ZEN GO プロジェクト」発表。AlphaGo対抗の囲碁ソフト開発をド」発表。1  ) . Hämtad 13 juli 2016. Arkiverad från originalet 6 juli 2016.
  84. ↑ Jiji. Go master Cho vinner bäst-av-tre-serien mot Japan-tillverkad AI . // The Japan Times Online (24 november 2016). Hämtad 27 november 2016. Arkiverad från originalet 14 augusti 2017.
  85. ↑ Bolton A. Människor slår tillbaka: Korean Go behärskar bästa AI i brädspelsmatch . // CNET (23 november 2016). Hämtad 27 november 2016. Arkiverad från originalet 25 november 2016.

Länkar