Varför neurala nätverk ser ut att slå de bästa Human Go-spelarna för första gången

Datorer börjar snabbt överträffa människor på mer eller mindre alla områden av strävan. Till exempel avslöjade maskinseendeexperter nyligen en algoritm som överträffar människor i ansiktsigenkänning. Liknande algoritmer börjar också matcha människor vid objektigenkänning. Och mänskliga schackspelare gav för länge sedan upp kampen för att slå datorer.

Men det finns ett område där människor fortfarande triumferar. Det är att spela det gamla kinesiska spelet Go. Datorer har aldrig bemästrat detta spel. De bästa algoritmerna uppnår bara skicklighetsnivån hos en mycket stark amatörspelare som de bästa mänskliga spelarna lätt överträffar.

Det ser ut att förändras tack vare Christopher Clarks och Amos Storkeys arbete vid University of Edinburgh i Skottland. Dessa killar har tillämpat samma maskininlärningstekniker som har förvandlat ansiktsigenkänningsalgoritmer till problemet med att hitta nästa drag i ett spel Go. Och resultaten lämnar lite hopp om att människor kommer att fortsätta att dominera detta spel.

Kort sagt, Go är ett spel för två spelare som vanligtvis spelas på ett 19 x 19 rutnät. Spelarna placerar omväxlande svarta och vita stenar på rutnätet i ett försök att sluta uppta mer av brädet än deras motståndare när spelet är slut. Spelare kan ta bort motståndarens stenar genom att omge dem med sina egna.

Experter tror att det finns två anledningar till att datorer har misslyckats med att bemästra Go. Den första är det stora antalet drag som är möjliga i varje skede av spelet. Go-spelare har 19 x 19 = 361 möjliga startdrag och det finns vanligtvis hundratals möjliga drag när som helst i spelet. Däremot är antalet drag i schack vanligtvis cirka 50.

Det andra problemet är att datorer har svårt att utvärdera styrkorna och svagheterna i en styrelsepost. I schack ger man en rimlig indikation på styrkan i en spelares position om man bara lägger ihop värdet av varje pjäs som finns kvar på brädet. Men detta fungerar inte i Go. Att räkna antalet stenar varje spelare har är en dålig indikator på vem som vinner, säger Clark och Storkey.

Sättet som toppmoderna Go-algoritmer löser detta problem är att spela ut hela spelet efter varje drag och att göra detta på många olika sätt. Om datorn vinner i de flesta av dessa spel anses det draget vara bra.

Det är klart att detta är en tidskrävande och beräkningsintensiv uppgift. Trots det misslyckas den i allmänhet med att slå mänskliga Go-experter som vanligtvis kan utvärdera tillståndet för en Go-bräda med lite mer än en blick.

Många experter tror att hemligheten bakom människans Go-playing-mästarskap är mönsterigenkänning - förmågan att upptäcka styrkor och svagheter baserat på formen som stenarna gör snarare än genom att se flera drag framåt.

Det är därför som de senaste framstegen inom algoritmer för mönsterigenkänning kan hjälpa datorer att göra mycket bättre. Dessa framsteg har använt massiva databaser med bilder för att träna djupa konvolutionella neurala nätverk för att känna igen objekt och ansikten med den typ av noggrannhet som nu matchar mänsklig prestation. Så det är rimligt att föreställa sig att samma typ av tillvägagångssätt kan göra stor skillnad för den automatiska utvärderingen av Go-brädor.

Och det är precis vad Clark och Storkey har gjort. Frågan som dessa killar har tränat ett djupt konvolutionellt neuralt nätverk att besvara är: med en ögonblicksbild av ett spel mellan två Go-experter, är det möjligt att förutsäga nästa drag i spelet?

Sättet de har närmat sig detta är att använda en stor databas med Go-spel för att träna ett neuralt nätverk för att hitta nästa drag. Clark och Storkey använde över 160 000 spel mellan experter för att skapa en databas med 16,5 miljoner positioner tillsammans med deras nästa drag. De använde nästan 15 miljoner av dessa positionsrörelsepar för att träna ett åttalagers konvolutionellt neuralt nätverk för att känna igen vilket drag dessa expertspelare gjorde härnäst. Detta var en process som tog flera dagar.

De använde sedan resten av datamängden för att testa det neurala nätverket. Med andra ord presenterade de nätverket en styrelseposition från ett spel och bad det välja nästa drag. Clark och Storkey säger att det utbildade nätverket kunde förutsäga nästa drag upp till 44 procent av tiden och överträffade tidigare toppmoderna på denna uppgift med betydande marginaler.

Det är intressant inte minst eftersom det nya tillvägagångssättet inte använder några av de tidigare dragen för att fatta sitt beslut; inte heller utvärderar den framtida positioner.

Efter att ha tränat det neurala nätverket spelade Clark och Storkey det sedan mot två av de bästa Go-algoritmerna som finns. Den första heter GNU Go, som spelar på en nivå som motsvarar en medelamatör med en ranking på 6-8 kyu. (Go-rankingen sträcker sig från en nybörjare med en ranking på 30-20 kyu till en professionell expert med en ranking på 1 kyu).

Det andra var ett toppmodernt program som heter Fuego 1.1, som har en ranking på cirka 5-4 kyu. En mänsklig spelare skulle vanligtvis ta många års studier för att nå denna nivå.

Resultaten tyder tydligt på att skriften finns på väggen för mänskliga Go-spelare. Clark och Storkeys neurala nätverk slog GNU Go nästan 90 procent av tiden i en serie av 200 spel. Med andra ord, efter några dagars träning kunde det neurala nätet slå GNU Go konsekvent.

Mot Fuego 1.1 gick det mindre bra och vann bara drygt 10 procent av sina matcher. Ändå är det en betydande prestation. Att kunna vinna ens ett fåtal matcher mot denna motståndare tyder på att en hög grad av skicklighet förvärvades, säger Clark och Starkey.

Det är helt klart mycket lovande. Även om nätverken spelar med en 'nollstegs se framåt'-policy och använder en bråkdel av beräkningstiden som sina motståndare, kan de fortfarande spela bättre än GNU Go och ta några spel från Fuego, säger de.

Och det finns helt klart förbättringspotential, till exempel genom att kombinera detta tillvägagångssätt med andra som använder tidigare drag och ser framåt. En idé som Clark och Starkey föreslår är att köra det konvolutionella neurala nätverket parallellt med det konventionella tillvägagångssättet för att hjälpa till att beskära trädet av möjliga rörelser som behöver utforskas.

Det finns inget förslag från Clark och Storkey att detta tillvägagångssätt kommer att slå de bästa Go-spelarna i världen. Men visst är det bara en tidsfråga innan ens Go-spelare kommer att behöva böja sig för sina datoriserade överherrar.

Ref: arxiv.org/abs/1412.3409 : Lär ut djupa konvolutionella neurala nätverk att spela Go

Dölj