Answers.Body: <p>Calculating moves 15-deep doesn't require keeping billions of boards in memory at once, only <strong>16</strong>. 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 <em>depth</em> of your search, not the <em>breadth</em>. 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.</p>
  <p>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 <em>list</em> of candidate moves — at each level you would only store the &quot;current&quot; candidate move, the best candidate seen so far, and the best score seen so far, and you would have an algorithm to generate the &quot;next&quot; candidate given a board and the &quot;current&quot; candidate, in a way that would reliably explore them all. Similarly, you could have a <em>single</em> board instead of one copy per level, as long as you can perfectly &quot;undo&quot; each move after evaluating it. But those are techniques for engines that only have a few <em>kilobytes</em> of working memory available; for someone who has entire megabytes at their disposal they're probably distractions.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-04-08T07:41:28.980Z
Answers.LastActivityDate: 2023-04-08T07:41:28.980Z
Answers.UserDisplayName: hobbs
Answers.Body: <p>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:</p>
  <pre><code>/// 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)
  </code></pre>
  <p>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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-04-06T12:41:28.063Z
Answers.LastActivityDate: 2023-04-06T12:41:28.063Z
Answers.UserDisplayName: Awalrod
Body: <p>I'm currently building chess engine in Rust from scratch but I am having RAM problems even on calculating 6 ply.</p>
  <p>According to <a href="https://en.wikipedia.org/wiki/Shannon_number" rel="nofollow noreferrer"><strong>Shannon's calculation</strong></a> there are <strong>119,060,324</strong> 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).</p>
  <p>Here is core of my board representation:</p>
  <pre><code>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,
  }
  
  </code></pre>
  <p><strong>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?</strong></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-04-06T03:03:27.620Z
Comments.Text: 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).
Comments.UserDisplayName: Charles Rockafellor
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-04-06T17:21:02.213Z
Comments.Text: 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. https://www.chessprogramming.org/Hash_Table
Comments.UserDisplayName: qwr
Tags: <engines>
Title: Running out of RAM while generating moves
ThreadText: # Running out of RAM while generating moves
  
  (Asked by: username_0 on 2023-04-06)
  
  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?
  
  **Tags:** engines
  
  > **Comments:**
  > **username_1**: 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).  
  > **username_2**: 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. https://www.chessprogramming.org/Hash_Table  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2023-04-08. Score: 2 | Accepted answer
  
  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 by username_4 on 2023-04-06. Score: 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.
  
  
  ---
  
  