国际象棋编程 : how to get a single move out of a bitboard attack-mask most efficently

Question

我怎样才能有效地从攻击面具中走出来，看起来像这样:

....1...
1...1...
.1..1..1
..1.1.1.
...111..
11111111
..1.11..
.1..1.1.

为女王。

我过去所做的是通过计算尾随零 (bitScanForward) 从皇后获得每一步可能移动的平方索引在我生成新的移动之后，我从攻击掩码中删除了这个方 block 并继续下一个攻击方 block 。有没有什么技术可以直接获取单个攻击位？

Answer 1

我认为你所描述的已经是最有效的方式了。在位板上循环直到它为零并一次选择一个 Action 。

用一些代码勾勒出这个想法，它可能看起来像这样:

using Bitboard = uint64_t; // 64 bit unsigned integer

pMoves createAllMoves(Bitboard mask, int from_sq, Move* pMoves) {
  while(moves != 0) {
    int to_sq = findAndClearSetBit(mask);
   *pMoves++ = createMove(from_sq, to_sq);
  }
  return pMoves;
}

findAndClearSetBit 函数可以选择任何设置位，但通常在当今的硬件上，找到最低有效位是最有效的。如果您使用的是 GCC 或 Clang，则可以使用应针对特定硬件进行优化的 __builtin_ctzll:

int findAndClearSetBit(Bitboard& mask) {
   int sq = __builtin_ctzll(mask); // find least significant bit
   mask &= mask - 1; // clear least significant bit
   return sq;
}

如果我没记错的话，您现有的函数 bitScanForward 已经是找到最低有效位的实现。因此，您可以使用它来获得便携版本。