Author: Alex Boby
Date: 10:49:13 05/08/01
Go up one level in this thread
On May 08, 2001 at 03:35:16, Dan Newman wrote: >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. that's a good point, 'cause that's next on my list of things to add... > >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.