Texas hold 'em - budowanie strategii gracza w oparciu o model przeciwnika

0. Abstract (eng.)

The report describes construction of mechanism that is trying to learn opponent's strategy and basing on few observations build its own strategy.
Opponent's behaviour is being represented by behavioral tree, individual in each stage of the game (pre-flop, flop, turn). Each node represents state of betting round with possible actions of FOLD, CALL or RAISE, which leads to another node.

Every node contains following informations:

How many times this node has been visited
How good cards opponent had when visited this node

Basing on those informations and on estimating its own hand strength AI approximates its chances for win.

1. Opis zadania

Zadanie polegało na stworzeniu mechanizmu gracza do gry karcianej Poker (odmiana Texas hold 'em).
Głównym założeniem było tworzenie modelu przeciwnika i opieranie swojej strategii na przewidywaniu zachowań w oparciu o wykreowany model.

2. Środowisko implementacji i testowania

Na potrzeby projektu autor w języku Java stworzył środowisko które umożliwiło implementację oraz testowanie budowanego mechanizmu. Program został załączony do raportu.

Środowisko implementacji i testowania

Rys 1. Środowisko użyte do implementacji oraz testowania

3. Podstawowe problemy

Podczas budowania modelu przeciwnika w grze w pokera pojawia się wiele przeszkód. W grze pojawia się problem niepełnej informacji. Nie jesteśmy w stanie przewidzieć jakie karty ma przeciwnik, możemy czynić jedynie obserwacje jego zachowań i analizować je. Niepewność informacji często może być wykorzystywana do blefowania. Dodatkowo występuje losowość kart.
Nie jesteśmy w stanie przewidzieć jakie karty pojawią się w poszczególnych etapach gry. Ponadto każda rozegrana partia tylko nieznacznie przybliża nas do zbudowania porządnej strategii przeciwnika, a niektóre wcale (gdy jeden z graczy pasuje nie możemy poznać kart przeciwnika)

4. Ocena ręki

Aby zbudować model przeciwnika potrzebna jest ocena ręki (kombinacja kart prywatnych z publicznymi), zarówno gracza jak i przeciwnika.
Oczywistym jest, że od siły ręki zależy w znaczącej mierze szansa na wygraną, a co za tym idzie – sposób gry w danym rozdaniu. To właśnie na podstawie oceny ręki opierać będziemy wszelkie wnioski potrzebne, do budowy modelu przeciwnika.

Do oceny siły ręki kart prywatnych użyty został ranking zbudowany na podstawie rzeczywistych rozgrywek (przeskalowany na wartości z zakresu [0,1]):

Tier	Hands	EV
1	AA, KK, QQ, JJ, AKs	1 - 0.39
2	AQs, TT, AK, AJs, KQs, 99	0.3 - 0.19
3	ATs, AQ, KJs, 88, KTs, QJs	0.16 - 0.10
4	A9s, AJ, QTs, KQ, 77, JTs	0.9 - 0.7
5	A8s, K9s, AT, A5s, A7s	0.5 - 0.04
6	KJ, 66, T9s, A4s, Q9s	0.04 - 0.025
7	J9s, QJ, A6s, 55, A3s, K8s, KT	0.02 - 0.005
8	98s, T8s, K7s, A2s	0.00
9	87s, QT, Q8s, 44, A9, J8s, 76s, JT	(-) 0.1

Tab 1. Tabela oceny kart prywatnych - używana w fazie pre-flop ( 's' - suited, jednakowego koloru).

W ocenie ręki dla dalszych etapów gry została użyta następująca hierarchia:

Rank	Karty
8	Straight flush (np. [A K Q J 10], ale tego samego koloru np. pik)
7	Four of a kind (cztery takie same figury, np. [A A A A])
6	Full house (trójka i dwójka jednocześnie, np. [A A K K K])
5	Flush (pięć kart tego samego koloru, np. pik)
4	Straight (jak poker, ale różnych kolorów)
3	Three of a kind (np. [A A A])
2	Two pairs (np. [A A K K])
1	Pair (np. [A A])
0	High card (najwyższa karta w ręce np. dla [A 10] jest to A)

Tab 2. Tabela oceny kart używana w fazach flop oraz turn.

W oparciu o ww. zasady oceny ręki będzie budowany model zachowań.

5. Szczegóły rozwiązania

5.0 Reprezentacja wiedzy - możliwe podejścia

Do opisu zachowań, akcji i strategii przeciwnika można podejść na różne sposoby oraz z użyciem róźnych technik i struktur.
Jedno z podejść - użycie sieci neuronowych [1]. Zaletami sieci są: ogólny system modelowania, odporność na szum (braki informacji). Wady: trudniejsze w implementacji, trudniejsze w analizie.
Inna możliwość - drzewa decyzyjne [1]. Zalety: łatwość analizowania rozwoju i zawartości drzew. Wady: mniejsza odporność na szum.
Alternatywnie - zestawy informacji (information sets) + analiza rozkładu [2]. W tym modelu, zapamiętujemy wszystkie dotychczasowe rozdania, wraz z akcjami wykonanymi przez oponenta. Aby przewidzieć prawdopodobieństwo wystąpienia danej akcji liczy się prawdopodobieństwo warunkowe na rozkładzie wszystkich dostępnych danych. Zalety: oparcie o solidne obliczenia, łatwość implementacji. Wady: mało realistyczny model, duża złożoność pamięciowa.

5.1 Reprezentacja wiedzy - rozwiązanie użyte

Do modelowania zachowań przeciwnika w tym projekcie użyte zostały użyte drzewa, charakteryzujące dotychczasowe zachowania przeciwnika (drzewa behawioralne). Struktura była niezbyt trudna w implementacji, łatwa w obserwacjach i ewentualnym debugowaniu oraz (jak się później okaże) daje satysfakcjonujące rezultaty. W ww. strukturze każdy wierzchołek zawiera w sobie informację o tym, ile razy został odwiedzony przez przeciwnika (counter) oraz (jeśli taka informacja była dostępna) jaki dobre karty posiadał on wykonując daną akcję (avgCard).
Każdy węzeł reprezentuje aktualne zaawansowanie licytacji z możliwymi akcjami fold(pas), call(wyrównanie,sprawdzenie), raise(podniesienie stawki).
Dodatkowo aby ograniczyć rozrastanie się drzewa ustalony został limit=2 dla akcji raise.

Drzewo zachowań

Rys 2. Drzewo reprezentujące dotychczasowe zachowania przeciwnika

Model przeciwnika zbudowany jest z trzech takich drzew, odpowiednio dla etapu PRE-FLOP, FLOP, TURN.
W etapie PRE-FLOP obu graczom znane są tylko ich prywatne karty a pole avgCard to średnia arytmetyczna dotychczasowych, znanych wartości kart przeciwnika, ocenianych zgodnie z [Tab 1].
Drzewa etapów FLOP oraz TURN różnią się od drzewa dla PRE-FLOP wartością avgCard - w tym wypadku jest to średnia arytmetyczna wartości zgodnie z [Tab 2], przykładowo:
W etapie FLOP, przeciwnik znając 2 karty prywatne i 3 karty publiczne wiedział, że w danym momencie ma 2 pary (rank = 2, [Tab 2]) i postanowił podbić stawkę (raise). Wtedy dla danego węzła w drzewie obliczamy nową wartość avgCard biorąc pod uwagę zdobytą informację. W przyszłości na podstawie zdobytych informacji SI będzie mogła oszacować rękę przeciwnika dla danego węzła i porównać z własną ręką.

5.2 Schemat działania algorytmu

Oprócz modelowania strategii przeciwnika (eksploracja) stworzony mechanizm stosuje zdobytą wiedzę do wzmacniania swojej strategii (eksploatacja).
Algorytm można opisać następującym schematem blokowym:
Schemat algorytmu

Rys 3. Schemat przebiegu algorytmu grającego

6. Wyniki i analiza

Mechanizm został przetestowany na próbce 5 badanych osób. Każda z nich rozegrała 20 rozdań, aby utrudnić człowiekowi szybką wygraną z SI ustalony został limit pojedynczego podniesienia stawki na 10$.
Poniższe wykresy przedstawiają stan konta zaprogramowanego agenta w kolejnych rozdaniach.

Wykres dla gracza A

Rys 4. AI vs gracz A

Rys 5. AI vs gracz B

Rys 6. AI vs gracz C

Rys 7. AI vs gracz D

Rys 8. AI vs gracz E

Biorąc pod uwagę prostotę algorytmu wyniki można uznać za satysfakcjonujące, gdyż sztuczna inteligencja potrafiła przez długi czas utrzymać stan konta wyższy niż przeciwnika.
Ponadto napawać optymizmem może fakt, że SI mimo serii porażek potrafi wyciągnąć z nich wnioski i stopniowo użyć ich w dalszych etapach gry aby odzyskać stracone pieniądze (rys. 5,6,7).
Dodatkowo rysunki 7 i 8 sugerować mogą, że dobry start algorytmu potrafi doprowadzić do długiej serii wygranych. Również faktem wartym zauważenia jest to, że testowane osoby znały strategie gry w pokera (na poziomie przynajmniej średnim), a ponadto starały się znaleźć słabe punkty algorytmu i wykorzystać je na swoją przewagę. Można pokusić się o stwierdzenie, że zarówno SI próbowała uczyć się strategii gracza, jak również gracz starał się odwzajemnić tym samym. Jeśli zatem wykresy przyjmiemy jako wyznacznik szybkości uczenia się obu graczy, to wyniki można uznać za przyzwoite.

7. Dalsze rozważania

Wyniki przedstawionego rozwiązania dla danego problemu wróżą dobrze na przyszłość.
Algorytm można spróbować ulepszyć eksperymentując, próbując otrzymać lepsze rezultaty przez zmianę współczynników losowości dla danych akcji. Analiza ta, może posłużyć jako podstawa do dalszych rozważań, a sam mechanizm rozbudować można o nowe strategie, takie jak blefowanie czy uczenie się ze wzmocnieniem.

8. Literatura

1. Metody Sztucznej Inteligencji do budowania mocnego gracza w Pokerze (http://www.mini.pw.edu.pl/~mandziuk/25-10-06.pps)
2. Bayes’ Bluff: Opponent Modelling in Poker (http://arxiv.org/ftp/arxiv/papers/1207/1207.1411.pdf)
3. Texas hold 'em starting hands (http://en.wikipedia.org/wiki/Texas_hold_%27em_starting_hands)
4. A Guide to Texas Hold'em Poker (http://www.how-to-hold-a-party.com/downloads/HowToPlayPoker.pdf)
5. Gry umysłowe: człowiek kontra maszyna (http://riad.usk.pk.edu.pl/~lscislo/doc/Krakow_24_04.pdf)