Alpha Go

AlphaGo  er et go -spil udviklet af Google DeepMind i 2015. AlphaGo var det første program i verden, der vandt en kamp uden handicap mod en professionel Go-spiller på et standard 19×19 -bræt , og denne sejr markerede et vigtigt gennembrud inden for kunstig intelligens, som de fleste specialister i kunstig intelligens mente, at et sådant program ikke vil blive oprettet før 2020-2025 . I marts 2016 vandt programmet 4-1 over Lee Sedol , en 9. dan (højest rangerende) professionel, under en meget omtalt historisk kamp [1] . Efter at have vundet kampen tildelte Korea Paduk Association AlphaGo en "æres 9. dan " for programmets "oprigtige indsats" for at mestre spillet [2] .

AlphaGos sejr over Lee Sedol sammenlignes ofte med skakkampen i 1997 mellem Deep Blue-programmet og Garry Kasparov , hvor IBM -programmets sejr over den regerende mester blev et symbolsk udgangspunkt for en ny æra, hvor computere overgik mennesker i skak [ 3] . I modsætning til Deep Blue er AlphaGo et program , der ikke er bundet til specifik hardware . Derudover er AlphaGo baseret på de generelle principper for maskinlæring og bruger praktisk talt ikke (i modsætning til skakprogrammer) hverken algoritmer eller evalueringsfunktioner, der er specifikke for spillet Go. Ved udviklingen af ​​AlphaGo brugte forfatterne kun den mest elementære teori om spillet Go, programmet nåede et højt niveau af spil og lærte sig selv fra professionelles spil . Således kan dens maskinlæringsmetoder bruges i andre anvendelsesområder for kunstig intelligens. Især planlægger udviklingsteamet at anvende de erfaringer, der er opnået, mens de skrev AlphaGo for at skabe et medicinsk diagnosesystem .

AlphaGo kombinerer den teknik, der gav det store gennembrud i kraften af ​​Go-programmer i 2007-2012 ( Monte Carlo-metoden til træsøgning ) og de seneste fremskridt inden for maskinlæring , nemlig deep learning med multilevel neurale netværk . netværk .

Historie

Ifølge en af ​​forfatterne af AlphaGo, David Silver , begyndte arbejdet med programmet i 2014 med en undersøgelse af, hvordan nye metoder til dyb læring ville fungere i Go [4] .

For at måle styrken af ​​deres program afholdt forfatterne en turnering mellem AlphaGo og den bedste gratis og kommercielle Go-software ( Crazy Stone , Zen , Pachi , Fuego ), som brugte Monte Carlo-metoden og GNU Go , som var den bedste gratis software før Monte Carlo-metoden. Som et resultat vandt den enkelte computerversion af AlphaGo 494 ud af 495 kampe [5] .

Match med Fan Hui

I oktober 2015 besejrede AlphaGo den tredobbelte europamester Fan Hui (2. professionel dan) i en fem-kamps kamp med en score på 5-0. Det er første gang i historien, at en computer har slået en professionel i et ligeværdigt spil. Dette blev offentligt annonceret i januar 2016 efter offentliggørelsen af ​​papir [6] i Nature [7] [8] . For hvert spil fik spillerne en time og 3 byoyomi på 30 sekunder.

Efter sit nederlag udtalte Fan Hui, at takket være denne kamp begyndte han at spille bedre og begyndte at se de elementer i spillet, som han ikke havde lagt mærke til før; i marts 2016 var Fan Huis globale placeringer steget med omkring 300 positioner [9] .

Nedenfor er et eksempel på et spil, hvor AlphaGo spillede sort. Fan Hui trak sig efter 165 træk [5] .

19
atten
17
16
femten
fjorten
13
12
elleve
ti
9
otte
7
6
5
fire
3
2
en
Første 99 træk (96 i 10)
19
atten
17
16
femten
fjorten
13
12
elleve
ti
9
otte
7
6
5
fire
3
2
en
Bevæger 100-165.

Efter kampen med Fan Hui begyndte AlphaGo-programmet at spille meget bedre (dets Elo-rating , beregnet af spil i forskellige versioner af programmet med hinanden, steg med 1500 point og oversteg 4500). Den nye version kunne slå den gamle og give et forspring på 3-4 sten [10] .

AlphaGo vs. Lee Sedol kamp

Fra 9. marts til 15. marts 2016 blev der spillet en AlphaGo-kamp med Lee Sedol (9. dan) [7] i Seoul, Sydkorea . Der blev spillet 5 kampe. For hvert spil fik spillerne 2 timer og 3 byoyomi i et minut. Præmiefonden beløb sig til 1 million dollars. Spillene blev streamet live på YouTube [11] .

På tidspunktet for kampen havde Lee Sedol det næsthøjeste antal verdensmesterskaber vundet [12] . Selvom der ikke er nogen enkelt officiel international metode til at rangere Go-spillere, rangerer nogle kilder Lee Sedol som den fjerde spiller i verden på tidspunktet for en kamp [13] [14] .

AlphaGo vandt kampen 4-1. Lee Sedol har overgivet sig i fire ud af fem kampe. AlphaGo, der spillede sort, tabte i det fjerde spil efter 180 træk. Ifølge udviklerne af programmet giver AlphaGo op, når det estimerer sandsynligheden for at vinde mindre end 20 % [15] .

Ifølge eksperter var AlphaGo under kampen med Li Sedol betydeligt stærkere og tilbød et sværere spil end under kampen med Fan Hui [16] . Lee Sedol sagde under en pressekonference, at hans nederlag er "Lee Sedols nederlag" og ikke "menneskehedens nederlag" [17] .

Uofficielle spil i slutningen af ​​2016/begyndelsen af ​​2017

Den 29. december 2016, på Tygem go-serveren, begyndte den nye konto " Master " at spille spil med go-professionelle, den 1. januar 2017 skiftede han til FoxGo go-serveren. Den 4. januar 2017 bekræftede DeepMind, at en opdateret version af AlphaGo [18] [19] spillede for Master og en tidligere Magister-konto . AlphaGo vandt alle 60 spillede spil (30 på hver server) [20] . I slutningen af ​​alle spil tweetede DeepMind-medstifter Demis Hassabis : "Ser frem til officielle Go-kampe senere i 2017, i samarbejde med Go-organisationer og eksperter" [18] [19] .

