Generazione di tutte le mani di 5 carte da poker

StackOverflow https://stackoverflow.com/questions/3829457

Domanda

Questo problema sembra semplice a prima vista, ma si rivela essere molto più complicato di quanto sembri. E 'mi ha perplesso per il momento.

Ci sono 52c5 = 2.598.960 modi per scegliere 5 carte da un mazzo di 52 carte. Tuttavia, dal momento che i semi sono intercambiabili nel poker, molti di questi sono equivalenti - la mano 2H 2C 3H 3S 4D è equivalente a 2D 2S 3D 3C 4H - semplicemente scambiare gli abiti in giro. Secondo wikipedia , ci sono 134,459 distinti 5 mani scheda una volta che conto per eventuali recolorings tuta.

La domanda è: come facciamo in modo efficiente generare tutti questi possibili mani? Non voglio generare tutte le mani, poi eliminare i duplicati, come voglio applicare il problema di un maggior numero di carte, e il numero di mani per valutare velocemente spirali fuori controllo. I miei attuali tentativi sono centrato o generare in profondità, e tenere traccia delle carte attualmente generati per determinare quali abiti e ranghi sono validi per la carta successiva, o in ampiezza, generando tutti i possibili prossimi carte, poi rimuovendo i duplicati convertendo ciascun mano a un 'canonica' la versione da ricolorazione. Ecco il mio tentativo di soluzione in ampiezza, in Python: 

# A card is represented by an integer. The low 2 bits represent the suit, while
# the remainder represent the rank.
suits = 'CDHS'
ranks = '23456789TJQKA'

def make_canonical(hand):
  suit_map = [None] * 4
  next_suit = 0
  for i in range(len(hand)):
    suit = hand[i] & 3
    if suit_map[suit] is None:
      suit_map[suit] = next_suit
      next_suit += 1
    hand[i] = hand[i] & ~3 | suit_map[suit]
  return hand

def expand_hand(hand, min_card):
  used_map = 0
  for card in hand:
    used_map |= 1 << card

  hands = set()
  for card in range(min_card, 52):
    if (1 << card) & used_map:
      continue
    new_hand = list(hand)
    new_hand.append(card)
    make_canonical(new_hand)
    hands.add(tuple(new_hand))
  return hands

def expand_hands(hands, num_cards):
  for i in range(num_cards):
    new_hands = set()
    for j, hand in enumerate(hands):
      min_card = hand[-1] + 1 if i > 0 else 0
      new_hands.update(expand_hand(hand, min_card))
    hands = new_hands
  return hands

Purtroppo, questo genera troppe mani: 

>>> len(expand_hands(set([()]), 5))
160537

Qualcuno può suggerire un modo migliore per generare solo le mani distinte, o indicare dove ho sbagliato andato nel mio tentativo?

È stato utile?

Soluzione

Il tuo approccio complessivo è suono. Sono abbastanza sicuro che le bugie problema con la funzione make_canonical. Si può provare a stampare le mani con num_cards impostato a 3 o 4 e look per equivalenze che hai persi.

ho trovato uno, ma ci può essere di più: 

# The inputs are equivalent and should return the same value
print make_canonical([8, 12 | 1]) # returns [8, 13]
print make_canonical([12, 8 | 1]) # returns [12, 9]

Per riferimento, qui di seguito è la mia soluzione (sviluppata prima di guardare la soluzione). Ho usato una ricerca in profondità, invece di una ricerca in ampiezza. Inoltre, invece di scrivere una funzione per trasformare una mano a forma canonica, ho scritto una funzione per controllare se una mano è canonico. Se non è canonica, mi saltare. Ho definito rango = carta% 13 e vestito = carta / 13. Nessuna di queste differenze sono importanti. 

import collections

def canonical(cards):
    """
    Rules for a canonical hand:
    1. The cards are in sorted order

    2. The i-th suit must have at least many cards as all later suits.  If a
       suit isn't present, it counts as having 0 cards.

    3. If two suits have the same number of cards, the ranks in the first suit
       must be lower or equal lexicographically (e.g., [1, 3] <= [2, 4]).

    4. Must be a valid hand (no duplicate cards)
    """

    if sorted(cards) != cards:
        return False
    by_suits = collections.defaultdict(list)
    for suit in range(0, 52, 13):
        by_suits[suit] = [card%13 for card in cards if suit <= card < suit+13]
        if len(set(by_suits[suit])) != len(by_suits[suit]):
            return False
    for suit in range(13, 52, 13):
        suit1 = by_suits[suit-13]
        suit2 = by_suits[suit]
        if not suit2: continue
        if len(suit1) < len(suit2):
            return False
        if len(suit1) == len(suit2) and suit1 > suit2:
            return False
    return True

