Bitboard file and rank, and bitboard footprint

[jshriver]

Given a bitboard is there an easy way to get the file and rank based on a position? Position being the nth bit.

Saw a slick way once for 0x88 but haven't come across any for bitboard yet.

-Josh

P.S. Side note, it seems bitboards have a larger footprint than even a plain 64bit character array. 6 pieces, 2 colors so 12 pieces at 64bits a position would be 8bytes per position so 96bytes per board state. Sound right?

[bhlangonijr]

Given a bitboard is there an easy way to get the file and rank based on a position? Position being the nth bit.

Saw a slick way once for 0x88 but haven't come across any for bitboard yet.

-Josh

P.S. Side note, it seems bitboards have a larger footprint than even a plain 64bit character array. 6 pieces, 2 colors so 12 pieces at 64bits a position would be 8bytes per position so 96bytes per board state. Sound right?

You must first retrieve the bit index from the bitboard (by doing a hardware bistscan or calculate it using De Brujin), and then convert the square index to the correlate Rank and File (It is very cheap if you lookup the rank and file in a table indexed by a given square).

But I guess you are looking for something more simple. I don't know if there is simpler method.

Regards,

[AlvaroBegue]

First you need a function that will map the 64 possible inputs into small numbers. Here are three (roughly from slow/simple to fast/complex):
* x%67
* ffsll(x) (http://linux.die.net/man/3/ffsll)
* (DE_BRUIJN_MAGIC_CONSTANT * x) >> 58

Then you make use of a small look-up table that has a precomputed answer for each possibility.

If you use some method that already computes the bit number for you, you can simply compute bit_number%8 and bit_number/8.

[AlvaroBegue]

P.S. Side note, it seems bitboards have a larger footprint than even a plain 64bit character array. 6 pieces, 2 colors so 12 pieces at 64bits a position would be 8bytes per position so 96bytes per board state. Sound right?

You probably mean "larger footprint than even a plan 64-byte array." The answer is yes, but it's basically irrelevant, since for the most part you shouldn't be making copies of the structure and you'll only have one of them.

[Gerd Isenberg]

* ffsll(x) (http://linux.die.net/man/3/ffsll)

That one was new to me. Thanks!

[Gerd Isenberg]

Given a bitboard is there an easy way to get the file and rank based on a position? Position being the nth bit.

Saw a slick way once for 0x88 but haven't come across any for bitboard yet.

Assuming the bitboard is single populated, I fear something like this is too expensive, specially if you need rank and file simultaneously ...

Code: Select all

int rank =   ((bb & 0xff00ff00ff00ff00 ) != 0)
         2 * ((bb & 0xffff0000ffff0000 ) != 0)
         4 * ((bb & 0xffffffff00000000 ) != 0);

As mentioned by others, this is a bitscan domain, bsf is fast again on todays x86-64 processors.

[Tord Romstad]

P.S. Side note, it seems bitboards have a larger footprint than even a plain 64bit character array. 6 pieces, 2 colors so 12 pieces at 64bits a position would be 8bytes per position so 96bytes per board state. Sound right?

Not necessarily. Use one bitboard for each color, and one for each piece type. When you want (say) a bitboard of all white bishops, you just intersect the bitboard of all white pieces with the bitboard of all bishops. You therefore need 2+6 = 8 bitboards to represent the board state, i.e exactly 64 bytes total.

This is almost exactly how we do it in Stockfish, by the way. But our board data structure is actually very large, because there is a lot of other info there, including an old-fashioned board[] array, piece lists for each piece type, piece counts for each piece type, and all previous hash keys all the way back to the last non-reversible move. The exact size of the entire board struct is probably architecture-dependent, but on my system (64-bit Mac OS X), it's 3808 bytes.