25,161
edits
Changes
Created page with "'''Home * Search * Transposition Table * Enhanced Transposition Cutoff''' border|right|thumb|ETC at node N <ref> [[Aske Plaat, Jonath..."
'''[[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'''). ''[http://arxiv.org/abs/1404.1518?context=cs.AI Nearly Optimal Minimax Tree Search?]'' Technical Report, [[University of Alberta]], ''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/>
an attempt to get a [[Beta-Cutoff|cutoff]] from the transposition table, even though an entry may not exist for the current position. Entries may exist for '''children''' of the current position and one of these could be used to produce a cutoff without having to expand the current node. This is done by looping over the legal moves calculating the [[Zobrist Hashing|hash keys]] and doing a transposition table lookup with them in the hopes that one of these will produce the desired cutoff. One enhancement of this idea is to try only the strongest moves, perhaps the first several that are deemed to have potential.
In cases where a cutoff cannot be found, a fairly substantial amount of time is wasted, so in general it should not be applied at shallow depths of the tree where the small sub-tree savings may not justify the extra work. Example code for Enhanced Transposition Cutoff is rather difficult to find. One possible source is [[Fruit]] version 1.5. However, this technique is not used since version 2.0, as tests have shown that it hurts Fruit's strength.
=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'''). ''[http://arxiv.org/abs/1404.1518?context=cs.AI Nearly Optimal Minimax Tree Search?]'' Technical Report, [[University of Alberta]], ''4.1 Maximizing Transpositions'' covers ETC</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.
We also experimented with more elaborate lookahead schemes. For example, ETC transposes the right portion of the tree into the left. ETC can be enhanced to also transpose from left to right. At an interior node, look up all the children’s positions in the transposition table. If no cutoff occurs, then check to see if one of the children leads to a position with a cutoff score that has not been searched deep enough. If so, then use the move leading to this score as the first move to try in this position. Unfortunately, several variations on this idea failed to yield a tangible improvement.
=See also=
* [[Beta-Cutoff]]
* [[Repetitions]]
* [[Transposition]]
=Publications=
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1994'''). ''[http://arxiv.org/abs/1404.1518?context=cs.AI Nearly Optimal Minimax Tree Search?]'' Technical Report, [[University of Alberta]]
* [[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 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=
==1995 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/LNIjJWxKL4U/F5KgDJjQ698J Hash Table test (re: move ordering)] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], February 8, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/P_odidE_noY/_2H_VymEUhIJ Trick Marsland] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], February 15, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/TkhrEajlMCs/r8BRbNjNCt8J Tree search issues!] by [[Magnus Heldestad]], [[Computer Chess Forums|rgcc]], May 26, 1997 » [[MTD(f)]]
: [https://groups.google.com/d/msg/rec.games.chess.computer/TkhrEajlMCs/Cg3pBOLSzv0J Re: Tree search issues!] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], May 26, 1997
: [https://groups.google.com/d/msg/rec.games.chess.computer/TkhrEajlMCs/HgrYwdBcjnEJ Re: Tree search issues!] by [[Aske Plaat]], [[Computer Chess Forums|rgcc]], May 27, 1997
* [https://groups.google.com/d/msg/rec.games.chess.computer/cLAwsdoYWUs/Th9y0jRRc5kJ ETC hashing discussion] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], May 28, 1997
* [https://groups.google.com/d/msg/rec.games.chess.computer/irT5FyNOsBY/5YQzCgeBFKQJ Enhanced Transposition Table Cutoffs] by [[Andrea Zinno]], [[Computer Chess Forums|rgcc]], July 30, 1997
* [https://www.stmintz.com/ccc/index.php?id=18821 Enhanced Transposition Cutoff] by [[Peter Fendrich]], [[CCC]], May 18, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=284050 Programmers: ETC] by [[Peter McKenzie]], [[CCC]], February 13, 2003
* [https://www.stmintz.com/ccc/index.php?id=379495 Enhanced Transposition Cutoff] by [[Stuart Cracraft]], [[CCC]], July 28, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=13005 Enhanced Transposition Cutoff] by [[Chua Kong Sian|kongsian]], [[CCC]], April 10, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=24835 Enhanced Transposition Cutoff] by hcyrano, [[CCC]], November 11, 2008
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=35697 Mult-cut, SE and ETC] by Ricardo Gibert, [[CCC]], August 05, 2010 » [[Multi-Cut]], [[Singular Extensions]]
=References=
<references />
'''[[Transposition Table|Up one Level]]'''
[[FILE:ETC.JPG|border|right|thumb|ETC at node N <ref> [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1994'''). ''[http://arxiv.org/abs/1404.1518?context=cs.AI Nearly Optimal Minimax Tree Search?]'' Technical Report, [[University of Alberta]], ''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/>
an attempt to get a [[Beta-Cutoff|cutoff]] from the transposition table, even though an entry may not exist for the current position. Entries may exist for '''children''' of the current position and one of these could be used to produce a cutoff without having to expand the current node. This is done by looping over the legal moves calculating the [[Zobrist Hashing|hash keys]] and doing a transposition table lookup with them in the hopes that one of these will produce the desired cutoff. One enhancement of this idea is to try only the strongest moves, perhaps the first several that are deemed to have potential.
In cases where a cutoff cannot be found, a fairly substantial amount of time is wasted, so in general it should not be applied at shallow depths of the tree where the small sub-tree savings may not justify the extra work. Example code for Enhanced Transposition Cutoff is rather difficult to find. One possible source is [[Fruit]] version 1.5. However, this technique is not used since version 2.0, as tests have shown that it hurts Fruit's strength.
=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'''). ''[http://arxiv.org/abs/1404.1518?context=cs.AI Nearly Optimal Minimax Tree Search?]'' Technical Report, [[University of Alberta]], ''4.1 Maximizing Transpositions'' covers ETC</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.
We also experimented with more elaborate lookahead schemes. For example, ETC transposes the right portion of the tree into the left. ETC can be enhanced to also transpose from left to right. At an interior node, look up all the children’s positions in the transposition table. If no cutoff occurs, then check to see if one of the children leads to a position with a cutoff score that has not been searched deep enough. If so, then use the move leading to this score as the first move to try in this position. Unfortunately, several variations on this idea failed to yield a tangible improvement.
=See also=
* [[Beta-Cutoff]]
* [[Repetitions]]
* [[Transposition]]
=Publications=
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1994'''). ''[http://arxiv.org/abs/1404.1518?context=cs.AI Nearly Optimal Minimax Tree Search?]'' Technical Report, [[University of Alberta]]
* [[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 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=
==1995 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/LNIjJWxKL4U/F5KgDJjQ698J Hash Table test (re: move ordering)] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], February 8, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/P_odidE_noY/_2H_VymEUhIJ Trick Marsland] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], February 15, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/TkhrEajlMCs/r8BRbNjNCt8J Tree search issues!] by [[Magnus Heldestad]], [[Computer Chess Forums|rgcc]], May 26, 1997 » [[MTD(f)]]
: [https://groups.google.com/d/msg/rec.games.chess.computer/TkhrEajlMCs/Cg3pBOLSzv0J Re: Tree search issues!] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], May 26, 1997
: [https://groups.google.com/d/msg/rec.games.chess.computer/TkhrEajlMCs/HgrYwdBcjnEJ Re: Tree search issues!] by [[Aske Plaat]], [[Computer Chess Forums|rgcc]], May 27, 1997
* [https://groups.google.com/d/msg/rec.games.chess.computer/cLAwsdoYWUs/Th9y0jRRc5kJ ETC hashing discussion] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], May 28, 1997
* [https://groups.google.com/d/msg/rec.games.chess.computer/irT5FyNOsBY/5YQzCgeBFKQJ Enhanced Transposition Table Cutoffs] by [[Andrea Zinno]], [[Computer Chess Forums|rgcc]], July 30, 1997
* [https://www.stmintz.com/ccc/index.php?id=18821 Enhanced Transposition Cutoff] by [[Peter Fendrich]], [[CCC]], May 18, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=284050 Programmers: ETC] by [[Peter McKenzie]], [[CCC]], February 13, 2003
* [https://www.stmintz.com/ccc/index.php?id=379495 Enhanced Transposition Cutoff] by [[Stuart Cracraft]], [[CCC]], July 28, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=13005 Enhanced Transposition Cutoff] by [[Chua Kong Sian|kongsian]], [[CCC]], April 10, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=24835 Enhanced Transposition Cutoff] by hcyrano, [[CCC]], November 11, 2008
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=35697 Mult-cut, SE and ETC] by Ricardo Gibert, [[CCC]], August 05, 2010 » [[Multi-Cut]], [[Singular Extensions]]
=References=
<references />
'''[[Transposition Table|Up one Level]]'''
