Poker, počítačová hra s umělou inteligencí

České vysoké učení technické v Praze Fakulta elektrotechnická Katedra počítačů

Bakalářská práce

Poker, počítačová hra s umělou inteligencí Tomáš Tvaroh

Vedoucí práce: Ing. Miroslav Balík, Ph.D.

Studijní program: Softwarové technologie a management, Bakalářský Obor: Softwarové inženýrství 29. května 2009

ii

Poděkování Rád bych poděkoval svému vedoucímu bakalářské práce Ing. Miroslavu Balíkovi, Ph.D. za rady a věcné připomínky při zpracování práce. Dále bych chtěl poděkovat svým rodičům za toleranci a pomoc, kterou mi v průběhu studia poskytli.

iii

iv

Prohlášení Prohlašuji, že jsem práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).

V Praze dne 29. 5. 2009

........................................................................................

v

vi

Abstrakt Tato práce se zabývá analýzou, návrhem a implementací aplikace, která umožňuje hrát v současné době nejpopulárnější variantu karetní hry poker s názvem Texas Hold’em. Aplikace podporuje hru více hráčů po síti a obsahuje umělou inteligenci pro hru proti hráčům ovládaným počítačem. Tyto možnosti se dají kombinovat a v jedné hře mohou hrát zároveň lidští i počítačoví hráči. Součástí práce je testování aplikace z hlediska uživatelského rozhraní, logiky programu a umělé inteligence.

vii

viii

Abstract This thesis describes analysis, design and implementation of application that provides functionality to play Texas Hold’em, world’s most popular variant of poker. Application supports multi-player game via computer network and implements artificial intelligence to play against computer players. These approaches can be combined so that a game can include both human and computer players. Application is then tested regarding user interface, program functionality and level of artificial inteligence.

ix

x

Obsah 1 Úvod 1.1 Zadání . . . . . . . . . . . 1.2 O pokeru . . . . . . . . . . 1.3 Cíl práce . . . . . . . . . . 1.4 Existující programy . . . . 1.4.1 Pokerové místnosti 1.4.2 Pokerové automaty 1.4.3 Podpůrný software 1.4.4 Hra proti počítači .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

2 Pravidla hry 2.1 Průběh hry . . . . . 2.1.1 Vlastnosti hry 2.1.2 Průběh kola . 2.1.3 Shrnutí . . . 2.2 Pořadí kombinací . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

7 . 7 . 7 . 9 . 10 . 11

. . . . . . . . . . . .

13 13 13 13 14 14 15 16 17 18 18 18 19

. . . . .

. . . . .

. . . . .

3 Analýza 3.1 Použité technologie . . . . . . . . . . . . 3.1.1 Programovací jazyk . . . . . . . . 3.1.2 Síťový protokol . . . . . . . . . . 3.2 Use Case diagramy . . . . . . . . . . . . 3.2.1 Uživatelé . . . . . . . . . . . . . . 3.2.2 Diagram nastavení . . . . . . . . 3.2.3 Diagram hry . . . . . . . . . . . . 3.3 Doménový diagram . . . . . . . . . . . . 3.4 Architektura aplikace . . . . . . . . . . . 3.4.1 Architektura klient/server . . . . 3.4.2 Samostatná aplikace . . . . . . . 3.4.3 Zhodnocení a výběr architektury

xi

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

1 1 2 2 3 3 3 4 5

4 Realizace 4.1 Funkcionalita balíčků . . . . . . . . . . . . . 4.1.1 Configuration . . . . . . . . . . . . . 4.1.2 Engine . . . . . . . . . . . . . . . . . 4.1.3 Interfaces . . . . . . . . . . . . . . . 4.1.4 Network . . . . . . . . . . . . . . . . 4.1.5 View . . . . . . . . . . . . . . . . . . 4.2 Ohodnocení karetní kombinace . . . . . . . . 4.2.1 Algoritmus vyhodnocovací funkce . . 4.3 Umělá inteligence . . . . . . . . . . . . . . . 4.3.1 Algoritmus ohodnocení síly karet . . 4.3.2 Výpočet indexu zisku . . . . . . . . . 4.3.3 Rozhodování na základě indexu zisku

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

21 21 22 22 22 23 23 23 23 24 24 25 26

5 Testování 5.1 Testování použitelnosti . . . . . . 5.2 Testování logiky programu . . . . 5.3 Testování umělé inteligence . . . 5.4 Srovnání s existujícími aplikacemi

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

27 27 28 28 28

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

6 Závěr

29

Literatura

31

A Slovník pojmů

33

B Instalační a uživatelská příručka B.1 Obsah přiloženého CD . . . . . B.2 Instalace a spuštění . . . . . . . B.3 Ovládání aplikace . . . . . . . . B.3.1 Menu . . . . . . . . . . . B.3.2 Hlavní pohled . . . . . . B.3.3 Nastavení . . . . . . . .

35 35 36 36 36 36 37

. . . . . .

xii

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

Seznam obrázků 3.1 3.2 3.3 3.4

Use Case diagramy . . . . . . Use Case - diagram nastavení Use Case - modul hry . . . . . Doménový diagram . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

14 15 16 17

B.1 Hlavní obrazovka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 B.2 Výchozí hodnoty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 B.3 Herní hodnoty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

xiii

xiv

Seznam tabulek 2.1

Příklady karetních kombinací . . . . . . . . . . . . . . . . . . . . . . 12

xv

xvi

Kapitola 1 Úvod Tato práce se zabývá implementací karetní hry poker včetně umělé inteligence umožňující hru proti počítačovým protivníkům. Poker představuje z hlediska umělé inteligence zajímavý problém, protože se jedná o hru s neúplnou informací, kdy žádný z hráčů nemá v danou chvíli všechny informace o stavu hry. U her s úplnou informací, jako jsou například Šachy nebo Go [9], je princip umělé inteligence založen převážně na prohledávání do hloubky, ohodnocování pozice a prořezávání výsledného stromu. U pokeru se navíc musí počítat s nejistotou, rizikem a také s psychologií protihráčů. Co je proti jednomu oponentovi dobrý tah může být špatný tah proti oponentovi jinému i přesto, že stav hry je v obou případech stejný. Kromě umělé inteligence je součástí výsledné aplikace možnost hrát hru i proti lidským protihráčům s využitím lokální počítačové sítě nebo Internetu. V této kapitole je čtenář seznámen s pokerem a bude vysvětleno, že poker není jen hazard o štěstí, ale komplexní hra s propracovanou složitou strategií. Budou zde popsány zadání a cíle této bakalářské práce a závěrem kapitoly budou uvedeny existující softwarové produkty, které se zabývají pokerovou tématikou.

1.1

Zadání

Cílem práce je vytvořit aplikaci, která by umožňovala hrát karetní hru poker. Aplikace bude umožňovat hru více hráčů po síti s využitím TCP protokolu i hru proti počítači. Součástí programu bude umělá inteligence, která bude umět poker hrát. Varianty hry půjdou mezi sebou kombinovat, a proto bude možné hrát zároveň proti lidským i počítačovým protihráčům. Kvalita navržené umělé inteligence bude otestována v reálné hře proti lidským hráčům.

1

1.2

O pokeru

