Idag (15 mars 2016) avslutades en historisk match mellan människa och maskin i det uråldriga brädspelet Go. Det sista av de klassiska spelen som, fram tills idag, dominerats av mänskliga spelare. Efter att Go legenden Lee Sedol gav upp i det sista av fem partier kan vi nu fastställa resultatet i matchen till 4-1 fördel AlphaGo, ett AI utvecklat av Google DeepMind. Matchens vinnare var dock fastställd redan efter AlphaGos tre inledande segrar men Lee Sedol kom tillbaka i fjärde partiet och lyckades med ett briljant spel ta hem ett parti. Detta ledde till spekulationer i huruvida Lee nu hittat datorns svaghet. I sista partiet spelade Lee med ett nytt självförtroende och partiet blev en stenhård kamp till sista stenen. Lee tog tidigt intiativ och såg ut att ha en ledning, men AlphaGo lyckades reducera försprånget, komma ikapp och slutligen besegra Lee i slutskedet av partiet.

Med detta resultat i beaktande kan vi bara konstatera att Go nu är ytterligare en historisk landvinning för artificiell intelligens. Men HUR har AlphaGo åstadkommit denna bedrift? Vill du veta det så är det bara att fortsätta att läsa!

Vad är problemet?

Go är ett spel med perfekt information vars tillstånd är ständigt tillgänglig för båda spelarna, i detta avseende påminner det om tex Schack. För spelaren innebär det att densamma endast behöver beakta spelets nuvarande tillstånd för att beräkna nästa drag optimalt. Denna egenskap kallas för Markovegenskapen och öppnar för en naiv algoritm som helt enkelt simulerar alla möjliga drag, från spelets nuvarande tillstånd till spelets slut, för att sedan välja det drag som med högs sannolikhet leder till vinst. I Go är detta dock problematiskt då spelaren har ca 250 drag att välja på i varje omgång och då spelet består av ca 150 drag i sekvens leder det till ca 250¹⁵⁰ möjliga spel. Ett tal väsentligt större än antalet atomer i universum och över 10²³⁰ gånger fler än schack som “bara” består av ca 35⁸⁰ spel. En sådan naiv algoritm är därför fullständigt hopplös i Go.

Rummet av möjliga utfall är alltså så enormt att det i praktiken kan betraktas som oändligt, vilket också är vad som gör problemet intressant då dom flesta verkliga problem i naturen har denna egenskap (tex bilkörning eller mänsklig dialog). Men om dessa problem är omöjliga, hur löser då människor dessa? Ett vanligt svar på denna fråga skulle kunna vara “Jag använder min intuition”. Men frågar man istället samma person hur dom känner igen att en katt är en katt kanske man får svaret “Jag bara vet!”. Möjligen betyder dessa två svar samma sak, nämligen “Jag använde min välutvecklade förmåga för mönsterigenkänning”. Detta är åtminstone vad Google DeepMind har antagit när dom utvecklade AlphaGo.

Så hur fungerar AlphaGo?

AlphaGo bygger på maskininlärning. Det innebär att ingen har försökt berätta för AlphaGo hur den ska spela, utan datorn har istället själv fått lista ut hur det ska gå till. Detta har den gjort genom att dels studera hur människor spelar Go och dels genom att spela mot sig själv. Erfarenheterna datorn samlat på sig under sina studier använder den sedan under matchen för att guida sin sökning efter ett fördelaktigt drag. Algoritmen kan enkelt delas upp i tre delar. Den första delen kalas för en policy, dess funktion är att föreslå vilka drag en professionell Go spelare skulle överväga. Den andra delen uppskattar sannolikheten att ett visst speltillstånd kommer leda till vinst, givet att båda spelarna spelar optimalt. Och den tredje delen är en sökning efter det optimala draget som använder sig av både policy och värdeuppskattning för att göra sökningen effektiv. Del ett och två kan ses som algoritmens intuition, som tränas upp innan matchen, medan del tre driver spelet under match och använder sig av sin intränade intuition för att söka bland intressanta drag istället för att göra en blind sökning efter en nål i universum.

Policynätverket

Policynätverket är ett convolutional neural network (CNN) som mappar från ett spelbräde till en sannolikhet för varje möjligt drag på det spelbrädet. CNN är en typ av djupt neuralt nätverk (deep learning) som dom senaste åren revolutionerat datorseende och som nu i vissa avseenden är på övermänsklig nivå även i denna domän, tex objektigenkänning. Analogin med Go är att bilden motsvaras av spelbrädet men istället för att beräkna vad som är i bilden beräknar nätet i AlphaGo vilka drag som är intressanta för sökalgoritmen att titta närmare på. Detta har effekten att begränsa bredden på sökningen så att AlphaGo, istället för att överväga runt 250 möjliga drag i varje omgång, kan koncentrera sig på en handfull rimliga drag.

