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.
Webové rozhraní, přes které hráči hráli z pohodlí domova

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ý...

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 v...

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...

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í...

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...

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...

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.

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

 

Nejčtenější

Dětem škodí obrazovky a displeje. Ale jinak, než si rodiče obvykle myslí

Jak všudypřítomné displeje ovlivňují výchovu dětí? (ilustrační fotografie)

Světová zdravotnická organizace vydala nová doporučení ohledně aktivit vhodných pro malé děti. Nejvíce pozornosti si...

Třímachový zabiják letadlových lodí Suchoj T-4 byl velkým žroutem rublů

Suchoj T-4

Historie letectví se pozoruhodnými stroji jenom hemží. Jedním takovým byl i sovětský bombardér Suchoj T-4. Vznikl pouze...

Poslední vrtulník. Začíná předehra zcela zapomenuté letecké tragédie

Reklama NYA zvoucí k cestování v proudové době.

Byla to budova, kterou by někteří obyvatelé New Yorku nejraději hned po dokončení nechali zdemolovat. Místní bar s...

Aktualizujte si WhatsApp. Kvůli chybě vás mohli útočníci odposlouchávat

Aplikace WhatsApp (ilustrační obrázek)

Nový trik využívající chybu v komunikační aplikaci WhatsApp umožnil na základě zmeškaného hovoru nainstalovat do...

Statisíce posluchačů přišly o svá internetová rádia, náprava je pomalá

DAB rádio Pure Oasis Flow

Mnoha posluchačům internetových rádií zmizely předvolené stanice i jimi přidané streamy. Největší výrobce čipů pro...

Další z rubriky

Tyto geny můžete jen závidět. Chrání před cukrovkou a obezitou

Obezita má svou genetickou složku, o tom dnes není sporu. Velké potíže...

„Poruchy“ v naší DNA mohou mít někdy nečekané výsledky. Ilustruje to mimo jiné i výzkum univerzity v Cambridge. Ukázal,...

Seismický úspěch. Sonda InSight zachytila první marsotřesení

Sonda InSight v konfiguraci, jak bude pracovat na povrchu Marsu. Všimněte si...

Seizmograf na sondě InSight zaznamenal první otřesy, které podle vědců pocházejí z nitra Marsu. O takzvaném...

Velký omyl českého rodáka odstartoval snahy o ovládnutí energie Slunce

Ronald Richter pracující na projektu Huemul. Snímek z argentinského zdroje není...

Příběh fyzika Ronalda Richtera, rodáka z dnešního Sokolova, dokazuje, že ve vědě slepé uličky opravdu mohou vést na...

Nejlepší dětské knihy podle věku: Testujeme na vlastních dětech
Nejlepší dětské knihy podle věku: Testujeme na vlastních dětech

Dětských knih je na trhu velké množství, a tak je někdy složité najít tu pravou, která bude děti opravdu bavit. My jsme vyzkoušeli osm knížek. Podívejte se, jak v testu našich „redakčních“ potomků obstály, a nechte se inspirovat.

Najdete na iDNES.cz