Poker je v současnosti nejrozšířenější karetní hra na světě. Na světě ho hraje přes sto miliónů lidí [1] a toto číslo stále roste, protože čím více poker nabývá na popularitě, tím více je o něm slyšet, a tím pádem má více lidí možnost se s ním seznámit. Z karetní hry se tak pomalu začíná stávat sportovní odvětví se vším, co ke sportovnímu odvětví neoddělitelně patří. Záznamy z větších turnajů jsou přenášeny na televizních sportovních kanálech a fanoušci se vydrží dívat celé hodiny na to, aby se dozvěděli, kdo turnaj vyhraje, případně aby mohli sledovat hru svého favorita a fandit mu. Existují i populární pořady (High Stakes Poker, Poker After Dark) [7], ve kterých moderátor komentuje pokerovou hru pro veřejnost, filmy s pokerovou tématikou (Rounders) a dokonce i celý seriál věnovaný jen této hře (Tilt). V České republice, hlavně mezi starší generací, má však zatím poker negativní nádech hazardu, který je obecně brán jako něco špatného. Poker není hazard, protože narozdíl od automatů a loterií, kde člověk musí nejprve vsadit určitou část peněz a potom v závislosti na náhodě, kterou nemůže ovlivnit, buď vyhraje nebo prohraje, mechanismus pokeru funguje trochu jinak. Hráč sází postupně v průběhu hry v závislosti na tom, jak daná hra probíhá. Pokud se mu nelíbí karty, které dostane na začátku, může se rozhodnout, že nebude hru vůbec hrát. Učiněním tohoto rozhodnutí nepřijde v dané hře o nic nebo jen o velmi málo. Poker tedy není hra hazardní, ale hra velice komplexní, kde záleží na umění hráče, přičemž ti dobří potom vítězí a ti špatní prohrávají. Hra v kasínu potom probíhá tak, že narozdíl od rulety, blackjacku a podobných, kde hraje člověk proti kasínu, v pokeru hrají hráči pouze proti sobě, a co jeden získá, to druhý musí ztratit. Dlouhodobě se tak dá finančně růst, a proto existuje spousta lidí, kteří se hraním pokeru živí. Ti zvládli strategii hry na takové úrovni, že vítězí nad ostatními, což je dalším důkazem toho, že poker není pouze o štěstí, jak si hodně lidí myslí.

1.3

Cíl práce

Cílem této práce je navrhnout a následně implementovat program, který bude umět poker hrát. Program se bude skládat ze tří následujících modulů: • logika programu, • uživatelské rozhraní, • umělá inteligence. Jednotlivé moduly budou na sobě nezávislé, což zvýší přehlednost kódu a usnadní to práci při případném pokračování v projektu. Logika programu bude zajišťovat 2

dodržování pravidel hry, bude se starat o balíček karet a o seznam hráčů, hlídat sázky, kontrolovat karty, přidělovat výhry, tedy obstarávat celou technickou stránku programu. Grafické uživatelské rozhraní bude mít na starost interakci s uživatelem a bude předávat události logickému modulu. Program bude schopen i sám hru hrát, o což se bude starat modul umělé inteligence. Před začátkem hry tak bude možné obsadit volná místa hráčem/počítačem, který bude schopen činit rozhodnutí, a hrát v závislosti na nich.

1.4

Existující programy

Existující programy, které se zabývají pokerem, se dají rozdělit do čtyř kategorií, přičemž každá kategorie má svá specifika. Proto budou rozebrány zvlášť, bude popsáno, v čem se od sebe liší, a uvedeny příklady softwaru, který do každé z nich spadá.

1.4.1

Pokerové místnosti

Pokerové místnosti se nazývají programy, které umožňují lidem z celého světa hrát proti sobě poker po Internetu. Často jsou vydávány provozovatelem internetového kasína, které vydělává na tom, že si strhává určité procento z každé výhry, tzv. rake, a mají formu klientských desktopových aplikací. Tyto programy jsou zdarma, mají vynikající design, výbornou technickou podporu a vždy se tam dají najít spoluhráči. Jejich nevýhodou je to, že neumožňují hru proti počítači, a již zmíněný rake. Tato kategorie je s ohledem na počet programů nejčetnější, přesto se však aplikace od sebe ve funkčnosti v zásadě neliší. Odlišuje je hlavně kvalita různých bonusů za věrnost. V těchto programech je možné hrát i zdarma o tzv. herní peníze, což slouží serveru jako reklama a hráčům jako možnost naučit se poker a vyzkoušet si nezávazně prostředí programu. Patří sem například programy PokerStars, PartyPoker, TitanPoker nebo například český ExpektPoker.

1.4.2

Pokerové automaty

Pokerové místnosti mají excelentní logiku programu a uživatelské rozhraní, ale žádnou umělou inteligenci. U pokerových automatů, v literatuře také označovaných jako boti, je tomu přesně naopak. Tyto programy implementují pokerovou AI a často ani žádné uživatelské rozhraní nemají, jen se připojí na nějaký existující poker server a chovají se jako hráč. Na většině serverů je ale oficiálně zakázáno je používat, protože tyto servery jsou určeny pouze pro lidské hráče.

3

WinHoldEm WinHoldEm je pokerový program Raye Borneta, který se připojí na zvolený pokerový server a hraje na něm místo hráče. Úroveň jeho umělé inteligence je vysoká a obsahuje implementaci statistik, sledování chování protivníků, ale například i blufování, což je umění předstírat, že má hráč dobré karty, přestože to ve skutečnosti není pravda. Jeho hlavní nevýhodou je to, že je ilegální. Používání automatických systémů na většině pokerových serverů může při odhalení vést od zablokování přístupu až po vážné právní následky. Polaris Polaris je pokerový bot vyvinutý výzkumnou skupinou na univerzitě v Albertě ve Spojených státech. V roce 2007 na pokerové soutěži „člověk vs. počítačÿ dokázal porazit pokerové profesionály, ovšem zatím pouze ve hře dvou hráčů. Stejně jako předchozí bot, ani tento nenabízí možnost si proti němu zahrát, protože z výše zmíněných třech částí mého softwarového projektu pokrývá pouze umělou inteligenci.

1.4.3

Podpůrný software

S rozvojem online pokeru šel ruku v ruce i vznik všemožných podpůrných softwarů. Je sice ilegální, aby místo vás hrál na Internetu bot, ale pokud máte spuštěný program, který Vám přesně říká, co máte dělat, je vše v pořádku. Protože online pokerem se dají vydělat peníze a tyto podpůrné programy jsou navíc legální, jsou mnohem rozšířenější než boti. Některé tyto programy se dají použít na testování umělé inteligence, a proto zde zmíním dva, které budu při vývoji využívat. Texas Calculatem Tento program se podobně jako bot připojí na pokerový server, ale tentokrát na tom serveru musíte být připojeni i vy, jako hráč. Texas Calculatem potom sleduje, jaké karty server rozdá a jak se chovají protihráči, a na základě toho vám radí, co máte dělat. Program pracuje hlavně s pravděpodobnostmi, takže se ze znalosti již vyložených karet snaží odhadnout šance na to, že zvítězíte. Více informací se dá nalézt na internetových stránkách softwaru [10]. Pokerstove Tento jednoduchý program počítá pravděpodobnost výhry vašich dvou karet nad kartami protivníků. Narozdíl od Texas Calculatem umožňuje zadat rozpětí karet, které si myslíte, že vaši soupeři drží. Další jeho výhodou je to, že je zdarma. Bohužel není možné ho připojit na pokerový stůl, takže všechna data se do něj musí zadávat 4

ručně. Navíc počítá pravděpodobnost pouze pro první dvě karty, takže v pozdější hře, kdy se situace změní, již nemá využití.

1.4.4

Hra proti počítači

Zatím žádná ze zmíněných kategorií nepokrývá plně rozsah tohoto projektu. Každá z nich obsahuje nějakou podmnožinu mnou stanovených cílů programu (logika, uživatelské rozhraní, umělá inteligence), ale žádný z nich neobsahuje všechny. Hra pokeru jen proti počítači ztrácí význam, protože nad počítačem se nedají vyhrát žádné reálné peníze. Texas Holdem Poker Texas Holdem Poker se nachází na adrese http://www.superhry.cz/games/1063/. Je to hra napsaná v programu flash a splňuje všechny cíle této práce včetně možnosti hry proti počítačovému protihráči. Je dobře graficky zpracovaná a kromě hraní pokeru, které představuje hlavní herní náplň, také poskytuje rámcový příběh a realistický zvukový doprovod. Logika programu i uživatelské rozhraní jsou v této hře zpracované výborně, ale v oblasti umělé inteligence má tato práce ambice Texas Holdem Poker překonat. Telltale Texas Hold’em Telltale Texas Hold’em je desktopová aplikace, která umožňuje hru hráče proti počítačovým protivníkům. Hra je ve 3D z pohledu hráče, což je na jednu stranu zajímavé, ale také méně přehledné oproti klasickému pohledu na stůl z vrchu. Umělá inteligence hry se nedopouští žádných elementárních chyb a z počátku pobaví i vtipně namluvené komentáře, které vaši protihráči při hře pronáší. Ve své práci bych chtěl oproti Telltale Texas Hold’em zlepšit hlavně přehlednost uživatelského rozhraní.

