Fun with De Bruijn

[Henk]

I wanted to convert a bitboard position into a square position. So I decided to use a de Bruijn sequence to calculate row and colnr but it did not work. Finally it is working but what is wrong with using a simple Math.Log(bb, 2).

[bob]

I wanted to convert a bitboard position into a square position. So I decided to use a de Bruijn sequence to calculate row and colnr but it did not work. Finally it is working but what is wrong with using a simple Math.Log(bb, 2).

Do NOT get Gerd started on this again.

your head will explode.

[stegemma]

There's nothing bad in any method but I think that you should try various ones and see what is the fastest in your program. For my engine, BitScaForward64 is the fastest but the second choice is simply getting row/columns and add together with row*8+col. Using DeBruijn seems slower, in my test.

[matthewlai]

I wanted to convert a bitboard position into a square position. So I decided to use a de Bruijn sequence to calculate row and colnr but it did not work. Finally it is working but what is wrong with using a simple Math.Log(bb, 2).

It would be extremely slow. Both bb and 2 have to be converted to float first, have the log done (which is slow), and then converted back to int.

Pre-mature optimizations is bad... but don't pessimize prematurely, too. This is done a lot in eval and/or move generation (both are on the critical path), so attention does need to be paid to performance.

If the C# standard library doesn't provide a bitscan method which uses the CPU's bitscan instruction when available, there's not much you can do. That's the price you pay for using a managed language. That's why most people use C/C++ for performance-critical stuff (like chess engines).

[Dann Corbit]

Csharp has both 64 bit integers and shift operations.

[matthewlai]

Csharp has both 64 bit integers and shift operations.

But no bitscan?

[Dann Corbit]

No bitscan.
C# Alfil (for instance) uses DeBruijn and tables.

[RoadWarrior]

My C# BitScanForward code:

Code: Select all

private const UInt64 DEBRUIJN64 = 0x03f79d71b4cb0a89;
private 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
};

internal static Byte BitScanForward(UInt64 bitmap)
{
  Debug.Assert(bitmap != 0);
  return INDEX64[((bitmap ^ (bitmap - 1)) * DEBRUIJN64) >> 58];
}

[hgm]

Yes, that is a pretty efficient method. And its advantage over hardware bitscans is that you can fill the lookup table with arbitrary numbers, so that you can also tabulate other things than just the bit number, which otherwise would require a second lookup indexed by square number, or a calculation. For instance, if you use 0x88-style square numbering, rather than just 0-63.

[vittyvirus]

I wanted to convert a bitboard position into a square position. So I decided to use a de Bruijn sequence to calculate row and colnr but it did not work. Finally it is working but what is wrong with using a simple Math.Log(bb, 2).

Wow! This is the fastest way I've heard of. I wonder why people are wasting their time with magic (debruijn) hashing based methods. They involve a lot of instructions compared to this: Math.Log(bb, 2)! Just one instruction!!! I haven't done benchmarks yet, but I predict it is 13.64 times faster than with debruijn hashing. Also, Math.Log(bb, 2) gives you the advantage of using 2, which is quite hardware friendly, and this method can even take advantages of floating point hardware intrinsics, and thus making it even faster. I don't think your idea is original, but still I'd appreciate you for making us know tjis revolutionary idea.