Raport z projektu na wykład ze sztucznej Inteligencji

Komputerowy gracz do gry texas hold'em

Kacper Górski
23 czerwca 2008

Wstęp

Texas hold'em to bardzo młoda odmiana pokera, jej początki sięgają roku 1970, jednak spopularyzowana została dopiero w połowie lat 90. Pomimo swojego młodego wieku szacuje się, że już teraz jest najbardziej popularną grą karcianą w amerykańskich i europejskich kasynach.

Opis problemu

Zasady gry

Podstawową różnicą pomiędzy teksańskim, a zwykłym pokerem jest to, że każdy gracz otrzymuje od rozdającego tylko dwie karty. Pozostałe karty (których jest pięć) są kartami wspólnymi i są one odsłaniane w kolejnych rundach. Wygrywa osoba, która dotrwa do końca każdej z czterech licytacji i ma najlepsze karty (osoba wybiera najlepsze ułozenie pięciu kart z dwóch kart prywatnych i pięciu kart publicznych).

Przykładowy pojedynek dwóch graczy
rys. 1 - Przykładowy pojedynek dwóch graczy


Modyfikacje te czynią grę znacznie ciekawszą ze względu na:

Sztuczna inteligencja

Celem projektu jest stworzenie programu, który byłby w stanie samodzielnie rozgrywać partie, tzn. podejmować decyzje dotyczące wysokości stawki, przebijać innych graczy lub pasować.
Ponieważ zasady gry umożliwiają przeprowadzenie analizy prawdopodobnego układu kart przeciwnika, być może uda sie skonstruować program, który będzie w stanie konkurować z żywym przeciwnikiem.
Na chwilę obecną można sciągnąć i przetestować kilka eksperymentalnych programów do gry w teksańskiego pokera, jednak okazało się, że podczas turniejów 'człowiek kontra maszyna' wygrywa zawsze ten pierwszy.
Nie udało mi sie znaleść w sieci literatury, która poruszałaby problem sztucznej inteligencji w teksańskim pokerze, toteż pomysł na napisanie sztucznego gracza podpowiedziała mi własna intuicja.

Srodowisko programowania

Część implementacyjna projektu jest napisana w Javie 1.5
Ponadto do obliczeń ewolucyjnych użyto biblioteki Wevo, napisanej przez studentów informatyki Uniwersytetu Wrocławskiego.

Opis rozwiązania

Ze względu na prostote gry i brak potrzeby angażowania dużej mocy obliczeniowej w rozgrywanie partii (średniej klasy komputer jest w stanie zasymulować kilkadziesiąt tysięcy partii na sekundę) zdecydowano się rozwiązać problem za pomocą algorytmów ewolucyjnych.
Zaimplementowano zbiór 105 reguł decyzyjnych, które definiują gre sztucznego gracza. Reguły te są bardzo proste, np:
Działanie programu grającego w pokera można podzielić na dwie fazy:

Pierwsza faza musi być przeprowadzona tylko raz, po czym wyuczony sztuczny gracz może rozpocząć rozgrywki.

W projekcie w trakcie fazy uczącej użyto algorytmów ewolucyjnych do odsiania złych reguł.
W procesie ewolucji sztuczny gracz jest osobnikiem i konkuruje z innymi sztucznymi graczami w populacji. Funkcją celu jest wartość wygranej/przegranej w pewnej liczbie gier przeciw wirtualnym przeciwnikom generowanych przez funkcję celu.

Kodowanie osobnika

Każdy gracz jest postaci wektora 105 liczb binarnych. Kazdy bit odpowiada za jedną ze 105 reguł definiujących zachowanie gracza. Reguły mogą odpowiadać ze wysokość stawki, skłonność do spasowania, bądz sprawdzania. Ustawienie wartości bitu na 1 oznacza, że dana reguła jest stosowana przez gracza, wartość 0 oznacza, że nie jest ona brana pod uwagę.

Przykładowy osobnik
rys. 2 - Przykładowy osobnik

Funkcja celu

Wartością funkcji celu jest bilans kwoty wygranej/przegranej, jaki osobnik osiągnął w pewnej liczbie gier przeciwko graczom wygenerowanym przez funkcje celu.
Liczbę gier ustalono na 5000, minimalną stawkę na 10, zaś ciąg gier, ułożenie przeciwników i rozkład kart jest powtarzalny, tzn. przy obliczaniu funkcji celu dla dwóch róznych osobników rozgrywają one taki sam ciąg gier, z takimi samymi przeciwnikami i identycznymi kartami.
Przykładowo, jeśli osobnik osiągnał wartość funkcji celu 100.000, to wygrał 10.000 stawek minimalnych, średnio dwie na grę.

Proces uczenia

Pierwszym krokiem uczenia programu jest stworzenie odpowiedniej liczby przeciwników, na których będzie on w stanie nauczyć się grać. Przeciwnicy ci muszą spełniać pewne wymagania:

