java - 9x9 位板实现

Question

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

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

在本例中，我需要一 block 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 指令即可找到所有合法的 Action 。例如，假设您通过移位和屏蔽来隔离当前排名，您将得到

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 板也能很好地工作。额外的位处理函数应该仍然比替代函数(if 和分支)快得多。正如评论中提到的，找出答案的最佳方法是测试几种方法!