Internal Iterative Deepening

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Move Ordering * Internal Iterative Deepening

Henry Moore - Mother and Child : Hood [1]

Internal Iterative Deepening (IID),
used in nodes of the search tree in a iterative deepening depth-first alpha-beta framework, where a program has no best move available from a previous search PV or from the transposition table. IID is used to find a good move to search first by searching the current position to a reduced depth, and using the best move of that search as the first move at the real depth. IID was already introduced by John J. Scott in 1969 inside his program Lancaster [2], and further elaborated by Thomas Anantharaman in 1991 [3], as used in Deep Thought with a reduction of 2 plies at PV-nodes and cut-nodes with no best-move information from the transposition table. While it is pretty much a washout on average, Deep Though used this heuristic since it makes the search times more predictable by avoiding those isolated instances when the search time suddenly becomes 10 times larger than expected [4].

Reduction

The main implementation detail of IID comes with how to reduce the search. Typical reductions include -1, -2, /2, or /4. Some also use either the minimum or the maximum of a subtraction and a division.

Conditions

Where to use IID is also an important question. Limiting the depth is an obvious condition (only use IID if depth > 5, say). Most only use IID in PV-Nodes, but it is also possible to use it at predicted Cut-Nodes.

Insurance

Harm Geert Muller in a reply to Stan Arts on the insurance aspect of IID, in a CCC discussion why IID does not work some programs like Movei and RomiChess [5] 

I completely agree. IID is like an insurance. Most of the time it was not needed, but then it also costs very little. And now and then it saves you big time.

Of course the lousier your basic move ordering, the more you benefit. But then it can be really spectacular, to the point where a program like micro-Max (which does have no move ordering at all, not even a move list, and can only search moves as it generates them) is able to compete with 'serious' engines. IID really works miracles there.

One thing still on my to-do list is to investigate if even more drastic IID would not even be better. I am thinking of situations where a previously best move in a PV node experiences a dramatic drop in score (or even any decrease in score) at high search depth. If that move has been best move for many ID or IID iterations, you will know next to nothing about the other moves. They have always been scoring below alpha, all their hashed scores are upper bounds, and in many cases the upper bounds are no longer usable. (With hard fail they would never be usable!) Disastrously poor moves might very well have the highest upper bounds. To prevent wasting lots of time on such a disastrous move at high search depth, it would make sense to start searching for moves that might beat the new alpha at small depth first, resetting the IID depth back to 1 in PV nodes each time the value of alpha after search of the previous best move drops compared to the previous iteration.

Publications

See also

Forum Posts

1998 ...

2000 ...

2005 ...

2010 ...

2015 ...

2020 ...

External Links

References

  1. ↑ Henry Moore - Mother and Child : Hood, St Paul's Cathedral, London, Image by James O'Gorman, April 08, 2015, Wikimedia Commons
  2. ↑ John J. Scott (1969). A chess-playing program. Machine Intelligence 4
  3. ↑ Thomas Anantharaman (1991). Extension Heuristics. 1.12 Internal iterative deepening, ICCA Journal, Vol. 14, No. 2
  4. ↑ John J. Scott and Thomas Anantharaman referred in Omid David, Moshe Koppel, Nathan S. Netanyahu (2010). Genetic Algorithms for Automatic Search Tuning. ICGA Journal, Vol. 33, No. 2, pp. 67--79
  5. ↑ Re: movei hash report by Harm Geert Muller, CCC, August 13, 2007

Up one level

Retrieved from "https://www.chessprogramming.org/index.php?title=Internal_Iterative_Deepening&oldid=21435"