9

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

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

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

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

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

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

1 1 0 1 1 1 1 1

并且圆形位置掩码是

0 0 0 0 0 1 0 0

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

4

1 回答 1

12

您是对的，仅使用按位运算无法确定滑动件的有效移动。您将需要按位运算和预先计算的查找表。

国际象棋案

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

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

  1. 隔离给定棋子可能从给定位置到达的方格，而不考虑棋盘的占用情况。这为我们提供了潜在目标方块的 64 位位掩码。我们称它为T（代表目标）。

  2. 将T与板上已占用方块的位掩码执行按位与运算。我们称后者为O（表示被占用）。

  3. 将结果乘以一个魔法值M并将结果向右移动一个魔法值S。这给了我们I（用于索引）。

  4. 使用I作为查找表中的索引来检索可以使用此配置实际达到的正方形的位掩码。

把它们加起来：

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

T，M，S和查找都是预先计算的，并且取决于片段的位置（P = 0 ... 63）。因此，更准确的公式是：

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

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

该算法的“神奇”部分是确定M和S值，以生成尽可能小的无冲突查找表。正如 Bo Persson 在评论中所注意到的，这是一个完美的哈希函数问题。然而，到目前为止，还没有为魔术位板找到完美的散列，这意味着使用中的查找表通常包含许多未使用的“洞”。大多数时候，它们是通过运行广泛的蛮力搜索来构建的。

你的测试用例

现在回到你的例子：

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

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

因此，在不应用“魔术”部分的情况下，根据位置和当前棋盘构建直接查找表是完全可行的。

我们会有：

reachable_squares = lookup[P][board]

这将产生一个查找表，其中包含：

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>

于 2016-08-03T08:47:49.513 回答