Answers.Body: <p>A traditional engine does not hold its entire tree in memory. E.g. Stockfish on a 6 core machine can search maybe ten million positions per second. Even if you could store a tree node in just 8 Bytes, that would take 80 MB per second searched. So an hour long search would need hundreds of gigabytes. Instead one uses so called transposition table where the evaluations for certain positions can be stored. Then if a research at a higher depth hits that position again one may already have a sufficiently deep evaluation.</p>
  <p>Obviously the same problem applies, a transposition table won't be big enough to store all positions. Because of that, a new transposition table entry may overwrite an existing entry if no memory is free anymore. That loses the old information, however that is not avoidable one way or another.</p>
  <p>Note that an engine like Leela has a much lower node per second speed. Because of that for it storing the entire tree is possible (and in fact necessary for the PUCT based search that it uses). Even then you can still eventually run out of memory, one way to combat that in practice is the use of a swap file to store a tree larger than your memory. But if that file fills up to then you can't search further.</p>
  <p>As for move generation, for engines that don't store the tree, like Stockfish, one indeed has to re-do the move generation at each point. However that's not much of a problem as a good move generator is very fast so it won't take a lot of time.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-02T12:44:55.040Z
Answers.LastActivityDate: 2020-12-02T12:57:29.830Z
Answers.LastEditDate: 2020-12-02T12:57:29.830Z
Answers.UserDisplayName: koedem
Answers.Body: <p>Yes, they do. They also store the evaluation for each position in the tree. It is critical to store the previously examined positions, because otherwise the computer would have to waste time re-calculating positions that it had already evaluated. In fact, not only chess programs, but any search algorithm usually remembers its search tree, a technique called <a href="https://en.wikipedia.org/wiki/Memoization#:%7E:text=In%20computing%2C%20memoization%20or%20memoisation,the%20same%20inputs%20occur%20again." rel="nofollow noreferrer">memoization</a>.</p>
  <p>The computer copes with limited memory by &quot;pruning&quot; its tree and removing lines that it considers least likely to be important.</p>
  <p>When a new position is calculated, it is given an evaluation score and the legal moves in that position are calculated.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-01T07:51:51.103Z
Answers.Text: "It is critical to store the previously examined positions" Storing and keeping in memory aren't synonymous.
Answers.UserDisplayName: Acccumulation
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-02T12:46:46.217Z
Answers.Text: Pruning is not a way to reduce space complexity, but time complexity instead. Any chess engine would work without pruning just fine, it would just need longer to reach the same search depth. You may be thinking of Leela, which does in fact store the entire search tree. But Stockfish does not.
Answers.UserDisplayName: koedem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-04T18:40:10.663Z
Answers.Text: this answer is just wrong for AB search
Answers.UserDisplayName: Oscar Smith
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-01T05:20:12.607Z
Answers.LastActivityDate: 2020-12-01T05:20:12.607Z
Answers.UserDisplayName: Cecil De Vere
Body: <p>Does a typical brute-force chess engine (e.g. Stockfish) hold its search tree in memory as it applies iterative deepening? If so how does it avoid running out of space? And if not, how does it store the results from each depth before it searches the next ply? It is my understanding that the evaluations from each depth are used to order the possible moves for the next depth, but where are these evaluations and their associated positions stored?</p>
  <p>Also, do engines save the pseudo-legal moves they generate for each position, or do they re-run the move generation function each iteration of the search?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-30T22:51:55.757Z
Comments.Text: I won't answer this question since I'm not an expert, but chess engines (not just Stockfish, but also the MCTS engines) do store their search tree - see https://www.chessprogramming.org/Hash_Table
Comments.UserDisplayName: Allure
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-02T12:49:00.307Z
Comments.Text: @Allure a transposition table doesn't store a full search tree, just some position - evaluation (and bestmove) pairs. This is an important difference because in such a transposition table you can overwrite entries if the table is full, without compromising the search (just possibly needing more time for a re-search later).
  
  Leela on the other hand does store the search tree in its entirety, which is necessarily since Leela expands the tree node by node.
