Running out of RAM while generating moves

Question

I'm currently building chess engine in Rust from scratch but I am having RAM problems even on calculating 6 ply.

According to Shannon's calculation there are 119,060,324 possible games after ply 6. If you store board position in 100 bytes that is over 11 GB. Machine I am using has 16 GB RAM (~5 GB used by system).

Here is core of my board representation:

pub struct ChessBoard {

    pub white_to_move: bool,

    pub white_pawns: u64,
    pub white_rooks: u64,
    pub white_knights: u64,
    pub white_bishops: u64,
    pub white_queens: u64,
    pub white_king: u64,

    pub black_pawns: u64,
    pub black_rooks: u64,
    pub black_knights: u64,
    pub black_bishops: u64,
    pub black_queens: u64,
    pub black_king: u64,
}

How is it even possible to calculate to 15+ depth when number of positions grows exponentially with each ply? How do chess engines on mobile calculate positions with even less RAM? Am I missing something?

Answer 1

Calculating moves 15-deep doesn't require keeping billions of boards in memory at once, only 16. To simplify: at each ply, you have a current board. You generate legal moves for that board, and maybe prune them. For each remaining legal move, you generate the board resulting from that move, evaluate that board (recursively), and store the resulting score along with the move, then finally return the min/max score. But there's no reason to ever store the complete game tree; you only need the boards on your current call stack, which depends on the depth of your search, not the breadth. The only thing you really need when all is said and done is the single move that you want to play at the first ply.

In fact, there are tricks you could use to get by with less. For instance, with a suitably deterministic move generation algorithm you could avoid ever generating a list of candidate moves — at each level you would only store the "current" candidate move, the best candidate seen so far, and the best score seen so far, and you would have an algorithm to generate the "next" candidate given a board and the "current" candidate, in a way that would reliably explore them all. Similarly, you could have a single board instead of one copy per level, as long as you can perfectly "undo" each move after evaluating it. But those are techniques for engines that only have a few kilobytes of working memory available; for someone who has entire megabytes at their disposal they're probably distractions.

Answer 2

I'm a general programmer, never worked on a chess engine, so take this with a grain of salt. Do you need to keep every position in RAM all at once? Could you instead encode positions as a series of moves away from the current one once it is evaluated, then free the memory? The stockfish code says:

/// A move needs 16 bits to be stored
///
/// bit  0- 5: destination square (from 0 to 63)
/// bit  6-11: origin square (from 0 to 63)
/// bit 12-13: promotion piece type - 2 (from KNIGHT-2 to QUEEN-2)
/// bit 14-15: special move flag: promotion (1), en passant (2), castling (3)

That means up to fifty tempos deep it's smaller to just store the move list than the resulting position. And then you could further optimize, if two move orders transpose into one another you only have to store one in memory. I'm sure this doesn't even scratch the surface of tricks that chess engine developers use to save memory.

Like Charles said, some phone apps do contact a server. Lichess, for example, does when you request analysis. I do not know about chess.com.