Best bitboard design?

[MartinBryant]

In 2019, after eleven years off from computer chess, I finally converted Colossus to use bitboards.
I only spent a couple of months on it (before getting distracted again) and adopted a 'keep it simple stupid' approach for my own sanity whilst trying to get my aging brain around bitboards.

Recently I have gotten back into the swing of things again and am now wondering if my current simple design should be improved upon.

My main bitboard storage is a single, two-dimensional array...
UINT64 PiecesBB[Sides][Pieces];

Looking at the Stockfish code they take a different approach...
Bitboard byTypeBB[PIECE_TYPE_NB];
Bitboard byColorBB[COLOR_NB];

(We both reserve a special entry for 'all' pieces within the array.)


I can see the Stockfish approach has an immediate advantage when you need the 'all occupied squares' bitboard...
For Colossus I often have to do...
PiecesBB[0][AllPieces] | PiecesBB[1][AllPieces];
But Stockfish simply has...
byTypeBB[ALL_PIECES]

Also the Stockfish design has the advantage of greater data density as it represents the whole board in fewer bitboards.


What other designs are there? What do you guys use?
Is there a generally accepted 'best' design?
What other advantages might they offer? (I'm loath to rewrite a load of working/tested code for negligible benefit )

Many thanks in advance for any pearls of wisdom!

[hgm]

Best design of course is mailbox + attack map. See the 'mailbox trials' discussion.

[MartinBryant]

Ahhh... but that wasn't the question

[Sven]

I think the number of bitboards you store is not so much a matter of design but an implementation detail which can be hidden to your "application code" (movegen, eval, search) by abstraction.

[Kotlov]

Best design of course is mailbox + attack map. See the 'mailbox trials' discussion.

questionable statement

[hgm]

questionable statement

Can you beat the speed of the sample program in the mailbox-trials thread, then?

The point was, when using a vastly sub-optimal design, why care which of the only marginally different sub-optimal designs is 'best'?

[Joost Buijs]

I expect that an optimized bitboard implementation on modern hardware compiled with a modern compiler will beat your mailbox implementation by a huge margin. With an old 32 bit compiler from 15 years back this will be difficult though, I agree.

[Joost Buijs]

What other designs are there? What do you guys use?
Is there a generally accepted 'best' design?
What other advantages might they offer? (I'm loath to rewrite a load of working/tested code for negligible benefit )

Many thanks in advance for any pearls of wisdom!

20 years ago I switched from mailbox to bit-boards, since that time I use this and never changed it:

Code: Select all

bb_t bb_occupied[numSides];
bb_t bb_pawns[numSides];
bb_t bb_knights[numSides];
bb_t bb_bishops[numSides];
bb_t bb_rooks[numSides];
bb_t bb_queens[numSides];
bb_t bb_king[numSides];
uint8_t pieces[numSquares];

It really doesn't matter much how you do it, you can put the bit-boards in an array of 2 structs (one for each color), or only use 1 bit-board for each piece type with an occupied bit-board for each color and mask them. In the end there is hardly any difference in performance.

[hgm]

I expect that an optimized bitboard implementation on modern hardware compiled with a modern compiler will beat your mailbox implementation by a huge margin. With an old 32 bit compiler from 15 years back this will be difficult though, I agree.

Well, I expect the opposit. Because it has to execute so many more instructions to do what it does. Not sure what fuels your expectations.

[Joost Buijs]

I expect that an optimized bitboard implementation on modern hardware compiled with a modern compiler will beat your mailbox implementation by a huge margin. With an old 32 bit compiler from 15 years back this will be difficult though, I agree.

Well, I expect the opposit. Because it has to execute so many more instructions to do what it does. Not sure what fuels your expectations.

Generally speaking mailbox implementations do a lot more memory accesses, this is at least my experience. It could be that when everything resides inside the cache it won't matter. The only way to find out is to mimic your example mailbox implementation with a bit-board one. Currently I'm too busy with other things like ANN's, but it is interesting enough to have a look at it later.