Generating Legal Moves P.1

Introduction

As we saw in the first devlog, chess programming is all about edge cases and little nuances that emerge from the basic rules. We’ll deal with these rare cases in the Move Generator class. All the logic we’ve done in previous devlogs could be inserted into this class. But we do it this way to avoid creating a really long class/routine that does everything by itself. Splitting responsibilities is always a good idea to create more modular and maintainable code.

The goal of this class is to generate a set of legal moves given a board configuration.

   /** 
    * @param {BoardImplementation} board 
    * @param {E_PieceColor} pieceColor
    * @returns {Move[]} Array of legal moves of pieces of given color
    */
   generateMoves(board, pieceColor) {

   }

Now let’s be clear on the definitions. A pseudo-legal move is any move that is consistent with the basic rules on how pieces can move given their position on the board [1]. A pseudo-legal move has a start and destination square defined by the movement pattern of the piece performing it. We have taken care of pseudo-legal moves in previous devlogs by implementing the basic movement rules of every chess piece.

A legal move is any pseudo-legal move that doesn’t leave its own king in check after performing it [2]. The logic we have built so far doesn’t take this into account. Therefore, King’s safety will be a huge part of the algorithm implemented in this class.

Generating pseudo-legal moves

Let’s start with the easiest part which is generating the pseudo-legal moves of every piece in the board.

    /**
     * @param {BoardImplementation} board 
     * @param {E_PieceColor} pieceColor 
     * @returns {Move[]} Array of legal moves of pieces of given color
     */
    generateMoves(board, pieceColor) {
        let legalMoves = [];
        let playingPieces = board.getPiecesOfType(pieceColor, E_PieceType.Any);

        //calculate regular moves for each piece
        for (let piece of playingPieces) {
            //get bitboard ofs moves
            let pieceMovesBitboard = piece.GetMoves(board);
            //convert bitboard to moves
            let pieceMoves = this.#bitboardToMoves(piece, pieceMovesBitboard, E_MoveFlag.Regular);
            //add moves
            legalMoves = legalMoves.concat(pieceMoves);      
        }

        //generate enpassant moves
        let pawns = board.getPiecesOfType(pieceColor, E_PieceType.Pawn);
        let enPassantMoves = this.#generateEnPassantMoves(pawns, board);
        legalMoves = legalMoves.concat(enPassantMoves);

        //generate castling moves
        let rooks = board.getPiecesOfType(pieceColor, E_PieceType.Rook);
        let castlingMoves = this.#generateCastlingMoves(king, rooks, board);
        legalMoves = legalMoves.concat(castlingMoves);

        return legalMoves;
    }

We get an array of pieces of the color provided. Then, we traverse it, get the moves of each piece, and add these moves to an array of legal moves. Finally, we add any possible en-passant and castling moves.

The function bitboardToMoves converts the bitboard returned by each piece to a set of moves with a given move flag.

Hands on! Try to implement this function. If you give it a shot, you’ll get more comfortable with the concept of bitboards and how to manipulate them.

Exercise  Implement the bitboardToMoves function with the following signature:

    /**
     * Converts a bitboard of moves to 
     * an array of moves with given flag.
     * @param {Piece} piece 
     * @param {bigint} movesBitboard 
     * @param {E_MoveFlag} moveFlag 
     * @returns  Array of moves with given flag
     */
    bitboardToMoves(piece, movesBitboard, moveFlag) {}
Solution
    /**
     * Converts a bitboard of moves to an array of moves with given flag
     * @param {Piece} piece 
     * @param {bigint} movesBitboard 
     * @param {E_MoveFlag} moveFlag 
     * @returns  Array of moves with given flag
     */
    bitboardToMoves(piece, movesBitboard, moveFlag) {
        let moves = [];
        let testBit = 1n;

        if (movesBitboard === 0n) return [];
        //for each square
        for (let index = 0; index < 64; index++) {
            //if square is attacked by piece
            let squareAttacked = (movesBitboard & testBit) > 0n;
            if (squareAttacked) {
                //calculate end rank and file
                let endRank = Math.floor((index) / NUMBER_OF_RANKS) + 1;
                let endFile = NUMBER_OF_FILES - (index % NUMBER_OF_FILES);
                //create move
                let newMove = new Move(piece.rank, piece.file, endRank, endFile, moveFlag);
                //add move to array
                moves.push(newMove);
            }

            //continue to next square
            testBit = testBit << 1n;
        }

        return moves;
    }

