9x9位板实现

Question

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

我读过一些关于比特板的文章，这是一种高效的游戏引擎表示方法。这方面有几篇有趣的文章，比如用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的四个合法动作，这不需要分支，因为您可以一个一个地提取位(例如，使用克尼汉法)。要获得合法抓捕的名单，你需要和第二个面具与对手的碎片在那个级别。

我希望这是很好的工作，即使是9x9板。额外的位处理功能仍然应该比替代(ifs和分支)快得多。正如评论中提到的，最好的方法是测试几种方法！