Sven Schüle wrote:I see a couple of other severe problems of the GusevHashing approach, although I am not sure whether some of these have already been mentioned in this thread:
1) For the 64 bits of a hash key that is built from zobrist keys created through this approach, the probability of a bit being set is not evenly distributed, unlike the standard zobrist hashing approach based on (pseudo-)random numbers. There are several reasons for that, here are some examples:
- pawns are not able to attack squares on rank 1+2 (white) resp. 7-8 (black);
- the probability of central squares being part of any attack set is higher than for squares towards the borders and corners of the board;
- if one bishop is captured but the other of the same player remains on board then half of all squares are more likely to be attacked than the other half.
This leads to bad usage of the hash table since some parts of it will be used less frequently while other parts will get overwritten frequently.
2) From the 64 bits hash key a fixed subset must be used for the table index while the remaining bits (or again a subset of them, or redundantly the whole 64 bit key) are stored as signature in the hash entry. Since the GusevHashing approach essentially associates each hash key bit with a square (an attacked square when looking at attacks on an otherwise empty board for each single piece), the index part of the key will always be associated with a fixed set of squares on the board, e.g. a 24 bit index would be associated with the first three ranks a1 .. h3. But during real games, moves and their corresponding changes of attack sets are not always "randomly" distributed over the board, so it may happen frequently that certain areas of the board are much more affected than others.
Think of pawn endgames as an extreme example, here I believe that there are many positions resulting from subsequent moves of a game that map to exactly the same table index, or to only few different indices, since these moves do not affect the first three ranks. Other endgame types will suffer from similar problems.
3) For the same reason described in 2) there will also be an asymmetric behaviour when using the hash table: moves mainly affecting the non-index squares since they happen on the "black" side of the board (and have mostly "local" effects, as in case of pawn/knight/king moves, or when a rook moves up or down a rank) will rarely lead to a different table index while moves mainly affecting the index squares (happening on the "white" side) do not suffer from that.
Randomness avoids all of that!
Sven
Any opinions to my arguments above?
Or am I wrong when stating that problems like unequal distribution, fixed assocation of hash index bits to certain squares, or asymmetric white-black behaviour are quite a bit more severe than that collision stuff everyone else is thinking about?
I think it would be quite hard to make anything more severe than the collision problem, when you have hundreds of thousands keys with a dependency of 4 in your set (i.e. the 4 keys XOR to zero). E.g. swapping two pieces of equal type (one white, one black) would already give a collision, and such positions are very likely to occur in the same tree.
The other points are a bit like worrying if someone will like the color, when you try to sell him a burnt-out care.
mvk wrote:The conclusion was that:
- Mersenne Twister and Bob Jenkins' 64-bit PRNG are equally as good (properly seeded, obviously).
- LCG even "good ones" (ie. 2^64 periodic that at least passes many of the dieharder tests) are measurably worse.
That is interesting. Do you by any chance also remember references to those measurements that show that LCG's make poor Zobrist keys?
I have always believed that the Mersenne Twister application for chess Zobrist hash codes was a bit of a fad, so I like to see my belief be corrected if it is wrong.
PS: I'm using Park and Miller's to generate individual bytes of the table.
Unfortunately I didn't keep the data nor the code (I rewrote my engine a while back). But as I remember the results were not like day and nighet either. Perhaps it was something like: 32 bit zobrist with LCG is the same as 28 with good PRNG or something like that.
That is a quite significant loss in my view.
Regarding which PRNG to use, I think there are lots of myths flying around. One of them is "cryptographically secure". Cryptographic security (often a misunderstood concept) has nothing to do with how good a generator is for statistics (general purpose PRNG) or for Zobrist hashing.
Mersenne Twister is slow and very complicated.
There are several such fads. One is that the collision rate is somehow related to the birthday paradox. (It isn't, it is only related to the number of bits stored and the number of buckets). Another is that you can improve the codes by maximising the hamming distance between the table entries. I count the Mersenne Twister thing in the same category (until proven otherwise, your finding is interesting in that respect).
PS: What 'n' do you use in the Lehmer generator ?
I use Park & Miller's: n=2**31-1, g=16807. seed = 1. Then peel of the lower 8 bits of each consecutive number and combine them into 64-bit values. I couldn't think of something simpler and portable.
I never noticed any difference in collision rate even with very poor PRNG (like just multiplying with 3+(1<<16) and taking the high-order bits). They were always as would be expected from purely random keys.
But of course I initialized the Zobrist table bytewise, using only 8 high-order bytes from the key. I can imagine that using the low bits of such poorly generated randoms would cause a loss.
lucasart wrote:
PS: What 'n' do you use in the Lehmer generator ?
I use Park & Miller's: n=2**31-1, g=16807. seed = 1. Then peel of the lower 8 bits of each consecutive number and combine them into 64-bit values. I couldn't think of something simpler and portable.
That's probably fine for Zobrist keys. I don't know if it's as good as any other good PRNG though. Perhaps the fact that you only take 1 byte of each run helps. The only way to find out is to reduce the number of bits and measure collisions and compare with other generators.
But as a general purpose generator for random numbers (monte carlo simulations, any statistical methods), I doubt it's good enough. The state space is just too small. I'll have a look and see if it at least passes the DieHarder test (a bare minimum).
I use the 64-bit version from (1), which passes all statistical tests I'm aware of (DieHard, DieHarder, TestU01-BigCrunch), as well as having proven its efficiency in Zobrist collision measurements.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
It is very easy to obtain a good table of random numbers to use in computing Zobrist keys: Try with several different methods and XOR the results together. If at least one of the methods is random enough, the result will be random enough.
Examples of methods:
* Whatever a Mersenne twister spits out.
* Whatever comes out of "/dev/urandom".
* Take a large compressed file, divide it into pieces that are the size of the table and XOR them all together.
My guess is that any of those three methods should be good enough, but I am in good shape even if only one of them is.
As for the subject of this thread, I can come up with collisions on my own in trivial ways, and if they tested their ideas on some deep Perft tests on endgame positions, they would find them right away.
ZirconiumX wrote:
The main point of this is that it has a much lower collision rate than Zobrist keys, even 128-bit ones, but 128 bits is impractical for anything other than Perft, IMO.
On what do you base that conclusion
I can already see a lot of trivial ways to make your keys collide...
Please demonstrate this, since with my stupid eyes I cannot see anything.
Matthew:out
I do not understand what these chess programs do when zobrist key collides.
In my chess program, which has a dreadful performance by the way, I use the hashcode to look up an entry. If there are more entries with the same hashcode an equality operation is applied on the board representation.
I do not want a hash function that possibly may look up wrong positions through collisions. I'm not gona implement a fruit machine. (gambling machine).
Of course there will always be errors in evaluation so it will always be a "gambling machine". So that argument does not hold. I do not know the weights of all these errors that may pile up.
Gusev wrote:Zobrist merely tries to ensure that, for any pair of positions, we are as unlikely to experience a collision as possible. This is not a chess-specific approach. Intuitively, it is somewhat wasteful in its generality, as it is trying to take equal care of pairs of positions one or both of which is illegal/unreachable and pairs of legal reachable positions (the only ones of practical interest). I am trying to design chess-specific hashing "biased" so as to minimize collisions between legal reachable positions. In order to achieve that, pseudo-randomness has to be abandoned. Instead, "intelligent design" is needed, so to speak. I am not claiming that I have already achieved that. But each example that makes legal reachable positions collide can lead to improvement of the directly designed technique. In the meanwhile, bad luck shall remain bad luck, for it's inherent to the non-chess-specific Zobrist approach that employs pseudo-randomness.
I'm afraid you're trying to solve a problem that simply does not exist. Zobrist hashing works very well and certainly well enough that nothing can be gained by further minimising collisions. Any alternative scheme that is less efficient (in terms of cpu cycles and memory usage) is a sure loss, and it is difficult to see how a hashing scheme could be more efficient.
"Nothing can be gained": Depends on how we measure the gain. In terms of Elo points, the gain may be very well be minuscule. In terms of the number of collisions, it may be possible to achieve something. I don't see why chess-specific hashing would be less efficient. The contributions of individual pieces are computed once, at initialization. After that, they are used as before.
Sorry, I did not realise you were proposing Zobrist hashing with specially generated keys.
I suppose an "optimal" set of keys may perform slightly better than an average set of random keys (but probably not measurably better in Elo) provided there was no "bad luck" when creating the random keys (e.g. two keys being identical). With a proper random generator chances of bad luck are quite tiny and with some testing can be eliminated (e.g. by using linear algebra to determine whether there are short linear combinations among the keys).
However, basing a scheme on a binary interpretation of Zobrist keys seems to invite for easy binary-linear relations among the keys and thereby for collisions.
Gusev wrote:
This is a real danger! Indeed, a position with two white rooks collides with a position with two black rooks in the same exact locations. Same happens with two white knights vs. two black knights. However, this won't happen with pawns, because the "footprints" of pawns are asymmetric. The white pawns are "looking up", and the black pawns are "looking down". This suggests a possible fix. Let's make "footprints" of the other pieces artificially asymmetric so as to distinguish the white ones from the black ones by means of this asymmetry. Now, the resulting table of modified "footprints" will no longer have the originally intended dual use (for hash key generation and move generation), but that's not a problem.
That already occurs with one white and black piece color exchanged. Since the -1 xor occurs twice due to two squares affected. Whether the whole key is complemented only depends on the parity of black pieces. Good luck in finding reasonable asymmetries, you may try rotate by 4 for black sliders or arbitrary geometrical pattern like a sets with same Chebyshev distance or taxi-distance from the origin as well
With all sympathies for your twiddling, don't take that too serious, but I agree more with HG, Ricardo and others, that your hashing is flawed. Despite you may use modulo prime or something for the table index though, Sven addressed some more valid points beside collisions.
mvk wrote:The conclusion was that:
- Mersenne Twister and Bob Jenkins' 64-bit PRNG are equally as good (properly seeded, obviously).
- LCG even "good ones" (ie. 2^64 periodic that at least passes many of the dieharder tests) are measurably worse.
That is interesting. Do you by any chance also remember references to those measurements that show that LCG's make poor Zobrist keys?
I have always believed that the Mersenne Twister application for chess Zobrist hash codes was a bit of a fad, so I like to see my belief be corrected if it is wrong.
PS: I'm using Park and Miller's to generate individual bytes of the table.
Unfortunately I didn't keep the data nor the code (I rewrote my engine a while back). But as I remember the results were not like day and nighet either. Perhaps it was something like: 32 bit zobrist with LCG is the same as 28 with good PRNG or something like that.
That is a quite significant loss in my view.
Regarding which PRNG to use, I think there are lots of myths flying around. One of them is "cryptographically secure". Cryptographic security (often a misunderstood concept) has nothing to do with how good a generator is for statistics (general purpose PRNG) or for Zobrist hashing.
Mersenne Twister is slow and very complicated.
There are several such fads. One is that the collision rate is somehow related to the birthday paradox. (It isn't, it is only related to the number of bits stored and the number of buckets). Another is that you can improve the codes by maximising the hamming distance between the table entries. I count the Mersenne Twister thing in the same category (until proven otherwise, your finding is interesting in that respect).
PS: What 'n' do you use in the Lehmer generator ?
I use Park & Miller's: n=2**31-1, g=16807. seed = 1. Then peel of the lower 8 bits of each consecutive number and combine them into 64-bit values. I couldn't think of something simpler and portable.
Yes, portability is a critical issue. We generally want to have the same behavior in windows, linux, 32 bits, 64 bits, etc. so we can compare nodes in different systems. Zobrist keys need to be identical for that.
At one point I decided to put an end to this whole issue and now I use a table of true random numbers taken from here http://www.random.org/
I cannot prove this is optimal, but I do know it cannot be too bad.
