25,161
edits
Changes
Created page with "'''Home * Search * Move Ordering * Internal Iterative Deepening''' FILE:Henry Moore at Kew Gardens 563.JPG|border|right|thumb|[[Arts#HenryMoore|Henry..."
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Internal Iterative Deepening'''
[[FILE:Henry Moore at Kew Gardens 563.JPG|border|right|thumb|[[Arts#HenryMoore|Henry Moore]]: Large Upright Internal/External Form <ref>[[Arts#HenryMoore|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> ]]
'''Internal Iterative Deepening (IID)''',<br/>
used in [[Node|nodes]] of the [[Search Tree|search tree]] in a [[Iterative Deepening|iterative deepening]] [[Depth-First|depth-first]] [[Alpha-Beta|alpha-beta]] framework, where a program has no [[Best Move|best move]] available from a previous search [[Principal Variation|PV]] or from the [[Transposition Table|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]] <ref>[[John J. Scott]] ('''1969'''). ''A chess-playing program''. [http://www.doc.ic.ac.uk/~shm/MI/mi4.html Machine Intelligence 4] </ref>, and further elaborated by [[Thomas Anantharaman]] in 1991 <ref>[[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. 1.12 Internal iterative deepening, [[ICGA Journal#14_2|ICCA Journal, Vol. 14, No. 2]]</ref>, as used in [[Deep Thought]] with a reduction of 2 [[Ply|plies]] at [[Node Types#PV|PV-nodes]] and [[Node Types#CUT|cut-nodes]] with no [[Best Move|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 <ref>[[John J. Scott]] and [[Thomas Anantharaman]] referred in [[Omid David]], [[Moshe Koppel]], and [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal]], Vol. 33, No. 2, pp. 67--79</ref>.
=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 [[Node Types#PV|PV-Nodes]], but it is also possible to use it at predicted [[Node Types#CUT|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]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=137538&t=15688 Re: movei hash report] by [[Harm Geert Muller]], [[CCC]], August 13, 2007</ref>
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|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 [[Node Types#PV|PV node]] experiences a dramatic drop in [[Score|score]] (or even any decrease in score) at high search depth. If that move has been best move for many [[Iterative Deepening|ID]] or IID iterations, you will know next to nothing about the other moves. They have always been scoring below [[Alpha|alpha]], all their hashed scores are [[Upper Bound|upper bounds]], and in many cases the upper bounds are no longer usable. (With [[Fail-Hard|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=
* [[John J. Scott]] ('''1969'''). ''A chess-playing program''. [http://www.doc.ic.ac.uk/~shm/MI/mi4.html Machine Intelligence 4]
* [[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. 1.12 Internal iterative deepening, [[ICGA Journal#14_2|ICCA Journal, Vol. 14, No. 2]]
=See also=
* [[Double Null Move]]
* [[Iterative Deepening]]
* [[ProbCut#MPC|Multi–ProbCut]]
* [[Node Types]]
=Forum Posts=
==1998 ...==
* [https://www.stmintz.com/ccc/index.php?id=24521 Internal Iterative Deepening] by [[Roberto Waldteufel]], [[CCC]], August 12, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=92088 Crafty internal iterative deepening] by [[Tijs van Dam]], [[CCC]], January 26, 2000 » [[Crafty]]
* [https://www.stmintz.com/ccc/index.php?id=311269 MTD, IID, fail-low, root-research] by Juergen Wolf, [[CCC]], August 14, 2003 » [[MTD(f)]], [[Fail-Low]], [[Root]]
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4456&p=23208 Something obious on IID that not everybody does] by [[Dann Corbit]], [[Computer Chess Forums|Winboard Forum]], March 04, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4698 self deepening: an improved implementation of IID] by [[Harm Geert Muller]], [[Computer Chess Forums|Winboard Forum]], April 24, 2006
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=137538&t=15688 Re: movei hash report] by [[Harm Geert Muller]], [[CCC]], August 13, 2007 » [[Movei]]
* [http://www.talkchess.com/forum/viewtopic.php?t=23947 Internal Iterative Deepening] by [[Andrew Short]], [[CCC]], September 24, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=25317 Null driven IID] by [[Marco Costalba]], [[CCC]], December 08, 2008
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=35302 iid and singular extensions] by [[Daniel Shawul]], [[CCC]], July 05, 2010 » [[Singular Extensions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=38140 Trouble with IID] by kenny stanley, [[CCC]], February 20, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38408 On internal iterative deepening] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Onno]], [[Node Types]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40484 Internal Iterative Deepening questions] by [[Alcides Schulz]], [[CCC]], September 21, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=44844 Reductions from internal iterative deepening] by [[Evert Glebbeek]], [[CCC]], August 20, 2012 » [[Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=47951 IID and move sorting] by [[Daniel Shawul]], [[CCC]], May 09, 2013 » [[ABDADA]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50419 What do you use IID for] by [[Daniel Shawul]], [[CCC]], December 10, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=51116 IFD vs IID] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], January 30, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=51284 Fail soft vs fail hard] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], February 15, 2014 » [[Fail-Soft]], [[Fail-Hard]], [[Fail-Low]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57374 Hash Refutation] by [[Dennis Sceviour]], [[CCC]], August 24, 2015 » [[Schooner]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61134 Mate scores from IID] by [[Matthew R. Brades]], [[CCC]], August 16, 2016 » [[Checkmate#MateScore|Mate Score]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61229 Value of IID] by [[Thomas Kolarik]], [[CCC]], August 25, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62737 improving iid] by [[Folkert van Heusden]], [[CCC]], January 06, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64321 (I)ID and PV dropout] by [[Harm Geert Muller]], [[CCC]], June 17, 2017 » [[Aspiration Windows]], [[Fail-Low]], [[Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64706 IID (skipped when in check and Score greater than alpha)] by Tamás Kuzmics, [[CCC]], July 24, 2017
=External Links=
* [http://home.hccnet.nl/h.g.muller/deepen.html µ-Max Search: Iterative Deepening] by [[Harm Geert Muller]]
=References=
<references />
'''[[Move Ordering|Up one level]]'''
[[FILE:Henry Moore at Kew Gardens 563.JPG|border|right|thumb|[[Arts#HenryMoore|Henry Moore]]: Large Upright Internal/External Form <ref>[[Arts#HenryMoore|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> ]]
'''Internal Iterative Deepening (IID)''',<br/>
used in [[Node|nodes]] of the [[Search Tree|search tree]] in a [[Iterative Deepening|iterative deepening]] [[Depth-First|depth-first]] [[Alpha-Beta|alpha-beta]] framework, where a program has no [[Best Move|best move]] available from a previous search [[Principal Variation|PV]] or from the [[Transposition Table|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]] <ref>[[John J. Scott]] ('''1969'''). ''A chess-playing program''. [http://www.doc.ic.ac.uk/~shm/MI/mi4.html Machine Intelligence 4] </ref>, and further elaborated by [[Thomas Anantharaman]] in 1991 <ref>[[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. 1.12 Internal iterative deepening, [[ICGA Journal#14_2|ICCA Journal, Vol. 14, No. 2]]</ref>, as used in [[Deep Thought]] with a reduction of 2 [[Ply|plies]] at [[Node Types#PV|PV-nodes]] and [[Node Types#CUT|cut-nodes]] with no [[Best Move|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 <ref>[[John J. Scott]] and [[Thomas Anantharaman]] referred in [[Omid David]], [[Moshe Koppel]], and [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal]], Vol. 33, No. 2, pp. 67--79</ref>.
=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 [[Node Types#PV|PV-Nodes]], but it is also possible to use it at predicted [[Node Types#CUT|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]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=137538&t=15688 Re: movei hash report] by [[Harm Geert Muller]], [[CCC]], August 13, 2007</ref>
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|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 [[Node Types#PV|PV node]] experiences a dramatic drop in [[Score|score]] (or even any decrease in score) at high search depth. If that move has been best move for many [[Iterative Deepening|ID]] or IID iterations, you will know next to nothing about the other moves. They have always been scoring below [[Alpha|alpha]], all their hashed scores are [[Upper Bound|upper bounds]], and in many cases the upper bounds are no longer usable. (With [[Fail-Hard|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=
* [[John J. Scott]] ('''1969'''). ''A chess-playing program''. [http://www.doc.ic.ac.uk/~shm/MI/mi4.html Machine Intelligence 4]
* [[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. 1.12 Internal iterative deepening, [[ICGA Journal#14_2|ICCA Journal, Vol. 14, No. 2]]
=See also=
* [[Double Null Move]]
* [[Iterative Deepening]]
* [[ProbCut#MPC|Multi–ProbCut]]
* [[Node Types]]
=Forum Posts=
==1998 ...==
* [https://www.stmintz.com/ccc/index.php?id=24521 Internal Iterative Deepening] by [[Roberto Waldteufel]], [[CCC]], August 12, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=92088 Crafty internal iterative deepening] by [[Tijs van Dam]], [[CCC]], January 26, 2000 » [[Crafty]]
* [https://www.stmintz.com/ccc/index.php?id=311269 MTD, IID, fail-low, root-research] by Juergen Wolf, [[CCC]], August 14, 2003 » [[MTD(f)]], [[Fail-Low]], [[Root]]
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4456&p=23208 Something obious on IID that not everybody does] by [[Dann Corbit]], [[Computer Chess Forums|Winboard Forum]], March 04, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4698 self deepening: an improved implementation of IID] by [[Harm Geert Muller]], [[Computer Chess Forums|Winboard Forum]], April 24, 2006
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=137538&t=15688 Re: movei hash report] by [[Harm Geert Muller]], [[CCC]], August 13, 2007 » [[Movei]]
* [http://www.talkchess.com/forum/viewtopic.php?t=23947 Internal Iterative Deepening] by [[Andrew Short]], [[CCC]], September 24, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=25317 Null driven IID] by [[Marco Costalba]], [[CCC]], December 08, 2008
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=35302 iid and singular extensions] by [[Daniel Shawul]], [[CCC]], July 05, 2010 » [[Singular Extensions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=38140 Trouble with IID] by kenny stanley, [[CCC]], February 20, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38408 On internal iterative deepening] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Onno]], [[Node Types]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40484 Internal Iterative Deepening questions] by [[Alcides Schulz]], [[CCC]], September 21, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=44844 Reductions from internal iterative deepening] by [[Evert Glebbeek]], [[CCC]], August 20, 2012 » [[Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=47951 IID and move sorting] by [[Daniel Shawul]], [[CCC]], May 09, 2013 » [[ABDADA]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50419 What do you use IID for] by [[Daniel Shawul]], [[CCC]], December 10, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=51116 IFD vs IID] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], January 30, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=51284 Fail soft vs fail hard] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], February 15, 2014 » [[Fail-Soft]], [[Fail-Hard]], [[Fail-Low]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57374 Hash Refutation] by [[Dennis Sceviour]], [[CCC]], August 24, 2015 » [[Schooner]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61134 Mate scores from IID] by [[Matthew R. Brades]], [[CCC]], August 16, 2016 » [[Checkmate#MateScore|Mate Score]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61229 Value of IID] by [[Thomas Kolarik]], [[CCC]], August 25, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62737 improving iid] by [[Folkert van Heusden]], [[CCC]], January 06, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64321 (I)ID and PV dropout] by [[Harm Geert Muller]], [[CCC]], June 17, 2017 » [[Aspiration Windows]], [[Fail-Low]], [[Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64706 IID (skipped when in check and Score greater than alpha)] by Tamás Kuzmics, [[CCC]], July 24, 2017
=External Links=
* [http://home.hccnet.nl/h.g.muller/deepen.html µ-Max Search: Iterative Deepening] by [[Harm Geert Muller]]
=References=
<references />
'''[[Move Ordering|Up one level]]'''
