Hi,
I have now tried to re-write my engine from using a 10x12 board representation to a bitboard one. Had to start from scratch due the massive amount of work to tweak the existing code. The progress so far:
* Created pre-computed tables for file, rank, masks, king moves, knight moves, pawn moves, and the Kindergarten method for sliding pieces as described here: https://www.chessprogramming.org/Effici ... ce_Attacks.
* Created move generation functions for all pieces which I hope is okay. They don't handle castling or enpassant yet though.
* Created a chessboard class with a 2x6 array bitboard for the pieces, 1x2 array bitboard for each colors pieces, 1x1 array bitboard for all pieces and a 1x1 array bitboard for color to move (a 0 or 1).
* Ability to generate a move object with (from_square, to_square, promotion), or add more attributes as well if needed.
Now I am having a hard time figuring out how to practically use this representation to create a game. Speed is important, that is the only reason I changed to bitboards at this stage. Here are some things I can't figure out at the moment:
1. How do I represent the actual board? In my old engine I used a dict where each square had a piece on it like this: {0: 'wR', 1: 'wN'..... 63: 'bR'}. Then I could easily loop through the board dict and get the possible moves for each piece and combine to a possible move list. Now how do I loop through the 16 bitboards to get what piece is located where in the most efficient way?
2. Right now the move generator is pseudo legal since I couldn't figure out how to do a pinned piece check with this representation. I will then have to check whether each move result in check and if so don't use it. Is this a common way to go or will this be significantly slower than trying to figure out pinned pieces in the move gen?
3. How would you handle e.p. and castling? Do you have a flag for when these are possible and then add them in the pseudo move generator? Or are these special moves handled somewhere else?
4. Is my move object concept the way to go? I have read about having it as a bit string instead with all info encoded (from, to, move_type etc). Is it very complicated to obtain the information from such string?
Sorry if this is obvious to some of you. To me it is all still very confusing but I hope to fully understand it soon I have read a lot on chessprogramming.org and also a lot here in this forum which helped a lot in the progress so far. Looking at code from e.g. Stockfish helped a little but is very confusing at times too.
Bitboard board representation
Moderators: hgm, Rebel, chrisw
-
- Posts: 114
- Joined: Sat Nov 14, 2020 12:49 pm
- Full name: Elias Nilsson
-
- Posts: 318
- Joined: Thu Mar 09, 2006 1:07 am
Re: Bitboard board representation
It looks like you use Python. That's not a problem but you may have to translate some syntax from C/C++ to Python.
Have a look at the youtube series
Bitboard CHESS ENGINE in C
piece bitboards for both colors,
two combined occupied bitboards for both colors,
the side to move,
castling flags,
en passant square,
fifty move counter,
a pieces on board array (list in Python, size 64 squares),
and may be more (like king position squares for both colors).
You can put this together in a class or have it as global variables.
You can fill the pieces on board array with integers or characters like rnbqkbnr, pppppppp, ........, ..., PPPPPPPP, RNBQKBNR
or like -4, -2, -3, -5, -6, -3, -2, -4, -1, -1, -1, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, ..., 1, 1, 1, 1, 1, 1, 1, 1, 4, 2, 3, 5, 6, 3, 2 ,4
I call the type of the entry PieceType.
If you know the number of the square you can immediately look up the piece and color (positive or negative integers).
To update this board is easy and fast and can be done parallel to all bitboard updates.
Otherwise you have to write a lookup funktion that goes through all the piece bitboards un til it finds a set bit on a square.
Example in C++:
(using the kindergarten method or a magic multiplication) from a virtual queen on the pinned piece or king square.
You get an attacked bitboard and can AND it with occupied bitboards or opponent occupied or piece bitboards.
This is just a filter for various questions that can be asked about the situation. If you need the individual
squares and pieces of the result see the example above.
Do not forget to clear the ep square with the next move when you update your position.
Castling is best handled with four flag bits in one integer value. Lets say the bits 3, 2, 1, 0 stand for KQkq castling.
White kingside, white queenside, black kingside, black queenside.
(............KQkq in a 16 bit integer)
These flags start as the value 15 in the opening position (15 = 8+4+2+1). When one possibility goes away
by a rook/king move, by a rook capture or by castling then clear that bit.
I assume you know how to set or clear individual bits using binary operators.
The move generator checks if the bits are still set.
Have a look at the youtube series
Bitboard CHESS ENGINE in C
Your board (or position) is just the combination of your1. How do I represent the actual board? In my old engine I used a dict where each square had a piece on it like this: {0: 'wR', 1: 'wN'..... 63: 'bR'}. Then I could easily loop through the board dict and get the possible moves for each piece and combine to a possible move list. Now how do I loop through the 16 bitboards to get what piece is located where in the most efficient way?
piece bitboards for both colors,
two combined occupied bitboards for both colors,
the side to move,
castling flags,
en passant square,
fifty move counter,
a pieces on board array (list in Python, size 64 squares),
and may be more (like king position squares for both colors).
You can put this together in a class or have it as global variables.
You can fill the pieces on board array with integers or characters like rnbqkbnr, pppppppp, ........, ..., PPPPPPPP, RNBQKBNR
or like -4, -2, -3, -5, -6, -3, -2, -4, -1, -1, -1, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, ..., 1, 1, 1, 1, 1, 1, 1, 1, 4, 2, 3, 5, 6, 3, 2 ,4
I call the type of the entry PieceType.
If you know the number of the square you can immediately look up the piece and color (positive or negative integers).
To update this board is easy and fast and can be done parallel to all bitboard updates.
Otherwise you have to write a lookup funktion that goes through all the piece bitboards un til it finds a set bit on a square.
Example in C++:
Code: Select all
// BB is just the bitboard integer type, unsigned long long in C/C++
BB occupied = pos.occupied_[White] | pos.occupied_[Black]; // All pawns, pieces and king combined
BB occ = occupied;
while (occ)
{
SquareType sq = msb_nr(occ); // SquareType is just an integer. msb_nr() gets the most significant bit number.
// Lookup msb_nr() in Google or ask again.
BB ff = BBB(sq); // BBB(sq) sets one bit in a bitboard. It means (1 << (sq)).
// In C/C++ take care of the unsigned long long type.
PieceType piece = pos.board_[sq]; // This is the piece on board lookup
switch (piece)
{
case NoPiece: // I defined names for the pieces
break;
case WPawn: // White pawn
{
...
}
...
occ = clear_bit(occ, sq); // This removes the one bit from the bitboard.
// BB clear_bit( BB bb, SquareType sq ) { return bb & ~BBB(sq); }
}
For a pinned piece detection as well as for an is_in_check detection calculate the possible slider attacks2. Right now the move generator is pseudo legal since I couldn't figure out how to do a pinned piece check with this representation. I will then have to check whether each move result in check and if so don't use it. Is this a common way to go or will this be significantly slower than trying to figure out pinned pieces in the move gen?
(using the kindergarten method or a magic multiplication) from a virtual queen on the pinned piece or king square.
You get an attacked bitboard and can AND it with occupied bitboards or opponent occupied or piece bitboards.
This is just a filter for various questions that can be asked about the situation. If you need the individual
squares and pieces of the result see the example above.
En passant is just a square number that is either -1 (NoSquare) or the square that the double pawn move just passed on its way.3. How would you handle e.p. and castling? Do you have a flag for when these are possible and then add them in the pseudo move generator? Or are these special moves handled somewhere else?
Do not forget to clear the ep square with the next move when you update your position.
Castling is best handled with four flag bits in one integer value. Lets say the bits 3, 2, 1, 0 stand for KQkq castling.
White kingside, white queenside, black kingside, black queenside.
(............KQkq in a 16 bit integer)
These flags start as the value 15 in the opening position (15 = 8+4+2+1). When one possibility goes away
by a rook/king move, by a rook capture or by castling then clear that bit.
I assume you know how to set or clear individual bits using binary operators.
The move generator checks if the bits are still set.
-
- Posts: 771
- Joined: Sat Sep 08, 2018 5:37 pm
- Location: Ukraine
- Full name: Maksim Korzh
Re: Bitboard board representation
Thanks for suggesting my series, Harald)Harald wrote: ↑Thu Dec 17, 2020 10:03 am It looks like you use Python. That's not a problem but you may have to translate some syntax from C/C++ to Python.
Have a look at the youtube series
Bitboard CHESS ENGINE in C
Your board (or position) is just the combination of your1. How do I represent the actual board? In my old engine I used a dict where each square had a piece on it like this: {0: 'wR', 1: 'wN'..... 63: 'bR'}. Then I could easily loop through the board dict and get the possible moves for each piece and combine to a possible move list. Now how do I loop through the 16 bitboards to get what piece is located where in the most efficient way?
piece bitboards for both colors,
two combined occupied bitboards for both colors,
the side to move,
castling flags,
en passant square,
fifty move counter,
a pieces on board array (list in Python, size 64 squares),
and may be more (like king position squares for both colors).
You can put this together in a class or have it as global variables.
You can fill the pieces on board array with integers or characters like rnbqkbnr, pppppppp, ........, ..., PPPPPPPP, RNBQKBNR
or like -4, -2, -3, -5, -6, -3, -2, -4, -1, -1, -1, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, ..., 1, 1, 1, 1, 1, 1, 1, 1, 4, 2, 3, 5, 6, 3, 2 ,4
I call the type of the entry PieceType.
If you know the number of the square you can immediately look up the piece and color (positive or negative integers).
To update this board is easy and fast and can be done parallel to all bitboard updates.
Otherwise you have to write a lookup funktion that goes through all the piece bitboards un til it finds a set bit on a square.
Example in C++:Code: Select all
// BB is just the bitboard integer type, unsigned long long in C/C++ BB occupied = pos.occupied_[White] | pos.occupied_[Black]; // All pawns, pieces and king combined BB occ = occupied; while (occ) { SquareType sq = msb_nr(occ); // SquareType is just an integer. msb_nr() gets the most significant bit number. // Lookup msb_nr() in Google or ask again. BB ff = BBB(sq); // BBB(sq) sets one bit in a bitboard. It means (1 << (sq)). // In C/C++ take care of the unsigned long long type. PieceType piece = pos.board_[sq]; // This is the piece on board lookup switch (piece) { case NoPiece: // I defined names for the pieces break; case WPawn: // White pawn { ... } ... occ = clear_bit(occ, sq); // This removes the one bit from the bitboard. // BB clear_bit( BB bb, SquareType sq ) { return bb & ~BBB(sq); } }
For a pinned piece detection as well as for an is_in_check detection calculate the possible slider attacks2. Right now the move generator is pseudo legal since I couldn't figure out how to do a pinned piece check with this representation. I will then have to check whether each move result in check and if so don't use it. Is this a common way to go or will this be significantly slower than trying to figure out pinned pieces in the move gen?
(using the kindergarten method or a magic multiplication) from a virtual queen on the pinned piece or king square.
You get an attacked bitboard and can AND it with occupied bitboards or opponent occupied or piece bitboards.
This is just a filter for various questions that can be asked about the situation. If you need the individual
squares and pieces of the result see the example above.
En passant is just a square number that is either -1 (NoSquare) or the square that the double pawn move just passed on its way.3. How would you handle e.p. and castling? Do you have a flag for when these are possible and then add them in the pseudo move generator? Or are these special moves handled somewhere else?
Do not forget to clear the ep square with the next move when you update your position.
Castling is best handled with four flag bits in one integer value. Lets say the bits 3, 2, 1, 0 stand for KQkq castling.
White kingside, white queenside, black kingside, black queenside.
(............KQkq in a 16 bit integer)
These flags start as the value 15 in the opening position (15 = 8+4+2+1). When one possibility goes away
by a rook/king move, by a rook capture or by castling then clear that bit.
I assume you know how to set or clear individual bits using binary operators.
The move generator checks if the bits are still set.
Didactic chess engines:
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
-
- Posts: 114
- Joined: Sat Nov 14, 2020 12:49 pm
- Full name: Elias Nilsson
Re: Bitboard board representation
Thank you super much for the detailed answer Harald, you helped a lot so far! I will try and think some more about the representation and how to fiddle with the bits.
Also thanks Maksim for the series, I looked at 2 episodes so far and it looks very promising! Even though it is not in Python I can use the concepts with some modifications.
Also thanks Maksim for the series, I looked at 2 episodes so far and it looks very promising! Even though it is not in Python I can use the concepts with some modifications.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Bitboard board representation
Maintaining 2x6 piece bitboards, 2 color bitboards and one "all pieces" bitboard involves some redundancy. If you are looking for speed then you might try to avoid storing more information than needed, and let some information be calculated on the fly.
Some examples:
bbWhitePawns = bbPawns AND bbWhite
bbBlackKnights = bbKnights AND bbBlack
bbAllPieces = bbWhite OR bbBlack
bbEmpty = NOT(bbAllPieces)
That means, you could use only 1x6 piece bitboards (bbPawns, bbKnights, ..), 2 color bitboards (bbWhite, bbBlack) and also no "all pieces" bitboard.
Usually doing less memory operations is faster than storing redundant data to avoid recalculation. Of course that needs to be checked for your individual case.
Some examples:
bbWhitePawns = bbPawns AND bbWhite
bbBlackKnights = bbKnights AND bbBlack
bbAllPieces = bbWhite OR bbBlack
bbEmpty = NOT(bbAllPieces)
That means, you could use only 1x6 piece bitboards (bbPawns, bbKnights, ..), 2 color bitboards (bbWhite, bbBlack) and also no "all pieces" bitboard.
Usually doing less memory operations is faster than storing redundant data to avoid recalculation. Of course that needs to be checked for your individual case.
Last edited by Sven on Thu Dec 17, 2020 8:24 pm, edited 1 time in total.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)
-
- Posts: 334
- Joined: Sat Feb 25, 2012 10:42 pm
- Location: Stockholm
Re: Bitboard board representation
I guess you menat AND for the two first linesSven wrote: ↑Thu Dec 17, 2020 8:14 pm Maintaining 2x6 piece bitboards, 2 color bitboards and one "all pieces" bitboard involves some redundancy. If you are looking for speed then you might try to avoid storing more information than needed, and let some information be calculated on the fly.
Some examples:
bbWhitePawns = bbPawns OR bbWhite
bbBlackKnights = bbKnights OR bbBlack
bbAllPieces = bbWhite OR bbBlack
bbEmpty = NOT(bbAllPieces)
That means, you could use only 1x6 piece bitboards (bbPawns, bbKnights, ..), 2 color bitboards (bbWhite, bbBlack) and also no "all pieces" bitboard.
Usually doing less memory operations is faster than storing redundant data to avoid recalculation. Of course that needs to be checked for your individual case.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Bitboard board representation
Yes, indeed I edited my post, thanks.Pio wrote: ↑Thu Dec 17, 2020 8:19 pmI guess you menat AND for the two first linesSven wrote: ↑Thu Dec 17, 2020 8:14 pm Maintaining 2x6 piece bitboards, 2 color bitboards and one "all pieces" bitboard involves some redundancy. If you are looking for speed then you might try to avoid storing more information than needed, and let some information be calculated on the fly.
Some examples:
bbWhitePawns = bbPawns OR bbWhite
bbBlackKnights = bbKnights OR bbBlack
bbAllPieces = bbWhite OR bbBlack
bbEmpty = NOT(bbAllPieces)
That means, you could use only 1x6 piece bitboards (bbPawns, bbKnights, ..), 2 color bitboards (bbWhite, bbBlack) and also no "all pieces" bitboard.
Usually doing less memory operations is faster than storing redundant data to avoid recalculation. Of course that needs to be checked for your individual case.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)
-
- Posts: 318
- Joined: Thu Mar 09, 2006 1:07 am
Re: Bitboard board representation
Sven wrote:
But I doubt that eligolf is really interested in these details now. And I doubt that these different methods make more than a very tiny difference in performance of the chess engine.
Also he uses Python and that means there is an extra layer of an interpreter with or without the help of a just in time compiler support. That is another whole story of micro performance tweaks.
My advice is: just use the method and position storage that you like most, that feels natural to you, that you can easily understand and explain and that is most comfortable to write and use.
Yes. It depends on the number of times a stored value or an expression is used, the CPU registers, L1, L2, L3 caches, cache lines, used memory bytes and how often they are copied and so on. That is in C/C++ where you have some control over these things and may be you even have a profiler.Maintaining 2x6 piece bitboards, 2 color bitboards and one "all pieces" bitboard involves some redundancy. If you are looking for speed then you might try to avoid storing more information than needed, and let some information be calculated on the fly.
...
Usually doing less memory operations is faster than storing redundant data to avoid recalculation. Of course that needs to be checked for your individual case.
But I doubt that eligolf is really interested in these details now. And I doubt that these different methods make more than a very tiny difference in performance of the chess engine.
Also he uses Python and that means there is an extra layer of an interpreter with or without the help of a just in time compiler support. That is another whole story of micro performance tweaks.
My advice is: just use the method and position storage that you like most, that feels natural to you, that you can easily understand and explain and that is most comfortable to write and use.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Bitboard board representation
You are right in general but your advice somehow contradicts to the OP's own statement "speed is important". Furthermore I doubt that saving time by doing less memory accesses is not relevant in a Python program. The saving may be smaller due to the interpreter overhead but it should still be measurable.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)