Na początku procesu uczenia dysponujemy tylko i wyłącznie osobnikami losowymi, których gra jest słaba lub beznadziejnie słaba.
Do wytrenowania przeciwników posłużono sie także algorytmami ewolucyjnymi. Wykorzystano do tego trzy różne funkcje celu:
1. Przeciwnikami są gracze losowi
2. Przeciwnikami są gracze I generacji
3. {rzeciwnikami są gracze II generacji

Pierwszym krokiem było uruchomienie prostego algorytmu ewolucyjnego z funkcja celu (1) i wygenerowanie 300 osobników dominujących w populacji (nazwijmy ich generacją I).
W drugim kroku funkcję celu (1) zastąpiono (2) i wygenerowano 300 osobników generacji II.
Ostatnim krokiem było uruchomienie bardziej wyszukanego algorytmu ewolucyjnego z funkcją celu (3) i wygenerowanie najlepszego osobnika.
W tym kroku próbowano algorytmów ECGA, BOA, selekcji/mutacji oraz selekcji/krzyżowania. Najlepszy rezultat dawał algorytm oparty na selekcji/mutacji, po 20 minutach działania wartość funkcji celu przekraczała 500.000.

Cały proces został zilustrowany na rysunku:
Proces uczenia
rys. 3 - Proces uczenia

Testy

Pojedynek reprezentantów różnych grup

Wybrano reprezentantów każdej z wygenerowanych generacji i kazano im rozegrać 5000 partii z przeciwnikami z innych generacji. (czyli zaaplikowano im kolejno funkcje celu nr.1, 2 i 3). Wyniki w poszczególnych komórkach oznaczają bilans pieniężny osobnika po rozegraniu 5000 gier przeciwko osobnikom z danej generacji.


Gracz Losowy I generacja II generacja Najlepszy osobnik
Losowy -13.730 741.444 185.140 743.830
I generacja-24.000 102.115 152.562 907.146
II generacja-22.455 -129.632 59.419 530.182

Test wykazał, że osobniki były w stanie pokonać przeciwników z każdej poprzedniej generacji.
Jest to pożyteczna obserwacja, gdyż oznacza to, że osobniki nie są uczone wygrywać tylko z przeciwnikami, na których bezpośrednio trenują.

Próba gry z człowiekiem

Wzięto najlepszego osobnika i rozegrano ok. 30 partii w serwisie internetowym przeciwko pięciu innym żywym graczom za wirtualne pieniądze. Gra odbywała sie za pośrednictwem GUI serwisu internetowego, toteż przez cały okres gry niezbędny był człowiek, który dostarczał informacje o ruchach przeciwników do sztucznego gracza i na odwrót.
Po około półtorej godzinie gry sztuczny gracz zanotował stratę 53 stawek minimalnych.
Oczywiście program wygrywał niektóre partie, jednak w miare przebiegu testów dawała się zauważyć tendencja do pogłębiania debetu. Prawdopodobnie tendencja ta utrzymałaby się dalej, aż w końcu program przegrałby całą dostępną kwotę.
Na niekorzyść programu przemawia ponadto fakt, iż jego przeciwnicy nie byli świadomi, iż grają z komputerem, w przeciwnym wypadku staraliby się odnaleść jego słabości, aby ograć go z większej ilości pięniędzy.

Wnioski

Najśmielszy cel projektu - ogranie żywych graczy z ich ciężko zarobionych pięniedzy nie został osiągnięty. Udało się jednak stworzyć sztucznego gracza, który nie kompromituje się swoją grą i którego można niedużym nakładem pracy poprawić, np. poprzez:

Perspektywy kontynuacji projektu oceniam jako bardzo obiecujące.

Dużym atutem sztucznego gracza jest to, że gra on całkowicie bezemocjonalnie, taki gracz nie ulegnie euforii po kilku wygranych, ani nie będzie miał chęci odgrywania.
Być może gdyby poświecić odpowiednią ilość czasu na udoskonalenie osobnika byłby on w stanie ogrywać ludzi z prawdziwych pieniędzy za pośrednictwem wirtualnego kasyna? (być może już są i udawają żywych graczy?)

Przykłady

Przykładowa partia 6 wytrenowanych graczy generacji II


Ranking wylosowanych graczy (funkcja celu nr.3):
Gracz 1 -12110.0
Gracz 2 28133.75
Gracz 3 126163.74999999999
Gracz 4 83849.58333333336
Gracz 5 74246.25
Gracz 6 -12110.0

Wylosowane rozdanie:
publiczne karty: & 2 kier & walet pik & 9 karo & walet karo & 9 pik
Gracz 1: & 6 karo & as kier
Gracz 2: & dama trefl & as trefl
Gracz 3: & as pik & 3 kier
Gracz 4: & 7 trefl & 5 karo
Gracz 5: & 8 pik & 7 pik
Gracz 6: & dama pik & 5 kier

runda 1
Gracz 1 spasowal
Gracz 2 stawia 150.0 pula 165.0
Gracz 3 stawia 150.0 pula 315.0
Gracz 4 stawia 150.0 pula 465.0
Gracz 5 stawia 150.0 pula 605.0
Gracz 6 spasowal

runda 2
Gracz 2 stawia 50.0 pula 655.0
Gracz 3 stawia 60.0 pula 715.0
Gracz 4 stawia 60.0 pula 775.0
Gracz 5 spasowal
Gracz 2 spasowal

runda 3
Gracz 3 stawia 110.0 pula 885.0
Gracz 4 stawia 110.0 pula 995.0

runda 4
Gracz 3 stawia 190.0 pula 1185.0
Gracz 4 stawia 190.0 pula 1375.0

wygrani:
Gracz 3

Literatura i odnośniki

  1. Szczegółowe zasady gry, Wikipedia - zasady gry.
  2. Wevo, Strona biblioteki Wevo do obliczeń ewolucyjnych
  3. IlliGAL, Strona główna Illinois Genetic Algorithms Laboratory - twórców algorytmów BOA i ECGA
  4. Turniej człowiek kontra maszyna, Strona turnieju, w którym corocznie testowany jest program 'Polars' w pojedynkach przeciw ludzkim graczom.
  5. gamedesire, Serwis, na którym można grać w teksańskiego pokera za pośrednictwem internetu.