国际象棋编程：如何最有效地从位板攻击掩码中走出一步

Question

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

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

为了女王。

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

Answer 1

我觉得你说的已经是最高效的方法了。在位板上循环直到它为零并一次选择一个动作。

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

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已经是找到最低有效位的实现了。所以，你可以用它来获得便携版。

国际象棋编程：如何最有效地从位板攻击掩码中走出一步

Chessprogramming: how to get a single move out of a bitboard attack-mask most efficently

chess

bitboard