Jak obliczyć prawdopodobieństwo wygrania w pokera?

Okej, więc mam kilku graczy. Każdy gracz ma dwie karty. Jest jeszcze pula pięciu kart wspólnych. Czyli każdy gracz może ułożyć swoje "rzeczy" ze swoich dwóch kart oraz kart z puli. (Np jeżeli ja mam dyszkę i w puli jest dyszka, to mam parę dyszek).

Mam to wyświetlić w moim programie w tabeli, ale klient chce jeszcze tą szansę na wygraną w procentach. Tak jak tutaj: http://www.cardplayer.com/poker-tools/odds-calculator/texas-holdem

Czytałem o tym tutaj http://en.wikipedia.org/wiki/Poker_probability_(Texas_hold_'em) ale ciągle nie wem jak liczyć ten procent na poszczególnych fazach gry. Szukałem jakiejś w funkcji do której przekazuje posiadane karty a ona zwraca jakoś te szanse, ale nie znalazłem.

Zajmował się już ktoś czymś takim?

Robiłem kiedyś taką małą apkę dla siebie, choć akurat nie w Hold'ema, a w Razza. Oczywiście takiej magicznej funkcji nie ma i żeby dokładnie przewidzieć te prawdopodobieństwa potrzeba sprawdzić wszystkie możliwe rozdania. Np. dla fazy pre-flop powinieneś sprawdzić wszystkie możliwe ułożenia boardu (permutacja bez powtórzeń 5 kart z pozostąłych), dla każdego takiego układu sprawdzić kto wygrał, zanotować i na podstawie tego policzyć prawdopodobieństwo. Oczywiście nie ma sensu sprawdzać wszystkich możliwości, bo jest to trudne i dość czasochłonne: wystarczy sprawdzić jakąś dużą liczbę losowych przypadków i prawdopodobieństwo powinno być w miarę dokładne. Miejsce na optymalizacji jest w współbieżnym liczeniu tych możliwych sytuacji.

Wydaje mi się, też są w javie jakaś biblioteka do tego była.

@datdata po to istnieje matematyka aby nie robić pełnego przeglądu.

Grałem w pokera online półprofesjonalnie kilka lat (równolegle z pisaniem tooli na własne potrzeby) i nie znalazłem ani jednego algorytmu czy formuły matematycznej, która pozwala łatwo szacować tak skomplikowany problem. Poza tym symulacja 100 tys. losowych sytuacji spokojnie w okolicach sekundy do kilku sekund (w zależności od technologii) daje niemal 100% dokładne wyniki. To najprostsze i najbardziej powszechne rozwiązanie.

Jeśli znasz lepsze - zaprezentuj lub daj jakiejś linki, jeśli nie - to idź powiedz ludziom piszącym soft do generowania ogromnych liczb pierwszych czy sprawdzania hipotezy Goldbacha, żeby się nie ośmieszali tylko wzięli za "normalną matematykę".

datdata napisał(a):

... i nie znalazłem ani jednego algorytmu czy formuły matematycznej, która pozwala łatwo szacować tak skomplikowany problem.
Oczywiście to że nie znalazłeś jest dowodem na nieistnienie? Kto powiedział że łatwo?

datdata napisał(a):

Poza tym symulacja 100 tys. losowych sytuacji spokojnie w okolicach sekundy do kilku sekund (w zależności od technologii) daje niemal 100% dokładne wyniki. To najprostsze i najbardziej powszechne rozwiązanie.
Wszystko zależy od definicji "100% dokładne wyniki". Najprostsze owszem. To że jest "najbardziej powszechne" wynika wyłącznie z braku wiedzy matematycznej osób którzy tym się zajmują a później publikują (bardzo istotne) wyniki.

datdata napisał(a):

Jeśli znasz lepsze - zaprezentuj lub daj jakiejś linki, jeśli nie - to idź powiedz ludziom piszącym soft do generowania ogromnych liczb pierwszych czy sprawdzania hipotezy Goldbacha, żeby się nie ośmieszali tylko wzięli za "normalną matematykę".
Co ma hipoteza Goldbacha do pokiera?

Zaprezentowałem powszechnie stosowane rozwiązanie w większości oprogramowania tego typu. Sądząc z opisu problemu, nie potrzeba tutaj niczego bardziej zaawansowanego. To, że nie znalazłem bardziej "matematycznego" rozwiązania lub dowodu na jego nie istnienie jest mało istotne: znam domenę problemu i jestem niemal pewien, że nic takiego nie jest tutaj potrzebne. Dodatkowo to rozwiązanie jest w miarę ogólne i nie potrzeba modyfikować całego, żeby np. dodać większą ilość graczy czy oddsy na innych rundach niż preflop.

