Vědci z Univerzity Karlovy, Českého vysokého učení technického v Praze a Albertské univerzity v Kanadě dosáhli úspěchu na poli umělé inteligence. Mezinárodní tým vyvinul počítačový program DeepStack, který v prosinci 2016 poprvé v historii porazil profesionální hráče v jedné z nejpopulárnějších karetních her na světě – dvouhráčovém no-limit Texas hold’em pokeru. Vědecké objevy, které vedly k tomto výsledku, publikuje Science, jeden z nejprestižnějších vědeckých časopisů. Kompletní vědecká práce [PDF].
DeepStack vytvořil další historický milník, kdy lidé v populárních hrách podlehli počítačům. Po backgammonu, dámě, šachu a go je tedy dalším v pořadí no-limit poker. Oproti předchozím hrám je tu však jeden zásadní rozdíl. Poker byl dlouholetou výzvou pro umělou inteligenci,“ říká Michael Bowling, profesor z Albertské univerzity, který výzkumný tým vedl.
Je to typická hra s neúplnou informací, ve které hráči během hry nemají stejnou informaci a pohled na hru.
Hra s neúplnou informací
Fakt, že hráč nevidí karty oponenta a oponent nevidí jeho karty, dělá problém výrazně složitějším z teoretického hlediska. Na druhou stranu je však tato neurčitost informace v reálném světě běžná. Matematické modely her umožňují popsat situace z ekonomie, aukcí, síťové bezpečnosti, ochrany důležitých cílů nebo kontroly jízdného. V těchto reálných situacích se jednotlivé strany jen velmi zřídka rozhodují na základě úplných a totožných informací. Proto je pokrok v řešení her s neúplnou informací zásadní pro praktické aplikace,“ vysvětluje Michael Bowling.
Část herního stromu, červené a tyrkysové reprezentují hráčovy akce, zelené značí odkryté veřejné karty, listy s žetony reprezentují konec hry
První dva autoři DeepStacku, Martin Schmid a Matej Moravčík z Katedry aplikované matematiky Matematicko-fyzikální fakulty UK, popisují začátky projektu: Jak už to tak v pokeru bývá, velkou roli sehrála náhoda. Při přátelském rozhovoru s profesorem Bowlingem na konferenci v Montrealu slovo dalo slovo a na stole bylo pozvání odjet na rok do Kanady a stát se členy Mikova týmu s odvážným cílem, který se nakonec více než povedl.
Náročnost projektu podtrhuje také fakt, že desetičlenný tým pracoval na projektu téměř rok. Celý Mikův tým je plný skvělých a šikovných lidí, těšíme se na další projekty v rámci tohoto týmu,
shrnuli Martin a Matej.
Další z českých vědců, Viliam Lisý z Centra umělé inteligence na katedře počítačů Fakulty elektrotechnické ČVUT, v té době na Albertské univerzitě již působil v rámci své post-doktorské stáže: Albertská univerzita má jednu z nejvlivnějších výzkumných skupin v oblasti výpočetní teorie her. Když mi Michael Bowling po doktorátu v této oblasti nabídl možnost absolvovat u něj post-doktorskou stáž, rozhodování bylo jednoduché.
Architektura algoritmu DeepStack
Algoritmus DeepStacku je přelomový, protože se nám podařilo přenést myšlenky, které byly klíčové v hrách s úplnou informací, do světa her s neúplnou informaci. Doposud nebylo jasné, zda je podobný přístup vůbec možný,“ říká Schmid. DeepStack umožňuje vypočítat vhodnou strategii pro situaci v pokeru až v momentě, kdy situace nastane, tedy bez nutnosti uvažovat o úplně celé hře předem naráz, což byl doteď převládající přístup.
Strojové učení s formou intuice
Tato zásadní změna principů řešení byla umožněna mimo jiné rozvojem strojového učení pomocí hlubokých neuronových sítí. Tato neuronová síť v případě DeepStacku vyhodnocuje jednotlivé pokerové situace, a jde tedy o jistou formu intuice, kterou algoritmus využívá pro správná rozhodnutí. Podobně jako v případě člověka, musí i DeepStack svoji intuici trénovat hraním mnoha pokerových partií. Naše síť v průběhu učení viděla miliony pokerových situací,“ dodává Moravčík.
Schopnost uvažovat o jednotlivých pokerových situacích až v momentě, když nastanou, je klíčová pro složité hry, jako je no-limit Texas Hold’em, ve kterých může nastat mnohem víc různých situací, než je počet atomů ve vesmíru,
vysvětluje Lisý. I takto složitou hru hraje DeepStack rychleji než lidi. V průměru potřebuje jen tři sekundy „myšlení“ na každé rozhodnutí a funguje i na běžném notebooku s výkonnější grafickou kartou od Nvidie, kterou používá pro své výpočty.
Tabulka ukazuje kvalitativní skok DeepStacku oproti předchozím nejlepším algoritmům. Předchozí programy snadno prohrály mnohem více peněz, než kdyby každou hru zahodily jakoukoliv kartu. Čili není překvapivé, ze byly daleko za lidskou úrovní,
říká Martin Schmid.
DeepStack hrál proti skupině profesionálních hráčů pokeru v prosinci 2016. Třicet tři hráčů vybraných Mezinárodní federací pokeru pocházelo ze sedmnácti států. Každý hráč měl možnost hrát 3 000 her během čtyř týdnů. DeepStack tyto hráče v průměru porazil s obrovskou převahou. Každého z jedenácti hráčů, kteří dohráli všech 3 000 her, porazil i individuálně a pouze v jednom případě výhra nebyla statisticky signifikantní. DeepStack je tedy první počítačový program, který porazil profesionální hráče v dvouhráčovém no-limit Texas hold’em pokeru.
Autoři kód raději nezveřejní
Kód byl implementován ve frameworku Torch7 a při samotné hře běží na jedné grafické kartě NVIDIA GeForce GTX 1080. To proto, aby byl algoritmus velmi rychlý a umožňoval situaci řešit přinejmenším stejně rychle jako to dělá živý hráč. Na vývoj programu a učení sítí jsme měli k dispozici dvacet karet NVIDIA Titan X, jakmile vyšla nová generace, přidali jsme dalších dvacet karet GTX 1080,
vysvětluje Martin Schmid.
Program má přibližně 40 tisíc řádek kódu, ale autoři se ho rozhodli nezveřejnit. V podstatě šlo o kompromis otevřenosti vědy kvůli publikaci a dobré vůle vůči pokerovým hráčům. Nechceme, aby si někdo stáhl program a hrál s nim na internetu o peníze,
řekl Schmid.
Výsledný kompromis je takový, že bude zveřejněn kód pro pokerovou „minihříčku“, na kterém bude možné demonstrovat vlastnosti algoritmu. Nebude ho ale možné jednoduše spustit na internetu proti lidem. Nebude to stejný kód, který jsme použili ve studii proti lidem.
Kód minihry by měl být k dispozici za několik týdnů spolu s tištěným článkem v časopise Science.
ČLÁNKY DO MAILU