Game History

The chess engine needs to keep a history of all positions that occurred in the game, including the associated data. This is needed for functionality such as move takebacks (which is done during search, for example) and determining if a game is a draw due to three-fold repetition.

There are three ways to keep the game history:

1. Save the entire board, including all the associated states, each time a move is made. When a move is taken back, you restore the previous version of the board with everything in it. This is a simple method to understand and relatively easy to implement, but the drawback is that it is very slow to save and restore the entire board.
2. It is possible to only store the moves that were played. When a move is taken back it is reversed on the board. This means it is not needed to save the entire board or the game state. Saving just the move is very fast. The problem with this method is that it needs to not only undo the move, but also incrementally undo all the associated data, such as the Zobrist Key, Phase and PSQT values, castling, and the en-passant square. This will take extra work and calculation on top of reversing the move, so restoring a board can still be slow.
3. The last option is to save the game state, and include the move that was made from that board position. This stores a bit more data than option 2, but not nearly as much as option 1. Now, when a move is taken back, the previous GameState is restored from history, which restores all incremental state variables instantly. The board still reflects the position after the stored move, so the move encoded in next_move is then retracted to restore the previous position.

I have chosen option 3 in Rustic because I didn’t want to reverse each state variable one by one and I also didn’t want to copy entire boards into the game history.

*Sidenote There is one snag here: We can’t use the board’s own functionality to put and remove pieces on the squares. The unmake function has its own version that don’t touch the incrementally updated states (because they are all instantly recovered when using option 3.) This will be explained in detail in the Unmake Moves section.

The Game History struct to implement this is the last part we need for the board representation, before we can create and initialize a new Board struct. This struct is even simpler than the GameState struct:

pub struct History {
    list: [GameState; MAX_GAME_MOVES],
    count: usize,
}

That’s it. This is just an array holding game states: one for each move, up to the maximum number of moves a game can last. In Rustic, that is 2048 moves, which is far beyond any realistic game length. The “count” member keeps track of the number of elements in use. Now we can write a few useful functions to make the history work like a stack:

The entire implementation looks like this:

impl History {
    // Create a new history array containing game states.
    pub fn new() -> Self {
        Self {
            list: [GameState::new(); MAX_GAME_MOVES],
            count: 0,
        }
    }

    // Put a new game state into the array.
    pub fn push(&mut self, g: GameState) {
        self.list[self.count] = g;
        self.count += 1;
    }

    // Return the last game state and decrement the counter. The game state is
    // not deleted from the array. If necessary, another game state will just
    // overwrite it.
    pub fn pop(&mut self) -> Option<GameState> {
        if self.count > 0 {
            self.count -= 1;
            Some(self.list[self.count])
        } else {
            None
        }
    }

    pub fn get_ref(&self, index: usize) -> &GameState {
        &self.list[index]
    }

    pub fn len(&self) -> usize {
        self.count
    }

    pub fn clear(&mut self) {
        self.count = 0;
    }
}

We’re done. This is the entire History implementation. Note that, for speed reasons, there is no error checking here. If you try to get a reference to an index that does not exist, the engine will panic. If you have no bugs in your engine, this should never happen. Still, Rustic’s chess logic will probably get turned into a library (libRustic) in the future, so error handling may get implemented at that point if the speed cost is not too great.

Now we have everything ready to make a new board struct and initialize it, which will be discussed in the next section.