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 ^{[1]}. 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^{[2]} as original source.

Tony Marsland

Tony Marsland mentions refutation table in his 1983 paper ^{[3]}:

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.

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.

## Table of Contents

Home * Search * Alpha-Beta * Move Ordering * Refutation TableThe

Refutation Tableis 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^{[1]}. Tony Marsland and Jonathan Schaeffer mention refutation tables in their respective papers and both quote Selim Akl's and Monroe Newborn's 1977 paperThe principal continuation and the killer heuristic^{[2]}as original source.## Tony Marsland

Tony Marsland mentions refutation table in his 1983 paper^{[3]}: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 arefutation 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^{[4]}: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

1977).The Principal Continuation and the Killer Heuristic. 1977 ACM Annual Conference Proceedings1982).An Enhancement to the Iterative, Alpha-Beta, Minimax Search Procedure. ICCA Newsletter, Vol. 5, No. 11983).Relative Efficiency of Alpha-beta Implementations. IJCAI 1983, pdf1989).The History Heuristic and Alpha-Beta Search Enhancements in Practice. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 11, No. 11, zipped ps, pdf2012).Transposition Table, History Heuristic, and other Search Enhancements. slides as pdf## Postings

## See also

## References

1982).An Enhancement to the Iterative, Alpha-Beta, Minimax Search Procedure. ICCA Newsletter, Vol. 5, No. 11977).The Principal Continuation and the Killer Heuristic. 1977 ACM Annual Conference Proceedings1983).Relative Efficiency of Alpha-beta Implementations. IJCAI 1983, pdf1989).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## What links here?

Up one level