Générer toutes les mains de poker à 5 cartes

Question

Ce problème semble simple à première vue, mais il s'avère être beaucoup plus compliqué qu'il n'y paraît. Il me laisse perplexe pour le moment.

Il y a 52c5 = 2.598.960 façons de choisir 5 cartes dans un jeu de 52 cartes. Cependant, comme les couleurs sont interchangeables au poker, beaucoup d'entre elles sont équivalentes - la main 2H 2C 3H 3S 4D est équivalente à 2D 2S 3D 3C 4H - il suffit d'intervertir les couleurs. D'après wikipedia Il existe 134 459 mains de 5 cartes distinctes, si l'on tient compte de la possibilité de recolorations de couleurs.

La question est de savoir comment générer efficacement toutes ces mains possibles. Je ne veux pas générer toutes les mains, puis éliminer les doublons, car je veux appliquer le problème à un plus grand nombre de cartes, et le nombre de mains à évaluer devient rapidement incontrôlable. Mes tentatives actuelles se sont concentrées sur la génération en profondeur d'abord, et sur le suivi des cartes actuellement générées pour déterminer quelles couleurs et quels rangs sont valables pour la prochaine carte, ou sur la génération en largeur d'abord, en générant toutes les cartes suivantes possibles, puis en éliminant les doublons en convertissant chaque main en une version "canonique" par recoloration. Voici ma tentative de solution "breadth-first", en 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

Malheureusement, cela génère trop de mains :

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

Quelqu'un peut-il suggérer une meilleure façon de générer uniquement les mains distinctes, ou m'indiquer où je me suis trompé dans ma tentative ?

Answer 1

Votre approche globale est saine. Je suis presque sûr que le problème se situe au niveau de votre make_canonical fonction. Vous pouvez essayer d'imprimer les mains avec num_cards réglé sur 3 ou 4 et rechercher les équivalences que vous avez manquées.

J'en ai trouvé un, mais il y en a peut-être d'autres :

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

Pour référence, voici ma solution (développée avant de regarder votre solution). J'ai utilisé une recherche en profondeur au lieu d'une recherche en largeur. De même, au lieu d'écrire une fonction pour transformer une main en forme canonique, j'ai écrit une fonction pour vérifier si une main est canonique. Si elle n'est pas canonique, je l'ignore. J'ai défini rang = carte % 13 et couleur = carte / 13. Aucune de ces différences n'est 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

Il génère le nombre correct de permutations :

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

Answer 2

Voici une solution Python qui fait appel à numpy et génère les donnes canoniques ainsi que leur multiplicité. J'utilise le module itertools de Python pour créer les 24 permutations possibles de 4 couleurs, puis pour itérer sur les 2 598 960 donnes possibles de 5 cartes. Chaque donne est permutée et convertie en un identifiant canonique en seulement 5 lignes. C'est assez rapide car la boucle ne fait que 10 itérations pour couvrir toutes les donnes et n'est nécessaire que pour gérer les besoins en mémoire. Toutes les opérations lourdes sont effectuées efficacement en numpy, à l'exception de l'utilisation de la fonction itertools.combinations . C'est une honte que cela ne soit pas supporté directement dans 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

Answer 3

Votre problème semblait intéressant, j'ai donc simplement essayé de l'implémenter en bouclant sur toutes les mains possibles de manière triée. Je n'ai pas regardé votre code en détail, mais il semble que mon implémentation soit assez différente de la vôtre. Devinez le nombre de mains que mon script a trouvé : 160537

• Mes mains sont toujours triées, par exemple 2 3 4 4 D
• S'il y a 2 cartes égales, la couleur est également triée (les couleurs sont simplement appelées 0,1,2,3).
• la première carte a toujours la couleur 0, la seconde la couleur 0 ou 1
• Une carte ne peut avoir que la couleur d'une carte précédente ou le nombre immédiatement supérieur, par exemple, si les cartes 1+2 ont la couleur 0, la carte trois ne peut avoir que les couleurs 0 ou 1.

Êtes-vous sûr que le chiffre indiqué sur wikipedia est correct ?

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)

Answer 4

Je ne suis pas un joueur de poker, donc les détails de la préséance des mains me dépassent. Mais il semble que le problème soit que vous traversez l'espace des "ensembles de 5 cartes" en générant des ensembles à partir du jeu, alors que vous devriez traverser l'espace des "mains de poker distinctes".

L'espace des mains distinctes nécessitera une nouvelle grammaire. L'important est de capturer exactement les informations qui sont pertinentes pour la préséance des mains. Par exemple, il n'y a que 4 mains qui sont des flushs royaux, donc ces mains peuvent être décrites par le symbole "RF" plus un indicateur de couleur, comme "RFC" pour flush royal à trèfle. Une couleur de cœur 10-high pourrait être "FLH10" (je ne suis pas sûr qu'il y ait d'autres caractéristiques de précédence des couleurs, mais je pense que c'est tout ce que vous devez savoir). Une main qui est "2C 2S AH 10C 5D" serait une expression plus longue, quelque chose comme "PR2 A 10 5" si je comprends bien votre problème initial.

Une fois que vous avez défini la grammaire des mains distinctes, vous pouvez l'exprimer sous forme d'expressions régulières, qui vous indiqueront comment générer l'espace entier des mains distinctes. Ça a l'air amusant !

Answer 5

Vous pourriez simplement donner à toutes les mains un ordre canonique de valeurs (A à K), puis attribuer des lettres de couleur abstraites en fonction de leur ordre de première apparition dans cet ordre.

Exemple : JH 4C QD 9C 3D serait converti en 3a 4b 9b Jc Qa.

La génération devrait mieux fonctionner en tant que programmation dynamique :

• commencer avec un ensemble d'une seule main qui est vide,
• faire un nouveau jeu :
  • pour chaque main de l'ancien jeu, générer chaque main possible en ajoutant une des cartes restantes
  • canoniser toutes les nouvelles mains
  • supprimer les doublons