algorithm - 生成一组满足以下 xor-property 的伪随机数？

Question

给定一个伪随机数生成器 int64 rand64()，我想构建一组伪随机数。该集合应具有每个子集的 XOR 组合不应导致值 0 的属性。

我正在考虑以下算法:

count = 0
set = {}
while (count < desiredSetSize)
    set[count] = rand64()
    if propertyIsNotFullfilled(set[0] to set[count])
        continue
    count = count + 1

问题是:如何实现propertyIsNotFullfilled？

注意:我喜欢生成这样一个集合的原因如下:我有一个哈希表，其中的哈希值是通过 Zobrist hashing 生成的.我没有为每个哈希表条目保留一个 bool 值来指示条目是否已填充，而是认为哈希值——与每个条目一起存储——足以提供此信息(0 ...空，!= 0 ...设置).将此信息作为标记值携带在哈希键表中还有另一个原因。我正在尝试从 AoS(结构数组)切换到 SoA(数组结构)内存布局。我正在尝试这样做以避免填充并测试是否有较少的缓存未命中。我希望在大多数情况下访问散列键表就足够了(这意味着散列值提供了条目是否为空的信息)。
我还考虑过为该信息保留散列值的最高有效位，但这会比必要的更多地减少可能散列值的区域。理论上，面积将从 2⁶⁴(减去重要的 0 值)减少到 2⁶³。
可以换一种方式解读这个问题:给定一组 84 个伪随机数，是否有任何数字不能通过对这个集合的任何子集进行异或生成，以及如何得到它？这个数字可以作为标记值。
现在，我需要它:我开发了一个连接四游戏引擎。玩家 A 和玩家 B 有 6 x 7 种可能的移动。因此有 84 种可能的移动(因此需要 84 个随机值)。棋盘状态的哈希值由预先计算的随机值按以下方式生成:hash(board) = randomset[move1] XOR randomset[move2] XOR randomset[move3] ...

Answer 1

This set should have the property that the XOR combinations of each subset should not result in the value 0.

恕我直言，这会将子集的最大数量限制为 64(鸽巢原则)；对于 >64 个子集，总会有一个(非空)子集异或为零。对于较小的子集，可以满足该属性。

为了进一步说明我的观点:考虑一个包含 64 个方程和 64 个未知变量的系统。然后，添加一个额外的方程式。方程式和变量是 bool 值这一事实并没有使问题有所不同。

--编辑/更新--:由于该应用程序似乎是“连连四”游戏，因此您可以枚举所有可能 配置。无法对不可能的电路板配置进行编码将节省足够的编码空间以适应 64 位中任何有效的电路板位置:

将有色 gem 编码为 {A,B}，将不相关的编码为 {X} (hight=6) 列的配置可以是以下之一:

                   X
                X  X
             X  X  X
          X  X  X  X
       X  X  X  X  X
_   A  A  A  A  A  A   <<-- possible configurations for one pile
--+--+--+--+--+--+--+ 
1   1  2  4  8 16 32   <<-- number of combinations of the Xs
               -2 -5   <<-- number of impossible Xs

(和 B 而不是 A 类似)。堆下方的数字是顶部 X 的可能性数量，负数是禁止/不可能配置的数量。对于有 1 个 A 和 4 个 X 的列，X 的每个值都是有效的，*除了 3*A(游戏已经结束)。最右边的堆也一样:最下面的3个X不可能都是A，X也不可能所有的X都是B。

这导致总数为 1 + 2 * (63-7) := 113。 (1为空板，2为颜色数)。所以:113 是一列的配置数，正好符合 7 位。对于 7 列，我们需要 7*7:=49 位。 (我们可能会为 L/R 镜像对称性节省一位，甚至可能为颜色对称性节省一位，但这只会使事情复杂化，恕我直言)。

仍然有很多编码空间被浪费(列不是独立的，棋盘上A的数量等于B的数量，或者多一个，等等)，但是我不要认为避免它们会很容易。幸运的是，这不是必需的。