8

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?

4
  • 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 chessprogramming.org/Hash_Table
    – Allure
    Nov 30, 2020 at 22:51
  • @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.
    – koedem
    Dec 2, 2020 at 12:49
  • @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.
    – Allure
    Dec 2, 2020 at 20:34
  • 1
    @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.
    – koedem
    Dec 3, 2020 at 7:32

2 Answers 2

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.

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.

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.

3
  • "It is critical to store the previously examined positions" Storing and keeping in memory aren't synonymous. Dec 1, 2020 at 7:51
  • 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.
    – koedem
    Dec 2, 2020 at 12:46
  • 1
    this answer is just wrong for AB search Dec 4, 2020 at 18:40

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.