Algoritmi per testare una mano di poker per un progetto di scala (4 per una scala)?

Question

Sono in procinto di scrivere una libreria di valutazione del poker per divertimento e sto cercando di aggiungere la possibilità di testare i disegni (open ended, gutshot) per un dato set di carte.

Basta chiedersi quale sia lo "stato dell'arte" per questo? Sto cercando di mantenere l'impronta della mia memoria ragionevole, quindi l'idea di usare un look up table non sta bene ma potrebbe essere un male necessario.

Il mio piano attuale è lungo le linee di:

• sottrarre il rango più basso dal rango di tutte le carte nel set.
• cercare di vedere se una sequenza specifica: 0,1,2,3 o 1,2,3,4 (per OESD) è un sottoinsieme della raccolta modificata.

Spero di fare meglio la saggia complessità, come 7 carte o 9 set di carte fermeranno le cose con un arresto con il mio approccio.

Qualsiasi input e/o idee migliori sarebbe apprezzato.

Answer 1

L'approccio più veloce probabilmente per assegnare una maschera di bit per ogni rango carta (es deuce = 1, tre = 2, quattro = 4, cinque = 8, sei = 16, sette = 32, otto = 64, nove = 128, dieci = 256, jack = 512, queen = 1024, king = 2048, asso = 4096) e OR insieme ai valori della maschera di tutte le carte nella mano. Quindi usa una tabella di ricerca di 8192 elementi per indicare se la mano è una scala, un open-ender, un gut-shot, o un nulla di significato (potresti anche includere i vari tipi di scala dritta backdoor senza influenzare il tempo di esecuzione).

Per inciso, utilizzando diversi valori di maschera di bit, è possibile rilevare rapidamente altre mani utili come due di un tipo, tre di un tipo, ecc. Se uno ha matematica a 64 bit interi disponibili, utilizzare il cubo delle maschere bit indicate sopra (quindi deuce = 1, tre = 8, ecc. fino all'asso = 2^36) e sommare i valori delle carte. Se il risultato, e con 04444444444444 (ottale) è diverso da zero, la mano è un quattro di un tipo. Altrimenti, se aggiungendo più 01111111111111 e anding con 04444444444444 produce un valore diverso da zero, la mano è un tris o un full-house. Altrimenti, se il risultato, e con 02222222222222 è diverso da zero, la mano è una coppia o una doppia coppia. Per vedere se una mano contiene due o più coppie, "e" il valore della mano con 02222222222222, e salvare quel valore. Sottrai 1 e 'e' il risultato con il valore salvato. Se non zero, la mano contiene almeno due coppie (quindi se contiene un tris, è un full, altrimenti è una doppia coppia).

Come nota di partenza, il calcolo fatto per verificare una scala ti permetterà anche di determinare rapidamente quanti diversi gradi di carte sono nella mano. Se ci sono N carte e N diversi gradi, la mano non può contenere alcuna coppia o migliore (ma potrebbe contenere una scala o un colore, ovviamente). Se ci sono diversi ranghi N-1, la mano contiene precisamente una coppia. Solo se ci sono meno gradi diversi bisogna usare una logica più sofisticata (se ci sono N-2, la mano potrebbe essere doppia o tripla, se N-3 o meno, la mano potrebbe essere un " three-pair "(punteggi come due coppie), full house o four-of-a-kind).

Un'altra cosa: se non è possibile gestire una tabella di ricerca di 8192 elementi, è possibile utilizzare una tabella di ricerca di 512 elementi.Calcola la maschera di bit come sopra, quindi esegui le ricerche su array [bitmask & 511] e array [maschera di bit >> 4] e OR sui risultati. Qualsiasi diritto o pareggio legittimo si registrerà su una o più ricerche. Nota che questo non ti darà direttamente il numero di ranghi diversi (dal momento che le carte da sei a dieci verranno conteggiate in entrambe le ricerche) ma un'ultima ricerca per lo stesso array (usando array [bitmask >> 9] conterebbe solo i jack attraverso gli assi.

Answer 2

Update: per il commento di Christian Mann ... può essere questo:

diciamo, A è rappresentato come 1. J come 11, come Q 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 

è necessario definire le funzioni a cercare il conteggio delle carte consecutive a sinistra e carte consecutive giuste ... e anche gestire il caso in cui, quando guardando a destra consecutivo , dopo K, lo A è consecutivo.

Answer 3

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

Supponendo nuovamente che le carte siano rappresentate dai numeri 1 - 13, quindi se le 4 carte hanno un range numerico di 3 o 4 (dal più alto al più basso grado di carte) e non contengono duplicati, allora si ha un possibile pareggio diretto .

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

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

Answer 4

So che hai detto che vuoi mantenere il footprint della memoria il più piccolo possibile, ma c'è una ottimizzazione della tabella di ricerca abbastanza efficiente per la memoria che ho visto usata in alcuni valutatori di poker e l'ho usata io stesso. Se stai facendo delle pesanti simulazioni di poker e hai bisogno della migliore prestazione possibile, potresti prendere in considerazione questo. Anche se ammetto che in questo caso la differenza non è così grande perché il test per un progetto di scala non è un'operazione molto costosa, ma lo stesso principio può essere utilizzato per praticamente ogni tipo di valutazione della mano nella programmazione del poker.

L'idea è che si crea una sorta di una funzione hash che ha le seguenti proprietà:
1) calcola un valore univoco per ciascuna diversa serie di carta ranghi
2) è simmetrica, nel senso che esso doesn' t dipende dall'ordine delle carte
Lo scopo di questo è di ridurre il numero di elementi necessari nella tabella di ricerca.

Un modo semplice 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 calcolare il prodotto dei numeri primi. Ad esempio se le carte sono 39TJQQ, l'hash è 36536259.

Per creare la tabella di ricerca, è possibile utilizzare tutte le possibili combinazioni di gradi e utilizzare un semplice algoritmo per determinare se formano un progetto di scala. Per ciascuna combinazione si calcola anche il valore hash e quindi si memorizzano i risultati in una mappa in cui Key è l'hash e Value è il risultato del controllo di stiratura. Se il numero massimo di carte è piccolo (4 o meno), allora anche un array lineare potrebbe essere fattibile.

Per utilizzare la tabella di ricerca, è innanzitutto necessario calcolare l'hash per il set di carte specifico e quindi leggere il valore corrispondente dalla mappa.

Ecco un esempio in C++. Non garantisco che funzioni correttamente e potrebbe essere ottimizzato molto usando una matrice ordinata e una ricerca binaria invece di hash_map. hash_map è piuttosto 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 

}