Enhanced Transposition Cutoff (ETC) [1],
an attempt to get a 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 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.
The reduction in search tree size offered by ETC is, in part, offset by the increased computation per node. For chess and checkers, it appears the performing ETC at all interior nodes is too expensive. A compromise, performing ETC at all interior nodes that are more than 2 ply away from the 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.
an attempt to get a 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 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.
Table of Contents
Maximizing Transpositions
Quote from Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin in Nearly Optimal Minimax Tree Search? [3]: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
Publications
Forum Posts
1995 ...
Re: Tree search issues! by Robert Hyatt, rgcc, May 26, 1997
Re: Tree search issues! by Aske Plaat, rgcc, May 27, 1997
2000 ...
2005 ...
2010 ...
References
What links here?
Up one Level