Klávesové zkratky na tomto webu - základní­
Přeskočit hlavičku portálu


Programátoři pokořili poker. Mohli vydělat miliony, vybrali si Science

  12:41aktualizováno  15:10
Karetní hra Poker Texas Hold’em je pro počítače neobyčejně náročná. Ještě nedávno měli nejlepší hráči nad počítačovými programy navrch. Letos to přestalo platit. I díky českým programátorům, kteří v článku pro Science popsali svou inovativní umělou inteligenci DeepStack.
Jak jsme (v jedné hře) porazili DeepStack, nejlepší pokerovou AI

Jak jsme (v jedné hře) porazili DeepStack, nejlepší pokerovou AI

„Teď se musíte jen rozhodnout, jestli dorovnáte, nebo přihodíte,” vysvětluje nám programátor Viliam Lisý a ukazuje na obrazovku, kde vidíme graficky velmi jednoduchý náčrt hráčského stolu, hrací žetony a dvě otočené karty. Mým soupeřem je počítač v Kanadě, kde běží program DeepStack, v současnosti zřejmě nejlepší umělá inteligence specializující se na poker Texas Hold’em No Limit.

Zkusíme blafovat a navýšíme sázku o 400 dolarů. Následuje osmisekundová prodleva. „To jsem zvědavý,” čeká na výsledek programátor Matej Moravčík. Přestože patří mezi hlavní autory programu DeepStack, nedokáže odhadnout, jak umělá inteligence zareaguje. Počítač na kanadské University of Alberta totiž pečlivě propočítává miliony alternativ a na základě natrénované neuronové sítě se „intuitivně” snaží odhadnout, jak na naši sázku odpovědět.

Jednu hru jsme vyhráli. Pokud bychom hráli déle, narazili bychom...

„Tak jste ho vyblafoval!” směje se Martin Schmid, třetí z programátorů, kteří nám na pražské Matematicko-fyzikální fakultě pokerovou umělou inteligenci předvedli. „Super, jedna hra stačí, končíme!“ odcházíme rychle od virtuálního stolu. Ze statistiky programu DeepStack totiž víme, že čím déle s ním budeme hrát, tím více prohrajeme.

Umělá inteligence hrála s třiceti třemi hráči, jedenáct z nich zahráli každý tři tisíce partií. Krabicový graf ukazuje, že žádnému hráči z první dvacítky se nepodařilo umělou inteligenci porazit. Celkové (průměrné) vítězství bylo vysoko nad výhodou, kterou umělá inteligence potřebuje k pohodlnému vyhrávání na profesionálních turnajích.

Umělá inteligence hrála s třiceti třemi hráči, jedenáct z nich zahráli každý tři tisíce partií. Krabicový graf ukazuje, že žádnému hráči z první dvacítky se nepodařilo umělou inteligenci porazit. Celkové (průměrné) vítězství bylo vysoko nad výhodou, kterou umělá inteligence potřebuje k pohodlnému vyhrávání na profesionálních turnajích.

Přesně to zjistili hráči, kteří měli v prosinci 2016 v rámci experimentu šanci vyhrát tisíce dolarů, pokud DeepStack porazí. Turnaje se zúčastnilo i několik hráčů širší světové špičky, ale statistika ukazuje, že nikdo z nich DeepStack nedokázal překonat. Krátkodobě lze proti umělé inteligenci vyhrávat, ale dlouhodobě je lepší. „Hraje totiž velmi blízko matematickému optimu,“ vysvětluje Viliam Lisý. Spočítá si pravděpodobnosti a dodržuje je v rámci her, v čemž lidé obvykle nejsou moc dobří. Ale DeepStack neumí jen počítat pravděpodobnosti. Jeho podstata je mnohem složitější, a proto také zajímavější. Mohl by totiž v budoucnu sloužit nejen pro pokerové turnaje, ale i pro další oblasti rozhodování, kde nemáte k dispozici všechna data.

S takto silným pokerovým automatem by také programátoři mohli za pár měsíců vydělat miliony dolarů (kdyby byli opatrní a nebylo jim proti srsti porušit pravidla internetových heren). Ale nezdálo se, že by je taková možnost lákala, spíše se jí smějí. Mnohem větší odměnou je pro ně evidentně možnost publikace článku v Science, jednom z nejprestižnějších vědeckých časopisů.

