Der einfachste Algorithmus für die Pokerhandauswertung

Question

Ich denke über Pokerhand (5 Karten) Auswertung in Java nach. Jetzt suche ich nach Einfachheit und Klarheit statt nach Leistung und Effizienz. Ich kann wahrscheinlich einen "naiven" Algorithmus schreiben, aber es erfordert viel Code.

Ich sah auch ein paar Poker-Evaluierungsbibliotheken, die Hashing und bitweise Operationen verwenden, aber sie sehen ziemlich komplex aus.

Was ist der "sauberste und einfachste" Algorithmus für die Pokerhandauswertung?

Answer 1

Hier ist eine sehr kurze, aber komplette Histogramm basierte 5 Karten Poker Scoring Funktion in Python (2.x). Es wird erheblich länger, wenn es in Java konvertiert wird.

def poker(hands): 
    scores = [(i, score(hand.split())) for i, hand in enumerate(hands)] 
    winner = sorted(scores , key=lambda x:x[1])[-1][0] 
    return hands[winner] 

def score(hand): 
    ranks = '23456789TJQKA' 
    rcounts = {ranks.find(r): ''.join(hand).count(r) for r, _ in hand}.items() 
    score, ranks = zip(*sorted((cnt, rank) for rank, cnt in rcounts)[::-1]) 
    if len(score) == 5: 
     if ranks[0:2] == (12, 3): #adjust if 5 high straight 
      ranks = (3, 2, 1, 0, -1) 
     straight = ranks[0] - ranks[4] == 4 
     flush = len({suit for _, suit in hand}) == 1 
     '''no pair, straight, flush, or straight flush''' 
     score = ([1, (3,1,1,1)], [(3,1,1,2), (5,)])[flush][straight] 
    return score, ranks 

>>> poker(['8C TS KC 9H 4S', '7D 2S 5D 3S AC', '8C AD 8D AC 9C', '7C 5H 8D TD KS']) 
'8C AD 8D AC 9C' 

Answer 2

Wenn Sie eine Hand als ein Array von zum Beispiel Card Objekten darstellen, dann würde ich Methoden haben, dieses Array durchzulaufen und zu bestimmen, ob es eine 2-of-a-kind, Flush etc - und wenn es tut, welcher Typ es ist; So können Sie die 3ofaKind() Methode 5 zurückgeben, wenn eine Hand drei 5s hatte. Dann würde ich eine Hierarchie von Möglichkeiten (z. B. 3 einer Art ist höher als 2 einer Art) und arbeiten von dort aus. Die Methoden selbst sollten ziemlich einfach zu schreiben sein.

Answer 3

Lookup-Tabellen sind die einfachste und einfachste Lösung für das Problem und auch die schnellste. Der Trick besteht darin, die Größe der Tabelle zu verwalten und die Verwendungsart so einfach zu halten, dass sie sehr schnell verarbeitet werden kann (space–time tradeoff). Offensichtlich könnten Sie theoretisch jede Hand kodieren, die gehalten werden könnte, und eine Reihe von Auswertungen haben, dann --poof - eine Tabellensuche und Sie sind fertig. Leider wäre solch ein Tisch für die meisten Maschinen riesig und nicht handhabbar und hätte Sie sowieso immer wieder mit Thrash-Disks zu tun, da der Speicher ausgelagert wird.

Die so genannte Zwei-plus-zwei-Lösung hat eine große 10M-Tabelle, beinhaltet aber buchstäblich eine Tabellensuche für jede Karte in der Hand. Sie werden wahrscheinlich keinen schnelleren und einfacher zu verstehenden Algorithmus finden.

Andere Lösungen beinhalten mehr komprimierte Tabellen mit komplexerer Indizierung, aber sie sind leicht verständlich und ziemlich schnell (obwohl viel langsamer als 2 + 2). Hier sehen Sie die Sprache bezüglich Hashing und so weiter - Tricks, um eine Tabellengröße auf überschaubare Größen zu reduzieren.

In jedem Fall sind Suchlösungen um Größenordnungen schneller als das Histogramm-Sort-Dance-on-the-Head-Vergleich-Special-Case-and-by-the-way-was-es-a-Flush Lösungen, von denen fast keiner einen zweiten Blick verdient.

Answer 4

Wenn Sie wollen einfach nur wissen, wie es hier ist einfacher Algorithmus funktioniert:

