Examining the search tree

Almost all chess engines go through a search tree, where the nodes are positions and edges are chess moves between the positions. The children of a node are all the positions that can be reached from that position with one legal chess move. Sometimes the legality requirement is loosened to allow pseudolegal moves for efficiency reasons. For example instead of checking for checkmate, it is often sufficient to assign the king a very high value and allow it to be "captured". However, the basic structure of the search tree is the same.

In typical middlegame positions there are around 40 legal moves. The number of legal moves varies between zero (stalemates and checkmates) and 218 (some artificially constructed positions) depending on the position. This is the branching factor of the tree. Let us call it B. Then, the number of nodes at depth D can be estimated with B^D. It is obvious that this number becomes very large quickly when D increases. The following table illustrates this:

Depth	Node count	Time at 10M nodes / s
1	40	0.000004 s
2	1 600	0.00016 s
3	64 000	0.0064 s
4	2 560 000	0.256 s
5	102 400 000	10.24 s
6	4 096 000 000	6 min 49,6 s
7	163 840 000 000	4 h 33 min 4 s
8	6 553 600 000 000	7 d 14 h 2 min 40 s

Consider the time take by the full traversal of the search tree as listed in the table. The 10 million nodes per second speed is realistic for modern chess engines. How is it then possible that they routinely reach depths like 15 or 20 ply at tournament play? They only have a few minutes per move, so they should be able to go only 5-6 ply deep. Half of the answer is that this represents only the worst case scenario with bad move ordering. The backbone of most of the chess engines is some version of the alpha-beta search. If the move order is optimal, it is necessary to search only one child at every other level of the tree. This means that the node count becomes B^D/2 or in other words: the search can be twice as deep. But multiplying the depths in the table with two gives 10-12 ply. That is still less than what is expected, even if the move order were optimal which it is not in practice.

Where does the extra depth come from? There are many factors that contribute to that. One factor is the transposition table. About 15-20 % of the positions encountered during the search happen to be among those already searched. If the results for these positions can be fetched directly from the hash table, it can reduce the number of positions to examine by a factor that for 5-6 plies is around 3. This might mean an extra ply for the search. In the endgame, transposition tables are even more beneficial, and can yield tremendous speed ups.

Another factor is selectivity. While pruning off some moves before the maximum depth is reached is risky and might not produce the correct results, most good chess engines do it. The benefit of getting deeper is greater than occasional miscalculations. If the pruning strategy is well designed, such mistakes can almost completely be avoided. Human intuition says that most moves in most positions are just dumb. However, it is far from easy to implement this intuition in a chess engine.