Generating Legal Moves P.2

June 26, 2024

Introduction

In this devlog, we’ll look further into the implementation of some functions that are crucial for calculating legal moves and that were not explained in the last devlog. As a disclaimer, the following algorithms are more convoluted than usual and may require extra brain cells to understand.

Overthinking Overthinker GIFfrom Overthinking GIFs
Me coding this. Taken from [1]

I strongly encourage you to try to implement these functions by yourself before looking at the solutions, even if it’s just pseudocode. There are advanced problems that require creative problem-solving. If you give them a go, you’ll develop important skills for a programmer, even if you don’t come up with the right answer.

If you prefer to skip to the next topics and leave this for later, or you already built something that works, you can continue with the next devlog and assume these functions work.

Let’s get right into it. We’ll go from the easiest to the most difficult algorithm.

Checkers

The number of pieces checking the king determines the course of action of the move generation algorithm. To calculate this number, we’ll manually go over every opponent piece and see if they are checking the king.

    /**
     * @param {King} king 
     * @param {Piece[]} enemyPieces 
     * @param {BoardImplementation} board 
     * @returns Array of pieces that check the king
     */
    calculateCheckers(king, enemyPieces, board) {
        let checkers = [];
        for (let enemyPiece of enemyPieces) {
            let pieceChecksKing = (enemyPiece.GetMoves(board) & king.position) > 0n;
            if (pieceChecksKing) {
                checkers.push(enemyPiece);
            }
        }
        return checkers;
    }

If the intersection of the bitboard of moves and the king’s position is not empty, the opponent piece is effectively checking the king.

If the number of checkers is one, we calculate the squares that our pieces need to move to for neglecting the check.

    /**
     * @param {King} king 
     * @param {Piece} checker 
     * @returns Bitboard with squares pieces can move to in order to avoid the check
     */
    calculateSquaresToAvoidCheck(king, checker) {
        //if checker is a slider
        if (checker.IsSlider()) {
            //We can block the check by moving to any square between the slider and the king or capturing the slider
            return getRay(checker.rank, 
            checker.file,
            king.rank,
            king.file,
            true, //include start square
            false); //exclude destination square
        } //if piece is not a slider
        else {
            //We can avoid the check only by capturing the checker
            return checker.position;
        }
    }

If the checker is a slider, we can neglect the check by blocking its way or capturing it. The getRay function allows us to return a ray between two pieces, including the position of both pieces if requested. If the checker is not a slider, the only option is to capture it, so we return its position.

King’s safe moves

The obvious step to achieve safe moves is to remove any square attacked by the opponent.

class MoveGenerator{
    /**
     * @param {King} king 
     * @param {bigint} enemyPieces 
     * @param {BoardImplementation} board 
     * @returns Array of moves the king can do safely
     */
    generateKingSafeMoves(king, enemyPieces, board) {
        let dangerousSquaresForKing = 0n;
        let squaresAttackedByEnemy = board.getAttackedSquares(OppositePieceColor(king.color));

        dangerousSquaresForKing = squaresAttackedByEnemy;

        let kingMovesBitboard = king.GetMoves(board) & ~dangerousSquaresForKing;
        return this.#bitboardToMoves(king, kingMovesBitboard, E_MoveFlag.Regular);
    }
}

class BoardImplementation{
    /**
     * @param {E_PieceColor} pieceColor 
     * @param {E_PieceType} pieceType 
     * @returns Bitboard with squares being attacked by pieces of given characteristics 
     */
    getAttackedSquares(pieceColor = E_PieceColor.Any, pieceType = E_PieceType.Any) {
        let attacksBitboard = 0n;
        //for every piece of given characteristics
        let pieces = this.getPiecesOfType(pieceColor, pieceType);
        pieces.forEach(piece => {
            let pieceAttackMoves;
            pieceAttackMoves = piece.GetMoves(this);
            //add moves to attacks
            attacksBitboard |= pieceAttackMoves;
        });

        return attacksBitboard;
    }
}

In the BoardImplementation class, we loop through every opponent piece and collect all their attacks. Then, we intersect the king’s moves with the squares that are not dangerous for it.

Unfortunately, it won’t be that easy this time. We have to address a couple of problems.

Attacks behind the king

The algorithm that calculates sliding pieces’ moves relies on projecting a ray that stops whenever it finds an occupied square. This introduces an error when calculating safe squares because attacks behind the king are being blocked by the king itself.

Sketch Code

//safe-moves-p2/behind-king.js

let attacks;
let missing;
let game;

