Deep Learning Machine lär sig schack på 72 timmar, spelar på internationell mästarnivå

Det har gått nästan 20 år sedan IBM:s Deep Blue superdator slog den regerande världsmästaren i schack, Garry Kasparov, för första gången enligt vanliga turneringsregler. Sedan dess har schackspelande datorer blivit betydligt starkare, vilket lämnar de bästa människorna små chanser även mot en modern schackmotor som körs på en smartphone.

Men medan datorer har blivit snabbare, har hur schackmotorer fungerar inte förändrats. Deras makt är beroende av brute force, processen att söka igenom alla möjliga framtida drag för att hitta den bästa nästa.

Naturligtvis kan ingen människa matcha det eller komma någonstans i närheten. Medan Deep Blue sökte omkring 200 miljoner positioner per sekund, sökte Kasparov förmodligen inte mer än fem i sekunden. Och ändå spelade han på i princip samma nivå. Det är uppenbart att människor har ett trick i rockärmen som datorer ännu inte bemästrat.

Det här tricket är att utvärdera schackpositioner och begränsa de mest lönsamma sökvägarna. Det förenklar beräkningsuppgiften dramatiskt eftersom den beskär trädet av alla möjliga rörelser till bara några få grenar.

Datorer har aldrig varit bra på detta, men idag förändras det tack vare Matthew Lais arbete vid Imperial College London. Lai har skapat en artificiell intelligensmaskin som heter Giraffe som har lärt sig att spela schack genom att utvärdera positioner mycket mer som människor och på ett helt annat sätt än konventionella schackmotorer.

Direkt ur lådan spelar den nya maskinen på samma nivå som de bästa konventionella schackmotorerna, av vilka många har finjusterats under många år. På mänsklig nivå motsvarar det FIDEs internationella mästarstatus, vilket placerar den bland de 2,2 procenten av turneringsschackspelarna.

Tekniken bakom Lais nya maskin är ett neuralt nätverk. Detta är ett sätt att bearbeta information inspirerad av den mänskliga hjärnan. Den består av flera lager av noder som är sammankopplade på ett sätt som förändras när systemet tränas. Denna träningsprocess använder massor av exempel för att finjustera anslutningarna så att nätverket producerar en specifik utdata med en viss input, för att känna igen närvaron av ansikte i en bild, till exempel.

Under de senaste åren har neurala nätverk blivit enormt kraftfulla tack vare två framsteg. Den första är en bättre förståelse för hur man finjusterar dessa nätverk när de lär sig, delvis tack vare mycket snabbare datorer. Det andra är tillgången till massiva kommenterade datauppsättningar för att träna nätverken.

Det har gjort det möjligt för datavetare att träna mycket större nätverk organiserade i många lager. Dessa så kallade djupa neurala nätverk har blivit enormt kraftfulla och överträffar nu rutinmässigt människor i mönsterigenkänningsuppgifter som ansiktsigenkänning och handskriftsigenkänning.

Så det är ingen överraskning att djupa neurala nätverk borde kunna upptäcka mönster i schack och det är precis det tillvägagångssätt som Lai har tagit. Hans nätverk består av fyra lager som tillsammans undersöker varje position på tavlan på tre olika sätt.

Den första tittar på spelets globala tillstånd, som antalet och typen av pjäser på varje sida, vilken sida som ska flyttas, kasträttigheter och så vidare. Den andra tittar på bitcentrerade funktioner som platsen för varje bit på varje sida, medan den sista aspekten är att kartlägga de rutor som varje bit attackerar och försvarar.

Lai tränar sitt nätverk med en noggrant genererad uppsättning data hämtade från riktiga schackspel. Denna datamängd måste ha korrekt fördelning av positioner. Till exempel är det inte vettigt att träna systemet på positioner med tre damer per sida, eftersom dessa positioner praktiskt taget aldrig kommer upp i faktiska spel, säger han.

Den måste också ha många olika ojämlika positioner utöver de som vanligtvis förekommer i schackspel på högsta nivå. Det beror på att även om ojämlika positioner sällan uppstår i riktiga schackspel, dyker de upp hela tiden i de sökningar som datorn utför internt.

Och denna datamängd måste vara enorm. Det enorma antalet anslutningar inuti ett neuralt nätverk måste finjusteras under träning och detta kan bara göras med ett stort dataset. Använd en datauppsättning som är för liten och nätverket kan hamna i ett tillstånd som inte känner igen den stora mängd mönster som förekommer i den verkliga världen.

