Piece Rules: Sliders

May 23, 2024

Introduction

We will develop the rules for a couple of pieces at once in this devlog. According to ChessProgramming Wiki: “Sliding Pieces can move an indefinite number of squares along a horizontal, vertical, or diagonal line until the edge of the board or another piece obstructs the ray of a line.” [1]. This definition includes bishops, queens, and rooks.

So, in order to implement sliding pieces and add them to the game, we need to solve a single problem: calculate a bitboard that contains a continuous ray alongside a direction that stops at a certain square.

Now, let’s start with solving a simple case and then make up our way to the whole solution progressively. Let’s say we want to calculate a horizontal ray between two squares on the same rank.

Before diving directly into the code, try to think about how you would solve the problem yourself. You are given two bitboards that represent the start and destination square, and you have to calculate a ray between both. Your job is to implement the following function:

/** 
 * @param {bigint} startSquare
 * @param {bigint} destinationSquare
 * @returns {bigint} Ray between start and destination square
*/
getHorizontalRay(startSquare, destinationSquare){
    //your code goes here...
}

You can start by using some of the techniques we learned in the previous devlog.

Exercise
Implement the getHorizontalRay function.

Using bit shifting

In the previous devlog, we learned that a bit can be translated across a bitboard by using bit shifting. The same idea can be applied here.

/** 
 * @param {bigint} startSquare
 * @param {bigint} destinationSquare
 * @returns {bigint} Ray between start and destination square
*/
getHorizontalRay(startSquare, destinationSquare){
    let ray = 0n;
    //incrementally add bits to the ray
    let i = 0;
    while(true){
        let shiftedBit = startSquare << BigInt(1*i);
        ray = ray | shiftedBit;
        i++;
    }

    return ray;
}

We incrementally build the ray by shifting the start square bit in one direction until we reach the destination bit.

The ’|’ operator [2] will perform a merge between the bitboard we have so far and the newly shifted bit.

This code is missing the stopping condition for the loop. We will stop when the shifted bit equals the destination square, meaning we reached the destination.

/** 
 * @param {bigint} startSquare
 * @param {bigint} destinationSquare
 * @returns {bigint} Ray between start and destination square
*/
getHorizontalRay(startSquare, destinationSquare){
    let ray = 0n;
   
    let i = 0;
    let shiftedBit = 0n;
    //while we are not at the destination
    while(shiftedBit !== destinationSquare){
         //incrementally add bits to the ray
        shiftedBit = startSquare << BigInt(1*i);
        ray = ray | shiftedBit;
        i++;
    }

    return ray;
}

This way, we move the start square towards the destination while adding bits to the ray as we go. But there’s a catch, this only works for rays going from right to left because we are performing a left bit shift. Hence, we need to account for the other case.

/** 
 * @param {bigint} startSquare
 * @param {bigint} destinationSquare
 * @returns {bigint} Ray between start and destination square
*/
getHorizontalRay(startSquare, destinationSquare){
    let ray = 0n;
    
    let i = 0;
    let shiftedBit = 0n;
    //while we are not at the destination
    while(shiftedBit !== destinationSquare){
        //incrementally add bits to the ray
        if(startSquare < destinationSquare){
            //destination is to the left
            shiftedBit = startSquare << BigInt(1*i);
        }else{
            //destination is to the right
            shiftedBit = startSquare >> BigInt(1*i);
        }

        ray = ray | shiftedBit;
        i++;
    }

    return ray;
}

If a binary number is greater than another, its most significant bit will surely be to the left than the most significant bit of the second number. Otherwise, if it is less, its most significant bit will surely be to the right. This only applies to bitboard with one bit, though. Here’s an example of that:

Code

//sliding-devlog/msb-example.js

let firstBitboard;
let number1;
let secondBitboard;
let number2;

function setup() {
    Quadrille.cellLength = 50;
    createCanvas(8 * Quadrille.cellLength, 5 * Quadrille.cellLength);
    firstBitboard = createQuadrille([1, 0, 0, 0]);
    number1 = 8;
    secondBitboard = createQuadrille([0, 0, 0, 1]);
    number2 = 2;
}