Träningen av policynätverket är i sig implementerat i två steg. I steg ett används en databas av runt 200 000 Go partier spelade av professionella Go spelare. Dessa partier resulterar i ca 30 miljoner träningsexempel bestående av spelbordets konfiguration samt spelarens valda drag givet den konfigurationen. Träningsalgoritmens mål är att försöka lära sig att gissa vilket drag som spelaren faktiskt gjorde. Efter träning lyckas nätverket gissa vilket drag den mänskliga spelaren gjorde i ca 57% av fallen vilket tydligt visar att det bara är ett fåtal drag av de 250 möjliga dragen som en människa faktiskt överväger. I steg två lämnar vi människan bakom oss och fortsätter träningen genom att låta AlphaGo spela mot en variant av sig själv och belöna den version som vinner partiet. Algoritmen kallas för deep reinforcement learning och är en teknik som DeepMind tidigare använt för att lära en dator att spela olika Atari-spel. Genom att träna på detta sättet har AlphaGo möjlighet att mappa ut möjliga spelvägar som inte fanns i träningsdatan vilket öppnar upp för vad man löst kan kalla kreativitet. Tidigt i spel två fick vi se ett exempel på detta när AlphaGo använde sig av en tidigare okänd strategi som starkt bidrog till AlphaGos seger i det partiet.

Värdenätverket

Istället för att utvärdera alla drag, från nuvarande speltillstånd hela vägen till partiets slut, används ett värdenätverk som uppskattar vilken sannolikhet AlphaGo har att vinna från ett specifikt spelbräde. Tekniskt är nätverket väldigt likt policynätverket men tränat på en annan uppgift. Under matchen är värdenätverkets roll att begränsa djupet på sökningen.

Sökning efter det perfekta draget

När det väl är dags för match kommer den sista komponenten i AlphaGo in, vars uppgift är att leta efter det bästa draget. Sökalgoritmen som används heter Monte Carlo tree search och är en algoritm som testar olika möjliga kombinationer av drag i sekvens. Dragen väljs probabilistiskt med hjälp av policynätverket som föreslår drag som är sannolikt bra, och resultatet av en sekvens drag utvärderas med värdenätverket som beräknar vilken sannolikhet för vinst sekvensen resulterar i. Resultatet av varje sekvens som testas antecknas och slutligen väljs det drag som förväntas vara det mest fördelaktiga, baserat på ett stort antal simuleringar. En fördel med denna typ av iterativa sökalgorithm är att AlphaGo kan välja att avbryta sökningen så snart den antingen hittar ett tillräckligt bra drag eller får slut på tid. Monte Carlo tree search hittar alltså direkt en approximativ lösning som sedan för varje simulering förbättras och som slutligen kommer konvergera till den globalt optimala lösningen, visserligen i limiten av oändlig tid.

Slutsatser

Att säga att Go nu är ett löst problem är att gå händelserna i förväg men det är tydligt att vi idag har tagit ett jättekliv åt det hållet. Men något som är helt klarlagt, och ännu intressantare, är att Google DeepMind med AlphaGo har visat att Deep Learning kan användas för att lösa uppgifter av mer generell karaktär, där planering och strategi är en viktig komponent. Detta är något som kan ha långtgående konsekvenser för framtiden inom AI och garanterat kommer att inspirera andra forskare/pionjärer att utforska andra utmanande domäner som tex mänsklig interaktion eller genetik. Framtiden står för dörren och nu är det upp till vår fantasi att bestämma dess gränser! Slutligen kan jag inte låta bli att gratulera Lee Sedol som faktiskt också blev historisk som den första människa som slagit AlphaGo i ett parti, även om han förlorade de övriga fyra.

Mikael Kågebäck, Doktorand i machine learning, Chalmers

Om ni vill läsa mer om AlphaGo och dess inre så kan jag rekommendera DeepMinds nature artikel som även utgör den huvudsakliga källan för denna posten. För en mer populärvetenskaplig beskrivning kan ni istället ta en titt på antingen SVT vetenskap eller NyTeknik. Slutligen, om ni vill se mig prata om detta i TV4Nyheterna så kan ni klicka här.