Author: Dan Newman
Date: 00:35:16 05/08/01
Go up one level in this thread
On May 08, 2001 at 01:58:00, Alex Boby wrote:
>
>This has probably been asked a thousand times in the past so sorry for asking
>but I grep'd the archives and didn't find anything satisfying so here goes...
>
>How do most people deal with hash key collisions (2 positions, same key)? These
>cause problems for me currently because of illegal moves. I figure that there
>are 2 solutions...
>
>1) store the actual unique board position in the hash record for comparision.
>2) check the moves stored in the hash table to see if they are valid before
>using them.
>
>1 doesn't seem like a plausible solution (gigantic hash records) and 2 seems
>like it would be slow unless I could find a trick to do it easily.
>
>Is there a standard solution to this problem?
>
>Alex
I check the move for legality, but only because an illegal move could
easily crash my program. The collision rate is so low with 64-bit hash
codes that an illegal move should be extremely rare. If your program
can tolerate making illegal moves (most can't, I think) you could save
some cpu cycles by not testing the move. I suspect the collision rate
is less than one per day with a 64-bit hash code and a node rate of,
say, 500 knps.
If you do killer moves, you'll need a fast legality checker anyway.
Speeding up the legality check depends a lot on what information is
available in your basic data structures that represent the game state.
I have (for instance) a variable that indicates double check. If in
double check, anything but a king move is illegal.
Actually, I don't do a full legality check since I generate pseudo-legal
moves and have to apply certain tests to every move that I make anyway.
I.e., the legality checker that I use on hash table moves and killers
doesn't check to see if the king is left en prise by the move--that gets
caught later.
I think about all I do is
1) test for non-king move if in double check
2) test to see if piece of proper type is on from-square
3a) test to see if to-square is clear or if to-square has opponent
piece in the case this is a capture move
4) make sure the way is clear for a sliding move
more or less the same things that the pseudo-legal move generator has to
do when generating a move.
(I just looked at an old profile output and my is_valid() function
consumes about 1 percent of the cpu time, so it's probably a lot
cheaper generally to do this than store the board in the hash record.)
-Dan.
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.