Author: Dann Corbit
Date: 16:34:44 11/13/01
Go up one level in this thread
On November 13, 2001 at 19:19:46, David Hanley wrote: >It's my understanding that the hash codes used in a chess program are hamming >codes, and they are generated such that > >bit_count( code[x]^ code[y] ) > threshold > >for all combinations of codes, obviously self excluded. > >Is this correct? Pretty much. It's just a pedagogic hash, designed to give you linear time access to previously performed calculations, provided that there are not too many collisions. >I plan on using 48 bit hash codes, and my threshold for bit mismatches is >hash_length/6, or in the case of 48 bit keys, 8 bit differences. Is this >sufficient? 64 bits is generally recognized as a good size for a hash, and 32 bits is *definitely* too small. 48 bits might be OK, but if you are playing at long time control, it will possibly be a problem. If someone wants to do correspondence chess analysis with your engine, 48 bits will almost surely be a problem. >In case anyone is interested, here is my code based on the preceeding ( C >programmers may need to recall college days ) > > >(defun count-one-bits( code ) > (if (zerop code) 0 > (+ (logand code 1) (count-one-bits (ash code -1))))) > >(defun make-hamming-generator( key-length ) > (let* ((codes nil) > (mask (reduce '+ (loop for a below key-length collect (ash 1 a)))) > (max-key-plus-one (1+ mask)) > (diff-needed (floor (/ key-length 6)))) > #'(lambda()(loop for new-code = (random max-key-plus-one) > while (notevery > #'(lambda(old-code) > (>= (count-one-bits (logxor new-code old-code)) >diff-needed)) > codes) > finally (push new-code codes)) > (first codes)))) > >(defparameter hamming-generator (make-hamming-generator 48)) > >(defun make-piece-hash-lookup() > (coerce (loop for square from a8 to h1 collect (funcall hamming-generator)) >'vector)) > > >This seems to work ok; i'm not sure if i have the algorithm correct, though. >Calling make-piece-hash-lookup results in the following array: > >#(240170279085727 157334487006636 9089813049686 154959083678061 226620342842881 >78204924498402 244633085803789 156899955215491 237031237910 164881600616497 >168363475253688 156155474458990 231030026344665 235440914478954 79175919103275 >21470603569512 146293660031740 22214488650626 224076450744105 239646307984193 >100952394921585 165248566550692 20146596022633 141378340240624 158654264192495 >80182210780390 114982710855 173203644367048 223043668279052 30743807537030 >12797190696689 164928172387604 87520899558448 13148900165122 76436614325898 >85025785589297 29460841659795 25343613038163 242477885040119 148165520338689 >143799123654291 74321028521355 17174922751244 9362921677848 384652287915 >145403034972295 75790654194956 165534939076792 73937303351286 235910117076048 >216947708138606 100500146927970 226038198553510 84855132191092 173095387051757 >164897250954004 24602714310124 74593417935634 14100624862128 152784460788034 >91829287528635 151735617636368 8474063563847 154910109965829) Seems like it would work. However, in chess -- the Zobrist hash scheme is almost always used. That's because it comes in really handy during make/unmake. You can undo a single move with a single xor and redo a single move with a single xor. You can well imagine what a handy time-saver that is. Have you seen Bruce's tutorial? He really has a wonderful gift for writing. When/if he writes a chess book, I do hereby swear I will buy it if it is less than or equal to $100 in price. Nobody I know of explains things as wonderfully as he does. Anyway, here it is: http://www.seanet.com/~brucemo/topics/topics.htm and hashing (in particular) is here: http://www.seanet.com/~brucemo/topics/zobrist.htm http://www.seanet.com/~brucemo/topics/hashing.htm http://www.seanet.com/~brucemo/topics/repetition.htm While you're there, have a gander at his Alpha-Beta explanation --> which is the only one I have ever seen that is so remarkably good that anyone will get the idea instantly after reading it: http://www.seanet.com/~brucemo/topics/alphabeta.htm
This page took 0.02 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.