blocks|key|4495925|text|好的，我会试着一步一步来。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4495926|index_to_uint64(+7,+10,+m+);+|code-block|syntax|javascript|4495927|7是在0和2%5E10之间随机选择的数字，10是m中设置的位数。m可以用四种方式表示：|4495928|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|4495929|下一步。这将被调用10次。它有一个返回值，它修改了m。|4495930|pop_1st_bit(&m);|4495931|在pop_1st_bit中，m由bb引用。为清楚起见，我将其更改为m。|4495932|uint64+b+=+m%5E(m-1);|4495933|m-1部分取所设置的最低有效位，并翻转它和它下面的所有位。在XOR之后，所有这些改变的位现在被设置为1，而所有更高的位被设置为0。|4495934|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|4495935|接下来：|4495936|unsigned+int+fold+=+(unsigned)+((b+&+0xffffffff)+%5E+(b+>>+32));|4495937|(b+&+0xffffffff)部分与低32个设置比特进行ANDs。所以这基本上清除了b的上半部分中的任何位。|offset|length|style|CODE|4495938|(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|4495939|...+%5E+(b+>>+32)部分将b的上半部分移入下半部分，然后将其与上一次操作的结果进行XOR运算。所以它基本上是对b的上半部分和b的下半部分进行异或运算，这在这种情况下没有作用，因为b的上半部分一开始就是空的。|4495940|>>+:0000+0000+0000+0000+0000+0000+0000+0000+0000+0000+0000+0000+0000+0000+0000+0000+
%5E++: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|4495941|我不明白这种“折叠”的意义，即使在b的上半部分设置了位。|4495942|不管怎样，下一步。下一行实际上是通过取消设置最低位来修改m。这是有道理的。|4495943|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+|4495944|下一部分将fold乘以某个十六进制数字(质数？)，右移乘积26，并将其用作BitTable的索引，这是我们神秘的随机有序数组0-63。在这一点上，我怀疑作者可能正在编写伪随机数生成器。|4495945|return+BitTable[(fold+*+0x783a9b23)+>>+26];|4495946|这就是pop_1st_bit的结论。所有这些操作都执行了10次(对于最初在m中设置的每一位，执行一次)。对pop_1st_bit的10次调用中的每一次都返回一个数字0-63。|4495947|j+=+pop_1st_bit(&m);
if(index+&+(1+<<+i))+result+%7C=+(1ULL+<<+j);|4495948|在上面两行中，i是我们当前所在的位，0-9。因此，如果index数(最初作为参数传递给index_to_uint64的7)设置了第i位，则设置结果中的第j位，其中j是pop_1st_bit的0-63返回值。|4495949|就是这样！我还是很困惑：|4495950|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0|G|0|0|0|F|0|0|0|0|0|5|4|0|0|0|0|7|1|R|5|0|0^^$0|@$1|2|3|4|5|6|7|1W|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|1X|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|1Y|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|1Z|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|20|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|21|8|@]|9|@]|A|$E|F]]|$1|O|3|P|5|6|7|22|8|@]|9|@]|A|$]]|$1|Q|3|R|5|D|7|23|8|@]|9|@]|A|$E|F]]|$1|S|3|T|5|6|7|24|8|@]|9|@]|A|$]]|$1|U|3|V|5|D|7|25|8|@]|9|@]|A|$E|F]]|$1|W|3|X|5|6|7|26|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|D|7|27|8|@]|9|@]|A|$E|F]]|$1|10|3|11|5|6|7|28|8|@$12|29|13|2A|14|15]]|9|@]|A|$]]|$1|16|3|17|5|D|7|2B|8|@]|9|@]|A|$E|F]]|$1|18|3|19|5|6|7|2C|8|@$12|2D|13|2E|14|15]]|9|@]|A|$]]|$1|1A|3|1B|5|D|7|2F|8|@]|9|@]|A|$E|F]]|$1|1C|3|1D|5|6|7|2G|8|@]|9|@]|A|$]]|$1|1E|3|1F|5|6|7|2H|8|@]|9|@]|A|$]]|$1|1G|3|1H|5|D|7|2I|8|@]|9|@]|A|$E|F]]|$1|1I|3|1J|5|6|7|2J|8|@$12|2K|13|2L|14|15]]|9|@]|A|$]]|$1|1K|3|1L|5|D|7|2M|8|@]|9|@]|A|$E|F]]|$1|1M|3|1N|5|6|7|2N|8|@]|9|@]|A|$]]|$1|1O|3|1P|5|D|7|2O|8|@]|9|@]|A|$E|F]]|$1|1Q|3|1R|5|6|7|2P|8|@$12|2Q|13|2R|14|15]|$12|2S|13|2T|14|15]]|9|@]|A|$]]|$1|1S|3|1T|5|6|7|2U|8|@]|9|@]|A|$]]|$1|1U|3|-4|5|6|7|2V|8|@]|9|@]|A|$]]]|1V|$]]

