不了解比特板技术在棋盘上的工作原理

Question

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

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

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

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

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

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

1 1 0 1 1 1 1 1

圆圈位置遮罩是

0 0 0 0 0 1 0 0

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

Answer 1

你是对的，不可能只使用按位操作来确定滑动块的有效移动。您需要按位操作和预先计算的查找表。

最新的国际象棋引擎正在使用一种被称为“魔法比特板”的技术。

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

>

执行T的按位与，并在板上使用占用方格的位掩码。让我们称后者为O（表示占用）。

将结果乘以一个神奇的值M，并将结果向右移动一个神奇的量S。这给我们I（代表索引）。

在查找表中使用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

该算法的“魔法”部分是确定M和S值，这将产生一个尽可能小的无冲突查找表。正如Bo Persson在评论中指出的，这是一个完美的哈希函数问题。然而，到目前为止，还没有为magic Bitboard找到完美的哈希，这意味着使用中的查找表通常包含许多未使用的“孔”。大多数情况下，它们都是通过大规模的暴力搜索建立起来的。

现在回到你的例子：

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │ ▲ │   │   │ ● │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘ 
  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>