Fan Hui, tre-tiden mästare i öst-Asiatiska brädspel, förlorade DeepMind program AlphaGo i fem raka matcher
Fan Hui gör en rörelse mot AlphaGo i DeepMind s HUVUDKONTOR i King ‘ s Cross.
Foto: Google DeepMind
@alexhern
Onsdag 27 januari 2016 18.15 GMT
Senast ändrad onsdag, 27 januari 2016 18.22 GMT
När Gary Kasparov förlorade mot schack dator Deep Blue 1997, IBM markerade en milstolpe i historien om artificiell intelligens. På onsdagen, i en uppsats som frigörs i Naturen, Google förtjänat sin egen position i historieböckerna, med tillkännagivande att dess dotterbolag DeepMind har byggt ett system som kan slå de bästa mänskliga spelarna i världen i öst-Asiatiska brädspel Gå.
Gå, ett spel som handlar om att placera svart eller vitt kakel på en 19×19 styrelsen och försöker ta bort dina motståndare, är mycket svårare för en dator att bemästra än ett spel som schack.
DeepMind programvara, AlphaGo, lyckas slå tre-tiden Europeisk mästare Fan Hui 5-0 i en serie av spel på företagets huvudkontor i King ‘ s Cross i oktober förra året. Dr Tanguy Chouard, senior redaktör på Naturen som deltog i matcherna som en del av översynen, som beskrivs segern som “verkligen skrämmande att titta på”.
“Det var en av de mest spännande ögonblicken i min karriär”, tillade han. “Men med den vanliga blandade känslor … i det tysta rummet på nedervåningen, man kunde inte låta bli root för de fattiga människors bli slagen.”
Det är det första seger för ett datorprogram, och det kom ett decennium innan någon hade förväntat sig det. Så sent som för 2014, Rémi Coulom, utvecklare av den tidigare ledande Gå spelets AI, Galen Sten, hade förutspått att det skulle ta 10 år för en maskin att vinna mot ett topp-betyg mänskliga spelare utan handikapp.
AlphaGo slå alla förväntningar genom att närma sig denna utmaning på ett helt annat sätt än tidigare program. Att bygga på teknik DeepMind hade använts i andra bedrifter av artificiell intelligens, såsom sitt system som kan lära sig att spela retro tv-spel, AlphaGo används för vad företaget kallar “Djupt Lärande” för att bygga upp sin egen förståelse av spelet. Det kunde sedan plocka flyttar det tänkte mest sannolikt att vinna.
När lära en dator att spela ett spel, är den enklaste metoden är att berätta det för att rangordna varje möjligt drag under loppet av spelet, från bäst till sämst, och sedan instruera den att alltid välja det bästa draget. Att denna typ av strategi som fungerar för triviala spel som drag och luffarschack, som båda är “löst” av datorer som till fullo har undersökt varje styrelse staten och arbetat fram ett sätt att spela minst oavgjort, oavsett vad andra spelare gör.
Men det komplicerade spel som Schack, den enkla metoden misslyckas. Schack är alldeles för stor: i varje tur finns det cirka 35 rättsliga åtgärder, och ett spel som varar i cirka 80 varv. Att räkna upp varje styrelsepost blir beräkningsmässigt omöjligt mycket snabbt, vilket är anledningen till att det tog så många år för IBM: s team för att arbeta fram ett sätt att slå Kasparov.
Go är större ändå. Definitionen av lätt att lära, svårt att bemästra, det har egentligen bara två regler för kärnan spel, vilket innebär att två spelare placera växelvis svarta och vita plattor på en 19×19 styrelsen. Stenarna skall placeras med minst en tom plats bredvid sig, eller en del av en grupp av stenar av samma färg med minst ett tomt utrymme, och om de förlorar sin “frihet”, tas de bort från brädet.
Medan ett parti schack kan ha 35 rättsliga åtgärder är varje tur, en omgång av Go har runt 250 (inklusive 361 rättsliga utgångspunkter ensam), där Schack spel att pågå cirka 80 varv, Gå spel sista 150. Om Google hade försökt att lösa spelet på samma sätt luffarschack var löst, det skulle ha varit tvungen att granska och rangordna en obscen mängd av möjliga lägen: i ballpark av 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 av dem.
Som gör en uttömmande sökning omöjligt, och även en selektiv sökning, av vilken stil som används av Djupa Blå för att besegra Kasparov, knepigt att köra effektivt.
Lägga till elände för dem som försöker att behärska Gå är att, till skillnad från schack, det är mycket svårt att titta på styrelse-och matematiskt bestämma vem som ska vinna. I schack, en spelare med sin drottning kommer nog slå en spelare vars drottning har fattats, och så vidare: det är möjligt att tilldela värden till dessa bitar, komma med en löpande värdering som ungefär rankas varje spelares förutsättningar. I Går däremot, räknare är sällan bort från brädet, och det finns inga enkla matematiska sätt att avgöra vem som är den starkare position tills spelet är väldigt långt framskridit.
Så AlphaGo fokus på en helt annan strategi. Som David Silver, DeepMind s co-lead forskare i projektet uttrycker det: “AlphaGo blickar framåt genom att spela ut resten av spelet i sin fantasi, många gånger om.” Programmet omfattar två neurala nätverk, programvara som imiterar strukturen i den mänskliga hjärnan att aggregera mycket enkla beslut i komplexa val, som körs parallellt.
En, politiska nätverk, var utbildad genom att observera miljontals skivor av att Gå upp till en online-arkivet. Med hjälp av dessa observationer, att det byggs upp en prediktiv modell där det förväntas nästa stycke spelas, får kunskap av styrelsen och alla tidigare ståndpunkter, som kunde exakt gissa nästa drag av en expert spelare 57% av tiden (jämfört med det tidigare rekordet på 44,4 procent från andra grupper).
Denna “övervakas lärande” var sedan backas upp av en släng av “reinforcement learning”: nätet var som att spela mot sig själv, lära sig från sina segrar och förluster som det utförs mer än 1m enskilda spel under loppet av en dag.
Den politiska nätverk var i stånd att förutsäga sannolikheten för att en viss åtgärd skulle spelas som nästa, men systemet också behövde en andra filter för att hjälpa det att välja vilka av dessa drag var den bästa. Som nätverk, “värde nätverk”, förutspår vinnaren av spelet får varje särskilt styrelsens tillstånd.
Byggnaden AlphaGo är inte bara viktig som en fjäder i DeepMind, cap. Företaget hävdar att finslipa djupt lärande tekniker som detta är av avgörande betydelse för dess framtida arbete. Demis Hassabis, DeepMind grundare, säger att “i slutändan vill vi tillämpa dessa tekniker i viktiga verkliga problem, från medicinsk diagnostik till climate modelling”.
För nu, DeepMind team som är fokuserade på en sista målet på Go-brädet: en match mot Lee Se-dol, världsmästare. Lee säger att “oavsett resultat, kommer det att vara en meningsfull händelse i baduk (den koreanska namn för att Gå) historia. Jag hörde Google DeepMind AI är förvånansvärt stark och blir starkare, men jag är övertygad om att jag kan vinna åtminstone den här gången.”