const FEN = '8/8/8/4k3/8/8/1Q2R3/8';

function setup() {
    Quadrille.cellLength = Chess.UISettings.BOARD_UI_SETTINGS.SQUARE_SIZE;
    Chess.UISettings.BOARD_UI_SETTINGS.BLACK_SQUARE_COLOR = '#ffffff';
    createCanvas(Chess.GAME_DIMENSIONS.WIDTH, Chess.GAME_DIMENSIONS.HEIGHT + 40);
    game = new Chess.Game(0, 0, FEN);
    game.setGameMode(Chess.E_GameMode.FREE)
    console.log(Chess)
}

function draw() {
    background(255);
    game.update();
    calculateBitboards();
    drawQuadrille(attacks,
        {
            x: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.x,
            y: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.y
        });
    drawQuadrille(missing,
        {
            x: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.x,
            y: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.y
        });

    textSize(15);
    text("🟢 We can calculate these unsafe squares \n🔴 We cannot calculate these unsafe squares behind the king",
        75,
        50);

}

function mouseClicked() {
    calculateBitboards();
}


function calculateBitboards() {
    let boardImplementation = new Chess.BoardImplementation(game.board.getFen());

    let king = boardImplementation.getPiecesOfType(Chess.E_PieceColor.Black, Chess.E_PieceType.King)[0];
    let attacksBitboard = boardImplementation.getAttackedSquares(Chess.E_PieceColor.White) & ~king.position;
    boardImplementation.removePiece(king.rank, king.file);
    let attacksWithNoKingBitboard = boardImplementation.getAttackedSquares(Chess.E_PieceColor.White) & ~king.position;
    boardImplementation.addPiece(king, king.rank, king.file);

    let missingBitboard = (attacksBitboard ^ attacksWithNoKingBitboard);

    attacks = createBitboardQuadrille(attacksBitboard);
    attacks.replace(1, color('rgba(179, 255, 179,0.7)'));
    missing = createBitboardQuadrille(missingBitboard);
    missing.replace(1, color('rgba(250,95,139,0.5)'));

}

function drawBitboard(bitboard, x, y, fill) {
    drawQuadrille(bitboard, {
        x: x,
        y: y,
        numberDisplay: ({ graphics, value, cellLength = Quadrille.cellLength } = {}) => {
            graphics.fill(color(0));
            graphics.textAlign(CENTER, CENTER);
            graphics.textSize(cellLength * Quadrille.textZoom * 0.8);
            graphics.text(fill, cellLength / 2, cellLength / 2);
        }
    });

}

function createBitboardQuadrille(bitboard) {
    let quadrille = createQuadrille(8, bitboard, 1);
    let quadrilleHeight = quadrille.height;
    if (quadrilleHeight < 8) {
        let rowsLeft = 8 - quadrilleHeight;
        for (let i = 0; i < rowsLeft; i++) {
            quadrille.insert(0);
        }
    }

    return quadrille;

}

A simple solution for this is to remove the king temporarily from the board and then calculate all the opponent’s attacks.

class MoveGenerator{
    /**
     * @param {King} king 
     * @param {bigint} enemyPieces 
     * @param {BoardImplementation} board 
     * @returns Array of moves the king can do safely
     */
    generateKingSafeMoves(king, enemyPieces, board) {
        let dangerousSquaresForKing = 0n;
        board.removePiece(king.rank, king.file);//remove king temporarily to consider squares behind the king
        let squaresAttackedByEnemy = board.getAttackedSquares(OppositePieceColor(king.color));
        board.addPiece(king, king.rank, king.file);

        dangerousSquaresForKing = squaresAttackedByEnemy;

        let kingMovesBitboard = king.GetMoves(board) & ~dangerousSquaresForKing;
        return this.#bitboardToMoves(king, kingMovesBitboard, E_MoveFlag.Regular);
    }
}

Attacks vs Moves

We need to make a distinction between piece attacks and piece moves. A piece can move to a square if the rules permit it. A piece can attack a square if 1) it can move to that square and 2) it would capture any opponent piece that was placed in that square. The important thing to understand is that not because a piece can move to a square means it can attack it. Likewise, not because a piece can attack a square means it can move to it.

This distinction is pointless for most pieces because they can always capture any piece placed in the squares they can move to. However, the pawn, as always, is a special case in which this distinction comes into play.

Sketch Code

//safe-moves-p2/pawn-attacks-moves.js

let attacks;
let moves;
let attackAndMoves;
let game;

