Do chess engines store all of the previously analysed positions between moves

Question

I am starting to play with chess engines. I notice that the best chess engines can take several minutes to move. I am wondering why. Before each move the engine examines all legal future moves to some depth. However it then seems to repeat this exercise for the next move. Given that the previous move was already included in the tree of moves examined, is this not inefficient ? Or have I misunderstood ?

[Edit: I am assuming that the reason why move analyses are not cached is due to some memory limitations of the computer that just make it faster to restart the analysis]

Answer 1

Programming chess engines is very complicated territory, so right up front I'll point you to the Chess Programming Wiki, which has a lot of great information on this topic.

Background

Chess calculations (and many similar things) are generally modeled and thought of as "game trees" or "decision trees". Broadly, this tree is a directed graph, with one node at the top (the current position), leading to a node for each possible move, each of which leads to more nodes for each possible next move, and so on.

In their most simplistic, brute-force form, Chess engines generate all positions on this tree down to some depth limit ("ply"), evaluating each resulting position based on some complex criteria¹. Then it plays the move that seems to lead to the best result. Nowadays, a lot of really complicated techniques have been developed to limit the number of positions that the engine has to look at, but I'm going to ignore those for the purpose of this answer, because they don't change the real issue at hand.

Math Tangent

The basic reason that engines typically take about the same amount of time to consider each move is that the size of the decision tree increases exponentially with depth (k).

Consider the starting position. The top of the tree (k=0) is one node. There are twenty possible first moves for White, so there are twenty nodes at depth k=1. Then, Black also has twenty available moves for each of White's options: so at k=2, there are 20 * 20 = 400 possible positions! And it only gets worse as the players develop their pieces!

For example, let's pretend that there are always twenty possible moves for each player at any given time². You instruct the computer to look ahead five moves for each player (ten ply). Let's look at the size of the brute-force tree at each level. For fun, we'll also look at the total number of positions in the tree (from the top to the given level).

Ply |    Positions   |  Total Tree Size
----------------------------------------
 0  | 1              | 1
 1  | 20             | 21
 2  | 400            | 421
 3  | 8000           | 8421
 4  | 160000         | 168421
 5  | 3200000        | 3368421
 6  | 64000000       | 67368421
 7  | 1280000000     | 1347368421
 8  | 25600000000    | 26947368421
 9  | 512000000000   | 538947368421
10  | 10240000000000 | 10778947368421

The result of each level being exponentially larger than the previous level is that the size of the whole tree is dominated by the bottom level. Consider the example above: the last level alone contains ten trillion nodes. The entire rest of the tree only contains five hundred billion. The tenth ply contains about 95% of the nodes in the entire tree (this is actually true at each level). In practice, what this means is that all of the search time is spent evaluating the "last" move.

Answer

So how does this relate to your question? Well, let's say the computer is set to ten ply, as above, and further it "remembers" the results of its evaluations. It calculates a move, plays it, and then you make a move. Now two moves have been made, so it prunes all the positions from memory related to the moves that didn't happen, and is left with a tree that goes down the remaining eight moves that it already calculated: 26,947,368,421 positions!

All right! So we only need to calculate the last two ply! Using our 20-moves-at-each-depth estimate, the total number of moves we need to calculate here is still over ten trillion. The positions we already calculated only account for 2.5% of the possibilities! So even by caching last move's results, the best we can hope for is a 2.5% increase in speed! At heart, this is why even if your program caches previous results, you don't usually see a significant speedup between moves (excepting cases when the computer finds a forced mate or something, of course!).

---

Simplification Disclaimer

There is a lot of complexity involved in this question, which is why I linked to the programming wiki at the very top and only attempted to explain the answer in broad mathematical terms. In reality, programs do generally cache parts of the tree from move to move, and there are other reasons why that's insufficient on its own--some simple reasons (e.g. a certain line might look good out to eight moves, but ends with a back-rank mate on move nine!) and many highly complicated ones (generally related to various clever pruning methods). So the computer must keep looking further ahead in an attempt to avoid making bad assumptions based on the previous move's cut-off depth.

---

¹I'm not going to get into heuristic functions here, because that's its own incredibly complex area, but there are frequently some gains that can be achieved via position caching schemes here as well.

²An average branching factor of 20 is probably much too low.

Answer 2

A typical chess engine will store some of the positions and their bracketing alpha-beta scores in a transposition table that can be consulted during subsequent searches. This table isn't consulted directly to choose the next move, but it makes searching for that move more efficient in two ways.

1. A position will likely be encountered multiple times in a search tree, being reached by a transposition or permutation of a sequence of moves. Because the table can be consulted such a position may only need to be evaluated few times (for different fixed search depths) instead of dozens of times as the position is visited and revisited.