First, we check if the bitboard has any “on” bits. If that’s not the case, the bitboard equals 0. The piece has no moves to perform. We can return an empty array of moves.

If the bitboard is not empty, we have to loop through every bit to check if it is “on” or “off”. We do this by using a test bit equal to 1 that we’ll shift through every square. Then, we use the ‘&’ operator, which will return 1 if and only if the bit we are checking is set to 1 too. Else it will return 0. If this square is set to “on”, then the piece can move to it.

Finally, we calculate the rank and file of the square to get the destination and we create a new move.

Promotion

The only special move we haven’t covered is promotion.

Relax, it’s not like I hate promotion or something.

It’s just that promotion is a simple move compared to castling or en-passant. The only condition necessary to generate promotion moves is that pawns are one rank before their last rank.

We can implement this condition within the pawn class and then check it while traversing pieces.

//--- ChessUtils.js ---
    const RANKS_TO_PROMOTE = {
        [E_PieceColor.White]: 7,
        [E_PieceColor.Black]: 2
    }
// --- Pawn.js ---
    isBeforePromotingRank() {
        return this.rank === RANKS_TO_PROMOTE[this.color];
    }
// --- MoveGenerator.js ---
    /**
     * @param {BoardImplementation} board 
     * @param {E_PieceColor} pieceColor
     * @returns {Move[]} Array of legal moves of pieces of given color
     */
    generateMoves(board, pieceColor) {
        let legalMoves = [];
        let playingPieces = board.getPiecesOfType(pieceColor, E_PieceType.Any);

        //calculate regular moves for each piece
        for (let piece of playingPieces) {
            //get board with permitted moves
            let pieceMovesBitboard = piece.GetMoves(board);
            //convert bitboard to moves
            let pieceMoves = this.#bitboardToMoves(piece, pieceMovesBitboard, E_MoveFlag.Regular);
            //add moves
            legalMoves = legalMoves.concat(pieceMoves);      
        }

        //if a pawn is about to promote
        if (piece.GetType() === E_PieceType.Pawn && piece.isBeforePromotingRank()) {
            //add promotion moves
            let promotionsMoves = this.#bitboardToMoves(piece, pieceMovesBitboard, E_MoveFlag.Promotion);
            legalMoves = legalMoves.concat(promotionsMoves);
        }// else, add regular piece moves
        else {
            let pieceMoves = this.#bitboardToMoves(piece, pieceMovesBitboard, E_MoveFlag.Regular);
            legalMoves = legalMoves.concat(pieceMoves);
        }

        //generate enpassant moves
        let pawns = board.getPiecesOfType(pieceColor, E_PieceType.Pawn);
        let enPassantMoves = this.#generateEnPassantMoves(pawns, board);
        legalMoves = legalMoves.concat(enPassantMoves);

        //generate castling moves
        let rooks = board.getPiecesOfType(pieceColor, E_PieceType.Rook);
        let castlingMoves = this.#generateCastlingMoves(king, rooks, board);
        legalMoves = legalMoves.concat(castlingMoves);

        return legalMoves;
    }

Try it out:

The details on how to create a selector to choose which piece to promote will be explained in upcoming devlogs.

King’s Safety

There’s nothing more imperative in Chess than keeping your king safe while threatening the safety of the opponent’s king. Everything in the game revolves around those two objectives. I’ve found that these apparently simple premises are ironically the most difficult things to achieve. This is because every other rule is limited and conditioned by these objectives, which brings a handful of new considerations that are more complex than what meets the eye at first.

Lazy Filtering

One approach to easily generate legal moves is what I call Lazy Filtering. I named it this way because it’s made for lazy people (lazy in a good-hearted way!) who want to keep things as straightforward as possible. Also, “lazy” is a common adjective for some programming strategies in which we defer an action until it becomes necessary (like lazy evaluation [3]). We programmers love to procrastinate work, don’t we?

