Author: David Rasmussen
Date: 06:14:10 12/09/01
Go up one level in this thread
On December 09, 2001 at 07:31:48, Sune Fischer wrote: >On December 09, 2001 at 06:57:28, David Rasmussen wrote: > >>>About linear independence: If you pick 768 random vectors of length 64, then >>>they span the whole space with probability close to 1 (I haven't exactly >>>computed that, and I don't intend to do it.) >> >>Sure, but that's not the only thing that is important. We want every vector be >>the linear combination of as many basis vectors as possible. If you imagine it >>in three dimensions with a plain orthonormal basis, we don't want the vectors to >>lie close to the axes. We want them scattered equally about. > >If you change just one bit, you are orthonormal to the rest and that is enough, >closeness is not related to spanning at all. > I haven't said that closeness and spanning were related. I am saying that vectors can be a linear combination of, say, 2 basis vectors (a basis from our set, not some other basis), or they can be a linear combination of, say, 37 basis vectors, and 37 is a lot better than 2 for this purpose. >>>As I said before, if your Hamming criterion works better than pure random >>>numbers, that's fine with me; I would just like to understand the reason why. >>>Always the inquisitive mind... >>> >> >>I also would like to know _exactly_ why it works better. As I have said before, >>no one really knows the exact full set of criterions we want for our vectors. > >I suggest we test it, not for 64 bits but for 16-20 bits, then we will cetainly >see collisions. OK. >How do you make those Hamming optimizers? >Do you just generate a lot of keys until they satisfy some requirement? >What you this requirement be for 20 bit keys? > I don't know how others do it. There could be several strategies with different properties. I once did it like this, just to test: We want 1000 vectors (just to pick a nice round number). So we loop 1000 times, and each time, we keep getting a random number until this random number as hamming distance at least n to all other vectors. I found that for 64-bit vectors and for appx. 1000 vectors, it was very hard to get above 23, if I remember correctly. On the other hand, it is _very_ improbable that you will get minimum hamming distance > 17 if you just make 1000 random numbers. Again, this is just from experience, I haven't analyzed why. I know there are algebraic codes with appx. 1000 codewords of length 64 bits that have minimum hamming distance 27. The problem with such numbers is that they don't necesarily spread well with our "usual" hashing function. In fact, they probably spread very badly. Anyway, the way I do it today, is that I have tried several random seeds for my PRNG, and have chosen one that makes the minimum hamming distance of my numbers 17 instead of 11 (which I think is the lowest I have seen). The numbers are still very well distributed and very random. And the avg. hamming distance is still appx. 32. You can easily find several seeds which will give you a set with min. hamming dist. appx. 10, and several seeds wich will give you one with appx. 15. You could then test these sets for all the properties that you want to check, very easily. > >>>Actually, the problem of hash codes is a little bit more complicated, since we >> >>Exactly. >> >>>also want to avoid minor collisions, i.e., different positions occupying the >>>same spot in the transposition table. Since usually the first 20 bits of the >>>hash key determine that position, we would like to avoid linear independence >>>also for small sets of these truncated vectors. Have you tried applying the >>>Hamming criterion to these leading bits? > >Actually I use the mod operator, so I am not 1-bit sensitive for indexing. > Yeah, I use mod too. I don't understand people that use AND. The speed difference is not at all important for a chess program, and it is a much more flexible design, if you want to change the size of you table, or to change the level if you use a two-level table. /David
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.