function draw() {
    background(255);
    drawBitboard(firstBitboard, 1, 2);
    drawBitboard(secondBitboard, 3, 2)


    textSize(15);
    textAlign(CENTER, TOP);
    textStyle(BOLD);
    text('Click squares to set bits', Quadrille.cellLength * 8 * 0.5, Quadrille.cellLength * 0.25);

    textStyle(NORMAL);
    text('Destination', 1 * Quadrille.cellLength, Quadrille.cellLength * 1.5);
    text('Start', 1 * Quadrille.cellLength, 3.5 * Quadrille.cellLength);

    textAlign(LEFT, TOP);
    textSize(20);
    text('= ' + number1, 6.5 * Quadrille.cellLength, Quadrille.cellLength * 1.5);
    text('= ' + number2, 6.5 * Quadrille.cellLength, 3.5 * Quadrille.cellLength);
    text('= ' + number2, 6.5 * Quadrille.cellLength, 3.5 * Quadrille.cellLength);

    textSize(15);
    textAlign(CENTER, TOP);
    let resultText = "Destination is to the " + (number1 >= number2 ? "left" : "right") + " of the start square";
    text(resultText, Quadrille.cellLength * 8 * 0.5, Quadrille.cellLength * 4.5);

}

function mouseClicked() {
    if (firstBitboard.read(firstBitboard.mouseRow, firstBitboard.mouseCol) !== undefined) {
        firstBitboard.replace(1, 0);
        firstBitboard.fill(firstBitboard.mouseRow, firstBitboard.mouseCol, 1);
        number1 = Math.pow(2, (4 - firstBitboard.mouseCol));
    } else if (secondBitboard.read(secondBitboard.mouseRow, secondBitboard.mouseCol) !== undefined) {
        secondBitboard.replace(1, 0);
        secondBitboard.fill(secondBitboard.mouseRow, secondBitboard.mouseCol, 1)
        number2 = Math.pow(2, (4 - secondBitboard.mouseCol));
    }
}

function drawBitboard(bitboard, row, col) {
    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(value, cellLength / 2, cellLength / 2);
        }
    });

}

Here’s the result of the code:

Code

//sliding-devlog/bit-shifting.js

let firstBitboard;
let secondBitboard;
let result;
function setup() {
    Quadrille.cellLength = 50;
    createCanvas(7 * Quadrille.cellLength, 6 * Quadrille.cellLength + 25);
    occupiedBitboard = createQuadrille([1, 0, 0, 0]);
    slidingBitboard = createQuadrille([0, 0, 0, 1]);
    result = getResult();
}

function draw() {
    background(255);
    drawBitboard(occupiedBitboard, 1, 0);
    drawBitboard(slidingBitboard, 3, 0);
    drawBitboard(result, 5, 0);

    textSize(15);
    textAlign(CENTER, TOP);
    textStyle(BOLD);
    text('Click squares to set bits. See resulting ray', Quadrille.cellLength * 7 * 0.5, Quadrille.cellLength * 0.25);

    textAlign(LEFT, TOP);
    textSize(15);
    textStyle(NORMAL);
    text('bitboard 1', 4.5 * Quadrille.cellLength, 1.5 * Quadrille.cellLength);
    text('bitboard 2', 4.5 * Quadrille.cellLength, 3.5 * Quadrille.cellLength);
    text('ray', 4.5 * Quadrille.cellLength, 5.5 * Quadrille.cellLength);

}

function mouseClicked() {
    if (occupiedBitboard.read(occupiedBitboard.mouseRow, occupiedBitboard.mouseCol) !== undefined) {
        occupiedBitboard.replace(1, 0);
        occupiedBitboard.fill(occupiedBitboard.mouseRow, occupiedBitboard.mouseCol, 1);
    } else if (slidingBitboard.read(slidingBitboard.mouseRow, slidingBitboard.mouseCol) !== undefined) {
        slidingBitboard.replace(1, 0);
        slidingBitboard.fill(slidingBitboard.mouseRow, slidingBitboard.mouseCol, 1)
    }
    result = getResult();
}

function getResult() {
    occupiedBitboard.replace(0, null);
    let bitboard1 = occupiedBitboard.toBigInt();
    occupiedBitboard.replace(null, 0);
    slidingBitboard.replace(0, null);
    let bitboard2 = slidingBitboard.toBigInt();
    slidingBitboard.replace(null, 0);
    let ray = getHorizontalRay(bitboard1, bitboard2);
    let quadrille = new Quadrille(4, ray, 1);
    quadrille.replace(null, 0)
    return quadrille;
}

