Move generation for bitboards

[lithander]

Should I try to make the move generation and make/unmake move functions faster than this before continuing with next phases of incorporating the engine itself? Or is this good enough in C# to continue?

My "I don't really care about the speed, I just want to learn alorithms of chess programming" engine does ~4M nps on perft with a mailbox board representation. (array with 64 slots of type piece)
My bitboard engine where I really do care about speed does 60-70M nps in perft with a pseudo-legal, bitboard based move generator.

Both engines are in C#. So I'd say try and see if you can't squeeze some extra performance out of it or at least try and find out why your perft is currently so much slower than it could be.

[eligolf]

Should I try to make the move generation and make/unmake move functions faster than this before continuing with next phases of incorporating the engine itself? Or is this good enough in C# to continue?

My "I don't really care about the speed, I just want to learn alorithms of chess programming" engine does ~4M nps on perft with a mailbox board representation. (array with 64 slots of type piece)
My bitboard engine where I really do care about speed does 60-70M nps in perft with a pseudo-legal, bitboard based move generator.

Both engines are in C#. So I'd say try and see if you can't squeeze some extra performance out of it or at least try and find out why your perft is currently so much slower than it could be.

That is great, 4 M nps sounds amazing with that approach.
I am using pseudo legal moves and in the end of the MakeMove function I check if the move left king in check, and if it did I UnMake the move. Like this:

Code: Select all

