Enhanced Transposition Cutoff

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Transposition Table * Enhanced Transposition Cutoff

ETC at node N [1]

Enhanced Transposition Cutoff (ETC) [2],
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.

Maximizing Transpositions

Quote from Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin in Nearly Optimal Minimax Tree Search? [3]:

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. 

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 ...

External Links

References

  1. Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1994, 2014). Nearly Optimal Minimax Tree Search? Technical Report, University of Alberta, arXiv:1404.1518, 4.1 Maximizing Transpositions ETC Image pp. 9
  2. original article by Don Dailey, May 18, 2008
  3. Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1994, 2014). Nearly Optimal Minimax Tree Search? Technical Report, University of Alberta, arXiv:1404.1518

Up one Level