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

Question

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

?????????????????????????????????
?   ?   ? ? ?   ?   ? ? ?   ?   ?
????????????????????????????????? 

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

现在假设用户将三角形移动到最后位置,如下所示:

?????????????????????????????????
?   ?   ?   ?   ?   ? ? ?   ? ? ?
?????????????????????????????????

对于此示例,三角形移动位板是

1 1 0 1 1 1 1 1

圆圈位置掩码是

0 0 0 0 0 1 0 0

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

Answer 1

你是对的,通过仅使用按位运算来确定滑动件的有效移动是正确的.您需要按位运算和预先计算的查找表.

国际象棋案

最近的国际象棋引擎使用的技术称为Magic Bitboards.

实现方式各不相同,但基本原则始终相同:

1. 隔离给定件可能从给定位置到达的正方形,而不考虑板的占用率.这为我们提供了一个潜在目标方块的64位位掩码.我们称之为T(针对目标).

2. 使用板上占用方块的位掩码执行T的按位AND .我们称之为O(对于被占领者).

3. 通过相乘结果魔术值中号和由该结果向右移位魔量小号.这给了我(索引).

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>