public bool MakeMove(ulong move)
        {
            // Extract variables from move
            int fromSquare = (int)Move.GetFromSquare(move);
            int toSquare = (int)Move.GetToSquare(move);
            int pieceMoved = (int)Move.GetPieceMoved(move);
            int moveFlag = (int)Move.GetMoveFlag(move);

            int pieceType = PieceTable[fromSquare];
            int enemyColor = Color.Invert(ColorToMove);

            // Increase counters
            if (ColorToMove == Color.White) MovesCount++;

            // Add variables to track lists
            Castlings.Add(Castling);
            Hashes.Add(Hash);
            PawnHashes.Add(PawnHash);
            EnPassants.Add(EnPassant);
            IrreversibleMovesCounts.Add(IrreversibleMovesCount);

            // Reset irreversible moves count if it is such a move
            if (pieceType == Piece.Pawn || Move.IsCapture(moveFlag) || Move.IsCastling(moveFlag))
            {
                IrreversibleMovesCount = 0;
            }
            else IrreversibleMovesCount++;

            // Check if enpassant is possible
            if (EnPassant != GameConstants.EmptyBitboard)
            {
                int enPassantRank = BitOperations.BitScan(EnPassant) % 8; // -1 ??? ;
                EnPassant = GameConstants.EmptyBitboard;
            }

            // -----    Check for different move types    ------

            // Quiet moves that are not double pushes
            if (Move.IsSinglePush(moveFlag))
            {
                MovePiece(ColorToMove, pieceType, fromSquare, toSquare);
            }
            // Double pawn pushes
            else if (Move.IsDoublePush(moveFlag))
            {
                MovePiece(ColorToMove, pieceType, fromSquare, toSquare);

                // Enable enpassant
                ulong epSquare = ColorToMove == Color.White ? 1ul << toSquare + 8 : 1ul << fromSquare + 8;
                EnPassant |= epSquare;
            }
            // Enpassant moves
            else if (Move.IsEnPassant(moveFlag))
            {
                // Find enemy pawn (which is not on the toSquare)
                int enemyPieceSquare = ColorToMove == Color.White ? (byte)(toSquare + 8) : (byte)(toSquare - 8);
                int capturedPiece = PieceTable[enemyPieceSquare];
                CapturedPieces.Add(capturedPiece);

                // Move own pawn and remove enemy pawn
                MovePiece(ColorToMove, pieceType, fromSquare, toSquare);
                RemovePiece(enemyColor, capturedPiece, enemyPieceSquare);
            }
            // Capture moves
            else if (Move.IsCapture(moveFlag))
            {
                // Find the captured piece and remove it from the board
                int capturedPiece = PieceTable[toSquare];
                RemovePiece(enemyColor, capturedPiece, toSquare);

                // Check if captured piece is a rook, if so change castling rights accordingly
                if (capturedPiece == Piece.Rook)
                {
                    // Black queen side castling
                    if (toSquare == 0)
                    {
                        Castling &= ~Castling.BlackQueenSide;
                    }
                    // Black king side castling
                    else if (toSquare == 7)
                    {
                        Castling &= ~Castling.BlackKingSide;
                    }
                    // White queen side castling
                    else if (toSquare == 56)
                    {
                        Castling &= ~Castling.WhiteQueenSide;
                    }
                    // White king side castling
                    else if (toSquare == 63)
                    {
                        Castling &= ~Castling.WhiteKingSide;
                    }
                }

                // Check for promotion captures
                if (Move.IsPromotion(moveFlag))
                {
                    // Find the piece that we should promote to
                    int promotionPiece = GetPromotionPiece(moveFlag);

                    // Remove pawn from square and add the promoted piece on 
                    RemovePiece(ColorToMove, pieceType, fromSquare);
                    AddPiece(ColorToMove, promotionPiece, toSquare);

                    // Add to list
                    PromotedPieces.Add(promotionPiece);
                }
                // If not it is a normal capture
                else
                {
                    // Move the piece as normal
                    MovePiece(ColorToMove, pieceType, fromSquare, toSquare);
                }

                // Add captured piece to list of captured pieces
                CapturedPieces.Add(capturedPiece);
            }
            // Castling moves
            else if (Move.IsCastling(moveFlag))
            {
                // White to move
                if (ColorToMove == Color.White)
                {
                    // Remove castling rights
                    Castling &= ~Castling.WhiteCastling;

                    // King side castling
                    if (Move.IsKingCastling(moveFlag))
                    {
                        // Move rook and king to the correct places
                        MovePiece(Color.White, Piece.King, 60, 62);
                        MovePiece(Color.White, Piece.Rook, 63, 61);
                    }
                    // Queen side castling
                    else
                    {
                        MovePiece(Color.White, Piece.King, 60, 58);
                        MovePiece(Color.White, Piece.Rook, 56, 59);
                    }
                }
                // Black to move
                else
                {
                    // Remove castling rights
                    Castling &= ~Castling.BlackCastling;

                    // King side castling
                    if (Move.IsKingCastling(moveFlag))
                    {
                        // Move rook and king to the correct places
                        MovePiece(Color.Black, Piece.King, 4, 6);
                        MovePiece(Color.Black, Piece.Rook, 7, 5);
                    }
                    // Queen side castling
                    else
                    {
                        MovePiece(Color.Black, Piece.King, 4, 2);
                        MovePiece(Color.Black, Piece.Rook, 0, 3);
                    }
                }                

                // Set castling is done for the color who moved
                CastlingDone[ColorToMove] = true;
            }
            // Normal promotion moves that are not captures
            else if (Move.IsPromotion(moveFlag))
            {
                // Get what piece was promoted
                int promotionPiece = GetPromotionPiece(moveFlag);

                // Remove pawn from square and add promoted piece on toSquare
                RemovePiece(ColorToMove, pieceType, fromSquare);
                AddPiece(ColorToMove, promotionPiece, toSquare);

                // Add piece to list
                PromotedPieces.Add(promotionPiece);
            }

            // Check if we moved our king without castling, if so remove castling rights for corresponding color
            if (pieceType == Piece.King && !Move.IsCastling(moveFlag))
            {
                if (ColorToMove == Color.White) Castling &= ~Castling.WhiteCastling;
                else Castling &= ~Castling.BlackCastling;
            }
            // Check if we moved rook and we have castling rights left
            else if (pieceType == Piece.Rook && Castling != 0)
            {
                if (fromSquare == 63)
                {
                    Castling &= ~Castling.WhiteKingSide;
                }
                else if (fromSquare == 56)
                {
                    Castling &= ~Castling.WhiteQueenSide;
                }
                else if (fromSquare == 7)
                {
                    Castling &= ~Castling.BlackKingSide;
                }
                else if (fromSquare == 0)
                {
                    Castling &= ~Castling.BlackQueenSide;
                }
            }

            // Change turns
            ColorToMove = enemyColor;
            int oldColorToMove = Color.Invert(ColorToMove);

            // Check if move is legal (king is not under attack after move is done)
            int ownKingSquare = BitOperations.GetLSBIndex(Pieces[oldColorToMove][Piece.King]);
            if (!IsSquareAttacked(oldColorToMove, ownKingSquare))
            {
                return true;
            }
            // If not, then unmake the move
            else
            {
                UnmakeMove(move);
                return false;
            }
        }

The structure itself is taken with great inspiration from Cosette. I know the castling checks can be faster but not sure how much difference that would make.
Is it reasonable to create legal moves instead with bitboard approach or is it standard to make the move and check for legality afterwards? Since that is such rare case and most moves will be pruned anyways.

[hgm]

So there's no other data structure other than piece lists in your suggested board representation? No mailbox array that you can index by square for example? How do you lookup the piece on a specific square, then, without looking through all of the 32 slots? (or maybe that's fast enough?)