Programátoři Viliam Lisý (vlevo), Matej Moravčík a Martin Schmid nám předvedli svůj výtvor, který museli více než dva měsíce držet pod pokličkou.

Programátoři Viliam Lisý (vlevo), Matej Moravčík a Martin Schmid nám předvedli svůj výtvor, který museli více než dva měsíce držet pod pokličkou.

„Věděli jsme, že máme šanci dostat článek do Science, ale mají tam velmi přísná embarga,“ popisuje Schmid. „Proto jsme museli vše držet pod pokličkou, dokud neprojde článek recenzním řízením a nebude schválen k publikaci.“

Umělá inteligence a její pohled na blafování a sázení

Tým vývojářů, v přední řadě zleva Martim Schmid, Michael Bowling a Matej Moravčík. Viliam Lisý je třetí v horní řadě vlevo.

Tým vývojářů, v přední řadě zleva Martim Schmid, Michael Bowling a Matej Moravčík. Viliam Lisý je třetí v horní řadě vlevo.

„Ani jeden z nás nehraje poker,“ přiznali se nám hned na začátku programátoři, kteří se na kanadské univerzitě na vývoji DeepStacku významně podíleli. Jejich specialitou je umělá inteligence, neuronové sítě a matematické metody k jejich optimalizaci. „Všechny neuronové sítě už dneska běží na grafických kartách, to byla jedna z inovací posledních let, jinak jsou tu s námi neuronové sítě už skoro padesát let, to není nic nového,“ vysvětluje Schmid. Ale jejich algoritmus, vyvíjený pod vedením profesora Michaela Bowlinga z University of Alberta, neuronovou inteligenci zapojil nečekaně efektivně.

„Algoritmus DeepStack je přelomový z toho důvodu, že se nám podařilo implementovat myšlenky, které velmi dobře fungují v jiných hrách, ve hrách s úplnou informací,“ vysvětlil nám Martin Schmid. Odkazuje tak na hry jako šachy, dáma nebo go, ve kterých počítač pracuje s prohledáváním možných tahů (rozhodnutí) na základě toho, v jaké pozici se nachází (jak omezené má rozhodování). Znázornit to lze na tzv. rozhodovacím stromě, který se větví vždy, když je na výběr více možností. Jen některé větve tohoto stromu ovšem mají pro daného hráče v daný moment smysl zvažovat.

Martin Schmid vysvětluje, proč je jejich program lepší, než konkurenční Liberatus: „Zatímco oni běží na superpočítači, my běžíme na obyčejném notebooku.“

Martin Schmid vysvětluje, proč je jejich program lepší, než konkurenční Liberatus: „Zatímco oni běží na superpočítači, my běžíme na obyčejném notebooku.“

„Hlavní stavební kámen DeepStacku je myšlenka lokálního vyhledávání. Kdykoli jsme na tahu, spustíme výpočet, a během toho času, který máme na rozhodnutí - řekněme tři až pět sekund - spočítáme, jakou akci zahrajeme v té dané pozici,“ pokračuje Schmid. Tím se liší od konkurenčních pokerových umělých inteligencí, které si obvykle svou strategii propočítají dopředu a pak už hrají podle této propočítané tabulky.

Druhým stavebním kamenem DeepStacku je neuronová síť. „Když nám dochází čas na rozhodování a my bychom nestihli spočítat všechny eventuality, naše vyhledávání v určité hloubce zarazíme. Místo exaktního dopočítání nastoupí hluboká neuronová síť.“ Tu Schmid označuje také jako „počítačovou intuici“. Neuronová síť se trénovala na deseti milionech náhodně vygenerovaných situací, pro které si matematicky spočítala nejlepší krok.

Pokud vám toto vysvětlení nestačí, nebojte, nám také nestačilo. Naštěstí na nás programátoři měli dost času i trpělivosti a vysvětlili nám vše podrobněji.

Proč je poker těžší, než šachy?

Porážka člověka počítačem v šachu se dnes při zpětném pohledu jeví jako téměř nevyhnutelná: dnes už by nejlepší člověk bez pomoci nestačil ani průměrnému programu. Šachy už jsou prakticy vyřešený problém. V kontrastu proti nim však totiž stojí celá řada jiných her, které se zdály příliš složité.

Počítač vs. lidé

Jak počítač porážel lidi v jejich vlastní hře

