Bitboard board representation

[eligolf]

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.

[Harald]

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
https://www.youtube.com/playlist?list=P ... wfiWNI76Cs

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?

Your board (or position) is just the combination of your
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); }
    }

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?

For a pinned piece detection as well as for an is_in_check detection calculate the possible slider attacks
(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.

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?

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.
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.

[maksimKorzh]

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
https://www.youtube.com/playlist?list=P ... wfiWNI76Cs

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?

Your board (or position) is just the combination of your
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); }
    }

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?

For a pinned piece detection as well as for an is_in_check detection calculate the possible slider attacks
(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.

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?

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.
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.

Thanks for suggesting my series, Harald)

[eligolf]

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.

[Sven]

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.

[Pio]

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.

I guess you menat AND for the two first lines

[Sven]

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.

I guess you menat AND for the two first lines

Yes, indeed I edited my post, thanks.

[Harald]

Sven wrote:

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.

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.

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.

[Sven]

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.