Master spillede 10 kampe om dagen og fangede hurtigt opmærksomheden fra mange spillere på Tygem-serveren med sine enestående færdigheder. Mange fik hurtigt mistanke om, at der var tale om en AI-spiller, da der enten ikke var nogen pauser mellem spillene, eller også varede de meget lidt. Mesterens modstandere var verdensmestre 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 ; ud over dem, nationale mestre og sølvmedaljevindere ved verdensmesterskaberne: Lian Xiao, Tan Xiao , Meng Tailing, Dan Yifei, Huang Yunsong, Yang Dingxin , Xing Jinso, Cho Hansyn , An Sunjun. Alle undtagen et af de 60 spil var hurtige med tre 20- eller 30-sekunders byoyomi, kun i kampen mod Nie Weiping foreslog Mesteren at øge byoyomien til et minut på grund af sidstnævntes høje alder. Efter 59 vinderspil afslørede Mesteren i en chat, at han blev drevet af Dr. Aya Huan fra DeepMind [21] .

AlphaGo- programmøren David Silver senere , at i modsætning til tidligere versioner af AlphaGo, var versionen, der spillede "Master", mere afhængig af læring, mens han spillede med sig selv, end at lære af professionelle spilleres spil, desuden brugte denne version ti gange færre beregninger og trænede i en uge i stedet for måneder som den version, der spillede med Lee Sedol [22] .

The Future of Go Summit

Den 23.-27. maj 2017 i den kinesiske by Wuzhen blev der afholdt et topmøde om Gos fremtid, hvor blandt andet AlphaGo afholdt flere demonstrationsspil [23] og vandt dem alle:

Pensionering

Efter topmødet om Gos fremtid sluttede, annoncerede DeepMind-grundlægger Demis Hassabis AlphaGos afgang fra Go, og der vil ikke være flere kampe i fremtiden. DeepMind har heller ingen planer om at frigive en offentlig version af AlphaGo [24] .

AlphaGo Zero

I oktober 2017 annoncerede DeepMind en endnu stærkere version af AlphaGo, AlphaGo Zero. Det nye neurale netværk blev trænet til at spille Go fra bunden, " tabula rasa ", ved at lege med sig selv (uden at lære af spil spillet af mennesker, som det var tilfældet i tidligere versioner af AlphaGo). På kun 21 dages selvlæring nåede systemet AlphaGo Master niveau af spilkraft og overgik det derefter. På den 40. dag, efter at have nået overlegenheden af ​​mere end 300 point af elo .

Sammenligning af AlphaGo-versioner

Versioner Hardware [25] Elo vurdering 1 Tændstikker
AlphaGo fan 176 GPU , [26] distribueret databehandling 3144 [27] 5:0 Kamp AlphaGo - Fan Hui
Alpha Go Lee 48 TPU , [26] distribueret databehandling 3739 [27] 4-1 AlphaGo mod Lee Sedol kamp
AlphaGo Master 4 TPU'er [26] v2, én maskine 4858 [27] 60:0 mod professionelle go-spillere;

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

AlphaGo Zero (40 blokke) 4 TPU'er [26] v2, én maskine 5185 [27] 100:0 mod AlphaGo Lee

89:11 vs. AlphaGo Master

AlphaZero (20 blokke) 4 TPU v2, én maskine 5018 [28] 60:40 vs. AlphaGo Zero (20 blokke) 2
Bemærkninger:

[1] Til sammenligning havde Ke Jies bedste human go-spiller en elo-vurdering på 3670 i oktober 2017 [29] . [2] AlphaZeros rating (20 blokke) er mindre end AlphaGo Zero (40 blokke), i en testkamp besejrede AlphaZero AlphaGo Zero med en score på 60:40 pga. der blev versioner af det neurale netværk med lige mange blokke sammenlignet.

Betydning

Før oprettelsen af ​​AlphaGo var Go et af de få traditionelle spil, som et menneske kunne spille bedre end en computer [30] .

Go er meget sværere end skak på grund af det større antal mulige positioner. For det første er der som regel flere lovlige træk i hver position i Go end i skak. For det andet varer et Go-spil flere træk i gennemsnit. Disse to egenskaber gør Go meget vanskelig for traditionelle AI -metoder såsom alfa-beta-beskæring [8] [31] .

En anden vanskelighed ved Go sammenlignet med skak og mange andre logiske spil er at skabe en evalueringsfunktion, der sammenligner en vilkårlig position med en bestemt vurdering: for hvilken side denne position er mere rentabel og hvor meget (eller positionen er lige). AlphaGo bruger 2 neurale netværk, hvoraf det ene er specialiseret i positionsvurdering. Det kan således betinget kaldes en analog af evalueringsfunktionen i skak [32] .

Af disse grunde, selv næsten tyve år efter, at Deep Blue- computeren første gang slog verdensmesteren Kasparov i 1997, har de stærkeste Go-programmer kun nået amatør 5 dan og kunne ikke slå pro'en på fuld bord [8] [33] [34] . De bedste præstationer af kunstig intelligens i Go var sejrene fra Zen -programmet , der kørte på en klynge af fire computere, mod den 9-dan professionelle Masaki Takemiya to gange med et handicap på fem og fire sten i 2012 [35] , samt sejren af ​​Crazy Stone -programmet over Yoshio Ishida (9. professionel dan) med et fire-stens handicap i 2013 [36] .

At skabe et program, der spiller Go well, har været en stopklods i udviklingen af ​​kunstig intelligens [1] . Indtil 2015 troede de fleste eksperter i kunstig intelligens, at et program, der kunne besejre verdensmesteren i Go, ikke ville blive skabt i mindst de næste fem år [37] , og mange af dem antog, at det ville tage mindst ti år [38] [39] [40] [41] . Selv efter AlphaGos sejr over Fan Hui forudsagde mange eksperter, at AlphaGo ville tabe til Li Sedol [42] .

Efter kampen med Lee Sedol annoncerede den sydkoreanske regering en investering på 1 billion won ($863 millioner ) i forskning i kunstig intelligens over de næste fem år [43] .

