chess-engine

chess-engine is a legal move generator written in C++ from scratch. The goal was to implement every rule of chess correctly at the bit level — not just the happy path, but pins, discovered checks, en passant validation, castling legality, and the distinction between checkmate and stalemate. The board is represented entirely in bitboards: twelve 64-bit integers (six piece types × two colors) plus three aggregated occupancy boards kept in sync on every mutation. Move generation is split into two phases: a pseudo-legal generator per piece type, then a legality filter that simulates each move on a copied board and verifies the king isn't left in check.

Board Representation

The entire board lives in a single BoardState struct. The core is a 2D array piece_bitboards[COLOR_NB][PIECE_TYPE_NB] — twelve uint64_t values where each set bit is a piece on the corresponding square. Three aggregated boards (white_occupancy, black_occupancy, all_occupancy) are derived from these twelve and updated on every mutation.

The four primitive operations — set_bit, clear_bit, is_bit_set, and shift — are all one-liners built on bitwise ops and left/right shifts. Square indexing goes A1=0 through H8=63 left-to-right, bottom-to-top. NORTH is +8, EAST is +1, diagonals are sums of those.

using Bitboard = uint64_t;

Bitboard set_bit(Bitboard board, Square sq)  { return board |  (1ULL << sq); }
Bitboard clear_bit(Bitboard board, Square sq) { return board & ~(1ULL << sq); }
bool     is_bit_set(Bitboard board, Square sq) { return (board >> sq) & 1ULL; }

Bitboard shift(Bitboard board, Direction dir) {
    return dir > 0 ? board << dir : board >> (-dir);
}

// BoardState keeps all three occupancy boards in sync
void BoardState::update_occupancy() {
    white_occupancy = black_occupancy = 0ULL;
    for (int pt = 0; pt < PIECE_TYPE_NB; ++pt) {
        white_occupancy |= piece_bitboards[WHITE][pt];
        black_occupancy |= piece_bitboards[BLACK][pt];
    }
    all_occupancy = white_occupancy | black_occupancy;
}

Move Generation Pipeline

generate_legal_moves iterates all six piece types for the given color. For each piece found on the board it calls generate_moves, which dispatches to a piece-specific generator. The pseudo-legal move list is then passed to filter_legal_moves, which removes any move that leaves the king in check.

If the filtered list ends up empty, the function checks whether the king is currently in check via is_square_attacked. Empty list + king in check = checkmate. Empty list + king safe = stalemate. The distinction is implicit in the return value — an empty vector in both cases — because downstream callers are responsible for interpreting game state.

std::vector<TypedMove> generate_legal_moves(const BoardState& board, Color color) {
    std::vector<TypedMove> legal_moves;

    for (int pt = PAWN; pt <= KING; ++pt) {
        Bitboard pieces = board.piece_bitboards[color][pt];
        for (int sq = 0; sq < 64; ++sq) {
            if (!is_bit_set(pieces, static_cast<Square>(sq))) continue;

            auto pseudo = generate_moves(board, static_cast<PieceType>(pt),
                                         color, static_cast<Square>(sq));
            auto filtered = filter_legal_moves(board, color,
                                               static_cast<PieceType>(pt), pseudo);
            legal_moves.insert(legal_moves.end(), filtered.begin(), filtered.end());
        }
    }
    return legal_moves; // empty = checkmate or stalemate
}

Legality Filtering & Pin Detection

filter_legal_moves runs two checks per candidate move. For king moves it calls is_square_attacked on the destination square before simulation. For all moves it copies the full BoardState, applies the move via simulate_move, then re-checks the king's square. King moves also get an adjacency check — the king cannot step adjacent to the enemy king.

Pin detection in move_breaks_pin works by ray-casting from the king in all 8 directions and collecting every occupied square along each ray. A pin is flagged when exactly two pieces appear: the first is ours (the candidate piece), and the second is an enemy slider that can attack along that axis — rook or queen for straight rays, bishop or queen for diagonals. If the candidate move takes the piece off the pin line without capturing the attacker, the move is illegal.

// For each ray from the king: collect pieces, check for pin
for (int dir : directions) {
    std::vector<Square> pieces_on_ray;
    int sq = static_cast<int>(king_sq);
    while (/* step is in bounds and stays on ray */) {
        sq += dir;
        if (is_bit_set(board_state.all_occupancy, sq))
            pieces_on_ray.push_back(static_cast<Square>(sq));
    }
    if (pieces_on_ray.size() != 2) continue;          // need exactly 2
    if (!first_is_ours || !second_is_enemy) continue; // own then enemy
    if (!is_attacker) continue;                        // enemy must be a slider
    if (move.from != pieces_on_ray[0]) continue;       // our pinned piece is moving
    if (!is_on_pin_line) return true;                  // breaks pin → illegal
}

Sliding Pieces & Special Moves

Bishops, rooks, and queens use ray loops that step one square at a time in each direction. After every step the code validates the file and rank delta against the expected change for that direction — this prevents the integer indexing from silently wrapping a rook from H-file to A-file or a bishop from one diagonal to another.

En passant requires three conditions to all hold: the attacking pawn is on rank 4 (white) or 3 (black), the file distance to the target en passant square is exactly 1, and the enemy pawn actually sits on the expected capture square. Castling in the generator only checks that the intermediate squares are empty and the rook is in place; the legality filter handles the 'king must not pass through check' constraint by simulating the king on each intermediate square.

// Sliding ray — bishop direction shown
while (true) {
    int next_sq   = sq + dir;
    int next_file = next_sq % 8;
    int next_rank = next_sq / 8;
    if (next_sq < 0 || next_sq >= 64) break;
    // Diagonal step must change file and rank by exactly 1
    if (abs(next_file - prev_file) != 1 ||
        abs(next_rank - prev_rank) != 1) break;
    if (is_bit_set(own, target))   break;              // blocked by own piece
    if (is_bit_set(enemy, target)) { add CAPTURE; break; }
    add NORMAL; // empty square — keep sliding
}

// En passant — all three conditions must pass
if (board_state.en_passant_square == target) {
    int correct_rank = color == WHITE ? 4 : 3;
    if (attacking_rank == correct_rank &&
        abs(attacking_file - target_file) == 1 &&
        is_bit_set(board.piece_bitboards[enemy][PAWN], enemy_pawn_sq))
        add CAPTURE;
}