测试扑克手牌是否为顺子听牌（4 为顺子）的算法？

Question

我正在为好玩而编写扑克评估库，并且希望添加测试给定牌组的听牌（开放式、内断）的功能。

只是想知道这方面的“最先进技术”是什么？我试图保持我的内存占用合理，所以使用查找表的想法不太合适，但可能是一个必要的邪恶。

我当前的计划是这样的：

• 从该组中所有卡牌的等级中减去最低等级。
• 查看某个序列，即：0,1,2,3 或 1,2,3,4（对于 OESD）是否是修改后的集合的子集。

我希望在复杂性方面做得更好，因为使用我的方法，7 张卡或 9 张卡组会让事情陷入停滞。

任何意见和/或更好的想法将不胜感激。

Answer 1

最快的方法可能是为每个卡牌分配一个位掩码（例如 deuce=1、三=2、四=4、五=8、六=16、七=32、八=64、九=128、十=256 ，jack=512，queen=1024，king=2048，ace=4096），并将手上所有牌的掩码值或在一起。然后使用 8192 个元素的查找表来指示这手牌是否是顺子、开放式、内脏击球或无意义（还可以包括各种类型的后门顺子听牌，而不影响执行时间）。

顺便说一句，使用不同的位掩码值，可以快速检测其他有用的牌，例如两手牌、三手牌等。如果有 64 位整数数学可用，请使用指示位的立方上面的掩码（所以 deuce=1，三=8，等等，直到 ace=2^36）并将卡片的值加在一起。如果与 04444444444444（八进制）进行与运算的结果非零，则这手牌是四手牌。否则，如果加上 01111111111111，并与 04444444444444 相加得到非零值，则这手牌是三张牌或葫芦。否则，如果与 02222222222222 的结果非零，则这手牌要么是一对，要么是两对。要查看一手牌是否包含两对或更多对，请将手牌值与 02222222222222 进行“和”，并保存该值。减去 1，并将结果与​​保存的值进行“与”。如果非零，则这手牌至少包含两对（因此，如果它包含三对，则为葫芦；否则为两对）。

顺便说一句，检查顺子的计算还可以让您快速确定手中有多少张不同等级的牌。如果有 N 张牌和 N 个不同的等级，则这手牌不能包含任何对子或更好的牌（但当然可能包含顺子或同花）。如果有 N-1 个不同的等级，则这手牌恰好包含一对。只有当不同等级较少时，才必须使用更复杂的逻辑（如果有 N-2，则这手牌可能是两对或三对；如果 N-3 或更少，则这手牌可能是“三对”（得分为两对）、葫芦、或四对）。

还有一件事：如果您无法管理 8192 个元素的查找表，您可以使用 512 个元素的查找表。如上所述计算位掩码，然后在 array[bitmask & [511] 和数组[位掩码>> 4]，并对结果进行“或”运算。任何合法的顺子或平局都将在一个或其他查找中注册。请注意，这不会直接为您提供不同等级的数量（因为卡六到十将在两次查找中计数），但对同一数组的另一次查找（使用 array[bitmask >> 9]）将仅计数J 通过 A。

Answer 2

我知道您说过您希望内存占用尽可能小，但是有一种内存效率很高的查找表优化，我已经在一些扑克牌评估器中看到过它的使用，并且我自己也使用过它。如果您正在进行大量的扑克模拟并需要尽可能最佳的性能，您可能需要考虑这一点。虽然我承认在这种情况下差异并没有那么大，因为测试顺子听牌并不是非常昂贵的操作，但是相同的原理可以用于扑克编程中几乎所有类型的手牌评估。

我们的想法是创建一种具有以下属性的哈希函数：
1) 计算每组不同卡牌等级的唯一值
2) 是对称的，因为它不依赖于卡片的顺序
这样做的目的是减少查找表中所需的元素数量。

一种巧妙的方法是为每个等级分配一个素数（2->2、3->3、4->5、5->7、6->11、7->11）。 13、8→17、9→19、T→23、J→29、Q→31、K→37、A→41)，然后计算乘积的素数。例如，如果牌是 39TJQQ，则哈希值是 36536259。

要创建查找表，您需要遍历所有可能的排名组合，并使用一些简单的算法来确定它们是否形成平局。对于每个组合，您还计算哈希值，然后将结果存储在映射中，其中键是哈希值，值是直接抽签检查的结果。如果卡片的最大数量很小（4 个或更少），那么即使是线性阵列也可能是可行的。

要使用查找表，您首先需要计算特定卡片组的哈希值，然后从映射中读取相应的值。

这是一个 C++ 示例。我不保证它正常工作，并且通过使用排序数组和二分搜索而不是 hash_map 可能可以对其进行很多优化。 hash_map 对于这个目的来说有点慢。

#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

这可能是一个幼稚的解决方案，但我很确定它会起作用，尽管我不确定性能问题。

再次假设卡片由数字 1 - 13 表示，那么如果您的 4 张卡片的数字范围为 3 或 4（从最高到最低的卡片等级）并且不包含重复项，那么您可能有顺子抽奖。

范围为 3 意味着您有一个开放式平局，例如 2,3,4,5 的范围为 3 并且不包含重复项。

范围为 4 意味着您有一个内音（如您所说），例如 5、6、8、9 的范围为 4 并且不包含重复项。

Answer 4

更新：根据 Christian Mann 的评论...可以是这样的：

比方说，A 表示为 1。 J 为 11，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是连续的。