एक सीधे ड्रा के लिए पोकर हाथ का परीक्षण करने के लिए एल्गोरिदम (4 से सीधे)?

Question

मैं मज़े के लिए पोकर मूल्यांकन पुस्तकालय लिखने के झुंड में हूं और कार्ड के दिए गए सेट के लिए ड्रॉ (ओपन एंड, गॉटशॉट) के परीक्षण की क्षमता जोड़ने की सोच रहा हूं।

बस सोच रहा है कि "कला की स्थिति" इसके लिए क्या है? मैं अपनी मेमोरी पदचिह्न को उचित रखने की कोशिश कर रहा हूं, इसलिए एक लुकअप टेबल का उपयोग करने का विचार अच्छी तरह से नहीं बैठता है लेकिन एक आवश्यक बुराई हो सकती है।

• घटाना सेट में सभी कार्ड के पद से सबसे कम रैंक:

  मेरे वर्तमान योजना की तर्ज पर है।

• यह देखने के लिए देखें कि कुछ अनुक्रम i.e .: 0,1,2,3 या 1,2,3,4 (ओईएसडी के लिए) संशोधित संग्रह का सबसेट है।

मैं बेहतर जटिलता के अनुसार काम करने की उम्मीद कर रहा हूं, क्योंकि 7 कार्ड या 9 कार्ड सेट मेरे दृष्टिकोण का उपयोग करके रोक लगाएंगे।

कोई भी इनपुट और/या बेहतर विचारों की सराहना की जाएगी।

Answer 1

सबसे तेजी से दृष्टिकोण शायद प्रत्येक कार्ड रैंक के लिए एक सा मुखौटा आवंटित करने के लिए (जैसे ड्यूस = 1, तीन = 2, चार = 4, पाँच = 8, छह = 16, सात = 32, आठ = 64, नौ = 128, दस = 256, जैक = 512, रानी = 1024, राजा = 2048, एसी = 40 9 6), और हाथ में सभी कार्डों के मुखौटे मूल्यों को एक साथ। फिर यह इंगित करने के लिए एक 8192-एलिमेंट लुकअप टेबल का उपयोग करें कि हाथ एक सीधा, ओपन-एंडर, एक आंत-शॉट, या महत्व का कुछ भी नहीं है (कोई निष्पादन समय को प्रभावित किए बिना विभिन्न प्रकार के बैकडोर सीधे ड्रॉ भी शामिल कर सकता है)।

संयोग से, अलग-अलग बिटमैस्क मानों का उपयोग करके, कोई अन्य उपयोगी हाथों को दो तरह की तरह, तीन तरह की तरह इत्यादि का पता लगा सकता है। यदि किसी के पास 64-बिट पूर्णांक गणित उपलब्ध है, तो घन का उपयोग करें ऊपर बताए गए बिट मास्क (इसलिए deuce = 1, three = 8, आदि तक एसी = 2^36 तक) और कार्ड के मानों को एक साथ जोड़ दें। यदि नतीजा है, और 04444444444444 (ऑक्टल) के साथ शून्य है, तो हाथ चार प्रकार का है। अन्यथा, अगर 01111111111111 प्लस जोड़ना है, और 04444444444444 के साथ गैर-शून्य उत्पन्न होता है, तो हाथ तीन प्रकार का या पूर्ण-घर होता है। अन्यथा, यदि परिणाम, और 02222222222222 के साथ गैर-शून्य है, तो हाथ या तो एक जोड़ी या दो जोड़ी है। यह देखने के लिए कि क्या एक हाथ में दो या दो से अधिक जोड़े हैं, और '02222222222222 के साथ हाथ मान, और उस मान को सहेजें। सहेजे गए मूल्य के साथ 1, और 'और' परिणाम घटाएं। यदि शून्य नहीं है, तो हाथ में कम से कम दो जोड़े होते हैं (इसलिए यदि इसमें तीन प्रकार का एक प्रकार है, तो यह एक पूर्ण घर है, अन्यथा यह दो जोड़ी है)।

एक विभाजन नोट के रूप में, सीधे जांच करने के लिए गणना की गई गणना आपको यह निर्धारित करने देगी कि कार्ड के कितने अलग रैंक हैं। यदि एन कार्ड और एन अलग-अलग रैंक हैं, तो हाथ में कोई भी जोड़ा या बेहतर नहीं हो सकता है (लेकिन निश्चित रूप से सीधे या फ्लश हो सकता है)। यदि एन -1 अलग-अलग रैंक हैं, तो हाथ में एक जोड़ी होती है। केवल तभी कम अलग-अलग रैंकों में से एक को अधिक परिष्कृत तर्क का उपयोग करना चाहिए (यदि एन -2 है, तो हाथ दो-जोड़ी या तीन तरह का हो सकता है; यदि एन -3 या उससे कम, तो हाथ " तीन जोड़ी "(स्कोर दो जोड़ी के रूप में), पूर्ण घर, या चार तरह का)।

एक और बात: यदि आप 8192-तत्व लुकअप टेबल का प्रबंधन नहीं कर सकते हैं, तो आप 512-तत्व लुकअप तालिका का उपयोग कर सकते हैं।उपरोक्त के रूप में बिटमैस्क की गणना करें, और फिर सरणी [bitmask & 511] और सरणी [बिटमास्क >> 4], और परिणामों पर लुकअप करें। कोई भी वैध सीधा या ड्रा एक या अन्य लुकअप पर पंजीकृत होगा। ध्यान दें कि यह आपको सीधे विभिन्न रैंकों की संख्या नहीं देगा (क्योंकि छः से दस कार्ड दोनों लुकअप में गिना जाएगा) लेकिन एक ही सरणी के लिए एक और लुकअप (सरणी [बिटमैस्क >> 9] का उपयोग करके) केवल जैक की गणना करेगा एसेस के माध्यम से।

