Gerando todas as mãos de pôquer de 5 cartas

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

Pergunta

Este problema parece simples à primeira vista, mas acaba por ser muito mais complicado do que parece.Isso me deixou perplexo no momento.

Existem 52c5 = 2.598.960 maneiras de escolher 5 cartas de um baralho de 52 cartas.No entanto, como os naipes são intercambiáveis ​​no pôquer, muitos deles são equivalentes - a mão 2H 2C 3H 3S 4D é equivalente a 2D 2S 3D 3C 4H - basta trocar os naipes.De acordo com Wikipédia, existem 134.459 mãos distintas de 5 cartas, uma vez que você considera possíveis recolorações de naipes.

A questão é: como podemos gerar de forma eficiente todas essas mãos possíveis?Não quero gerar todas as mãos e depois eliminar duplicatas, pois quero aplicar o problema a um número maior de cartas e ao número de mãos para avaliar espirais rápidas fora de controle.Minhas tentativas atuais se concentraram em gerar primeiro a profundidade e manter o controle das cartas geradas atualmente para determinar quais naipes e valores são válidos para a próxima carta, ou primeiro em largura, gerando todas as próximas cartas possíveis e, em seguida, removendo duplicatas convertendo cada mão para uma versão 'canônica' recolorindo.Aqui está minha tentativa de uma solução abrangente, em 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

Infelizmente, isso gera muitas mãos:

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

Alguém pode sugerir uma maneira melhor de gerar apenas mãos distintas ou apontar onde errei na minha tentativa?

Foi útil?

Solução

Sua abordagem geral é sólida.Tenho certeza de que o problema está no seu make_canonical função.Você pode tentar imprimir as mãos com num_cards definido como 3 ou 4 e procurar equivalências que você perdeu.

Encontrei um, mas pode haver mais:

# 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]

Para referência, abaixo está minha solução (desenvolvida antes de analisar sua solução).Usei uma pesquisa em profundidade em vez de uma pesquisa em largura.Além disso, em vez de escrever uma função para transformar uma mão em forma canônica, escrevi uma função para verificar se uma mão é canônica.Se não for canônico, eu pulo.Eu defini classificação = carta % 13 e naipe = carta / 13.Nenhuma dessas diferenças é importante.

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

Ele gera o número correto de permutações:

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

Outras dicas

Aqui está uma solução Python que utiliza numpy e gera as negociações canônicas, bem como sua multiplicidade.Eu uso o módulo itertools do Python para criar todas as 24 permutações possíveis de 4 naipes e, em seguida, iterar todas as 2.598.960 possíveis negociações de 5 cartas.Cada transação é permutada e convertida em um ID canônico em apenas 5 linhas.É bastante rápido, pois o loop passa por apenas 10 iterações para cobrir todos os negócios e só é necessário para gerenciar os requisitos de memória.Todo o trabalho pesado é feito de forma eficiente em numpy, exceto pelo uso de itertools.combinations.É uma pena que isso não seja suportado diretamente no 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

Seu problema parecia interessante, então tentei implementá-lo simplesmente percorrendo todas as mãos possíveis de maneira ordenada.Não analisei seu código em detalhes, mas parece que minha implementação é bem diferente da sua.Adivinhe qual contagem de mãos meu script encontrou:160537

  • Minhas mãos estão sempre ordenadas, por ex.2 3 4 4 D
  • Se houver 2 cartas iguais, a cor também será classificada (as cores são chamadas apenas de 0,1,2,3)
  • a primeira carta sempre tem a cor 0, a segunda cor 0 ou 1
  • Uma carta só pode ter a cor de uma carta anterior ou o próximo número maior, por ex.se a carta 1+2 tiver a cor 0, a carta três só poderá ter as cores 0 ou 1

Tem certeza de que o número na Wikipedia está correto?

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)

Não sou um jogador de pôquer, então os detalhes da precedência das mãos estão além da minha compreensão.Mas parece que o problema é que você está atravessando o espaço de "conjuntos de 5 cartas" gerando conjuntos do baralho, quando deveria estar atravessando o espaço de "mãos de pôquer distintas".

