Piece Rules: King and Knight

Introduction

The King and the Knight are the easiest pieces we will implement in this series. As opposed to pawns and sliders, their movement is not defined by complicated rules. The only rule is that they cannot move to a square occupied by a piece of the same color, as it happens with all pieces.

Bit shifting is again applicable to this case. However, I’ll explain a new approach that is also applicable to calculating the moves of any of the pieces we’ve covered in previous devlogs.

Precalculating an attack mask

As you might know, the knight is able to move in L shapes in 8 different ways. These movements are not restricted by pieces that might be surrounding the knight.

Alt text
Knight moves. Taken from [1]

What we will do is create a bitboard that contains the knight moves in a certain square. The square selected is arbitrary. We’ll choose the first square in which the knight can perform all of its 8 possible moves, which is square 19th (considering the 1st square is the one at the bottom right and it increments from right to left and bottom to top). This approach was taken from this video [2].

Code
//king-knight-devlog/knight-moves.js

const KNIGHT_DEFAULT_MOVES = 0xA1100110An;
Quadrille.cellLength = 25;
const WIDTH = Quadrille.cellLength * 10;
const HEIGTH = Quadrille.cellLength * 11;
let chessBoard;
let squareNumbers;
let knight;
let moves;


function setup() {
    createCanvas(WIDTH, HEIGTH);
    chessBoard = new Quadrille();

    knight = new Quadrille(8, 8);
    knight.fill(5, 5, Quadrille.chessSymbols['N']);

    squareNumbers = new Quadrille(8, 8);
    visitQuadrille(squareNumbers, (row, col) => {
        let rank = (8 - row);
        let file = col + 1;
        let squareNumber = (rank - 1) * 8 + (9 - file);
        squareNumbers.fill(row, col, squareNumber.toString());
    })

    moves = createBitboardQuadrille(KNIGHT_DEFAULT_MOVES);
}

function draw() {
    background(255);
    drawQuadrille(chessBoard, { row: 2, col: 1 });
    drawQuadrille(squareNumbers, {
        row: 2,
        col: 1,
        stringDisplay: ({ graphics, value, cellLength = Quadrille.cellLength } = {}) => {
            graphics.textAlign(LEFT, TOP);
            graphics.textSize(cellLength * 0.3);
            graphics.text(value, 1, 1);
        }
    });
    drawQuadrille(knight, { row: 2, col: 1 });
    drawBitboard(moves, 2, 1, 1);
    textAlign(CENTER, TOP);
    textStyle(BOLD);
    text("Knight's default movement mask", WIDTH / 2, Quadrille.cellLength * 1)
}

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;

}

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

}

Translating attack mask

To obtain the moves of the knight, we just have to move the default movement mask to the appropriate square.

Code
//king-knight-devlog/moving-moves-mask.js

Quadrille.cellLength = 25;

const KNIGHT_DEFAULT_MOVES = 0xA1100110An;
const START_SQUARE_BITBOARD = 0x40000n;
const START_SQUARE = 19;
const WIDTH = Quadrille.cellLength * 10;
const HEIGTH = Quadrille.cellLength * 11;
let chessBoard;
let displacement;
let moves;
let squareNumbers;
let knightSquare;

function setup() {
    createCanvas(WIDTH, HEIGTH);
    chessBoard = new Quadrille();

    squareNumbers = new Quadrille(8, 8);
    visitQuadrille(squareNumbers, (row, col) => {
        let rank = (8 - row);
        let file = col + 1;
        let squareNumber = (rank - 1) * 8 + (9 - file);
        squareNumbers.fill(row, col, squareNumber.toString());
    })

    displacement = 0;
    updateMoves();
}

function draw() {
    background(255);
    drawQuadrille(chessBoard, { row: 2, col: 1 });
    drawQuadrille(squareNumbers, {
        row: 2,
        col: 1,
        stringDisplay: ({ graphics, value, cellLength = Quadrille.cellLength } = {}) => {
            graphics.textAlign(LEFT, TOP);
            graphics.textSize(cellLength * 0.3);
            graphics.text(value, 1, 1);
        }
    });
    drawQuadrille(knightSquare, { row: 2, col: 1 })
    drawBitboard(moves, 2, 1, 1);
    textAlign(CENTER, TOP);
    textStyle(BOLD);
    text("Click 'A' key to shift knight to the left", WIDTH / 2, Quadrille.cellLength * 0.5)
    text("Click 'D' key to shift knight to the right", WIDTH / 2, Quadrille.cellLength * 1)
}


