ETC hashing discussion
Robert Hyatt
Here's a problem I had forgotten about. I thought I'd pose it as a
question first time around to see what ideas might be worth trying:
In Crafty, I generate moves in two passes. I first generate only
captures, and then sort by SEE and try the non-losers. I don't generate
non-captures for two reasons: (a) it is trivial to pick out only
captures with bitmaps and (b) I then don't have to skip over the non-
captures when picking out captures to order.
This has a minor problem when trying to do ETC of course, because I
don't generate all the moves until I've tried the captures only. Here's
what I'd think would be my most efficient alternative:
try the hash move. If there is one it is likely the best move. If
there is not, I can generate captures, and quickly "make/unmake them
to see if any would fail low at the next ply, and if so I can select
that move *right now* since it will fail high at this ply, guaranteed.
I would do this before doing any SEE analysis is done, hoping to get a
fail high without sorting the captures at all.
If no captures would cause the fail high condition, I can then pop off
the non-capture moves and try them with the quick make/unmake test to
see if any of them would cause a cutoff.
This seems to be the most efficient approach, given the context of how
I currently produce moves in spurts rather than in splashes...
I can also generate moves twice of course, once to try the ETC idea, and
then throw that away and try the normal move ordering, just as it is. I
don't like generating moves twice. I don't like doing *anything* twice,
even setting or clearing a single bit.
I can generate moves in one batch, test them, and then simply modify my
capture extraction code to skip over non-captures, but this would be a
little slower than the optimal way.
Bottom line:
what is the probability that a capture might cause a cutoff, and if they
don't, what is the probability that another move might? If this is low,
my "optimal" strategy above would work, doing ETC in two phases.
Any ideas or suggestiong or, even better, actual statistics???
Bob
Magnus Heldestad
Robert Hyatt wrote:
I think that generating all moves and try ETC on them first is the
best approach. ETC hits will occur infrequent, but when they do, several
subtrees wont be searched. According to my own tests, it is also good to
give a normal hit in the TT a value of about a pawn capture.
The best thing is probably:
1. generate the next capture move. If no more captures
exists, generate the next noncapture
2. perform a move-hash-update on the move
3. Check for ETC hit, and if so, return immediately
4. save the move and the result from retrieve in 3.
5. if more moves exists, goto 1
6. sort moves in the normal way, modified somewhat
if the retrieve in 3 was a hit
This was, no unnecessary moves are generated when ETC is used.
Further, I strongly suspect that ETC will be more frequent among
capture moves than on noncapture moves, so its probably better
(and faster) to try ETC on captures first.
Magnus H