/**
 * @param {bigint} startSquare
 * @param {bigint} destinationSquare
 * @returns {bigint} Ray between start and destination square
*/
function getHorizontalRay(startSquare, destinationSquare) {
    let ray = 0n;
    //incrementally add bits to the ray
    let i = 0;
    let shiftedBit = 0n;
    while (shiftedBit !== destinationSquare) {

        if (startSquare < destinationSquare) {
            //destination is to the left
            shiftedBit = startSquare << BigInt(1 * i);
        } else {
            //destination is to the right
            shiftedBit = startSquare >> BigInt(1 * i);
        }

        ray = ray | shiftedBit;
        i++;
    }

    return ray;
}

function drawBitboard(bitboard, row, col) {
    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(value, cellLength / 2, cellLength / 2);
        }
    });

}

How does this apply to vertical and diagonal rays? Well, the logic stays the same. We just have to shift a different number of times to get to the proper square. Also, we can make it work by passing the bitboard with occupied squares instead of passing the destination square to the function.

I encourage you to implement the other two functions for vertical and diagonal rays.

Exercise
Implement the getVerticalRay and getDiagonalRay function.

The o^(o-2r)-trick

A neat trick to easily get sliding rays from one bit to another is to use bit subtraction.

Bit propagation

Do you remember your math classes back in school? Maybe not, but let me give you a fresh reminder. When we subtract two numbers, it is usual that a number needs to borrow a unit from the next number so the subtraction can be performed.


Borrowing when doing a subtraction. Taken from [3]

Well, the exact same happens when working with binary numbers. Except it’s ten times easier because you only have 0’s and 1’s.


Borrowing when doing a binary subtraction. Taken from [4]

When doing a binary subtraction, an interesting phenomenon occurs where “on” bits (bits set to 1) propagate in the difference. Look at this subtraction:

$$ \begin{align*} &01000000 \newline -\ &\underline{00000010} \newline &00111110 \end{align*} $$

“On” bits are repeated in the difference on every place there is an “off” bit (bit set to zero) in the minuend. The propagation stops at the minuend’s first “on” bit. If we think of the minuend as the occupied bitboard of a chessboard, and the subtrahend as a sliding piece, we can observe how similar the result is to the moves of a sliding piece. The incomplete equation would be:

$$ s = o - r \newline s:\text{sliding moves} \quad o:\text{occupied} \quad r:\text{sliding piece} $$

Now let’s see how that would look on a bitboard.

Code

//sliding-devlog/bit-propagation.js

let occupiedBitboard;
let slidingBitboard;
let result;

function setup() {
    Quadrille.cellLength = 25;
    createCanvas(19 * Quadrille.cellLength, 22 * Quadrille.cellLength);
    occupiedBitboard = createQuadrille(8, 0x1000804200000010n, 1);

    slidingBitboard = createQuadrille(8, 8);
    slidingBitboard.fill(4, 5, 1);

    result = getResult();
}

function draw() {
    background(255);
    drawBitboard(occupiedBitboard, 3, 1, Quadrille.chessSymbols['p']);
    drawBitboard(slidingBitboard, 3, 10, Quadrille.chessSymbols['R']);
    drawBitboard(result, 13, 5, 1);

    textSize(15);
    textAlign(CENTER, TOP);
    textStyle(BOLD);
    text('Click "sliding piece" bitboard to change its position. See result', Quadrille.cellLength * 19 * 0.5, Quadrille.cellLength * 0.5);

    textStyle(NORMAL);
    text("Occupied", Quadrille.cellLength * 5, Quadrille.cellLength * 2);
    text("Sliding Piece", Quadrille.cellLength * 14, Quadrille.cellLength * 2);
    text("Result", Quadrille.cellLength * 9, Quadrille.cellLength * 12);
}

function mouseClicked() {
    if (slidingBitboard.read(slidingBitboard.mouseRow, slidingBitboard.mouseCol) !== undefined) {
        slidingBitboard.replace(1, null);
        slidingBitboard.fill(slidingBitboard.mouseRow, slidingBitboard.mouseCol, 1);
    }
    result = getResult();
}

