Difference between revisions of "Internal Iterative Deepening"

From Chessprogramming wiki
Jump to: navigation, search
Line 1: Line 1:
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Internal Iterative Deepening'''
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Internal Iterative Deepening'''
[[FILE:Henry Moore at Kew Gardens 563.JPG|border|right|thumb|260px|[[:Category:Henry Moore|Henry Moore]] - Large Upright Internal/External Form <ref>[[:Category:Henry Moore|Henry Moore]] sculpture [https://de.wikipedia.org/wiki/Henry_Moore_Sculpture_Perry_Green Large Upright Internal/External Form] (1981/1982) at [https://en.wikipedia.org/wiki/Kew_Gardens Kew Gardens], [https://en.wikipedia.org/wiki/London London], at an extensive exhibition of his work in 2007, [https://commons.wikimedia.org/wiki/File:Henry_Moore_at_Kew_Gardens_563.JPG image] by [https://commons.wikimedia.org/wiki/User:Patche99z Patche99z], October 29, 2007, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]  
[[FILE:Henry Moore, Mother and Child – Hood, St Paul's Cathedral.jpg|border|right|thumb|260px|[[:Category:Henry Moore|Henry Moore]] - Mother and Child : Hood <ref>[[:Category:Henry Moore|Henry Moore]] - [https://atceramicsima.wordpress.com/2016/06/07/mother-and-child-hood-henry-moore-1983/ Mother and Child : Hood], [https://en.wikipedia.org/wiki/St_Paul%27s_Cathedral St Paul's Cathedral], [https://en.wikipedia.org/wiki/London London], Image by James O'Gorman, April 08, 2015, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]  
'''Internal Iterative Deepening (IID)''',<br/>
'''Internal Iterative Deepening (IID)''',<br/>

Revision as of 20:20, 25 May 2020

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


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.


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.


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. 


See also

Forum Posts

1998 ...

2000 ...

2005 ...

2010 ...

2015 ...

External Links


  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