5

6

Kapitola 2 Pravidla hry Na začátek je potřeba upřesnit, že se celá práce zabývá pouze variantou pokeru s názvem Texas Hold’em, což je v současnosti nejrozšířenější varianta. Pokud někoho slyšíte bavit se o pokeru, mluví pravděpodobně právě o Texas Hold’emu. Pravidla hry jsou velice jednoduchá. Je až překvapivé, kolik možností může přinést hra, která má tak jednoduchá pravidla, že se dají naučit během několika málo minut. V této kapitole je popsáno, jak probíhá hra od začátku až do konce, a poté je uvedeno pořadí hodnocených figur, podle kterého se určuje, kdo z hráčů vyhrál.

2.1 2.1.1

Průběh hry Vlastnosti hry

Než se pustíme do vysvětlování pravidel, je potřeba zmínit několik obecných věcí, které se vztahují ke hře jako celku. Hra se skládá z většího počtu kol, přičemž hned jak se odehraje jedno kolo, tak hned začíná kolo další, a takto se postupuje po celou dobu. Mezi důležité vlastnosti hry patří počet hráčů, ve kterém se dá poker hrát, varianta hry a výše sázek. Počet hráčů Minimální počet hráčů na poker je 2. Maximální počet hráčů, kteří spolu hrají u jednoho stolu, se může různit a nejčastěji nabývá hodnot 6, 8 nebo 10. Protože v jednom turnaji může být zapojeno více stolů, teoretický maximální počet není omezen. Na největším pokerovém turnaji na světě, World Series of Poker - Main event, hraje v jednu chvíli více než 7000 lidí a v některých online turnajích je počet ještě vyšší. Pokud v jedné hře hraje větší množství lidí, rozdělí se na skupiny k jednotlivým stolům a hrají pouze spolu. Jak hráči postupně vypadávají nebo odcházejí, stoly jsou spojovány dohromady, aby celkový počet hráčů u stolu byl co nejblíže jeho 7

maximálnímu počtu. Pro účely této práce v bude v aplikaci uvažován pouze jeden stůl pro maximálně osm hráčů. Balíček karet Poker se hraje s balíčkem obsahujícím 52 hracích karet, součástí kterého je 13 různých hodnot karet ve 4 různých barvách. Všechny barvy jsou vůči sobě rovnocenné, karty v rámci jedné barvy mají každá různou hodnotu - nejmenší je ve standardním balíčku dvojka, nejvyšší je eso. Karty se na začátku každé hry míchají, takže pořadí karet je pro každou hru náhodné. Sázky Důležitým aspektem hry je výše sázek. Většinou se hraje o reálné peníze, ale není to podmínkou, dá se hrát i o peníze imaginární. Výše sázek je potom jedním z parametrů, podle kterých vybíráme hru, a značí se dvěma čísly - to druhé je většinou dvojnásobkem toho prvního. V každém kole má jeden z hráčů povinnost dát na začátku sázku odpovídající tomu menšímu z čísel, tzv. small blind, a hráč sedící po jeho levici pak povinně sází částku odpovídající tomu většímu neboli tzv. big blind. Tyto povinné sázky jsou zavedeny z toho důvodu, že v každé hře je pak alespoň nějaká základní hodnota, o kterou se dá hrát. Kdyby nic takového neexistovalo, byla by optimální strategie pokládat všechny karty, které nejsou excelentní, čímž by se hra stala nudnou. Hodnota big blindu potom představuje minimální částku, kterou je možné v průběhu sázení ve hře vsadit. Varianty podle sázení Texas Hold’em je jedna z více než tisíce variant pokeru, ale i ta se dále ještě dělí na tři subvarianty podle způsobu, jakým se dá ve hře sázet. Tou nejrozšířenější je No-limit, u kterého platí, že minimální sázka je rovna big blindu a maximální není omezena. Hráč tedy může v průběhu sázení vsadit i vše, co má. Ostatní varianty nějakým způsobem omezují maximální možnost sázky, což sice ubírá na možnostech, jak hru hrát, ale na druhou stranu to zabraňuje riziku ztráty všeho hned v prvním kole. Tato práce se bude zabývat pouze variantou No-limit. Varianty podle způsobu hry Podle způsobu vypadávání hráčů se Texas Hold’em dělí na dvě varianty. První z nich se nazývá cash game a spočívá v tom, že kdokoliv chce může kdykoliv přisednout ke stolu a začít hrát. Stejně tak když chce někdo odejít, tak se může v libovolnou chvíli zvednout a odejít. Druhý, turnajový způsob funguje tak, že hráči na začátku zaplatí vstupní poplatek a dostanou nějaké žetony, se kterými hrají. Když někomu 8

dojdou, tak vypadává ze hry, a i kdyby měl peníze a chtěl hrát dál, tak už by nemohl. Hráči během hry postupně vypadávají, až nakonec zbyde několik posledních, kteří si podle konečného pořadí rozdělí celkovou výhru, která je složená ze vstupních poplatků všech původních hráčů. U turnajového způsobu se navíc postupem času zvedají povinné sázky, aby turnaj netrval věčně. Obě varianty mají své pro a proti a většina pokerových hráčů je střídá buď podle nálady nebo podle času, který chtějí hře v danou chvíli věnovat. Principy hry jsou ale v obou hrách až na pár výjimek stejné, a proto program bude hrát pro jednoduchost cash game variantu.

2.1.2

Průběh kola

Hra pokeru se skládá z jednotlivých kol, která na sobě nijak nezávisí. Kolo probíhá tak, že na začátku po zamíchání karet dostane každý hráč do ruky dvě karty, které vidí jen on, a v průběhu kola se na stůl ještě vyloží celkem pět karet, které vidí všichni. Během hry také několikrát probíhá sázení, čímž se tvoří bank neboli tzv. pot, o který hráči v daném kole hrají. Když někdo nechce dorovnat sázku, tak z kola vypadává a nemá už žádnou šanci bank v tomto kole vyhrát. Na konci kola hráči, kteří zbyli, vyberou z pěti vyložených a ze svých dvou karet nejlepší kombinaci pěti karet a ten, kdo má nejlepší, tak vyhrává celý pot. Pořadí jednotlivých kombinací je důkladně popsáno v následující sekci. Každé kolo má čtyři části s tím, že na začátku každé části se odhalí nějaké nové karty a pak začne sázení. Když sázení skončí, ukážou se nějaké další karty, potom znovu sázení atd. Protože sázení se provádí ve všech částech stejně, dá se princip jeho fungování popsat zvlášť. Princip střídání jednotlivých částí kola je uveden hned poté. Sázení Sázet začíná hráč po levici rozdávajícího a má dvě možnosti, co udělat. Může vsadit nějakou částku, která ale musí být vyšší nebo rovna hodnotě big blindu, nebo může tzv. vyčkávat, což vlastně znamená, že vsadil 0. Slovo potom postupně přechází na následujícího hráče, který má vždy možnosti tři. Pokud nechce dorovnávat protihráčovu sázku, může položit, a tím pádem z daného kola vypadává a už do něj nemůže nijak zasahovat. V případě, že chce zůstat ve hře, musí minimálně dorovnat sázku nejvýše sázejícího hráče nebo, pokud si věří, může vsadit ještě víc, až do maxima svých žetonů. Sázení takhle pokračuje v kruhu až do doby, než zbyde jen jeden poslední hráč, nebo dokud všichni hráči nedorovnají nějakou částku, tj. nikdo v průběhu celého kola sázku nezvýší. Vyvstává otázka, co se děje v případě, že někdo chce zůstat ve hře, ale jeho celkový počet peněz je nižší, než sázka, kterou potřebuje dorovnat. V tomto jediném případě pravidla povolují výjimku a dovolují hráči vsadit. Kdyby se ale stalo, že hráč

