2

In a previous question I asked, linked here: How can I speed up my check detection in Javascript? I was told to implement bit-boards to speed up my engine. I can say that bit-boards have improved my performance from being able to generate 500 moves/second to 10-15 thousand moves/second, but I have a question, how can I make my implementation of bit-boards faster?

Here is the code for the move generation:

const board = [
    ["c", "h", "b", "q", "k", "b", "h", "c"],
    ["p", "p", "p", "p", "p", "p", "p", "p"],
    ["", "", "", "", "", "", "", ""],
    ["", "", "", "", "", "", "", ""],
    ["", "", "", "", "", "", "", ""],
    ["", "", "", "", "", "", "", ""],
    ["P", "P", "P", "P", "P", "P", "P", "P"],
    ["C", "H", "B", "Q", "K", "B", "H", "C"]
];

function createMoveMask(mask, board, type, centerPosition) {
    let x = centerPosition.x;
    let y = centerPosition.y;
    let moveMask = [
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]
    ];

    let blockedBitMask = getOccupiedSquares(board, type);

    if (type == "blackPieces") {
        var capturableSquares = getOccupiedSquares(board, "whitePieces");
    } else {
        var capturableSquares = getOccupiedSquares(board, "blackPieces");
    }

    switch (mask) {
        case "north":
            for (row = y - 1; row >= 0; row--) {
                if (blockedBitMask[row][x] == 1) {
                    break;
                } else if (capturableSquares[row][x] == 1) {
                    moveMask[row][x] = 1;
                    break;
                }
                moveMask[row][x] = 1;
            }
            break;

        case "south":
            for (row = y + 1; row < 8; row++) {
                if (blockedBitMask[row][x] == 1) {
                    break;
                } else if (capturableSquares[row][x] == 1) {
                    moveMask[row][x] = 1;
                    break;
                }
                moveMask[row][x] = 1;
            }
            break;

        case "east":
            for (col = x + 1; col < 8; col++) {
                if (blockedBitMask[y][col] == 1) {
                    break;
                } else if (capturableSquares[y][col] == 1) {
                    moveMask[y][col] = 1;
                    break;
                }
                moveMask[y][col] = 1;
            }
            break;

        case "west":
            for (col = x - 1; col >= 0; col--) {
                if (blockedBitMask[y][col] == 1) {
                    break;
                } else if (capturableSquares[y][col] == 1) {
                    moveMask[y][col] = 1;
                    break;
                }
                moveMask[y][col] = 1;
            }
            break;

        case "northEast":
            row = y - 1;
            col = x + 1;
            while (row >= 0 && col < 8) {
                if (blockedBitMask[row][col] == 1) {
                    break;
                } else if (capturableSquares[row][col] == 1) {
                    moveMask[row][col] = 1;
                    break;
                }
                moveMask[row][col] = 1;
                row -= 1;
                col += 1;
            }
            break;

        case "northWest":
            row = y - 1;
            col = x - 1;
            while (row >= 0 && col >= 0) {
                if (blockedBitMask[row][col] == 1) {
                    break;
                } else if (capturableSquares[row][col] == 1) {
                    moveMask[row][col] = 1;
                    break;
                }
                moveMask[row][col] = 1;
                row -= 1;
                col -= 1;
            }
            break;

        case "southEast":
            row = y + 1;
            col = x + 1;
            while (row < 8 && col < 8) {
                if (blockedBitMask[row][col] == 1) {
                    break;
                } else if (capturableSquares[row][col] == 1) {
                    moveMask[row][col] = 1;
                    break;
                }
                moveMask[row][col] = 1;
                row += 1;
                col += 1;
            }
            break;

        case "southWest":
            row = y + 1;
            col = x - 1;
            while (row < 8 && col >= 0) {
                if (blockedBitMask[row][col] == 1) {
                    break;
                } else if (capturableSquares[row][col] == 1) {
                    moveMask[row][col] = 1;
                    break;
                }
                moveMask[row][col] = 1;
                row += 1;
                col -= 1;
            }
            break;
    }
    return moveMask;
}