const FEN = '8/1p3p2/8/8/2K5/8/8/8';

function setup() {
    Quadrille.cellLength = Chess.UISettings.BOARD_UI_SETTINGS.SQUARE_SIZE;
    Chess.UISettings.BOARD_UI_SETTINGS.BLACK_SQUARE_COLOR = '#ffffff';
    createCanvas(Chess.GAME_DIMENSIONS.WIDTH, Chess.GAME_DIMENSIONS.HEIGHT + 40);
    game = new Chess.Game(0, 0, FEN);
    game.setGameMode(Chess.E_GameMode.FREE)
    calculateBitboards();
}

function draw() {
    background(255);
    game.update();
    drawQuadrille(pinned,
        {
            x: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.x,
            y: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.y
        });
    drawQuadrille(moves,
        {
            x: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.x,
            y: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.y
        });
    drawQuadrille(attackAndMoves,
        {
            x: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.x,
            y: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.y
        });

    textSize(15);
    text("🟢 Pawn can move but cannot attack. King can move here. \n🔴 Pawn can attack but cannot move. King cannot move here. \n🔵 Pawn can attack and move.",
        75,
        30);

}

function mouseClicked() {
    calculateBitboards();
}

function calculateBitboards() {
    let boardImplementation = new Chess.BoardImplementation(game.board.getFen());

    let pawns = boardImplementation.getPiecesOfType(Chess.E_PieceColor.Any, Chess.E_PieceType.Pawn);
    let attacksBitboard = 0n;
    let movesBitboard = 0n;
    let attackAndMovesBitboard = 0n;

    pawns.forEach(pawn => {
        movesBitboard |= pawn.GetMoves(boardImplementation);
        attacksBitboard |= pawn.GetCapturingSquares(boardImplementation);
    });

    attackAndMovesBitboard = movesBitboard & attacksBitboard;
    movesBitboard = movesBitboard & ~attacksBitboard;
    attacksBitboard = attacksBitboard & ~attackAndMovesBitboard;

    pinned = createBitboardQuadrille(attacksBitboard);
    pinned.replace(1, color('rgba(250,95,139,0.5)'));
    moves = createBitboardQuadrille(movesBitboard);
    moves.replace(1, color('rgba(179, 255, 179,0.7)'));
    attackAndMoves = createBitboardQuadrille(attackAndMovesBitboard);
    attackAndMoves.replace(1, color('rgba(31,132,194,0.5)'));
}

function drawBitboard(bitboard, x, y, fill) {
    drawQuadrille(bitboard, {
        x: x,
        y: y,
        numberDisplay: ({ graphics, value, cellLength = Quadrille.cellLength } = {}) => {
            graphics.fill(color(0));
            graphics.textAlign(CENTER, CENTER);
            graphics.textSize(cellLength * Quadrille.textZoom * 0.8);
            graphics.text(fill, cellLength / 2, cellLength / 2);
        }
    });

}

function createBitboardQuadrille(bitboard) {
    let quadrille = createQuadrille(8, bitboard, 1);
    let quadrilleHeight = quadrille.height;
    if (quadrilleHeight < 8) {
        let rowsLeft = 8 - quadrilleHeight;
        for (let i = 0; i < rowsLeft; i++) {
            quadrille.insert(0);
        }
    }

    return quadrille;

}

As we can see, just obtaining the squares a piece can move to is not a perfect metric for calculating dangerous squares. But, we are going to be lazy and take advantage of the fact that this just applies to pawns.

So, we’ll add a method in the Pawn class that returns the squares the pawn attacks separately from the ones it can move to. Then, we’ll check for this special case in the previous routine.

class BoardImplementation{
    /**
     * @param {E_PieceColor} pieceColor 
     * @param {E_PieceType} pieceType 
     * @returns Bitboard with squares being attacked by pieces of given characteristics 
     */
    getAttackedSquares(pieceColor = E_PieceColor.Any, pieceType = E_PieceType.Any) {
        let attacksBitboard = 0n;
        //for every piece of given characteristics
        let pieces = this.getPiecesOfType(pieceColor, pieceType);
        pieces.forEach(piece => {
            let pieceAttackMoves;
            pieceAttackMoves = piece.GetMoves(this);
            //if not a pawn,get regular moves
        if (piece.GetType() !== E_PieceType.Pawn) {
            pieceAttackMoves = piece.GetMoves(this);
        } //otherwise, get squares that pawn would capture if there was a piece there
        else {
            pieceAttackMoves = piece.GetCapturingSquares();
        }
        });

        return attacksBitboard;
    }
}

