如何找到魔法位板？

Question

const int BitTable[64] = {
  63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
  51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
  26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
  58, 20, 37, 17, 36, 8
};

int pop_1st_bit(uint64 *bb) {
  uint64 b = *bb ^ (*bb - 1);
  unsigned int fold = (unsigned) ((b & 0xffffffff) ^ (b >> 32));
  *bb &= (*bb - 1);
  return BitTable[(fold * 0x783a9b23) >> 26];
}

uint64 index_to_uint64(int index, int bits, uint64 m) {
  int i, j;
  uint64 result = 0ULL;
  for(i = 0; i < bits; i++) {
    j = pop_1st_bit(&m);
    if(index & (1 << i)) result |= (1ULL << j);
  }
  return result;
}

来自 Chess Programming Wiki：
https://www.chessprogramming.org/Looking_for_Magics

它是一些用于查找 magic numbers 的代码的一部分。

参数 uint64 m 是一个 bitboard 代表车或主教移动可能被阻挡的方块。 e4 方格上的车示例：

0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 1 1 1 0 1 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0

边缘方块为零，因为它们总是阻塞，减少所需的位数显然有帮助。

/* Bitboard, LSB to MSB, a1 through h8:
 * 56 - - - - - - 63
 *  - - - - - - - -
 *  - - - - - - - -
 *  - - - - - - - -
 *  - - - - - - - -
 *  - - - - - - - -
 *  - - - - - - - -
 *  0 - - - - - - 7
 */

因此在上面的示例中，index_to_uint64 取一个索引（0 到 2^ 位），位板中设置的位数 (10)，以及位板。

然后对每个位数 pops_1st_bit，然后是另一个移位的代码位。 pops_1st_bit 将位板与自身减一进行异或运算（为什么？）。然后它用一个完整的 32 位对其进行 AND 运算，在这附近的某个地方，我的大脑耗尽了 RAM。不知何故涉及神奇的十六进制数 0x783a9b23（这是 Lost 中的数字序列吗？）。还有这个荒谬的神秘数组，由 0-63 (BitTable[64]) 随机排列的数字组成。

Answer 1

好的，我会尝试逐步解决这个问题。

index_to_uint64( 7, 10, m );

7只是0到2^10之间随机选择的一个数，10是m中设置的位数。 m可以用四种方式表示：

bitboard:
0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 1 1 1 0 1 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 
dec: 4521262379438080
hex: 0x1010106e101000
bin: 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0001 0000 0000 0000

继续前进。这将被调用 10 次。它有一个 return 值并修改 m.

pop_1st_bit(&m);

在pop_1st_bit中，m由bb引用。为了清楚起见，我将其更改为 m。

uint64 b = m^(m-1);

m-1 部分采用设置的最低有效位并翻转它和它下面的所有位。在 XOR 之后，所有这些更改的位现在都设置为 1，而所有高位都设置为 0。

m  : 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0001 0000 0000 0000 
m-1: 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0000 1111 1111 1111
b  : 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 1111 1111

下一个：

unsigned int fold = (unsigned) ((b & 0xffffffff) ^ (b >> 32));

(b & 0xffffffff) 部分与 b 与较低的 32 个设置位。所以这基本上清除了 b.

上半部分的所有位

(b & 0xffffffff)
b: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 1111 1111
&: 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111 1111 1111 1111 1111
=: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 1111 1111

... ^ (b >> 32)部分将b的上半部分移入下半部分，然后与前一个操作的结果异或。所以它基本上是将 b 的上半部分与 b 的下半部分进行异或运算。这在这种情况下没有影响，因为 b 的上半部分一开始是空的。

>> :0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 
^  :0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 1111 1111 

uint fold = 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 1111 1111

我不明白 "folding" 的意义，即使在 b 的上半部分设置了位。

无论如何，继续前进。下一行实际上通过取消设置最低位来修改 m。这有点道理。

m &= (m - 1);
m  : 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0001 0000 0000 0000 
m-1: 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0000 1111 1111 1111
&  : 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0000 0000 0000 0000

下一部分将 fold 乘以某个十六进制数（质数？），将乘积 26 右移，并将其用作 BitTable 的索引，这是我们随机排列的数字 0-63 的神秘数组。在这一点上，我怀疑作者可能正在编写一个伪随机数生成器。

return BitTable[(fold * 0x783a9b23) >> 26];

到此结束 pop_1st_bit。这一切都完成了 10 次（最初在 m 中设置的每个位一次）。对 pop_1st_bit return 的 10 次调用中的每一次都是一个数字 0-63。

j = pop_1st_bit(&m);
if(index & (1 << i)) result |= (1ULL << j);

上面两行中，i是我们当前所在的位，0-9。因此，如果 index 数字（最初作为参数传递给 index_to_uint64 的 7）设置了第 i 位，则设置结果中的第 j 位，其中 j 是 0-63 return 来自 pop_1st_bit.

的值

