Author: Dieter Buerssner
Date: 11:44:25 03/24/04
Go up one level in this thread
On March 23, 2004 at 08:31:38, Heiner Marxen wrote:
>On March 22, 2004 at 16:55:23, Dieter Buerssner wrote:
>
>>On March 22, 2004 at 12:11:19, Heiner Marxen wrote:
>>
>>>I have not yet looked at fruit source, but from my own recollection how
>>>to do ETC... in Chest I restrict the usage of ETC to non-trivial depths.
>>>If the expected work without ETC probing is too small, the overhead of
>>>ETC is does not pay off. May be fruit does restrict it in such a way,
>>>that even the additional overhead of move make/undo is small compared
>>>to the potential savings.
>>
>>Are you using any search extensions in Chest?
>
>No, definitely not. The basic function of Chest is very tightly coupled
>to a real "ply depth". A mate in 3 is at most 5 plies deep... in every
>branch, otherwise it would _not_ be a mate in 3, right?
Yes, I thought so, that extensions were no issue for chest. But perhaps pruning?
(Trivial example: I am looking for a mate for side to move, but this side has no
pieces/pawns left).
>> I think, this is a real problem
>>for a normal playing engine. Assume some "mate threat extensions" (decision for
>>such an extension for example by doing a shallow search after a null move). I
>>see no method, to keep the extensions consistent for ETC, without doing that
>>search again. And now, this is not only a makemove, but a real search with many
>>makemoves ...
>
>I'm not sure I really understand...
I was confused, sorry. What I meant was something like this.
absearch(side, alpha, beta, depth)
{
int extension = -1;
lookup_ht(depth);
/* Possible cutoff here, if not ... */
/* Now I thought, try the ETC stuff here */
if (not_in_check && ... )
{
/* Try null move */
score = -absearch(xside, ...);
if (score > beta)
return;
if (score is get_mated_soon_score)
ext +=1; /* mate thread */
/* One could probe around a zero window with large negative score instead */
/* score = -absearch(xside, MATE-1000, MATE, some_shallow_depth); */
/* THis would give more reliable thread detection */
}
/* But doing here the ETC-Stuff would solve the problem */
for (all moves)
{
ext += calc_extension(current_move); /* or pruning */
score = -absearch(xside, -beta, -alpha, depth+ext);
... /* adjust alpha, beta, cutoffs, ... */
}
...
/* Added this here to the pseudo code, so one can see with which depths/drafts
positions will be stored, probed. Slightly other schemes might be
possible, but this one should at least be consistent. */
store_to_ht(depth);
}
Doing the ETC-stuff at the second point, I indicated, would get rid of the
problem I meant. But you lose the possibility, to avoid the null move search
(because it may influence the search depth of following searches, and you need
to know this, for consistent ETC). Other searches may follow before the for (all
moves) loop. For example to detect singular moves in another way, or internal
iterative deepening. If I now thought correctly, one would have to delay ETC
until the last thing happened, that will influence the new depth (or var ext,
above).
>I understand that extensions are decided upon along with moves, sometimes
>after the move has been executed, already. And just inspecting the resulting
>board is not always sufficient to decide whether an extension has been done
>at the last move, so we have to extend first, and only then have to look
>into the TT.
>
>For ETC this means (in order to be able to decide whether the depth in the TT
>is sufficient) we have not only to compute the hash resulting from a move,
>but also the extensions we would do for it... what may be a problem.
>Is this what you mean?
Yes. Also, what I called "calc_extension()" above, is all over the place of my
search code. It does sometimes use some information, that was collected at
several stages of the search code. So it is not a trivial copy and paste to
collect it in a function. Some other info must be communicated to the function,
too. So, it is sort of a mess. What sounds so easy in theory (the ETC idea),
seems to be quite some work.
>For Chest this is no problem at all, fortunately ;-)
>Therefore I havn't yet thought about this problem: it just did not occur to me.
>
>I suspect that easy to calculate estimates (upper and lower bound) will
>fail to decide the most frequent case of a hash hit... but what about
>the even more frequent case of a cache miss? Cache hit rates are typically
>below 20%, so 80+% of the TT lookups should be decidable with the hash code
>alone, right? Depth estimates could decide some more cases, and the rest
>would need something more sophisticated.
>Hmmm... if we really have to make a move in order to decide a TT hit,
>this destroys a large part of the benefits of ETC... :-(
I think, this wouldn't be too bad. Just don't do ETC very close to the leafs,
and the overhead should be small. BTW. I think hash hits are typically higher
than 20% (only a little in early middle game, and much in late endgame). As I
said, I wouldn't be too worried about the overhead of doing a real makemove.
>>Already keeping normal extensions (that do not depend on a new search, only on
>>the position and previous moves) consistent seems not easy, for a "grown"
>>engine, that did not think of encapsulating search extension decisions in a
>>function, but rather has it all over the place in a long search routine.
>>
>>It might still be an idea that works, when some special searches are included to
>>calculate extensions.
>
>Something like a restricted 1-ply search?
Or other shallow (perhaps depth dependant) searches.
>Sounds kind of complicated,
>and does not pay off near the leaves of the search tree.
I had the same typo in my engine for a long time. I called the nodes leave
nodes, which actually are leaf nodes (I thought, it came from "to leave"(/stop)
the recursion).
I am not sure, I expressed my thoughts clearer and more correct, this time ...
Cheers,
Dieter
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.