class Pawn{
    GetCapturingSquares() {
        let rightDiagonalSquare;
        let leftDiagonalSquare;

        //calculate destination squares based on color 
        switch (this.color) {
            case E_PieceColor.White:
                rightDiagonalSquare = (this.position << 7n);
                leftDiagonalSquare = (this.position << 9n);
                break;
            case E_PieceColor.Black:
                rightDiagonalSquare = (this.position >> 9n);
                leftDiagonalSquare = (this.position >> 7n);
                break;
            default:
                throw new Error("No color specified");
        }

        let rightCapture = rightDiagonalSquare &
            ~getFile(1); //remove right capture from 8th file to 1st file

        let leftCapture = leftDiagonalSquare &
            ~getFile(8); //remove right capture from 1st file to 8th file

        return rightCapture | leftCapture;
    }
}

If we had more pieces whose moves and attacks differ, we may have to rethink how to implement this.

Dangerous captures

Let’s recall from previous devlogs that any square where there’s an ally piece is excluded from possible moves. Of course, a general rule is that a piece cannot move to squares occupied by pieces of the same color. However, this is problematic to our code because we cannot calculate protected pieces.

A piece is protected if, after being captured, we can recapture the opponent piece in the next move, as explained in this article [2].

Here’s an example of protected pieces:

Sketch Code

//safe-moves-p2/protected-pieces.js

let game;

const FEN = '1rb1k3/6r1/n3n3/1Qp1ppB1/2P3P1/8/P3B2P/1R2K1N1';
let whiteProtectedPieces = 0n;
let blackProtectedPieces = 0n;

function setup() {
    Quadrille.cellLength = Chess.UISettings.BOARD_UI_SETTINGS.SQUARE_SIZE;
    Chess.UISettings.BOARD_UI_SETTINGS.BLACK_SQUARE_COLOR = '#ffffff';
    createCanvas(Chess.GAME_DIMENSIONS.WIDTH - Chess.UISettings.MOVE_RECORD_UI_SETTINGS.WIDTH,
        Chess.GAME_DIMENSIONS.HEIGHT + 50);
    game = new Chess.Game(0, 75, FEN);
    game.setGameMode(Chess.E_GameMode.VIEW_ONLY);
    whiteProtectedPieces = createBitboardQuadrille(0x4022000848n);
    whiteProtectedPieces.replace(1, color('rgba(255, 212, 92,0.5)'));
    blackProtectedPieces = createBitboardQuadrille(0x6002882000000000n);
    blackProtectedPieces.replace(1, color('rgba(92, 135, 255,0.5)'));
}

function draw() {
    background(255);
    game.update();
    drawQuadrille(whiteProtectedPieces,
        {
            x: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.x,
            y: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.y + 75
        });
    drawQuadrille(blackProtectedPieces,
        {
            x: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.x,
            y: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.y + 75
        });
    textSize(15);
    text("🟡 Protected white pieces. \n🔵 Protected black pieces.",
        100,
        40);

}

function createBitboardQuadrille(bitboard) {
    let quadrille = createQuadrille(8, bitboard, 1);
    let quadrilleHeight = quadrille.height;
    if (quadrilleHeight < 8) {
        let rowsLeft = 8 - quadrilleHeight;
        for (let i = 0; i < rowsLeft; i++) {
            quadrille.insert(0);
        }
    }

    return quadrille;

}

This means the king cannot capture protected pieces because the opponent could recapture the king in the next move. These dangerous captures must be excluded from the possible moves of the king.

    /**
     * @param {King} king 
     * @param {Piece[]} enemyPieces 
     * @param {BoardImplementation} board 
     * @returns Array of moves the king can do safely
     */
    generateKingSafeMoves(king, enemyPieces, board) {
        let dangerousSquaresForKing = 0n;

        board.removePiece(king.rank, king.file);//remove king temporarily to consider squares behind the king
        let squaresAttackedByEnemy = board.getAttackedSquares(OppositePieceColor(king.color));
        let dangerouseCaptures = this.#calculateProtectedPieces(enemyPieces, board);
        board.addPiece(king, king.rank, king.file);

        dangerousSquaresForKing = dangerouseCaptures | squaresAttackedByEnemy;

        let kingMovesBitboard = king.GetMoves(board) & ~dangerousSquaresForKing;
        return this.#bitboardToMoves(king, kingMovesBitboard, E_MoveFlag.Regular);
    }