function getResult() {
    let bitboard1 = occupiedBitboard.toBigInt();
    let bitboard2 = slidingBitboard.toBigInt();
    let result = bitboard1 - bitboard2;
    if (result < 0) result = BigInt.asUintN(64, result);
    let quadrille = createBitboardQuadrille(result);
    return quadrille;
}
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;

}

As we can see, “on” bits are propagated from the square of the sliding piece to the next occupied square.

Sliding mask

If we now apply a bit mask in the direction of movement, we get a bitboard with the moves of the sliding piece in such direction.

$$ s = (o - r) \cap m \newline s:\text{sliding moves} \quad o:\text{occupied} \quad r:\text{sliding piece} \quad m:\text{mask} $$

Code

//sliding-devlog/mask.js

let occupiedBitboard;
let slidingBitboard;
let mask;
let result;

function setup() {
    Quadrille.cellLength = 25;
    createCanvas(19 * Quadrille.cellLength, 22 * Quadrille.cellLength);
    occupied = createQuadrille(8, 0x1000804200000010n, 1);

    slidingPiece = createQuadrille(8, 8);
    slidingPiece.fill(4, 5, 1);

    mask = getMask();
    maskedResult = getResult();
}

function draw() {
    background(255);
    drawBitboard(occupied, 3, 1, Quadrille.chessSymbols['p']);
    drawBitboard(slidingPiece, 3, 10, Quadrille.chessSymbols['R']);
    drawBitboard(mask, 13, 1, 1);
    drawBitboard(maskedResult, 13, 10, 1);

    textSize(15);
    textAlign(CENTER, TOP);
    textStyle(BOLD);
    text('Click "sliding piece" bitboard to change its position. See results', Quadrille.cellLength * 19 * 0.5, Quadrille.cellLength * 0.5);

    textStyle(NORMAL);
    text("Occupied", Quadrille.cellLength * 5, Quadrille.cellLength * 2);
    text("Sliding Piece", Quadrille.cellLength * 14, Quadrille.cellLength * 2);
    text("Mask", Quadrille.cellLength * 5, Quadrille.cellLength * 12);
    text("Result", Quadrille.cellLength * 14, Quadrille.cellLength * 12);
}

function mouseClicked() {
    if (slidingPiece.read(slidingPiece.mouseRow, slidingPiece.mouseCol) !== undefined) {
        slidingPiece.replace(1, null);
        slidingPiece.fill(slidingPiece.mouseRow, slidingPiece.mouseCol, 1);
    }
    mask = getMask();
    maskedResult = getResult();
}

function getResult() {
    let bitboard1 = occupied.toBigInt();
    let bitboard2 = slidingPiece.toBigInt();
    let result = bitboard1 - bitboard2;
    if (result < 0) result = BigInt.asUintN(64, result);
    let quadrille = createQuadrille(8, result, 1);
    quadrille = Quadrille.and(quadrille, mask);
    return quadrille;
}

function getMask() {
    let bitboard1 = slidingPiece.toBigInt();
    let quadrille = createQuadrille(8, 8);

    for (let i = 0; i < 8; i++) {
        let rank = i + 1;
        let rankBitboard = Chess.BitboardUtils.getRank(rank);
        console.log((rankBitboard & bitboard1) > 1)
        if ((rankBitboard & bitboard1) > 0) {
            quadrille.fill(8 - rank, 1);
            break;
        }
    }

    return quadrille;
}

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);
        }
    });

}

However, we also need to apply this mask to the occupied bitboard because we only have to consider blockers in the direction the sliding piece is moving.

$$ s = [(o\cap m) - r] \cap m \newline s:\text{sliding moves} \quad o:\text{occupied} \quad r:\text{sliding piece} \quad m:\text{mask} $$

Code

//sliding-devlog/masked-occupied.js

let occupied;
let slidingPiece;
let mask;
let blockers;
let result;

function setup() {
    Quadrille.cellLength = 25;
    createCanvas(28 * Quadrille.cellLength, 22 * Quadrille.cellLength);
    occupied = createBitboardQuadrille(0x1000804200000010n);

    slidingPiece = createQuadrille(8, 8);
    slidingPiece.fill(4, 5, 1);

    mask = getMask();
    blockers = getBlockers();
    result = getResult();
}

