Algoritmi per testare una mano di poker per un sorteggio dritto (da 4 a una dritta)?

Question

Sono in preda alla scrittura di una biblioteca di valutazione del poker per divertimento e sto cercando di aggiungere la possibilità di testare i sorteggi (aperto, gutshot) per un determinato set di carte.

Ti chiedi solo quale sia lo "stato dell'arte" per questo? Sto cercando di mantenere ragionevole l'impronta della mia memoria, quindi l'idea di usare una tavola di ricerca non si adatta bene ma potrebbe essere un male necessario.

Il mio piano attuale è sulla falsariga di:

• Sottrai il rango più basso dal rango di tutte le carte nel set.
• Cerca se una certa sequenza IE: 0,1,2,3 o 1,2,3,4 (per OESDS) è un sottoinsieme della raccolta modificata.

Spero di fare una migliore complessità per quanto riguarda la complessità, poiché 7 carte da 7 o 9 carte avranno una brusca approccio usando il mio approccio.

Qualsiasi input e/o idee migliori sarebbero apprezzate.

Answer 1

L'approccio più veloce probabilmente per assegnare una maschera bit per ciascun rango di carta (ad es. Deuce = 1, tre = 2, quattro = 4, cinque = 8, sei = 16, sette = 32, otto = 64, nove = 128, dieci = 256 , jack = 512, regina = 1024, re = 2048, ace = 4096) e o insieme i valori della maschera di tutte le carte nella mano. Quindi utilizzare una tabella di ricerca ad elementi 8192 per indicare se la mano è dritta, aperta, uno shot intestinale o nulla di significato (si potrebbe anche includere i vari tipi di pareggio dritto backdoor senza influire sul tempo di esecuzione).

Per inciso, usando diversi valori di Bitmask, si possono rapidamente rilevare altre mani utili come due di tipo, tre di mezzo genere, ecc. Se uno ha una matematica intera a 64 bit disponibile, utilizzare il cubo del bit indicato maschere sopra (quindi deuce = 1, tre = 8, ecc. fino ad Ace = 2^36) e aggiungere i valori delle carte. Se il risultato, e, con 0444444444444 (ottale) è diverso da zero, la mano è un tipo quattro. In caso contrario, se aggiunge più 0111111111111 e e con 0444444444444 produce diverso da zero, la mano è un tre o meno nel suo genere. Altrimenti, se il risultato, e, con 02222222222222, è diverso da zero, la mano è una coppia o due coppie. Per vedere se una mano contiene due o più coppie "e" il valore della mano con 022222222222222 e salva quel valore. Sottrai 1 e 'e' il risultato con il valore salvato. Se diverso da zero, la mano contiene almeno due coppie (quindi se contiene un tre di mezzo, è una casa piena; altrimenti è a due coppie).

Come nota di separazione, il calcolo effettuato per verificare una dritta consentirà anche di determinare rapidamente quanti ranghi di carta diversi sono nella mano. Se ci sono N carte e N diversi ranghi, la mano non può contenere coppie o meglio (ma potrebbe contenere una dritta o un flush, ovviamente). Se ci sono gradi N-1 diversi, la mano contiene esattamente una coppia. Solo se ci sono meno ranghi diversi devono usare una logica più sofisticata (se ci sono N-2, la mano potrebbe essere a due o tre di un po '; se n-3 o meno, la mano potrebbe essere una " Tre coppia "(punteggi come due coppie), casa piena o quattro di loro nel suo genere).

Un'altra cosa: se non riesci a gestire una tabella di ricerca dell'elemento 8192, è possibile utilizzare una tabella di ricerca ad elementi 512. Calcola la maschera bit come sopra, quindi fai ricerche su Array [Bitmask & 511] e Array [Bitmask >> 4] e i risultati. Qualsiasi legittimo dritto o pareggio si registrerà su una o altra ricerca. Si noti che questo non ti darà direttamente il numero di gradi diversi (poiché le carte da sei a dieci verranno conteggiate in entrambe le ricerche) ma un'altra ricerca allo stesso array (usando Array [Bitmask >> 9]) conta solo i jacks attraverso assi.

Answer 2

So che hai detto che vuoi mantenere l'impronta di memoria il più piccola possibile, ma c'è un'ottimizzazione della tabella di ricerca abbastanza efficiente dalla memoria che ho visto usato in alcuni valutatori delle mani del poker e l'ho usato da solo. Se stai facendo simulazioni di poker pesanti e hai bisogno delle migliori prestazioni possibili, potresti voler considerare questo. Anche se lo ammetto in questo caso, la differenza non è così grande perché i test per un sorteggio dritto non sono un funzionamento molto costoso, ma lo stesso principio può essere usato per praticamente ogni tipo di valutazione delle mani nella programmazione del poker.

L'idea è che creiamo una sorta di funzione hash che ha le seguenti proprietà:
1) Calcola un valore univoco per ogni diverso set di gradi di carte
2) è simmetrico nel senso che non dipende dall'ordine delle carte
Lo scopo è ridurre il numero di elementi necessari nella tabella di ricerca.

