Hashing based on move lists

[Gusev]

The point is that there isn't a shred of evidence that these keys, or any other one can design or hand-pick, would work any better than randomly picked keys. This seems to be nothing more than wishful thinking.

Even if for the moment we forget about the problem of the black keys, for which you have not proposed a working solution yet, you don't seem to have done even the most elementary analysis of the white set of keys to verify they are sufficiently independent. That you could not find a depence between two or three of them with pencil and paper is hardly an indication. That would also not have been possible with 64-bit random keys.

You're mostly right, with one exception. This is more than wishful thinking. Imagine for a moment that you're running a casino or lottery, so your enterprise's well-being depends on events that happen at random. You're in fine shape, the house seldom loses. But you could still rig the process so that no client ever wins. You don't want to, or the clients will stop coming. But in our application this wouldn't be a problem. We could be happy entirely without collisions. Our problem is different: 64 bits are not enough to eliminate all collisions. As far as the programs' chess strength is concerned, this is not an issue, so this problem is purely theoretical. Still, the pseudo-random approach takes equally good care of positions that can occur in a chess game and those that are invalid or unreachable. Inherently, being general (not chess-specific), it cannot know any better. Intuitively, the chess-specific non-random approach, once perfected, should be able to take better care of the legal/reachable positions at the expense of the other ones. This would make us a slightly happier casino.

[Gusev]

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;
}

Thank you very much for testing the initial approach based on the attacks! The first airplanes were pretty bad compared to contemporary dirigibles as well.

[hgm]

Intuitively, the chess-specific non-random approach, once perfected, should be able to take better care of the legal/reachable positions at the expense of the other ones. This would make us a slightly happier casino.

But your proposed approach does not take into account reachability or legality or maximum number of pieces of a given type at all. The only thing you take into account is how pieces move. Which, intuitively, doesn't provide anything that you could use to reduce collisions. In fact, intuitively using the attack sets seems to be asking for trouble, as in Chess all pieces move pretty much the same (namely along orthogonals or diagonals). So the move patterns resemble each other a lot. Random bit patters on average resemble each other much less. So even intuitively it seems a giant leap backwards.

By picking the attack sets as Zobrist keys, you leave it just as much to chance whether you have bad dependencies as when you picked them at random. But by picking them at random you at least know that the chances were very good. Here you don't even know that. If you are going to select keys, you'd better make sure that they are any good by subjecting them to some test. You don't seem to be prepared to do that at all...

[Daniel Shawul]

Well you are missing the fact that all you did is make computation of keys extra hard by insisting on them being attack sets. That takes much work as evidenced by pradu's code. Now fnv-1a exactly does the same thing but much cheaper and also it is non-random. You can reproduce the same hash key for a given (sq,pic), so I don't understand your premise that it is a non-random approach that can be perfected. There I gave you fnv-1a that is non-random , gives lower collision rates, and is faster. Note that after those changes with bishop and color, your method probably has no glaring holes. If that is the case, then it means the poor structure in the attack sets is what is holding it back from equaling fnv-1a's performance. So this is not like invention of first aeroplane by Wright brothers that is going to result in an Airbus. We are already there and it is lacking

[hgm]

More like an Airbus with the wings sawed off, and someone incessantly insisting this is obviously the better approach to flying, because it makes it lighter, and only needs to be perfected.

[Gusev]

More like an Airbus with the wings sawed off, and someone incessantly insisting this is obviously the better approach to flying, because it makes it lighter, and only needs to be perfected.

It makes it lighter, yes, and it can be transformed into a missile, which will not need such large wings. It'll fly, alright.

[Gusev]

Intuitively, the chess-specific non-random approach, once perfected, should be able to take better care of the legal/reachable positions at the expense of the other ones. This would make us a slightly happier casino.

But your proposed approach does not take into account reachability or legality or maximum number of pieces of a given type at all. The only thing you take into account is how pieces move. Which, intuitively, doesn't provide anything that you could use to reduce collisions. In fact, intuitively using the attack sets seems to be asking for trouble, as in Chess all pieces move pretty much the same (namely along orthogonals or diagonals). So the move patterns resemble each other a lot. Random bit patters on average resemble each other much less. So even intuitively it seems a giant leap backwards.

By picking the attack sets as Zobrist keys, you leave it just as much to chance whether you have bad dependencies as when you picked them at random. But by picking them at random you at least know that the chances were very good. Here you don't even know that. If you are going to select keys, you'd better make sure that they are any good by subjecting them to some test. You don't seem to be prepared to do that at all...

It exploits the number of pieces limitation by placing halos around piece locations. However, it does appear that the attack sets aren't the best choice of halos.

[mvk]

Thank you very much for testing the initial approach based on the attacks! The first airplanes were pretty bad compared to contemporary dirigibles as well.

The first airplane flew because their inventors did the engineering themselves. Prior to that there were a lot of people with "ideas", "analogies" and "intuition". The Wright Brothers didn't rely on intuition in their wing design, they explored the design space meticulously, they actually measured what worked and THEN they flew. This discussion is not on that level until you provide numerical support.

[hgm]

It exploits the number of pieces limitation by placing halos around piece locations. However, it does appear that the attack sets aren't the best choice of halos.

How does that 'exploit the piece limitation'? Why would 'halos' around the piece location work any better if there is just one King as when positions with 32 Kings were just as common as positions with only a single one?

Seems to me you are just dreaming this up...

[syzygy]

Intuitively, the chess-specific non-random approach, once perfected, should be able to take better care of the legal/reachable positions at the expense of the other ones. This would make us a slightly happier casino.

The problem is that this is still just a wish. As far as I can tell, you have not made any advances towards realising this wish.