Best bitboard design?

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
MartinBryant
Posts: 26
Joined: Wed Nov 20, 2013 11:37 pm
Location: Manchester, UK
Full name: Martin Bryant

Best bitboard design?

Post by MartinBryant » Thu May 13, 2021 9:50 am

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!

User avatar
hgm
Posts: 26434
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Best bitboard design?

Post by hgm » Thu May 13, 2021 11:14 am

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

MartinBryant
Posts: 26
Joined: Wed Nov 20, 2013 11:37 pm
Location: Manchester, UK
Full name: Martin Bryant

Re: Best bitboard design?

Post by MartinBryant » Thu May 13, 2021 11:29 am

Ahhh... but that wasn't the question :)

Sven
Posts: 4004
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Best bitboard design?

Post by Sven » Thu May 13, 2021 11:40 am

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.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

User avatar
Kotlov
Posts: 254
Joined: Fri Jul 10, 2015 7:23 pm
Location: Russia

Re: Best bitboard design?

Post by Kotlov » Thu May 13, 2021 12:39 pm

hgm wrote:
Thu May 13, 2021 11:14 am
Best design of course is mailbox + attack map. See the 'mailbox trials' discussion.
questionable statement
Eugene Kotlov
Hedgehog 2.1 64-bit coming soon...

User avatar
hgm
Posts: 26434
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Best bitboard design?

Post by hgm » Thu May 13, 2021 2:11 pm

Kotlov wrote:
Thu May 13, 2021 12:39 pm
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
Posts: 1344
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Best bitboard design?

Post by Joost Buijs » Thu May 13, 2021 2:50 pm

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
Posts: 1344
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Best bitboard design?

Post by Joost Buijs » Thu May 13, 2021 3:08 pm

MartinBryant wrote:
Thu May 13, 2021 9:50 am
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.
Last edited by Joost Buijs on Thu May 13, 2021 3:10 pm, edited 1 time in total.

User avatar
hgm
Posts: 26434
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Best bitboard design?

Post by hgm » Thu May 13, 2021 3:11 pm

Joost Buijs wrote:
Thu May 13, 2021 2:50 pm
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
Posts: 1344
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Best bitboard design?

Post by Joost Buijs » Thu May 13, 2021 3:38 pm

hgm wrote:
Thu May 13, 2021 3:11 pm
Joost Buijs wrote:
Thu May 13, 2021 2:50 pm
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.

Post Reply