9x9 位板实现

Question

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

我阅读了有关位板的文章，这是一种表示游戏引擎的有效方式。有几篇关于此的有趣文章，例如 Chess bitboard implementation in Java and 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

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

Answer 1

关于 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's method）。要获得合法捕获列表，您需要将第二个掩码与该等级的对手棋子进行 AND 运算。

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

9x9 位板实现

9x9 bitboard implementation

java

chess

bitboard