25,161
edits
Changes
no edit summary
'''[[Main Page|Home]] * [[Search]] * [[Transposition Table]] * Enhanced Transposition Cutoff'''
[[FILE:ETC.JPG|border|right|thumb|ETC at node N <ref> [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1994, 2014'''). ''[http://arxiv.org/abs/1404.1518?context=cs.AI Nearly Optimal Minimax Tree Search?]'' Technical Report, [[University of Alberta]], [https://arxiv.org/abs/1404.1518 arXiv:1404.1518], ''4.1 Maximizing Transpositions'' ETC Image pp. 9</ref> ]]
'''Enhanced Transposition Cutoff''' (ETC) <ref>[https://chessprogramming.wikispaces.com/page/diff/Enhanced+Transposition+Cutoff/24577949 original article] by [[Don Dailey]], May 18, 2008</ref>,<br/>
=Maximizing Transpositions=
Quote from [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]] and [[Arie de Bruin]] in ''Nearly Optimal Minimax Tree Search?'' <ref> [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1994, 2014'''). ''[http://arxiv.org/abs/1404.1518?context=cs.AI Nearly Optimal Minimax Tree Search?]'' Technical Report, [[University of Alberta]], ''4[https://arxiv.org/abs/1404.1518 arXiv:1404.1 Maximizing Transpositions'' covers ETC1518]</ref>:
The reduction in [[Search Tree|search tree]] size offered by ETC is, in part, offset by the increased computation per node. For chess and [[Checkers|checkers]], it appears the performing ETC at all [[Interior Node|interior nodes]] is too expensive. A compromise, performing ETC at all interior nodes that are more than 2 ply away from the [[Leaf Node|leaves]], results in most of the ETC benefits with only a small computational overhead. Thus, ETC is a practical enhancement to most [[Alpha-Beta]] search programs.
=Publications=
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1994, 2014'''). ''[http://arxiv.org/abs/1404.1518?context=cs.AI Nearly Optimal Minimax Tree Search?]'' Technical Report, [[University of Alberta]], [https://arxiv.org/abs/1404.1518 arXiv:1404.1518]* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1996'''). ''Exploiting Graph Properties of Game Trees.'' [http://www.aaai.org/[Conferences/#AAAI/aaai96.php 13th National Conference on Artificial Intelligence] ([http://www.aaai.org/Press/Proceedings/aaai96.php -96|AAAI-96]), Vol. 1, pp. 234-239, ISBN 978-0-262-51091-2. [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=812B9CDE7707A402265713DD254EE227?doi=10.1.1.50.3346&rep=rep1&type=pdf pdf], [http://webdocs.cs.ualberta.ca/~jonathan/Grad/Papers/graph.ps ps]
=Forum Posts=