Praktisk anvendelse

Metoderne udviklet til at spille AlphaGo kan anvendes på andre områder af kunstig intelligens, især til medicinsk diagnostik [44] . Ifølge DeepMind-grundlægger Demis Hassabis har DeepMind indgået en aftale med UK National Health Service om at undersøge muligheden for at bruge kunstig intelligens til at analysere medicinske data [45] [46] . Til dette blev DeepMind Health- divisionen grundlagt .

AlphaGo-enhed

Grundlæggende principper

Et væsentligt træk ved AlphaGo er, at det bruger generelle algoritmer, der praktisk talt er uafhængige af funktionerne i spillet Go [47] . AlphaGo-algoritmen indeholder kun de grundlæggende principper i spillet, som enhver nybegynder begynder at studere spillet med, såsom at tælle antallet af gratis point ( dame ) for en gruppe af sten, og analysere muligheden for at fange sten ved hjælp af "stigen" "( shicho ) teknik. Resten lærte AlphaGo af sig selv ved at analysere en database med 160.000 spil ved hjælp af almindelige metoder, der kan bruges inden for andre områder af kunstig intelligens [48] . Heri adskiller AlphaGo sig fra systemer som Deep Blue  , en skaksupercomputer [4] . Når man skrev algoritmen til Deep Blue, blev der brugt avanceret skakteori. Så for eksempel brugte Deep Blue 8000 tilpasselige funktioner til at estimere positionen, Deep Blue havde et enormt bibliotek af åbninger [49] . AlphaGo er et program, der kan køre på enhver hardware (selvom det brugte en processor designet specifikt til maskinlæring ), og hvis principper kan bruges på andre områder. Det bruger ikke åbningsbiblioteket og har ikke direkte adgang til nogen database over træk under spillet (men bruger kun et neuralt netværk, der er trænet på et stort antal spil). Udviklerne af programmet ved ikke selv, hvordan AlphaGo vurderer positionen, dets tiltag er et fremkomstfænomen [50] . Derudover blev Deep Blue designet med ét mål for øje: at vinde en skakkamp mod Garry Kasparov [4] [51] . AlphaGo var ikke specifikt trænet til at spille mod Lee Sedol [17] [52] , desuden indeholdt AlphaGos træningsdatabase ikke Lee Sedols spil [53] , og under kampen ændrede AlphaGos program sig ikke eller tilpassede sig Lee Sedols spillestil [ 54] .

Den vigtigste innovation ved AlphaGo er brugen af ​​deep learning  , en teknik, der med succes er blevet anvendt til mønstergenkendelse (for eksempel til at søge efter billeder i Google Images ) [55] . AlphaGo bruger nemlig neurale netværk trænet i et stort antal professionelle spil, der er i stand til at forudsige, hvilket træk en professionel vil foretage i en bestemt position. Selvspillede spil forbedrede de neurale netværk yderligere. Dette alene gjorde det muligt for AlphaGo at spille på niveau med de bedste computerprogrammer i 2015: uden opremsning af muligheder, ved kun at bruge et neuralt netværk til at vælge et træk, var programmet i stand til at slå Pachi (et program, der spillede på niveau med en amatørsekund dan ) [56] .

Som de bedste tidligere Go-programmer, bruger AlphaGo også Monte Carlo-metoden til træsøgning (MCST) [56] . Essensen af ​​denne metode (navngivet i analogi med Monte Carlo-metoden i beregningsmatematik ) er, at for at estimere positionen, spiller programmet tilfældigt med sig selv mange gange, hver gang det bringer spillet til ende. Så vælger han det træk med det højeste antal sejre.

Teknologier før AlphaGo

Generelle tilgange til spil med perfekt information

Go er et spil med komplet information . Teoretisk set er der en optimal strategi for ethvert spil med perfekt information. For at finde den optimale strategi skal vi krydse hele spiltræet . For eksempel løste Chinook -programmet i 2007 fuldstændigt engelske udkast [57] på denne måde . Men for de fleste spil er denne metode upraktisk, fordi størrelsen af ​​træet kan være meget stor. Det kan estimeres som , hvor  er graden af ​​forgrening af spiltræet (det vil sige det omtrentlige antal mulige træk i hver position), og  er dybden af ​​spiltræet (det vil sige den omtrentlige længde af spillet) . For Go while for Chess Opregningen kan forkortes ved hjælp af to teknikker.

For det første kan dybden af ​​søgningen reduceres ved hjælp af evalueringsfunktionen : i stedet for at betragte spillet til ende, kan du estimere den mellemliggende position ved hjælp af heuristik . Denne tilgang fungerede godt i spil som skak , hvor en computer var i stand til at spille bedre end et menneske. Denne tilgang var dog ikke tilstrækkelig for Go på grund af spillets enorme kompleksitet.

En anden tilgang er at reducere graden af ​​forgrening af det viste træ ved at kassere nogle bevægelser. En sådan metode er Monte Carlo-metoden, som gjorde det muligt for computere at spille spil såsom backgammon bedre end mennesker .

Monte Carlo metode til træsøgning

Monte Carlo-metoden til træsøgning i sin enkleste form er som følger. Først vælges alle mulige træk fra den aktuelle position, og derefter spilles der et stort antal tilfældige spil for hvert træk. En tur scores som forholdet mellem sejre og tab for tilfældige spil, der starter på den tur. Samtidig afhænger sandsynligheden for at vælge et eller andet træk også af den aktuelle vurdering af positionen: de positioner, hvor sejren opstod oftere, vælges med en højere sandsynlighed. En sådan strategi tenderer asymptotisk til den optimale. Ved at bruge denne tilgang var AlphaGos forgængerprogrammer i stand til at nå niveauet som en svag amatør.

For at forbedre denne algoritme blev funktioner brugt til at forudsige det mest sandsynlige næste træk. Før AlphaGo blev lineære evalueringsfunktioner og funktioner afledt af overfladiske politikker brugt . Denne tilgang tillod mig at nå niveauet som en stærk amatør.

Dyb læring