HandStrength(ourcards,boardcards) 
{ 
    ahead = tied = behind = 0 
    ourrank = Rank(ourcards,boardcards) 
    /* Consider all two-card combinations 
    of the remaining cards. */ 
    for each case(oppcards) 
    { 
     opprank = Rank(oppcards,boardcards) 
     if(ourrank>opprank) 
      ahead += 1 
     else if(ourrank==opprank) 
      tied += 1 
     else /* < */ 
      behind += 1 
    } 
    handstrength = (ahead+tied/2)/(ahead+tied+behind) 
    return(handstrength) 
} 

Es ist von „-Algorithmen und Beurteilung COMPUTER POKER“ von Darse Billings.

Answer 5

Hier ist ein naiver Ansatz zu fünf Karten Vergleich, dass ich mit zunächst eine Lookup-Tabelle füllen helfen:

• https://gist.github.com/gdejohn/8293321#file-hand-java

Statt als lapidare des Seins wie möglich , Priorisierte ich Typsicherheit und klaren, selbstdokumentierenden Code. Wenn Sie mit den von mir verwendeten Guava-Typen nicht vertraut sind, können Sie deren documentation durchsuchen.

Und ich werde den Code hier (minus statische Importe für die Enum-Konstanten am unteren Rand), obwohl es wirklich zu lang ist, um bequem in einer Antwort zu sehen.

import static com.google.common.base.Preconditions.checkArgument; 
import static com.google.common.collect.Ordering.from; 
import static com.google.common.collect.Ordering.natural; 
import static java.util.Comparator.comparing; 
import static java.util.Comparator.comparingInt; 

import java.util.Comparator; 
import java.util.EnumSet; 
import java.util.LinkedList; 
import java.util.Set; 
import java.util.function.Function; 

import com.google.common.collect.EnumMultiset; 
import com.google.common.collect.Multiset; 
import com.google.common.collect.Multiset.Entry; 
import com.google.common.collect.Ordering; 

public class Hand implements Comparable<Hand> { 
    public final Category category; 

    private final LinkedList<Rank> distinctRanks = new LinkedList<>(); 

    public Hand(Set<Card> cards) { 
     checkArgument(cards.size() == 5); 
     Set<Suit> suits = EnumSet.noneOf(Suit.class); 
     Multiset<Rank> ranks = EnumMultiset.create(Rank.class); 
     for (Card card : cards) { 
      suits.add(card.suit); 
      ranks.add(card.rank); 
     } 
     Set<Entry<Rank>> entries = ranks.entrySet(); 
     for (Entry<Rank> entry : byCountThenRank.immutableSortedCopy(entries)) { 
      distinctRanks.addFirst(entry.getElement()); 
     } 
     Rank first = distinctRanks.getFirst(); 
     int distinctCount = distinctRanks.size(); 
     if (distinctCount == 5) { 
      boolean flush = suits.size() == 1; 
      if (first.ordinal() - distinctRanks.getLast().ordinal() == 4) { 
       category = flush ? STRAIGHT_FLUSH : STRAIGHT; 
      } 
      else if (first == ACE && distinctRanks.get(1) == FIVE) { 
       category = flush ? STRAIGHT_FLUSH : STRAIGHT; 
       // ace plays low, move to end 
       distinctRanks.addLast(distinctRanks.removeFirst()); 
      } 
      else { 
       category = flush ? FLUSH : HIGH_CARD; 
      } 
     } 
     else if (distinctCount == 4) { 
      category = ONE_PAIR; 
     } 
     else if (distinctCount == 3) { 
      category = ranks.count(first) == 2 ? TWO_PAIR : THREE_OF_A_KIND; 
     } 
     else { 
      category = ranks.count(first) == 3 ? FULL_HOUSE : FOUR_OF_A_KIND; 
     } 
    } 

    @Override 
    public final int compareTo(Hand that) { 
     return byCategoryThenRanks.compare(this, that); 
    } 

    private static final Ordering<Entry<Rank>> byCountThenRank; 

    private static final Comparator<Hand> byCategoryThenRanks; 

    static { 
     Comparator<Entry<Rank>> byCount = comparingInt(Entry::getCount); 
     Comparator<Entry<Rank>> byRank = comparing(Entry::getElement); 
     byCountThenRank = from(byCount.thenComparing(byRank)); 
     Comparator<Hand> byCategory = comparing((Hand hand) -> hand.category); 
     Function<Hand, Iterable<Rank>> getRanks = 
       (Hand hand) -> hand.distinctRanks; 
     Comparator<Hand> byRanks = 
       comparing(getRanks, natural().lexicographical()); 
     byCategoryThenRanks = byCategory.thenComparing(byRanks); 
    } 