Bitboard engines usually also maintain a mailbox board to tell them which piece type is on a given square. How else would you know from which bitboard to remove a captured piece? You would also have to loop through all bitboards to figure that out. For that mailbox board copy-make would probably not be an optimal method, though.

But my original question was: "why use bitboards rather than a list of square numbers to record where pieces of a certain type are standing?". That is not really dependent on what other (possibly redundant) data structures you might maintain to speed things up.

[lithander]

You code is very readable to my eye and I notice that you keep track of a lot of things that are not strictly necessary for perft in lists. So comparing the speed of your current implementation with one that guns to maximize perft speed is probably not fair. Maybe for all the things you do the speed is fine.

What I do know is that I didn't regret postponing the obsessing about speed for a few months to get a better understanding of the domain.

Is it reasonable to create legal moves instead with bitboard approach or is it standard to make the move and check for legality afterwards? Since that is such rare case and most moves will be pruned anyways.

I use pseudo-legal moves, too, and when I play the move and it ends up with the king in check I just go right to the next move. I found that IsSquareAttacked() is fast enough to not worry too much about it. Legal move generators will be faster in perft (where you play all the moves) but when used in an engine I don't know if it's worth it as most moves are never going to be played.

[hgm]

Piecelist is the worst board structure. No way to do rayscan and you still need to maintain neighbour tables - which you also need to copy for copy make or you have to recalculate those.
Moving a piece on a bitboard is this operation: BB ^= move. = 1 instruction
Moving a piece on a mailbox is: brd[to] = brd[from]; brd[from] = 0; = 3 lookups and 2 assignments

I never suggested the piece list would be the only data structure used to record the game state.

But you overlook that the captured piece also has to be removed (and that typically 94% of the moves are captures). So updating the bitboard stack is not a single instruction at all. The white and black bitboard also veto be updated. You also ignore the fact that in an engine you cannot afford to keep the complete game state in the CPU registers the entire time. So changing a single bitboard is not 1 instruction, but 3 (load, XOR, store). And typically you have to change 4.

Finally you overlook that you either have to maintain a mailbox board anyway (so that the bitboard operations, no matter how few there might be, are just extra). Either that, or you have to do something quite complex (in terms of number of instructions) to figure out the type of the captured piece. (Which you need for updating the PST evaluation incrementally).

[lithander]

My original question was: "why use bitboards rather than a list of square numbers to record where pieces of a certain type are standing?". That is not really dependent on what other (possibly redundant) data structures you might maintain to speed things up.

My answer to that question was that in a copy/make setup you don't want other redundant data structures because they have to be copied, too. And then a bitboard representation is a good catch-all solution. Better than piece-lists that are great for some queries but not for others.

Bitboard engines usually also maintain a mailbox board to tell them which piece type is on a given square. How else would you know from which bitboard to remove a captured piece? You would also have to loop through all bitboards to figure that out. For that mailbox board copy-make would probably not be an optimal method, though.

Mine doesn't.

In copy/make I have to touch each bitboard once; to copy it. When I play a capture then, in the copy step I copy with a mask where the bit of the target square is zero:

Code: Select all

        
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void CopyMasked(BoardState from, ulong mask)
        {
            White = from.White & mask;
            Black = from.Black & mask;
            Pawns = from.Pawns & mask;
            Knights = from.Knights & mask;
            Bishops = from.Bishops & mask;
            Rooks = from.Rooks & mask;
            Queens = from.Queens & mask;
            Kings = from.Kings & mask;
            CastleFlags = from.CastleFlags & mask;
        }

The captured piece get's removed without even knowing which piece it was. The castling rights are also represented as a bitboard so if you capture a rook the bit is automatically cleared in the copy step.

I don't want to argue with decades of personified chess programming knowledge. I'm just saying that for the copy/make approach which I was trying I found bitboards to be very convenient. And I don't use any additional data structures and it's still quite fast - for a C# engine. And the thing with C# is really, that because it's a managed language, arrays and for loops over them are more expensive than they can be in C/C++. The array is always a pointer into some managed memory block on the heap that you have to access via indexing. You can't increment a pointer to memory directly. (unless you're using unsafe code)

[eligolf]

You code is very readable to my eye and I notice that you keep track of a lot of things that are not strictly necessary for perft in lists. So comparing the speed of your current implementation with one that guns to maximize perft speed is probably not fair. Maybe for all the things you do the speed is fine.

What I do know is that I didn't regret postponing the obsessing about speed for a few months to get a better understanding of the domain.

Is it reasonable to create legal moves instead with bitboard approach or is it standard to make the move and check for legality afterwards? Since that is such rare case and most moves will be pruned anyways.