AlphaGo arbejder ved hjælp af neurale netværk , en teknik, der med succes er blevet anvendt til mønstergenkendelse . Et stort gennembrud på dette område kom fra brugen af ​​flerlags konvolutionelle neurale netværk og en speciel teknik til træning af dem - dyb læring . Konvolutionelle neurale netværk består af flere lag af neuroner. Hvert niveau modtager en matrix af tal som input, kombinerer dem med nogle vægte og producerer ved hjælp af en ikke-lineær aktiveringsfunktion et sæt tal som output, som overføres til næste niveau. Ved mønstergenkendelse føres billedet til det første niveau, og det sidste niveau producerer resultatet. Neurale netværk trænes på et stort antal billeder, der konstant justerer de vægte, der bruges til at beregne resultatet. Som et resultat kommer det neurale netværk til en konfiguration, der selv er i stand til at genkende lignende billeder. Denne proces er umulig at forudsige, så det er svært at sige, hvordan det neurale netværk "tænker", men groft sagt svarer outputtene på mellemniveauerne til forskellige mulige klassifikationer [55] [58] .

Med denne teknik er der gjort store fremskridt inden for mønstergenkendelse , især inden for ansigtsgenkendelse . Det er også blevet brugt af DeepMind til at skabe kunstig intelligens , der er i stand til at lære at spille et videospil på egen hånd på en Atari 2600 videospilkonsol , ved at bruge skærmvideo som input [59] .

AlphaGo-algoritmen

Positionsrepræsentation

AlphaGo bruger foldede neurale netværk til at evaluere en position eller forudsige det næste træk. Ligesom et billede føres til et neuralt netværk under mønstergenkendelse, feeder AlphaGo en position til neurale netværk. Hver position er repræsenteret som et lagdelt billede , hvor hvert lag repræsenterer beskrivelser af de simple egenskaber for hvert emne på tavlen. Følgende simple egenskaber bruges: stenens farve, antallet af frie point ( dame ) for en given gruppe af sten (hvis der ikke er mere end 8), at tage sten, evnen til at gå til dette punkt, om dette sten blev sat for nylig. Den eneste ikke-trivielle egenskab, der bruges, er om en given gruppe er truet af at blive fanget i en stige ( shicho ). Der bruges i alt 48 binære egenskaber (egenskaber udtrykt som et heltal er repræsenteret ved hjælp af en enhedskode ). Således er hver position repræsenteret som en tabel af bit [60] .

Strategisk netværk

For ikke at overveje helt dårlige træk, og derved mindske graden af ​​forgrening ved søgning, bruger AlphaGo strategiske netværk [61] ( engelske  policy networks ) - neurale netværk , der hjælper med at vælge et godt træk.

Et af disse netværk ( SL policy networks ) kan forudsige det træk, som en professionel ville foretage i en given position. Dette er et 13-niveau neuralt netværk opnået ved overvåget læring (SL ) på 30 millioner positioner taget fra 160 tusinde spil spillet på KGS serveren af ​​spillere fra 6 til 9 dan. Træningen fandt sted over fire uger på 50 GPU'er ; stokastisk gradientnedstigning blev brugt som en indlæringsalgoritme til maksimal sandsynlighedssøgning [ 62] . Det resulterende neurale netværk beregnede en sandsynlighedsfordeling blandt alle mulige bevægelser i en given position (repræsenteret som beskrevet ovenfor ). Som et resultat var det neurale netværk i stand til korrekt at forudsige den bevægelse, som personen valgte i 57 % af testsituationer (ikke brugt til træning). Til sammenligning var det bedste resultat før AlphaGo 44%. Selv en lille stigning i nøjagtigheden af ​​forudsigelser øger spillets styrke betydeligt.  

Et strategisk netværk er i stand til at spille Go selv, hver gang det vælger et tilfældigt træk med en beregnet sandsynlighed.

Forbedret strategisk netværk

Det strategiske netværk blev forbedret med forstærkende læring ( RL ) :  Netværket blev nemlig konstant forbedret ved at lege med et af de tidligere opnåede netværk. Samtidig blev der hver gang valgt et tilfældigt netværk blandt de tidligere opnåede for at undgå genoptræning (situationer, hvor programmet vælger det bedste træk, forudsat at modstanderen bruger samme strategi, men kan spille dårligt mod en anden modstander). Resultatet var et strategisk netværk ( RL policy network ), der klarede sig bedre end det oprindelige netværk i 80 % af spillene.

Det viste sig, at det resulterende strategiske netværk, der hverken brugte evalueringsfunktionen eller opremsningen af ​​muligheder, var i stand til at vinde 85% af spillene mod det stærkeste åbne program på det tidspunkt, Pachi . Til sammenligning slog det før det bedste program, der spillede uden at bruge en søgning på muligheder, men kun et foldet neuralt netværk, Pachi 11% af spillene. Således var AlphaGo, uden opremsning af muligheder, i stand til at nå cirka niveauet for den tredje amatør dan, ifølge forfatterne af programmet [63] .

Hurtigt strategisk netværk

For at simulere det spil, der kræves i Monte Carlo-metoden (se nedenfor ), bruger AlphaGo en hurtigere, men mindre præcis version af det strategiske netværk ( udrulningspolitik ), som modtager et svar på kun 2 µs. Dette hurtige netværk forudsiger en persons bevægelse med 30 % sandsynlighed [64] , mens det forbedrede strategiske netværk giver et svar på det samme udstyr på 3 ms med 57 % sandsynlighed.

Vurderingsnetværk

AlphaGo brugte et værdinetværk [ 61 ] til at reducere søgedybden .  Dette neurale netværk estimerer sandsynligheden for at vinde i en given position. Dette netværk er resultatet af træning på 30 millioner stillinger opnået ved at spille det forbedrede strategiske netværk med sig selv. Samtidig blev der ikke valgt mere end én position fra hvert spil (for at undgå genoptræning på grund af ligheden mellem positioner i et spil). For hver af disse positioner blev sandsynligheden for at vinde estimeret ved hjælp af Monte Carlo-metoden: der blev arrangeret en turnering med mange spil, hvor det forbedrede strategiske netværk bygget på det foregående trin spillede med sig selv, startende fra denne position. Herefter blev scoringsnetværket trænet på disse data. Uddannelsen tog en uge på 50 GPU'er . Resultatet var et netværk, der kunne forudsige sandsynligheden for at vinde for hver position, mens man brugte 15.000 gange mindre beregning end Monte Carlo-metoden.