The calculateProtectedPieces method returns a bitboard with every square where there’s a protected piece. We can merge this bitboard with the bitboard of attacked squares to get all squares that the king cannot move to.

class MoveGenerator{
    /**
     * @param {King} king 
     * @param {Piece[]} enemyPieces 
     * @param {BoardImplementation} board 
     * @returns Bitboard of enemy pieces that are protected (i.e the enemy can recapture if they are captured)
     */
    calculateProtectedPieces(enemyPieces, board) {
        let protectedPieces = 0n;
        //for every enemy piece
        for (let enemyPiece of enemyPieces) {
            let rawAttacks = enemyPiece.getRawAttacks();
            let allyPieces = board.getOccupied(enemyPiece.color)
            protectedPieces |= rawAttacks & allyPieces;
        }

        return protectedPieces;
    }
} 
class Piece{
    getRawAttacks(){
        //...implement in derived classes
    }
}

To implement this method, we’ll calculate attacks normally. But this time we won’t exclude ally pieces. We’ll call these raw** moves**. Then, we’ll get the intersection between raw moves and the position of allied pieces. This way, we get every piece that is in a square attacked by a piece of the same color or, in other words, a protected piece.

The nuances we mentioned in the previous section about attacks and moves also apply here. Protected pieces are placed in squares that we can attack, not necessarily move to.

Pinned pieces

Obtaining pinned pieces is not as simple as one might think. An initial idea would be to intersect the opponent’s moves with the position of our pieces. However, as we can see in the following sketch, this is not always the case.

Sketch Code

//safe-moves-p2/pinned-initial.js

let pinned;
let slidingAttacks;
let game;

const FEN = 'R3p1kr/5n2/3N2p1/6b1/8/8/1B6/4K1R1';
function setup() {
    Quadrille.cellLength = Chess.UISettings.BOARD_UI_SETTINGS.SQUARE_SIZE;
    Chess.UISettings.BOARD_UI_SETTINGS.BLACK_SQUARE_COLOR = '#ffffff';
    createCanvas(Chess.GAME_DIMENSIONS.WIDTH - Chess.UISettings.MOVE_RECORD_UI_SETTINGS.WIDTH,
        Chess.GAME_DIMENSIONS.HEIGHT + 50);
    game = new Chess.Game(0, 75, FEN, Chess.E_PieceColor.Black);
    game.setGameMode(Chess.E_GameMode.VIEW_ONLY);
    calculatePinned();
}

function draw() {
    background(255);
    game.update();
    drawQuadrille(pinned,
        {
            x: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.x,
            y: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.y + 75
        });
    drawQuadrille(slidingAttacks,
        {
            x: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.x,
            y: Chess.UISettings.BOARD_UI_SETTINGS.LOCAL_POSITION.y + 75
        });

    textSize(15);
    text('🟡 Sliding attacks. \n🔴 "Pinned pieces"',
        100,
        40);

}

function mouseClicked() {
    calculatePinned();
}

function calculatePinned() {
    let boardImplementation = new Chess.BoardImplementation(game.board.getFen());

    let blackOccupied = boardImplementation.getOccupied(Chess.E_PieceColor.Black, Chess.E_PieceType.Any);
    let whiteOccupied = boardImplementation.getAttackedSquares(Chess.E_PieceColor.White, Chess.E_PieceType.Any);
    let whitePieces = boardImplementation.getPiecesOfType(Chess.E_PieceColor.White, Chess.E_PieceType.Any);

    let slidingAttacksBitboard = 0n;
    whitePieces.forEach(whitePiece => {
        if (whitePiece.IsSlider()) {
            slidingAttacksBitboard |= whitePiece.GetMoves(boardImplementation);
        }
    });
    slidingAttacksBitboard = slidingAttacksBitboard & ~blackOccupied;

    let pinnedBitboard = blackOccupied & whiteOccupied;

    pinned = createBitboardQuadrille(pinnedBitboard);
    pinned.replace(1, color('rgba(250,95,139,0.5)'));
    slidingAttacks = createBitboardQuadrille(slidingAttacksBitboard);
    slidingAttacks.replace(1, color('rgba(255, 212, 92,0.5)'));
}

function drawBitboard(bitboard, x, y, fill) {
    drawQuadrille(bitboard, {
        x: x,
        y: y,
        numberDisplay: ({ graphics, value, cellLength = Quadrille.cellLength } = {}) => {
            graphics.fill(color(0));
            graphics.textAlign(CENTER, CENTER);
            graphics.textSize(cellLength * Quadrille.textZoom * 0.8);
            graphics.text(fill, cellLength / 2, cellLength / 2);
        }
    });

}