9

vyhraje, tak nezíská celý pot, ale pouze poměrnou část toho, co vsadil on, zbytek by šel druhému nejlepšímu ve hře. Střídání jednotlivých částí kola Na začátku kola rozdá jeden z hráčů, tzv. dealer, všem po dvou kartách. Rovnou začíná první kolo sázení a dva hráči po dealerově levici musí postupně vsadit své povinné sázky - small blind a big blind. Sázení pokračuje dokud neskončí a poté se na stůl otočí tři vrchní karty z balíčku, které jsou společné pro všechny zúčastněné. Opět se sází, ale tentokrát se po sázení odkryje už jen jedna karta. To se ještě jednou zopakuje a když se vyloží i poslední, pátá karta, začne poslední sázení a po něm kolo končí. Hráči, kteří zůstali ve hře, si ukáží karty a ten s nejlepší kombinací vyhraje celý pot. V případě, že má více hráčů stejnou kombinaci, pak si pot mezi sebou rozdělí.

2.1.3

Shrnutí

V průběhu celého kola se opakují pouze dvě věci - odhalování nových karet a sázení. Hráči se přitom aktivně zapojují do hry pouze při sázení, takže ve skutečnosti jsou pravidla velmi jednoduchá. Pro přehlednost zde ještě v bodech shrneme průběh jednoho kola: 1. Jeden z hráčů, dealer, rozdá všem po dvou kartách. 2. Hráč po dealerově levici vsadí povinně small blind a následující hráč big blind. 3. Proběhne sázení tak, jak je popsáno v 2.1.2. 4. Na stůl se vyloží tři karty. 5. Proběhne sázení. 6. Na stůl se vyloží jedna karta. 7. Proběhne sázení. 8. Na stůl se vyloží poslední, pátá karta. 9. Proběhne sázení. 10. Zbývající hráči ve hře si ukáží karty a ten s nejlepší kombinací získává pot. 11. Dealerem se stává hráč, který byl v tomto kole po dealorově levici, zamíchají se karty a začíná nové kolo. 10

Jedno takové kolo trvá průměrně jen pár minut, takže v jedné standardní pokerové hře se hrají desítky až stovky takových kol. Cílem pokeru potom není vyhrát co nejvíce kol, ale mít na konci co největší výhru, takže se může stát, že hráč vyhraje pouze dvě kola, ale pokud to jsou kola důležitá a hraje se v nich o hodně, může tak vyhrát i celou hru.

2.2

Pořadí kombinací

Až doposud bylo hodnocení na konci kola popisováno tak, že vyhraje ten hráč, který bude mít nejlepší kombinaci karet. Pořadí jednotlivých kombinací seřazené od nejlepší k nejhorší je následující: 1. Čistá postupka - pět karet stejné barvy, které následují přímo po sobě. 2. Poker - z pěti karet musí alespoň čtyři mít stejnou hodnotu. 3. Full house - právě tři karty tvoří trojici a zbylé dvě karty tvoří dvojici. 4. Flush - všech pět karet má stejnou barvu. 5. Špinavá postupka - všechny karty následují přímo po sobě bez ohledu na barvu. 6. Trojice - právě tři karty mají stejnou hodnotu. 7. Dva páry - mezi pěti kartami existují dvě různé dvojice stejných hodnot. 8. Jeden pár - právě dvě karty mají stejnou hodnotu. 9. Vysoká karta - hodnota nejvyšší karty. Platí, že pokud má hráč lepší kombinaci než ostatní, tak nezáleží na hodnotě karet, které danou kombinaci tvoří. Pokud má více hráčů stejnou kombinaci, tak vítězí ten, jehož karty tvořící kombinaci mají vyšší hodnotu. V případě, že více hráčů má dva páry, je při vyhodnocení rozhodující hodnota vyššího páru. To znamená, že (A♠, A♦, 3♥, 3♦, 7♠) je lepší kombinace než (K♠, K♥, Q♠, Q♥, J♠), protože dvě esa představují nejvyšší dosažitelný pár. Nižší pár by se bral v potaz pouze v případě, že má více hráčů stejnou hodnotu nejvyššího páru. Full house se vyhodnocuje primárně podle hodnoty karet trojice a teprve v případě remízy se hodnotí dvojice. Při porovnání kombinací (10♠, 10♥, 10♦, A♠, A♥) a (J♠, J♥, J♦, 3♠, 3♥) by zvítězila druhá uvedená, protože primární kritérium, hodnota karty v trojici, je vyšší než v případě první kombinace. Může se stát, že mají hráči stejnou kombinaci, která má navíc i stejnou hodnotu, což často nastává, když hráči sdílí větší množství společných karet. V takovém případě rozhoduje hodnota nejvyšší zbývající karty. V případě remízy se vyhodnocuje 11

druhá nejvyšší karta a tímto způsobem se postupuje dokud některý z hráčů nevyhraje nebo dokud se nerovná všech pět karet, což by znamenalo celkovou remízu a rozdělení výhry. Pro lepší představu uvádíme následující tabulku, ve které jsou uvedeny příklady k různým karetním kombinacím. Kombinace

Příklad

čistá postupka poker full house flush špinavá postupka trojice dva páry jeden pár vysoká karta

(3♠, 4♠, 5♠, 6♠, 7♠) (J♠, J♣, J♥, J♦, 7♠) (K♠, K♥, K♣, 2♥, 2♦) (5♠, J♠, 8♠, 2♠, K♠) (10♠, J♥, Q♠, K♦, A♣) (7♠, 7♥, 7♣, 2♠, J♠) (10♠, 10♦, 5♥, 5♦, 7♠) (A♠, A♥, 2♠, 6♦, J♠) (K♠, A♠, 5♥, J♣, 7♣)

Tabulka 2.1: Příklady karetních kombinací

12

Kapitola 3 Analýza V této kapitole je popsán návrh aplikace. Návrh aplikace bude obsahovat popis technologií použitých při vývoji, všechny podstatné UML diagramy a zhodnocení a výběr architektury programu.

3.1

Použité technologie

Důležitým prvkem analýzy každého softwaru je volba vhodných technologií. Rozhodnutí týkající se volby programovacího jazyka, vývojového prostředí, knihoven, protokolů, atd. by měla být učiněna v prvotních fázích projektu, protože ovlivní zásadním způsobem celý vývoj aplikace.

3.1.1

Programovací jazyk

V programu nebudou potřeba rychlé operace s ukazateli, které by v jiných případech mohly vést k volbě jiného programovacího jazyka. Naopak bude kladen důraz na přenositelnost, ve které nemá programovací jazyk Java konkurenci. Projekt bude tedy vyvíjen v Javě. Má navíc hotové knihovny pro práci se síťovou komunikací v balíčku java.net a pro práci s grafickými komponentami v balíčcích java.awt a javax.swing.

3.1.2

Síťový protokol

Aplikace bude využívat síťový protokol TCP. Vhodnost použití v tomto případě je dána malým objemem dat, který bude potřeba přenášet, a bezztrátovostí protokolu. Alternativou by mohl být protokol UDP s nějakým potvrzovacím schématem, ale protože data budou přenášena vždy až po nějaké uživatelově akci a půjde jen o malé packety, bude TCP výhodnější i s ohledem na rychlost jejich zpracování.

13

3.2

Use Case diagramy

Use Case diagramy neboli případy užití znázorňují interakci různých uživatelských rolí se systémem. Ta se bude lišit podle toho, zda hráč teprve nastavuje parametry hry, nebo už ve hře je a ta probíhá. Tyto dva případy bude nutné uvést ve dvou diagramech, protože činnosti v obou se liší a různé jsou i vztahy uživatelských rolí, které se v nich vyskytují.