Alright, I'm going to try to step through this.

<pre><code>index_to_uint64( 7, 10, m ); 
</code></pre>

7 is just a randomly chosen number between 0 and 2^10, and 10 is the number of bits set in m. m can be represented in four ways:

<pre><code>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
</code></pre>

Moving on. This will be called 10 times. It has a return value and it modifies m.

<pre><code>pop_1st_bit(&amp;m);
</code></pre>

In pop_1st_bit, m is referred to by bb. I'll change it to m for clarity. 

<pre><code>uint64 b = m^(m-1);
</code></pre>

The m-1 part takes the least significant bit that is set and flips it and all the bits below it. After the XOR, all those changed bits are now set to 1 while all the higher bits are set to 0.

<pre><code>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
</code></pre>

Next:

<pre><code>unsigned int fold = (unsigned) ((b &amp; 0xffffffff) ^ (b &gt;&gt; 32));
</code></pre>

The <code>(b &amp; 0xffffffff)</code> part ANDs b with lower 32 set bits. So this essentially clears any bits in the upper half of b.

<pre><code>(b &amp; 0xffffffff)
b: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 1111 1111
&amp;: 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
</code></pre>

The <code>... ^ (b &gt;&gt; 32)</code> part shifts the upper half of b into the lower half, then XORs it with the result of the previous operation. So it basically XORs the top half of b with the lower half of b. This has no effect in this case because the upper half of b was empty to begin with.

<pre><code>&gt;&gt; :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
</code></pre>

I don't understand the point of that "folding", even if there had been bits set in the upper half of b. 

Anyways, moving on. This next line actually modifies m by unsetting the lowest bit. That makes some sense.