I use pseudo-legal moves, too, and when I play the move and it ends up with the king in check I just go right to the next move. I found that IsSquareAttacked() is fast enough to not worry too much about it. Legal move generators will be faster in perft (where you play all the moves) but when used in an engine I don't know if it's worth it as most moves are never going to be played.

Yes you are right, some "unnecessary" features for perft only, but will be nice for engine later on. I will continue with AI now, minor optimazations can be done later on I guess if needed

[hgm]

In copy/make I have to touch each bitboard once; to copy it. When I play a capture then, in the copy step I copy with a mask where the bit of the target square is zero:

Code: Select all

        
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void CopyMasked(BoardState from, ulong mask)
        {
            White = from.White & mask;
            Black = from.Black & mask;
            Pawns = from.Pawns & mask;
            Knights = from.Knights & mask;
            Bishops = from.Bishops & mask;
            Rooks = from.Rooks & mask;
            Queens = from.Queens & mask;
            Kings = from.Kings & mask;
            CastleFlags = from.CastleFlags & mask;
        }

The captured piece get's removed without even knowing which piece it was. The castling rights are also represented as a bitboard so if you capture a rook the bit is automatically cleared in the copy step.

I don't want to argue with decades of personified chess programming knowledge. I'm just saying that for the copy/make approach which I was trying I found bitboards to be very convenient. And I don't use any additional data structures and it's still quite fast - for a C# engine. And the thing with C# is really, that because it's a managed language, arrays and for loops over them are more expensive than they can be in C/C++. The array is always a pointer into some managed memory block on the heap that you have to access via indexing. You can't increment a pointer to memory directly. (unless you're using unsafe code)

So you get around knowing which piece was captured, by clearing all possibile pieces. That works, but it means of course that 5 of the 6 clears are redundant no-ops. But updating the game state is only one thing. You also have to update the incremental (PST) evaluation, and the hash key. I don't see how you can do either of that without knowing which piece was captured.

Also, you were talking about "just 4 bitboards". In your code I actualy see 9. That makes 72 bytes. A mailbox board is only 64 bytes...

[lithander]

So you get around knowing which piece was captured, by clearing all possibile pieces. That works, but it means of course that 5 of the 6 clears are redundant no-ops.

Copy with mask is slower than without mask but not by a lot. Sorry, I forgot the exact measurements but while writing the perft I was really benchmarking every little step to write something that's actually fast. And this solution was doing pretty good. (Much better than copying an array of bitboards)

Also, you were talking about "just 4 bitboards". In your code I actualy see 9. That makes 72 bytes. A mailbox board is only 64 bytes...

https://www.chessprogramming.org/QBBEngine uses only four bitboards and a copy/make approach. I opted to use more

Does copying 9 ulong take the same amount of time as copying 72 bytes? Probably, if you can copy the 72 bytes as a memory block. Looping over an array of 72 bytes, incrementing and index and then copying each byte value by value is something else entirely. And that's exactly the problem - not only when copying but when *using* the array in practice.

But it's not really an either/or thing, right? You wouldn't use just the mailbox array (without bitboards and piece lists etc) and expect it to be as fast as a bitboard-only engine like mine? In the end I don't know how much data you have to copy for a practical engine but it's not just 64 bytes I'm sure. Except that in a bitboard only approach like QBB takes it you can get away with less.

But updating the game state is only one thing. You also have to update the incremental (PST) evaluation, and the hash key. I don't see how you can do either of that without knowing which piece was captured.

The move knows which piece was captured! But updating the zobrist hash has nothing to do with the bitboards that store the pieces. All you need is the old hash and information that is already stored in the move.

Okay... how does the move generator know the type of the captured piece without looking at the bitboards. Yes... it looks. It has to touch 6 + 1 bitboards. And it's not pretty but it's also not big enough an issue that I'd need a mailbox array to speed it up. The bitboards are in the cache as the move generator is using them just now to generate moves. Also I need the information in the moves for MVV-LVA sorting anyway even before playing these moves so that's not driving up the cost of the incremental updates.

I really don't want to claim that this is the best way to do it. I didn't read tutorials or study engines. I just wrote something mostly from scratch and if some of my reinvented wheels are squares... well... I guess I had some fun exploring off the beaten path nonetheless. And really I think 60-70M nps in perft with a pseudo legal movegen (so you have to invoke IsSquareAttacked on every node in addition to generating the move and playing it) is pretty good for a C# engine. So most wheels must be fairly round.

Of course now that I add features to the search the speed goes down but I don't think it's due to the board representation. Otherwise... maybe in my 3rd engine I'll get everything right.

[mvanthoor]

Otherwise... maybe in my 3rd engine I'll get everything right.

Oh, shit. So that will be called "Feniks" ? And Leorik will be retroactively be renamed "Titanic" ?