function draw() {
    background(255);
    drawBitboard(occupied, 3, 1, Quadrille.chessSymbols['p']);
    drawBitboard(slidingPiece, 3, 10, Quadrille.chessSymbols['R']);
    drawBitboard(mask, 3, 19, 1);
    drawBitboard(blockers, 13, 1, Quadrille.chessSymbols['p']);
    drawBitboard(result.old, 13, 10, 1);
    drawBitboard(result.new, 13, 19, 1);

    textSize(15);
    textAlign(CENTER, TOP);
    textStyle(BOLD);
    text('Click "sliding piece" bitboard to change its position. See results', Quadrille.cellLength * 28 * 0.5, Quadrille.cellLength * 0.5);

    textStyle(NORMAL);
    text("Occupied", Quadrille.cellLength * 5, Quadrille.cellLength * 2);
    text("Sliding Piece", Quadrille.cellLength * 14, Quadrille.cellLength * 2);
    text("Mask", Quadrille.cellLength * 23, Quadrille.cellLength * 2);

    text("Blockers (masked occupied)", Quadrille.cellLength * 5, Quadrille.cellLength * 12);
    text("Result (without masked occupied)", Quadrille.cellLength * 14, Quadrille.cellLength * 12);
    text("Result (with masked occupied)", Quadrille.cellLength * 23, Quadrille.cellLength * 12);
}

function mouseClicked() {
    if (slidingPiece.read(slidingPiece.mouseRow, slidingPiece.mouseCol) !== undefined) {
        slidingPiece.replace(1, null);
        slidingPiece.fill(slidingPiece.mouseRow, slidingPiece.mouseCol, 1);
    }
    mask = getMask();
    blockers = getBlockers();
    result = getResult();
}

function getResult() {
    let occupiedBitboard = occupied.toBigInt();
    let pieceBitboard = slidingPiece.toBigInt();

    let oldResult = occupiedBitboard - pieceBitboard;
    if (oldResult < 0) oldResult = BigInt.asUintN(64, oldResult);
    let oldQuadrille = createBitboardQuadrille(oldResult);
    oldQuadrille = Quadrille.and(oldQuadrille, mask);

    let blockersBitboard = blockers.toBigInt();
    let newResult = blockersBitboard - pieceBitboard;
    if (newResult < 0) newResult = BigInt.asUintN(64, newResult);
    let newQuadrille = createBitboardQuadrille(newResult);
    newQuadrille = Quadrille.and(newQuadrille, mask);

    return {
        old: oldQuadrille,
        new: newQuadrille
    };
}

function getMask() {
    let bitboard1 = slidingPiece.toBigInt();
    let quadrille = createQuadrille(8, 8);

    for (let i = 0; i < 8; i++) {
        let file = i + 1;
        let fileBitboard = Chess.BitboardUtils.getFile(file);
        if ((fileBitboard & bitboard1) > 0) {
            quadrille.transpose();
            quadrille.fill(file - 1, 1);
            quadrille.transpose();
            break;
        }
    }

    return quadrille;
}

function getBlockers() {
    return Quadrille.and(occupied, mask);
}

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;

}

As we can see, the previous result is inaccurate because it considers blockers that are not in the direction of the mask.

Positive and negative rays

A limitation of this trick is that the number of directions we can get attacks from is limited. If you notice in the previous examples, bit propagation always goes from right to left and bottom to top. This means that we can get attacks only in directions that follow this bit-propagation order. These directions are known as positive rays and they are upward, left, top-left diagonal, and top-right diagonal [5].

On the other hand, we cannot get attacks in moving directions that go in the inverse order. These directions are called negative rays and they are downward, right, down-right diagonal, and down-left diagonal [5].

Code

//sliding-devlog/pos-neg-rays.js

let ones;
let occupied;
let queen;
let positiveRays;
let negativeRays;