Obrázek 3.1: Use Case diagramy

3.2.1

Uživatelé

Dle dostupných případů užití se dají uživatelé zařadit do třech základních rolí: Hráč, Server a Klient. Hráč představuje lidského hráče, který nechce hrát proti jiným lidským protihráčům. Ten může na volnou pozici u stolu usadit sebe nebo počítačového protivníka, nastavovat výši základních sázek a v případě, že je všechno nastavení dle jeho přání, může hru odstartovat. Ve hře pak může provádět klasická pokerová rozhodnutí a, v případě potřeby, také hru zastavit. Server má přístup ke všem funkcím programu jako samotný hráč, ale navíc může povolit připojení vzdáleným lidským hráčům, které může ovšem ze hry kdykoliv odpojit. Klient představuje hráče, který se chce připojit ke hře založené vzdálenou stanicí. Nemá tedy přístup do nastavení parametrů, jako je počet a pozice hráčů, a ve hře samotné je omezen pouze na zadávání svých pokerových rozhodnutí. Mezi uživatelskými rolemi je také na diagramech znázorněna dědičnost. To představuje zjednodušený zápis vazeb na případy užití, který funguje tím způsobem, že potomek sdílí všechny případy užití se svým rodičem. 14

3.2.2

Diagram nastavení

Fáze nastavování představuje fázi ještě před samotnou hrou. Hráč založí hru a bude muset nastavit parametry hry, jako je počet hráčů, jejich jména, vklady a rozmístění. Klient přebírá tyto informace od serveru, ke kterému se připojí.

Obrázek 3.2: Use Case - diagram nastavení

15

3.2.3

Diagram hry

Hra začíná, když Hráč ve fázi nastavování odstartuje hru. Od té doby hra pokračuje, dokud ji Hráč nezastaví nebo dokud některému z hráčů nedojdou peníze, což pro něj znamená okamžitou prohru.

Obrázek 3.3: Use Case - modul hry

16

3.3

Doménový diagram

V doménovém diagramu jsou znázorněny základní vztahy mezi moduly v programu. Narozdíl od diagramu tříd, od kterého je požadována přesnost a úplnost v atributech a metodách, tento diagram slouží pro představu o architektuře systému a návrh tříd z něj vychází.

Obrázek 3.4: Doménový diagram

17

3.4

Architektura aplikace

Mezi rozhodnutí, které bude mít velký vliv na implementaci a poté i na používání programu, patří rozhodnutí o jeho architektuře. Při zvažování vhodných architektur je třeba vycházet z požadavků na aplikaci a zohlednit je při výběru architektury finální. Poker je hra pro více hráčů a přestože se hráči střídají po tazích, nemohou hrát u jednoho počítače, protože je důležité, aby navzájem neviděli své karty. Protože hra po síti je jedním ze základních požadavků, nabízí se nám možnost zvážit vícevrstvou architekturu klient/server. Druhou možností by bylo vytvořit aplikaci jako samostatný program, kde by volba síťové role byla ponechána na uživatelově rozhodnutí.

3.4.1

Architektura klient/server

Klient-server je síťová architektura, která rozlišuje 2 druhy programů - server a klient. Server zajišťuje logiku programu a umožňuje připojení klientů. Klient obsahuje rozhraní, které slouží pro připojení k serveru po síti, a pomocí tohoto rozhraní se serverem komunikovat. Komunikace probíhá ve formě požadavků, které server vyhodnotí, a pošle klientovi odpověď, který ji v našem případě zobrazí uživateli. V aplikaci umožňující hrát poker po síti by tato architektura byla implementována tím způsobem, že by se vytvořily 2 různé programy, přičemž jeden z nich by představoval server a druhý klienta. Server by obsahoval veškerou logiku programu zahrnující implementaci pravidel a umělou inteligenci, zatímco klient by pouze přijímal a zobrazoval informace o stavu hry. Nemusel by provádět žádnou kontrolu správnosti, jediná funkcionální věc, která by se od něj vyžadovala, je možnost odeslat rozhodnutí o klientově tahu, jehož vyhodnocení bude ale zajišťovat až server. Výhodou této architektury je, že umožňuje úplné oddělení logiky serveru a logiky klienta. Protože se jedná o různé programy, umožňuje tato architektura vytvořit více různých klientů dle potřeby, dokonce i v různých programovacích jazycích. Pokud budou implementovat stejný protokol, budou všichni schopni komunikovat se serverem.

3.4.2

Samostatná aplikace

Vytvoření programu jako samostatné aplikace by znamenalo vytvořit pouze jeden program, který by se v závislosti na nastavení choval buď jako server nebo jako klient. Toho by mohlo být dosáhnuto například dvěma různými možnostmi v menu nebo výběrem odpovědi na otázku položenou při startu aplikace. Tento způsob má dvě velké výhody oproti klient/server architektuře. První výhodou je skutečnost, že části programu, které klient a server sdílí, se nacházejí pouze na jednom místě.

18

V tomto případě se jedná například o grafiku programu, způsob zobrazování informací, způsob vybírání hráčova rozhodnutí nebo správu nastavení programu. Druhou výhodou je vyšší uživatelská přívětivost, protože pro uživatele je jednodušší ovládat jednu aplikaci než dvě. Kromě toho tento způsob umožňuje měnit síťovou roli, aniž by musel uživatel vypínat aplikaci.

3.4.3

Zhodnocení a výběr architektury

Výhody jednotlivých architektur byly již popsány výše a možnost vytváření různých klientských programů není u karetní hry nijak zásadní. Mnohem důležitější je jednoduchost ovládání a v tom jasně vítězí architektura samostatné aplikace. Z implementačního hlediska je tento způsob také vhodnější, protože klientská část programu bude sdílet velkou část zdrojového kódu se serverovou částí. Aplikace tedy bude implementována jako samostatný program.

19

20

Kapitola 4 Realizace V této kapitole je stručně uvedena funkcionalita jednotlivých balíčků tříd a poté jsou rozebrány některé postupy a algoritmy použité při programování umělé inteligence.

4.1

Funkcionalita balíčků

Důraz byl při implementaci programu kladen na přehlednost a případnou znovupoužitelnost jednotlivých částí programu, v důsledku čehož jsou třídy rozděleny do balíčků podle funkce, kterou zajišťují. Seznam balíčku je následující: • configuration, • engine, • engine.AI, • engine.handEvaluation, • engine.player, • enumerations, • interfaces, • network, • network.packets, • view, • view.dialog, • view.events. 21

4.1.1

Configuration

Balíček configuration zajišťuje správu konfigurace výchozích a systémových hodnot, jejich načítání, ukládání a možnost jejich změny. Jeho druhou funkcí je správa externích textů a popisků, které se načítají ze souboru, což umožňuje podporu vícejazyčnosti.

4.1.2

Engine

Engine je na počet tříd nejobsáhlejší balíček a jeho cílem je implementovat logiku programu. Obsahuje třídy reprezentující logické komponenty jako stůl, karty nebo bank. O koordinaci se stará třída GameController, která pro start hry zavolá buď třídu GameServer nebo třídu GameClient v závislosti na síťové roli dané instance programu. Engine.AI Všechny třídy, které se podílejí na vytváření rozhodnutí počítačového hráče, jsou v balíčku engine.AI. Celý balíček pracuje nezávisle na ostatních třídách a hlavní třída DecisionMaker je připojena k logice aplikace přes definované rozhraní. Engine.handEvaluation V tomto balíčku jsou shromážděny všechny třídy pracující na závěrečném vyhodnocení vítězného hráče. Princip vyhodnocování je vysvětlen v sekci 4.2.1. Engine.player Ve hře jsou celkem tři druhy hráčů. Hlavní hráč je člověk hrající na dané instanci spuštěného programu, síťový hráč je někdo vzdáleně připojený a počítačový hráč je hráč ovládaný počítačem. Každý má svá specifika, každý má různý způsob zjišťování herního rozhodnutí, ale většinu věcí sdílí. Tyto tři třídy společně s jejich abstraktním předkem jsou uloženy v balíčku engine.player.

