Author: Christophe Theron
Date: 16:54:43 02/27/01
Go up one level in this thread
On February 27, 2001 at 19:28:52, Ricardo Gibert wrote:
>On February 27, 2001 at 19:17:55, Christophe Theron wrote:
>
>>On February 27, 2001 at 18:57:47, Ricardo Gibert 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.
>>>
>>>That makes sense.
>>>
>>>How about a slight modification: Let's say you decide not to try N + 2, due to
>>>lack of time. You could still decide to do N + 1 and thus only have the odd-even
>>>problem on the last ply. When you don't have time to do N + 1, then you've
>>>avoided the odd-even problem completely.
>>
>>
>>I have noticed that ChessGenius for Palm does that.
>>
>>I tried with my program Chess Tiger, and the results were bad. I think I have
>>spent one week on this, and I was disappointed by the results.
>
>What explanation did you come up with to account for the disappointing results?
The savings are small, and the drawback offset them.
You save in the best case half of the iterations. But that represents only a 30%
saving in the best case (approximately).
On the other hand, your last iteration can discover a "surprise" which could
have already been seen at the previous ply. But you skipped it. When it happens
you spend a lot of time realizing that your best move is not that good, and
another lot of time finding another move. This can easily double the time of
your last iteration. It happens so often that in the end you gained nothing.
Christophe
>>I notice that Genius for PC does not do that anymore. ChessGenius for Palm is
>>the 1987 version of Lang's program, Genius for PC is the 1995 version, so it
>>looks like Lang himself has found it was not such a good idea.
>>
>>
>> Christophe
>>
>>
>>
>>
>>>>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.
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.