用位棋盘识别国际象棋棋子

Question

用位棋盘识别国际象棋棋子

3

当棋盘以多种位板的形式存储时，现代国际象棋引擎是如何识别特定单元格中的棋子类型/方面的？我在这方面遇到了一些问题，因为我必须始终执行以下操作才能找出特定位上的棋子类型/方面：

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数组，它将固有地存储棋子类型。

考虑到在搜索函数中进行捕获分析需要执行数百万次，哪种方法更好？我做错了吗？

- Shreyas

把那个测试级联放到一个单独的函数中，而不是每次需要时重复代码怎么样？ - πάντα ῥεῖ

据我所知，这是关于操作时间而非外观的。 - Shreyas

2个回答

1

这是位棋盘上最慢的操作。但你很少需要执行它。

我看到你正在维护所有白子的按位“或”运算，white和所有黑子的按位“或”运算，black。使用它们，您可以快速拒绝移动到自己的棋子上，并轻松检测捕获。

在相当不太可能的情况下进行捕获时，您必须测试最多6个敌方棋子位棋盘中的5个，因为国王捕获应该已经被排除了。此外，这并不像您想象的那样繁琐；在64位系统上，每个掩码只需要1个位棋盘操作和比较，因此需要10个整数操作。And/Or是处理器上最轻的操作之一。仅维护Piece[64]就比这更费时间。

我认为（在引擎代码中）没有其他情况需要从给定的方格获取pieceID。

位棋盘的主要优势是移动生成和位置分析。没有任何东西可以与之相比，因此无论如何，您都将维护此结构。

- VoidStar

如果你看代码，white和black已经混合在一起了。我同意，对于现代ALU来说，位运算是轻而易举的。 - Shreyas

嗯，仔细想想，你说得很对，因为在移动生成过程中捕获是比较少见的。 - Shreyas

我不确定是否值得为“所有白色棋子”使用位棋盘，因为它可以轻松生成。 - MSalters

这是肯定的，我已经用不同的方法进行了测量。它被读取为早期退出和其他情况的一部分，并且在位置分析代码中也是如此。 - VoidStar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MSalters · Accepted Answer

比特检查本身很快，我更担心的是分支问题。相反，考虑将uint64_t bitboards[12]作为所有棋子的12个位棋盘数组。现在它在内存中是连续的并且可以在循环中扫描。

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

只有两个分支（循环和检查）对于分支预测器更容易，连续的内存优化了预取器。

明显的变体是仅检查白色棋子的位板[0]到[5]，并且仅检查黑色棋子的位板[6]到[11]。

一个更微妙的变体：

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

将空值返回-1的代码改为返回标记值12。但这会用更快的无条件跳转替换条件循环分支。同时，返回值总是int i。

另一个不相关的优化是认识到兵是最常见的棋子，因此更高效的方法是对于白色兵使用bitboards[0]，对于黑色兵使用bitboards[1]或bitboards[6]，具体取决于你是否交替使用黑色或白色棋子。

[编辑] 如果您有一个单独的color位板，则不需要为白兵和黑兵分别使用两个位板。相反，只需使用一个兵位板即可。要检查黑兵，请使用AND操作符检查两个值 (bit_check & color & bitboard[0])。要检查白兵，反转颜色 (bit_check & ~color & bitboard[0])。