pau*_*222 17 c chess bit-manipulation
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;
}
它来自国际象棋编程维基:https:
//www.chessprogramming.org/Looking_for_Magics
它是查找幻数的一些代码的一部分.
该参数uint64 m是一个位板,表示车辆或主教移动的可能被阻挡的方块.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将位板与自身减去一个XOR(为什么？).然后它用一个完整的32位对它进行AND运算,在这里的某个地方,我的大脑耗尽RAM.不知何故,涉及神奇的十六进制数0x783a9b23(是Lost的数字序列？).并且有一个从0-63(BitTable[64])随机排序的数字的荒谬神秘数组.
好吧,我想通了.
首先,一些术语:
阻挡掩模:包含所有可以阻挡一块的方块的位板,对于给定的块类型和该块所在的方块.它排除了终止边缘正方形,因为它们总是阻塞.
阻挡板:包含占用方块的位板.它只有阻挡掩码中的方块.
移动板:一个包含所有方块的位板,一块可以移动到,给定一块,一个正方形和一块挡板.如果棋子可以在那里移动,它包括终止边缘正方形.
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)魔术数字方法的目标是非常快速地查找给定阻挡板的预先计算的移动板.否则你每次都必须(慢慢地)计算移动板.这仅适用于滑块,即车和主教.女王只是车和主教的组合.
可以为每个正方形和片段类型组合找到幻数.要做到这一点,你必须计算每个方块/件组合的每个可能的阻挡板变化.这就是有问题的代码正在做的事情.它是如何做到这一点对我来说仍然有点神秘,但对于明显的原创作者马特泰勒而言,情况似乎也是如此.(感谢@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 ^位的每个整数都具有1和0的唯一序列长度bits.因此,该函数仅将给定整数中的每个位对应于阻塞掩码中的相关位,并相应地将其关闭/打开以生成唯一的阻塞板.
它不是那么聪明或快,但它是可读的.
好吧，我将尝试逐步解决这个问题。
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 次。它有一个返回值并修改 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
我不明白“折叠”的意义，即使在 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 的 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 是 pop_1st_bit 的 0-63 返回值。
就是这样！我还是很困惑:(