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!
Best bitboard design?
Moderators: hgm, Rebel, chrisw
-
- Posts: 69
- Joined: Thu Nov 21, 2013 12:37 am
- Location: Manchester, UK
- Full name: Martin Bryant
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Best bitboard design?
Best design of course is mailbox + attack map. See the 'mailbox trials' discussion.
-
- Posts: 69
- Joined: Thu Nov 21, 2013 12:37 am
- Location: Manchester, UK
- Full name: Martin Bryant
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Best bitboard design?
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)
-
- Posts: 266
- Joined: Fri Jul 10, 2015 9:23 pm
- Location: Russia
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Best bitboard design?
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.
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Best bitboard design?
20 years ago I switched from mailbox to bit-boards, since that time I use this and never changed it:MartinBryant wrote: ↑Thu May 13, 2021 11: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!
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];
Last edited by Joost Buijs on Thu May 13, 2021 5:10 pm, edited 1 time in total.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Best bitboard design?
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 wrote: ↑Thu May 13, 2021 4: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.
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Best bitboard design?
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.hgm wrote: ↑Thu May 13, 2021 5:11 pmWell, 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 wrote: ↑Thu May 13, 2021 4: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.