python algorithm permutation combinatorics poker

python - Generando las 5 manos de poker de cartas



algorithm permutation (12)

Este problema parece simple a primera vista, pero resulta ser mucho más complicado de lo que parece. Me tiene perplejo por el momento.

Hay 52c5 = 2,598,960 formas de elegir 5 cartas de una baraja de 52 cartas. Sin embargo, dado que los trajes son intercambiables en el póquer, muchos de estos son equivalentes, la mano 2H 2C 3H 3S 4D es equivalente a 2D 2S 3D 3C 4H, simplemente intercambia los trajes. De acuerdo con la wikipedia , hay 134,459 manecillas de 5 cartas distintas una vez que cuenta las posibles repeticiones de los trajes.

La pregunta es, ¿cómo generamos eficientemente todas estas manos posibles? No quiero generar todas las manos, luego eliminar duplicados, ya que quiero aplicar el problema a un mayor número de cartas, y el número de manos para evaluar espirales rápidas fuera de control. Mis intentos actuales se han centrado en generar primero la profundidad y hacer un seguimiento de las tarjetas generadas actualmente para determinar qué jugadas y rangos son válidos para la siguiente carta, o en primer lugar, generar todas las siguientes cartas posibles y luego eliminar las duplicadas convirtiendo cada una mano a una versión ''canónica'' por reposición. Aquí está mi intento de una solución de amplitud, 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

Desafortunadamente, esto genera demasiadas manos:

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

¿Alguien puede sugerir una mejor manera de generar solo las manos distintas, o señalar dónde me he equivocado en mi intento?

Aquí hay un algoritmo simple y directo para reducir las manos a uno canónico basado en las permutatoins del traje.

  1. Convierta la mano en cuatro juegos de monedas, una por juego que represente cartas del juego
  2. ordenar los conjuntos de bits
  3. convertir bitsets nuevamente en la mano

Este es el aspecto del algoritmo en C ++, con algunas clases implícitas de Suit y CardSet. Tenga en cuenta que la declaración de devolución convierte la mano al concatenar las cadenas 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); }

Aquí hay una solución de Python que hace uso de numpy y genera las ofertas canónicas, así como su multiplicidad. Utilizo el módulo itertools de Python para crear las 24 permutaciones posibles de 4 palos y luego iterar sobre las 2,598,960 posibles ofertas de 5 cartas. Cada transacción se permuta y se convierte en una identificación canónica en solo 5 líneas. Es bastante rápido ya que el ciclo solo pasa por 10 iteraciones para cubrir todas las transacciones y solo es necesario para administrar los requisitos de memoria. Todo el trabajo pesado se realiza de forma eficiente en numpy, excepto por el uso de itertools.combinations . Es una pena que esto no sea compatible directamente en 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

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

Paso 1: para cada rango mayor o igual que el rango más alto utilizado, configure todos los palos en ese rango a 0. Usted puede salirse con la única verificación de las cartas más altas porque las combinaciones más bajas serán verificadas por los puntos de inicio más bajos.

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

Paso 2: contraer filas 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