4.1.3

Interfaces

V balíčku interfaces se nacházejí rozhraní pro všechny grafické elementy, které nějakým způsobem reflektují stav logických komponent. Díky tomu je velmi jednoduché vyměnit grafický element za jakýkoliv jiný, pokud bude implementovat dané rozhraní. V tomto balíčku se nachází i několik rozhraní pro logické třídy umělé inteligence a vyhodnocování vítězných karet.

22

4.1.4

Network

Network je balíček zodpovědný za síťovou komunikaci aplikace se serverem nebo s klienty. Network.packets obsahuje serializovatelné třídy, jejichž instance slouží jako datové jednotky určené k odeslání druhé straně.

4.1.5

View

V balíčku view jsou uloženy třídy, které zobrazují uživateli informace uložené v logických komponentách. S těmi komunikují prostřednictvím rozhraní, které implementují. Příkladem takového vztahu může být karetní stůl. Všechna data o kartách a o sázkách jsou uložena v logické třídě Table v balíčku engine, ale tato data je potřeba zobrazit a k tomu slouží třída TablePanel v balíčku view. View.dialogs View.dialogs shromažďuje dialogy umožňující okamžitý zisk informace od uživatele. Příkladem může být dialog InitialInformationDialog, který se spustí ihned po spuštění programu a který se ptá na jméno a počáteční vklad hlavního hráče.

4.2

Ohodnocení karetní kombinace

První a nejdůležitější věc při implementaci pravidel pokeru je vytvořit vyhodnocovací funkci, která dokáže určit vítěze daného kola. Taková funkce musí dostat jako parametr kombinaci sedmi karet a jako výsledek vrátit číslo, které bude vyšší, než by dostala kombinace horší, a zároveň nižší než by dostala kombinace lepší. Pro porovnání se používá stupnice kombinací uvedená v pravidlech hry v kapitole 2. Tímto způsobem se ohodnotí všechny kombinace a ta, která dostane bodů nejvíce (resp. nejméně v závislosti na použitém měřítku), je označena jako vítězná. Určení vítěze kola však není jediné využití této vyhodnocovací funkce. Své uplatnění najde také v umělé inteligenci, kde se k určení síly karet a pravděpodobnosti výhry musí provést mnohonásobně opakované vyhodnocení, a to v pokud možno co nejkratším čase. To přidává požadavek na rychlost vyhodnocení, bez kterého by umělá inteligence byla nepoužitelná.

4.2.1

Algoritmus vyhodnocovací funkce

Aby byla vyhodnocovací funkce dostatečně rychlá, není možné použít naivní algoritmy, které by pro každou kombinaci zkoušely, zda odpovídá daným kategoriím. Jedním z důvodů je i to, že karet je celkem sedm, ale program má ohodnotit jen nejlepších pět, které člověk dokáže vybrat snadno, ale počítač už nikoliv. Bez nějakého 23


druhu prořezávání by musel provést 75 = 42 zařazení do kategorie a to tolikrát, dokud by kartu správně nezařadil. Poté by musel ještě nějakým způsobem zohlednit karty, které kombinaci neovlivňují, a na základě toho teprve přiřadit ohodnocení. Tento algoritmus používá při vyhodnocování člověk a počítač ho může také použít, ale pouze pokud by jeho funkce byla určení vítěze kola. Pro využití v umělé inteligenci je rychlost algoritmu výrazně nedostatečná. Lepší výsledky poskytují algoritmy založené na předgenerovaném ohodnocení karetních kombinací, ale tento přístup naráží na paměťová omezení v důsledku velkého
52 počtu kombinací. Celkový počet různých kombinací 7 karet z 52 je 7 = 133784560. Vyhodnocovací funkce navíc dostane karty v náhodném pořadí, což počet záznamů v předgenerované tabulce zvyšuje na 52!/45! = 674274182400, což je zaprvé zbytečné, protože velké množství kombinací bude mít přiřazenu stejnou hodnotu, a za druhé neproveditelné kvůli vysokým nárokům na paměť. Cílem je tedy nějakým způsobem snížit počet záznamů v tabulce na únosnou míru, k čemuž jsem použil algoritmus acyklického orientovaného grafu Moritze Hammera. Princip jeho fungování je detailně vysvětlen na jeho stránkách uvedených v seznamu použitých zdrojů [11]. Při testování tohoto algoritmu jsem dosáhl rychlosti 15000000 ohodnocení za vteřinu a to vše s tabulkou obsahující „pouhýchÿ 76153 záznamů, což splňuje požadavky jak na rychlost, tak na paměťovou únosnost.

4.3

Umělá inteligence

Poker je hra s neúplnou informací, což znamená, že nikdo z hráčů nemá všechny informace o aktuálním stavu hry. Narozdíl od her s úplnou informací jako jsou například Šachy nebo Othello, u kterých je umělá inteligence většinou řešena nějakou formou prohledávání do hloubky a následným prořezáváním, se u pokeru pracuje s nejistotou, pravděpodobností, ale také psychologií hráčů. Co bylo v jednom případě správné rozhodnutí může být ve hře proti jiným protivníkům rozhodnutí špatné. To činí z pokeru, z hlediska programování umělé inteligence, velice zajímavou výzvu. Algoritmy pokerové umělé inteligence jsou velice komplexním tématem a narozdíl od algoritmů ohodnocovací funkce vítězných karet, přístupů k racionálnímu rozhodování počítačem v pokerové hře existuje více. Nejvíce se touto oblastí zabývá výzkumná skupina Computer Poker Research Group na University of Alberta v Kanadě, odkud vzešlo mnoho významných prací o umělé inteligenci v pokeru.

4.3.1

Algoritmus ohodnocení síly karet

Algoritmus ohodnocení síly karet použitý v implementaci programu je založen na metodě Monte Carlo [6]. Princip této metody spočívá v mnohonásobném opakování simulace určité situace a vyvození závěru z výsledků těchto simulací. V případě 24

ohodnocení síly karet se při daných dvou počátečních kartách a daných vyložených kartách na stole simulují náhodné hry proti danému počtu protihráčů a síla karet se vypočítá jako:  Pn  remíza výhra + i=0 počet hráčů s remizující kombinací (4.1) n Proměnná n značí počet provedených simulací, výhra značí vyhranou hru a remíza značí takovou hru, kdy si umělá inteligence dělí s někým výhru kvůli stejnému ohodnocení. Pokud by síla karet vyšla rovna 0, 5, znamená to, že proti danému počtu hráčů s danými kartami bude mít program 50% šanci, že zvítězí.

4.3.2

Výpočet indexu zisku

Samotná síla karet pro hru však nestačí, protože nebere v potaz výši sázek, celkovou výši banku ani rozhodnutí ostatních hráčů. Pro další uvažování je potřeba zavést důležitý termín pot-odds. Pot-odds představuje poměr požadované částky pro to, aby hráč zůstal ve hře, k celkovému objemu banku. Jako příklad se dá uvést situace, kdy je hráč na tahu, musí dorovnat 20, aby zůstal ve hře, a v banku už je dohromady 20 = 18 . Obecně platí, že chce hráč mít 160. Pot-odds bude v tomto případě rovno 160 nižší pot-odds než je šance, že danou hru vyhraje. V opačném případě by musel za možnost zůstat ve hře zaplatit vyšší částku, než kolik je očekávaná střední hodnota zisku z daného rozhodnutí, a v dlouhém období by ztrácel. Z pot-odds a síly karet se dá vypočítat index zisku jako: index zisku =

síla karet pot-odds

(4.2)

