不理解位棋盘技术在国际象棋棋盘上的运作方式

Question

不理解位棋盘技术在国际象棋棋盘上的运作方式

9

我尝试理解这个位棋盘技术的机制，但感觉头脑冒烟。为了简化问题，我们可以想象一个只有两种棋子和一行8个位置的游戏，而不是象棋和复杂的棋子移动。其中一种棋子是三角形，另一种是圆形，如下图所示：

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

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

现在想象一下，用户将三角形移动到最后一个位置，就像这样：

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

对于这个例子，三角形移动位棋盘是：

1 1 0 1 1 1 1 1

圆形位置掩码为：

0 0 0 0 0 1 0 0

显然，这种移动是非法的，因为三角形不能跳过圆形，但是如何使用魔术比特板技术来检查移动是否合法呢？

- Duck

1

你看过这个吗？https://chessprogramming.wikispaces.com/Subtracting+a+Rook+from+a+Blocking+Piece - Peter de Rivaz

5

是的，这听起来对我来说像克林贡语。 - Duck

页面链接由@PeterdeRivaz提供的方法只能单向工作，这就是为什么它在您的示例中无法工作（在他们的示例中，车在右侧）。同一网站上的此页面列出了几种位操作方法，其中一些可以双向工作：https://chessprogramming.wikispaces.com/Sliding+Piece+Attacks - m69 ''snarky and unwelcoming''

此外，请查看本页面右侧的“相关问题”栏。 - m69 ''snarky and unwelcoming''

1个回答

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

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

- Arnauld · Accepted Answer

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

国际象棋案例

大多数最新的国际象棋引擎都使用称为Magic Bitboards的技术。

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

从给定的位置中找到一个棋子可能到达的方块，不考虑棋盘上的占用情况。这将为我们提供一个潜在目标方块的64位掩码。我们称其为“T”（目标）。
对“T”执行按位与操作，与棋盘上占用方块的掩码进行比较。我们称后者为“O”（占用）。
将结果乘以一个“魔术”值“M”，并将结果向右移动一个“魔术”数量“S”。这将给我们带来一个“I”（索引）。
使用“I”作为查找表中的索引，检索可以实际到达此配置的方块的掩码。

总之：

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]

第三步的目的是将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>