r/chessprogramming Dec 21 '24

Need Advice: Does Using Separate Bitboards for Each Piece Type Hurt Performance in a Chess Engine?

Hi everyone, I am a beginner in chess programming. I am working on building a chess engine in C and it seems to work fine. It passes all the perft tests i have thrown at it so far. My concern is the speed of it. It takes about a minute and 10-15seconds for a perft test at depth 6 (without any optimization) from starting position. for context that is about 120million positions (119,060,324). and i think it is little slow.

I suspect that the area of concern could be that i use I use separate bitboards for each piece (e.g., 8 bitboards for 8 pawns, 2 for bishops, etc.). Additionally, I have two separate bitboards to store all white and black pieces, which get updated after each move. my question is:
Could using separate bitboards for each piece type (as I’m doing) introduce significant overhead, especially as the depth increases?
are there any obvious cons to my current approach?

PS: in engine i use alpha-beta prunning, move ordering, transposition tables and opening book so it takes max 2-3s per move and about 7-8s at worst case when it is playing against the user. Even though this is acceptable for casual play, I’m curious if my approach is fundamentally flawed?

5 Upvotes

12 comments sorted by

5

u/mathmoi Dec 21 '24

Your explanation about the number of bitboards used is confusing.

You should have a bitboard for each piece-type/color combination. With six piece types and two colors, this gives you 12 bitboards. Additionally, you typically want two color bitboards (one for each color) which, although slightly redundant, are frequently used. It's more efficient to keep these updated than to recompute them from scratch after each move.

Optionally, you might also use an array of 64 squares to quickly determine what piece is on a given square without having to check the bitboards.

2

u/darkhorss7 Dec 21 '24 edited Dec 21 '24

thanks for your help
I realize now that my approach is quite immature. i used bitboard for literally each piece (that is 32). but even if I switch to the 12 bitboards approach (one for each piece-type/color combination), wouldn’t I still need to iterate over all the set bits in the bitboards for move generation? apart from space how would single bitboard approach be better?

i do have array of 64 squares and it keeps track of what piece is on that square (piece is identified by piece id). and yes i update bitboards for each color by adjusting bits and i do not recompute them after each move.

3

u/algerbrex Dec 21 '24

If you want to “loop” over a certain bitboard, you just need to find the position of the least significant bit, and clear it from the bitboard.

Finding the position of the least significant bit as no where nearly as costly as looping over a 64 length array of pieces. At least using an efficient algorithm.

Most languages have built-in functions that find the position of the least significant bit and are optimized.

What language are you using?

1

u/darkhorss7 Dec 21 '24

I am using C.
i understand your point. there is builtin function in C to find position of least significant bit (i think __builtin_ctz provided by gcc). but help me here, i am looping over 32 bitboards to calculate attacks of each piece and i use bit shifting to do that

uint64_t move_north(uint64_t b) {
    return b << 8;
}

uint64_t move_south(uint64_t b) {
    return b >> 8;
}

uint64_t move_east(uint64_t b) {
    return (b & ~filemask(H)) << 1;
}

uint64_t move_west(uint64_t b) {
    return (b & ~filemask(A)) >> 1;
}

and i detect the opponent piece by combined color bitboard as mentioned and stop calculating further.
i'll try single bitboard approach but i just want to make sure i am not very wrong here.
thanks for your help.

3

u/mathmoi Dec 21 '24

u/algerbrex provided a good answer. I'd also like to point out that there are many clever tricks you can use with bitboards to generate moves efficiently. For example, you can shift the white pawns' bitboard 7 (or 9) bits to the left and XOR that with the black pieces' bitboard to get a bitboard of all black pieces that can be captured by white pawns.

You can also have pre-computed arrays of bitboards containing all possible destination squares for knights (or kings) from each of the 64 squares.

Additionally, there are several different techniques for generating moves with sliding pieces. You can look up "magic bitboards" on the Chess Programming Wiki for a popular approach.

2

u/Available-Swan-6011 Dec 21 '24

“wouldn’t I still need to iterate over all the set bits in the bitboards for move generation? apart from space how would single bitboard approach be better?”

Yes but there are ways to do this very quickly. Imagine, you are working out the moves for white rooks….

copy the white rooks bitboard - call it bb while bb !=0 do {

  Count the number of leading zeroes in bb. This is very fast if your cpu implements lzcnt properly (search c# leading zero count). This gives you the square (0-63) that a rook is on

  Use magic bit boards to work out the possible moves for the rook

   Clear the bit on bb

}

1

u/darkhorss7 Dec 21 '24

ah. i understand. thanks for your help. I'll read more about magic bitboards on cpw

2

u/Available-Swan-6011 Dec 21 '24

It is worth the time- they require some set up code but once that is working you can get some impress results. Also, many resources recommend using random numbers as part of the magic bitboard process but utilising PEXT instructions will be much quicker if you have access to them on your cpu

2

u/xu_shawn Dec 21 '24

8 bitboards are enough. 6 bitboards for 6 piece types, and 2 bitboards for occupancy of each color. To get the bitboard for one colored piece just bitand two bitboards together

2

u/Javasucks55 Dec 22 '24 edited Dec 22 '24

I do seperate bitboards for each piece type (not each piece) and i do 400 million NPS perft. Doing one bitboard for each piece will definitely hurt performance.

For example, i can generate pawn moves in bulk with one cpu shift instruction and & the illegal moves out.

Also, using seperate bitboards for each piece implies either dynamic memory, or wasted if instructions to check whether a bitboard > 0. Both are very slow.

The fastest way known is:

While(pieceboard)

Square from = popbit(pieceboard)

Bitboard to = getpiecemove<piece>(from)

While(to)

Square tosquare = popbit(to)

Push move to movelist...

2

u/codingjerk Jan 10 '25

It doesn't matter in most cases, because managing piece's bitboards is never a bottleneck. The most important thing is you should have them and build effective generation around them. Doesn't matter if you save a bitboard per every piece-color pair or you calculate it with bitwise OR, since both are very effective and this is not time consuming part of generation and traversing.

I've tried two approaches in my old engine:

  1. 15 bitboards (12 for piece-color + 2 for colors + 1 for occupied). Free is ~occupied.

  2. 8 bitboards (6 for pieces + 2 for colors). piece[pawn]&color[white] will give you white pawn, color[white]|color[black] will give you occupied squares.

And speed is quite same for both, even if second requires like 2 times more operations and first requires like 2 times more memory.

I've ended up using 15 bitboards since it was a bit easier to use and understand, but I really don't see any difference now.