function setup() {
    Quadrille.cellLength = 50;
    createCanvas(10 * Quadrille.cellLength, 10 * Quadrille.cellLength)
    queen = createQuadrille(8, 8);
    queen.fill(4, 4, Quadrille.chessSymbols['Q']);
    occupied = createQuadrille(8, 8);
    occupied.fill(1, 1, Quadrille.chessSymbols['p']);
    ones = createBitboardQuadrille(occupied.toBigInt() - queen.toBigInt());
    getRays();
}

function draw() {
    background(255);

    let boardRow = 1;
    let boardCol = 1;

    drawQuadrille(positiveRays, { row: boardRow, col: boardCol });
    drawQuadrille(negativeRays, { row: boardRow, col: boardCol });
    drawBitboard(ones, boardRow, boardCol, 1);
    drawQuadrille(occupied, { row: boardRow, col: boardCol });
    drawQuadrille(queen, { row: boardRow, col: boardCol });

    textSize(15);
    textAlign(CENTER, TOP);
    text("🟢 Positive Rays (can calculate) \n 🔴 Negative Rays (cannot calculate)", Quadrille.cellLength * 10 * 0.5, Quadrille.cellLength * 0.25);
}

function getRays() {

    let rank = Chess.BitboardUtils.getRank(4);
    let file = Chess.BitboardUtils.getFile(5);
    let diagonal = Chess.BitboardUtils.getDiagonal(4, 5);
    let antiDiagonal = Chess.BitboardUtils.getAntiDiagonal(4, 5);

    let occupiedBitboard = occupied.toBigInt();
    let queenBitboard = queen.toBigInt();

    let rankRay = Chess.BitboardUtils.hyperbolaQuintessenceAlgorithm(occupiedBitboard, queenBitboard, rank);
    let fileRay = Chess.BitboardUtils.hyperbolaQuintessenceAlgorithm(occupiedBitboard, queenBitboard, file);
    let diagonalRay = Chess.BitboardUtils.hyperbolaQuintessenceAlgorithm(occupiedBitboard, queenBitboard, diagonal);
    let antiDiagonalRay = Chess.BitboardUtils.hyperbolaQuintessenceAlgorithm(occupiedBitboard, queenBitboard, antiDiagonal);

    let positiveRaysBitboard = rankRay.positiveRay | fileRay.positiveRay | diagonalRay.positiveRay | antiDiagonalRay.positiveRay;
    positiveRays = createBitboardQuadrille(positiveRaysBitboard);
    positiveRays.replace(1, color('#b3ffb3'));

    let negativeRaysBitboard = rankRay.negativeRay | fileRay.negativeRay | diagonalRay.negativeRay | antiDiagonalRay.negativeRay;
    negativeRays = createBitboardQuadrille(negativeRaysBitboard);
    negativeRays.replace(1, color('rgba(250,95,139,0.5)'));
}


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;

}

Fortunately, we can solve this by reversing all the elements in the equation. Reversing a bitboard means that its first bit will be the last one and its last bit will be the first.

$$ x’’ = inverse(x) \newline p = [(o\cap m) - r] \cap m \newline n = [(o\cap m)’’ - r’’]’’ \cap m \newline p:\text{positive ray} \quad n:\text{negative ray} \quad o:\text{occupied} \newline r:\text{sliding piece} \quad m:\text{mask} $$

Final equation

These are the fundamentals of the o^(o-2r)-trick. The complete equation is:

$$ x’’ = inverse(x) \newline b = o\cap m \newline p = [(b - 2*r)\oplus o] \cap m \newline n = [(b’’ - 2 * r’’)\oplus o]’’ \cap m \newline s = p \cup n \newline o:\text{occupied} \quad r:\text{sliding piece} \quad m:\text{mask} \quad b:\text{blockers} \newline p:\text{positive ray} \quad n:\text{negative ray} \quad s:\text{sliding moves} $$

The additional terms in the expression that weren’t covered here are fully explained in this article [6]. This trick is more convoluted and difficult to understand than the previous one. However, it significantly reduces all the logic down to an equation that can be coded in a few lines.

Generalizing sliding pieces

Now that we have chosen our preferred approach to calculate sliding moves, we will create an interface that generalizes the move calculation algorithm for every sliding piece. The way the interface looks will vary depending on the approach we choose. In this case, we’ll use the o^(o-2r)-trick as the base algorithm and create the interface around it.

class SlidingPiece extends Piece {