Alt text
What I tell myself while procrastinating. Taken from [4]

In this case, we filter bad moves only after generating them. This is what that would look like:

/**
    * @param {Board} board 
    * @param {E_PieceColor} pieceColor
    * @returns {Move[]} Array of legal moves of pieces of given color
    */
   generateMoves(board, pieceColor) {
       let pseudoMoves = generatePseudoMoves(board, pieceColor);
       let legalMoves = [];

       pseudoMoves.forEach(pseudoMove => {
           board.makeMove(pseudoMove);
           if(!board.IsKingInCheck(pieceColor)){
               legalMoves.Add(pseudoMove);
           }
           board.unmakeMove(pseudoMove);
       });
   }

We generate the set of pseudo-legal moves using the algorithm we created previously. Then, we make each move on the board, checking if our king is in check after performing it. If it is not, then that move is legal and we add it to the set of legal moves. Otherwise, we omit it and continue with the next move. Finally, we unmake the move on the board to keep things the same as before. This approach is showcased in this video [5].

As we can see, this technique is the simplest we can apply to generate legal moves. We don’t need to account for any consideration because everything boils down to whether the king is in check or not after moving.

However, there’s a reason why it is not popular amongst the chess programming community. Most chess programming literature out there is focused on creating chess engines like Stockfish. Chess engines work by calculating a million possibilities to judge which move will guarantee the best possible outcome. To be able to perform all those calculations in a short span, the code running behind must have outstanding performance and efficiency. This technique is nowhere near the most performant one because it will unnecessarily iterate through a lot of illegal moves.

Whether this is relevant to you or not depends on your specific application for chess. If you just want to get a chess game working, this might be the best fit to quickly get something working. For a chess engine, though, you might want to pick another alternative.

“Not-Lazy” Filtering

In this case, we will prune a lot of illegal moves as we calculate them.

After tons of coding, testing, and hours spent staring at my computer without knowing what was going on, I’ve learned that ensuring king safety comes down to three aspects:

  • Generating safe moves for the king
  • Dealing with pieces that are checking the king
  • Limiting the movement of pinned pieces

In this devlog, I’ll briefly go over how each aspect plays a role in the Move Generation algorithm. I won’t go into detail on how some functions work. This will be further explained in future entries.

King’s safe moves

Currently, our king is a bit careless and likes to go wherever it wants regardless if he could be captured in the next move.

Alt text
King’s Gambit. Taken from [6]

The first thing we want to do is to discard any king move that’ll put him in a tight spot. For this, we add a simple function that takes the king, the enemy pieces, and the board, and returns an array of moves. Then, we exclude the calculation of king moves from the loop.

/**
     * @param {BoardImplementation} board 
     * @param {E_PieceColor} pieceColor
     * @returns {Move[]} Array of legal moves of pieces of given color
     */
    generateMoves(board, pieceColor) {
        let legalMoves = [];
        let playingPieces = board.getPiecesOfType(pieceColor, E_PieceType.Any);
        let enemyPieces = board.getPiecesOfType(OppositePieceColor(pieceColor), E_PieceType.Any);

        //calculate safe moves for king
        let king = board.getPiecesOfType(pieceColor, E_PieceType.King)[0];
        if (king !== undefined) {
            let kingSafeMoves = this.#generateKingSafeMoves(king, enemyPieces, board);
            legalMoves = legalMoves.concat(kingSafeMoves);
        }

        //calculate regular moves for each piece
        for (let piece of playingPieces) {

            //exclude calculation for king
            if (piece.GetType() === E_PieceType.King) continue;

            //get board with permitted moves
            let pieceMovesBitboard = piece.GetMoves(board);

            //if a pawn is about to promote
            if (piece.GetType() === E_PieceType.Pawn && piece.isBeforePromotingRank()) {
                let promotionsMoves = this.#bitboardToMoves(piece, pieceMovesBitboard, E_MoveFlag.Promotion);
                legalMoves = legalMoves.concat(promotionsMoves);
            }// else, add regular piece moves
            else {
                let pieceMoves = this.#bitboardToMoves(piece, pieceMovesBitboard, E_MoveFlag.Regular);
                legalMoves = legalMoves.concat(pieceMoves);
            }
        }

        //generate enpassant move
        let pawns = board.getPiecesOfType(pieceColor, E_PieceType.Pawn);
        let enPassantMoves = this.#generateEnPassantMoves(pawns, board);
        legalMoves = legalMoves.concat(enPassantMoves);

        //generate castling moves
        let rooks = board.getPiecesOfType(pieceColor, E_PieceType.Rook);
        let castlingMoves = this.#generateCastlingMoves(king, rooks, board);
        legalMoves = legalMoves.concat(castlingMoves);

        return legalMoves;
    }

