不了解 bitboard 技术如何适用于国际象棋棋盘

Question

我的大脑在冒烟，试图理解这种位板技术的机制。为了简单起见，让我们想象一下，我们没有国际象棋和许多复杂的棋子动作，而是有一个只有两个棋子和一个一排 8 个位置的游戏。一块是三角形，一块是圆形，像这样：

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │ ▲ │   │   │ ● │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

三角形可以像车一样移动。水平任意位置，但不能越过圆圈

现在假设用户将三角形移动到最后一个位置，如下所示：

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │ ● │   │ ▲ │
└───┴───┴───┴───┴───┴───┴───┴───┘

对于这个例子，三角形移动位板是

1 1 0 1 1 1 1 1

圆形位置掩码是

0 0 0 0 0 1 0 0

显然走法是非法的，因为三角形不能跳过圆，但是软件如何使用魔术位板技术检查走法是否合法？

Answer 1

您说得对，仅使用位运算无法确定滑动块的有效移动。您将需要按位运算和预计算查找 tables.

国际象棋案

最新的国际象棋引擎正在使用称为 Magic Bitboards 的技术。

实现方式各不相同，但基本原则始终相同：

隔离给定棋子从给定位置可能到达的方格，而不考虑棋盘占用。这为我们提供了潜在目标方块的 64 位位掩码。我们称它为 T（对于 Target）。
对T与棋盘上被占用方块的位掩码进行位与运算。让我们称后者为 O（对于已占用）。
将结果乘以 magic 值 M 并将结果右移魔法数量S。这给了我们 I（对于索引）。
使用 I 作为查找中的索引 table 以检索使用此配置实际可以到达的方块的位掩码。

总结一下：

I = ((T & O) * M) >> S
reachable_squares = lookup[I]

T、M、S 和 lookup 都是预先计算的，取决于棋子的位置 (P = 0 ... 63)。因此，更准确的公式是：

I = ((T[P] & O) * M[P]) >> S[P]
reachable_squares = lookup[P][I]

步骤#3 的目的是将 64 位值 T & O 转换为更小的值，以便可以使用合理大小的 table。我们通过计算 ((T & O) * M) >> S 得到的本质上是一个随机位序列，我们希望将这些序列中的每一个映射到一个可达目标方块的唯一位掩码。

此算法中的 'magic' 部分是确定 M 和 S 值，它们将产生 无冲突查找table尽可能小。正如 Bo Persson 在评论中指出的那样，这是一个 Perfect Hash Function 问题。然而，到目前为止，还没有找到适用于魔术位板的完美散列，这意味着正在使用的查找 table 通常包含许多未使用的 'holes'。大多数时候，它们是通过运行广泛的暴力搜索构建的。

你的测试用例

现在回到你的例子：

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │ ▲ │   │   │ ● │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘ 
  7   6   5   4   3   2   1   0

这里，块的位置在 [0 ... 7] 中，占用位掩码在 [0x00 ... 0xFF] 中（因为它是 8 位宽）。

因此，不应用'magic'部分，直接根据位置和当前棋盘构建table查找是完全可行的。

我们有：

reachable_squares = lookup[P][board]

这将导致查找 table 包含：

8 * 2^8 = 2048 entries

显然我们不能为国际象棋这样做，因为它会包含：

64 * 2^64 = 1,180,591,620,717,411,303,424 entries

因此需要神奇的乘法和移位运算以更紧凑的方式存储数据。

下面是一个 JS 片段来说明该方法。点击棋盘切换敌人棋子。

var xPos = 5,          // position of the 'X' piece
    board = 1 << xPos, // initial board
    lookup = [];       // lookup table

function buildLookup() {
  var i, pos, msk;

  // iterate on all possible positions
  for(pos = 0; pos < 8; pos++) {
    // iterate on all possible occupancy masks
    for(lookup[pos] = [], msk = 0; msk < 0x100; msk++) {
      lookup[pos][msk] = 0;

      // compute valid moves to the left
      for(i = pos + 1; i < 8 && !(msk & (1 << i)); i++) {
        lookup[pos][msk] |= 1 << i;
      }
      // compute valid moves to the right
      for(i = pos - 1; i >= 0 && !(msk & (1 << i)); i--) {
        lookup[pos][msk] |= 1 << i;
      }
    }
  }
}

function update() {
  // get valid target squares from the lookup table
  var target = lookup[xPos][board];

  // redraw board
  for(var n = 0; n < 8; n++) {
    if(n != xPos) {
      $('td').eq(7 - n)
        .html(board & (1 << n) ? 'O' : '')
        .toggleClass('reachable', !!(target & (1 << n)));
    }
  }
}

$('td').eq(7 - xPos).html('X');

$('td').click(function() {
  var n = 7 - $('td').index($(this));
  n != xPos && (board ^= 1 << n);
  update();
});

buildLookup();
update();

td { width:16px;border:1px solid #777;text-align:center;cursor:pointer }
.reachable { background-color:#8f8 }

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table>
  <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
</table>

不了解 bitboard 技术如何适用于国际象棋棋盘

Not understanding how the bitboard technique works for chess boards

algorithm

chess

2d-games

bitboard

国际象棋案

你的测试用例