Author: Heiner Marxen
Date: 12:25:47 11/19/01
Go up one level in this thread
On November 19, 2001 at 09:36:39, leonid wrote:
>
>>Small depths do not gain from the hash table. From Chest:
>>
>> static Bool
>>job_dep_wants_acm( int jt, int depth )
>>{
>> /*
>> * For a repeated position we need at least 4 plies (two full moves).
>> * Since we ask at the start of "do_ana()", where the attacker is
>> * to move, an additional preply turns out to make no difference.
>> */
>> switch( jt ) {
>> default:
>> case JT_normal:
>> case JT_stalemate:
>> case JT_selfmate:
>> case JT_selfstalemate:
>> break; /* take default rule below */
>> case JT_helpmate:
>> case JT_helpstalemate:
>> return depth >= 3; /* since storing jobs of depth >= 1 */
>> }
>> return depth >= 4; /* since storing jobs of depth >= 2 */
>>}
>
>It is true what you have said. To even use hash you must have certain depth to
>make it fonctional. But I have seen with Rebel even more simple reason why hash
>is not effective with less that 5 moves. It look like that program do initially
>certain work with hard disk in order to initialize something. If it is really
>so, it could be that this initialization work is just too big to be payed back
>at shallow depth.
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.
>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.
>Cheers,
>Leonid.
CU,
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.