Answer 2

अद्यतन: प्रति ईसाई मान की टिप्पणी ... यह हो सकता है:

के A1 के रूप में प्रस्तुत किया जाता है कहते हैं, करते हैं। 11 के रूप में J, Q 12 के रूप में, आदि

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 

आप भी इस मामले को संभाल जब जब सही लगातार देख बाईं लगातार कार्ड और सही लगातार ताश के पत्तों की गिनती के लिए देखने के लिए कार्यों को परिभाषित करने की आवश्यकता होगी ... और , K के बाद, A लगातार है।

Answer 3

यह एक बेवकूफ समाधान हो सकता है, लेकिन मुझे पूरा यकीन है कि यह काम करेगा, हालांकि मुझे परफॉर्मेंस मुद्दों के बारे में निश्चित नहीं है।

मान लीजिए कि कार्ड संख्या 1 - 13 द्वारा दर्शाए जाते हैं, तो यदि आपके 4 कार्ड्स की संख्या 3 या 4 (उच्चतम से निम्नतम कार्ड रैंक तक) है और इसमें कोई डुप्लीकेट नहीं है तो आपके पास एक संभावित ड्रॉ है ।

3 की एक श्रृंखला का तात्पर्य है कि आपके पास ओपन-एंड ड्रा है उदाहरण के लिए 2,3,4,5 में 3 की एक श्रृंखला है और इसमें कोई डुप्लिकेट नहीं है।

4 की एक श्रृंखला का तात्पर्य है कि आपके पास एक गॉटशॉट है (जैसा कि आपने इसे कहा है) उदाहरण के लिए 5,6,8,9 में 4 की एक श्रृंखला है और इसमें कोई डुप्लिकेट नहीं है।

Answer 4

मुझे पता है कि आपने कहा है कि आप मेमोरी पदचिह्न को जितना संभव हो सके रखना चाहते हैं, लेकिन एक बहुत मेमोरी कुशल लुकअप टेबल ऑप्टिमाइज़ेशन है जिसे मैंने कुछ पोकर हैंड मूल्यांकनकर्ताओं में उपयोग किया है और मैंने इसे स्वयं इस्तेमाल किया है। यदि आप भारी पोकर सिमुलेशन कर रहे हैं और सर्वोत्तम संभव प्रदर्शन की आवश्यकता है, तो आप इसे विचार करना चाहेंगे। हालांकि मैं इस मामले में प्रवेश करता हूं, अंतर इतना बड़ा नहीं है क्योंकि सीधे ड्रॉ के लिए परीक्षण बहुत महंगा संचालन नहीं है, लेकिन उसी सिद्धांत का उपयोग पोकर प्रोग्रामिंग में हर प्रकार के हाथ मूल्यांकन के लिए किया जा सकता है।

विचार हम एक हैश समारोह निम्नलिखित गुण है कि एक तरह का बनाने के है जो:
1) की गणना करता है कार्ड के प्रत्येक अलग सेट के लिए एक अनूठा मूल्य रैंकों
2) अर्थ में सममित है कि यह नहीं करता है 'है टी
के आदेश पर निर्भर करता है इसका उद्देश्य लुकअप तालिका में आवश्यक तत्वों की संख्या को कम करना है।

ऐसा करने का एक साफ तरीका प्रत्येक रैंक (2-> 2, 3-> 3, 4-> 5, 5-> 7, 6-> 11, 7-> 13, 8-> 17, 9-> 1 9, टी-> 23, जे-> 2 9, क्यू-> 31, के-> 37, ए-> 41), और फिर प्राइम के उत्पाद की गणना करें। उदाहरण के लिए यदि कार्ड 39TJQQ हैं, तो हैश 3653625 9 है।

लुकअप टेबल बनाने के लिए आप रैंक के सभी संभावित संयोजनों के माध्यम से जाते हैं, और यह निर्धारित करने के लिए कुछ सरल एल्गोरिदम का उपयोग करते हैं कि वे सीधे ड्रॉ बनाते हैं या नहीं। प्रत्येक संयोजन के लिए आप हैश मान की भी गणना करते हैं और फिर परिणामों को उस मानचित्र में संग्रहीत करते हैं जहां कुंजी हैश और मान सीधे ड्रॉ चेक का परिणाम है। यदि कार्ड की अधिकतम संख्या छोटी है (4 या उससे कम) तो एक रैखिक सरणी भी संभव हो सकती है।

लुकअप टेबल का उपयोग करने के लिए आप पहले कार्ड के विशेष सेट के लिए हैश की गणना करते हैं और फिर मानचित्र से संबंधित मान पढ़ते हैं।

यहां सी ++ में एक उदाहरण है। मैं गारंटी नहीं देता कि यह सही तरीके से काम कर रहा है और इसे शायद हैश_मैप के बजाय क्रमबद्ध सरणी और बाइनरी खोज का उपयोग करके बहुत अनुकूलित किया जा सकता है। इस उद्देश्य के लिए हैश_मैप थोड़ी धीमी है।

#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 

}