Un modo pulito per farlo è assegnare un numero primo a ciascun grado (2-> 2, 3-> 3, 4-> 5, 5-> 7, 6-> 11, 7-> 13, 8-> 17 , 9-> 19, t-> 23, j-> 29, q-> 31, k-> 37, a-> 41), quindi calcola il prodotto dei primi. Ad esempio, se le carte sono 39TJQQ, l'hash è 36536259.

Per creare la tabella di ricerca, visitare tutte le possibili combinazioni di ranghi e utilizzare un semplice algoritmo per determinare se formano un sorteggio diretto. Per ogni combinazione si calcola anche il valore di hash e quindi si memorizza i risultati in una mappa in cui la chiave è l'hash e il valore è il risultato del controllo di disegno diretto. Se il numero massimo di carte è piccolo (4 o meno), anche un array lineare potrebbe essere fattibile.

Per utilizzare la tabella di ricerca, si calcola prima l'hash per il particolare set di carte e quindi leggi il valore corrispondente dalla mappa.

Ecco un esempio in C ++. Non garantisco che funzioni correttamente e probabilmente potrebbe essere ottimizzato usando un array ordinato e una ricerca binaria invece di Hash_map. Hash_map è un po 'lento per questo scopo.

#include <iostream>
#include <vector>
#include <hash_map>
#include <numeric>
using namespace std;

const int MAXCARDS = 9;
stdext::hash_map<long long, bool> lookup;

//"Hash function" that is unique for a each set of card ranks, and also
//symmetric so that the order of cards doesn't matter.
long long hash(const vector<int>& cards)
{
    static const int primes[52] = {
        2,3,5,7,11,13,17,19,23,29,31,37,41,
        2,3,5,7,11,13,17,19,23,29,31,37,41,
        2,3,5,7,11,13,17,19,23,29,31,37,41,
        2,3,5,7,11,13,17,19,23,29,31,37,41
    };

    long long res=1;
    for(vector<int>::const_iterator i=cards.begin();i!=cards.end();i++)
        res *= primes[*i];
    return res;
}

//Tests whether there is a straight draw (assuming there is no
//straight). Only used for filling the lookup table.
bool is_draw_slow(const vector<int>& cards)
{
    int ranks[14];
    memset(ranks,0,14*sizeof(int));

    for(vector<int>::const_iterator i=cards.begin();i!=cards.end();i++)
        ranks[ *i % 13 + 1 ] = 1;
    ranks[0]=ranks[13]; //ace counts also as 1

    int count = ranks[0]+ranks[1]+ranks[2]+ranks[3];
    for(int i=0; i<=9; i++) {
        count += ranks[i+4];
        if(count==4)
            return true;
        count -= ranks[i];
    }

    return false;
};

void create_lookup_helper(vector<int>& cards, int idx)
{
    for(;cards[idx]<13;cards[idx]++) {
        if(idx==cards.size()-1)
            lookup[hash(cards)] = is_draw_slow(cards);
        else {
            cards[idx+1] = cards[idx];
            create_lookup_helper(cards,idx+1);
        }
    }
}

void create_lookup()
{
    for(int i=1;i<=MAXCARDS;i++) {
        vector<int> cards(i);
        create_lookup_helper(cards,0);
    }
}

//Test for a draw using the lookup table
bool is_draw(const vector<int>& cards)
{
    return lookup[hash(cards)];
};

int main(int argc, char* argv[])
{
    create_lookup();

    cout<<lookup.size()<<endl; //497419

    int cards1[] = {1,2,3,4};
    int cards2[] = {0,1,2,7,12};
    int cards3[] = {3,16,29,42,4,17,30,43};

    cout << is_draw(vector<int>(cards1,cards1+4)) <<endl; //true
    cout << is_draw(vector<int>(cards2,cards2+5)) <<endl; //true
    cout << is_draw(vector<int>(cards3,cards3+8)) <<endl; //false

}

Answer 3

Questa potrebbe essere una soluzione ingenua, ma sono abbastanza sicuro che funzionerebbe, anche se non sono sicuro dei problemi di perfomance.

Supponendo che le carte siano rappresentate dai numeri 1 - 13, quindi se le 4 carte hanno un intervallo numerico di 3 o 4 (dal più alto al più basso rango di carte) e non contengono duplicati, allora hai un possibile disegno diretto.

Un intervallo di 3 implica che hai un disegno aperto, ad esempio 2,3,4,5, ha un intervallo di 3 e non contiene duplicati.

Un intervallo di 4 implica che hai un gutshot (come lo hai chiamato) ad esempio 5,6,8,9 ha un intervallo di 4 e non contiene duplicati.

Answer 4

Aggiornamento: per commento di Christian Mann ... può essere questo:

diciamo, A è rappresentato come 1. J come 11, Q come 12, ecc.

loop through 1 to 13 as i
  if my cards already has this card i, then don't worry about this case, skip to next card
  for this card i, look to the left for number of consecutive cards there is
  same as above, but look to the right
  if count_left_consecutive + count_right_consecutive == 4, then found case

Dovrai definire le funzioni per cercare il conteggio delle carte consecutive sinistro e delle carte consecutive a destra ... e gestire anche la custodia quando si guarda a destra consecutiva, dopo K, il A è consecutivo.