9x9位板实现

Question

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

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

关于位板和车的最好的事情之一就是你可以根据等级或文件的占用情况预先计算合法的移动。这很好，因为你可以找到所有合法的动作，没有任何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）。要获得合法捕获列表，您需要将第二个掩码与该等级上的对手部分进行对比。

我希望即使对于9x9主板也能正常工作。额外的位处理功能应该比替代（ifs和分支）快得多。正如评论中所提到的，最好的方法是测试几种方法！