1

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?

3
  • At first I thought that this might be better for one of the programming SEs, but it might be too chess-specific for them. This isn't remotely enough for an answer, but the programs might prune the branches (I'd swear that I've read that before, but I'm not certain), or communicate with a larger server elsewhere (I doubt this one, though I suppose that some could). Apr 6 at 3:03
  • Are you sure this is not a Rust thing, and an effect of its particular type of memory management? In small footprint chess programs, the programmer usually does all memory management by hand, and throws away data that is no longer useful. Rust doesn't seem to have that, so instead you need to structure your code accordingly. But for that you need a Rust expert, and that's not me.
    – user30536
    Apr 6 at 16:45
  • I think there is no need to store all positions in memory. Instead you can just iterate through all possibilities, pruning most of them with alpha beta pruning. Many positions are transpositions that can be stored in its own hash table. chessprogramming.org/Hash_Table
    – qwr
    Apr 6 at 17:21

2 Answers 2

2

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.

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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