Deep Blue (IBM)

Fanoušci logických her si možná vzpomenou na rok 1997, kdy tehdy nejsilnější světový šachista Garri Kasparov prohrál se superpočítačem firmy IBM Deep Blue. Po tomto historickém zápase se pozornost obrátila ke hře go. I přes obrovské nasazení programátorů trvalo dlouhých osmnáct let, než se podařilo vytvořit program, který by se mohl měřit s profesionálními hráči. Až loni v říjnu program AlphaGo překvapivě porazil trojnásobného mistra Evropy a zároveň profesionála Fan Huie z Francie, a to se skóre 5:0. Do té doby i nejsilnější programy hrály pouze na úrovni silných amatérů. Po pěti měsících se program AlphaGo chystá na mnohem silnějšího soupeře. Třiatřicetiletý Lee Sedol je nejúspěšnějším hráčem go posledních více než deseti let. Za svou kariéru vyhrál osmnáct mezinárodních turnajů nejvyšší kategorie, čímž se v historických tabulkách řadí na druhé místo.

AlphaGo - počítačový program vyvinutý firmou Google DeepMind

Hrát se bude opět na pět partií. Vítěz, který bude jasný nejpozději 15. března, si odnese milion dolarů. Tipy odborníků se různí. Mistr Evropy Fan Hui sice zdaleka není tak silný jako Lee Sedol, na druhé straně je otázka, jak moc se AlphaGo dokázal během posledních pěti měsíců zlepšit.

Co je to go?
Go je nejstarší desková hra na světě. Vznikla před 4-5 tisíci let v Číně. Odtud se rozšířila po celé východní Asii, kde je dodnes velmi populární. V posledních desetiletích však získává čím dál více příznivců i v dalších částech světa. Pravidla go jsou velmi jednoduchá a zvládnou je i malé děti: Dva hráči střídavě pokládají na desku své kameny a snaží se ohraničit si co největší území a zároveň obklíčit co nejvíce kamenů soupeře. Hru go hrála nebo hraje celá řada známých osobností. Go uměl například Albert Einstein. Zakladatel firmy Microsoft Bill Gates měl dokonce v mládí cíl stát se nejsilnějším hráčem go na světě. Ze známých Čechů se pak hře go věnuje miliardář a bojovník proti korupci Karel Janeček

AlphaGo (černé kameny) versus  Fan Hui, čtvrtá hra. 8. října loňského roku Fan Hui rezignoval.

Proč je programování go tak složité?
Prvním problémem je počet variant. „Oproti u nás známějšímu šachu má hráč go v každém okamžiku mnohem více možností, jaký udělat další tah. A systematicky probrat všechny možnosti je pro počítač neskonale obtížnější,“ říká Petr Baudiš, odborník na umělou inteligenci a programování go z Fakulty elektrotechnické ČVUT. Zatímco u šachů je počet variant zhruba 10²⁰⁰, u go, které se hraje na desce 19×19 průsečíků, je to 10⁸⁰⁰. Pokud to velmi zjednodušíme, tak na hru go bychom potřebovali 10⁶⁰⁰× rychlejší superpočítač Deep Blue než na šachy (nikoliv čtyřikrát rychlejší, jak by se mohlo na první pohled zdát). To je i přes technický pokrok nepředstavitelné.

Druhým problémem je, že v go je velice obtížné najít algoritmus na správné ohodnocení síly tahu. Jasné lokální vítězství může při celkovém pohledu být ztrátou. Je lepší si naznačit malé jisté území, nebo velké nejisté? Jaké slabiny nebo naopak silné stránky bude položený kámen mít třeba za 50 nebo 100 tahů? Velkou roli při těchto hodnoceních hrají zkušenost a intuice hráče. Navíc lidský mozek má schopnost rychle a poměrně přesně odfiltrovat vyloženě špatné tahy. První plně funkční počítačový program hrající go vznikl již v roce 1968. Od té doby bylo představeno několik set dalších programů. Byly vypsány finanční odměny, např. pro autory programu, který jako první porazí profesionála. Přesto výsledky až do minulého roku zůstávaly daleko za očekáváním.