<pre><code>m &amp;= (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
&amp; : 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0000 0000 0000 0000 
</code></pre>

This next part multiplies <code>fold</code> by some hex number (a prime?), right shifts the product 26, and uses that as an index into BitTable, our mysterious array of randomly ordered numbers 0-63. At this point I suspect the author might be writing a pseudo random number generator.

<pre><code>return BitTable[(fold * 0x783a9b23) &gt;&gt; 26];
</code></pre>

That concludes pop_1st_bit. That's all done 10 times (once for each bit originally set in m). Each of the 10 calls to pop_1st_bit returns a number 0-63. 

<pre><code>j = pop_1st_bit(&amp;m);
if(index &amp; (1 &lt;&lt; i)) result |= (1ULL &lt;&lt; j);
</code></pre>

In the above two lines, <code>i</code> is the current bit we are on, 0-9. So if the <code>index</code> number (the 7 originally passed as an argument to index_to_uint64) has the i'th bit set, then set the j'th bit in the result, where j was the 0-63 return value from pop_1st_bit.

And that's it! I'm still confused :(

blocks|key|4496804|text|当我在youtube上观看国际象棋引擎的视频系列时，我和paulwal222有完全相同的问题。这似乎涉及到一些高水平的数学。解释这个困难主题背景的最好的链接是https://chessprogramming.wikispaces.com/Matt%2BTaylor和https://chessprogramming.wikispaces.com/BitScan。似乎Matt+Taylor在2003年的google.group+(+https://groups.google.com/forum/#!topic/comp.lang.asm.x86/3pVGzQGb1ys+)+(也是由pradhan发现的)中想出了现在被称为Matt+Taylor的折叠技巧，一个32位友好的实现来查找LS1B+(+https://en.wikipedia.org/wiki/Find_first_set+)的位索引。泰勒的折叠技巧显然是对De+Bruijn+(+https://en.wikipedia.org/wiki/Nicolaas_Govert_de_Bruijn+)位扫描的改编，根据Martin+Läuter的Donald+Knuth在1997年设计的通过最小完美散列(+https://en.wikipedia.org/wiki/Perfect_hash_function+)确定LS1B索引。BitTable的编号(63，30，..)PopBit中的折叠数(0x783a9b23)可能是所谓的幻数(唯一？)与马特·泰勒的32位折叠技巧有关。这种折叠技巧似乎非常快，因为许多引擎都复制了这种方法(f.i+Stockfish)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|4496805|entityMap|0|LINK|mutability|MUTABLE|url|https://chessprogramming.wikispaces.com/Matt%2BTaylor|1|https://chessprogramming.wikispaces.com/BitScan|2|https://groups.google.com/forum/#!topic/comp.lang.asm.x86/3pVGzQGb1ys|3|https://en.wikipedia.org/wiki/Find_first_set|4|https://en.wikipedia.org/wiki/Nicolaas_Govert_de_Bruijn|5|https://en.wikipedia.org/wiki/Perfect_hash_function^0|27|1F|0|3N|1B|1|5Y|1X|2|9N|18|3|BP|1J|4|ES|1F|5|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@$A|W|B|X|1|Y]|$A|Z|B|10|1|11]|$A|12|B|13|1|14]|$A|15|B|16|1|17]|$A|18|B|19|1|1A]|$A|1B|B|1C|1|1D]]|C|$]]|$1|D|3|-4|5|6|7|1E|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]|N|$5|G|H|I|C|$J|O]]|P|$5|G|H|I|C|$J|Q]]|R|$5|G|H|I|C|$J|S]]|T|$5|G|H|I|C|$J|U]]]]

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 <a href="https://chessprogramming.wikispaces.com/Matt+Taylor" rel="nofollow noreferrer">https://chessprogramming.wikispaces.com/Matt+Taylor</a> and <a href="https://chessprogramming.wikispaces.com/BitScan" rel="nofollow noreferrer">https://chessprogramming.wikispaces.com/BitScan</a> . It seems that Matt Taylor in 2003 in a google.group ( <a href="https://groups.google.com/forum/#!topic/comp.lang.asm.x86/3pVGzQGb1ys" rel="nofollow noreferrer">https://groups.google.com/forum/#!topic/comp.lang.asm.x86/3pVGzQGb1ys</a> ) (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 ( <a href="https://en.wikipedia.org/wiki/Find_first_set" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Find_first_set</a> ). Taylor's folding trick apparently is an adaptation of the De Bruijn ( <a href="https://en.wikipedia.org/wiki/Nicolaas_Govert_de_Bruijn" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Nicolaas_Govert_de_Bruijn</a> ) bitscan, devised in 1997, according to Donald Knuth by Martin Läuter to determine the LS1B index by minimal perfect hashing ( <a href="https://en.wikipedia.org/wiki/Perfect_hash_function" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Perfect_hash_function</a> ). 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).

<pre><code>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 &amp; 0xffffffff) ^ (b &gt;&gt; 32));
 *bb &amp;= (*bb - 1);
 return BitTable[(fold * 0x783a9b23) &gt;&gt; 26];
}

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

It's from the Chess Programming Wiki: 
<a href="https://www.chessprogramming.org/Looking_for_Magics" rel="nofollow noreferrer">https://www.chessprogramming.org/Looking_for_Magics</a>

It's part of some code for finding <a href="http://www.rivalchess.com/magic-bitboards/" rel="nofollow noreferrer">magic numbers</a>.

The argument <code>uint64 m</code> is a <a href="https://www.chessprogramming.org/Bitboards" rel="nofollow noreferrer">bitboard</a> representing the possible blocked squares for either a rook or bishop move. Example for a rook on the e4 square:

<pre><code>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 
</code></pre>

The edge squares are zero because they always block, and reducing the number of bits needed is apparently helpful.

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

So in the example above, <code>index_to_uint64</code> takes an index (0 to 2^bits), and the number of bits set in the bitboard (10), and the bitboard.

It then <code>pops_1st_bit</code> for each number of bits, followed by another shifty bit of code. <code>pops_1st_bit</code> XORs the bitboard with itself minus one (why?). Then it ANDs it with a full 32-bits, and somewhere around here my brain runs out of RAM. Somehow the magical hex number 0x783a9b23 is involved (is that the number sequence from Lost?). And there is this ridiculous mystery array of randomly ordered numbers from 0-63 (<code>BitTable[64]</code>).

How to find magic bitboards?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

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, ...

问如何找到魔术位板？
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何找到魔术位板？EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何找到魔术位板？
EN