Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Iterative deepening deep increment

Author: Robert Hyatt

Date: 18:40:04 02/27/01

Go up one level in this thread


On February 27, 2001 at 19:20:48, Christophe Theron wrote:

>On February 27, 2001 at 18:36:03, Robert Hyatt wrote:
>
>>On February 27, 2001 at 17:08:16, Alvaro Jose Povoa Cardoso wrote:
>>
>>>By definition the iterative deepening procedure calls Search() several times,
>>>and each time it increments _Depth_ by one.
>>>But what if we increment by two?
>>>Isn't a waste of time stepping just one ply deep at a time?
>>>In my checkers program, I increment _Depth_ by two (2,4,6,8,10,12,14,16...) and
>>>it seams to work better than stepping by one ply (2,3,4,5,6,7,8,9,10,11,12,...).
>>>Surely a previous search at _Depth-2_ gives a good PV to try first at this
>>>iteration.
>>>Comments anyone?
>>>Does this aply to chess?
>>>
>>>Thank you
>>>Alvaro Cardoso
>>
>>
>>There are a couple of issues:
>>
>>1.  each iteration takes about 3x as long as the previous if you increment
>>depth by 1.  If you increment depth by 2, then each iteration will take about
>>9x as long.  If iteration N takes 1 minute, you have a target of 3 minutes,
>>you will choose to not try N+2 as there is no hope of finishing it.  It actually
>>makes more sense to go in .5 ply increments near the end of the search since
>>that gives you a better chance of finishing an 12.5 ply search when a 12 ply
>>search would be too quick and a 13 ply search would take too long.
>>
>>2.  BeBe did odd ply searches.  The reason was to eliminate the odd-even
>>problem where odd ply searches are aggressive, even ply searches are more
>>passive.  But he had the problem described in 1 above.
>
>
>The idea is interesting but if you have a QSearch then you have no control on
>where (odd or even) the search stops. So BeBe's way will not work if you have a
>QSearch.

Bebe had a q-search.  But in normal positions, _many_ pathways end at the last
regular ply with no useful captures to be made.  IE even in Crafty I often
do a 12 ply search and get a 12 ply PV.  And those turn out to be subject
to the odd/even phenom.




>
>And what about extensions? You think you are going to do an even ply search,
>then a check extension happens and you end up doing an odd depth search!


That really doesn't matter.  If it turns an even into an odd, then it will
turn an odd into an even...  Note that _I_ don't put much stock in the
approach...  I don't do it, and have never done it.  I have noticed that
"junior" does something similar...  it increments the ply depth by numbers
> 1 early in the search process, then as time gets closer to running out it
seems to go by 1's...

I tend to think that makes more sense since he counts plies differently
and he effectively goes by a ply early and then a fraction of a ply for
later searches...


>
>
>    Christophe



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.