Index zisku vyjadřuje pravděpodobnost na výhru v závislosti na částce, kterou je třeba zaplatit pro možnost zůstat ve hře. Hráč by se měl snažit zůstávat ve hrách, ve kterých má index zisku vyšší než 1 a pokládat hned, jak index zisku pod tuto hranici klesne. Příklad 1 V tomto příkladu uvažujeme situaci, kdy jsou na stole 3 karty a ve hře zbývají už jen 2 hráči. První hráč má čtyři karty stejné barvy a je přesvědčený, že druhý hráč drží dvě esa. V banku je z předchozího kola 150 a druhý hráč vsadil 50. Jak by měl první hráč reagovat? Vyhrál by, pokud by se mu podařilo dokončit jeho flush, na který mu chybí už pouze jedna karta. Pravděpodobnost, že ze dvou karet přijde alespoň jedna taková, která by mu pomohla, je přibližně 31 , což znamená, že pravděpodobně prohraje. Stačí mu ale dorovnat pouze 50 na to, aby hrál o bank, ve kterém je

25

dohromady 200. Pot-odds se rovná 41 a index zisku je tedy roven 43 , což je více než 1. Měl by tedy ve hře zůstat a dorovnat. Příklad 2 Uvažujme stejnou situaci, jako v předchozím případě s tím rozdílem, že druhý hráč nevsadil 50, ale 150. Pravděpodobnost na výhru se nezmění, ale pot-odds se budou 150 rovnat 300 = 12 . Index zisku v tomto případě vyjde 23 a správné rozhodnutí je položit.

4.3.3

Rozhodování na základě indexu zisku

Počítačoví hráči v aplikaci se rozhodují na základě indexu zisku. Pokud by se ho ale držely vždy, stalo by se jejich chování pro protivníky snadno čitelné. Proto jsou definována pravidla, která určují pravděpodobnost jednotlivých akcí, pokud bude index zisku náležet do intervalu daného pravidlem. Pravidlo je uspořádaná pětice čísel (ai ; bi ; ci ; di ; ei ). Pokud index zisku spadá do intervalu (ai , bi ), počítačový hráč s pravděpodobností ci karty položí, di určuje pravděpodobnost dorovnání a ei udává pravděpodobnost, že sázku zvýší. Pro intervaly různých pravidel platí, že se nepřekrývají, a pravděpodobnosti jednotlivých akcí dávají pro každé pravidlo součet roven 1. Výběr akce může být demonstrován na vymyšleném pravidle (0; 0, 7; 0, 9; 0; 0, 1). Pokud umělá inteligence zjistí, že index zisku má nižší než 0,7, pak z 90% karty položí a z 10% sázku zvýší, což představuje pokus o bluff. Definice těchto pravidel umožňuje jednoduchým způsobem měnit charakter hráče při zachování mechanismu všech výpočtů. Pokud by se například zdálo, že hráč málo bluffuje, stačí zvýšit hodnotu ei na úkor ci u všech pravidel.

26

Kapitola 5 Testování V této kapitole je popsán způsob testování aplikace a to z hlediska testování použitelnosti, bezchybné implementace logiky programu a kvality umělé inteligence. V rámci testování aplikace byly vytvořeny dvě skupiny testerů. První skupina se skládá z pěti zkušených hráčů pokeru, kteří mají zkušenosti s mnoha programy s pokerovou tématikou a kteří vědí, co mají od implementace pokeru očekávat. Tato skupina se zaměřila na všechny tři testované aspekty aplikace. Druhou skupinu tvoří tři pokeroví začátečníci a jejím cílem je odhalit nejasnosti, které zkušení hráči nezaznamenají, převážně v oblasti uživatelského rozhraní a použitelnosti. Oběma skupinám byl dán čas na testování a poté jim byl předložen dotazník pro poskytnutí zpětné vazby. Součástí této kapitoly je interpretace výsledků z těchto dotazníků.

5.1

Testování použitelnosti

Cílem testů použitelnosti je zjistit, zda je aplikace pro uživatele intuitivní a pochopitelná, zda je vyhovující rozložení prvků na hlavní stránce a v menu, atd. Testování bylo nejprve provedeno skupinou zkušených pokerových hráčů, a protože rozložení prvků v uživatelském rozhraní odpovídá standardnímu rozložení v online pokerových místnostech, bylo ovládání hry bez problémů. Pokeroví laici byli také schopni hrát hru bez problémů, uvedli však námitky, že v aplikaci chybí nápověda a možnost zobrazit pořadí jednotlivých karetních kombinací. Protože koncový uživatel bude mít jako součást programu i kompletní dokumentaci, ve které jsou všechny tyto věci popsány, nebude tento uvedený problém nijak zásadní. Uživatelské rozhraní bylo navrženo tak, aby odpovídalo vzorům, na které jsou hráči pokeru zvyklí, a mohli s ním pracovat hned při prvním spuštění aplikace. Dodatečná funkcionalita zahrnující textovou nápovědu ke kartám, průvodce založením hry nebo internacionalizaci společně s tím přispívá k tomu, že uživatelské rozhraní bylo testery ohodnoceno kladně. 27

5.2

Testování logiky programu

Bezchybná implementace pravidel je základem, bez kterého by byl program nepoužitelný. Testování logiky programu zahrnovalo kontrolu rozdávání karet, hlídání výše sázek, střídání rozdávající pozice, kontrolu funkčnosti síťové komunikace atd. Mezi nejdůležitější aspekty logiky programu patří i vyhodnocování vítězné kombinace a správné přidělení výhry. To zahrnuje testování všech nestandardních situací jako je například dělení výhry mezi více vítězů, korektní rozdělení side-potů v případě, že alespoň jeden hráč vsadil celý svůj vklad, atd. Podle odpovědí v dotaznících implementuje program logiku bezchybně. Protože se jedná o nejdůležitější část fungování aplikace, byl na testování logiky kladen důraz v průběhu celé fáze její implementace. Naprostá správnost dodržování pravidel není úspěchem implementace, ale nutnou podmínkou a jedná se o jedinou možnost, jak mohlo projít testováním jako úspěšné.

5.3

Testování umělé inteligence

Testování umělé inteligence se zaměřovalo na úroveň hry počítačových protihráčů. V testovací hře byli vždy dva počítačoví hráči, a testeři sledovali chování obou z nich, přičemž hlavní důraz byl zaměřen na závislost jejich rozhodnutí v průběhu hry a karet, které odkryli při vyhodnocení. Testovací hra probíhala celkem dvě hodiny a účastnilo se jí pět testerů, autor aplikace a dva počítačoví hráči. Na konci těchto dvou hodin byli hráči seřazeni od nejlepšího podle výše jejich banku a počítačoví hráči se umístili na 4. a 6. místě. Vezme-li se v potaz, že byli nasazeni proti zkušeným hráčům univerzitní pokerové ligy [8], je tento výsledek uspokojivý.

5.4

Srovnání s existujícími aplikacemi

Aplikací s pokerovou tématikou existuje velké množství a některé z nich, včetně základní kategorizace a srovnání s touto aplikací, byly uvedeny v sekci 1.4. Některé umožňují hru lidských hráčů po síti, jiné hru proti počítači, ale dosud jsem se nesetkal s programem, který by oba přístupy dokázal kombinovat. To činí z výsledku této práce unikátní program, protože poskytuje prostředí, ve kterém mohou lidé hrát proti sobě bez nutnosti placení poplatku provozovateli serveru. Nedostatek hráčů se dá vyřešit zapojením počítačových hráčů a ostatní parametry hry nastavit, což dohromady tvoří komplexní pokerový software. Ten najde nejlepší uplatnění jako doplněk pro skupiny hráčů, které se pravidelně scházejí k živé hře.

28

