Author: leonid
Date: 04:38:46 11/20/01
Go up one level in this thread
On November 19, 2001 at 15:25:47, Heiner Marxen wrote:
>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.
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. 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? 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. Every variable (including the most important "best move for each
ply") is initiated and search started from beginning.
>>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.
Cheers,
Leonid.
>>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.