L'algorithme le plus simple pour l'évaluation des mains de poker

Les tables de recherche sont la solution la plus simple et la plus simple au problème, et aussi la plus rapide. L'astuce consiste à gérer la taille de la table et à garder le mode d'utilisation assez simple pour traiter très rapidement (compromis espace–temps ). Évidemment, en théorie, vous pouvez simplement encoder chaque main qui pourrait être tenue et avoir un tableau d'évaluations, puis-poof-une recherche de table et vous avez terminé. Malheureusement, un tel tableau serait énorme et ingérable pour la plupart des machines, et serait invariablement, vous battez des disques de toute façon car la mémoire est échangée beaucoup.

La solution dite deux plus deux arbore une grande table de 10M, mais implique littéralement une recherche de table pour chaque carte dans la main. Vous n'êtes pas susceptible de trouver un algorithme plus rapide et plus simple à comprendre.

D'autres solutions impliquent des tables plus compressées avec une indexation plus complexe, mais elles sont facilement compréhensibles et assez rapides (bien que beaucoup plus lentes que 2+2). C'est là que vous voyez la langue concernant le hachage et ainsi de suite-astuces pour réduire la taille d'une table à des tailles plus gérables.

Dans tous les cas, la recherche de solutions sont des ordres de grandeur plus rapide que l'histogramme-tri-danse-sur-votre-tête-comparer-cas spécial-et-par-la-manière-est-il-un-flush solutions, presque aucun n'est digne d'un deuxième coup d'œil.

Vous n'avez pas besoin de fonctions avancées, tout peut être fait par bit: (source: http://www.codeproject.com/Articles/569271/A-Poker-hand-analyzer-in-JavaScript-using-bit-math)

(celui-ci est en fait écrit en JavaScript, mais vous pouvez évaluer JavaScript à partir de Java si nécessaire, donc cela ne devrait pas poser de problème. En outre, c'est aussi court que possible, donc si même pour l'illustration de l'approche...):

D'abord, vous divisez vos cartes en deux tableaux: ranks (cs) et costumes (ss) et pour représenter les costumes, vous utiliserez soit 1,2,4 ou 8 (c'est-à-dire 0b0001, 0b0010,...):

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

Maintenant, voici la 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];
}

Utilisation:

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

Maintenant ce qu'il fait (très brièvement) est qu'il met 1 dans le 3ème bit de s quand il y a un 2, dans le 4ème quand il y a 3, etc., donc, pour l'exemple ci-dessus s ressemble à ceci:

0b111110000000000

Pour [A, 2,3,4, 5] cela ressemblerait à ceci

0b100 0000 0011 1100

Etc.

V utilise quatre bits pour enregistrer plusieurs occurences de la même carte, donc c'est 52 bits de long et si vous avez trois As et deux rois, ses 8 bits MSB ressemblent à:

0111 0011 ...

La dernière ligne vérifie alors une quinte flush ou quinte flush ou royal flush (0x7c00).

Voici une approche naïve de la comparaison des mains à cinq cartes que j'utilise pour aider à remplir initialement une table de recherche:

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

Au lieu d'être aussi laconique que possible, j'ai donné la priorité à la sécurité des types et au code clair et auto-documenté. Si vous n'êtes pas familier avec les types de goyave que j'utilise, Vous pouvez parcourir leur documentation .

Et je vais inclure le code ici (moins les importations statiques pour l'énumération constantes en bas), bien qu'il soit vraiment trop long pour voir confortablement dans une réponse.

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;
        }
    }
}

Voici une version modifiée du programme de dansalmo qui fonctionne pour holdem hands:

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()

Holdem () renvoie une liste d'indices de la ou des main(s) gagnante (s). Dans l'exemple test() c'est [1, 3, 6], puisque les trois mains avec des as divisent le pot, ou [8] si la main flush n'est pas commentée.

