Move generation for bitboards

[eligolf]

Hi,

I am fairly new to bitboards in general and implemented magic bitboards with the help of Code Monkey Kings nice tutorial on YouTube, but as a C# engine instead. All attack tables seems to be working find after some random tests so I started implementing move generation. This is when I find some questions that I have a hard time deciding about, and which seems to be important for performance.

Question 1

Right now I loop through all piece bitboards for the given color. I the loop I have another loop going through all bits in that table (fromSquares).
If we take the pawn moves I can then get the bitboard corresponding to legal quiet (or attacking) moves for a fromSquare. How do I go from here? I could again loop through each bit in those boards (toSquares and add a move as (fromSquare, toSquare, extraInfo...). Is there a more efficient or more clever way?

Question 2
Speaking of generating/defining moves, I am not sure what the best solution will be for defining a move in C#. In Cosette which was linked to me it uses it according to this: https://github.com/Tearth/Cosette/blob/ ... es/Move.cs. However I have no idea how to understand the first init of From and To, or even how a struct works in general.
Instead I was thinking of just using a normal static class with information about fromSquare, toSquare, moveFlags etc and store all these in a list of possible moves. Will this be a huge decrease in performance, or are there other ways that are more performance friendly than that, but less complex than the struct solution in Cosette?

[hgm]

You could encode captures as (attacker, victim) pairs rather than (fromSqr, toSqr) pairs, and put all 256 possible captures in a static list, in MVV/LVA order. And then use a bitmap (e.g. stored in 4 64-bit integers) to indicate which of the captures is actually possible.

[eligolf]

I am not sure if I am clear. When I generate moves I want to get all possible moves in a moves list which I can then loop over in negamax function. The questions are regarding how to encode a move to put in the list, and how to retrieve the move parameters from the bitboard with possible attack/quit squares.

[hgm]

Well, you already pretty much described that, right? You have to extract the target squares from the bitboard for the given piece its destinations in a loop, which gives you the toSqr numbers. You can then store the (fromSqr, toSqr) pairs in a list. Depending on whether you want to assign score keys during move generations, or in a separate loop through that list (see another active discussion) you could also immediately look up what is on the toSqr, and derive an MVV/LVA key from that, which you also store in the move representation. E.g. as an extra field in the struct you use to encode moves. I usually encode moves as an integer (sortKey << 24 | fromSqr << 8 | toSqr).

It is usually more efficient to extract captures and non-captures from the bitboard of destinations in separate loops, (each acting on the destinations ANDed with squares of the desired occupancy), so these end up in separate lists, or at opposit ends of the same list. This saves you work in pick the captures from the list. You could also defer extracting the non-captures until after the captures are searched, which then would also require a second loop over all pieces. In the non-capture loop you would calculate the sort keys in a different way (e.g. history instead of MVV/LVA).

You could also store the type of the moved and captured piece in the move, so you can use those during UnMake. I never saw the point of that, though, as the UnMake then would have to read it from the move struct, which is not any faster than reading it from the board. It just bloats the move representation, which might make it more work to shuttle those around during move sorting. What you do during preparation of the move list you do on all moves, while what you do during MakeMove is only done on the moves you actually search before you get a cutoff.

[eligolf]

Thanks for the input H.G., that is good input. And sorry, I am only average in both chess programming and C# so some questions could be seen as "dumb". It is fun and a bit addicting to develop engines though and one learns by each new tutorial/article/forum posts

[lithander]

Instead I was thinking of just using a normal static class with information about fromSquare, toSquare, moveFlags etc and store all these in a list of possible moves.

You can do that and it's not preventing you from writing a fast engine. I would advice for using a struct instead of a class though. You want moves to live on the stack and not the heap. (e.g. value types, not reference types)

Code: Select all

    public readonly struct Move
    {
        public readonly Piece Flags;
        public readonly Piece Target;
        public readonly byte FromSquare;
        public readonly byte ToSquare;
    }

This is how my Move struct looks like. Note that the Piece enumeration will fit into a "byte" and also encodes whether the move is enPassant, Promotions or Castling. That means the struct takes up 4 bytes == 32 bit of space. Cosette tries to pack the information into 16 bits (ushort) but in my experience that does not have any practial advantage.

Storing the target here is useful mostly for captures because if you know the target you can cheaply compute a MvvLva score for move ordering on the fly.

Code: Select all

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int MvvLvaScore()
        {
            //Most valuable Victim, Least valuable Attacker
            //EnPassent = -1
            //King capturing Pawn = 1 * 6 - 6 = 0
            //Pawn capturing Queen = 6 * 5 - 1 = 29  
            return 6 * Order(Target) - Order(Flags & Piece.PieceMask);
        }

        //Pawn = 1, Knight = 2, Bishop = 3; Rook = 4, Queen = 5, King = 6
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Order(Piece piece) => (int)piece >> 2;

Note these quite ugly MethodImpl attributes I have over the methods? It will tell the JIT-compiler (or whatever is responsible to turn IL into binary in the end) that you really don't want the overhead of method calls here. Everything is getting inlined. So using a Method like Order in the code is just to make it more human readable.

You have a lot of options what you store in the Move struct besides from and to square. As hgm said you could look up the target from the board once you need it. The best choice depends on what other choices you've made so I advice you to just setup a project that runs a few test when you start the executable (like perft(X) on a number of positions) and then you just test the different ideas you have.

If you follow a tutorial you often don't realize that you have a lot more options than what the tutorial explained. So don't be discouraged from trying your own ideas. Just make sure you test every little step to make sure your assumptions are actually correct.

(I'm only a few days from making the repository of my bitboard C# engine public but if you want to have a look at the move generator now send me a PM.)

[hgm]

There is no advantage to squeezing the size of the move representation below 32 bits. Except for storing moves in the hash table. There you would like it to be 2 bytes. That means the flags have to be packed somehow with the from- and to-square. To avoid the complexity of packing / unpacking, I tend to use the same format for moves in the hash table and in the move list. Except that in the move list I also include the sort key as one of the two extra bytes available there.

For this reason I encode the move flags and the to-square together in a single byte. E.g. values 0-63 could mean the to-square of a normal move, while the values 128-255 could be used for indicating a special move (4 castlings, 28 e.p. captures, 64 promotions and 16 pawn double pushes). Values >= 128 are then used during MakeMove() to index a table that contains the additional info needed to execute the move (the true to-square, the piece to put there, the score bonus this gives, optionally a second piece to move).

[eligolf]

Instead I was thinking of just using a normal static class with information about fromSquare, toSquare, moveFlags etc and store all these in a list of possible moves.

You can do that and it's not preventing you from writing a fast engine. I would advice for using a struct instead of a class though. You want moves to live on the stack and not the heap. (e.g. value types, not reference types)

Code: Select all

    public readonly struct Move
    {
        public readonly Piece Flags;
        public readonly Piece Target;
        public readonly byte FromSquare;
        public readonly byte ToSquare;
    }

This is how my Move struct looks like. Note that the Piece enumeration will fit into a "byte" and also encodes whether the move is enPassant, Promotions or Castling. That means the struct takes up 4 bytes == 32 bit of space. Cosette tries to pack the information into 16 bits (ushort) but in my experience that does not have any practial advantage.

(I'm only a few days from making the repository of my bitboard C# engine public but if you want to have a look at the move generator now send me a PM.)

Very exciting news with your engine, I will follow the thread and looking forward of trying it out and looking at the code! Cosette is probably very good but it written in an advanced way without any comments which makes it hard to follow for an intermediate selftaught programmer as myself. The generate move function for example is nested with all kind of functions and I can't figure out how it all holds together

I have a pretty straightforward way of calculating moves , which can probably be speed up a bit but I just finished the "skeleton" of it today. If you have time and feel like you would comment please do, otherwise I will figure it out myself. Will look into structs and how they work, thanks for the input

Code: Select all

public void GetAllMoves()
        {
            // Clear list of moves
            PossibleMoves = new List<int>();

            // Loop through all piece bitboards
            for (int piece = Piece.Pawn; piece <= Piece.King; piece++)
            {
                // Loop through all occupied squares for the given bitboard
                ulong pieceBitboard = Pieces[ColorToMove][piece];
                foreach (int fromSquare in BitOperations.GetOccupiedSquares(pieceBitboard))
                {

                    // ##################################################################
                    //                             PAWNS
                    // ##################################################################
                    if (piece == Piece.Pawn)
                    {
                        List<int> promotionSquares = ColorToMove == Color.White ?
                            GameConstants.PromotionSquaresWhite : GameConstants.PromotionSquaresBlack;

                        // Quiet moves (shift depends on color to move), as per comments in https://www.youtube.com/watch?v=62Hy1JEehqI&list=PLmN0neTso3Jxh8ZIylk74JpwfiWNI76Cs&index=23
                        int direction = ColorToMove == Color.White ? -8 : 8;
                        ulong possibleSquares = (1ul - (1ul & (OccupancyAll >> (fromSquare + direction)))) * (Pawns.QuietMasks[ColorToMove][fromSquare] & ~OccupancyAll);
                        foreach (int toSquare in BitOperations.GetOccupiedSquares(possibleSquares))
                        {
                            // No promotions 
                            if (!promotionSquares.Contains(toSquare))
                            {
                                // One step moves
                                if (Mathf.Abs(fromSquare - toSquare) == 8)
                                {
                                    Debug.Log("Pawn one step: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                                }
                                // Two step moves
                                else
                                {
                                    Debug.Log("Pawn two steps: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                                }
                            }
                            // Promotions
                            else
                            {
                                Debug.Log("Pawn promotion: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                            }
                        }

                        // Captures
                        possibleSquares = Pawns.AttackMasks[ColorToMove][fromSquare] & Occupancy[Color.Invert(ColorToMove)];
                        foreach (int toSquare in BitOperations.GetOccupiedSquares(possibleSquares))
                        {
                            // No promotions 
                            if (!promotionSquares.Contains(toSquare))
                            {
                                Debug.Log("Pawn capture: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                            }
                            // Promotions
                            else
                            {
                                Debug.Log("Pawn capture promotion: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                            }
                        }

                        // Enpassant
                        if (EnPassant != GameConstants.EmptyBitboard)
                        {
                            ulong epAttacks = Pawns.AttackMasks[ColorToMove][fromSquare] & EnPassant;
                            if (epAttacks != GameConstants.EmptyBitboard)
                            {
                                int toSquare = BitOperations.GetLSBIndex(epAttacks);
                                Debug.Log("Pawn enpassant: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                            }
                        }
                    }

                    // ##################################################################
                    //                              KING
                    // ##################################################################
                    else if (piece == Piece.King)
                    {
                        // Quiet moves
                        ulong possibleSquares = Kings.AttackMasks[fromSquare] & ~OccupancyAll;
                        foreach (int toSquare in BitOperations.GetOccupiedSquares(possibleSquares))
                        {
                            Debug.Log("King quiet moves: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                        }

                        // Attack moves
                        possibleSquares = Kings.AttackMasks[fromSquare] & Occupancy[Color.Invert(ColorToMove)];
                        foreach (int toSquare in BitOperations.GetOccupiedSquares(possibleSquares))
                        {
                            Debug.Log("King attack moves: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                        }

                        // CASTLING

                        // White side
                        if (ColorToMove == Color.White)
                        {
                            // King side
                            if (Kings.WhiteCanCastleKingSide(this, ColorToMove))
                            {
                                Debug.Log("White king castle O-O");
                            }
                            // Queen side
                            if (Kings.WhiteCanCastleQueenSide(this, ColorToMove))
                            {
                                Debug.Log("White king castle O-O-O");
                            }
                        }
                        // Black side
                        else
                        {
                            // King side
                            if (Kings.BlackCanCastleKingSide(this, ColorToMove))
                            {
                                Debug.Log("Black king castle O-O");
                            }
                            // Queen side
                            if (Kings.BlackCanCastleQueenSide(this, ColorToMove))
                            {
                                Debug.Log("Black king castle O-O-O");
                            }
                        }
                    }

                    // ##################################################################
                    //                       ALL OTHER PIECES
                    // ##################################################################
                    
                    // Knight
                    else if (piece == Piece.Knight)
                    {
                        // Quiet moves
                        ulong possibleSquares = Knights.AttackMasks[fromSquare] & ~OccupancyAll;
                        foreach (int toSquare in BitOperations.GetOccupiedSquares(possibleSquares))
                        {
                             Debug.Log("Knight move: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                        }

                        // Attack moves
                        possibleSquares = Knights.AttackMasks[fromSquare] & Occupancy[Color.Invert(ColorToMove)];
                        foreach (int toSquare in BitOperations.GetOccupiedSquares(possibleSquares))
                        {
                            Debug.Log("Knight capture: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                        }
                    }

                    // Bishop
                    else if (piece == Piece.Bishop)
                    {
                        // Quiet moves
                        ulong possibleSquares = Bishops.GetAttacks(fromSquare, OccupancyAll) & ~OccupancyAll;
                        foreach (int toSquare in BitOperations.GetOccupiedSquares(possibleSquares))
                        {
                            Debug.Log("Bishop move: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                        }

                        // Attack moves
                        possibleSquares = Bishops.GetAttacks(fromSquare, OccupancyAll) & Occupancy[Color.Invert(ColorToMove)];
                        foreach (int toSquare in BitOperations.GetOccupiedSquares(possibleSquares))
                        {
                            Debug.Log("Bishop capture: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                        }
                    }

                    // Rook
                    else if (piece == Piece.Rook)
                    {
                        // Quiet moves
                        ulong possibleSquares = Rooks.GetAttacks(fromSquare, OccupancyAll) & ~OccupancyAll;
                        foreach (int toSquare in BitOperations.GetOccupiedSquares(possibleSquares))
                        {
                            Debug.Log("Rook move: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                        }

                        // Attack moves
                        possibleSquares = Rooks.GetAttacks(fromSquare, OccupancyAll) & Occupancy[Color.Invert(ColorToMove)];
                        foreach (int toSquare in BitOperations.GetOccupiedSquares(possibleSquares))
                        {
                            Debug.Log("Rook capture: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                        }
                    }

                    // Queen
                    else if (piece == Piece.Queen)
                    {
                        // Quiet moves
                        ulong possibleSquares = Queens.GetAttacks(fromSquare, OccupancyAll) & ~OccupancyAll;
                        foreach (int toSquare in BitOperations.GetOccupiedSquares(possibleSquares))
                        {
                            Debug.Log("Queen move: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                        }

                        // Attack moves
                        possibleSquares = Queens.GetAttacks(fromSquare, OccupancyAll) & Occupancy[Color.Invert(ColorToMove)];
                        foreach (int toSquare in BitOperations.GetOccupiedSquares(possibleSquares))
                        {
                            Debug.Log("Queen capture: " + GameConstants.squareIndexToString(fromSquare) + "-" + GameConstants.squareIndexToString(toSquare));
                        }
                    }
                }
            }
        }

[mvanthoor]

...

Personally, my advice would be to not create very long functions. You Gen_All() function does generate all the moves, but it can be broken up into distinct sections. Also, it is going to be harder to modify the move generator to generate only captures or quiets. My move generator looks like this:

Main move generator part

As you can see, the new() function calls several init functions to create all the attack tables for all the pieces, instead of having one massive init function. Same for generate_moves(). It calls the piece(), pawn() or casting() functions to create those moves, and because it has a MoveType already, it can be decided if a particular move is going to be generated/added to the move list or not.

This way you can change a move generator function (for example, generating knight moves) without worrying that you're going to touch something that is going to mess up generating the moves of the king.

[Tearth]

Indeed packing Move into 16 bits in Cosette didn't give me any visible performance gain, I've just felt better having one structure everywhere (so the smallest possible because of TT entries).