O.S.E.L. - Hravá umělá inteligence: Chinook, AlphaGo, Liberatus
 Hravá umělá inteligence: Chinook, AlphaGo, Liberatus
Jaký je rozdíl mezi dámou, šachami, go a pokerem z hlediska počítačových programů a co k tomu může říct umělá inteligence? Strojové učení a neuronové sítě se dostávají do módy, triumfují nad člověkem stále častěji. A navíc ještě o hře kámen-nůžky-papír.

Marvin Minsk. Vědec zabývající se umělou inteligencí. Byl spoluzakladatelem laboratoře umělé inteligence na MIT a autorem několika filosofických textů. Roku 1969 obdržel Turingovu cenu, nejprestižnější ocenění v oblasti informatiky. (Kredit: Sethwoodworth, Wikipedia, CC BY 3.0
Marvin Minsk. Vědec zabývající se umělou inteligencí. Byl spoluzakladatelem laboratoře umělé inteligence na MIT a autorem několika filosofických textů. Roku 1969 obdržel Turingovu cenu, nejprestižnější ocenění v oblasti informatiky. (Kredit: Sethwoodworth, Wikipedia, CC BY 3.0

Zatímco na počátku loňského roku počítač AlphaGo zvítězil nad nejlepším lidským hráčem v Go, nyní podle všeho definitivně končí éra lidské převahy v pokeru. Tento obor je dnes v kurzu – natolik, že jím přímo přetékají marketingová oznámení, analýzy a prognózy (10 spotřebitelských trendů pro rok 2017: AI a virtuální realita - Ericsson , Top 10 technologických trendů pro rok 2017 - Gartner).

 

SPUSTIT  VIDEO
AlphaGo: všechno co uděláte, je špatně…
AlphaGo: všechno co uděláte, je špatně…

Stejně tak se do módy dostalo vše zmiňovat i související strojové učení a neuronové sítě. Přitom tyto technologie existují už hrozně dlouho. Takový loni zemřelý Marvin Minsky, považovaný za jednoho z otců umělé inteligence vůbec, první neuronovou síť zkonstruoval již v roce 1951 a v roce 1969 podle svých odpůrců výzkum kolem neuronových sítí zase málem pohřbil, když z toho, že jednovrstvá neuronová síť se neumí vypořádat s funkcí XOR, vyvozoval mnohem obecnější fakta o (ne)schopnosti těchto systémů. Pak skoro 20 let trvalo, než jako odpověď na Minského argumenty byla objevena metoda backpropagation, obor znovu přišel do módy, ale v rámci akademické vědy. Ze vzpomínek dalšího pamětníka, tentokrát mě osobně: Ve 2. polovině 90. let byly v počítačové publicistice neuronové sítě příkladem tématu tak zoufale nepřitažlivého a bez praktického dopadu, že se příslušné nabízené články málem rovnou vyhazovaly a autorům doporučovalo, ať si všímají nějakých sexy témat zajímavých i pro čtenáře, třeba Internetu. Časy se prostě mění, jinak by ostatně technologie ani nebyly zajímavé.

 

 

Lee Se-dol, jihokorejský profesionální hráč Go výkonostní třídy 9. dan. (Kredit Cyberoro ORO, Wikipedia, CC BY 3.0)
Lee Se-dol, jihokorejský profesionální hráč Go výkonostní třídy 9. dan. (Kredit Cyberoro ORO, Wikipedia, CC BY 3.0)

 

V následujícím textu se přidržíme her, zcela pomineme minimálně jednu velmi zajímavou oblast současné AI, a to sice zpracování přirozeného jazyka (chatboty/digitální asistenti, počítačové překladače), na což snad dojde někdy jindy. I tak se už text bude rozbíhat mnoha směry a odbočkami, řada věcí jsou spíše poznámky a i samotný pojem umělá inteligence se v dalším textu používá poněkud vágně.

 

Kapitola 1: dáma

Někteří příznivci dámy tvrdí, že tato hra je inteligentnější než šachy, čistí, s jednoduššími pravidly a tudíž víc závislá na lidské inteligenci a porozumění. Naopak v šachách je ve hře tolik možností, že jde spíše o to v chaosu zrovna něco nepřehlédnout, důležitější je pozornost než porozumění. Takže by pro počítačové programy, které pochopitelně takto „nepřehlížejí“, měla být dáma obtížnější? Jak se však ukázalo, je zase příliš omezená.

V případě dámy se programu prostě podařilo obsáhnout celý stavový prostor hry (samozřejmě si to bylo stejně nutné nějak chytře zjednodušovat, kontrolovat proti databázi pozic s již známým výsledkem, brát v úvahu symetrie...). Ukázalo se, že dáma skončí vždy remízou. V roce 2007 se tak program Chinook stal prokazatelně neporazitelným. Ne že bych se orientovat v různých verzích dámy, ale předpokládám, že to bude cca stejné, jak co do počítačové zvládnutelnosti, tak i výsledku.

Matlab

Chinook bychom do umělé inteligence zařadili stěží. Ne že by tím ale přitažlivost dámy pro tuto disciplínu nutně vyčerpávala. Vezměte si takovou pitomou hru kámen-nůžky-papír. Stačí generátor náhodných čísel a neprohrajete, jistě, co ale když chcete (statisticky) vyhrát proti člověku (který podvědomě alespoň částečně sleduje určitý systém, nehraje náhodně)? Musíte nějak projít soupeřovu strategii a adaptovat se na ni, takové programy existují a jsou proti lidem úspěšně (a samozřejmě – protože samy nehrají náhodně, jsou už zase porazitelné). Některé z nich by se možná do kategorie umělé inteligence zařadit daly.

 

Jak to souvisí s dámou? Program znalý stavového prostoru hry neudělá chybu a dokáže chyb soupeře plně využít, dokáže ho k chybám ale i přimět? Úspěšnější proti omylným lidem by tak mohl být program, který by hrál různě proti různým lidem na základě jejich předešlých partií, snažil se jim maximálně klást léčky apod.

 

Kapitola 2: šachy

Zde hrubá síla stačila rovněž, a to i když se celý stavový prostor hry obsáhnout nepodařilo. Někteří soudí, že k tomu může dojít tak po roce 2060, podle jiných nikdy.

(Zato máme k dispozici různé databáze koncovek, jejichž prostor zmapován je. Hrát si s těmito databázemi je mimochodem fascinující, i když samozřejmě jen pro šachisty. Takže 2 střelci proti jezdci vyhrávají, věž a střelec proti věži není zase zrovna tak jednoduchá remíza, dvě lehké figurky lze různě stavět tak, aby remizovaly proti dámě, dáma a spojení pěšci na 2 krajních sloupcích proti dámě bývá kupodivu remis. Opravdová lahůdka je pak podle mě věž a jezdec proti dvěma jezdcům, kdy některé pozice jsou vyhrané, jiné velmi podobné ne, ale zdali se v tom dá dobrat nějakého obecnějšího poučení...)

V počátcích vývoje šachových programů existovaly vedle sebe dva přístupy, jeden snažící se napodobovat lidské uvažování o šachách, druhý v podobě hrubé síly. Tento přístup dosahoval podstatně lepších výsledků, a to i když tyto šachové programy narazí ve strašlivě se větvícím prostoru variant samozřejmě na své limity (dané především množstvím času, po který je necháme počítat).

Na nejlepší lidské hráče stačí hrubá výpočetní síla i bez toho, že by takový program byl neomylný; stačí výkonný hardware, kvalitní prořezávání větví stromu možností a především pak neustále zdokonalovaný systém, který dokáže vyhodnotit pozice v dosažitelné hloubce propočtu, pak je seřadit dle výhodnosti a podle toho zvolit pokračování. Takové šachové programy opět nejsou nijak inteligentní – v tom smyslu, že jsou strašně jednoúčelové, nedají se (asi) použít pro nic jiného než zase jen pro šachy. V některých ohledech nám dokonce přijdou hloupé a existují speciální typy pozic, s nimiž si dnešní programy neporadí, nicméně toto množství stále klesá. Už asi 12 let nejsou zápasy mezi nejlepšími lidskými hráči a programy zajímavé, nicméně člověk zde ještě úplně zbytečný není. Takový mistr světa s určitým programem hraje stále lépe než tento program sám o sobě.

A mimochodem, protože šachové programy neobsáhly celý prostor hry, tak pochopitelně nevíme ani to, zda šachy bez chyby jsou remiz jako v případě dámy. Předpokládáme, že ano, výhoda bílých figur není k výhře dostačující, ale to je opravdu jen taková nejistá extrapolace.

 

VIDEO:  Libratus

 

Kapitola 3: Go

Dostáváme se ke Go. I zde zastánci hry podobně jako u dámy tvrdí, že je „inteligentnější“ než šachy, protože v ní jde ne tolik o počítání, ale o rozpoznávání vzorů (obecných struktur). Podobný přístup jako u šachů zde nepřinášel zvláštní výsledky, i když to může být dáno i jinými faktory než samotnou hrou – třeba programátoři prostě věnovali více svého času šachům.

Počátkem loňského program AlphaGo vyvinutý v Googlu konečně vyhrál nad mistrem světa Lee Se-dol (Sciencemag.cz), čímž je podle všeho vymalováno i zde. Nezdá se pravděpodobné, že by se lidé dokázali stylu motorů přizpůsobit a prvenství jim opět uzmout (v šachách se objevily úvahy o hráčích specializovaných na počítače, ale to by mělo stejně smysl jen v situacích, kdo by člověk dostával dopředu nějakou výhodu).

Vlastně vše, co k úspěchu programu lze dodat, bylo již řečeno výše. Go se podobá šachům velikostí stavového prostoru (dnes neobsáhnutelný), dámě zase důrazem na geometrické vzory bez zahlcení hromadou dalších subpravidel, prostě jakousi minimalistickou elegancí. Programy tedy zřejmě dokáží vnímat i eleganci. (Nakolik můžeme říct, že zatímco šachový program prostě počítá, AlphaGo chápe Go podobně jako lidský hráč? To by se chtělo podívat, jakou podobu mají abstraktnější struktury používané v rámci programu.)

Zajímavé je, zda teď, když už víme, že to jde v Go, by podobný přístup nešlo oživit i v šachách. V roce 2015 se objevil program Giraffe, což měl být experimentální pokus o zavedení metod umělé inteligence i do šachů, kdy software např. různé varianty počítal do různé hloubky, rozpoznával obecné vzory podobě jako lidští šachisté („izolovaný pěšec“, „sedmá řada“, „špatný střelec“), nehrál ovšem na nijak vrcholné úrovni a pak už o něm nikdo neslyšel, respektive autor práce přerušil, i když pro případné zájemce je kód k dispozici. A pokud AI porazí lidské šachisty, stále zde bude zbývat prostor pro střet programů AI s těmi, které využívají hrubou sílu?

(Samozřejmě stavět do protikladu přístupy pomocí výpočetní síly a inteligence úplně neodpovídá realitě. Faktem je, že i pokrok v oblasti neuronových sítí/strojového učení je do značné míry výsledkem ne toho, že bychom vymýšleli chytřejší algoritmy, ale že nám toho víc umožňuje hardware, viz třeba Matlab R2016a, kdy se vícevrstvé neuronové sítě staly už loni součástí zcela standardního, masově používané produktu, Matlabu https://sciencemag.cz/matlab-nabizi-strojove-uceni-pomoci-vicevrstvych-neuronovych-siti/).

 

Kapitola 4: Poker

Aktuálně přichází zprávy, že program Libratus drtí nejlepší lidské hráče v pokeru (Sciencemag.cz). Jde o variantu Heads-Up, No-Limit Texas Hold’em, prý počítačově obzvlášť obtížně zvládnutelnou.

Pokeru nerozumím vůbec, hrál jsem naposledy před 18 lety, takže následující spekulace by jistě mohl doplnit někdo povolanější. Jak se liší třeba přístup umělé inteligence k pokeru a go? Předpokládám, že AlphaGo hraje stále „nejlepší tahy“, tj. nijak neanalyzuje, kdo zrovna stojí proti ní, nevymýšlí nějaké záměrné léčky („co by asi tak člověk mohl přehlédnout“). Libratus má naproti tomu nejen počítat, ale i blufovat a navíc analyzuje vlastní partie a zlepšuje se (určitě se dá dohledat, zda to dělá AlphaGo; u brute force šachových programů parametry přirozeně ladí programátoři ručně). Ve stejné situaci volí slušnější lidský i umělý hráč pokeru různé možnosti, protože zde je samozřejmě klíčové být nepředvídatelný. Nelze uplatňovat žádnou ve hře jiného typu racionální strategii typu „mám-li horší než průměrné karty, nebudu zvyšovat sázky“. Když už, pak optimalizace zní „mám-li o tolik a tolik horší než průměrné karty, nebudu zvyšovat sázky s pravděpodobností x“. Tah se pak vybere podle generátoru náhodných čísel. Tento analytický přístup sám o sobě by ovšem sotva stačil. Jak vidno, dostáváme k umělé inteligenci nejvyšší úrovně i prvky onoho stupidního kámen-nůžky-papír. Výsledkem je pak program velmi obecný, prý použitelný všude tam, kde se hraje s neúplnými informacemi, ať už jde o data (karty) nebo další algoritmy (strategie protihráčů). Libratus by pak po úpravě byl ideálním vojevůdcem do bitvy i pro obchodní vyjednávání.

Související diskuse viz též odkaz výše.


Autor: Pavel Houser
Datum:30.01.2017