Programátoři rádi hledají způsoby, jak naprogramovat algoritmus, který porazí člověka (nebo jiný algoritmus) v nějaké hře. Je to dobrý trénink a často lze použité metody aplikovat i v jiných oblastech.

  • nejjednodušší ukázkou jsou piškvorky 3x3 (tic-tac-toe), kde lze všechny varianty vyřešit ručně
  • 1988 - slabě vyřešené jsou i piškvorky, ve kterých jde o propojení čtyř symbolů (Connect Four). V roce 1995 dopočítáno silné řešení všech pozic na desce 8x8.
  • 1997 - počítač IBM Deep Blue porazil Garryho Kasparova v šachu. I nadále jsou však šachy hra, která není zcela spočítaná.
  • 2007 - počítačový program Chinook z University of Alberta nejenže dokázal v dámě porazit nejlepší lidské soupeře (to už uměl v roce 1995), tale také hrubou silou dopočítal všechny možnosti tahů, což zaručuje, že žádný zápas neprohraje (nejhůře remízuje).
  • 2011 - počítač IBM Watson porazil lidské soupeře ve hře Jeopardy (podobá hře Riskuj), odpovídal přitom na stejné otázky, jako soupeři. Nelze ale říci, že bynedělal chyby.
  • 2016 - počítačový program AlphaGo (Google) porazil nejlepšího hráče světa ve hře go. Také zde byla použita „počítačová intuice“, tedy hluboké neuronové sítě.

Jedním důvodem je čistě náročnost na výpočty. Příkladem je třeba go, kde je počet možných kombinací kamenů na desce zhruba 10180. V případě pokeru (tedy přesněji řečeno jeho varianty Poker Texas Hold’em No Limit) je počet možných výsledků zhruba o dvacet řádů nižší (10160), takže tady je podobné.

Ani jedno se se současnými počítači spočítat nedá (a ještě dlouho se to nezmění), a tak se musel problém hodně osekávat. V případě go byly výsledky dlouho hodně špatné, nakonec se poprvé povedlo u softwaru AlphaGo, který v loňském roce začal porážet i špičkové hráče. AlphaGo to dokázal díky tomu, že v sobě kombinoval učenlivou neuronovou síť, která se naučila a pak také odehrála miliony partií, se softwarem, který pak dokázal neuronové sítí navržené varianty do nutné hloubky dopočítat (znovu zjednodušujeme, podrobněji o AlphaGo v našem starším článku).

Poker je ale o to složitější, protože v jeho průběhu nejsou všechny karty vyložené na stůl. Hráč sice vidí karty vyložené na stole, ale nikdy neuvidí dvě karty, které má v ruce protihráč, a ani to, která karta se na stole objeví příště. A v práci s neúplnými informacemi byly počítače špatné.

Pokerové „umělé inteligence” se programovaly tedy v minulých letech obvykle tak, aby si na začátku propočítaly podle předem nastavených parametrů jeden konkrétní postup (tabulku), a pak se ho držely až do konce. Ten býval obvykle hořký, protože takové programy nijak nereagovaly na vývoj situace. Když hráči jejich slabiny odhalili, mohli je do nekonečna využívat. A tak není divu, že i na soutěžích v počítačovém pokeru programátorských týmů ze špičkových pracovišť se objevovaly i programy, které si statisticky vedly hůře než hráč, který by karty pokaždé složil.

DeepStack ovšem dokáže při každé změně situaci (vyložené kartě) svou strategii přehodnotit. Týmu se totiž podařilo vytvořit „souřadnicový systém”, který dobře popíše důležité parametry každé herní situace. A to zase umožní softwaru rychle a přesně se zorientovat při výběru možných řešení. (Definice herní situace je jeden velký teoretický úspěch práce, ale je to natolik odborné, že vážné zájemce znovu odkážeme na práci v Science, a zbytek čtenářů ujistíme, že bez této informace mohou žít).

Počítač přitom správné řešení vybírá podle starého známého principu teorie „hraj, tak abys toho co nejméně litoval”. Přesně jde o variantu, pro kterou se používá anglický výraz „counterfactual regret minimalisation” (CFR) a jde o teoretický postup dovedený k dokonalosti právě skupinou profesora Bowlinga z Alberty, u kterého tři česko-slovenští programátoři byli na stáži (jejich první práce o tomto postupu je dostupná odsud). V roce 2015 pak kanadský tým dokázal (my jsme o tom psali zde), že tento postup může opravdu porazit i téměř dokonalé hráče, což pak nejnovější studie dokázala i prakticky.

