Author: David Hanley
Date: 16:19:46 11/13/01
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?
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?
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)
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.