Author: Larry Griffiths
Date: 15:33:19 02/24/99
Go up one level in this thread
On February 24, 1999 at 18:19:23, Dan Newman wrote: >On February 24, 1999 at 08:18:34, Larry Griffiths wrote: > >>On February 23, 1999 at 15:23:14, Dan Newman wrote: >> >>>On February 23, 1999 at 14:43:29, Larry Griffiths wrote: >>> >>>>On February 23, 1999 at 14:33:03, Larry Griffiths wrote: >>>> >>>>>Dan, >>>>> >>>>>I read your post on hash collisions. I have tried some hamming distance >>>>>code and I see little difference when compared to generating random >>>>>numbers. I have been thinking of writing code that does what you said >>>>>where 64 bits must have 32 bits (or 50%) turned on in each number. I also see >>>>>where there are many references to the 12 pieces times 64 squares = 768 >>>>>hash codes. Pawns only use 48 squares for each side, so 32 squares are unused by pawns. >>>> >>>>Forget my reference to the Bishops. >>>> >>>>>768-48 leaves 720 hashcodes for the piece square table. >>>>>Food for thought? Errors in my thinking? >>>>> >>>>>Larry. >>> >>>That's interesting. You can generate a smaller set of random numbers and >>>fill out only those portions of the table that are actually used. And a >>>smaller set can be better optimized in the same period of time. (Currently, >>>IIRC, I use 1024 numbers for the piece-square part since I use Bob Hyatt's >>>numbering scheme for pieces: P=1,N=2,K=3,B=5,R=6,Q=7 -- which is quite >>>nice for distiguishing sliders from non-sliders.) >>> >>>-Dan. >>> >>>-Dan. >> >>Dan, >> >>I actually only use a power of 2 for my hash keys. If my hash table is >>262144 entries, then I only use 18 bits for a hash key. I currently store >>a 64 bit bitboard in the hash entry for collision checking. I did create >>some code to choose numbers that have exactly 9 bits on with equal distances >>between the numbers. I ran 6 ply test using these keys but it did not seem >>to make much difference. I did try small number of bits and large number of >>bits also. I have a graph in my program to display the hash table usage. >>I saw bands (16 of them) occur when using very few bits per number or >>very many bits per number. I think this is caused by the 16 pawn moves that >>can be made on the very first ply but I am not sure of this. I have "holes" >>in my hash table that only get used after several moves by each side. >> >>Larry. > >I've been playing around with trying to get a better set of numbers >(from the point of view of reducing hashing errors rather than filling >in the holes). But so far I've only managed to increase the error >rate :). (I went from about 1 error per second to 20/s using 32-bit >hashcodes when I tried to generate a good set of numbers with exactly >16 one bits. I'm beginning to think that that wasn't such a great >idea.) I also tried Bob's idea of adding in ~N for every N (I put them >right next to each other in my table) and got no change in error rate >for a very short test. This is also contrary to my expectations... >but I need to do some more extensive tests. > >-Dan. Dan, I even took the rabbit trail down to using prime numbers and hamming distances between numbers. I am thinking that the 16 bands that I saw in my graph were really blacks 16 pieces moving at the 1st ply. I guess I need to fire up that code again and capture a black piece. If 15 bands show up then I've hit the nail on the head. Larry.
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.