Author: Richard Pijl
Date: 05:15:45 07/29/04
Go up one level in this thread
On July 29, 2004 at 00:25:04, Stuart Cracraft wrote:
>
>>Before starting the main loop (that does a search of the children) ETC will
>>check the positions reached by each of the children to check the hash signatures
>>and whether a cutoff can be done. With perfect moveordering this will not get
>>you anything. But when not the first but e.g. the third move will get you a beta
>>-cutoff, ETC will enable you to do a cutoff fast, without searching the first
>>two moves. In MTD, the chances that children's positions are already in the
>>hashtable is bigger than in regular PVS, so the gain may be bigger there.
>>
>>But watchout for the pitfalls. Also consider extensions that you may do on
>>certain moves to determine whether an entry found in the hashtable has
>>sufficient depth.
>>
>>What I'm doing to make sure that the cutoff is ok, is that I do not do an
>>immediate cutoff. Instead I replace the hashmove by the move that should create
>>a cutoff according to ETC.
>>This got me a few percent speedup although I'm using PVS.
>>Oh, one thing more: As ETC costs a bit, only do it when the remaining depth is
>>high enough to make up for the costs. I'm only doing ETC based moveordering when
>>there are at least 4 ply to go.
>
>Tried ETC with MTD(f) with 30 position test @ 1 second each
>for any depth in main search (and some quiescence). Total
>tree reduction was 25%. Same for PVS/NEGASCOUT with MTD(f).
>25%.
That is a lot. It makes me wonder whether there are some moveordering tricks
that you haven't tried yet.
>Overhead of ETC was high though and the time savings was
>very small (1%) for ETC-enhanced versions.
ETC is very sensitive to efficiency of implementation. The more inefficient the
implementation, the larger the subtrees have to be to earn something from ETC.
In the Baron I'm not doing a makemove (makemove is very expensive in the Baron),
but I only calculate a new hashkey.
In pseudocode:
if (hashmove found)
get hashtable entry for the hashmove
if (hashmove provides cutoff)
return
for all moves (except hashmove) do
get hashtable entry for the move
if (move provides cutoff)
if (move leads to a repetition and beta > 0)
continue with next move
hashmove=move
return
Another thing to consider is to include repetition checks in the ETC and mark
that the check is done in the movelist so it isn't done twice. That may provide
a few additional cutoffs, especially in the endgame.
Or try to guess whether a node is an allnode and skip ETC (as there are likely
to be no cutoffs).
>Anyway... research results reproduced but practical benefit minor
>for small, fast searches (expected). Need more testing. Probably
>will prove helpful for longer searches typical in a normal game.
>
>Stuart
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.