Hashing based on move lists

[lucasart]

This improves collision rate very slightly i.e. xoring the 'from' square for all pieces except bishops. It brought down collision rate from 3000coll/mill to 2900coll/mill. The major problem is that white and black have same keys. Fixing that in such a way that black have ~b reduces collision rate to 100coll/mill ! This is good but still no better than a simple fnv1a that gives 60coll/mill right way. It is simple and fast, OTOH generating attacks with magics is darn slow. For 28 bit key i am sure it would be much worse since attacks sets have some structure that requires all the 64 bit keys for maximum performance.

Code: Select all

U64 gusev(int cp, int sq) {
	int pc = cp / 2;
	int co = cp % 2;
	U64 b=0;
	switch(pc) {
	case 0: b=unitBB(sq) | king_attacks(sq); break;
	case 1: b=unitBB(sq) | knight_attacks(sq); break;
	case 2: b=bishop_attacks(sq,0); break;
	case 3: b=unitBB(sq) | rook_attacks(sq,0); break;
	case 4: b=unitBB(sq) | queen_attacks(sq,0); break;
	case 5: b=unitBB(sq) | pawn_attacks(sq,co); break;
	}
	if(co == 1) b=~b; //black has negation
	return b;
}

Why are you doing all the work for him ?

He hasn't written a single line of code and tested anything himself. So he really doesn't deserve that you spend your time doing his homework, IMO.

Besides, he'll never learn by reading forum posts. He has to do things for himself. Just like the other troll...

[Gusev]

He hasn't written a single line of code and tested anything himself.

You didn't notice that I had posted the code. Some of its lines are mine. And the array of proto-moves found in that code was generated by yet another program that I wrote, but I didn't publish that program. Most folks here have their own attack generators, so no one asked for it.

[Daniel Shawul]

He hasn't written a single line of code and tested anything himself.

You didn't notice that I had posted the code. Some of its lines are mine. And the array of proto-moves found in that code was generated by yet another program that I wrote, but I didn't publish that program. Most folks here have their own attack generators, so no one asked for it.

Eh ? It is code written years ago for a legit discussion we had about reducing number of zobrist keys. The magic attack generation code was ripped of from scorpio who ripped it from Buzz so nothing from you (didn't notice your code until you mentioned it now). Anyway this is silly, because I don't think anybody was doubting you can't write it but that you simply didn't have the testing framework. I had that which i find really helpful so I do it even if it was not asked for it . I can even see the effect that a + and * have on collision rate late alone when it has obvious problems as your scheme.

[Sven]

He hasn't written a single line of code and tested anything himself.

You didn't notice that I had posted the code. Some of its lines are mine. And the array of proto-moves found in that code was generated by yet another program that I wrote, but I didn't publish that program. Most folks here have their own attack generators, so no one asked for it.

Eh ? It is code written years ago for a legit discussion we had about reducing number of zobrist keys. The magic attack generation code was ripped of from scorpio who ripped it from Buzz so nothing from you (didn't notice your code until you mentioned it now). Anyway this is silly, because I don't think anybody was doubting you can't write it but that you simply didn't have the testing framework. I had that which i find really helpful so I do it even if it was not asked for it . I can even see the effect that a + and * have on collision rate late alone when it has obvious problems as your scheme.

Hi Daniel,

while you are talking about your code that you posted here, Dmitri obviously was talking about his own code to which he posted a link in the beginning of his thread. Let's not mix that up.

Apart from that, I fully agree that Dmitri's code seems to be much less tested in a real environment. I think he knows that.

Sven

[Sven]

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.

I would like to emphasize the fundamental difference between the original implementation being flawed, which it is, and the underlying idea of chess-specific non-random hashing being flawed. My PowerPoint presentation mentioned that "it is easier to control and modify the technique to reduce collisions", because I had suspected that such modifications would prove necessary.

Hi Dmitri,

can you explain in some more detail which observation you made with classical Zobrist hashing that lets you believe there is something in it that should be improved? You mentioned the word "luck" in some earlier post, so do you believe that using a pseudo-random generator makes the success of the classical Zobrist hashing method dependent from "luck"?

Have you noticed how the classical method is used in reality? E.g.:
- always using exactly the same set of Zobrist keys (by generating them once and storing them, or by always using the same seed for the PRNG) after having found one "successful" set,
- explicitly measuring the quality of a set of Zobrist keys by measuring hit rates, collision rates, hash table usage ratios, etc.

Regarding the second point of measuring the quality of keys I'd like to add that you will have a hard time to find a PRNG-based set of Zobrist keys that actually has a bad quality, so in fact practically all keys sets are "successful" if you do it right. Nevertheless doing the measurement will be needed to compare the method against another method.

I think it is necessary to go through all these points, i.e. telling exactly what's wrong with the old method and comparing old and new method based on measurements, before introducing a fundamentally new hashing method.

Sven

[hgm]

The funny thing is that basing the keys on the move patterns and location of the pieces is just as much dependent on luck. You should be lucky that the pieces don't move in such a way that the keys do not collide. The Tai Shogi Emperor, for instance, who can move to every square on the board, would have its keys collide for all squares: they would all be -1. If you try to circumvent that by not marking the square the Emperor occupies, (as with the Bishop), keys for the Emperor on two squares just in front of each other, when XORed, would leave only the two squares they occupy set. Which is just the key of a (Tai-Shogi) Pawn. So you would have an order-3 dependency. (Many of them, actually...)

No proof whatsoever is given that Chess is one of the 'lucky' games...

[AlvaroBegue]

The funny thing is that basing the keys on the move patterns and location of the pieces is just as much dependent on luck. You should be lucky that the pieces don't move in such a way that the keys do not collide. The Tai Shogi Emperor, for instance, who can move to every square on the board, would have its keys collide for all squares: they would all be -1. [...]

Of course, this has already been covered by Dmitri before: You could detect this flaw with the scheme when dealing with the Tai Shogi Emperor, and use a different pattern for that piece. For instance, we could use a random pattern of bits. It doesn't even have to be the same pattern translated: Each square could get its own random pattern. If you suspect the attack pattern of other pieces might introduce fragility in the hashing scheme, you could use random patterns for them as well. You could even be proactive and use random patterns for all the pieces. Oh, wait...

[hgm]

[Daniel Shawul]

I am bored so i will just draw a your points with me vs your speech curve

Code: Select all

Points       |
|            |
|            |
|            |
|            |
|            |
|\           |
|   \        |
|      \     |
|         \  |
|           \|
------------------------> Time
|            |
Blabber      Oh wait