Comments.UserDisplayName: koedem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-02T20:34:34.753Z
Comments.Text: @koedem oh? I thought the traditional engines will store at least some of their search tree, because the previous move's PV is part of the move ordering for the current move.
Comments.UserDisplayName: Allure
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-03T07:32:46.467Z
Comments.Text: @Allure the way this is usually done (at least in my engine it is) is to simply look up the previous PV in the transposition table. Or more generally in any position you first look at the move that is the best move according to the transposition table entry. (if that entry is too low depth to just return immediately) Since most nodes are not PV nodes (i.e. not full window searched) those will usually be protected from overwriting.
Comments.UserDisplayName: koedem
Tags: <engines>
Title: Do Chess Engines hold their Search Tree in Memory?
ThreadText: # Do Chess Engines hold their Search Tree in Memory?
  
  (Asked by: username_0 on 2020-11-30)
  
  Does a typical brute-force chess engine (e.g. Stockfish) hold its search tree in memory as it applies iterative deepening? If so how does it avoid running out of space? And if not, how does it store the results from each depth before it searches the next ply? It is my understanding that the evaluations from each depth are used to order the possible moves for the next depth, but where are these evaluations and their associated positions stored?
  
  Also, do engines save the pseudo-legal moves they generate for each position, or do they re-run the move generation function each iteration of the search?
  
  **Tags:** engines
  
  > **Comments:**
  > **username_1**: I won't answer this question since I'm not an expert, but chess engines (not just Stockfish, but also the MCTS engines) do store their search tree - see https://www.chessprogramming.org/Hash_Table  
  > **username_2**: @username_1 a transposition table doesn't store a full search tree, just some position - evaluation (and bestmove) pairs. This is an important difference because in such a transposition table you can overwrite entries if the table is full, without compromising the search (just possibly needing more time for a re-search later).  Leela on the other hand does store the search tree in its entirety, which is necessarily since Leela expands the tree node by node.  
  > **username_1**: @username_2 oh? I thought the traditional engines will store at least some of their search tree, because the previous move's PV is part of the move ordering for the current move.  
  > **username_2**: @username_1 the way this is usually done (at least in my engine it is) is to simply look up the previous PV in the transposition table. Or more generally in any position you first look at the move that is the best move according to the transposition table entry. (if that entry is too low depth to just return immediately) Since most nodes are not PV nodes (i.e. not full window searched) those will usually be protected from overwriting.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-12-02. Score: 3
  
  A traditional engine does not hold its entire tree in memory. E.g. Stockfish on a 6 core machine can search maybe ten million positions per second. Even if you could store a tree node in just 8 Bytes, that would take 80 MB per second searched. So an hour long search would need hundreds of gigabytes. Instead one uses so called transposition table where the evaluations for certain positions can be stored. Then if a research at a higher depth hits that position again one may already have a sufficiently deep evaluation.
  
  Obviously the same problem applies, a transposition table won't be big enough to store all positions. Because of that, a new transposition table entry may overwrite an existing entry if no memory is free anymore. That loses the old information, however that is not avoidable one way or another.
  
  Note that an engine like Leela has a much lower node per second speed. Because of that for it storing the entire tree is possible (and in fact necessary for the PUCT based search that it uses). Even then you can still eventually run out of memory, one way to combat that in practice is the use of a swap file to store a tree larger than your memory. But if that file fills up to then you can't search further.
  
  As for move generation, for engines that don't store the tree, like Stockfish, one indeed has to re-do the move generation at each point. However that's not much of a problem as a good move generator is very fast so it won't take a lot of time.
  
  
  ---
  
  ### Answer by username_3 on 2020-12-01. Score: 0
  
  Yes, they do. They also store the evaluation for each position in the tree. It is critical to store the previously examined positions, because otherwise the computer would have to waste time re-calculating positions that it had already evaluated. In fact, not only chess programs, but any search algorithm usually remembers its search tree, a technique called [memoization](https://en.wikipedia.org/wiki/Memoization#:%7E:text=In%20computing%2C%20memoization%20or%20memoisation,the%20same%20inputs%20occur%20again.).
  
  The computer copes with limited memory by "pruning" its tree and removing lines that it considers least likely to be important.
  
  When a new position is calculated, it is given an evaluation score and the legal moves in that position are calculated.
  
  > **Comments:**
  > **username_4**: "It is critical to store the previously examined positions" Storing and keeping in memory aren't synonymous.  
  > **username_2**: Pruning is not a way to reduce space complexity, but time complexity instead. Any chess engine would work without pruning just fine, it would just need longer to reach the same search depth. You may be thinking of Leela, which does in fact store the entire search tree. But Stockfish does not.  
  > **username_5**: this answer is just wrong for AB search  
  
  ---
  
  