c++ - 用位板识别棋子

Question

当棋盘存储在各种位板上时，现代国际象棋引擎如何识别特定单元格上的类型/边棋子？我对此有疑问，因为要找出特定位是什么类型/侧面，我必须始终这样做:

if((bit_check & occupied) == 0ULL) ... // empty
else if((bit_check & white) != 0ULL) // white
    if((bit_check & white_pawns) != 0ULL) ... // white pawns
    else if((bit_check & white_rooks) != 0ULL) ... // white rooks
    ....
    else if((bit_check & white_kings) != 0ULL) ... // white kings
else if((bit_check & black) != 0ULL) // black
    if((bit_check & black_pawns) != 0ULL) ... // black pawns
    ....
    else if((bit_check) & black_kings) != 0ULL) ... // black kings

这是一个相当繁琐的过程，必须进行多次(例如，在移动生成期间查看正在捕获的内容)。我不确定我是否应该直接使用它，或者简单地创建一个类型为 Piece[64] 的 64 数组是否会更快，它将固有地存储 piece 类型。

哪个更好，考虑到它必须是数百万次，以便在搜索功能中进行捕获分析。我做错了吗？

Answer 1

位校验本身很快；我主要担心分支。

相反，将 uint64_t bitboards[12] 视为所有部分的 12 个位板的数组。这现在在内存中是连续的，可以循环扫描:

for (int i = 0; i != 12; ++i)
{
  if (bitboards[i] && bit_check) return i;
}
return -1; // empty.

只有两个分支(循环和检查)对于分支预测器来说更容易，并且连续的内存优化了预取器。

明显的变化是检查位板 [0] 到 [5] 只检查白色 block ，[6] 到 [11] 只检查黑色 block 。

一个更微妙的变体:

uint64_t bitboards[13];
bitboards[12] = ~uint64_t(0);
for (int i = 0; /* NO TEST*/ ; ++i)
{
     if (bitboards[i] && bit_check) return i;
}

这将返回 12(哨兵值)，而不是为空返回 -1。但是，这用更快的无条件分支代替了条件循环分支。这也意味着返回值始终是 int i。

另一个不相关的优化是识别棋子是最常见的棋子，因此对白色棋子使用 bitboards[0] 和 bitboards[1] 会更有效或用于黑色棋子的 bitboards[6]，具体取决于您是交错黑色棋子还是白色棋子。

[编辑]如果您有一个用于color 的单独位板，那么您就不需要用于白色棋子和黑色棋子的两个位板。取而代之的是，为棋子设置一个位板。检查黑色棋子和两个值。 (bit_check & color & bitboard[0])。要检查白色棋子，请反转颜色 (bit_check & ~color & bitboard[0])