3

我正在模拟扑克，现在我必须有效地对手牌进行排名：

每手牌是 5 张牌的组合，表示为uint64_t。
从 0（黑桃 A）、1（红心 A）到 51（梅花二）的每一位表示相应的牌是手牌的一部分（位 == 1）还是不是手牌的一部分（位 == 0） . 从 52 到 63 的位总是设置为零并且不保存任何信息。

我已经知道我理论上如何生成一个表格，这样每一个有效的手都可以映射到uint16_t1（2,3,4,5,7 - 不同颜色）和 7462（皇家同花顺）之间的范围（表示为 ）和所有其他人到零距离。

因此，一个简单的查找表（以卡片的 整数值作为索引）将具有2 bytes * 2^52 >= 9.007 PB.
大部分内存将被零填充，因为uint64_t从 0 到 2^52-1 的几乎所有 ' 都是无效的手，因此范围等于零。
有价值的数据只占 2 bytes * 52!/(47!*5!) = 5.198 MB.

我可以使用什么方法进行映射，这样我只需要从有效卡中保存排名和一些开销（最大 100 MB），并且仍然不必进行一些昂贵的搜索......它应该和可能的！

如果您有其他想法，欢迎您！;)

4

5 回答 5

3

您只需要一张 13^5*2 的表格，额外的信息级别表明所有卡片是否都花色相同。如果由于某种原因“心”的排名超过“钻石”，您最多仍需要一个大小为 13^6 的表格，因为最后一条信息编码为“0 = 无模式，1 = 所有黑桃，2 = 所有红心， ETC。'。

哈希表可能也是一种很好且快速的方法——从 nCk(52,5) 组合创建表并不需要太多时间（与所有可能的牌相比）。但是，需要为每个条目存储 65 位信息以存储密钥（52 位）和秩（13 位）。

加快手的评估，首先从掩码中排除非法组合
if (popcount(mask) != 5)：之后一次可以使用来自例如 crc32(mask) 的足够位，它至少在 i7 架构中具有指令级支持。

于 2013-11-10T11:39:39.157 回答
1

如果我正确理解您的方案，您只需要知道特定手的汉明权重恰好为 5 即可成为有效手。有关如何计算汉明权重的信息，请参阅计算 O(1)中的汉明权重。

从那里开始，您似乎可以自己解决其余的问题。就个人而言，我想将结果存储在一些持久内存中（如果它在您选择的平台上可用），以便后续运行更快，因为它们不需要生成索引表。

于 2013-11-10T11:38:46.877 回答
1

这是一个很好的来源
Cactus Kev's

对于一手牌，您最多可以利用任何花色中的
4 个 等级 (0-12) 4 位，花色 2 位
6 位 * 5 张牌只有 30 位
称之为 4 字节
只有 2598960 手
总大小略低于 10 mb

于 2017-04-09T01:59:49.400 回答
0

我会以不同的方式表示你的手：只有 4 个花色 = 2 位，只有 13 张牌 = 4 位，总共 6 位 * 5 = 30 - 所以我们适合 32 位整数 - 我们也可以强制它始终根据您的订单排序

[花色 0][花色 1][花色 2][花色 3][花色 4][价值 0][价值 1][价值 2][价值 3][价值 4]

然后我会使用一个单独的哈希：

  • 连续值（非常小）[屏蔽掉西装]
  • 1 或更多倍数（对，2 对，满堂）[掩饰西装]
  • 相同的西装（非常小）[掩盖价值]

然后使用 3 个哈希来计算您的排名 在 5MB 时，您可能会遇到足够的缓存问题，这将使一些数学运算和三个小查找更快

于 2013-11-13T02:26:29.490 回答
0

想到的一个简单实现是将您的方案更改为以 52 为基数的 5 位数字。保存所有这些值的结果表仍将大于必要的值，但实现起来非常简单，并且很容易适应现代计算机上的 RAM。

编辑：您还可以通过仅存储每张牌的等级和一个附加标志（例如，最低位）来指定是否所有牌都具有相同的花色（即，同花是可能的）来减少更多。然后，这将以 13 为基数 + 一位用于排名表示。然后，您可能需要单独存储卡片的特定花色，以重建确切的手牌以进行展示等。

于 2013-11-10T11:46:06.950 回答