A machine considers responses to the queen moves as well, of course. But it must also analyze in detail every other Black move, carefully demonstrating that each of these other moves can be refuted by capturing the Black queen. A six-ply search will have to analyze every one of these moves five further ply, even if the refutations are identical in all cases.

Conventional pruning techniques cannot help here; using ϧ pruning, for example, the entire "main line" (White's winning choices and all of Black's losing responses) must be analyzed even though there is a great deal of apparent redundancy in this analysis. 3 In other search problems, techniques based on the ideas of dependency maintenance (Stallman & Sussman, 1977) can potentially be used to overcome this sort of difficulty. As an example, consider ronological backtracking applied to a map coloring problem. When a dead end is reached and the search backs up, no information is cached and the effect is to eliminate only the specific dead end that was encountered. Recording information giving the reason for the failure can make the search substantially more efficient.

In attempting to color a map with only three colors, for example, thirty countries may have been colored while the detected contradiction involves only five.  By recording the contradiction for those five countries, dead ends that fail for the same reason can be avoided.

Dependency-based methods have been of limited use in practice because of the overhead involved in constructing and using the collection of accumulated reasons. This problem has ben substantially addressed in the work on dynamic backtracking (Ginsberg, 1993) and its successors such as RELSAT (Bayardo & Miranker, 1996), where polynomial limits are placed on the number of nogoods being maintained.

In game search, however, most algorithms already include significant cached information in the form of a transposition table (Greenblatt, Eastlake, & Crocker, 1967; Marsland, 1986).

A transposition table stores a single game position and the backed up value that has been associated with it. The name reflects the fact that many games "transpose" in that identical positions can be reached by swapping the order in which moves are made. The transposition table eliminates the need to recompute values for positions that have already been analyzed.

These collected observations lead naturally to the idea that transposition tables should store not single positions and their values, but sets of positions and their values.  Continuing the dependency-maintenance analogy, a transposition table storing sets of positions can prune the subsequent search far more efficiently than a table that stores only singletons.

There are two reasons that this approach works. The first, which we have already mentioned, is that most game-playing programs already maintain transposition tables, thereby incurring the bulk of the computational expense involved in storing such tables in a more general form. The second and more fundamental reason is that when a game ends with one player the winner, the reason for the victory is generally a local one. A chess game can be thought of as ending when one side has its king captured (a completely local phenomenon);
a checkers game, when one side runs out of moves. Even if an internal search node is evaluated before the game ends, the reason for assigning it any specific value is likely to be independent of some global features (e.g., is the Black pawn on a5 or a6?). Partition search exploits both the existence of transposition tables and the locality of evaluation for realistic games.