Joh*_*ter 9 language-agnostic algorithm poker
我正在为编写一个扑克评估库以获得乐趣,我希望为一组给定的卡片添加测试绘图(开放式,内容式)的能力.
只是想知道"最先进的"是什么？我试图保持我的记忆足迹合理,所以使用查找表的想法并不好,但可能是一个必要的邪恶.
我目前的计划是:
我希望能够做到更好的复杂性,因为使用我的方法,7张卡或9张卡片会使事情停止.
任何输入和/或更好的想法将不胜感激.
我知道你说你想保持尽可能小的内存占用,但是有一个非常有效的内存查找表优化,我在一些扑克手评估器中看到过,我自己也用过它.如果您正在进行大量的扑克模拟并且需要最佳性能,您可能需要考虑这一点.虽然我承认在这种情况下差异并不大,因为测试直接抽奖并不是非常昂贵的操作,但是同样的原理可以用于扑克编程中的几乎所有类型的手牌评估.
我们的想法是创建一种具有以下属性的哈希函数:
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
}
最快的方法可能是为每个卡等级分配一个位掩码(例如deuce = 1,三个= 2,四个= 4,5个= 8,6个= 16,7个= 32,8个= 64,9个= 128,10 = 256 ,jack = 512,queen = 1024,king = 2048,ace = 4096),和OR一起手中所有卡的掩码值.然后使用一个8192元素的查找表来指示手是直的,开放的,一个是直接的,还是一个没有意义的(一个也可以包括各种类型的后门直接绘制而不影响执行时间).
顺便说一句,使用不同的位掩码值,可以快速检测其他有用的手,如两种类型,三种类型等.如果有一个64位整数数学可用,使用指示位的立方体上面的面具(所以deuce = 1,三个= 8,等等,直到ace = 2 ^ 36)并将卡的值加在一起.如果结果和'04444444444444(八进制)不为零,则手是四种.否则,如果加上加01111111111111,并且和04444444444444一起产生非零,则该手是三种或全屋.否则,如果结果和'02222222222222'非零,则手是一对或两对.要查看一只手是否包含两个或更多对,'和'手持值为02222222222222,并保存该值.减去1,并使用保存的值'和'结果.如果非零,
作为分离注释,为检查直线而进行的计算还可以让您快速确定手中有多少不同等级的牌.如果有N张牌和N个不同等级,则手牌不能包含任何对或更好(当然可能包含直线或同花).如果有N-1个不同的等级,那么手只包含一对.只有少数不同的等级必须使用更复杂的逻辑(如果有N-2,手可以是两对或三种;如果N-3或更少,手可以是"三对"(分数为两对),满堂红或四种类型".
还有一件事:如果您无法管理8192元素的查找表,则可以使用512元素的查找表.如上所述计算位掩码,然后在数组[bitmask&511]和array [bitmask >> 4]上进行查找,并对结果进行OR运算.任何合法的直接或抽签将在一个或其他查找上注册.请注意,这不会直接为您提供不同排名的数量(因为在两次查找中都会计算6到10的卡),但是对同一个阵列的一次查找(使用数组[bitmask >> 9])将只计算插孔数通过ace.