9

我正在为好玩而编写一个扑克评估库而痛苦，并希望增加测试一组给定卡牌的平局（开放式，内奏）的能力。

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

我目前的计划是这样的：

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

我希望在复杂性方面做得更好，因为 7 卡或 9 卡套使用我的方法会使事情停止。

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

4

4 回答 4

7

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

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

一种巧妙的方法是为每个等级分配一个素数 (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)，然后计算素数的乘积。例如，如果卡片是 39TJQQ，那么哈希是 36536259。

要创建查找表，您需要检查所有可能的排名组合，并使用一些简单的算法来确定它们是否形成顺子。对于每个组合，您还计算哈希值，然后将结果存储在映射中，其中 Key 是哈希值，Value 是直接抽签检查的结果。如果卡片的最大数量很小（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

}
于 2010-10-29T14:32:59.437 回答
7

最快的方法可能是为每个卡片等级分配一个位掩码（例如 deuce=1、3=2、4=4、5=8、6=16、7=32、8=64、9=128、10=256 , jack=512, queen=1024, king=2048, ace=4096)，然后将手中所有牌的掩码值进行或运算。然后使用一个包含 8192 个元素的查找表来指示这手牌是顺子、开局者、内手顺子还是无关紧要的牌（也可以包括各种类型的后门顺子听牌，而不会影响执行时间）。

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

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

还有一件事：如果您无法管理 8192 元素的查找表，则可以使用 512 元素的查找表。计算上面的位掩码，然后在 array[bitmask & 511] 和 array[bitmask >> 4] 上进行查找，并对结果进行 OR 运算。任何合法的顺子或听牌都将在一次或其他查找中注册。请注意，这不会直接为您提供不同等级的数量（因为在两次查找中都会计算 6 到 10 张牌），但是对同一个数组的再查找一次（使用数组 [位掩码 >> 9]）将只计算千斤顶通过王牌。

于 2010-10-31T23:31:17.677 回答
3

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

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

范围为 3 表示您有一个开放式抽牌，例如 2,3,4,5 的范围为 3，并且不包含重复。

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

于 2010-10-28T09:49:06.897 回答
0

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

比方说，A表示为1。 J如 11、12Q等。

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连续的。

于 2010-10-28T05:30:33.843 回答