Best bitboard design?

[chrisw]

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.

I use
U64 manhattans;
U64 diagonals;
Instead of
U64 rooks;
U64 bishops;
U64 queens;
Sometimes, I wish I didn’t, but these things tend to get fixed in cement.
U64 rooks = manhattans & not(diagonals);
U64 bishops = diagonals & not(manhattans);
U64 queens = manhattans & diagonals;

[Desperado]

I use a bitboard array bb[14].

Code: Select all

bb[0] = WHITE ( 0 == WHITE)
bb[1] = BLACK ( 1 == BLACK)
bb[2] = WP     ( 2 + WHITE ) 
bb[3] = BP      ( 2 + BLACK )

WN,BN,WB,BB,WR,BR,WQ,BQ

bb[13] = WK
bb[14] = BK

Having different bishop types (lightsquare,darksquare) you can simply increase the index to 16.

There are many code snippets where the code gets very simple. If you like it more compact (like array size [6])
you need to mask the piece types at a later point to get the color. This probably is a matter of taste (merge vs. split)

But it also can be relevant when you access piece type relevant arrays. If you hink of PSTs you can define color dependent arrays
and access them easily for example. On the other hand there might be redundant data at some other places.

To have WHITE,BLACK as index for the bitboards is pretty handy too (for me).

I am not sure what the best way in general is and although i use the scheme from the very beginning, i guess the memory footprint
can be a good reason to decide. For my thinking it was easier to code solutions with seperated piece ids and i simply kept it.

[Joost Buijs]

I completely forgot that in the past I used a union with an anonymous struct, this made it easier to index the board by piece type. Later I stopped using this.

Code: Select all

union board_t {
	struct {
		bb_t bb_occupied[2];
		bb_t bb_pawns[2];
		bb_t bb_knights[2];
		bb_t bb_bishops[2];
		bb_t bb_rooks[2];
		bb_t bb_queens[2];
		bb_t bb_king[2];
	};
	
	bb_t board[14];
};

enum pieceType {
	White, Black,
	whitePawn, blackPawn,
	whiteKnight, blackKnight,
	whiteBishop, blackBishop,
	whiteRook, blackRook,
	whiteQueen, blackQueen,
	whiteKing, blackKing
};

[Kotlov]

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'?

This "sample program" play chess or just show some values?

[hgm]

It measures the speed with which you can do a representative search.

[Raphexon]

I'm not sure if you ever want mailboxes where a 32 bit bitboard would suffice. (Checkers)

But mailboxes certainly seems like the more attractive option for bigger board sizes.

[Kotlov]

It measures the speed with which you can do a representative search.

In other words, it not chess engine?

UPD
Ok, I see http://hgm.nubati.net/mailbox7.c
It looks like a chess program.

What hardware did you use for 5,9M nps?

[Kotlov]

UPD2
Why do you count the nodes twice?

Code: Select all

    if(!todo && gap > 0) {                             // opponent has no non-futile move
      u-> parentAlpha = -u->alpha;                     // fail-high score (-u->alpha is parent's beta)
      attackers -= SZ; presence[stm] = u->oldPresence; // undo updates
      u->searched++; nodeCnt++; qsCnt += (u->depth <= 0);
      return 1;                                        // and abort move ('overkill pruning')
    }

[hgm]

It measures the speed with which you can do a representative search.

In other words, it not chess engine?

UPD
Ok, I see http://hgm.nubati.net/mailbox7.c
It looks like a chess program.

What hardware did you use for 5,9M nps?

Indeed, it is not an engine. Just a bare alpha-beta search of a hard-coded test position. I suppose it could serve as a basis for an engine. It doesn't implement all chess rules, though; details that are supposed to have no impact on speed of move generation (promotions, e.p., castling) were not implemented.

I am not sure where the 5.9Mnps was achieved. The latest state was 8.0Mnps, on a 2.2GHz i3 CPU. Also not sure if I uploaded the exact source of that version; I do not consider this final, but I had to take a break from the project to tend to other matters.

UPD2
Why do you count the nodes twice?

Code: Select all

    if(!todo && gap > 0) {                             // opponent has no non-futile move
      u-> parentAlpha = -u->alpha;                     // fail-high score (-u->alpha is parent's beta)
      attackers -= SZ; presence[stm] = u->oldPresence; // undo updates
      u->searched++; nodeCnt++; qsCnt += (u->depth <= 0);
      return 1;                                        // and abort move ('overkill pruning')
    }

You mean the u->searched++; and the nodeCnt++;? The latter is the (global) total node count for calculatin the nps. u->searched is local to the node, and is used at the end of the node to determine whether that node was a leaf or not. For the purpose of counting the number of leaf nodes.

[Kotlov]

You mean the u->searched++; and the nodeCnt++;? The latter is the (global) total node count for calculatin the nps. u->searched is local to the node, and is used at the end of the node to determine whether that node was a leaf or not. For the purpose of counting the number of leaf nodes.

No, I mean only nodeCnt.

Code: Select all

int Search(UndoInfo *u) // pass all parameters in a struct
{
  UndoInfo undo;
  int pvMove;
  int curMove, noncapts = 10000;
  undo.pv = pvPtr;
  undo.first = msp;
  nodeCnt++;

 ......................


if(PATH) printf("       new=%08x existing=%08x worse=%08x\n       undetected=%08x todo=%08x\n", u->newThreats, u->existingThreats, worseThreats, u->undetectedThreats, todo);
    if(!todo && gap > 0) {                             // opponent has no non-futile move
      u-> parentAlpha = -u->alpha;                     // fail-high score (-u->alpha is parent's beta)
      attackers -= SZ; presence[stm] = u->oldPresence; // undo updates
      u->searched++; nodeCnt++; qsCnt += (u->depth <= 0);
      return 1;                                        // and abort move ('overkill pruning')
   
............................

}

two increment in one node.