Poker "rozwiązany" - opracowano strategię, która zawsze wygrywa

Naukowcom z Uniwersytetu Alberty udało się stworzyć coś, co jeszcze 10 lat temu wydawało im się nieosiągalnym marzeniem. Napisali program komputerowy, który zawsze wygrywa w pokera. To olbrzymie osiągnięcie nie tylko z punktu widzenia tej gry, ale też całej informatyki, a jego wpływ na współczesny świat może znacząco wykroczyć poza gry karciane.

Teoria gier wyróżnia ich dwa rodzaje. Gry o doskonałej i niedoskonałej informacji. W tych pierwszych wszystkie dane, potrzebne uczestnikowi do podjęcia właściwej decyzji, znajdują się na planszy czy stole. Należą do nich szachy, warcaby, kółko i krzyżyk. Jedne są trudniejsze, drugie prostsze, ale niezależnie od tego wiemy na pewno przynajmniej tyle, że najlepsze możliwe posunięcie można wybrać patrząc na dostępne dane. Dlatego mogą istnieć programy komputerowe, pokonujące najlepszych mistrzów szachowych. Mają one zapisane reguły gry, wiedzą, jakie ruchy są korzystniejsze w jakiej sytuacji i na podstawie tych danych podejmują potencjalnie najlepsze decyzje.

W grach o niedoskonałej informacji, do których należy poker, sytuacja jest zgoła odmienna. Nawet jeżeli ich ogólne zasady są prostsze, to fakt, że część danych jest przed graczami ukryta (w przypadku pokera jest to zawartość ręki przeciwnika), niezwykle utrudnia opracowanie optymalnych, automatycznych reguł postępowania, których mógłby używać komputer. Michael Bowling z Uniwersytetu Alberty rozpoczął prace nad tym problemem 11 lat temu. Jego pierwsze programy miały po prostu wykorzystywać popełniane przez człowieka błędy i grać tak, by go przechytrzyć. Nie śmiał wtedy nawet marzyć, że uda mu się napisać taki, który wygra _ zawsze _. A jednak w końcu okazało się to możliwe.

W tym miejscu należy kilka spraw wyjaśnić. Po pierwsze, rozwiązanie ogranicza się do relatywnie prostej odmiany pokera – dwuosobowego Texas Hold'em z limitem. W przypadku większej liczby graczy do gry wchodzi możliwość ich świadomej bądź nieświadomej współpracy przeciwko programowi, która znacząco utrudnia jego działanie. Po drugie nie oznacza to, że program wygra _ każde rozdanie _ – to nie wydaje się być możliwe ze względu na losowy charakter gry. Oznacza to jednak tyle, że statystycznie, po pewnej ilości gier, komputer zawsze przynajmniej wyjdzie na swoje. Niezależnie od tego, jak zacznie się gra, od pewnego momentu człowiek nie będzie już w stanie odbić się od dna, nawet gdyby grał z maszyną przez całe swoje życie. W tym sensie więc program jest _ nie do pokonania _.

Jak to działa? W teorii – bardzo prosto. Program połączony jest z olbrzymią bazą danych potencjalnych stanów gry. Stając przed koniecznością podjęcia decyzji przeszukuje on ją w poszukiwaniu analogicznej sytuacji i wybiera ruch, który według jego danych jest w tym momencie najkorzystniejszy. Problemem było jednak samo skonstruowanie takiej bazy. Zaczęto od uruchamiania programu tak, by grał sam ze sobą i zapisywał w pamięci rezultaty wszystkich posunięć.

- Program analizuje wszystkie możliwe punkty decyzyjne i każde możliwe posunięcie, jakie może w nich wykonać. Dla przykładu – może się zastanowić "a co, jeżeli podbiję tutaj, zamiast grać przypadkowo, o ile więcej mogę wygrać lub przegrać?" Jeżeli zdecyduje się grać losowo i straci pieniądze, to cofa się o jeden krok i przelicza, ile pieniędzy wygrałby, gdyby podjął odwrotną decyzję. Ta kwota jest zapisywana jako "wartość żalu". Program przelicza tę "wartość żalu" dla każdej możliwej decyzji w każdej możliwej sytuacji i wtedy podejmuje ostateczną decyzję – tłumaczy Bowling.

Po 70 dniach takich prób, do których zaprzęgnięto 200 komputerów, po 32 GB pamięci RAM i 24 procesory każdy, udało się dojść do zbioru danych, który umożliwia coś, co Bowling nazywa "nieomylną grą". Nie twierdzi, że programu nie można by jeszcze udoskonalić i że nie grałby on lepiej – ale uważa, że dalsza poprawa byłaby już niezauważalna z punktu widzenia normalnej rywalizacji w pokera. Miałoby jedynie wartość akademicką.

To osiągnięcie to nie tylko ważna informacja dla akademików zajmujących się teorią gier i pokerzystów. Bowling uważa, że praca jego zespołu znajdzie znacznie szersze zastosowanie. Jego program mógłby znaleźć zastosowanie np. w opracowywaniu ścieżek patroli strażników, które uczyniłyby obiekty niemożliwymi do zinfiltrowania, pomóc rządom czy firmom w konstruowaniu najskuteczniejszych strategii obronnych czy nawet wspomóc lekarzy i pacjentów w walce z cukrzycą, w której również konieczne jest podejmowanie decyzji bez znajomości wszystkich danych.

Tymczasem jednak mamy maszynę, której nie da się pokonać w pokera. Nie wierzycie? Możecie spróbować. Program, nazywający się Cepheus, wypróbować może każdy na stronie internetowej Uniwersytetu Alberty.

_ DG _