2

I am making a chess engine, and for now I’m working on the move generation. I’m using bitboards, and so for example my magic bit boards file for a knight on d4 is

00000000
00000000
00101000
01000100
000N0000
01000100
00101000
00000000

Which is represented by some unsigned long long integer.

I need this in a format where I can store the moves in a move list, and also make the move. E.g. {10,12,17,21,33,37,42,44}

What would be the fastest way to get the indices of the “1” bits in the bitboard during runtime? Currently I isolate the least significant 1 bit with x &= -x, and then XOR the position until I get 0. But is there a faster way to do this?

3

I found some well hidden pages in the Chess Programming Wiki.

The first one basically introduces your solution:

https://www.chessprogramming.org/Bitboard_Serialization#Single_Bits

However, the next chapter states that most applications are interested in the index of the square rather than its bitboard representation:

https://www.chessprogramming.org/Bitboard_Serialization#Square_Index_Serialization

This is done using a bitscan routine. There is another page dedicated to them:

https://www.chessprogramming.org/BitScan

It shouldn't be a surprise that the fastest method is to use processor specific instructions:

https://www.chessprogramming.org/BitScan#bsfbsr

If this is not possible, there are many other algorithms described there, which you can choose from.

There is also a Java dedicated version of this page, which describes API methods, which may be intrinsified by the VM:

https://www.chessprogramming.org/Java-Bitscan

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.