Refutation Table

Home * Search * Move Ordering * Refutation Table

The Refutation Table is based on a triangular PV-Table utilized in early chess programs with no or only a small transposition table. It is used not only to store and re-use the PV of the best root move, but variants or at least one refutation move of all other root moves, which may be considered during the next iteration of an iterative deepening framework. However that requires a different update of the triangular array even at Cut-nodes at least near the root. Todays modern programs therefor typically abandon the refutation table and rely on transposition table and Killer heuristic.

History

In 1982, William Fink, author of the Sfinks program, mentions to save two moves of the variation for every root move . Tony Marsland and Jonathan Schaeffer mention refutation tables in their respective papers and both quote Selim Akl's and Monroe Newborn's 1977 paper The principal continuation and the killer heuristic as original source.

Tony Marsland

Tony Marsland mentions refutation table in his 1983 paper :

For each initial move in the game tree, the alpha-beta algorithm determines a sequence of moves which is sufficient to cut off the search. These sequences may be stored in a refutation table. After a search to depth D on a tree of constant width W this table will contain W*D entries. Thus upon the next iteration there exists a set of move sequences of length D-ply that are to be tried first. The next ply is then added and the search continues. The candidate principal variation is fully searched, but for the alternate variations the moves in the refutation table may again be sufficient to cut off the search, and thus save the move generation that would normally occur at each node. The storage overhead is very small, although a small triangular table is also needed to identify the refutations. 

Jonathan Schaeffer

Jonathan Schaeffer describes the refutation tables as follows :

Refutation tables. The major disadvantage of transposition tables is their size. Refutation tables attempt to retain one of the advantages of transposition tables, when used with iterative deepening, but with smaller memory requirements. For each iteration, the search yields a path for each move from the root to a leaf node that results in either the correct minimax score or an upper bound on its value. This path from the d - 1 ply search can be used as the basis for the search to d ply. Often, searching the previous iteration’s path or refutation for a move as the initial path examined for the current iteration will prove sufficient to refute the move one ply deeper. 

Publications

• Selim Akl, Monroe Newborn (1977). The Principal Continuation and the Killer Heuristic. 1977 ACM Annual Conference Proceedings
• William Fink (1982). An Enhancement to the Iterative, Alpha-Beta, Minimax Search Procedure. ICCA Newsletter, Vol. 5, No. 1
• Tony Marsland (1983). Relative Efficiency of Alpha-beta Implementations. IJCAI 1983, pdf
• Jonathan Schaeffer (1989). The History Heuristic and Alpha-Beta Search Enhancements in Practice. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 11, No. 11, zipped ps, pdf
• Tsan-sheng Hsu (2012). Transposition Table, History Heuristic, and other Search Enhancements. slides as pdf

Postings

• alpha beta search iterative deepening refutation table by bysreg, Stack Overflow, April 26, 2013
• killer trees by Harm Geert Muller, CCC, February 23, 2015 » Killer Heuristic

See also

• Countermove Heuristic
• Killer Heuristic
• Last Best Reply
• Principal Variation
• Refutation Move
• Transposition Table
• Triangular PV-Table

References

Up one level