问题标签 [bitboard]

我知道 Magic BitBoard 技术对于 8x8 网格上的现代游戏很有用，因为它与单个 64 位整数完美对齐，但是这个想法是否可以扩展到大于 64 方格的棋盘尺寸？

一些像 Shogi 这样的游戏有更大的棋盘大小，例如 81 个方格，这不完全适合 64 位整数。

我假设您必须使用多个整数，但使用 2 个 64 位整数或 3 个 32 位整数会更好吗？

我知道这可能没有一个简单的答案，但是我需要什么样的知识来研究这样的事情？我只有一些基本/中级算法和数据结构知识。

考虑以下居中的六边形位板表示（填充以粗体显示）：

此表示适合 64 位整数，并允许通过分别向右或向左旋转位 1、7 或 8 个空格，在 6 个六边形方向上轻松移动。如果它有助于可视化，您可以将此六边形变形为正方形：

现在，我想做的是顺时针旋转这个位板 60°，这样 [45,46,47,38,39,31] 三角形变成 [48,41,34,40,33,32] 三角形等。 我该怎么做呢？

在许多棋盘游戏（如跳棋、围棋和黑白棋）中，每个方格可以由三种状态表示：白色、黑色或空。

这种游戏引擎中的 8x8 棋盘通常表示为两个位棋盘：一个 64 位整数用于定位白色棋子，另一个 64 位整数用于黑色棋子。

但是，在存储本地游戏模式时，这种二进制表示可能需要大量空间。例如，为 8 平方行的所有可能值创建一个查找表将需要一个具有 256*256 = 4^8 = 65536 个值的数组，而只有 3^8 = 6561 个可能的位置（因为一个正方形永远不可能被黑白棋子占据）。

另一种方法是将板存储为三进制数 - 所谓的titboards。但是我在任何地方都没有找到在两个二进制整数表示和三元整数表示之间进行转换的快速算法。

因此，我的问题是

是否有一种有效的方法可以将两个互斥的二进制数w & b == 0（（最好在 C/C++ 中。）

Python 示例

这是我的 Python 解决方案：

示例值：

• w = 1010001 ₂ = 81
• b = 0100100 ₂ = 36
• 结果 = 1010001 ₃ + 0100100 ₃ *2 = 1010001 ₃ + 0200200 ₃ = 1210201 ₃ = 1315

所以white_black_empty(81, 36) == 1315。

但是，将整数转换为二进制的字符串表示形式format(x, 'b')，然后使用基数 3 从字符串转换回整数int(x, base=3)看起来相当低效。

我想使用位板编写一个国际象棋引擎。因为我对位板不是很熟悉，所以我想先弄清楚如何使用它们。我写了一个应该打印位板的小函数。那是我偶然发现一个问题的地方。我的函数似乎可以正确打印出排名，但似乎无法正确打印出文件。

结果：

我正在编写国际象棋ai。在尝试计算主教所有可能的对角线移动时，我遇到了一个问题。我认为问题出在函数中：reverse_bits()。我不认为我在我的程序中正确处理负二进制数，但我可能是错的。

例如在这种情况下，它会正确计算所有可能的主教移动：

但是，例如，当我将主教移动到另一个方格时，会发生这种情况：

当我检查函数中的代码时：对角线对角线移动（），它找到所有对角线/对角线移动，我开始打印不同的位板。我注意到一些位板上有“-”号。例如我拿了：reverse_bits(occupied & antidiagonal[antidiagonalnum]) - 2 * reverse_bits(slider) from

并打印出位板。结果是这样的：

这就是为什么我认为在 reverse_bits 函数中反转负整数时一定有问题。

有趣的是，用于查找所有可能的车移动的函数 vertical_horizo​​ntal_moves() 似乎工作得很好。

我希望有人能给我一个想法，我的代码到底出了什么问题。

我正在编写国际象棋ai。当我想将位从 king_span 移到左侧时遇到了问题。当我将位移动到 45 个位置时，它工作正常。如果我想将它们移动超过 45 个位置，则输出的位板是相同的，就好像它只移动了 45 个位置一样。为什么它没有进一步移动它们，我怎么可能解决这个问题？我必须为此做第二个 king_span 吗？

感谢您尝试帮助我。

输出：

--> 位不会进一步移动。下一个位板应如下所示：

我需要计算 numpy uint64 变量中尾随和前导零的数量，所以现在我这样做：

有没有更好的方法来做到这一点，而不使用字符串？优先级是速度。谢谢！

