我正在研究扑克模拟,现在我必须有效地对手牌进行排名:
每手牌都是 5 张牌的组合,表示为 uint64_t
。
从 0(黑桃 A)、1(红桃 A)到 51(梅花二)的每一位表示相应的牌是手牌的一部分(位 == 1)还是不是手牌的一部分(位 == 0) .从 52 到 63 的位总是设置为零并且不保存任何信息。
我已经知道理论上如何生成一个表,以便每只有效手牌都可以映射到 1(2,3,4,5,7 - 不是在相同的颜色)和 7462(皇家同花顺)和所有其他人都为零。
因此,一个简单的查找表(以卡片的整数值作为索引)的巨大大小为
2 字节 * 2^52 >= 9.007 PB
。
此内存的大部分将被零填充,因为几乎所有从 0 到 2^52-1 的 uint64_t
都是无效手,因此其范围为零。
有值(value)的数据只占
2 字节 * 52!/(47!*5!) = 5.198 MB
。
我可以使用什么方法进行映射,这样我只需要保存有效卡片的排名和一些开销(最多 100 MB),而且仍然不必进行一些昂贵的搜索... 它应该尽可能快!
如果您有任何其他想法,欢迎您! ;)
最佳答案
您只需要一张 13^5*2 的表格,如果所有牌都属于同一花色,则需要额外的信息级别。如果出于某种原因“红心”的排名高于“钻石”,您最多仍需要一张大小为 13^6 的表格,因为最后一条信息编码为“0 = 无模式,1 = 所有黑桃,2 = 所有红心,等等'。
散列表可能也是一种很好且快速的方法——从 nCk(52,5) 组合创建一个表并不需要太多时间(与所有可能的手相比)。但是,需要为每个条目存储 65 位信息,以存储 key (52 位)和等级(13 位)。
加快手牌评估,首先从掩码中排除非法组合:
if (popcount(mask) != 5)
;之后一旦可以使用足够的位来自例如crc32(mask),至少在i7架构中有指令级支持。
关于c - 快速扑克手排名,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19889147/