Do Chess Engines hold their Search Tree in Memory?

Question

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?

Answer 1

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 2

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.

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.