国际象棋:bitscanning

本文关键字：bitscanning 国际象棋 | 更新日期: 2023-09-27 18:13:15

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

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循环)。

任何建议都是感激的。

国际象棋:bitscanning

我会说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

在C/Assembly中，您可以使用TZCNT, LZCNT和POPCNT命令进行位扫描，您可以在处理器上找到这些命令。我使用Java的JNI进行了编程，令我惊讶的是，它并不比Java的Long.numberOfTrailingZeroCount()快。原因是JVM无论如何都会使用TZCNT进行优化，所以我只是增加了JNI开销。这是从Java 7开始的，但我相信微软一定对。net做了同样的优化。

相关文章：