Magic bitboards未给国际象棋引擎带来预期提速问题咨询

• 你当前的查找表实现并非标准Magic bitboards逻辑：Magic bitboards的核心是通过预计算的Magic数对阻挡位掩码做哈希运算，将不同的阻挡组合映射到无冲突的紧凑索引，而你当前使用的(occ >> (64-13)) + 8192 * square索引计算逻辑，本质是对所有格子统一保留13位阻挡位做全量索引，没有用到Magic哈希的压缩能力，不仅没有减少走法生成的运算量，过大的查找表还会降低CPU缓存命中率，自然不会有明显提速。
• 优化方案：
  1. 采用标准Magic bitboards实现，为每个格子预计算专属的Magic数、掩码长度和偏移量，不同位置的车/象所需的索引长度不同（比如边角的车掩码仅需6~10位），总查找表大小可以压缩到1MB以内，大幅提升缓存命中率。
  2. 更换perft测试场景：你当前使用的R7/8/8/8/8/8/8/8局面无子力阻挡，走法生成逻辑的运算量极低，无法体现Magic bitboards的优势，换成子力密集的中局测试局面才能测出真实的提速效果。
• 查找表体积本身不是核心问题，只要索引计算逻辑正确，即使是2MB以内的查找表都可以完全被CPU L2缓存容纳，不会产生性能损耗。

你当前使用的ls1b和count函数都是纯软件循环实现，性能远低于硬件指令级的实现：

• 位计数优化：直接使用编译器内置位计数函数，GCC/Clang下用__builtin_popcountll，MSVC下用__popcnt64，C++20标准可以直接用std::popcount，以上实现都会被编译为单条popcntCPU指令，单周期即可完成运算，比循环实现快5~10倍。
• 最低位1索引优化：直接使用编译器内置trailing zero计数函数，GCC/Clang下用__builtin_ctzll，MSVC下用_BitScanForward64，C++20标准可以直接用std::countr_zero，对应CPU的tzcnt指令，同样是单周期运算，完全不需要额外调用位计数函数。
• 标准位遍历代码实现：

#include <cstdint>
#ifdef _MSC_VER
#include <intrin.h>
#endif

int popcount(uint64_t bb) {
#ifdef _MSC_VER
    return static_cast<int>(__popcnt64(bb));
#else
    return static_cast<int>(__builtin_popcountll(bb));
#endif
}

int lsb(uint64_t bb) {
#ifdef _MSC_VER
    unsigned long idx;
    _BitScanForward64(&idx, bb);
    return static_cast<int>(idx);
#else
    return static_cast<int>(__builtin_ctzll(bb));
#endif
}

// 遍历示例
void iterate_bb(uint64_t bb) {
    while (bb) {
        uint64_t lsb_bb = bb & -bb;
        int sq = lsb(lsb_bb);
        // 处理sq对应的格子
        bb ^= lsb_bb;
        // 支持BMI2指令集可以替换为 bb = _blsr_u64(bb); 进一步提速
    }
}

Stockfish完全基于编译器内置函数和CPU指令集优化位遍历逻辑：

• 位计数和最低位索引直接调用对应内置函数，编译为popcnt、tzcnt硬件指令
• 支持BMI2指令集的编译目标下，使用blsr指令直接清零最低位1，省略bb &= bb -1的运算步骤
• 所有位操作函数都会被声明为inline甚至force_inline，避免函数调用开销

内容的提问来源于stack exchange，提问作者spinosarus123