Checkers

If a piece is checking your king, you forcefully need to take care of it in the next move. There are 2 scenarios that are relevant to us.

One checker

If the king is being checked by one piece, we can avoid the check by:

  • Moving the king to a safe square.
  • Blocking the path of the piece that’s giving check.
  • Capturing the piece that’s giving check.

You can only block sliding pieces because they are the only ones that can check from a distance. And let’s not talk about the bishop…

Alt text
Happens every time. Taken from [7]

You cannot block the knight because it can jump over pieces. Pawns can capture when they are right next to a piece, so there’s no way of blocking there.

Here are some examples of dealing with one checker:

Two or more checkers

If the king is being checked by multiple pieces at a time, the only possibility is to move the king to a safe square. This is simply because a single piece cannot capture two pieces in a single move. Neither it cannot block two lines of attack in a single move. And yeah, certainly it cannot block a line of attack while capturing a checking piece.

I know it might be a bit difficult to wrap your head around this concept. It surely was for me. I tried to think of one configuration in which this rule is not valid. But trust me, it is just not possible.

Alt text
It’s just not… Taken from [8]

We can see it here:

Code

/**
     * @param {BoardImplementation} board 
     * @param {E_PieceColor} pieceColor
     * @returns {Move[]} Array of legal moves of pieces of given color
     */
    generateMoves(board, pieceColor) {
        let legalMoves = [];
        let playingPieces = board.getPiecesOfType(pieceColor, E_PieceType.Any);
        let enemyPieces = board.getPiecesOfType(OppositePieceColor(pieceColor), E_PieceType.Any);

        //calculate safe moves for king
        let king = board.getPiecesOfType(pieceColor, E_PieceType.King)[0];
        let targetSquaresToAvoidCheck = getBooleanBitboard(true);//squares to block check or capture checkers

        if (king !== undefined) {
            let kingSafeMoves = this.#generateKingSafeMoves(king, enemyPieces, board);

            let checkers = this.#calculateCheckers(king, enemyPieces, board);

            //if there's more than one checker
            if (1 < checkers.length) {
                //the only possible moves are king moves
                return kingSafeMoves;
            } //else if there is just 1 checker
            else if (checkers.length === 1) {
                //calculate squares that can block the check or capture checker
                targetSquaresToAvoidCheck = this.#calculateSquaresToAvoidCheck(king, checkers[0], board);
            }

            legalMoves = legalMoves.concat(kingSafeMoves);
        }

        //calculate regular moves for each piece
        for (let piece of playingPieces) {

            //exclude calculation for king
            if (piece.GetType() === E_PieceType.King) continue;

            //get board with permitted moves
            let pieceMovesBitboard = piece.GetMoves(board);

            //filter moves if king is in check
            pieceMovesBitboard = pieceMovesBitboard & targetSquaresToAvoidCheck;

            //if a pawn is about to promote
            if (piece.GetType() === E_PieceType.Pawn && piece.isBeforePromotingRank()) {
                let promotionsMoves = this.#bitboardToMoves(piece, pieceMovesBitboard, E_MoveFlag.Promotion);
                legalMoves = legalMoves.concat(promotionsMoves);
            }// else, add regular piece moves
            else {
                let pieceMoves = this.#bitboardToMoves(piece, pieceMovesBitboard, E_MoveFlag.Regular);
                legalMoves = legalMoves.concat(pieceMoves);
            }
        }

        //generate enpassant move
        let pawns = board.getPiecesOfType(pieceColor, E_PieceType.Pawn);
        let enPassantMoves = this.#generateEnPassantMoves(pawns, board);
        legalMoves = legalMoves.concat(enPassantMoves);

        //generate castling moves
        let rooks = board.getPiecesOfType(pieceColor, E_PieceType.Rook);
        let castlingMoves = this.#generateCastlingMoves(king, rooks, board);
        legalMoves = legalMoves.concat(castlingMoves);

        return legalMoves;
    }