    public enum Category { 
     HIGH_CARD, 
     ONE_PAIR, 
     TWO_PAIR, 
     THREE_OF_A_KIND, 
     STRAIGHT, 
     FLUSH, 
     FULL_HOUSE, 
     FOUR_OF_A_KIND, 
     STRAIGHT_FLUSH; 
    } 

    public enum Rank { 
     TWO, 
     THREE, 
     FOUR, 
     FIVE, 
     SIX, 
     SEVEN, 
     EIGHT, 
     NINE, 
     TEN, 
     JACK, 
     QUEEN, 
     KING, 
     ACE; 
    } 

    public enum Suit { 
     DIAMONDS, 
     CLUBS, 
     HEARTS, 
     SPADES; 
    } 

    public enum Card { 
     TWO_DIAMONDS(TWO, DIAMONDS), 
     THREE_DIAMONDS(THREE, DIAMONDS), 
     FOUR_DIAMONDS(FOUR, DIAMONDS), 
     FIVE_DIAMONDS(FIVE, DIAMONDS), 
     SIX_DIAMONDS(SIX, DIAMONDS), 
     SEVEN_DIAMONDS(SEVEN, DIAMONDS), 
     EIGHT_DIAMONDS(EIGHT, DIAMONDS), 
     NINE_DIAMONDS(NINE, DIAMONDS), 
     TEN_DIAMONDS(TEN, DIAMONDS), 
     JACK_DIAMONDS(JACK, DIAMONDS), 
     QUEEN_DIAMONDS(QUEEN, DIAMONDS), 
     KING_DIAMONDS(KING, DIAMONDS), 
     ACE_DIAMONDS(ACE, DIAMONDS), 

     TWO_CLUBS(TWO, CLUBS), 
     THREE_CLUBS(THREE, CLUBS), 
     FOUR_CLUBS(FOUR, CLUBS), 
     FIVE_CLUBS(FIVE, CLUBS), 
     SIX_CLUBS(SIX, CLUBS), 
     SEVEN_CLUBS(SEVEN, CLUBS), 
     EIGHT_CLUBS(EIGHT, CLUBS), 
     NINE_CLUBS(NINE, CLUBS), 
     TEN_CLUBS(TEN, CLUBS), 
     JACK_CLUBS(JACK, CLUBS), 
     QUEEN_CLUBS(QUEEN, CLUBS), 
     KING_CLUBS(KING, CLUBS), 
     ACE_CLUBS(ACE, CLUBS), 

     TWO_HEARTS(TWO, HEARTS), 
     THREE_HEARTS(THREE, HEARTS), 
     FOUR_HEARTS(FOUR, HEARTS), 
     FIVE_HEARTS(FIVE, HEARTS), 
     SIX_HEARTS(SIX, HEARTS), 
     SEVEN_HEARTS(SEVEN, HEARTS), 
     EIGHT_HEARTS(EIGHT, HEARTS), 
     NINE_HEARTS(NINE, HEARTS), 
     TEN_HEARTS(TEN, HEARTS), 
     JACK_HEARTS(JACK, HEARTS), 
     QUEEN_HEARTS(QUEEN, HEARTS), 
     KING_HEARTS(KING, HEARTS), 
     ACE_HEARTS(ACE, HEARTS), 

     TWO_SPADES(TWO, SPADES), 
     THREE_SPADES(THREE, SPADES), 
     FOUR_SPADES(FOUR, SPADES), 
     FIVE_SPADES(FIVE, SPADES), 
     SIX_SPADES(SIX, SPADES), 
     SEVEN_SPADES(SEVEN, SPADES), 
     EIGHT_SPADES(EIGHT, SPADES), 
     NINE_SPADES(NINE, SPADES), 
     TEN_SPADES(TEN, SPADES), 
     JACK_SPADES(JACK, SPADES), 
     QUEEN_SPADES(QUEEN, SPADES), 
     KING_SPADES(KING, SPADES), 
     ACE_SPADES(ACE, SPADES); 

     public final Rank rank; 

     public final Suit suit; 

     Card(Rank rank, Suit suit) { 
      this.rank = rank; 
      this.suit = suit; 
     } 
    } 
} 