Lee Sedol Go je poslední logickou hrou, u níž se i přes desítky let trvající snahu nedařilo vymyslet způsob, jak mají počítače člověka porazit. Až nyní to vypadá, že by mohl i tento milník umělé inteligence být překonán. Zvítězí počítač nad nejlepším hráčem světa ve hře go? (Kredit: senseis.xmp.net)

Řešení: hluboké neuronové sítě a Monte Carlo
Je jasné, že běžnými programátorskými postupy je go neřešitelný oříšek. Velký krok kupředu znamenala až aplikace tzv. hlubokých neuronových sítí a metody Monte Carlo. Neuronové sítě svým způsobem imitují lidský mozek. V umělé inteligenci se používají k řešení úloh, které jsou běžnými postupy neřešitelné, případně velmi obtížně, např. rozpoznávání lidí na fotografii. Přitom člověk v řadě případů tyto úlohy řeší bez velkých obtíží. Hluboké neuronové sítě navíc mají tu výhodu, že dokáží učit samy sebe.

„Tým kolem programu AlphaGo používá neuronové sítě podobné třeba těm, kterými Facebook rozpoznává tváře nebo které stojí za chytřejším hledáním obrázků na internetu. Tento nápad neměl Google jako první, ovšem doteď se neuronové sítě učily pouze z cizích mistrovských partií. I člověk se ovšem ze svých vlastních chyb naučí více než při sledování hry jiných a tým z výzkumné společnosti DeepMind vlastněné Googlem vymyslel nový způsob, jakým se neuronová síť dokáže učit z partií, které sama odehrála – to, spolu s použitím obrovského výpočetního výkonu Googlu na naučení herního algoritmu, může za poslední průlom v herní síle,“ popisuje Petr Baudiš.

Velký krok kupředu znamenalo i nasazení matematické metody stromového prohledávání nazvané Monte Carlo zhruba před deseti lety. Tato metoda je známa už od 40. let 20. století a byla původně používána např. při vývoji jaderných zbraní. Ve hře go její nasazení vypadá tak, že pro každý neuronovou sítí předvybraný tah partii náhodně mnohokrát dohraje. A poté vyhodnotí statisticky nejúspěšnější tah. Přestože tato metoda v souvislosti s go vypadá velmi primitivně a fádně, znamenala velký pokrok kupředu

Josef Moudřík

Právě spojení těchto dvou metod je klíčem k síle programu AlphaGo. Hluboké neuronové sítě mají schopnost rozlišit dobré a špatné tahy nebo vyhrávající a prohrávající pozice. V tomto ohledu pracují podobně jako vizuální intuice silných hráčů. Metoda Monte Carlo sice nemá žádné podobné specifické znalosti hry, které člověk používá k odfiltrování špatných tahů, je ale zase velmi dobrá k prohledávání velkého množství kombinací. „Spojením obou technik je AlphaGo schopné dobře prohledávat relevantní varianty a dostatečně brzy rozpoznat, která varianta vede k výhře a která k prohře,“ říká Josef Moudřík z Matematicko-fyzikální fakulty Univerzity Karlovy, další z českých odborníků na programování hry go.

Je důležité dodat, že programování go není úplně samoúčelné. Právě jeho složitost, kde není možné pouhé „hrubé“ prohledávání, ale je potřeba si vypomáhat vizuální intuicí a abstraktním myšlením, z něj dělá ideální pole pro výzkum umělé inteligence. „Vyvinuté algoritmy – ať již jde o prohledávání, hluboké neuronové sítě nebo sebezdokonalovací programy – mají široké pole aplikací: od robotiky a samohybných vozidel, přes porozumění obsahu z obrazu, videa a textu, automatického překladu textů až třeba k aplikacím v medicíně,“ dodává Josef Moudřík.

Podrobnější informace na stránce DeepMind a České asociace go

Literatura:

David Silver et al.: „Mastering the game of Go with deep neural networks and tree search“, Nature 529, 484–489 (28 January 2016) doi:10.1038/nature16961

Video: Pravidla hry během 15 minut

Základní lekce