Kapitola 6 Závěr Výsledkem této práce je funkční aplikace, která umožňuje hrát karetní hru poker. Aplikace podporuje hru více hráčů po síti a obsahuje umělou inteligenci pro hru proti počítačovým protivníkům. Součástí práce bylo i testování, kterého se zúčastnily dvě nezávislé skupiny testerů, a aplikace byla ve všech aspektech, včetně testování umělé inteligence, ohodnocena pozitivně. S ohledem na zadání se tedy cíle práce úspěšně podařilo naplnit. Funkcionalita nad rámec zadání se týká převážně uživatelského rozhraní, které poskytuje široké možnosti nastavení herních a výchozích hodnot, vícejazyčnost, průvodce založením hry nebo textovou nápovědu ke kartám. Implementace pravidel představuje kompletní komponentu a neumožňuje již žádné další vylepšení. Nejvíce prostoru pro možnost pokračování projektu poskytuje oblast umělé inteligence, která se dá vyvíjet nezávisle na ostatních programových komponentách. Příkladem vylepšení úrovně počítačového hráče může být implementace modelování oponentů, které zahrnuje uchovávání historie provedených akcí ke každému hráči. Na základě té se dá určit jeho herní styl, což poslouží pro zkvalitnění odhadu jeho karet. Mezi další strategické prvky, které by excelentní umělá inteligence měla umět, patří poziční hra, slow-playing, adaptivní učení, mechanismy pro efektivní využívání chyb protivníků, a další. Přínosem této práce je umožnění hry proti lidským i počítačovým hráčům zároveň, mimo to však aplikace poskytuje rozhraní pro libovolnou implementaci tříd, které na základě stavu hry dokáží provést pokerové rozhodnutí. Dá se tedy použít jako prostředí pro testování pokerové umělé inteligence, které bych se chtěl věnovat v rámci své diplomové práce.

29

30

Literatura [1] R. Harroch, L. Krieger: Poker for Dummies, John Wiley & Sons Inc., 2000 [2] Darse Billings: Computer poker, Department of Computing Science, University of Alberta, 1995 [3] J. Nielsen: Usability Engineering, Academic Press Inc., 1994 [4] Denis Papp: Dealing with Imperfect Information in Poker, Department of Computing Science, University of Alberta, 1998 [5] Darse Billings: Algorithms and Assesment in Computer Poker, Department of Computing Science, University of Alberta, 2006 [6] Jonathan Pengelly: Monte Carlo methods, 2002 [7] Seznam televizních pořadů o pokeru http://www.mujpoker.cz/poker-forum/35/porady-o-pokeru [8] Stránky univerzitní pokerové ligy Unipoker http://www.unipoker.cz/ [9] Stránky České asociace Go http://www.goweb.cz/ [10] Stránky softwaru Texas Calculatem http://www.calculatem.cz [11] DAG algorithm by Moritz Hammer http://www.pst.ifi.lmu.de/ hammer/poker/handeval.html [12] Computer Poker Research Group at University of Alberta http://poker.cs.ualberta.ca/

31

32

Příloha A Slovník pojmů all-in

-

vsazení všech herních peněžních prostředků

big blind

-

velká povinná sázka, minimální hodnota sázky

blind

-

povinná sázka, která se sází dříve než se rozdají karty

bot

-

počítačový hráč

cash game

-

varianta hry, kdy žetony představují reálné peníze

dealer

-

rozdávající hráč

limit

-

varianta hry, ve které je pevně daná výše sázek

no-limit

-

varianta hry, ve které není omezena výše sázek

pot

-

celková výše sázek v dané hře

pot-odds

-

poměr minimální sázky pro setrvání k celkové výši potu

pot-limit

-

varianta hry, ve které je výše sázek omezena velikostí banku

rake

-

poplatek kasínu z každé odehrané hry

side-pot

-

vedlejší pot pro hráče, kteří již nemají co vsadit

slow-playing

-

záměrné nezvyšování s výbornými kartami

small blind

-

malá povinná sázka, většinou poloviční hodnota big blindu

33

34

Příloha B Instalační a uživatelská příručka Tato příloha popisuje instalaci aplikace včetně adresářové struktury obsahu přiloženého CD a postupu, jak aplikace spustit. Dále se věnuje základním ovládacím prvkům programu.

B.1

Obsah přiloženého CD

Na přiloženém CD se nachází čtyři adresáře, každý se specifickým obsahem týkajícím se této práce. Celková adresářová struktura je následující: • Application – configuration – data – images – language • Forms • Source – application – document • Text Adresář Application obsahuje funkční verzi programu a dále podadresáře uchovávající konfigurační soubory, pravidla pro umělou inteligenci, obrázky a data pro jazykové mutace programu. Adresář Forms obsahuje dotazníky, které byly vyplněné 35

v rámci testování aplikace pro získání zpětné vazby, a adresář Text obsahuje konečnou podobu dokumentace. Zdrojové kódy k projektu aplikace v prostředí NetBeans 6.1 a zdrojové kódy textu práce v prostředí TeXnicCenter se nacházejí v adresáři Source a slouží převážně jako reference způsobu tvorby práce.

B.2

Instalace a spuštění

Aplikace nevyžaduje instalaci a je možné ji spustit ihned po zkopírování. Je nutné pouze zachovat adresářovou strukturu programu a v případě ukládání nastavení mít povolen zápis do daného adresáře. Na CD zápis není povolen a proto je doporučeno adresář Application před spuštěním zkopírovat na pevný disk. Nejjednodušší způsob spuštění aplikace je kliknutí na soubor PokerSoftware.jar, který se nachází v adresáři Application. Z příkazové řádky téhož adresáře je možné spustit program příkazem: java -jar PokerSoftware.jar

B.3

Ovládání aplikace

V této sekci je popsán způsob ovládání důležitých prvků grafického uživatelského rozhraní aplikace.

B.3.1

Menu

V menu se nacházejí čtyři základní kategorie: Hra, Síťové připojení, Nastavení a Nápověda. Menu hra obsahuje možnosti spuštění hry, zastavení hry a ukončení programu. Volba ukončující program je dostupná z každého stavu aplikace, ale zbylé dvě možnosti se navzájem vylučují a je tedy aktivní vždy pouze jedna z nich. Síťové připojení umožňuje povolit připojení vzdáleným uživatelům, což je volba, kterou je možné zapnout i v průběhu rozehraného kola. Noví hráči se mohou ke hře hned připojit a pozorovat ji, hrát však mohou až od dalšího kola. Další možnost položky menu Síťové připojení - připojení se k síťové hře - vyžaduje ukončení rozehrané hry, protože se veškeré herní informace budou přebírat od serveru. Nastavení umožní otevření dvou dialogů, nastavení výchozích hodnot a nastavení hry, a poslední položka v menu zobrazí informace o programu.

B.3.2

Hlavní pohled

Po zapnutí aplikace a nastavení informací o hráči se otevře hlavní pohled. Volné pozice, na které může hráč usednout nebo na ně usadit počítačového hráče, jsou 36

označeny ikonou s křeslem, která znázorňuje volné místo u stolu. Obsadit pozici je možné kliknutím na ní a vybráním akce z nabízeného seznamu možností. V levém dolním rohu je prostor pro zobrazování historie hry a pro zasílání textových zpráv soupeřům a v pravém dolním rohu se nachází rozhodovací panel, ve kterém činí hráč všechna svá rozhodnutí během hry. Prostřední panel představuje pokerový stůl, na který jsou v průběhu hry vykládány hrací karty a na kterém se zobrazuje měnící se výše potu.

Obrázek B.1: Hlavní obrazovka

B.3.3

Nastavení

Nastavení je v aplikaci dvojího druhu. Nastavení výchozích hodnot umožňuje nastavit hodnoty, které se zobrazují jako výchozí u programových dialogů. Kromě informací o hráči a hodnot síťového připojení je možné nastavit výchozí jazykovou 37

mutaci, která se v programu nastaví při jeho spuštění. Druhý dialog pracuje s herními proměnnými a jejich hodnoty jsou závazné, takže nemusí být nejprve potvrzeny jako hodnoty výchozí. Mezi tyto proměnné patří výše sázek, současná jazyková verze programu a trojice časových intervalů. Tyto intervaly zahrnují časový údaj doby trvání tahu počítačového hráče a dobu, po kterou jsou zobrazeny karty všech hráčů zbývajících ve hře při vyhodnocení.

Obrázek B.2: Výchozí hodnoty

Obrázek B.3: Herní hodnoty

38