1

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

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

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

// 9x9 board, possible representation (64bits+32bits)
  000000000
  000000000
  000000000
  000000000
  000000000
  000000000
  000000000
  000000000
  000000000
  +15 unused bits

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

4

1 回答 1

0

关于 bitboards 和 rooks 最好的事情之一是，您可以预先计算给定等级或文件占用的合法移动。这很棒，因为您可以在没有任何if指示的情况下找到所有合法的动作。例如，假设您通过移位和屏蔽来隔离当前排名，您得到

10100R001

其中 1 是一个被占用的方格，0 是一个空方格，你的车从第 3 个方格开始（从最低有效位开始计算，即第 0 位）。假设您预先计算：

ROOK_MOVE[3][101000001] = 000110110
ROOK_CAPTURE[3][101000001] = 001000001

（幼稚的方法在这里已经足够好了，因为剩下的 8 个方格只有 9 个起始位置和 256 个占用。）然后您可以生成四个合法移动到方格 1、2、4 和 5。这不需要分支，因为您可以逐个提取位（例如使用Kernighan 的方法）。要获得合法捕获的列表，您需要将第二个掩码与该级别的对手棋子相加。

我希望这即使对于 9x9 板也能很好地工作。额外的位处理功能应该仍然比替代方案（ifs 和分支）快很多。如评论中所述，找出答案的最佳方法是测试几种方法！

于 2019-04-22T15:28:55.747 回答