Co do Goldbacha, to był żart z Twojego podejścia. Jak znajdę chwilę to podeślę link do jakiejś naukowej pracy nt. poczucia humoru.

Przecież to jest klasyczny problem kombinatoryki, która jeszcze X lat temu była uczona w liceum (zapewne teraz wypadła z programu nauczania).
Po prostu trzeba policzyć ile jest silniejszych kombinacji od twojej ręki i podzielić przez wszystkie możliwe kombinacje i dostaniesz prawdopodobieństwo przegranej na jednego przeciwnika.
Policzanie takich możliwości może być troszkę skomplikowane (łatwo się pomylić), ale naprawdę da się uzyskać analityczną formułę (liczba wszystkich możliwości jest stała).

Fajniej jednak byłoby obliczać jednak poprawki związane, że ktoś odpadł z licytacji i ktoś podbił, ale to to jest już naprawdę bardzo trudne.

A ten tool z linka jest bezsensowny dla gracza, bo podaje prawdopodobieństwa znając karty wszystkich graczy. Ten tool się nadaje do relacji TV, gdzie kamery podglądają jakie karty ma każdy gracz.

Przy liczeniu "silniejszych" kombinacji trzeba uzględniać pary, trójki, dwie pary, strity, karety oraz pokery. Dodatkowo podziały puli (remisy). Uogólnij to jeszcze na zmienną liczbę graczy (od dwóch do dziesięciu). Pewnie się da, niemniej jest to trudne.

Fajniej jednak byłoby obliczać jednak poprawki związane, że ktoś odpadł z licytacji i ktoś podbił, ale to to jest już naprawdę bardzo trudne.

Klientowi na 99% chodzi o obliczenie pojęcia oddsów i takie sytuacje nie wpadają pod to pojęcie we wszystkich podręcznikach do strategii pokerowej oraz żadne oprogramowanie tego typu na rynku tego nie uwzględnia, o ile nie bazuje na analizie historii z danym przeciwnikiem.

Nie tyle co trudne, ale dość zawiłe i łatwo o czymś zapomnieć. Sama matematyka z tym związana jest bardzo prosta.
jeśli na stole masz 5 kart znasz 2 swoje, to przeciwnik ma 45*44/2 możliwych układów, więc nie jest to dużo.
Rozwiązując to informatycznie można na bezczelnego liczyć brute forcem i wynik będzie od ręki.
Pseudo/python kod:

stol = [ 1, 2, 3, 4, 5];
moje = [ 42, 12];
remis_count = 0
wygrana_count = 0

for in range(0,52) :
    if i in stol or i in moje :
         continue
    for j in range(0, 52) :
         if j in stol or j in moje or i==j :
              continue

         if czyRemis(stol, moje, [i, j]) :
              remis_count = remis_count  + 1
              
         if czyWygrana(stol, moje, [i, j]) :
              wygrana_count = remis_count  + 1

wszystkichKombinacji = 45.0*44/2
print "prawdopodobieństwo wygranej: %f  prawdopodobieństwo remisu: %f" %(wygrana_count/wszystkichKombinacji, remis_count/wszystkichKombinacji)

Matematyka matematyką, ale np. w brydżu prawdopodobieństwa obliczone (np. brakuje 4 kart w kolorze jakie jest prawdopodobieństwo podziału 4-0) nie zgadzają się z prawdopodobieństwami obserwowanymi. Rozbieżność jest niewielka jeśli tasuje komputer (jakiś generator pseudolosowy, większa gdy tasują ludzie). Obliczenia zakładają tasowanie idealne.

@bogdans możesz podać źródło opisujące to zjawisko względnie jego wyjaśnienie (lub przynajmniej dokładniej opisać).
Pamiętaj, że zdrowy rozsądek często zwodzi na manowce, doskonały przykład to rozkład Benforda, gdzie rozkład pierwszej cyfry dość dowolnego zestawu danych statystycznych nie jest jednorodny.
Brydż to bardzo specyficzny przypadek. Pamiętaj, że jest coś takiego jak licytacja, więc jeśli jedna para ma renons ma większą szansę na wygranie licytacji, jeśli para przegrała licytację szansa na rozkład 4-0 muszą być niższe niż przy założeniu, że każda kombinacja występuje z równym prawdopodobieństwem.

Disclaimer: w brydża grałem dawno mało i słabo, wiec zapewne coś pokręciłem.