Schéma ukazuje, jakým způsobem se rozhoduje program DeepStack. Během hry program neustále upřesňuje pravděpodobnosti pro jednotlivé karty soupeře. Protože kompletní propočítání všech možností by trvalo neúnosně dlouho, stará se o „intuitivní odhad“ neuronová síť.

Schéma ukazuje, jakým způsobem se rozhoduje program DeepStack. Během hry program neustále upřesňuje pravděpodobnosti pro jednotlivé karty soupeře. Protože kompletní propočítání všech možností by trvalo neúnosně dlouho, stará se o „intuitivní odhad“ neuronová síť.

Bohužel se pro účely lidského pokeru tato metoda nedá “odkoukat“. Spočívá v tom, že pokerová umělá inteligence si nejprve sama se sebou zahraje miliony partií, ve kterých jen tak náhodně přihazuje a hází karty na stůl. Po každém rozhodnutí si ovšem zpětně propočítá, jak by byla hra dopadla, kdyby hrála jinak, a porovná výsledek se skutečností. U rozhodnutí, která (by) vedla k lepším výsledkům, si udělá obrazně řečeno +1, u těch, která by vedla k horším, pak -1. Číslo může být tím větší, čím horší či lepší jsou dopady rozhodnutí. Podle toho pak upraví svou strategii pro další hry: zvýší pravděpodobnost dobrých rozhodnutí a sníží pravděpodobnost těch špatných.

Když počítač odehraje dost partií, má mapu všech možných situací s poznámkou, jak dobré či špatné jsou. A co je důležitější, má na jejím základě už hotovou strategii, která sice není úplně ideální, ale je jí tak blízko, že z praktického hlediska mezi nimi není rozdíl. Důležité také je, že byť je vytváření strategie výpočetně náročné, použití už hotové strategie ve hře dá výrazně méně práce. A tak může software běžet i na relativně slabém počítači - když tedy použijete ještě jeden trik.

Mám pocit, že bych měl přihodit

DeepStack byl měl být dostatečně rychlý, aby mohl hrát poker s lidmi, tedy aby se rozhodoval jen během několika sekund jako lidští hráči. Byť se počítač dokáže rychle zorientovat, projít si všechna možná rozhodnutí až do všech možných konců je stejně příliš strojově náročné. Druhým důležitý trikem k vytvoření prakticky použitelného pokerového programu tedy bylo vypěstování „intuice”.

Neuronová síť tvoří počítačovou inteligenci, která se na základě předchozích zkušeností dokáže rychle rozhodovat

Je jí neuronová síť, dnes jeden z největších softwarových hitů. Neuronové sítě jsou velmi zjednodušeně řečeno učenlivé programy, které lze vytrénovat v celé řadě dovedností. V tomto případě k tomu, aby odhadovaly výsledky hry a vybraly z nich rychle a jednoduše tu nejslibnější. Program tedy začne počítat, co by bylo v dané situaci nejlepší, ale autoři ho nenechají dopočítat do konce. Brzy mu výpočet useknou a nechají neuronovou síť, aby mezi možnými rozhodnutí vybrala tu, která (doslova) podle jejich zkušeností nejspíše povede k žádoucímu výsledku.

Síť se sestává ze sedmí vrstev (každá s pěti stovkami neuronů) a počítá nejen s viditelnými kartami, ale i s dosavadními sázkami.

Síť se sestává ze sedmí vrstev (každá s pěti stovkami neuronů) a počítá nejen s viditelnými kartami, ale i s dosavadními sázkami.

Počítač tak nehraje zcela optimálně, ale jeho výsledek se ideálu blíží natolik, že ani naprosto dokonalý hráč by si velmi dlouho nemohl být úplně jistý, že vyhrává opravdu proto, že je lepší, a ne proto, že mu šla karta. A zároveň se díky použitým softwarovým „trikům” podařilo snížit nároky na výpočet natolik, že program, který porážel i špičkové profesionální hráče, pracoval na jednom jediném notebooku s výkonnější grafickou kartou (neuronové sítě běhají optimálně na grafických kartách, protože jde o výpočty probíhající paralelně, což je právě doména GPU).