After generating safe moves for the king, we determine which pieces are checking the king. If there’s more than one checker, we immediately return the king’s safe moves, as there are no other possible moves. If there’s just one checker, we calculate a bitboard that holds the squares that pieces can move to in order to capture the checker or block the check. This bitboard is later applied as a filter to the moves of every piece.

Pinned pieces

A pinned piece is a piece that’s blocking a distant check to the king. Any move in the wrong direction will leave the king in check. Therefore, the movement of a pinned piece is limited to the squares within the direction of attack of the enemy piece.

    generateMoves(board, pieceColor) {
        let legalMoves = [];
        let playingPieces = board.getPiecesOfType(pieceColor, E_PieceType.Any);
        let enemyPieces = board.getPiecesOfType(OppositePieceColor(pieceColor), E_PieceType.Any);

        //calculate data to ensure king safety
        let king = board.getPiecesOfType(pieceColor, E_PieceType.King)[0];
        let targetSquaresToAvoidCheck = getBooleanBitboard(true);//squares to block check or capture checkers
        let moveFilterForPinnedPieces = {};//filter for moves of pinned pieces

        if (king !== undefined) {
            let kingSafeMoves = this.#generateKingSafeMoves(king, enemyPieces, board);

            let checkers = this.#calculateCheckers(king, enemyPieces, board);
            //if there's more than one checker
            if (1 < checkers.length) {
                //the only possible moves are king moves
                return kingSafeMoves;
            } //else if there is just 1 checker
            else if (checkers.length === 1) {
                //calculate squares that can block the check or capture checker
                targetSquaresToAvoidCheck = this.#calculateSquaresToAvoidCheck(king, checkers[0], board);
            }

            //calculate filters for moves of pinned pieces
            moveFilterForPinnedPieces = this.#calculatePinnedPieces(king, enemyPieces, board);
  
            legalMoves = legalMoves.concat(kingSafeMoves);
        }

        //calculate regular moves for each piece
        for (let piece of playingPieces) {

            //exclude calculation for king
            if (piece.GetType() === E_PieceType.King) continue;

            //get board with permitted moves
            let pieceMovesBitboard = piece.GetMoves(board);

            //filter moves if king is in check
            pieceMovesBitboard = pieceMovesBitboard & targetSquaresToAvoidCheck;

            //if piece is pinned, remove moves that discover a check
            let isPiecePinned = moveFilterForPinnedPieces[piece.position] !== undefined;
            if (isPiecePinned) {
                let moveFilter = moveFilterForPinnedPieces[piece.position];
                pieceMovesBitboard = pieceMovesBitboard & moveFilter;
            }

            //if a pawn is about to promote
            if (piece.GetType() === E_PieceType.Pawn && piece.isBeforePromotingRank()) {
                //add promotion moves
                let promotionsMoves = this.#bitboardToMoves(piece, pieceMovesBitboard, E_MoveFlag.Promotion);
                legalMoves = legalMoves.concat(promotionsMoves);
            }// else, add regular piece moves
            else {
                let pieceMoves = this.#bitboardToMoves(piece, pieceMovesBitboard, E_MoveFlag.Regular);
                legalMoves = legalMoves.concat(pieceMoves);
            }
        }

        //generate enpassant move
        let pawns = board.getPiecesOfType(pieceColor, E_PieceType.Pawn);
        let enPassantMoves = this.#generateEnPassantMoves(pawns, board);
        legalMoves = legalMoves.concat(enPassantMoves);

        //generate castling moves
        let rooks = board.getPiecesOfType(pieceColor, E_PieceType.Rook);
        let castlingMoves = this.#generateCastlingMoves(king, rooks, board);
        legalMoves = legalMoves.concat(castlingMoves);

        return legalMoves;
    }