Answer 6

Hier ist eine modifizierte Version des dansalmo des Programms, die für holde Hand arbeitet:

def holdem(board, hands): 
    scores = [(evaluate((board + ' ' + hand).split()), i) for i, hand in enumerate(hands)] 
    best = max(scores)[0] 
    return [x[1] for x in filter(lambda(x): x[0] == best, scores)] 

def evaluate(hand): 
    ranks = '23456789TJQKA' 
    if len(hand) > 5: return max([evaluate(hand[:i] + hand[i+1:]) for i in range(len(hand))]) 
    score, ranks = zip(*sorted((cnt, rank) for rank, cnt in {ranks.find(r): ''.join(hand).count(r) for r, _ in hand}.items())[::-1]) 
    if len(score) == 5: # if there are 5 different ranks it could be a straight or a flush (or both) 
     if ranks[0:2] == (12, 3): ranks = (3, 2, 1, 0, -1) # adjust if 5 high straight 
     score = ([1,(3,1,2)],[(3,1,3),(5,)])[len({suit for _, suit in hand}) == 1][ranks[0] - ranks[4] == 4] # high card, straight, flush, straight flush 
    return score, ranks 

def test(): 
    print holdem('9H TC JC QS KC', [ 
     'JS JD', # 0 
     'AD 9C', # 1 A-straight 
     'JD 2C', # 2 
     'AC 8D', # 3 A-straight 
     'QH KH', # 4 
     'TS 9C', # 5 
     'AH 3H', # 6 A-straight 
     '3D 2C', # 7 
     # '8C 2C', # 8 flush 
    ]) 

test() 

holde() gibt eine Liste des Indizes der Gewinnerhand (s). Im Test() Beispiel ist das [1, 3, 6], da die drei Hände mit Assen den Pot teilen, oder [8] wenn der Flush Hand unkommentiert ist.

Answer 7

Sie brauchen eigentlich keine erweiterten Funktionen, kann sie alles getan, was bitweise sein: (Quelle: http://www.codeproject.com/Articles/569271/A-Poker-hand-analyzer-in-JavaScript-using-bit-math)

(Dieses in JavaScript tatsächlich geschrieben wird, aber Sie können JavaScript von Java zu bewerten, wenn nötig, Also sollte es kein Problem sein, auch wenn es nur kurz ist:

Zuerst teilen Sie Ihre Karten in zwei Arrays: Ränge (cs) und Anzüge (ss) und um Anzüge darzustellen, verwenden Sie entweder 1,2,4 oder 8 (das ist 0b0001, 0b0010, ...):

var J=11, Q=12, K=13, A=14, C=1, D=2, H=4, S=8; 

Jetzt ist hier der Magie:

function evaluateHand(cs, ss) { 
    var pokerHands = ["4 of a Kind", "Straight Flush","Straight","Flush","High Card","1 Pair","2 Pair","Royal Flush", "3 of a Kind","Full House"]; 

    var v,i,o,s = 1 << cs[0] | 1 << cs[1] | 1 << cs[2] | 1 << cs[3] | 1 << cs[4]; 
    for (i = -1, v = o = 0; i < 5; i++, o = Math.pow(2, cs[i] * 4)) {v += o * ((v/o & 15) + 1);} 
    v = v % 15 - ((s/(s & -s) == 31) || (s == 0x403c) ? 3 : 1); 
    v -= (ss[0] == (ss[1] | ss[2] | ss[3] | ss[4])) * ((s == 0x7c00) ? -5 : 1); 
    return pokerHands[v]; 
} 

Verbrauch:

evaluateHand([A,10,J,K,Q],[C,C,C,C,C]); // Royal Flush 

Nun, was es tut (sehr kurz) ist, dass es 1 in 3. Bit von s setzt, wenn es eine 2 , in 4., wenn es 3, usw., so für das obige Beispiel s sieht so aus:

0b111110000000000

für [A, 2,3,4,5] es wie dieses

0b100 0000 0011 1100

usw.

v verwendet vier Bits aussehen würde um mehrere Vorkommen der gleichen Karte aufzuzeichnen, so ist es 52 Bit lang und wenn Sie drei Asse und zwei Könige haben, sehen seine 8 MSB Bits wie folgt aus:

0111 0011 ...

Die letzte Zeile prüft dann auf einen Flush oder Straight Flush oder Royal Flush (0x7c00).