就是这样！我还是很困惑:(

Answer 2

好的，我知道了。

首先，一些术语：

blocker mask：对于给定的棋子类型和棋子所在的方格，包含所有可以阻挡棋子的方块的位板。它排除了终止边缘方块，因为它们总是阻塞。

blocker board：包含被占用方块的位板。它只有方块，这些方块也在屏蔽掩码中。

移动板：一个位板包含一个棋子可以移动到的所有方格，给定一个棋子类型，一个正方形和一个挡板。它包括终止边缘方块，如果棋子可以移动到那里。

e4 格上的车示例，e2、e5、e7、b4 和 c4 上有一些随机棋子。

 The blocker mask        A blocker board         The move board
 0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0 
 0 1 1 1 0 1 1 0         0 1 1 0 0 0 0 0         0 0 1 1 0 1 1 1 
 0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 1 0 0 0 
 0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0

一些注意事项：

对于给定的正方形和棋子类型（车或象），阻挡掩码始终相同。
阻挡板包括友方棋子和敌方棋子，它是阻挡面具的子集。
由此产生的棋盘可能包括吃掉你自己的棋子的棋步，但这些棋步之后很容易被删除：moveboard &= ~friendly_pieces)

幻数方法的目标是非常快速地查找给定[=45]的预先计算的移动板 =]拦截板。否则你每次都必须（慢慢地）计算移动板。这仅适用于滑动件，即车和主教。女王只是车和主教的组合。

每个方块和棋子类型的组合都可以找到神奇的数字。为此，您必须为每个 square/piece 组合计算每个可能的 blocker board 变化。这就是有问题的代码正在做的事情。 它是如何 对我来说仍然有点神秘，但是 that also seems to be the case for the apparent original author, Matt Taylor。（感谢@Pradhan link）

所以我所做的是重新实现代码以生成所有可能的拦截板变体。它使用不同的技术，虽然速度稍慢，但更容易阅读和理解。它稍微慢一点的事实不是问题，因为这段代码对速度并不关键。程序只需要在程序启动时做一次，在双核i5上只需要几微秒。

/* Generate a unique blocker board, given an index (0..2^bits) and the blocker mask 
 * for the piece/square. Each index will give a unique blocker board. */
static uint64_t gen_blockerboard (int index, uint64_t blockermask) 
{
    /* Start with a blockerboard identical to the mask. */
    uint64_t blockerboard = blockermask;

    /* Loop through the blockermask to find the indices of all set bits. */
    int8_t bitindex = 0;
    for (int8_t i=0; i<64; i++) {
        /* Check if the i'th bit is set in the mask (and thus a potential blocker). */
        if ( blockermask & (1ULL<<i) ) {
            /* Clear the i'th bit in the blockerboard if it's clear in the index at bitindex. */
            if ( !(index & (1<<bitindex)) ) {
                blockerboard &= ~(1ULL<<i); //Clear the bit.
            }
            /* Increment the bit index in the 0-4096 index, so each bit in index will correspond 
             * to each set bit in blockermask. */
            bitindex++;
        }
    }
    return blockerboard;
}

要使用它，请执行以下操作：

int bits = count_bits( RookBlockermask[square] );
/* Generate all (2^bits) blocker boards. */ 
for (int i=0; i < (1<<bits); i++) {
    RookBlockerboard[square][i] = gen_blockerboard( i, RookBlockermask[square] );
}

工作原理：有 2^bits 的屏蔽板，其中 bits 是屏蔽掩码中 1 的数量，它们是唯一相关的位。此外，从 0 到 2^bits 的每个整数都有一个长度为 bits 的唯一的 1 和 0 序列。所以这个函数只是将给定整数中的每一位对应到blocker mask中的相关位，并将其off/on相应地生成一个唯一的blocker board。

它不是那么聪明或快速，但它是可读的。

Answer 3

在 youtube 上观看有关国际象棋引擎的视频系列时，我遇到了与 paulwal222 完全相同的问题。似乎涉及一些高级数学。解释这个困难主题背景的最佳链接是 https://chessprogramming.wikispaces.com/Matt+Taylor and https://chessprogramming.wikispaces.com/BitScan . It seems that Matt Taylor in 2003 in a google.group ( https://groups.google.com/forum/#!topic/comp.lang.asm.x86/3pVGzQGb1ys ) (also found by pradhan) came up with something that is now called Matt Taylor's folding trick, a 32-bit friendly implementation to find the bit-index of LS1B ( https://en.wikipedia.org/wiki/Find_first_set ). Taylor's folding trick apparently is an adaptation of the De Bruijn ( https://en.wikipedia.org/wiki/Nicolaas_Govert_de_Bruijn ) bitscan, devised in 1997, according to Donald Knuth by Martin Läuter to determine the LS1B index by minimal perfect hashing ( https://en.wikipedia.org/wiki/Perfect_hash_function )。 BitTable 中的数字 (63, 30, ..) 和 PopBit 中的折叠 (0x783a9b23) 可能是与 Matt Taylor 的 32 位折叠技巧相关的所谓幻数（唯一？）。这种折叠技巧看起来很快，因为很多引擎都复制了这种方法(f.i Stockfish)。

如何找到魔法位板？

How to find magic bitboards?

c

bit-manipulation

chess