    getType() {
        throw new Error("Method 'GetType()' must be implemented.");
    }
    
    /**
     * @param {BoardImplementation} board 
     * @returns Array of legal moves
     */
    getMoves(board) {

        //Moves calculated using o^(o-2r)-trick. 
        //Taken from https://www.youtube.com/watch?v=bCH4YK6oq8M&list=PLQV5mozTHmacMeRzJCW_8K3qw2miYqd0c&index=9&ab_channel=LogicCrazyChess.

        let occupied = board.getOccupied();
        let rays = this.getSlidingRays();
        let position = this.position;
        let slidingMoves = 0n;

        //calculate moves in every direction
        rays.forEach(ray => {
            let blockers = occupied & mask;
            let positiveRay = ((blockers - 2n * position) ^ occupied) & mask;
            let negativeRay = (reverseBitboard((reverseBitboard(blockers) - 2n * reverseBitboard(position))) ^ occupied) & mask;
            slidingMoves = positiveRay | negativeRay | slidingMoves;
        });

        return slidingMoves & ~board.getOccupied(this.color);
    }
    
    getSlidingRays() {
        throw new Error("Method 'GetType()' must be implemented.");
    }
}

The first step is to calculate the variables we need to apply the trick. We begin by retrieving the bitboard with the squares occupied by pieces from the current board.

Next, we calculate the rays or directions in which this piece is moving. These rays will be the mask that’s going to be applied both to the occupied bitboard and the final result. Clearly, these directions depend on the type of piece. Therefore, we create an abstract method that will be implemented in the derived classes of each piece.

The bitboard with the current position is inherited from Piece abstract class.

After initializing the variables required for the trick, we apply the equation for every direction the piece can move. This needs to be done ray by ray to avoid the problem we had in this section, where blockers that should not be considered in the current direction produce incorrect results. For every iteration, we add the positive and negative ray obtained to the sliding moves we already have.

Finally, we exclude squares occupied by pieces of our own color because they are not distinguished by the algorithm.

As we said before, each type of piece will specify the directions it can slide. Here’s an example of the rook:

class Rook extends SlidingPiece {

    getType() {
        return E_PieceType.Rook;
    }
    
    /**
     * @param {BoardImplementation} board 
     * @returns Array of legal moves
     */
    getMoves(board) {
        return super.getMoves(board);
    }
    
    getSlidingRays() {
        return [getFile(this.file), getRank(this.rank)];
    }
}

As always, try to implement the other two pieces: the Bishop and the Queen.

Exercise
Implement the derived classes of the Queen and the Bishop.

Final Result

Code

//sliding-devlog/final-result.js

let game;
const GAME_MARGIN = 50;
const EXTRA_WIDTH_BUTTONS = 70;
const FEN = '1b6/3P1P2/1P6/6r1/p2q4/1Q4p1/8/1B5R';
function setup() {
    createCanvas(Chess.GAME_DIMENSIONS.WIDTH + GAME_MARGIN + EXTRA_WIDTH_BUTTONS, Chess.GAME_DIMENSIONS.HEIGHT + GAME_MARGIN);
    game = new Chess.Game(GAME_MARGIN / 2, GAME_MARGIN / 2, FEN);
    game.setGameMode(Chess.E_GameMode.FREE);
}

function draw() {
    background(255);
    game.update();
}

References

[1] Sliding pieces. Chessprogramming wiki. (2018, May 7). https://www.chessprogramming.org/Sliding_Pieces
[2] Bitwise or (: ) - javascript: MDN. MDN Web Docs. (n.d.). https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_OR
[3] Portilla, E. R. (1970, January 1). Pedir Prestado. MATEMÁTICA ECA DE ENSEÑANZA BÁSICA. https://eca-matematica.blogspot.com/2011/10/pedir-prestado.html
[4] Suma y resta binaria. UNIGAL.MX (2022, March 22). https://unigal.mx/suma-y-resta-binaria/
[5] On an empty board. On an empty Board - Chessprogramming wiki. (2022, January 18). https://www.chessprogramming.org/On_an_empty_Board
[6] Subtracting a rook from a blocking piece. Chessprogramming wiki. (2019, October 22). https://www.chessprogramming.org/Subtracting_a_Rook_from_a_Blocking_Piece