Co s tím dál? Rozhodování bez veškerých informací se hodí

DeepStack zatím zvládá pouze hru pro dva hráče. Hra pro více hráčů už je totiž trochu jiná záležitost: „Tam ani přesně teoreticky nevíme, jaké by mělo být ideální řešení, a z matematického hlediska je to méně zajímavé,” říká Matej Moravčík. Dopočítat se ideálního řešení tedy asi nebude jen tak možné, což ovšem zřejmě neznamená, že by si počítače v této disciplíně musely vést špatně. Michael Bowling z Alberty pro časopis Nature řekl, že během prvních zkoušek upravené „umělé inteligence” pro hru více hráčů si vedla překvapivě dobře. Na lidi tedy možná počítače budou stačit, i když k dokonalosti budou mít daleko.

Programátoři doufají, že podobný princip půjde uplatit i v při řešení reálných problémů, například v bezpečnosti nebo v medicíně, kde také obvykle nemáme všechny informace.

Zajímavější by mohl být vývoj podobných algoritmů pro využití čistě mimo omezeného pole akademického pokeru. „Her” s neúplnou informací je kolem nás celá řada, od financí přes medicínu po bezpečnost (kybernetickou i fyzickou). Pravidla většiny z nich jsou samozřejmě dána mnohem méně jasně než u pokeru, a tak by bylo ještě lepší, kdyby se počítače učily jejich pravidla za pochodu - to je další velký problém umělé inteligence, na kterém pracuje řada týmů. Teoreticky se tedy podobným „umělým inteligencím” nabízí velmi široké pole možných uplatnění. Uvidíme, jestli k nim opravdu dorostou.

Dvě pokerové umělé inteligence a jedno prvenství

Pokud sledujete zprávy z vědy a techniky, možná jste si všimli, že o vítězství počítače nad člověkem v pokeru už se letos jednou mluvilo. Systém nazvaný Liberatus porazil na speciálně pořádaném turnaji vybrané pokerové profesionály.

Šel na to ovšem trochu jinak. Liberatus je v podstatě řešení problému „hrubou silou“, které používá superpočítač jak před partií, tak v průběhu zápasu. (Nepočítá samozřejmě všechny varianty, na to výkon dnešních strojů nestačí.)

Liberatus v průběhu speciálně uspořádaného turnaje porazil lepší hráče než DeepStack, ale není jednoduché oba programy porovnávat. Kromě toho, že software Liberatus běžel na ohromné sestavě a byl zhruba 150krát výpočetně náročnější než DeepStack, přistupoval údajně jeho tým také v průběhu turnaje k „záplatování“ některých chyb programu. Součástí Liberatu byl totiž speciální modul, který sledoval, jak soupeři objevují a využívají slabiny ve strategii počítače. DeepStack se během měsíc trvajícího turnaje nijak neměnil.

Řešení DeepStacku se zdá tedy na pohled elegantnější a méně náročné na výpočetní výkon, to ovšem nutné neznamená, že v zápase obou soupeřů by vyhrál. Teoreticky by hra měla být prakticky vyrovnaná, ale je docela dobře možné, že jeden program by náhodou našel slabinu v soupeřově strategii. Každopádně šéf kanadského týmu Michael Bowling pro Nature prohlásil, že střetnutí obou počítačů z vědeckého hlediska podle něj příliš mnoho nového nepřinese, a tak nečekejme, že by se oba rivalové v dohledné době sešli nad jedním virtuálním stolem.

Aktualizace: Článek jsme rozšířili a doplnili jsme odkazy na další AI.





Hlavní zprávy

Akční letáky
Akční letáky

Všechny akční letáky na jednom místě!

Najdete na iDNES.cz



mobilní verze
© 1999–2017 MAFRA, a. s., a dodavatelé Profimedia, Reuters, ČTK, AP. Jakékoliv užití obsahu včetně převzetí, šíření či dalšího zpřístupňování článků a fotografií je bez souhlasu MAFRA, a. s., zakázáno. Provozovatelem serveru iDNES.cz je MAFRA, a. s., se sídlem
Karla Engliše 519/11, 150 00 Praha 5, IČ: 45313351, zapsaná v obchodním rejstříku vedeném Městským soudem v Praze, oddíl B, vložka 1328. Vydavatelství MAFRA, a. s., je členem koncernu AGROFERT.