function createBitboardQuadrille(bitboard) {
    let quadrille = createQuadrille(8, bitboard, 1);
    let quadrilleHeight = quadrille.height;
    if (quadrilleHeight < 8) {
        let rowsLeft = 8 - quadrilleHeight;
        for (let i = 0; i < rowsLeft; i++) {
            quadrille.insert(0);
        }
    }

    return quadrille;

}

We observe three inaccuracies here:

The black knight. Non-sliding pieces cannot create pinned pieces.
The black rook. The king and the pinned piece must be in the attacking direction of the slider.
The black bishop. There must be one piece between the king and the slider. More than one piece means there are no pinned pieces.

In conclusion, using regular moves is not the answer to the problem. We’ll look at another approach.

Opposite-ray attacks

This technique is explained in the Chess Programming Wiki 3].

Let’s say we have a slider and a king within the same ray. This ray could be a rank, a file, a diagonal, or an antidiagonal.

Now, imagine the king has grown some balls and decided to attack the opponent with a sliding ray in the opposite direction.

The idea is that we can obtain information about pinned pieces by calculating the intersection between the attacks of the sliding piece and the imaginary attacks of the king. There are 3 cases:

No pieces between the king and the rook.

The intersection might have two values in this case. It will be equal to zero if the slider is right next to the king. Otherwise, it’ll be equal to a bitboard with the empty squares between the king and the rook.

One piece between the king and the rook

In this case, the opposite rays intersect in the piece between, resulting in an intersection with one bit. If this piece is the same color as the king, we have a pinned piece.

Two or more pieces between the king and the rook

In this case, both rays never intersect and the intersection equals zero.

The following sketch lets you simulate these three scenarios and see the results.

Sketch Code

//safe-moves-p2/opposite-rays.js

let board;
let auxiliaryBoard;
let kingAttacks;
let rookAttacks;
let intersection;

const FEN = '8/8/8/8/K6r/8/8/8';
const rows = 24;
const columns = 20;
const blackRookSymbol = Quadrille.chessSymbols['r'];
const whiteRookSymbol = Quadrille.chessSymbols['R'];
const whiteKingSymbol = Quadrille.chessSymbols['K'];
const whitePawnSymbol = Quadrille.chessSymbols['P'];


function setup() {
    Quadrille.cellLength = 25;
    createCanvas(columns * Quadrille.cellLength, rows * Quadrille.cellLength);
    board = createQuadrille(FEN);
    auxiliaryBoard = createQuadrille(FEN).replace(whiteKingSymbol, whiteRookSymbol);

    calculateBitboards();
}

function draw() {
    background(255);
    drawQuadrille(board, { row: 4, col: 1 })
    drawBitboard(kingAttacks, 4, 10, 1);
    drawBitboard(rookAttacks, 14, 1, 1);
    drawBitboard(intersection, 14, 10, 1);

    textAlign(CENTER, TOP);
    textStyle(BOLD);
    textSize(15);
    rectMode(CENTER);
    text("Click 'Board' quadrille to add pawns.  See results.",
        columns * Quadrille.cellLength / 2,
        25,
        columns * Quadrille.cellLength);
    text("Board", 5 * Quadrille.cellLength, 3 * Quadrille.cellLength);
    text("King Attacks", 14 * Quadrille.cellLength, 3 * Quadrille.cellLength);
    text("Rook Attacks", 5 * Quadrille.cellLength, 13 * Quadrille.cellLength);
    text("Intersection", 14 * Quadrille.cellLength, 13 * Quadrille.cellLength);
    rectMode(CORNER);
    textStyle(NORMAL);
}


function mouseClicked() {
    let cellContent = board.read(board.mouseRow, board.mouseCol);
    if (cellContent !== undefined) {
        if (cellContent == null) {
            board.fill(board.mouseRow, board.mouseCol, whitePawnSymbol);
            auxiliaryBoard.fill(board.mouseRow, board.mouseCol, whitePawnSymbol);
        } else if (cellContent !== whiteKingSymbol && cellContent !== blackRookSymbol) {
            board.clear(board.mouseRow, board.mouseCol);
            auxiliaryBoard.clear(board.mouseRow, board.mouseCol);
        }
        calculateBitboards();
    }
}