Træsøgning

AlphaGo opregner mulighederne ved at bruge Monte Carlo-metoden til at søge i træet som følger. AlphaGo bygger et delvist spiltræ [ , startende fra den aktuelle position, og laver adskillige simuleringer af spillet. For hvert træk registreres en score i træet, som på en særlig måde afhænger af scorerne for træk opnået ved hjælp af de strategiske og evaluering netværk, på resultatet af tilfældige spil i tidligere simuleringer, og på antallet af tidligere simuleringer, der valgte dette træk (jo oftere, jo tidligere dette træk, jo lavere score, så programmet overvejer mere forskelligartede træk).

I begyndelsen af ​​hver simulering vælger AlphaGo et træk i det allerede byggede træ, med den højeste score. Når simuleringen når en position, der ikke er i træet, tilføjes denne position til træet sammen med alle træk, der er tilladt i den position, som evalueres ved hjælp af det strategiske net . Yderligere, som i Monte Carlo-metoden, simuleres spillet til slutningen uden forgrening. I denne simulering er hvert træk valgt tilfældigt med en sandsynlighed opnået ved hjælp af et hurtigt strategisk netværk .

Ved afslutningen af ​​simuleringen, afhængigt af resultatet, opdateres bevægelsesestimaterne i det konstruerede træ. Således starter hver simulering fra den aktuelle spilposition, når slutningen, og som et resultat af en simulering afsløres en position i det aktuelle træ.

Forfatterne af programmet fandt ud af, at det på dette stadium er mere rentabelt ikke at bruge det forbedrede strategiske netværk , men det originale ( SL-politiknetværk ) . Ifølge forfatterne skyldes det, at professionelle spillere vælger mere forskelligartede træk end det forbedrede netværk, som gør det muligt for programmet at overveje flere muligheder. Det forbedrede strategiske netværk bliver således ikke brugt under spillet, men dets brug er essentielt for at opbygge evalueringsnetværket , når programmet lærer ved at lege med sig selv.

Hardware

AlphaGo blev trænet over flere uger på 50 GPU'er ved hjælp af Google Cloud platformen hostet i USA [62] [65] .

AlphaGo er blevet testet på computersystemer med varierende antal CPU'er og GPU'er , der kører parallelt eller distribueret . I hvert tilfælde blev der givet 2 sekunder pr. træk. Ratings opnået på samme tid, beregnet på grundlag af resultaterne af spil med hinanden i henhold til Elo-systemet , er præsenteret i tabellen: [66]

Computing Udførelsestråde
_
Antal CPU'er Antal GPU'er Elo bedømmelse
Parallel 40 48 en 2181
Parallel 40 48 2 2738
Parallel 40 48 fire 2850
Parallel 40 48 otte 2890
Uddelt 12 428 64 2937
Uddelt 24 764 112 3079
Uddelt 40 1202 176 3140
Uddelt 64 1920 280 3168

Den version, der slog Fan Hui i oktober 2015, kørte på 1202 CPU'er og 176 GPU'er [67] .

I et spil med Lee Sedol i marts 2016 brugte AlphaGo 1920 CPU'er og 280 GPU'er, der kørte på et distribueret netværk [68] .

I maj 2016 annoncerede Google , at AlphaGo brugte TPU , en processor udviklet af Google specifikt til maskinlæring [69] [70] .

I kampen mod Ke Jie i maj 2017 brugte den nye version af AlphaGo kun én computer på Google Cloud med en TPU-processor, det vil sige omkring 10 gange mindre computerkraft end der blev brugt i kampen med Lee Sedol [71] .

Spillestil

Toby Manning, dommeren i AlphaGos kamp med Fan Hui, beskrev AlphaGos spillestil som konservativ snarere end aggressiv [72] . Ifølge DeepMind CEO , Demis Hassabis, forsøger AlphaGo at øge sandsynligheden for at vinde, ikke scoregabet [4] .

Professionelle spillere bemærkede, at nogle af AlphaGos træk, som oprindeligt så ud til at være fejlagtige, viste sig at være strategisk vigtige ved nærmere undersøgelse [73] .

Nie Weiping (Pro 9. Dan, Kina ) foreslog efter det første spil med Li Sedol, at AlphaGo spillede på 6. eller 7. dan-niveau i fuseki og 13-15 dan i chuban [74] .

I den tredje rate blev det fundet, at AlphaGo var i stand til at kontrollere situationen under ko-fighting , som tidligere var blevet betragtet som en væsentlig svaghed i de fleste Go-programmer [75] .

Nogle anmeldere har beskrevet AlphaGos fejl, der førte til tabet i spil 4 , som typiske fejl for et Monte Carlo-program [76] . Demis Hassabis udtalte, at disse fejl vil blive nøje analyseret, og at AlphaGo tilsyneladende ikke kender nogle af de klassiske tesuji og laver taktiske fejl [77] . Efterfølgende sagde Aya Huan (en af ​​AlphaGo-udviklerne, der satte stenene bag AlphaGo), at skriveholdet havde to antagelser om årsagerne til disse fejl: enten havde AlphaGo simpelthen ikke nok visningsdybde til at analysere situationen; eller Lee Sedols 78. træk var så usædvanligt (kommentatorer kaldte det "guddommelig" [76] ), at programmet ikke stødte på sådanne situationer under selvlæring, som et resultat, viste dets evaluerende funktion (se ovenfor ) i denne situation at være svag. I hvert fald, ifølge Aya Huang, spiller den nye version af AlphaGo allerede korrekt i denne situation. Samtidig lavede holdet ikke noget særligt, AlphaGo selv, som følge af træning, holdt op med at lave sådanne fejl [78] .

Efter kampen udtalte Lee Sedol, at han blev slået psykologisk, men slet ikke teknisk [79] . Programmet viste en evne til kreative løsninger, som overraskede mange spillere (for eksempel træk nummer 37 i det andet spil ); nogle træk var i modstrid med den klassiske teori om Go, men de beviste deres effektivitet i kampen, nogle professionelle begyndte at bruge disse resultater i deres spil [50] .

Lignende systemer

Facebook er også ved at udvikle et Go-spil, Darkforest , som også er baseret på maskinlæring og træsøgning [72] [80] . I begyndelsen af ​​2016 viste Darkforest et stærkt spil mod andre computere, men kunne ikke slå pro'en [81] . Med hensyn til styrke er Darkforest vurderet på niveau med Crazy Stone og Zen [82] programmer .

Den 1. marts 2016 annoncerede udviklerne af Zen-programmet (Yoji Ojima og Hideki Kato), DWANGO og University of Tokyo Deep Learning Research Group (som oprettede Ponanza -programmet til at spille shogi , der besejrer en person) en fælles projekt "Deep Zen Go Project" , med det mål at besejre AlphaGo inden for 6-12 måneder. Japan Go Association lovede at støtte projektet [83] . I november 2016 tabte Deep Zen Go 2-1 til Japans mest dekorerede spiller 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. Mestring af spillet Go med dybe neurale netværk og træsøgning  (engelsk)  // Nature. - 2016. - 28. januar ( vol. 529 , iss. 7587 ). - S. 484-489 . — ISSN 0028-0836 . - doi : 10.1038/nature16961 . Arkiveret fra originalen den 24. september 2019.

Se også

Noter

  1. 1 2 Metz C. Hvorfor det sidste spil mellem AlphaGo og Lee Sedol er så stort for menneskeheden  . // Wired News (14. marts 2016). Hentet 10. november 2016. Arkiveret fra originalen 22. december 2016.
  2. Googles AlphaGo får 'guddommelig' Go-  rangering . // The Straits Times (15. marts 2016). Hentet 10. november 2016. Arkiveret fra originalen 7. oktober 2016.
  3. Kunstig intelligens: Googles AlphaGo slår Go-mester Lee Se-dol . // BBC News (12. marts 2016). Hentet 12. juli 2016. Arkiveret fra originalen 26. august 2016.
  4. 1 2 3 4 Ribeiro J. AlphaGos usædvanlige træk beviser dens AI-dygtighed, siger eksperter . // PC World (14. marts 2016). Hentet 12. juli 2016. Arkiveret fra originalen 17. juli 2016.
  5. 1 2 Silver et al., 2016 , s. 488.
  6. Silver et al., 2016 .
  7. 1 2 Kunstig intelligens slår en professionel Go-spiller for første gang . // Meduza. Dato for adgang: 27. januar 2016. Arkiveret fra originalen 4. februar 2016.
  8. 1 2 3 Forskningsblog: AlphaGo: Mestring af det ældgamle spil Go med Machine Learning . // Google Research Blog (27. januar 2016). Dato for adgang: 28. januar 2016. Arkiveret fra originalen 1. februar 2016.
  9. Metz C. Tristheden og skønheden ved at se Googles AI Play Go . // Wired News (11. marts 2016). Arkiveret fra originalen den 7. november 2017.
  10. Huang A. Alpha Go: Combining Deep Neurale Networks with Tree Search // Keynote Lecture CG2016 ConferenceYouTube , startende kl. 35:56
  11. Demis Hassabis på Twitter . // Twitter. Hentet 14. februar 2016. Arkiveret fra originalen 27. juli 2019.
  12. Borowiec S. Googles AI-maskine mod verdensmester i 'Go': alt hvad du behøver at vide . // The Guardian (9. marts 2016). Hentet 15. marts 2016. Arkiveret fra originalen 15. marts 2016.
  13. Coulom R. . Bedømmelsesliste af 2016-01-01 . Arkiveret fra originalen den 18. marts 2016.
  14. Ji-yoon L. Koreansk Go-mester beviser, at menneskelig intuition stadig er stærk i Go (link utilgængeligt) . // The Korean Herald/ANN (14. marts 2016). Hentet 15. marts 2016. Arkiveret fra originalen 12. april 2016. 
  15. Metz C. Go Stormester Lee Sedol får trøstesejr mod Googles AI . // Wired News (13. marts 2016). Hentet 29. marts 2016. Arkiveret fra originalen 17. november 2017.
  16. Ribeiro J. Googles AlphaGo AI-program er stærkt, men ikke perfekt, siger den besejrede sydkoreanske Go-spiller . // PC World (12. marts 2016). Hentet 13. marts 2016. Arkiveret fra originalen 13. marts 2016.
  17. 1 2 Sung-vundne Y. Lee Se-dol viser AlphaGo beatable . // The Korea Times (13. november 2016). Hentet 15. marts 2016. Arkiveret fra originalen 14. marts 2016.
  18. 1 2 Hassabis D. Demis Hassabis på Twitter: "Glæder mig til at dele en opdatering om #AlphaGo!" . // Demis Hassabis' Twitter - konto (4. januar 2017). Hentet 4. januar 2017. Arkiveret fra originalen 15. februar 2019.
  19. 1 2 Gibney E. Google afslører hemmelig test af AI-bot for at slå top Go-spillere . // Natur (4. januar 2017). Hentet 4. januar 2017. Arkiveret fra originalen 5. januar 2017.
  20. Et andet spil endte uafgjort, da en menneskelig spiller afbrød forbindelsen til serveren på grund af netværksproblemer. Men resultatet blev ikke regnet med på FoxGo-serveren, fordi afbrydelsen skete i begyndelsen af ​​spillet.
  21. 横扫中日韩棋手斩获59胜的Master发话:我是阿尔法狗. // 澎湃新闻 (4. januar 2017). Hentet 5. januar 2017. Arkiveret fra originalen 30. september 2020.
  22. The Future of Go Summit, Match One: Ke Jie & AlphaGoYouTube , startende kl. 5:58:50 (23. maj 2017)
  23. Udforsk mysterierne bag Go med AlphaGo og Kinas bedste spillere (10. april 2017). Hentet 10. april 2017. Arkiveret fra originalen 11. april 2017.
  24. AlphaGo trækker sig fra konkurrencedygtige Go efter at have besejret verdens nummer et 3-0 - The Verge . Hentet 4. juni 2017. Arkiveret fra originalen 7. juni 2017.
  25. 【柯洁战败解密】AlphaGo Master最新架构和算法,谷歌云与TPU拆解 (kinesisk) . Sohu (24. maj 2017). Hentet 1. juni 2017. Arkiveret fra originalen 17. september 2017.
  26. 1 2 3 4 AlphaGo Zero: At lære fra bunden . DeepMind officielle hjemmeside (18. oktober 2017). Hentet 19. oktober 2017. Arkiveret fra originalen 19. oktober 2017.
  27. 1 2 3 4 Sølv, David; Schrittwieser, Julian; Simonyan, Karen; Antonoglou, Ioannis; Huang, Aja; Guez, Arthur; Hubert, Thomas; Bager, Lucas; Lai, Matthew; Bolton, Adrian; Chen, Yutian; Lillicrap, Timothy; Fan, Hui; Sifre, Laurent; Driessche, George van den; Graepel, Thore; Hassabis, Demis. Mestring af spillet Go uden menneskelig viden  (engelsk)  // Nature  : journal. - 2017. - 19. oktober ( bd. 550 , nr. 7676 ). - S. 354-359 . — ISSN 0028-0836 . - doi : 10.1038/nature24270 . Skabelon: Lukket adgang
  28. En generel forstærkende læringsalgoritme, der mestrer skak, shogi og gå gennem selvspil | videnskab . Hentet 16. februar 2021. Arkiveret fra originalen 8. marts 2021.
  29. Bedømmelse af Go-spillere . Hentet 12. juli 2016. Arkiveret fra originalen 1. april 2017.
  30. Levinovitz A. Mysteriet om Go, det ældgamle spil, som computere stadig ikke kan vinde  . // Kablede nyheder . Dato for adgang: 30. januar 2016. Arkiveret fra originalen 31. januar 2016.
  31. Schraudolph NN, Dayan P., Sejnowski TJ Temporal forskelsindlæring af positionsevaluering i spillet Go. // Fremskridt inden for neurale informationsbehandlingssystemer. - 1994. - S. 817.
  32. Demis Hassabis How Artificial Intelligence (AI) Works DeepMind (Voice Hello Robots)YouTube , startende kl. 6:50
  33. Google opnår AI 'gennembrud' ved at slå Go-mesteren . // BBC News (27. januar 2016). Hentet 12. juli 2016. Arkiveret fra originalen 30. januar 2016.
  34. Mullen J. Computer opnår stor sejr mod mennesker i det gamle spil Go . // CNN (28. januar 2016). Arkiveret fra originalen den 5. februar 2016.
  35. Ormerod D. Zen computer Go-programmet slår Takemiya Masaki med kun 4 sten! (utilgængeligt link) . // Go Game Guru. Dato for adgang: 28. januar 2016. Arkiveret fra originalen 1. februar 2016. 
  36. Cambier A. Le Corps sans limits  (fransk) . — Tryk Univ. Septentrion, 2016. - S. 100. - 146 s. — ISBN 9782757414859 .
  37. Gershgorn D. Googles AlphaGo slår verdensmester i tredje kamp for at vinde hele serien . // Populærvidenskab (12. marts 2016). Hentet 13. november 2016. Arkiveret fra originalen 16. december 2016.
  38. Hoffman W. Elon Musk siger, at Google Deepmind's Go Victory er et 10-årigt spring for AI . // Omvendt (9. marts 2016). Hentet 12. marts 2016. Arkiveret fra originalen 12. marts 2016.
  39. Silver et al., 2016 , s. 484.
  40. Google DeepMind computer AlphaGo fejer menneskelig mester i Go-kampe . // CBC News (12. marts 2016). Hentet 13. marts 2016. Arkiveret fra originalen 13. marts 2016.
  41. Yan S. En Google-computer, der sejrede over verdens 'Go'-mester . // CNN Money (12. marts 2016). Hentet 13. marts 2016. Arkiveret fra originalen 13. marts 2016.
  42. Borowiec S., Lien T. AlphaGo slår den menneskelige Go-mester som milepæl for kunstig intelligens . // Los Angeles Times (12. marts 2016). Hentet 13. marts 2016. Arkiveret fra originalen 12. marts 2016.
  43. Zastrow M. Sydkorea udbasunerer $860 millioner AI-fond efter AlphaGo 'chok'  //  Nature News. - 2016. - 18. marts. - doi : 10.1038/nature.2016.19595 .
  44. Zhang Z. Når læger mødes med AlphaGo: potentiel anvendelse af maskinlæring til 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. DeepMind-grundlægger Demis Hassabis om, hvordan AI vil forme fremtiden . // The Verge (10. marts 2016). Hentet 12. juli 2016. Arkiveret fra originalen 11. juli 2016.
  46. AlphaGo kan forme fremtidens sundhedspleje (link ikke tilgængeligt) . // Den medicinske fremtidsforsker (5. april 2016). Hentet 12. juli 2016. Arkiveret fra originalen 14. juli 2016. 
  47. Mand vs. maskine: Googles AI til at tage på stor mester i det gamle kinesiske brætspil  (engelsk) . // ABC News (8. marts 2016). Hentet 12. juli 2016. Arkiveret fra originalen 15. juni 2016.
  48. Silver et al., 2016 , Metoder, s. 489.
  49. Arlazarov V. L. Algoritmer for skakprogrammer . // acm.mipt.ru. Hentet 12. juli 2016. Arkiveret fra originalen 9. oktober 2016.
  50. 1 2 Metz C. Googles AI vinder afgørende andet spil i kamp med Go Grandmaster . // Wired News (10. marts 2016). Hentet 12. marts 2016. Arkiveret fra originalen 11. marts 2016.
  51. Silver N. Signalet og støjen: Hvorfor så mange forudsigelser slår fejl, men nogle gør det ikke . - Penguin, 2012-09-27. — 449 s. - S. 195. - ISBN 9781101595954 .
  52. Kamp 3 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGoYouTube , starter kl. 22:30
  53. Kamp 4 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGoYouTube , startende kl. 6:09:35
  54. Google AlphaGo og maskinlæring (Alphago Korean Press Briefing 2 af 2)YouTube
  55. 1 2 Maas D. Sådan fungerer AlphaGo  . // Maas Digital (28. januar 2016). Hentet 29. september 2016. Arkiveret fra originalen 5. oktober 2016.
  56. 1 2 Burger C. Google DeepMind's AlphaGo: Sådan virker det . // Om personalisering og data (16. marts 2016). Hentet 1. november 2016. Arkiveret fra originalen 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. - S. 1518–22. - doi : 10.1126/science.1144079 . — PMID 17641166 .
  58. Convolutional Neural Networks (LeNet) - DeepLearning 0.1-dokumentation (utilgængeligt link) . // DeepLearning 0.1 (LISA Lab). Hentet 31. august 2013. Arkiveret fra originalen 28. december 2017. 
  59. Clark L. DeepMind's AI er nu en Atari gaming pro . // Wired UK. Hentet 1. november 2016. Arkiveret fra originalen 21. maj 2016.
  60. Silver et al., 2016 , Metoder.
  61. 1 2 Chernikov A. Chronicles of Go-4. Efter kampen . // Computeranmeldelse (18. marts 2016). Dato for adgang: 6. juni 2016. Arkiveret fra originalen 2. august 2016.
  62. 1 2 Huang A. Alpha Go: Combining Deep Neurale Networks with Tree Search // Keynote Lecture CG2016 ConferenceYouTube , startende kl. 27:00
  63. Huang A. Alpha Go: Combining Deep Neurale Networks with Tree Search // Keynote Lecture CG2016 ConferenceYouTube , startende kl. 27:45
  64. ↑ En Nature - artikel ( Silver et al., 2016 Arkiveret 24. september 2019 på Wayback Machine ) hævdede, at AlphaGos strategiske netværk forudsagde en persons bevægelse med en sandsynlighed på 24 %, men senere udtalte en af ​​forfatterne, Aya Huan, at dette data fejlagtige. Se Huang A. Alpha Go: Combining Deep Neural Networks with Tree Search // Keynote Lecture CG2016-konferenceYouTube , der starter kl. 34:45
  65. 李世乭:即使Alpha Go得到升级也一样能赢 (kinesisk) . // JoongAng Ilbo (23. februar 2016). Hentet 7. juni 2016. Arkiveret fra originalen 4. marts 2016.
  66. Silver et al., 2016 , tabel 8.
  67. Silver et al., 2016 , tabel 6.
  68. ↑ Showdown: Vind eller tab , et computerprograms konkurrence mod en professionel Go-spiller er endnu en milepæl i AI  . // The Economist (12. marts 2016). Hentet 28. september 2017. Arkiveret fra originalen 14. august 2017.
  69. McMillan R. Google spiller ikke spil med ny chip . // Wall Street Journal (18. maj 2016). Hentet 26. juni 2016. Arkiveret fra originalen 29. juni 2016.
  70. Jouppi N. Google supercharger maskinlæringsopgaver med TPU tilpasset chip  . // Google Cloud Platform Blog (18. maj 2016). Hentet 26. juni 2016. Arkiveret fra originalen 18. maj 2016.
  71. The Future of Go Summit, Match One: Ke Jie & AlphaGoYouTube , startende kl. 06:03:10 (23. maj 2017)
  72. ↑ 1 2 Gibney E. Google AI-algoritme mestrer det gamle Go-spil . // Naturnyt & Kommentar (27. januar 2016). Hentet 3. februar 2016. Arkiveret fra originalen 2. maj 2019.
  73. Lee Sedol forventer "ikke let" spil med AlphaGo i 3. Go-kamp . // Shanghai Daily (10. marts 2016). Hentet 10. marts 2016. Arkiveret fra originalen 11. marts 2016.
  74. Nie Weiping 9d: "AlphaGo er en 6-7 dan pro i begyndelsen; 13d midt i spillet; 15d slutspil" . // Reddit (15. marts 2016). Hentet 13. september 2016. Arkiveret fra originalen 1. juli 2016.
  75. Byford S. AlphaGo slår Lee Se-dol igen for at tage Google DeepMind Challenge-serien . // The Verge (Vox Media) (12. marts 2016). Hentet 12. marts 2016. Arkiveret fra originalen 13. marts 2016.
  76. 1 2 Ormerod D. Lee Sedol besejrer AlphaGo i mesterligt comeback - Spil 4  ( downlink  ) . // Go Game Guru (13. marts 2016). Dato for adgang: 4. november 2016. Arkiveret fra originalen 16. november 2016.
  77. Tanguy C. The Go Files: AI computer afslutter 4-1 sejr mod menneskelig  mester . // Natur (15. marts 2016). Hentet 13. september 2016. Arkiveret fra originalen 17. september 2016.
  78. Huang A. Alpha Go: Combining Deep Neurale Networks with Tree Search // Keynote Lecture CG2016 ConferenceYouTube , startende kl. 37:28
  79. Audureau, W. Jeu de go: pour Lee Sedol, la victoire de la machine est moins tactique que psychologique  (fransk) . // Le Monde (15. marts 2016). Hentet 13. juni 2016. Arkiveret fra originalen 16. marts 2016.
  80. Tian Y., Zhu Y. Better Computer Go Player with Neural Network and Long-term Prediction // ICLR 2016. - 2016. - 29. februar. - arXiv : 1511.06410v3 .
  81. HAL 90210 No Go: Facebook formår ikke at spolere Googles store AI-dag  ( 28. januar 2016). Hentet 1. februar 2016. Arkiveret fra originalen 15. marts 2016.
  82. ↑ Foredrag om Hassabis D. Strachey . // Den nye livestream. Hentet 17. marts 2016. Arkiveret fra originalen 16. marts 2016.
  83. 「DEEP ZEN GO プロジェクト」発表。AlphaGo対抗の囲碁ソフト開発をド」発表 。1 ) . Hentet 13. juli 2016. Arkiveret fra originalen 6. juli 2016.
  84. Jiji. Go master Cho vinder bedst-af-tre-serien mod Japan-fremstillet AI . // The Japan Times Online (24. november 2016). Hentet 27. november 2016. Arkiveret fra originalen 14. august 2017.
  85. Bolton A. Mennesker slår tilbage: Korean Go mestrer bedst AI i brætspilskamp . // CNET (23. november 2016). Hentet 27. november 2016. Arkiveret fra originalen 25. november 2016.

Links