0

我正在用 C# 编写一个带有魔法位板的国际象棋引擎，现在速度很慢。从初始位置计算 perft 6（119,060,324 个位置）需要 2 分钟，而其他引擎可以在 1-3 秒内完成。我目前正在使用这种方法来查找位板上所有 1 的索引：

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

public static List<int> bitScan(ulong bitboard) {
        var indices = new List<int>(30);
        const ulong deBruijn64 = 0x03f79d71b4cb0a89UL;

        while (bitboard != 0) {
            indices.Add(index64[((bitboard ^ (bitboard - 1)) * deBruijn64) >> 58]);
            bitboard &= bitboard - 1;
        }
        return indices;
    }

这是被调用最多的方法，我想加快它。有没有更快的方法来做到这一点？我想返回一个数组而不是一个列表，但是我不知道如何因为位数是未知的（而且我不想要空元素，因为我有很多 foreach 循环）。

任何建议表示赞赏。

4

2 回答 2

1

我会说这List<T>是最大的性能小偷。与您自己的实现相比，这如何工作？：

public static readonly byte[] index64 = {
         0, 47,  1, 56, 48, 27,  2, 60,
         57, 49, 41, 37, 28, 16,  3, 61,
         54, 58, 35, 52, 50, 42, 21, 44,
         38, 32, 29, 23, 17, 11,  4, 62,
         46, 55, 26, 59, 40, 36, 15, 53,
         34, 51, 20, 43, 31, 22, 10, 45,
         25, 39, 14, 33, 19, 30,  9, 24,
         13, 18,  8, 12,  7,  6,  5, 63
    };

private static const ulong deBruijn64 = 0x03f79d71b4cb0a89UL; // Do not initialize many times
public static byte[] bitScan(ulong bitboard) {
  // Should never be more than that right, queen can hit maximum 28 squares?
  var indices = new byte[28]; 
  var index = 0;
  while (bitboard != 0) {
    indices[index++] = index64[((bitboard ^ (bitboard - 1)) * deBruijn64) >> 58];
    bitboard &= bitboard - 1;
  }
  return indices;
}

在方法之外使用它时，不要关心数组中的 0。

于 2014-07-17T09:20:15.710 回答
0

在 C/Assembly 中，您可以使用 TZCNT、LZCNT 和 POPCNT 命令进行位扫描，您现在可以在处理器上找到这些命令。使用 Java 的 JNI 我就是这样编程的，令我惊讶的是，它并不比 Java 的 Long.numberOfTrailingZeroCount() 快。解释是 JVM 无论如何都使用 TZCNT 进行优化，所以我只是添加了 JNI 开销。这是从 Java 7 开始的，但我确信 Microsoft 必须对 .Net 进行相同的优化。

于 2015-08-26T11:33:45.727 回答