AlphaGo del 3 - Vägen till AlphaGo Zero – tekniken bakom

AlphaGo del 3 - Vägen till AlphaGo Zero – tekniken bakom

I början av 2016 avslöjades att programmet AlphaGo från Google-ägda DeepMind i oktober 2015 besegrat en professionell Go-spelare utan handikapp. Sedan följde en serie matcher mellan olika versioner av AlphaGo och stadigt bättre mänskliga spelare. Detta inlägget handlar om de olika varianterna av programmet, hur de utvecklades till en version som till slut helt på egen hand lärde sig spelet bättre än någon spelare i historien.

Här kan du läsa del 1, början av historien.

Här kan du läsa del 2, som handlar om de olika matcherna.


Den första versionen av AlphaGo, som besegrade den europeiske mästaren Fan Hui i oktober 2015, var radikalt annorlunda från den sista versionen som DeepMind utvecklade. Denna första version, som kallats AlphaGo Fen, använde sig av en kombination av två neurala nätverk, ett ”policy-nätverk” och ett ”värde-nätverk”, och tränades på tusentals historiska matcher av mänskliga spelare. Beräkningarna utfördes av ett nätverk av datorer som tillsammans använde 176 grafikkort.


Nästa version, AlphaGo Lee, använde förfinade algoritmer och annan hårdvara. Man frångick grafikkorten till förmån för en speciell sorts beräkningskort från Google, så kallade TPUs, Tensor Processing Units. 48 stycken var i bruk, distribuerade över ett nätverk.


AlphaGo Master hade effektiviserats betydligt och krävde bara fyra TPUs för att överträffa tidigare versioner. Det var denna version som gick obesegrad ur en serie onlinematcher mot några av världens bästa spelare, och som spelade mot världens högst rankade spelare Ke Jie i maj 2017 i Kina.


Lärdomar – AlphaGo Teach

Deep Mind har publicerat en webbplats där man kan se hur AlphaGo värderar olika populära öppningssekvenser. Den används nu av Go-spelare för att omvärdera traditionella strategier. Verktyget kallas AlphaGo Teach och du finner det här


AlphaGo Zero

Den 19:e oktober 2017 publicerades en artikel i Nature av teamet bakom AlphaGo. Där beskriver de AlphaGo Zero, en ny och ännu starkare version av programmet. Men det var inte bara starkare, det var helt annorlunda uppbyggt. Där tidigare versioner använde två neurala nätverk, ett ”policy-nätverk” och ett ”värde-nätverk”, har AlphaGo Zero kombinerat dessa till ett vilket lett till ökad effektivitet.

Dessutom startade AlphaGo Zero utan förkunskaper, och därmed utan förutfattade meningar om hur spelet bör spelas. Tidigare versioner hade utgått från historiska partier spelade av människor. Istället prövade det sig fram helt slumpmässigt och spelade mot sig självt, och resultaten användes för att justera algoritmerna så de blev bättre och bättre på att förutse vilka drag som leder till vinst.

Efter bara tre dagars självträning besegrade AlphaGo Zero versionen som vann över Lee Sedol i Korea. Efter 40 dagars självträning var AlphaGo Zero ännu starkare, och besegrade versionen som blivit känd som ”Master” och som besegrat världens bästa mänskliga spelare Ke Jie i Kina.

Det har inte offentliggjorts några matcher mellan mänskliga spelare och AlphaGo Zero, men det besegrar alla tidigare versioner av programmet.

Här är DeepMind’s egen sida där de beskriver AlphaGo Zero.

Den intresserade kan lasta ned deras artikel i Nature som pdf här: Mastering the game of Go without human knowledge. Silver et al. Nature 2017.  


AlphaZero

AlphaZero är en generaliserad variant av algoritmen i AlphaGo Zero, och kan användas även för spel som schack och shogi (japanskt schack). Med 24 timmars träning så klarade den av att slå både det bästa schackprogrammet i världen, Stockfish, och tredagarsversionen av AlphaGo Zero.

En teknik som används av dessa programmen är något som kallas Monte Carlo Search Trees (MCST). AlphaZero gjorde 80000 MCTS-sökningar per sekund mot 70 miljoner för Stockfish. AlphaZero kompenserar för det lägre antalet genom att använda neurala nätverk för att utvärdera vilka varianter som är mest lovande, och fokusera på dessa.

Reaktionerna på AlphaZero var blandade, inklusive en del som ifrågasatte om resultaten var rättvisande när det kom till schack. Danska schackmästaren Peter Heine Nielsen sade till BBC: 

"I always wondered how it would be if a superior species landed on earth and showed us how they played chess. Now I know."

Den intresserade kan lasta ned en förhandsutgåva av artikeln som beskriver AlphaZero här: Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. Silver et al. 2017. 


Länkar till källor och vidare information om AlphaGo

DeepMind's egna sidor om AlphaGo


Videos

The computer that mastered Go - Nature, 2016-01-27.

AlphaGo & Deep Learning - Computerphile, 2016-03-18.

Google's Deep Mind Explained! - Self Learning A.I. - ColdFusion, 2016-05-01.

What did AlphaGo do to beat the strongest human Go player? - Tobias Pfeiffer, Full Stack Fest, 2016-09-14.

AlphaGo Zero: Starting from scratch - DeepMind, 2017-10-18.

AlphaGo Zero: Discovering new knowledge - DeepMind, 2017-10-18.

Artificial Intelligence Starting From a Blank Slate - Chalmers University of Technology, 2017-11-10.


Nyheter och annat

In a huge Breakthrough, Google's AI Beats a Top Player at the Game of Go - Wired, 2016-01-27.

Understanding AlphaGo - Machine Learnings, Mirek Stanek, 2017-03-05.

How the Computer Beat the Go Master - Scientific American, 2016-03-19.

The latest AI can work things out without being taught - The Economist, 2016-10-21.

Secret Test of Google AI Bot Stops Top Go Players - Scientific American, 2017-01-05.

New version of AlphaGo self-trained and much more efficient - American Go E-Journal, 2017-05-24.

AI versus AI: Self-Taught AlphaGo Zero Vanquishes Its Predecessor - Scientific American, 2017-10-18.

Artificial intelligence: Learning to play Go from scratch - Nature 2017-10-18.

Google's New AlphaGo Breakthrough Could Take Algorithms Where No Humans Have Gone - Fortune, 2017-10-19.


Vetenskapliga artiklar

Mastering the game of Go with deep neural networks and tree search – Silver et al., Nature 2016-01-28.

doi:10.1038/nature16961


Where Does AlphaGo Go: From Church-Turing Thesis to AlphaGo Thesis and Beyond - Wang et al., IEEE/CAA Journal of Automatica Sinica, Vol. 3, No. 2, april 2016.

doi: 10.1109@JAS.2016.7471613


The Evolution of Computing – AlphaGo – Jim X. Chen, Computing in Science & Engineering, July/August 2016.

doi: 10.1109/MCSE.2016.74


Mastering the game of Go without human knowledge – Silver et al., Nature 2017-10-19.

doi:10.1038/nature24270


Jie Ke versus AlphaGo: A ranking approach using decision making method for large-scale data with incomplete information – Chao et el., European Journal of Operational Research, Volume 265, Issue 1, 2018-02-16. Preprint.

doi: 10.1016/j.ejor.2017.07.030


Bild: Google