Générer les 5 mains de poker
Ce problème semble simple au premier abord, mais s'avère être beaucoup plus compliqué qu'il n'y paraît. Ça me fait trébucher pour le moment.
il y a 52c5 = 2,598,960 façons de choisir 5 cartes à partir d'un jeu de 52 cartes. Cependant, puisque les costumes sont interchangeables au poker, beaucoup d'entre eux sont équivalents - la main 2H 2C 3H 3S 4D est l'équivalent de 2D 2S 3D 3C 4H - simplement échanger les costumes autour. Selon wikipédia, il y a 134,459 5 mains de carte distinctes une fois que vous tenir compte de recolorings possibles de costume.
La question est, comment pouvons-nous générer efficacement des toutes ces mains? 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 pour évaluer les spirales rapides hors de contrôle. Mes tentatives actuelles se sont centrées sur soit générer de la profondeur-d'abord, et garder la trace des cartes actuellement générées pour déterminer quelles combinaisons et les rangs sont valides pour la prochaine carte, ou largeur-d'abord, générer toutes les cartes suivantes possibles, puis supprimer les doublons en convertissant chaque main en une version "canonique" par recoloration. Voici ma tentative d'une première solution, 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
est-ce que quelqu'un peut suggérer une meilleure façon de générer juste les mains distinctes, ou faire remarquer où je me suis trompé dans ma tentative?
12 réponses
Votre approche globale est bonne. Je suis sûr que le problème est avec votre make_canonical fonction. Vous pouvez essayer d'imprimer les mains avec num_cards réglé à 3 ou 4 et chercher des équivalences que vous avez manquées.
j'en ai trouvé un, mais il y a peut-être plus:
# 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, ci-dessous est ma solution (développé avant de regarder votre solution). J'ai utilisé une recherche en profondeur au lieu d'une recherche en largeur. Aussi, au lieu d'écrire une fonction pour transformer un la main à la forme canonique, j'ai écrit une fonction pour vérifier si une main est canonique. Si ce n'est pas canonique, je saute. J'ai défini rang = carte % 13 et costume = carte / 13. Aucune de ces différences sont importantes.
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
Voici une solution Python qui utilise numpy et génère les offres canoniques ainsi que leur multiplicité. J'utilise le module itertools de Python pour créer les 24 permutations possibles de 4 combinaisons et ensuite pour itérer les 2,598,960 offres possibles de 5 cartes. Chaque affaire est permutées et converti canonique id en 5 lignes. C'est assez rapide car la boucle ne passe que par 10 itérations pour couvrir toutes les transactions et n'est nécessaire que pour gérer les besoins en mémoire. Tout le levage lourd est fait efficacement dans numpy sauf pour l'utilisation de itertools.combinations. C'est dommage que ce ne soit pas supposé être 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
Votre problème avait l'air intéressant, j'ai donc simple essayé de l'implémente simplement en boucle sur toutes les mains possibles triés. Je n'ai pas regardé votre code en détail, mais il semble que ma mise en œuvre soit très différente de la vôtre. Devinez quel nombre de mains 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 aussi triée (les couleurs sont juste appelées 0,1,2,3)
- la première carte toujours la couleur 0, la deuxième couleur 0 ou 1
- une carte ne peut avoir que la couleur d'une carte précédente ou le numéro suivant plus grand, par exemple si la carte 1+2 a la couleur 0, la carte 3 ne peut avoir que les couleurs 0 ou 1
Etes-vous sûr, le nombre 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)
Je ne suis pas un joueur de poker, donc les détails de la préséance de main sont au-delà de moi. Mais il semble que le problème est que vous traversez l'espace de "jeux de 5 cartes" en générant des jeux à partir du deck, quand vous devriez être en train de traverser l'espace de "mains de poker distinctes".
l'espace des mains distinctes exigera une nouvelle grammaire. L'important est de saisir exactement les informations qui sont pertinentes à la main priorité. Par exemple, il n'y a que 4 mains qui sont royales flushes, de sorte que ces mains peuvent être décrites comme le symbole "RF" plus un désignateur de costume, comme "RFC" pour Royal flush dans les clubs. Une bouffée de chaleur à 10 cœurs pourrait être "FLH10" (pas sûr s'il y a d'autres caractéristiques de priorité des bouffées de chaleur, 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 undestand votre énoncé de problème initial.
une fois que vous avez défini la grammaire de mains distinctes, vous pouvez exprimer il comme des expressions régulières et qui vous diront comment générer l'espace entier de mains distinctes. Il semble amusant!
vous pouvez simplement donner à toutes les mains un ordre canonique des valeurs (A à K), puis assigner des lettres de costume abstraites selon leur ordre de première apparition dans cet ordre.
exemple: JH 4C QD 9C 3D convertirait en 3a 4b 9b JC Qa.
Génération devrait fonctionner mieux que la programmation dynamique:
- démarrer avec un ensemble d'une seule main, qui est vide,
- faire un nouvel ensemble:
- pour chaque main de l'ancien ensemble, générer chaque possible main en ajoutant une des cartes restantes
- accepter toutes les nouvelles mains
- supprimer les doublons
input Initial:
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
Étape 1: pour chaque grade supérieur ou égal au grade le plus élevé utilisé, placez toutes les combinaisons de ce grade à 0. vous pouvez vous en tirer avec seulement la vérification des cartes supérieures parce que les combinaisons inférieures seront vérifiées par les points de départ inférieurs.
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
Étape 2: Effondrement de lignes distinctes
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
Étape 3: remontez pour déterminer la première combinaison qui correspond à chaque rangée distincte, et choisissez les combinaisons qui correspondent aux rangées distinctes (identifiés par 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
maintenant la répétition pour le rang 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
Étape 4: Une fois qu'il y a 5 cellules positionnées à 1, incrémentez le total de la combinaison possible mains abstraites compter par 1 et de revenir en haut.
le nombre total de mains abstraites de la combinaison est de 134 459. C'est le code que j'ai écrit pour le tester:
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;
}
}
}
espérons qu'il est assez fragmenté pour être facilement compréhensible.
voici un algorithme simple et simple pour réduire les mains à un canonique basé sur les permutatoines de costume.
- convertissez la main en quatre bitsets, un par costume représentant les cartes du costume
- trier les bitsets
- convertir bitsets en arrière dans la main
voici à quoi ressemble l'algorithme en C++, avec quelques classes implicites de combinaison et de CardSet. Notez que la déclaration de retour convertit la main en concaténant des chaînes 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);
}
Regardez Pokersource. Le problème devient encore pire quand vous envisagez de compléter les mains compte tenu de certaines cartes déjà tirées.
le gars derrière PokerStove a fait un excellent travail dans cette direction, mais la source est divulguée.
générer des classes d'équivalence pour 5 cartes n'est pas une tâche facile. Quand j'en ai besoin, j'utilise habituellement lehttp://www.vpgenius.com/ page web. At http://www.vpgenius.com/video-poker/games/ Vous pouvez choisir la variété de jeu de poker dont vous avez besoin, et dans l'onglet "programmation" vous avez une section sur "Unique Suit Patterns". Donc simplement copier cela et charger dans le programme pourrait être plus facile que d'essayer de générer votre propre.
jetez un coup d'oeil ici:
http://specialk-coding.blogspot.com/
http://code.google.com/p/specialkpokereval/
ceux-ci considèrent une main de 5 cartes (et une main de 7 cartes) comme un entier, la somme des cartes individuelles, qui est indépendante de la combinaison. Exactement ce dont vous avez besoin.
ceci fait partie d'un schéma pour classer rapidement les mains de 7 et 5 cartes, écrites en Objectif - C et Java.
si vous êtes simplement intéressé par les mains qui donnent lieu à des classements de mains différents, il n'y a en fait que 7462 classes de mains distinctes qui doivent être considérées (voir Wikipédia