Author: Heiner Marxen
Date: 10:58:07 03/25/04
Go up one level in this thread
On March 24, 2004 at 14:44:25, Dieter Buerssner wrote:
>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).
Sure! Things like that (and much more complicated ones) happen all the time.
Otherwise Chest would not be so fast.
>>> 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).
Together with your followup correction that is now quite clear for me.
And I guessed right the first time, actually :-)
>>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.
I agree. And I have nothing to add, except for the depth estimation ideas
below.
>>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.
In Chest my ETC hit frequency reaches 20% or above only for endgame positions
(say with 8 pieces). It can even exceed 70%, there, but with middlegame
positions (most pieces still on board) it does not exceed 15%, and most of the
time it is below 10%.
Of course, for a playing program that may well be quite different.
As always... measure it!
Actually, in Chest I had to restrict the ETC tries near the leafs,
in order to avoid them to cost more than the benefit.
Near the leafs the chance to have a hit is larger, but further up the
potential benefit is larger, so it may be ok, to just not do them
near the leafs (written correctly, this time :-).
>>>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).
LOL! Thanks for pointing out.
>I am not sure, I expressed my thoughts clearer and more correct, this time ...
Yes, you did make it clear, this time, thanks!
>Cheers,
>Dieter
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.