2. A standard technique for alpha-beta searches is to use iterative deepening, repeatedly probing the tree at a greater search depth until the terminal depth is reached. The valuation scores computed in earlier iterations are used to order the moves searched in later iterations. Alpha-beta is known to perform better (i.e. prune more of the search tree) if good moves are searched before bad moves.

Answer 3

Example evidencing the memory of the engine:

Consider positions where deep theoretical novelties are discovered, in particular the game Caruana vs Topalov played this year. When you let the engine analyze the position after move 12 for a more or less short amount of time (say 10-15 minutes) you may check the suggested moves and see that the TN (13.Re2!) does not appear among them. Introduce the move yourself, go back a move and let the engine analyze again the same position for more or less the same time. Surprisingly, after some thought, now the engine does consider the TN among the best moves and approves it.

EDIT: The original answer (kept below) is wrong, however, it provides a useful example of the memory of the engine, which has been quoted at the top.

As far as I know, they do not, that is, they start the tree search almost from scratch at every move.

However, they must have some kind of function that actualizes the values for each move, and this function surely has some short-term memory. Some examples are positions where deep theoretical novelties are discovered, in particular the game Caruana vs Topalov played this year. When you let the engine analyze the position after move 12 for a more or less short amount of time (say 10-15 minutes) you may check the suggested moves and see that the TN (13.Re2!) does not appear among them. Introduce the move yourself, go back a move and let the engine analyze again the same position for more or less the same time. Surprisingly, after some thought, now the engine does consider the TN among the best moves and approves it.

I'm no expert on chess software, but this happens. This can be at least partially explained if (as said) the function that evaluates the moves for the position has some memory.

Answer 4

Henry Keiter already gave you a general answer, I'll give you a more technical answer. It's all about transposition table, search depth and cutoff. The discussion here is MUCH more technical than other answers, but it'll be beneficial to whoever wants to learn chess programming.

It's a common misunderstanding that if a position was evaluated before, the evaluation score could be reused as long as there is enough memory to store the moves. Chess programming is more complicated than that. Even given infinite memory, you'd still have to search the positions again. For each move, an evaluation score is attached with its deep and its bound. For instance, if the engine stores a move by fail-high, the table entry would have a lower bound. This means, if you're looking for a position you'd still have to check the bounds whether you can use the previous evaluation score.

Apart from that, each evaluation has a depth attached to it. In an iterative-deepening framework, as you increase the depth for each iteration, you'd still have to search those positions that you have searched already in the previous iteration.

The short answer to your question is that an engine does store all of the previous analyzed positions (as long as enough memory), but those stored results can't be reused as easily as you might have thought. In an opening phase where there are less repetitions, those stored results are most useful for move-ordering and a dozen of move-reduction heuristics. For example, one would assume the best move from the last depth be the best move in the current depth, so we'd sort the move lists and search the best move before any other moves. Hopefully, we'd get an early fail-high cutoff.

We don't have infinite memory for storing the positions. We'd need to define a hashing algorithm. Zobrist hashing algorithm give us a pseudo-random distribution, but sooner or later we'd still have to replace some existing entries.

Answer 5

Each engine has its own time management scheme. Some engines and GUIs let you set the pace at which the engine will play. Engines always calculate/evaluate/minimax as much as they can given the constraints imposed by the time management subroutines or the user settings. If an engine thinks for a long time, it is likely because the time control for the game is a slow one, or the user has set it to play slowly.

Positions and evaluations that the engine has calculated are stored in a hash table. The user can set the size of the available hash in the settings of most UCI engines. The engine itself uses a certain amount of RAM, and if you set your hash table size too high, the computer will start storing hash on your hard-drive in the form of virtual RAM. Hard drive memory is accessed slower than RAM, and you will usually be able to hear the hard drive churning away. A lot of users set the hash table size so that it will fit within the available RAM.

A large proportion of any hash table becomes useless after the engine and its opponent have made their moves as the other positions considered are no longer relevant. The engine will re-use the evaluations stored in hash, but some of the evaluations prove incorrect due to horizon effects once the engine goes deeper down the same line, so it often has to re-order its candidate moves.

Since the amount of hash is finite, an engine also has to make decisions as to what information to delete from its hash as it adds new information. The engine does not know in advance what moves will be played, so it may inadvertently delete information that would have been useful as it adds new data.

Engines in general do not examine all legal moves to a certain depth. They eliminate certain branches of the tree from consideration based on forward and backward pruning. Also, if a leaf-node position has captures or checks yet to be made, the engine will continue down that line until it reaches a quiet (quiescent) position. The actual tree is probably quite deep in some places, while other lines may have been truncated after a small number of moves.