def deal_cards(permutations, n, cards):
    if len(cards) == n:
        permutations.append(list(cards))
        return
    start = 0
    if cards:
        start = max(cards) + 1
    for card in range(start, 52):
        cards.append(card)
        if canonical(cards):
            deal_cards(permutations, n, cards)
        del cards[-1]

def generate_permutations(n):
    permutations = []
    deal_cards(permutations, n, [])
    return permutations

for cards in generate_permutations(5):
    print cards

Si genera il numero corretto di permutazioni: 

Cashew:~/$ python2.6 /tmp/cards.py | wc
134459

Altri suggerimenti

Ecco una soluzione Python che fa uso di NumPy e genera le offerte più canoniche, così come la loro molteplicità. Io uso itertools di Python modulo per creare tutte le 24 possibili permutazioni di 4 semi e poi a iterare su tutte le possibili offerte 2.598.960 5 carte. Ogni affare è permutata e convertito in un id canonica in soli 5 linee. E 'abbastanza veloce come il ciclo va solo attraverso 10 iterazioni per coprire tutte le offerte ed è necessaria solo per gestire i requisiti di memoria. Tutto il lavoro pesante è svolto in modo efficiente in numpy tranne che per l'uso di itertools.combinations. E 'un peccato che questo non è supportedly direttamente NumPy. 

import numpy as np
import itertools

# all 24 permutations of 4 items
s4 = np.fromiter(itertools.permutations(range(4)), dtype='i,i,i,i').view('i').reshape(-1,4)

c_52_5 = 2598960 # = binomial(52,5) : the number of 5-card deals in ascending card-value order
block_n = c_52_5/10
def all5CardDeals():
    '''iterate over all possible 5-card deals in 10 blocks of 259896 deals each'''
    combos = itertools.combinations(range(52),5)
    for i in range(0, c_52_5, block_n):
        yield np.fromiter(combos, dtype='i,i,i,i,i', count=block_n).view('i').reshape(-1,5)

canon_id = np.empty(c_52_5, dtype='i')
# process all possible deals block-wise.
for i, block in enumerate(all5CardDeals()):
    rank, suit = block/4, block%4     # extract the rank and suit of each card
    d = rank[None,...]*4 + s4[:,suit] # generate all 24 permutations of the suits
    d.sort(2)                         # re-sort into ascending card-value order
    # convert each deal into a unique integer id
    deal_id = d[...,0]+52*(d[...,1]+52*(d[...,2]+52*(d[...,3]+52*d[...,4])))
    # arbitrarily select the smallest such id as the canonical one 
    canon_id[i*block_n:(i+1)*block_n] = deal_id.min(0)
# find the unique canonical deal ids and the index into this list for each enumerated hand
unique_id, indices = np.unique(canon_id, return_inverse=True)
print len(unique_id) # = 134459
multiplicity = np.bincount(indices)
print multiplicity.sum() # = 2598960 = c_52_5

Il tuo problema sembrava interessante, semplice e così ho cercato di attrezzi il programma semplicemente con loop su tutte le possibili mani in un modo ordinato. Non ho guardato il codice in dettagli, ma sembra che la mia applicazione è molto diversa dalla vostra. Indovinate un po 'conta delle mani il mio script Trovato: 160.537

  • Le mie mani sono sempre ordinati, per esempio 2 3 4 4 D
  • Se ci sono 2 carte uguali, il colore è anche allineati (i colori sono appena chiamato 0,1,2,3)
  • la prima carta è sempre di colore 0, il secondo colore 0 o 1
  • Una carta può avere solo il colore di una carta precedente o il numero successivo più grande, per esempio se la carta 1 + 2 hanno colore 0, tre carte può avere solo i colori 0 o 1

Sei sicuro, il numero su wikipedia è corretto? 