Paso 3: sube de nuevo determinando el primer palo que coincida con cada fila distinta, y elige los trajes que coinciden con las filas distintas (identificadas por 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

Ahora mostrando la repetición para el 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

Paso 4: Una vez que haya 5 celdas configuradas en 1, incremente el total posible de manos abstractas recuedas por 1 y recupérese.

El número total de manos abstractas posibles es de 134,459. Este es el código que escribí para probarlo:

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

Con suerte, está roto lo suficiente como para ser fácilmente comprensible.

Generar clases de equivalencia para 5 cartas no es una tarea fácil. Cuando lo necesito, suelo utilizar la página web http://www.vpgenius.com/ . En http://www.vpgenius.com/video-poker/games/ puede elegir la variedad de juegos de póquer que necesita, y en la "Pestaña de programación" tiene una sección sobre "Patrones de trajes únicos". Entonces, copiarlo y cargarlo en el programa podría ser más fácil que tratar de generar uno propio.

Lo más probable es que realmente desee generar la cantidad de manos distintas, en el sentido de no equivalentes. En ese caso, según el artículo de wikipedia hay 7462 manos posibles. Aquí hay un fragmento de Python que los enumerará a todos.

La lógica es simple: hay una mano para cada 5 conjuntos de rangos; Además, si todos los rangos son distintos, se puede formar otro tipo diferente de mano haciendo coincidir todos los palos.

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

Mira a Pokersource . El problema empeora cuando considera completar las manos dadas algunas cartas que ya se han dibujado.

El tipo detrás de PokerStove hizo un gran trabajo en esta dirección, pero se revela la fuente.

No soy un jugador de póquer, por lo que los detalles de la precedencia de la mano están más allá de mí. Pero parece que el problema es que estás atravesando el espacio de "conjuntos de 5 cartas" generando conjuntos desde el mazo, cuando debes atravesar el espacio de "manos de póker distintas".

El espacio de manos distintas requerirá una nueva gramática. Lo importante es capturar exactamente la información que es relevante para la precedencia de la mano. Por ejemplo, solo hay 4 manos que son rubores reales, por lo que esas manos se pueden describir como el símbolo "RF" más un designador de traje, como "RFC" para la escalera real en los clubes. Una descarga de corazón de 10 de alto podría ser "FLH10" (no estoy seguro de si hay otras características de prevalencia de sofocos, pero creo que eso es todo lo que necesita saber). Una mano que sea "2C 2S AH 10C 5D" sería una expresión más larga, algo así como "PR2 A 10 5" si entiendo tu enunciado de problema inicial.

Una vez que haya definido la gramática de las distintas manos, puede expresarla como expresiones regulares y eso le dirá cómo generar el espacio completo de distintas manos. ¡Suena divertido!

Si solo te interesan las manos que dan lugar a diferentes clasificaciones de manos, en realidad hay solo 7462 clases de mano distintas que deben considerarse (ver Wikipedia ).

Al crear una tabla con un ejemplo para cada clase y su multiplicidad de acompañamiento, puede verificar todas las manos relevantes ponderadas con su probabilidad bastante rápido. Es decir, suponiendo que no se conocen cartas y, por lo tanto, ya están corregidas de antemano.

Simplemente podría otorgar a todas las manos un orden canónico de valores (A a K), luego asignar letras de traje abstractas de acuerdo con su orden de aparición en ese orden.

Ejemplo: JH 4C QD 9C 3D se convertiría en 3a 4b 9b Jc Qa.

La generación debería funcionar mejor como programación dinámica:

  • comienza con un conjunto de una sola mano que está vacía,
  • hacer un nuevo conjunto:
    • para cada mano en el conjunto anterior, genere cada mano posible agregando una de las cartas restantes
    • canonicalizar todas las nuevas manos
    • eliminar duplicados

Su enfoque general es sólido. Estoy bastante seguro de que el problema radica en tu función make_canonical . Puedes intentar imprimir las manos con num_cards configuradas en 3 o 4 y buscar las equivalencias que te perdiste.

Encontré uno, pero puede haber más:

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

Como referencia, a continuación se muestra mi solución (desarrollada antes de analizar su solución). Usé una búsqueda de profundidad primero en lugar de una búsqueda de amplitud. Además, en lugar de escribir una función para transformar una mano en forma canónica, escribí una función para verificar si una mano es canónica. Si no es canónico, lo omito. Definí rango = tarjeta% 13 y suit = tarjeta / 13. Ninguna de esas diferencias es 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

Genera el número correcto de permutaciones:

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

Tu problema sonaba interesante, así que intenté implementarlo haciendo un círculo sobre todas las manos posibles de una manera ordenada. No he revisado tu código en detalle, pero parece que mi implementación es bastante diferente a la tuya. Adivina qué cantidad de manos encontró mi guión: 160537

  • Mis manos siempre están ordenadas, por ejemplo, 2 3 4 4 D
  • Si hay 2 cartas iguales, el color también se clasifica (los colores se llaman simplemente 0,1,2,3)
  • la primera carta siempre tiene color 0, el segundo color 0 o 1
  • Una carta solo puede tener el color de una carta anterior o el siguiente número más grande, por ejemplo, si la carta 1 + 2 tiene color 0, la carta tres solo puede tener los colores 0 o 1.

¿Estás seguro, el número en wikipedia es correcto?

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)