Lai genererade sin datauppsättning genom att slumpmässigt välja fem miljoner positioner från en databas med datorschackspel. Han skapade sedan större variation genom att lägga till ett slumpmässigt lagligt drag till varje position innan han använde den för träning. Totalt genererade han 175 miljoner positioner på detta sätt.

Det vanliga sättet att träna dessa maskiner är att manuellt utvärdera varje position och använda denna information för att lära maskinen att känna igen de som är starka och de som är svaga.

Men det här är en enorm uppgift för 175 miljoner tjänster. Det kunde göras av en annan schackmotor men Lais mål var mer ambitiöst. Han ville att maskinen skulle lära sig själv.

Istället använde han en bootstrapping-teknik där Giraffe spelade mot sig själv med målet att förbättra sin förutsägelse av sin egen utvärdering av en framtida position. Det fungerar eftersom det finns fasta referenspunkter som i slutändan avgör värdet på en position – om spelet senare vinner, förloras eller oavgjorts.

På så sätt lär sig datorn vilka positioner som är starka och vilka som är svaga.

Efter att ha tränat Giraffe är det sista steget att testa den och här blir resultatet intressant läsning. Lai testade sin maskin på en standarddatabas som heter Strategic Test Suite, som består av 1 500 positioner som är valda för att testa en motors förmåga att känna igen olika strategiska idéer. Till exempel testar ett tema förståelsen för kontroll av öppna filer, ett annat testar förståelsen för hur biskops och riddares värderingar förändras i förhållande till varandra i olika situationer, och ytterligare ett annat testar förståelsen av centrumkontroll, säger han.

Resultaten av detta test får 15 000 poäng.

Lai använder detta för att testa maskinen i olika skeden under utbildningen. När bootstrapping-processen börjar når Giraffe snabbt en poäng på 6 000 och når slutligen en topp på 9 700 efter bara 72 timmar. Lai säger att det matchar de bästa schackmotorerna i världen.

[Det] är anmärkningsvärt eftersom deras utvärderingsfunktioner alla är noggrant handdesignade giganter med hundratals parametrar som har justerats både manuellt och automatiskt under flera år, och många av dem har arbetats på av mänskliga stormästare, tillägger han.

Lai fortsätter med att använda samma typ av maskininlärningsmetod för att bestämma sannolikheten för att ett givet drag sannolikt är värt att fortsätta. Det är viktigt eftersom det förhindrar onödiga sökningar i olönsamma grenar av trädet och dramatiskt förbättrar beräkningseffektiviteten.

Lai säger att detta probabilistiska tillvägagångssätt förutsäger det bästa draget 46 procent av gångerna och placerar det bästa draget i sin topp tre-ranking, 70 procent av gångerna. Så datorn behöver inte bry sig med de andra rörelserna.

Det är intressant arbete som representerar en stor förändring i hur schackmotorer fungerar. Det är inte perfekt, naturligtvis. En nackdel med Giraffe är att neurala nätverk är mycket långsammare än andra typer av databehandling. Lai säger att Giraffe tar ungefär 10 gånger längre tid än en konventionell schackmotor för att söka samma antal positioner.

Men även med denna nackdel är den konkurrenskraftig. Giraffe kan spela på samma nivå som en FIDE International Master på en modern mainstream-PC, säger Lai. Som jämförelse spelar toppmotorerna på superstormästarnivå.

Det är fortfarande imponerande. Till skillnad från de flesta schackmotorer som finns idag, hämtar Giraffe sin spelstyrka inte från att kunna se väldigt långt fram, utan från att kunna utvärdera knepiga positioner exakt, och förstå komplicerade positionsbegrepp som är intuitiva för människor, men som har varit svårfångade för schack motorer under lång tid, säger Lai. Detta är särskilt viktigt i öppnings- och slutspelsfasen, där det spelar exceptionellt bra.

Och detta är bara början. Lai säger att det borde vara enkelt att tillämpa samma tillvägagångssätt på andra spel. En som sticker ut är det traditionella kinesiska spelet Go, där människor fortfarande har en imponerande fördel gentemot sina kiselkonkurrenter. Kanske Lai kan få en spricka på det härnäst.

Ref: arxiv.org/abs/1509.01549 : Giraffe: Använder Deep Reinforcement Lär dig spela schack

Dölj