Tak samo zresztą jest w przypadku Pokera. Każda krok licytacji to decyzje graczy o rezygnacji z gry podbiciu itd, wiec po river faktyczne prawdopodobieństwa wygranej zapewne też będą się różnić od tego co zostanie obliczone na podstawie prostych zasad kombinatoryki.
Przykładowo jeśli przeciwnicy na samym początku zrezygnowali z gry to najprawdopodobniej mają blotki (lub wręcz najgorszą możliwą ich wrsję 2-7), więc jeśli na końcu na stole pojawiają się blotki szanse na wgraną z wysoką parą są większe niż liczone z prostego rachunku kombinatoryki, bo szanse na podwójną parę z niskich kart są dużo mniejsze.

Niestety modelowanie matematyczne zachowań graczy, by potem obliczyć szanse wygranej jest już bardzo trudne. John Nash Jr dostał nobla z ekonomi chyba właśnie za to.

http://www.intellipoker.pl/articles/Odds-Outs-Szanse-na-wygrana-i-karty-poprawiajace-uklad
http://www.intellipoker.pl/articles/Prawdopodobienstwo-wariancja-i-pechowe-rozdania

@MarekR22, nie pamiętam źródła, była to książka o brydżu. Opisano w niej działania pierwszego teoretyka brydża (Ely Culbertson), który między innymi zatrudniał ludzi, których jedynym zadaniem było tasowanie, rozdawanie i zapisywanie rozdań. Po analizie ogromnej ilości rozdań okazało się, że rozkłady różnią się od obliczonych. Oni nie licytowali, zatem Twoje uwagi o wpływie licytacji nie mają żadnego zastosowania.
Niedawno jeden z najlepszych polskich brydżystów (Krzysztof Jassem) powiedział mi, że na turniejach, na których karty tasują programy komputerowe, rozkłady są dużo bardziej nierównomierne niż przy tradycyjnym tasowaniu.
Moim zdaniem doświadczalne ustalanie prawdopodobieństw jest w grach karcianych jak najbardziej uzasadnione.

To o czym mówisz to w kontekście planowania strategii traktowane jest jedynie jako błąd poznawczy.Poker, ani mam nadzieję brydż, z którym mam nikłe doświadczenie, to nie jest oczko, gdzie liczenie kart powinno wpływać na decyzję.

do obliczania prawodopodobienstwa na turniejach pokerowych uzywa sie tego algorytmu

http://en.wikipedia.org/wiki/Monte_Carlo_algorithm

puszcza sie rozgrywke duza liczbe razy (milion? a moze wiecej, nie wiem ile dokladnie) i wtedy oblicza sie % wygranych dla kazdego uczestnika.

Może się trochę źle wyraziłem. Nie chodziło mi o to żeby sprawdzać to prawdopodobieństwo żeby potem uzależnić od niego późniejsze decyzje.

Po prostu mam kilku graczy z których każdy ma 2 karty oraz pulę. Chce wiedzieć jakie szanse na wygraną ma każdy z nich tylko w tym momencie i w takim ułożeniu.

Narzędzie z linka z pierwszego postu nie jest useless, bo dokładnie prezentuje problem z którym się zmagam. Znam wszystkie karty na stole, sugeruję dokładniej czytać pytanie.

A przeczytałeś dokładnie ten artykuł na wiki, który sam wkleiłeś?
Nic więcej nie potrzebujesz, oprócz liczenia prawdopodobieństwa wystąpienia figur.

I etap
Każdy z graczy ma na wejściu po dwie karty. Liczysz prawdopodobieństwo dla wszystkich graczy wystąpienia wszystkich figur - dostępna pula kart 52 - liczba graczy x 2.
II etap
Wykładane są trzy karty. Sprawdzasz wszystkie kombinacje prawdopodobieństwa ile brakuje do trójki, karety, strita, koloru itd.- dostępna pula 52 - liczba graczy x 2 -3.
Kolejne etapy analogicznie poprzez zmniejszanie dostępnej puli.

Na każdym etapie porównujesz poszczególne prawdopodobieństwa i ich sumy z każdym graczem.
Tutaj nie ma zawiłego algorytmu tylko dwumian newtona i "jazda".

No dobra, a kto w takim razie ma większe szanse wygrania przy rozdaniu kard: osoba, która ma dwie damy (para) czy osoba, która ma jopka i asa?

To zależy od tego jakie karty są w puli. Chodzi mi o dokładnie takie samo prawdopodobieństwo jak tutaj: http://www.cardplayer.com/poker-tools/odds-calculator/texas-holdem

Co do kodu @MarekR22:

Nie znam się na kombinatoryce więc muszę zapytać. Czy ten kod wymaga przerobienia żeby działał z czterema kolorami kart (kier, karo, trefl i pik)?

Nie jestem pewien boo liczba kombinacji będzie różna ale z drugiej strony dyszka karo ma taką samą wartość jak dyszka kier. I'm confused :|