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

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.




Nejčtenější

Být první nestačí. Spermie musí projít záhadným „pracovním pohovorem“

Vajíčko si podle některých vědců aktivně vybírá, kterou spermii vpustí k...

Spermie vyrážejí k vajíčku a ta nejrychlejší spermie vajíčko oplodní. Přibližně tak si většina lidí představuje...

Otázka dne: Jak může dítě v děloze přežít týdny hlavou dolů?

Dítě vydrží v děloze několik týdnů hlavou dolů. Vy to ovšem doma nezkoušejte,...

Jak může dítě v děloze přežít týdny hlavou dolů, tedy v poloze, která u dospělého vede spolehlivě ke smrti? To je téma...



Měla to být revoluce v létání. Před 50 lety poprvé vyjel Concorde z hangáru

První premiéra Concorde na veřejnosti v Toulouse.

Letiště Toulouse-Blagnac, pondělí 11.prosince 1967. Veřejnost má poprvé možnost na vlastní oči spatřit Concorde, první...

Poslední tři dny: hlasujte a vyhrajte špičkový smartphone

Mobil roku

Hlasujte v jubilejním 20. ročníku ankety Mobil roku. Vyberte nejlepší letošní smartphone a vyhrajte jednu z...

Čínská letadlová loď bude asi mít elektromagnetický katapult na letadla

Vizualizace nové čínské letadlové lodě Type 002

Nová třída letadlových lodí čínského námořnictva Type 002 bude pravděpodobně vybavena elektromagnetickým katapultem pro...



Další z rubriky

Tohle astronomové ještě neviděli. Přiletěla první mezihvězdná planetka

Rekonstrukce možné podoby planetky 1I/2017 U1 (‘Oumuamua) na základě údajů...

V naší soustavě už více či méně dobře známe 750 tisíc různých planetek a dalších menších těles. Ale žádný z nich se...

Evropská komise dala herbicidu glyfosátu dalších pět let

Roundup je dnes nejpoužívanějším totálním herbicidem.

Patrně nejpoužívanější pesticid na světě, známý pod obchodní značkou Roundup, má poněkud překvapivě prodlouženou lhůtu...

Budou stačit jen obnovitelné zdroje? V USA se kvůli tomu vědci žalují

(Ilustrační snímek)

Může být vědecká kritika dehonestace? Americký soud se bude zabývat nezvyklým sporem mezi dvěma skupinami odborníků.

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

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



Najdete na iDNES.cz