Chess: bitscanning

Question

I'm writing a chess engine in C# with magic bitboards and it's very slow right now. It takes 2 minutes to calculate perft 6 (119,060,324 positions) from the initial position when other engines can do it in 1-3 seconds. I'm currently using this method to find the indices of all 1s in the bitboard:

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;
    }

This is the method that is called the most, and I want to speed it up. Is there a faster way to do this? I want to return an array instead of a list, but I can't figure out how since the number of bits is unknown (and I don't want empty elements since I have lots of foreach loops).

Any advice is appreciated.

Have you tried using Visual Studios performance analyzer? Might give you a better clue as to what part of you program is causing the slowdown. — Dave3of5, Jul 17 '14 at 08:39
possible duplicate of [Get an array of the bit positions within a 64-bit integer](http://stackoverflow.com/questions/14086854/get-an-array-of-the-bit-positions-within-a-64-bit-integer) — AnthonyLambert, Jul 17 '14 at 08:43
This is the same home work as http://stackoverflow.com/questions/14086854/get-an-array-of-the-bit-positions-within-a-64-bit-integer — AnthonyLambert, Jul 17 '14 at 08:43

score 1 · Answer 1 · answered Jul 17 '14 at 09:20

I would say that the List<T> is the biggest performance thief. How does this work compared to your own implementation?:

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;
}

When using it outside of the method, just don't care about the 0's in the array.

score 0 · Answer 2 · answered Aug 26 '15 at 11:33

In C/Assembly you can use the TZCNT, LZCNT and POPCNT commands for bit-scanning which you find on processors nowadays. Using JNI for Java I programmed just that and to my surprise found that it was not faster than Java's Long.numberOfTrailingZeroCount(). The explanation was that the JVM optimizes using TZCNT anyway so I was just adding JNI overhead. This is from Java 7 onwards, but I am sure Microsoft must have the same optimization for .Net.

Chess: bitscanning

2 Answers2