Si vous représentez une main comme un tableau de, par exemple, Card objets, alors j'aurais des méthodes pour boucler ce tableau et déterminer s'il a un 2-of-a-kind, flush etc - et si c'est le cas, quel type c'est; donc vous pourriez avoir la méthode 3ofaKind() retourner 5 si une main avait trois 5s. alors j'établirais une hiérarchie des possibilités (par exemple 3 d'une sorte est supérieur à 2 d'une sorte) et travailler à partir de là. Les méthodes elles-mêmes devraient être assez simples à écrire.

Si vous voulez juste comprendre comment cela fonctionne, voici un algorithme simple:

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)
}

Il est de "algorithmes et D'évaluation dans le POKER informatique" par Darse Billings.

Voici l'algorithme traduit de R, testé avec 6 cartes, correspondant à 42.504 combinaisons indiquées par le résultat de:

Combinaisons de mains de poker. N'a pas testé avec 13 jeu de cartes en raison de limitations de traitement (il correspondrait à 2.598.960 combinaisons).

L'algorithme représente la valeur d'une main par une chaîne , composée de 2 parties:

• 5 caractères avec le nombre de cartes ordonné (ex. "31100" signifie trois d'une type)
• les numéros de carte sont évalués par des lettres de " B "(Deuce) à " N " (Ace) (ex. "NILH" signifie as, Reine, neuf et huit). Il commence par la lettre ' B 'à cause de la main de poker A2345 où l'as vient avant le' 2 ' qui (L'as) aura la valeur 'A'.

Ainsi, par exemple, "32000NB" sera une maison pleine de trois As et deux Deuce.

La chaîne de valeur de la main de poker est pratique à des fins de comparaison et de commande .

library(tidyverse)
library(gtools)

hand_value <- function(playerhand) {

  numbers <- str_split("23456789TJQKA", "")[[1]]
  suits <- str_split("DCHS", "")[[1]]

  playerhand <- data.frame(card = playerhand) %>% separate(card, c("number", "suit"), sep = 1)

  number_values <- data.frame(number = numbers, value = LETTERS[2:14], stringsAsFactors = FALSE)

  playerhand_number <- playerhand %>% 
    group_by(number) %>% 
    count(number) %>%
    inner_join(number_values, by = "number") %>%
    arrange(desc(n), desc(value))

  playerhand_suit <- playerhand %>% 
    group_by(suit) %>% 
    count(suit) %>%
    arrange(desc(n))

  if (nrow(playerhand_number) == 5)
    {
      if (playerhand_number[1,1] == 'A' & playerhand_number[2,1] == '5')
        playerhand_number <- data.frame(playerhand_number[,1:2], value = str_split("EDCBA", "")[[1]], stringsAsFactors = FALSE)
      straight <- asc(playerhand_number[1,3]) - asc(playerhand_number[5,3]) == 4
    } else
      straight = FALSE

  flush <- nrow(playerhand_suit) == 1

  if (flush)
    {
    if (straight)
      playerhand_number <- data.frame(playerhand_number[,c(1,3)], n = c(5, 0, 0, 0, 0), stringsAsFactors = FALSE) else
      playerhand_number <- data.frame(playerhand_number[,c(1,3)], n = c(3, 1, 1, 2, 0), stringsAsFactors = FALSE)
    } else
    {
    if (straight)
      playerhand_number <- data.frame(playerhand_number[,c(1,3)], n = c(3, 1, 1, 1, 0), stringsAsFactors = FALSE)
    }  

  playerhand_value <- append(append(c(playerhand_number$n), rep("0", 5 - nrow(playerhand_number))), c(playerhand_number$value))
  playerhand_value <- paste(playerhand_value, collapse = '')

  playerhand_value

}

Tester le fonction avec les mêmes mains de l'exemple ci-dessus:

l <- c("8C TS KC 9H 4S", "7D 2S 5D 3S AC", "8C AD 8D AC 9C", '7C 5H 8D TD KS')
t <- as_tibble(l)
t <- t %>% mutate(hand = str_split(value, " ")) %>% select(hand)
t <- t %>% mutate(value = sapply(t[,1]$hand, hand_value)) %>% arrange(desc(value))
paste(t[[1]][[1]], collapse = " ")

Qui renvoie le même résultat:

[1] "8C AD 8D AC 9C"

J'espère que ça aide.