After dealing with checkers, we calculate which pieces are pinned. Then, we create a filter for the moves of each piece that’s pinned. The calculatePinnedPieces function returns a lookup table [9], which receives the piece position as the key, and returns a filter for its moves.

While looping through our pieces, we’ll check if the current piece is pinned by looking for it in the lookup table. If it is, we retrieve the filter and apply it to the bitboard of moves.

Here’s the result:

Safety in special moves

A final note on how King’s safety plays into the logic of special moves.

Promotion

Promotions are just regular pawn moves with a special flag. Hence, all we’ve talked about so far applies indistinctively to these moves.

Castling

One of the rules for castling specifies that the king cannot pass through squares that are being attacked by enemy pieces. If any square risks the chance of putting the king in check, the castling is not possible in the first place. This means that the king will always be in a safe square after castling. There’s no need for extra considerations in this case.

En-Passant

En-passant will forever be a pain in the back of chess players, who always forget it exists, and chess programmers, who had to deal with the special exceptions of this move.

Alt text
Google En Passant. Taken from [10]

Yet it comes back to haunt us again. Since an en-passant capture removes a piece from the board while simultaneously moving another piece, the risk of discovering a check on the king is really high.

We could stand for the “not-lazy” mindset we’ve had so far and try to determine if performing an en-passant capture will leave the king in check. However, considering that en-passant is a move that’s not common during a game, we can give in to the temptation of using the lazy approach. The overhead this technique generates won’t matter much because it will rarely happen anyway.

    /**
     * Checks if an en passant move is legal.
     * @param {E_PieceColor} playingColor 
     * @param {Move} enPassant 
     * @param {BoardImplementation} board 
     * @returns Whether the en passant move is legal
     */
    #isEnPassantLegal(playingColor, enPassant, board) {
        let capturedPawnRank = enPassant.startRank;
        let capturedPawnFile = enPassant.endFile;
        let capturingPawnRank = enPassant.startRank;
        let capturingPawnFile = enPassant.startFile;

        //check is king is currently in check
        let checkBeforeEnPassant = board.isKingInCheck(playingColor);

        //simulate making the en passant capture by removing both pieces
        let capturedPawn = board.removePiece(capturedPawnRank, capturedPawnFile);
        let capturingPawn = board.removePiece(capturingPawnRank, capturingPawnFile);

        //check if king is in check after making the en passant capture
        let checkAfterEnPassant = board.isKingInCheck(playingColor);

        //add removed pawns
        board.addPiece(capturedPawn, capturedPawnRank, capturedPawnFile);
        board.addPiece(capturingPawn, capturingPawnRank, capturingPawnFile);

        if (!checkBeforeEnPassant & !checkAfterEnPassant) {
            //en passant is legal
            return true;
        } else if (checkBeforeEnPassant && !checkAfterEnPassant) {
            //en passant blocks the check or captures pawn that was checking. Therefore, it is legal
            return true;
        } else if (!checkBeforeEnPassant & checkAfterEnPassant) {
            //en passant discovers a check. Therefore, it is illegal
            return false;
        } else if (checkBeforeEnPassant & checkAfterEnPassant) {
            //en passant discovered another check or enpassant move does not remove the check
            return false;
        }
    }

We add a function that checks if the en-passant generated is legal. As explained in the section of lazy filtering, we simulate performing the move by removing both pieces and we check if the king is in check. If it is, the en-passant move is not legal. The last four if-conditionals explain the meaning of each case in terms of what’s happening on the board. This approach is inspired by this article[11].

Conclusion

To wrap up this entry, let me point out that the algorithm we have developed here is not remotely close to what I came up with on my first try. This algorithm is the result of tons of mistakes, debugging, and testing that ultimately lead to a functional solution.

So don’t feel discouraged if what you create does not work the first time. You’ll eventually get there if you keep trying.

In the next devlog, we’ll look at a useful testing technique that will definitely help you track down errors in your code so you can get to the solution much faster.

References