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;
}
它来自国际象棋编程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
将位板与自身减1进行异或(为什么?)。然后它将其与一个完整的32位,在这里的某个地方,我的大脑内存用完了。不知何故,神奇的十六进制数0x 783 a9 b23被卷入其中(那是《迷失》中的数字序列吗?)。还有这个荒谬的神秘数组,由0-63(X1 M4 N1 X)随机排序的数字组成。
4条答案
按热度按时间4nkexdtk1#
好吧,我想出来了。
首先是一些术语:
例如e4方块上的车,在e2,e5,e7,b4和c4上有一些随机的棋子。
注意事项:
moveboard &= ~friendly_pieces)
每一个方块和方块组合都可以找到神奇的数字。要做到这一点,你必须计算每一个方块/方块组合的每一个可能的阻挡板变化。这就是问题代码正在做的事情。* 它是如何 * 做的,对我来说仍然是一个谜,但似乎也是原作者马特泰勒的情况。(感谢@Pradhan提供链接)
因此,我所做的是重新实现生成所有可能的阻隔板变体的代码。它使用了不同的技术,虽然速度稍慢,但更容易阅读和理解。速度稍慢的事实不是问题,因为这段代码并不要求速度。程序只需在程序启动时执行一次,在双核i5上只需几微秒。
要使用它,请执行以下操作:
工作原理:有2^bits阻塞器板,其中
bits
是阻塞器掩码中1的数量,1是唯一相关的位。此外,从0到2^bits的每个整数都有一个长度为bits
的1和0的唯一序列。因此,该函数只是将给定整数中的每个位与阻塞器掩码中的相关位相对应。并相应地将其关闭/打开以生成唯一的阻断板。它不是那么聪明或快速,但它是可读的。
uz75evzq2#
好吧,我试着一步步来。
7只是在0和2^10之间随机选择的一个数,10是m中设置的位数。m可以用四种方式表示:
继续,这个函数会被调用10次,它有一个返回值,它修改了m.
在pop_1st_bit中,m用bb表示,为清楚起见,我将其改为m。
m-1部分取已设置的最低有效位,并翻转该位及其以下的所有位。XOR之后,所有更改的位现在都设置为1,而所有较高的位都设置为0。
下一篇:
(b & 0xffffffff)
部件将b与低32个置位进行AND运算,因此这实际上清除了b上半部分的所有位。... ^ (b >> 32)
部分将B的上半部分移到下半部分,然后将其与前一个操作的结果进行异或,因此它基本上是将b的上半部分与b的下半部分进行异或,这在本例中没有任何效果,因为b的上半部分一开始就是空的。我不明白“折叠”的意义,即使b的上半部分已经有了位。
不管怎样,继续,下一行实际上修改了m,通过置零最低位,这是有意义的。
下一部分将
fold
乘以某个十六进制数(质数?),将乘积26右移,并将其用作BitTable的索引,BitTable是我们神秘的随机排序数数组0-63。此时,我怀疑作者可能正在编写伪随机数生成器。这就结束了pop_1st_bit,一共执行了10次(m中初始设置的每一位执行一次),10次调用pop_1st_bit都返回一个数字0-63。
在上面的两行中,
i
是我们当前使用的位,0-9。因此,如果index
数字(最初作为参数传递给index_to_uint64的7)设置了第i位,则设置结果中的第j位,其中j是pop_1st_bit的返回值0-63。就是这样!我还是很困惑
svdrlsy43#
When watching a video series on chess engines on youtube I had exactly the same questions as paulwal222. There seems to be some high level mathematics involved. The best links explaining the background of this difficult subject are 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 ). The numbers of the BitTable (63, 30, ..) and the fold in PopBit (0x783a9b23) are probably the so called magic numbers (uniquely?) related to Matt Taylor's 32-bit folding trick. This folding trick seems to be very fast, because lots of engines have copied this approach (f.i Stockfish).
c90pui9n4#
目标是找到并返回给定整数中最低有效位(LSB)的位置,然后将LSB设置为零,因此如果
m = 1010 0100
,我们希望函数返回索引2并将m修改为:为了了解在这个过程中发生了什么,最简单的是查看8位情况以及在pop_1st_bit
的前2行中发生了什么:在上面,X表示我们不关心这些位置的位的值,所以,
m^(m-1)
根据LSB的位置将每个8位数字Map到8个8位密钥中的一个。然后,折叠操作将每个8位密钥转换为唯一的4位密钥。(64位)情况是通过用32位乘法代替fold*magic
中的64位乘法来避免它。8位情况下的表包含8个值(8位整数中每个可能的LSB位置对应一个值),因此,我们需要3位来索引表,右移将给予这3位,即计算移位位数的公式:
因此,在原始情况下,我们得到:32 -log 2(64)= 26,而在8位的情况下,我们得到4 -log 2(8)= 1。
因此:
table_index = fold*magic >> 1
,将为我们提供0-7之间的数字,我们需要索引表。我们现在需要做的是找到magic
,它为我们的8个4位键中的每一个提供不同的值。在本例中,我们需要的4位幻数是5(0 b 0101),您可以通过强力查找
magic
,使fold*magic >> 1
为8个“fold”键中的每一个键生成唯一的值(这里值得注意的是,我假设fold
和magic
的4位乘法的任何溢出位都消失了):当LSB是第0位时,
fold*5 >> 1
将是2,因此我们将0放在数组的索引2处;当LSB是第1位时,fold*5 >> 1
将是7,因此我们将1放在数组的索引7处,等等。根据上面的结果,我们可以将数组构建为{7,2,0,4,6,3,5,1},数组的排序看起来毫无意义,但实际上它只与
fold*5 >> 1
输出索引值的顺序有关。至于你是否应该这样做,我想这是硬件相关的,但是,我的处理器可以做同样的事情快五倍左右: