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 ^ bits)，在位板(10)和位板中设置的位数。然后，为每个位数添加
pops_1st_bit，然后再添加另一个移位的代码位。 pops_1st_bit对位板本身进行减一运算(为什么？)。然后将其与一个完整的32位进行“与”运算，然后我的大脑在内存不足的地方耗尽。不知何故涉及到了神奇的十六进制数字0x783a9b23(这是Lost的数字序列吗？)。还有一个荒谬的神秘数组，其中包含0-63(BitTable[64])中随机排列的数字。 最佳答案
好吧，我知道了。
首先，一些术语:
阻止程序 mask :一个位板，包含可以阻止一个块的所有正方形，对于给定的块类型和该块所在的正方形。它不包括终止边缘方块，因为它们总是会阻塞。
封闭板:包含占用正方形的位板。它仅具有正方形，也位于阻止程序蒙版中。
移动板:一个位板，包含一块可以移动到的所有正方形，给定一块类型，一个正方形和一块封闭板。如果 Artifact 可以移动到那里，它包括终止边缘正方形。
一个在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) 幻数方法的目标是非常快速地查找给定的封闭板的预先计算的移动板。否则，您每次都必须(缓慢地)计算移动板。这仅适用于滑动件，即车子和主教。女王只是新秀和主教的结合。
可以为每个方块和棋子组合找到魔术数字。为此，您必须为每个正方形/一块组合计算每种可能的挡板差异。这就是有问题的代码在做什么。它的运行方式对我来说还是个谜，但是that also seems to be the case for the apparent original author, Matt Taylor。 (感谢@Pradhan的链接)
因此，我所做的就是重新实现了用于生成所有可能的插板变化的代码。它使用了不同的技术，虽然速度稍慢一些，但阅读和理解起来却容易得多。它稍微慢一点的事实不是问题，因为此代码对速度没有严格要求。该程序仅需在程序启动时执行一次，并且在双核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是阻塞器掩码中的1的数目，这是唯一相关的位。同样，每个从0到2 ^ bits的整数具有bits长度的1和0的唯一序列。因此，此功能仅将给定整数中的每个位与阻止程序掩码中的相关位相对应，并相应地将其关闭/打开以生成唯一的阻止程序板。它不那么聪明或快速，但可读性强。