function calculateBitboards() {

    let boardImplementation = new Chess.BoardImplementation(auxiliaryBoard.toFEN());

    let whiteRook = boardImplementation.getPiecesOfType(Chess.E_PieceColor.White, Chess.E_PieceType.Rook)[0];
    let blackRook = boardImplementation.getPiecesOfType(Chess.E_PieceColor.Black, Chess.E_PieceType.Rook)[0];

    let rankBitboard = Chess.BitboardUtils.getRank(4);
    let kingAttacksBitboard = Chess.BitboardUtils.hyperbolaQuintessenceAlgorithm(boardImplementation.getOccupied(), whiteRook.position, rankBitboard).wholeRay;
    let rookAttacksBitboard = Chess.BitboardUtils.hyperbolaQuintessenceAlgorithm(boardImplementation.getOccupied(), blackRook.position, rankBitboard).wholeRay;

    kingAttacks = createBitboardQuadrille(kingAttacksBitboard);
    rookAttacks = createBitboardQuadrille(rookAttacksBitboard);
    intersection = createBitboardQuadrille(kingAttacksBitboard & rookAttacksBitboard);
}

function drawBitboard(bitboard, row, col, fill) {
    drawQuadrille(bitboard, {
        row: row,
        col: col,
        numberDisplay: ({ graphics, value, cellLength = Quadrille.cellLength } = {}) => {
            graphics.fill(color(0));
            graphics.textAlign(CENTER, CENTER);
            graphics.textSize(cellLength * Quadrille.textZoom * 0.8);
            graphics.text(fill, cellLength / 2, cellLength / 2);
        }
    });

}

function createBitboardQuadrille(bitboard) {
    let quadrille = createQuadrille(8, bitboard, 1);
    let quadrilleHeight = quadrille.height;
    if (quadrilleHeight < 8) {
        let rowsLeft = 8 - quadrilleHeight;
        for (let i = 0; i < rowsLeft; i++) {
            quadrille.insert(0);
        }
    }

    return quadrille;

}

To recapitulate, the steps we’ll take to calculate pinned pieces and address the previous issues are:

Check if the piece is a slider. If not, we skip.
Calculate a ray between the king and the sliding piece. If such a ray is not possible, we skip.
Calculate pinned pieces in the obtained ray with the previous technique.

Step One

The first step is easy.

/**
     * @param {King} king 
     * @param {Piece[]} enemyPieces 
     * @param {BoardImplementation} board 
     * @returns Object with pinned pieces and the filters for their moves
     */
    calculatePinnedPieces(king, enemyPieces, board) {
        let moveFilterForPinnedPieces = {};
        //for every enemy piece
        for (let enemyPiece of enemyPieces) {
            //if it is not a slider, it cannot pin pieces
            if (!enemyPiece.IsSlider()) continue;
        }
        return moveFilterForPinnedPieces;
    }

Step Two

For the second step, we’ll use the getRay function we mentioned earlier.

/**
     * @param {King} king 
     * @param {Piece[]} enemyPieces 
     * @param {BoardImplementation} board 
     * @returns Object with pinned pieces and the filters for their moves
     */
    calculatePinnedPieces(king, enemyPieces, board) {
        let moveFilterForPinnedPieces = {};
        //for every enemy piece
        for (let enemyPiece of enemyPieces) {
            //if it is not a slider, it cannot pin pieces
            if (!enemyPiece.IsSlider()) continue;
            
            let slider = enemyPiece;
            let rayFromSliderToKing = getRay(slider.rank, slider.file, king.rank, king.file, false, false);

            //if there's no  ray between slider and king:
            //1) king is not within slider's attack range
            //2) slider is besides the king. There's no pinned pieces
            //then, continue.
            if (rayFromSliderToKing === 0n) continue;

        }
        return moveFilterForPinnedPieces;
    }

The function returns a ray between the square of the sliding piece and the square of the king, excluding both squares from the ray. If this ray is equal to zero, it could mean that there’s no possible ray between those squares or that the sliding piece is right next to the king. In both cases, no pinned pieces are possible.

A middle step is to make sure the sliding piece can actually move in the ray we calculated. It’s pointless to calculate pinned pieces in a diagonal ray for a rook because it cannot attack in that direction.