function getOccupiedSquares(board, type) {
    let occupiedSquares = [
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]
    ];

    if (type == "blackPieces") {
        for (row = 0; row < 8; row++) {
            for (col = 0; col < 8; col++) {
                if (
                    board[row][col] == "q" ||
                    board[row][col] == "k" ||
                    board[row][col] == "c" ||
                    board[row][col] == "h" ||
                    board[row][col] == "p" ||
                    board[row][col] == "b"
                ) {
                    occupiedSquares[row][col] = 1;
                }
            }
        }
    } else {
        for (row = 0; row < 8; row++) {
            for (col = 0; col < 8; col++) {
                if (
                    board[row][col] == "Q" ||
                    board[row][col] == "K" ||
                    board[row][col] == "C" ||
                    board[row][col] == "H" ||
                    board[row][col] == "P" ||
                    board[row][col] == "B"
                ) {
                    occupiedSquares[row][col] = 1;
                }
            }
        }
    }
    return occupiedSquares;
}

function castleMoves(board, position, type) {
    let north = createMoveMask("north", board, type, position);
    let south = createMoveMask("south", board, type, position);
    let east = createMoveMask("east", board, type, position);
    let west = createMoveMask("west", board, type, position);

    let moves = [
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]
    ];

    for (row = 0; row < 8; row++) {
        for (col = 0; col < 8; col++) {
            moves[row][col] = 
            north[row][col] |
            south[row][col] |
            east[row][col] |
            west[row][col];
        }
    }

    return moves;
}

function bishopMoves(board, position, type) {
    let northEast = createMoveMask("northEast", board, type, position);
    let northWest = createMoveMask("northWest", board, type, position);
    let southEast = createMoveMask("southEast", board, type, position);
    let southWest = createMoveMask("southWest", board, type, position);

    let moves = [
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]
    ];

    for (row = 0; row < 8; row++) {
        for (col = 0; col < 8; col++) {
            moves[row][col] = 
            northEast[row][col] |
            southEast[row][col] |
            northWest[row][col] |
            southWest[row][col];
        }
    }

    return moves;
}

function queenMoves(board, position, type) {
    let northEast = createMoveMask("northEast", board, type, position);
    let northWest = createMoveMask("northWest", board, type, position);
    let southEast = createMoveMask("southEast", board, type, position);
    let southWest = createMoveMask("southWest", board, type, position);
    let north = createMoveMask("north", board, type, position);
    let south = createMoveMask("south", board, type, position);
    let east = createMoveMask("east", board, type, position);
    let west = createMoveMask("west", board, type, position);

    let moves = [
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]
    ];

    for (row = 0; row < 8; row++) {
        for (col = 0; col < 8; col++) {
            moves[row][col] = 
            north[row][col] |
            south[row][col] |
            east[row][col] |
            west[row][col] |
            northEast[row][col] |
            northWest[row][col] |
            southEast[row][col] |
            southWest[row][col];
        }
    }

    return moves;
}

If you need any clarifications regarding the question or the code, feel free to ask.

  • 2
    I just realized that I posted a link to a similar question that you asked. As feedback, the included code makes you question easier to understand. I would suggest that you only post one questions at a time and ask them to expand the answer if needed. Good Luck! – Mike Jones Feb 1 at 7:32
5

The real speed in bitboards is created by precomputing the bitboards for every instance. This means that you already have the attacked squares for a rook on d4 and every other piece on every square. Even faster is to use magic bitboards, but that is too complicated for a forum. Although both are written in c, I suggest Crafty to understand bitboards better, and Stockfish for magic bitboards.

Note, most chess engines using bitboards keep the position in a bitboard. To get the occupied bitboard, they just or together all the piece bitboards. You're using an array for the position and trying to create these bitboards at each move generation, which is wasting more time than is saved from using the bitboard operations.

An alternative which is easier to understand with just a modest speed hit, I suggest a system described here. Chess move generation with bit boards in Javascript (In c, I timed the move generation in a 32,000 loop and it took only 32 ms. In Javascript it will be much slower, but it should be efficient enough.)

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.