count = 0
for a1 in range(13):
    c1 = 0
    for a2 in range(a1, 13):
        for c2 in range(2):
            if a1==a2 and c1==c2:
                continue
            nc3 = 2 if c1==c2 else 3
            for a3 in range(a2, 13):
                for c3 in range(nc3):
                    if (a1==a3 and c1>=c3) or (a2==a3 and c2>=c3):
                        continue
                    nc4 = nc3+1 if c3==nc3-1 else nc3
                    for a4 in range(a3, 13):
                        for c4 in range(nc4):
                            if (a1==a4 and c1>=c4) or (a2==a4 and c2>=c4) or (a3==a4 and c3>=c4):
                                continue
                            nc5 = nc4+1 if (c4==nc4-1 and nc4!=4) else nc4
                            for a5 in range(a4, 13):
                                for c5 in range(nc5):
                                    if (a1==a5 and c1>=c5) or (a2>=a5 and c2>=c5) or (a3==a5 and c3>=c5) or (a4==a5 and c4>=c5):
                                        continue
                                    #print([(a1,c1),(a2,c2),(a3,c3),(a4,c4),(a5,c5)])
                                    count += 1
print("result: ",count)

Non sono un giocatore di poker, in modo che i dettagli di precedenza mano sono al di là di me. Ma sembra che il problema è che si sta che attraversano lo spazio del "set di 5 carte" da gruppi elettrogeni dal ponte, quando si dovrebbe essere che attraversano lo spazio di "mani di poker distinte".

