Author: Heiner Marxen
Date: 10:17:32 11/20/01
Go up one level in this thread
On November 20, 2001 at 07:38:46, leonid wrote:
>On November 19, 2001 at 15:25:47, Heiner Marxen wrote:
>
>>On November 19, 2001 at 09:36:39, leonid wrote:
>>
[snip]
>>I see. But I do not know of any such initialization, except perhaps the
>>initial clearing of the (possibly huge) hash table, which would not involve
>>any disk I/O.
>
>I have no idea in what way "iterative deepening" could be used for speeding
>search, it is only something that I have read just here in Chess Club.
Normal chess programs use it exactly for the purpose you describe below:
to find a good candidate for a "best" move. The first move in PVS costs
most, all further moves are searched with a minimal alpha/beta window.
When the hash table does not provide a "best move", iterative deepening
can be used to find one. Overall it is faster, I am told.
In Chest I do it for different reasons: I want all, even partial solutions
to be of minimal depth.
> I never
>read no other program code to have my own idea about this. Obviously, I don't
>speak about hash since I don't have such. In my mind, I expected that probable
>usage of best found move for each ply other programs can use in their "next"
>deeper search. I speak about search that is done in your program where it search
>after indication like this: (3 4 5 6 7 8 9...). If somehow after searching 4
>moves deep and restarting search for 5 moves it will receive some help from
>useful variable from previous search for 4 moves?
Yes, I think I did understand that.
> In mine, I was not able to use
>old "best move" for each ply when mine start search in 5 move, after completed
>search in 4.
You were "not able"? Why is that?
> Every variable (including the most important "best move for each
>ply") is initiated and search started from beginning.
Why do you do that?
For sure you can have a best move variable (along with a flag or coding
for "not yet filled"), and not clear it at the start of a search.
>>>Heiner, I wanted to ask you something already few times but manage to forget it
>>>all the time. Are you able to use successfully data when making mate search for
>>>contantly growing depth? I think that this is called "iterative search". If, for
>>>instance, search at depth 3 will make quicker search for you at depth 4?
>>
>>I think you mean "iterative deepening".
>>Yes, I do reuse some data, provided iterative deepening does really happen.
>>The main search routine in Chest is something like this:
>>
>>do_ana(int depth)
>> lodep = 1;
>> hidep = depth;
>> if( found in hash table ) {
>> possibly increase lodep or decrease hidep,
>> or even return result
>> }
>> compute initial data, like list of legal moves
>> for( dep=lodep ; dep<=hidep ; ++dep ) { /* iterative deepening */
>> really do it for depth "dep",
>> reuse move list, and collect some other data for next "dep"
>> for( next legal attacker move ) {
>> ...
>> eventually call recursively do_ana(dep-1)
>> }
>> ...
>> }
>>
>>All variables used in that function are local to the function (stack vars).
>>
>>>In my program I was not able to reuse data. At each new depth all variables are
>>>initiated. When I tried to use search data, it was never successful. I do make
>>>this question thinking that maybe even here I can look for some extra speed that
>>>until now eluded me.
>>
>>Well, there is some potential for extra speed. It is not very common,
>>but it can happen (in the problems you compose it does happen frequently),
>>that the recursive call to do_ana() comes up with more data than was requested,
>>i.e. we asked for a mate-in-3 (say) and it returns "cannot mate-in-63",
>>e.g. because of a forced stalemate, or a forced mate to the attacker.
>>In that case the current attacker move need not be looked at in the next "dep".
>>That also happens with hash table hits and EGTBs.
>>
>>In some cases the gain is significant.
>>
>>I'm not sure what sort of trouble hinders you to "reuse data".
>>Of course, one has to be very careful to only use "valid" data.
>>Since I increase the depth inside the recursive function,
>>I know about the constant context I have, and can manage the rest myself.
>>I do not try to reuse global data across multiple calls of do_ana(),
>>except the hash table, of course.
>
>Probably what I wanted to ask you was about something that you call "global
>data". It could be that you found better use for them, in each next deeper
>search, that me.
Besides the hash table there is not much global data.
There is one cached move for the defender in the mate-in-2, kind of a
killer move.
During the iterative deepening Chest remembers the move list of the attacker,
the "cannot do in X" from every move in that list we have computed so far,
and some info to short-cut underpromotions, when the =Q was refuted by
capturing the promoted piece.
That data is local to the function call (it must be).
[ One could use global arrays, indexed by some depth. ]
Cheers,
Heiner
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.