/**
     * @param {King} king 
     * @param {Piece[]} enemyPieces 
     * @param {BoardImplementation} board 
     * @returns Object with pinned pieces and the filters for their moves
     */
    calculatePinnedPieces(king, enemyPieces, board) {
        let moveFilterForPinnedPieces = {};
        //for every enemy piece
        for (let enemyPiece of enemyPieces) {
            //if it is not a slider, it cannot pin pieces
            if (!enemyPiece.IsSlider()) continue;
            
            let slider = enemyPiece;
            let rayFromSliderToKing = getRay(slider.rank, slider.file, king.rank, king.file, false, false);
            
            //if there's no  ray between slider and king:
            //1) king is not within slider's attack range
            //2) slider is besides the king. There's no pinned pieces
            //then, continue.
            if (rayFromSliderToKing === 0n) continue;

            //calculate if slider is allowed to move on the ray to the king
            let sliderRays = slider.getSlidingRays();
            let isSliderAllowedToMoveOnRay = false;
            for (let ray of sliderRays) {
                if ((ray & rayFromSliderToKing) > 0n) {
                    isSliderAllowedToMoveOnRay = true;
                }
            }
            //if slider is not allowed to move on the ray to the king, king is not within slider's attack range, continue. 
            if (!isSliderAllowedToMoveOnRay) continue;

        }
        return moveFilterForPinnedPieces;
    }

We go through every ray the slider can traverse, and check if the intersection between the sliding ray and the ray we calculated is empty. If it is not empty, the slider can move in that direction.

Step Three

Let’s apply the trick we explained earlier.

    /** 
     * @param {King} king 
     * @param {Piece[]} enemyPieces 
     * @param {BoardImplementation} board 
     * @returns Object with pinned pieces and the filters for their moves
     */
    calculatePinnedPieces(king, enemyPieces, board) {
        let moveFilterForPinnedPieces = {};
        //for every enemy piece
        for (let enemyPiece of enemyPieces) {
            //...
            //calculate pinned pieces
            let attacksFromSliderToKing = hyperbolaQuintessenceAlgorithm(board.getOccupied(), slider.position, rayFromSliderToKing);
            let attacksFromKingToSlider = hyperbolaQuintessenceAlgorithm(board.getOccupied(), king.position, ray-FromSliderToKing);
            let emptySpaceBetweenKingAndSlider = rayFromSliderToKing;
            let intersection = attacksFromKingToSlider.wholeRay & attacksFromSliderToKing.wholeRay;

            //if there's no intersection
            if (intersection === 0n) {
                //There are two or more pieces in between slider and king. Therefore, there are not pinned pieces.
            } //else if the intersection is equal to empty spaces
            else if (intersection === emptySpaceBetweenKingAndSlider) {
                //There's no pieces in between slider and king. Slider is distant-cheking the king.
            } else {
                //There's one piece in between slider and king
                //if the piece is an ally
                let isPieceAnAlly = (intersection & board.getOccupied(king.color)) > 0n;
                if (isPieceAnAlly) {
                    //piece is being pinned by the slider.
                    //piece can only move in the ray from the slider to the king to avoid discovering a check
                    moveFilterForPinnedPieces[intersection] = rayFromSliderToKing | slider.position;
                }
            }
        }
        return moveFilterForPinnedPieces;
    }

The hyperbolaQuintessenceAlgorithm method wraps up the logic we explained for calculating sliding moves. We check the conditions for each case. If the intersection has one bit, we check if it has the same color as the king by intersecting with a bitboard with squares occupied by pieces of the king’s color.

Finally, the way we filter pinned pieces moves is by limiting them to the attack direction of the slider.

Small oopsie

There’s a particular situation in which this algorithm fails miserably. When we have a sequence of slider-piece-king right next to each other, the intersection is equal to a bitboard with the empty squares between the king and the rook. But this is not the correct result because there’s indeed one piece between the king and the rook.

We can solve this with a small fix:

    else if ((intersection & board.getEmptySquares()) === emptySpaceBetweenKingAndSlider) {
        //There's no pieces in between slider and king. Slider is distant-cheking the king.
    }

This tweak works for this edge case only. For every other case, the conditional will work as it’s supposed to.

Conclusion

The logic we have built here is not intuitive at all. At least it took me quite some time to understand and apply these techniques. Take your time to review the code line by line and let it sink in. Grab a notebook and make some handmade sketches that help you understand what the code is doing.

References

[1] MuhammadFarag. (2022, January 29). Overthinking overthinker GIF. Tenor. https://tenor.com/es/view/overthinking-overthinker-vapour-confusion-confused-gif-24689422
[2] Attacking and protecting pieces. Learn.Chess (n.d.). https://learn.chessbase.com/en/page/attacking-and-protecting-pieces
[3] Checks and pinned pieces (bitboards). Chessprogramming wiki. (2022, April 4). https://www.chessprogramming.org/Checks_and_Pinned_Pieces_(Bitboards)