Design

The design of the move generator is mosty data-based: it precomputes almost everything when the engine starts. This makes the term “generator” a bit misleading, because very little is either generated or calculated when the move list is being filled. In the chess engine community the term “move generator” was basically kept from chess engines of the past. The earliest engines didn’t use bitboards, but calculated every single possible move for each piece in every position, one by one.

This move generator doesn’t do that: it pre-calculates as much as possible for every possible piece movent when the engine starts, so it can find moves very quickly by just looking up values in tables and combining some bitboards.

The move generator has a lot of moving parts. (I couldn’t resist making this pun. Sorry.) Therefore it has to be designed in a cohesive and consistent fashion. This is necessary to be able to understand what is going on, and to test it during development. See the Sidenote at the end of this page for more information.

The fact that Rustic is already precomputing a lot of things when it boots up becomes clear when you take a look at the move generator struct:

pub struct MoveGenerator {
    king_attacks: EverySquare<Bitboard>,
    knight_attacks: EverySquare<Bitboard>,
    pawn_attacks: EverySide<EverySquare<Bitboard>>,
    rook_attacks: Vec<Bitboard>,
    bishop_attacks: Vec<Bitboard>,
    rook_magics: EverySquare<Magic>,
    bishop_magics: EverySquare<Magic>,
}

It holds a massive amount of bitboards. These are all initialized when the move generator starts:

pub fn new() -> Self {
    pub fn new() -> Self {
        let mut mg = Self {
            king_attacks: EverySquare::new(Bitboard::empty()),
            knight_attacks: EverySquare::new(Bitboard::empty()),
            pawn_attacks: EverySide::new(EverySquare::new(Bitboard::empty())),
            rook_attacks: vec![Bitboard::empty(); ROOK_TABLE_SIZE],
            bishop_attacks: vec![Bitboard::empty(); BISHOP_TABLE_SIZE],
            rook_magics: EverySquare::new(Default::default()),
            bishop_magics: EverySquare::new(Default::default()),
        };
        let rook = IndexingContext {
            table_size: ROOK_TABLE_SIZE,
            attack_mask: rook_attack_mask,
            attack_boards_fn: rook_attack_boards,
            piece_attacks: &mut mg.rook_attacks,
            piece_magics: &mut mg.rook_magics,
            magic_numbers: &ROOK_MAGIC_NRS,
        };
        let bishop = IndexingContext {
            table_size: BISHOP_TABLE_SIZE,
            attack_mask: bishop_attack_mask,
            attack_boards_fn: bishop_attack_boards,
            piece_attacks: &mut mg.bishop_attacks,
            piece_magics: &mut mg.bishop_magics,
            magic_numbers: &BISHOP_MAGIC_NRS,
        };

        MoveGenerator::init_king(&mut mg.king_attacks);
        MoveGenerator::init_knight(&mut mg.knight_attacks);
        MoveGenerator::init_pawns(&mut mg.pawn_attacks);
        MoveGenerator::init_magics(rook);
        MoveGenerator::init_magics(bishop);

        mg
    }
}

Don’t worry if you don’t immediately understand how we can precompute basically any move on the board without even a game going on. It will all be explained in the coming sections. I’ll run thorugh each mg.init function and explain it. I’ll also explain how the “magic numbers” are obtained and what they mean. The kings and knights are relatively straight-forward. The pawns are somewhat more challenging, but the real complexity hides in the initialization of the rook and bishop.

Those with keen eyes may be wondering about a few things now that I can clear up right away, so you can get them out of the back of your mind:

• Qeustion: Why does everything use an array, but rook_attacks and bishop_attacks are vectors? Answer: An array lives on the stack, and these lists are too large to be there. ROOK_TABLE_SIZE and BISHOP_TABLE_SIZE are 102.400 and 5.248 items long respectively, and that is just not suited to be hosted on the stack. When discussing magic numbers, we’ll get to why these vectors have these specific lengths.

• Question: What is the difference between “rook_attacks” and “rook_magics”? Answer: The first, rook_attacks, holds every possible attack a rook can make on the board, depending on the square it is on and the location of other pieces. (Yes, EVERY possible attack.) The rook_magics array holds a magic number for each square. This number is used to to compute the index in the rook_attack table, so we can find the correct rook attack by lookup. How this works exactly is discussed in the sections about magic bitboards.

• Question: Why isn’t there an “init_queen”? Answer: First, a “queen_attacks” table would be absolutely huge. A queen on an empty board can move to 27 different squares. Imagine all the ways it could be blocked off from one or more squares. Each of those permutations would need to be in the queen_attacks table, which would make it enormous. Second, we don’t even need it. A queen is basically a combination between a rook and a bishop, so we can ‘make’ queen moves by just getting the rook and bishop attacks for a square and then we combine them.

• Question: I see pawn_attacks, but no pawn_pushes. Where are the pushes stored? Answer: this is one of the few places where the move generator does not store information beforehand, because we can just shift the pawn bits when we want to find out pawn moves. This is actually faster than looking up the new pawn locations. We could have also dispensed with the pawn_attacks array if we wanted to, but having this is very useful to have when determining if a square is attacked or not.

  Sidenote: Pay even more attention to the move generator than you would do to other parts of the chess engine. If there’s a bug here, it will break everything: If the move generator cannot be trusted to generate pseudo-legal moves without fail, you can’t trust any other part of your chess engine either. If the engine generates illegal moves, this will make any user interface such as cutechess kill the game during a match and award a loss. If you are working on different parts of the chess engine later, and something doesn’t work correctly you will know that the problem is in the part you are working on. You MUST have the confidence that the move generator is correct AND that make-unmake are both flawless. There is a saying in software engineering, which counts double and triple for the move generator (and make/unmake): “First make it work correctly. Then make it fast. Then make it pretty.”

  With all of that said, we can take a look into how the non-slider bitboards work.