O espaço de mãos distintas exigirá uma nova gramática.O importante é capturar exatamente as informações relevantes para a precedência manual.Por exemplo, existem apenas 4 mãos que são royal flushes, então essas mãos podem ser descritas como o símbolo "RF" mais um designador de naipe, como "RFC" para royal flush em clubes.Um heart flush de 10 pontos poderia ser "FLH10" (não tenho certeza se existem outras características de precedência de flushes, mas acho que isso é tudo que você precisa saber).Uma mão que seja "2C 2S AH 10C 5D" seria uma expressão mais longa, algo como "PR2 A 10 5" se eu entender a declaração inicial do seu problema.

Depois de definir a gramática de mãos distintas, você poderá expressá-la como expressões regulares e isso lhe dirá como gerar todo o espaço de mãos distintas.Parece divertido!

Você poderia simplesmente dar a todas as mãos uma ordem canônica de valores (A a K) e, em seguida, atribuir letras abstratas de naipes de acordo com a ordem em que aparecem pela primeira vez nessa ordem.

Exemplo:JH 4C QD 9C 3D seria convertido para 3a 4b 9b Jc Qa.

A geração deve funcionar melhor como programação dinâmica:

  • comece com um conjunto de uma única mão vazia,
  • faça um novo conjunto:
    • para cada mão do conjunto antigo, gere cada mão possível adicionando uma das cartas restantes
    • canonizar todas as novas mãos
    • remover duplicatas

Entrada inicial:

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

Passo 1:para cada classificação maior ou igual à classificação mais alta usada, defina todos os naipes dessa classificação como 0.você pode verificar apenas as cartas mais altas porque as combinações mais baixas serão verificadas pelos pontos iniciais mais baixos.

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

Passo 2:Recolher em linhas distintas

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

Etapa 3:Suba novamente determinando o primeiro naipe que corresponde a cada linha distinta e escolha os naipes que correspondem às linhas distintas (identificados por um *)

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

Agora mostrando a repetição para a classificação 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:Quando houver 5 células definidas como 1, aumente a contagem total de mãos abstraídas de naipes possíveis em 1 e repita para cima.

O número total possível de mãos abstraídas de naipes é 134.459.Este é o código que escrevi para testá-lo:

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

Esperamos que esteja dividido o suficiente para ser facilmente compreensível.

Aqui está um algoritmo simples e direto para reduzir mãos a uma mão canônica baseada em permutações de naipes.

  1. converter mão em quatro bitsets, um por naipe representando cartas do naipe
  2. classificar os bitsets
  3. converter bitsets de volta em mãos

Esta é a aparência do algoritmo em C++, com algumas classes Suit e CardSet implícitas.Observe que a instrução return converte a mão concatenando as cadeias de bits.

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

Olhe para Fonte de pôquer.O problema fica ainda pior quando você pensa em completar mãos com algumas cartas já desenhadas.

O cara por trás do PokerStove fez um ótimo trabalho nesse sentido, mas a fonte foi divulgada.

Gerar classes de equivalência para mãos de 5 cartas não é uma tarefa fácil.Quando preciso disso costumo usar o http://www.vpgenius.com/ página da Internet.No http://www.vpgenius.com/video-poker/games/ você pode escolher qual variedade de jogo de pôquer você precisa, e na "guia Programação" você tem uma seção sobre "Padrões de naipes exclusivos".Portanto, apenas copiar e carregar no programa pode ser mais fácil do que tentar gerar o seu próprio.

Dê uma olhada aqui:

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

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

Estes consideram uma mão de 5 cartas (e uma mão de 7 cartas) como um número inteiro, a soma das cartas individuais, que é independente do naipe.Exatamente o que você precisa.

Isso faz parte de um esquema para classificar rapidamente mãos de 7 e 5 cartas, escrito em Objective-C e Java.

Se você está interessado apenas em mãos que resultam em classificações de mãos diferentes, na verdade existem apenas 7.462 classes de mãos distintas que devem ser consideradas (veja Wikipédia).

Ao criar uma tabela com um exemplo para cada classe e a multiplicidade que a acompanha, você pode verificar rapidamente todas as mãos relevantes ponderadas com suas probabilidades.Isto é, assumindo que nenhum cartão é conhecido e, portanto, já foi corrigido de antemão.

Provavelmente, você deseja realmente gerar o número de mãos distintas, no sentido de não equivalentes.Nesse caso, de acordo com o artigo da Wikipedia, existem 7.462 mãos possíveis.Aqui está um trecho de python que irá enumerar todos eles.

A lógica é simples:há uma mão para cada conjunto de 5 classificações;além disso, se todas as fileiras forem distintas, outro tipo diferente de mão pode ser formado combinando todos os naipes.

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
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top