function keyPressed() {
    if (key === 'a') {
        displacement = Math.min(64 - START_SQUARE, displacement + 1);
    } else if (key === 'd') {
        displacement = Math.max(-START_SQUARE + 1, displacement - 1);
    }

    updateMoves();
}

function updateMoves() {
    let movesBitboard = KNIGHT_DEFAULT_MOVES;
    let knightSquareBitboard = START_SQUARE_BITBOARD;
    if (displacement > 0) {
        movesBitboard = movesBitboard << BigInt(displacement);
        movesBitboard = BigInt.asUintN(64, movesBitboard); //clamp bitboard to 64 bits
        knightSquareBitboard = knightSquareBitboard << BigInt(displacement);
    } else {
        movesBitboard = movesBitboard >> BigInt(-displacement);
        knightSquareBitboard = knightSquareBitboard >> BigInt(-displacement);
    }

    moves = createBitboardQuadrille(movesBitboard);
    knightSquare = createBitboardQuadrille(knightSquareBitboard);
    knightSquare.replace(1, Quadrille.chessSymbols['N']);
}

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;

}

function drawBitboard(bitboard, row, col, fill) {
    drawQuadrille(bitboard, {
        row: row,
        col: col,
        numberDisplay: ({ graphics, 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);
        }
    });

}

As we can see, the idea is pretty simple. However, we have the same problem as the pawn’s case where bits wrap around the edges of the board to the other side.

Now that you have an idea of what we are trying to accomplish, give it a shot to implement a solution that uses this approach to calculate knight moves. The calculation of king moves is similar, just with a different default movement mask.

You can take a look at the code of the previous sketch. It might give you some ideas on how to build the logic.

Exercise 

Implement a function that returns the moves of the knight and the king using a default movement mask.

Solution
class Knight extends Piece {
    #movementMask = 0xA1100110An;

    getType() {
        return E_PieceType.Knight;
    }
    /**
     * 
     * @param {BoardImplementation} board 
     * @returns 
     */
    getMoves(board) {
        //calculate current square
        let currentSquare = (this.rank - 1) * NUMBER_OF_RANKS + (NUMBER_OF_FILES - this.file + 1);
        let moves = 0n;

        //displace attack mask to current square
        if (19 <= currentSquare) {
            moves = this.#movementMask << BigInt(currentSquare - 19);
        } else {
            moves = this.#movementMask >> BigInt(19 - currentSquare);
        }

        //remove bits that "wrap around" the edge
        if (this.file < 3) {
            moves = moves & ~getFile(7) & ~getFile(8);
        } else if (6 < this.file) {
            moves = moves & ~getFile(1) & ~getFile(2);
        }
        //remove pieces of same color
        moves = moves & ~board.getOccupied(this.color);

        return moves;
    }

Given the rank and file of the piece, we can calculate the square we are currently in. Knowing the current square, we can determine the number of times the default mask has to be displaced and in which direction. Then, we remove bits that wrap around when we are near the edge of the board. Finally, we exclude moves to squares occupied by pieces of the same color.

class King extends Piece {
    #movementMask = 0x70507n;

    getType() {
        return E_PieceType.King;
    }
    /**
     * 
     * @param {BoardImplementation} board 
     * @returns 
     */
    getMoves(board) {
        //calculate current square
        let currentSquare = (this.rank - 1) * NUMBER_OF_RANKS + (NUMBER_OF_FILES - this.file + 1);
        let moves = 0n;

        //displace attack mask to current square
        if (10 <= currentSquare) {
            moves = this.#movementMask << BigInt(currentSquare - 10);
        } else {
            moves = this.#movementMask >> BigInt(10 - currentSquare);
        }

        //remove bits that "wrap around" the sides
        if (this.file < 3) {
            moves = moves & ~getFile(7) & ~getFile(8);
        } else if (6 < this.file) {
            moves = moves & ~getFile(1) & ~getFile(2);
        }
        //remove pieces of same color
        moves = moves & ~board.getOccupied(this.color);

        return moves;
    }
}

The logic for the king is the same except for the value of the default mask and the start square.

Final result

References