25,161
edits
Changes
Created page with "'''Home * Search * Move Ordering * Refutation Table''' The '''Refutation Table''' is based on a triangular PV-Table utilized in..."
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Refutation Table'''
The '''Refutation Table''' is based on a [[Triangular PV-Table|triangular PV-Table]] utilized in early chess programs with no or only a small [[Transposition Table|transposition table]]. It is used not only to store and re-use the [[Principal Variation|PV]] of the [[Best Move|best root move]], but variants or at least one [[Refutation Move|refutation move]] of all other [[Root|root]] moves, which may be considered during the next [[Iteration|iteration]] of an [[Iterative Deepening|iterative deepening]] framework. However that requires a different update of the triangular [[Array|array]] even at [[Node Types#CUT|Cut-nodes]] at least near the root. Todays modern programs therefor typically abandon the refutation table and rely on transposition table and [[Killer Heuristic|Killer heuristic]].
=History=
In 1982, [[William Fink]], author of the [[Sfinks]] program, mentions to save two moves of the variation for every root move <ref>[[William Fink]] ('''1982'''). ''An Enhancement to the Iterative, Alpha-Beta, Minimax Search Procedure''. [[ICGA Journal#5_1|ICCA Newsletter, Vol. 5, No. 1]]</ref>. [[Tony Marsland]] and [[Jonathan Schaeffer]] mention refutation tables in their respective papers and both quote [[Selim Akl|Selim Akl's]] and [[Monroe Newborn|Monroe Newborn's]] 1977 paper ''The principal continuation and the killer heuristic'' <ref>[[Selim Akl]], [[Monroe Newborn]] ('''1977'''). ''The Principal Continuation and the Killer Heuristic''. 1977 ACM Annual Conference Proceedings</ref> as original source.
==Tony Marsland==
[[Tony Marsland]] mentions refutation table in his 1983 paper <ref>[[Tony Marsland]] ('''1983'''). ''Relative Efficiency of Alpha-beta Implementations''. [[Conferences#IJCAI1983|IJCAI 1983]], [http://webdocs.cs.ualberta.ca/~tony/OldPapers/IJCAI-83.pdf pdf]</ref>:
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 <ref>[[Jonathan Schaeffer]] ('''1989'''). ''The History Heuristic and Alpha-Beta Search Enhancements in Practice''. [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 11, No. 11, [http://ljk.imag.fr/membres//Jean-Guillaume.Dumas/Enseignements/Polys/Externes/schaeffer_history_heuristic.ps.gz zipped ps], [https://eprints.kfupm.edu.sa/70119/1/70119.pdf pdf]</ref>:
'''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'''). ''[http://dl.acm.org/citation.cfm?id=810240 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''. [[ICGA Journal#5_1|ICCA Newsletter, Vol. 5, No. 1]]
* [[Tony Marsland]] ('''1983'''). ''Relative Efficiency of Alpha-beta Implementations''. [[Conferences#IJCAI1983|IJCAI 1983]], [http://webdocs.cs.ualberta.ca/~tony/OldPapers/IJCAI-83.pdf pdf]
* [[Jonathan Schaeffer]] ('''1989'''). ''The History Heuristic and Alpha-Beta Search Enhancements in Practice''. [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 11, No. 11, [http://ljk.imag.fr/membres//Jean-Guillaume.Dumas/Enseignements/Polys/Externes/schaeffer_history_heuristic.ps.gz zipped ps], [https://eprints.kfupm.edu.sa/70119/1/70119.pdf pdf]
* [[Tsan-sheng Hsu]] ('''2012'''). ''Transposition Table, History Heuristic, and other Search Enhancements''. [http://www.iis.sinica.edu.tw/~tshsu/tcg2012/slides/slide10.pdf slides as pdf]
=Postings=
* [http://stackoverflow.com/questions/16235923/alpha-beta-search-iterative-deepening-refutation-table alpha beta search iterative deepening refutation table] by [http://stackoverflow.com/users/854058/bysreg bysreg], [https://en.wikipedia.org/wiki/Stack_Overflow Stack Overflow], April 26, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=55438 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=
<references />
'''[[Move Ordering|Up one level]]'''
The '''Refutation Table''' is based on a [[Triangular PV-Table|triangular PV-Table]] utilized in early chess programs with no or only a small [[Transposition Table|transposition table]]. It is used not only to store and re-use the [[Principal Variation|PV]] of the [[Best Move|best root move]], but variants or at least one [[Refutation Move|refutation move]] of all other [[Root|root]] moves, which may be considered during the next [[Iteration|iteration]] of an [[Iterative Deepening|iterative deepening]] framework. However that requires a different update of the triangular [[Array|array]] even at [[Node Types#CUT|Cut-nodes]] at least near the root. Todays modern programs therefor typically abandon the refutation table and rely on transposition table and [[Killer Heuristic|Killer heuristic]].
=History=
In 1982, [[William Fink]], author of the [[Sfinks]] program, mentions to save two moves of the variation for every root move <ref>[[William Fink]] ('''1982'''). ''An Enhancement to the Iterative, Alpha-Beta, Minimax Search Procedure''. [[ICGA Journal#5_1|ICCA Newsletter, Vol. 5, No. 1]]</ref>. [[Tony Marsland]] and [[Jonathan Schaeffer]] mention refutation tables in their respective papers and both quote [[Selim Akl|Selim Akl's]] and [[Monroe Newborn|Monroe Newborn's]] 1977 paper ''The principal continuation and the killer heuristic'' <ref>[[Selim Akl]], [[Monroe Newborn]] ('''1977'''). ''The Principal Continuation and the Killer Heuristic''. 1977 ACM Annual Conference Proceedings</ref> as original source.
==Tony Marsland==
[[Tony Marsland]] mentions refutation table in his 1983 paper <ref>[[Tony Marsland]] ('''1983'''). ''Relative Efficiency of Alpha-beta Implementations''. [[Conferences#IJCAI1983|IJCAI 1983]], [http://webdocs.cs.ualberta.ca/~tony/OldPapers/IJCAI-83.pdf pdf]</ref>:
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 <ref>[[Jonathan Schaeffer]] ('''1989'''). ''The History Heuristic and Alpha-Beta Search Enhancements in Practice''. [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 11, No. 11, [http://ljk.imag.fr/membres//Jean-Guillaume.Dumas/Enseignements/Polys/Externes/schaeffer_history_heuristic.ps.gz zipped ps], [https://eprints.kfupm.edu.sa/70119/1/70119.pdf pdf]</ref>:
'''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'''). ''[http://dl.acm.org/citation.cfm?id=810240 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''. [[ICGA Journal#5_1|ICCA Newsletter, Vol. 5, No. 1]]
* [[Tony Marsland]] ('''1983'''). ''Relative Efficiency of Alpha-beta Implementations''. [[Conferences#IJCAI1983|IJCAI 1983]], [http://webdocs.cs.ualberta.ca/~tony/OldPapers/IJCAI-83.pdf pdf]
* [[Jonathan Schaeffer]] ('''1989'''). ''The History Heuristic and Alpha-Beta Search Enhancements in Practice''. [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 11, No. 11, [http://ljk.imag.fr/membres//Jean-Guillaume.Dumas/Enseignements/Polys/Externes/schaeffer_history_heuristic.ps.gz zipped ps], [https://eprints.kfupm.edu.sa/70119/1/70119.pdf pdf]
* [[Tsan-sheng Hsu]] ('''2012'''). ''Transposition Table, History Heuristic, and other Search Enhancements''. [http://www.iis.sinica.edu.tw/~tshsu/tcg2012/slides/slide10.pdf slides as pdf]
=Postings=
* [http://stackoverflow.com/questions/16235923/alpha-beta-search-iterative-deepening-refutation-table alpha beta search iterative deepening refutation table] by [http://stackoverflow.com/users/854058/bysreg bysreg], [https://en.wikipedia.org/wiki/Stack_Overflow Stack Overflow], April 26, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=55438 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=
<references />
'''[[Move Ordering|Up one level]]'''
