Efficient Generation of Move Info Bitboards

[oriyonay]

Hi there - this is my first post on here, this is exciting!!
I've been developing my chess engine for a few weeks now, and it performs 60% as fast as Stockfish on perft tests (about 43 mn/s on my laptop). For a while I've noticed an opportunity to speed up my move generation by eliminating redundancies in calculating move info bitboards (mainly can/can't capture bitboards). I am currently doing the following:

Code: Select all

if (turn == WHITE) {
    CANT_CAPTURE = bitboard[WP] | bitboard[WN] | bitboard[WB] | bitboard[WR] |
                   bitboard[WQ] | bitboard[WK] | bitboard[BK];
    CAN_CAPTURE  = bitboard[BP] | bitboard[BN] | bitboard[BB] | bitboard[BR] |
                   bitboard[BQ];
  }
  else {
    CANT_CAPTURE = bitboard[BP] | bitboard[BN] | bitboard[BB] | bitboard[BR] |
                   bitboard[BQ] | bitboard[BK] | bitboard[WK];
    CAN_CAPTURE  = bitboard[WP] | bitboard[WN] | bitboard[WB] | bitboard[WR] |
                   bitboard[WQ];
 }
 

but it seems almost obvious that there must be a better way to do this. I've tried the following procedure:
1) calculate kings bitboard (bitboard[WK] | bitboard[BK]) and the moved bitboard ((1L << from) | (1L << to))
2) swap the current CAN_CAPTURE and CANT_CAPTURE bitboards
3) XOR the kings bitboard into both CAN_CAPTURE and CANT_CAPTURE
4) XOR the moved bitboard into CANT_CAPTURE

I've thought that perhaps this was failing only on special moves, but this approach doesn't work even when I use the original (long) way of calculating these bitboards only on special moves. What could be wrong?

Also - how good is 60% perft speed from SF and qperft?

Have a wonderful rest of your day!!
- Ori

[Edsel Apostol]

If you don't do any other tricks like bulk counting then that's fast.

[AndrewGrant]

Hi there - this is my first post on here, this is exciting!!
I've been developing my chess engine for a few weeks now, and it performs 60% as fast as Stockfish on perft tests (about 43 mn/s on my laptop). For a while I've noticed an opportunity to speed up my move generation by eliminating redundancies in calculating move info bitboards (mainly can/can't capture bitboards). I am currently doing the following:

Code: Select all

if (turn == WHITE) {
    CANT_CAPTURE = bitboard[WP] | bitboard[WN] | bitboard[WB] | bitboard[WR] |
                   bitboard[WQ] | bitboard[WK] | bitboard[BK];
    CAN_CAPTURE  = bitboard[BP] | bitboard[BN] | bitboard[BB] | bitboard[BR] |
                   bitboard[BQ];
  }
  else {
    CANT_CAPTURE = bitboard[BP] | bitboard[BN] | bitboard[BB] | bitboard[BR] |
                   bitboard[BQ] | bitboard[BK] | bitboard[WK];
    CAN_CAPTURE  = bitboard[WP] | bitboard[WN] | bitboard[WB] | bitboard[WR] |
                   bitboard[WQ];
 }
 

but it seems almost obvious that there must be a better way to do this. I've tried the following procedure:
1) calculate kings bitboard (bitboard[WK] | bitboard[BK]) and the moved bitboard ((1L << from) | (1L << to))
2) swap the current CAN_CAPTURE and CANT_CAPTURE bitboards
3) XOR the kings bitboard into both CAN_CAPTURE and CANT_CAPTURE
4) XOR the moved bitboard into CANT_CAPTURE

I've thought that perhaps this was failing only on special moves, but this approach doesn't work even when I use the original (long) way of calculating these bitboards only on special moves. What could be wrong?

Also - how good is 60% perft speed from SF and qperft?

Have a wonderful rest of your day!!
- Ori

So you have bitboards for WP, BP, WN, .... WK, BK. Its also common to have a bitboard for W, and B.
ie, at all times you have a bitboard W = WP | WN | ... WK. Updating that is cheap, and saves you this annoyance.
What is faster for pure PERFT? I cannot say. Bitboard design decisions depend on many things.

Few methods:
1. Quad bitboards. you can actually store all info needed in just 4x (64bit) bitboards.
2. One bitboard for each piece-colour, like you have. 12x (64bit) bitboards.
3. One bitboard for each piece, one for each colour. 8x (64bit) bitboards.
Advantages and disadvantages to all of them.

Another question for you. How do you determine the type of the piece on a given square?
What would this function look like for you:

Code: Select all

PieceType getPieceTypeAtSquare(int sq) {
    ...
}

[hgm]

I've been developing my chess engine for a few weeks now, and it performs 60% as fast as Stockfish on perft tests (about 43 mn/s on my laptop).

Just for my understanding of this number: is this nodes/sec or moves/sec? On my laptop qperft (a mailbox program) takes 1.297 sec for perft(6) (119M nodes), which would be 92M moves/sec.

[oriyonay]

So you have bitboards for WP, BP, WN, .... WK, BK. Its also common to have a bitboard for W, and B.
ie, at all times you have a bitboard W = WP | WN | ... WK. Updating that is cheap, and saves you this annoyance.
What is faster for pure PERFT? I cannot say. Bitboard design decisions depend on many things.

Few methods:
1. Quad bitboards. you can actually store all info needed in just 4x (64bit) bitboards.
2. One bitboard for each piece-colour, like you have. 12x (64bit) bitboards.
3. One bitboard for each piece, one for each colour. 8x (64bit) bitboards.
Advantages and disadvantages to all of them.

Another question for you. How do you determine the type of the piece on a given square?
What would this function look like for you:

Code: Select all

PieceType getPieceTypeAtSquare(int sq) {
    ...
}

Hey Andy! Thank you so much for your reply - I'm a big fan of Ethereal!
Assuming I have such W and B bitboards (which does sound like a very smart idea), then I can just use those instead - or derive CAN_CAPTURE and CANT_CAPTURE directly from them in less time? That sounds like what I'm going to do

As for determining the piece type on a given square - I'm also using a piece list for board representation, so this would simply be an array lookup

[oriyonay]

If you don't do any other tricks like bulk counting then that's fast.

I am doing bulk counting, but that's about it for tricks

[oriyonay]

Just for my understanding of this number: is this nodes/sec or moves/sec? On my laptop qperft (a mailbox program) takes 1.297 sec for perft(6) (119M nodes), which would be 92M moves/sec.

Hi - thank you for your reply This is moves/sec - I'm doing bulk counting.

[hgm]

As for determining the piece type on a given square - I'm also using a piece list for board representation, so this would simply be an array lookup

Note that this is not a piece list, but a mailbox board. In a piece list you can look up the location of a given piece, on a board the piece (or piece type) on a given square.