Lo spazio delle mani distinte richiederà una nuova grammatica. La cosa importante è quello di catturare esattamente le informazioni che sono rilevanti per la precedenza mano. Ad esempio, ci sono solo 4 mani che sono scale reali, in modo da quelle mani può essere descritto come il simbolo "RF" più un designatore tuta, come "RFC" per la scala reale in un locale. Un rossore 10-alta cuore potrebbe essere "FLH10" (non so se ci sono altre caratteristiche di precedenza di vampate, ma penso che è tutto quello che c'è da sapere). Una mano che è "2C 2S AH 10C 5D" sarebbe un'espressione più lunga, qualcosa come "PR2 A 10 5" se io undestand sua dichiarazione problema iniziale.

Dopo aver definito la grammatica di mani diverse, si può esprimere come le espressioni regolari e che vi dirà come generare l'intero spazio delle mani distinte. Sembra divertente!

Si potrebbe semplicemente dare tutte le mani un ordinamento canonico di valori (da A a K), quindi assegnare le lettere astratte tuta in base al loro ordine di apparizione in questo ordine.

Esempio:. JH 4C QD 9C 3D sarebbe convertire 3a 4b 9b Jc Qa

Generazione dovrebbe funzionare meglio di programmazione dinamica:

  • iniziare con un insieme di una sola mano che è vuota,
  • fare una nuova serie:
    • per ogni mano nel vecchio set, generano ogni mano possibile con l'aggiunta di uno dei restanti carte
    • canonicalize tutte le nuove mani
    • i duplicati Rimuovi

ingresso iniziale: 

H 0 0 0 0 0 0 0 0 0 0 0 0 0
C 1 0 0 0 0 0 0 0 0 0 0 0 0
D 1 0 0 0 0 0 0 0 0 0 0 0 0
S 1 1 0 0 0 0 0 0 0 0 0 0 0
+ A 2 3 4 5 6 7 8 9 T J Q K

Passaggio 1: per ogni maggiore rango o uguale il grado più alto utilizzato, impostare tutti i semi in quel rango 0. è possibile ottenere via con solo controllando le carte più elevati perché le combinazioni più bassi saranno controllati dai punti di partenza più bassa 

H 0 0 0 0 0 0 0 0 0 0 0 0 0
C 1 0 0 0 0 0 0 0 0 0 0 0 0
D 1 0 0 0 0 0 0 0 0 0 0 0 0
S 1 0 0 0 0 0 0 0 0 0 0 0 0
+ A 2 3 4 5 6 7 8 9 T J Q K

Passaggio 2: Riduci a righe distinte 

0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0
A 2 3 4 5 6 7 8 9 T J Q K

Fase 3: Risalire determinazione primo abito che corrispondono ciascuna riga distinta, e scegliere i vestiti che corrispondono alle righe distinte (contraddistinte da un *) 

H 0 * 0 0 0 0 0 0 0 0 0 0 0
C 1 0 0 0 0 0 0 0 0 0 0 0 0
D 1 * 0 0 0 0 0 0 0 0 0 0 0
S 1 1 0 0 0 0 0 0 0 0 0 0 0
+ A 2 3 4 5 6 7 8 9 T J Q K

Ora mostra la ripetizione per rango 3 

H 0 0 0 0 0 0 0 0 0 0 0 0 0
C 1 0 0 0 0 0 0 0 0 0 0 0 0
D 1 0 0 0 0 0 0 0 0 0 0 0 0
S 1 1 0 0 0 0 0 0 0 0 0 0 0
+ A 2 3 4 5 6 7 8 9 T J Q K

0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0
A 2 3 4 5 6 7 8 9 T J Q K

H 0 0 * 0 0 0 0 0 0 0 0 0 0
C 1 0 0 0 0 0 0 0 0 0 0 0 0
D 1 0 * 0 0 0 0 0 0 0 0 0 0
S 1 1 * 0 0 0 0 0 0 0 0 0 0
+ A 2 3 4 5 6 7 8 9 T J Q K

Passo 4: Una volta che ci sono 5 celle impostati a 1, incrementare la tuta totale possibile astrarre contano mani di 1 e ricorsivamente fino

.

Il numero totale di tuta estratta mani possibile è 134.459. Questo è il codice che ho scritto di provarlo: 

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication20
{
    struct Card
    {
        public int Suit { get; set; }
        public int Rank { get; set; }
    }
    
    class Program
    {
        static int ranks = 13;
        static int suits = 4;
        static int cardsInHand = 5;

        static void Main(string[] args)
        {
            List<Card> cards = new List<Card>();
            //cards.Add(new Card() { Rank = 0, Suit = 0 });
            int numHands = GenerateAllHands(cards);
    
            Console.WriteLine(numHands);
            Console.ReadLine();
        }
  
        static int GenerateAllHands(List<Card> cards)
        {
            if (cards.Count == cardsInHand) return 1;
    
            List<Card> possibleNextCards = GetPossibleNextCards(cards);
    
            int numSubHands = 0;
    
            foreach (Card card in possibleNextCards)
            {
                List<Card> possibleNextHand = cards.ToList(); // copy list
                possibleNextHand.Add(card);
                numSubHands += GenerateAllHands(possibleNextHand);
            }
    
            return numSubHands;
        }
    
        static List<Card> GetPossibleNextCards(List<Card> hand)
        {
            int maxRank = hand.Max(x => x.Rank);
            
            List<Card> result = new List<Card>();
    
            // only use ranks >= max
            for (int rank = maxRank; rank < ranks; rank++)
            {
                List<int> suits = GetPossibleSuitsForRank(hand, rank);
                var possibleNextCards = suits.Select(x => new Card { Rank = rank, Suit = x });
                result.AddRange(possibleNextCards);
            }
    
            return result;
        }
    
        static List<int> GetPossibleSuitsForRank(List<Card> hand, int rank)
        {
            int maxSuit = hand.Max(x => x.Suit);
    
            // select number of ranks of different suits
            int[][] card = GetArray(hand, rank);
    
            for (int i = 0; i < suits; i++)
            {
                card[i][rank] = 0;
            }
    
            int[][] handRep = GetArray(hand, rank);
    
            // get distinct rank sets, then find which ranks they correspond to
            IEnumerable<int[]> distincts = card.Distinct(new IntArrayComparer());
    
            List<int> possibleSuits = new List<int>();
    
            foreach (int[] row in distincts)
            {
                for (int i = 0; i < suits; i++)
                {
                    if (IntArrayComparer.Compare(row, handRep[i]))
                    {
                        possibleSuits.Add(i);
                        break;
                    }
                }
            }
    
            return possibleSuits;
        }
    
        class IntArrayComparer : IEqualityComparer<int[]>
        {
            #region IEqualityComparer<int[]> Members
    
            public static bool Compare(int[] x, int[] y)
            {
                for (int i = 0; i < x.Length; i++)
                {
                    if (x[i] != y[i]) return false;
                }
    
                return true;
            }
    
            public bool Equals(int[] x, int[] y)
            {
                return Compare(x, y);
            }
    
            public int GetHashCode(int[] obj)
            {
                return 0;
            }

            #endregion
        }

        static int[][] GetArray(List<Card> hand, int rank)
        {
            int[][] cards = new int[suits][];
            for (int i = 0; i < suits; i++)
            {
                cards[i] = new int[ranks];
            }

            foreach (Card card in hand)
            {
                cards[card.Suit][card.Rank] = 1;
            }
    
            return cards;
        }
    }
}

Speriamo che si è rotto abbastanza per essere facilmente comprensibile.

Ecco un semplice e l'algoritmo semplice per ridurre le mani ad uno canonica in base a permutatoins tuta.

  1. Converti mano a quattro bitsets, uno per ogni seme che rappresenta carte del seme
  2. Ordina i bitset
  3. bitsets riconvertire in mano

Questo è ciò che gli sguardi algoritmo come in C ++, con qualche vestito implicita e classi cardset. Si noti che l'istruzione return converte la mano concatenando le stringhe di bit. 

CardSet CardSet::canonize () const
{
  int smasks[Suit::NUM_SUIT];
  int i=0;
  for (Suit s=Suit::begin(); s<Suit::end(); ++s)
    smasks[i++] = this->suitMask (s);

  sort (smasks, smasks+Suit::NUM_SUIT);

  return CardSet(
    static_cast<uint64_t>(smasks[3])                        |
    static_cast<uint64_t>(smasks[2]) << Rank::NUM_RANK      |
    static_cast<uint64_t>(smasks[1]) << Rank::NUM_RANK*2    |
    static_cast<uint64_t>(smasks[0]) << Rank::NUM_RANK*3);
}

PokerSource . Il problema diventa ancora peggiore quando si sta valutando completando le mani dato alcune carte già disegnato.

Il ragazzo dietro PokerStove fatto un ottimo lavoro in questa direzione, ma la fonte è divulgato.

Generazione equivalenza classi per 5 mani di carte non è un compito facile. Quando ho bisogno di questo io di solito uso la http://www.vpgenius.com/ pagina web. A http://www.vpgenius.com/video-poker/games/ voi può scegliere quale varietà di gioco di poker si ha bisogno, e nella scheda "Programmazione" si dispone di una sezione sui "modelli Suit Unique". Quindi, solo la copia che e caricamento nel programma potrebbe essere più facile che cercare di generare il proprio.

Date un'occhiata qui:

http://specialk-coding.blogspot.com/

http://code.google.com/p/specialkpokereval/

Questi riguardano una mano 5 carte (e una mano di 7 scheda) come un intero, la somma delle singole carte, che è indipendente dal seme. Esattamente quello che vi serve.

Questo fa parte di un sistema per lo classifica in modo rapido 7 e le mani di 5 carte, scritto in Objective-C e Java.

Se siete solo interessati a mani che si traducono in diversi posti della mano, ci sono in realtà solo 7462 classi mano distinte che devono essere considerati (vedi Wikipedia ).

Con la creazione di un tavolo con un esempio per ogni classe e la loro molteplicità di accompagnamento è possibile controllare tutte le mani rilevanti ponderate con la loro probabilità abbastanza veloce. Cioè, supponendo che nessuna carta sono noti e quindi fissati preventivamente già.

È probabile che si vuole veramente per generare il numero di mani diverse, nel senso di non-equivalente. In tal caso, secondo l'articolo wikipedia ci sono 7462 possibili mani. Ecco un frammento di pitone che tutti li enumerare.

La logica è semplice: c'è un lato per ciascun 5-serie di ranghi; Inoltre, se tutti i ranghi sono distinti, un altro, diverso tipo di mano può essere formato facendo tutte le tute corrispondono. 

count = 0 

for i in range(0,13):
    for j in range (i,13):
        for k in range(j,13):
            for l in range(k,13):
                for m in range(l,13):
                    d = len(set([i,j,k,l,m])) # number of distinct ranks
                    if d == 1: continue    # reject nonsensical 5-of-a-kind
                    count += 1
                    # if all the ranks are distinct then 
                    # count another hand with all suits equal
                    if d == 5: count += 1

print count   # 7462
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top