我正在编写一个强化学习检查引擎，但我遇到了性能障碍。网络能够在我的机器上快速学习，但是我的游戏/mcts 实现非常慢，以至于网络需要几个小时才能与自己玩几百场比赛。这使得学习过程非常缓慢，所以我决定使用位板重写游戏。这是我在重写之前的第一个实现：

本质上，游戏被表示为一个 4x8 numpy 数组，其条目范围为 -2、-1、0、1、2。这些值表示不同的棋子类型和一个空方块。辅助函数 jump_generator 和 move_generator 采用给定的正方形 (i, j) 并返回从那里可能的步骤/捕获列表。jump_function 递归生成强制捕获序列。游戏状态对象使用棋盘数组进行初始化，然后使用辅助函数生成合法动作。基本上就是这样。它还有一种从自己的法律行为中生成新状态的方法。

下面是我使用位板的新实现。之前的二维数组现在是四个 32 位整数。每个整数代表一个棋子类型，整数的二进制表示该棋子类型在棋盘上的存在。该板以一种巧妙的方式编码，因此只需将每个“移动向量”的位旋转固定数字即可访问角落相邻的方块。有用于这些位操作的函数，以及对导致每个移动“向量”越界的正方形进行编码的常量整数掩码。有一个函数需要四个平面（整数）并返回 8 个移动平面。这一切都是使用 np.uint32 上的位逻辑完成的。我什至使用了一些记忆。最后，这些平面通过位移“迭代”以找到合法移动并生成结果位置。

我通过让它们连续一千次“推出”到终端状态来测试两者。第一个实现的速度提高了 3-4 倍。对于任意多的游戏来说，这似乎都是正确的。

我想实现一个类似于国际象棋的 9x9 棋盘游戏，它只有类似车的移动棋子。性能至关重要，因为我也想开发人工智能。

我阅读了有关位板的文章，这是一种表示游戏引擎的有效方式。有几篇关于这方面的有趣文章，例如Java 中的 Chess bitboard implementation和https://www.chessprogramming.org/Bitboards。当然，它们指的是 8x8 板，它们非常适用于 64 位 CPU，因为它允许快速按位运算。

在这种情况下，我需要一个 9x9 板，因此我希望使用至少两个原始数据（64 位 + 32 位，以表示我需要的 81 个方格）。

除了我需要的更复杂的逻辑之外，在这种情况下是否值得使用位板？我真的会在性能上获得很好的收益吗？

我正在努力寻找一种计算正方形对角线的 64 位表示的有效方法。

有问题的游戏是一款名为 Othello 或 Reversi 的棋盘游戏。我目前正在研究一种确定作品稳定性的方法。稳定的棋子可以定义为不能翻转的棋子。我正在处理的当前问题可以定义为：“如果所有四个方向的所有方格都被占用，则无法翻转一块。”

因此，例如，如果棋盘如下所示，则无法捕获标有 A 的棋子：

其中 x 表示该位置存在一块（无论其颜色如何）。由于该棋子被各个方向的棋子包围，因此无法捕获。

垂直线很容易计算。在一个 8x8 的嵌套 for 循环中，可以通过 ver0 >> j 找到下一条垂直线，而通过 hor0 >> i*8 可以找到下一条水平线。

作为一个视觉示例，hor0 看起来像：

因此移位 8 会将线下移 1。

ver0 看起来像：

因此，移位一位会将线向右移动一位。

要找到他们的组合光标，我只需 OR 结果：

现在真正的问题开始了。为了确定稳定性，我需要所有四个方向。我不确定如何仅使用 (i, j) 位置可行地计算对角线。

我的第一次尝试是使用位移。这非常失败，因为当我不想要垃圾位时，移位会导致镜像。

我的第二次尝试是简单地将所有对角线放在一个数组中，并使用索引来查找相应的线。该数组非常大，但这里是一些元素外观的示例（仅左对角线）：

我不知道如何将数组的索引与 (i, j) 索引匹配。例如，如果一个正方形在索引 (2, 1) 上，则对应的索引应该是数组中的 [1]。但是如果正方形在 (3, 2) 上，则数组的索引也应该是 [1]。如果正方形在 (1,1), ... (7, 7), (8, 8) 上，则索引应为 [0]。

我无法确定一种轻松找到线路的方法。我想到的一件事是获取当前正方形的 64 位表示形式，然后将其与两条线的交点进行或运算。问题是这将需要一个 for 循环，并且此操作将执行数千次，这在计算上不是最优的。

有人知道从单个正方形计算对角线的方法或计算对角线数组中相应索引的方法吗？

非常感谢您的帮助。