魔术比特板不会加速国际象棋引擎

Question

我刚刚开始编写国际象棋引擎，但最近刚刚完成了我的第一个程序。但它运行得很慢，所以我切换到了比特板，现在切换到了魔法比特板。我经常使用国际象棋编程维基。

我现在尝试一个测试位置和perft函数，看看程序每秒可以计算多少节点（包括批量计数）。现在，我的perft函数被设置为只计算伪合法移动，我已经设置make_move函数不切换回合。因此我可以用perft分析位置R7/8/8/8/8/8/8 w。

然而我的问题是，如果没有魔术比特板，我每秒得到622万个节点，而有了我只得到6.29。似乎我的魔术比特板没有正常工作。直觉上感觉魔术比特板的速度应该要大得多。此外，95%的计算时间花在我的伪合法移动生成器中。

正如我所提到的，我是国际象棋引擎的新手，尤其是魔术比特板。我不知道如何正确地完成搜寻列表，现在我有一个64*8192条目的表（用于rooks）。我在程序开始时初始化这个表，通过计算每个方块的所有不同的阻止器组合。然后我的索引由（occ给出

我缓慢的魔术比特板的原因是我巨大的表大小吗？有没有其他方法可以更有效地做到这一点？

速度如此之小的原因完全有可能是因为时间不是花在生成移动上，而是在不同的位板上迭代。有没有办法加快这个过程？似乎（通过谷歌搜索）我的功能

int ls1b(u64 bitboard) {
    if (bitboard) {
        return count((bitboard & -bitboard) - 1);
    }
    return -1;
}

和

int count(u64 bitboard) {
    int count = 0;
    while(bitboard) {
        count++;
        bitboard &= bitboard - 1;
    }
    return count;
}

尽可能快。stockfish（或其他c引擎）是如何进行这种迭代的？

Answer 1

我无法对程序的其余部分发表评论，因为我看不到它，但对于您的位函数，它们可以改进，请参见：

https://www.chessprogramming.org/BitScan#Trailing_Zero_Counthttps://en.wikipedia.org/wiki/Hamming_weight

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

const uint64_t m1  = 0x5555555555555555; //binary: 0101...
const uint64_t m2  = 0x3333333333333333; //binary: 00110011..
const uint64_t m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...

int count(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    return (x * h01) >> 56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}