Header format for polyglot books

[Michel]

I think this implies that the polyglot hash function is not as good as an ideal hash function.

Normally one would expect the number of positions needed to be searched to be O(2^64) to get a collision specifically with 0x0.

Of course since the pg hash is linear, one you have a arbitrary collision you can take the xor of the positions to get a collision with zero. So then it would require only O(2^32) steps.

One would not expect a position found in this way to be "reasonable" though.

[hgm]

Maybe we can get Steven Edwards to run perft 14 next - and modify his software to report polyglot keys that are zero! If there are none, then we will at least know we can use this system up to 14 ply without breaking any software.

No chance you wold find a specific key (like 0x0) that way, I guess. You would need a tree of 2^64 positions for that, on average. Of course you would have many collissions within the tree with about 2^32 positions in the tree. But they won't be zero keys.

[Michel]

No chance you wold find a specific key (like 0x0) that way, I guess. You would need a tree of 2^64 positions for that, on average. Of course you would have many collissions within the tree with about 2^32 positions in the tree. But they won't be zero keys.

Did you read my xor comment (which is not entirely valid since you have to rule out multiple piece on the same square, too may piece of the same kind etc...)?

[hgm]

Did you read my xor comment (which is not entirely valid since you have to rule out multiple piece on the same square).

Yes, our postings are badly crossing. My reply was to Don.

XORing two positions in general will give no reasonable position. (0 or 2 Kings per side, two different pieces on one square.)

My earlier proposal of colliding Pawn-only and piece-only keys would do it, though. (In O(2^32) x 2 if your memory was big enough, but a bit longer if you assume only 4GB.)

[Michel]

My earlier proposal of colliding Pawn-only and piece-only keys would do it, though. (In O(2^32) x 2 if your memory was big enough, but a bit longer if you assume only 4GB.)

That would be called "meet in the middle".

Dividing your set of pieces into two equal parts seems indeed the right way to do it.

It seems that one can generate the partial positions in such a way that the two sets of pieces are put on disjoint sets of squares.

[Don]

No chance you wold find a specific key (like 0x0) that way, I guess. You would need a tree of 2^64 positions for that, on average. Of course you would have many collissions within the tree with about 2^32 positions in the tree. But they won't be zero keys.

Did you read my xor comment (which is not entirely valid since you have to rule out multiple piece on the same square, too may piece of the same kind etc...).

My comment was tongue in cheek - I don't expect Steven to run perft(14) to find zero keys.

Don

[petero2]

How did you get this position?

Zobrist hashing is a linear operator if you work in the GF(2) field. Therefore you can compute a null space basis for the operator using standard linear algebra techniques. After that it is just a matter of trying different linear combinations of the basis vectors until you find a vector with desirable properties, such as not too many pieces, exactly one king of each color, not more than one piece on each square and so on.

I computed the basis such that for every non-pawn piece on any square, there is a corresponding set of white and black pawns that cancels out that piece/square. With that basis I can select an arbitrary set of non-pawn pieces and quickly calculate what the required pawns are to get a zero hash key.

I confined the kings to their initial positions and confined the pieces to the first/last rank, then tried different combinations until the number of pawns were <= 8 for each color and no square was occupied by both a white and a black pawn.

[Michel]

I computed the basis such that for every non-pawn piece on any square, there is a corresponding set of white and black pawns that cancels out that piece/square.

To cancel out one piece you would need on average 32 other pieces (assuming that you would naively want to write it as a linear combination of a fixed set of 64 keys). But I guess you searched for solutions which were more sparse?

[petero2]

This is just nitpicking though. I don't believe this header format will cause problems in practice. If you are worried about hash collisions, you should not use the polyglot book format.

Exactly. But _if_ you are worried then you can just regard 0x0 as invalid for book lookup.

Disregarding 0x0 does not solve the problem though, as it only avoids an extremely small fraction of the possible collisions. You would still have problems in the following position for example:
[d]3rk1nq/1p1p4/P1p3p1/1p2p3/3PP3/6P1/1PP4P/R2QK1R1 w - - 0 1
Some other positions that have the same hash as the initial position:

Code: Select all

3rkn1b/p1p4p/3p4/1Pp3p1/PP3p1p/5P2/3P4/1N1RKNBB w - - 0 1
2b1kqrn/5p2/3pp3/5P1p/3pp3/1P2P2P/2PPP3/1QB1KR2 w - - 0 1
1r2kn1b/2p1p3/P7/P3p1p1/1P4Pp/5P2/P3P1P1/BR2KR1Q w - - 0 1
qr1nkrnb/5p2/8/p4P1P/P1p1P2p/8/P1P1P2P/RNN1KRQ1 w - - 0 1
rqn1kn2/2p5/3p4/1P1p4/6P1/pP3P2/1PP3PP/1R1BK1N1 w - - 0 1
nr1rkq2/p7/1pp2p2/6p1/3PpP2/1PP5/2P1P3/BBNRKNQR w - - 0 1
b2bknqr/3p3p/p6p/7P/1p1p1p1P/P1P2P2/1P6/1B2KB2 w - - 0 1
1bbnk2q/4p2p/2p2pp1/p2pPP2/1P2P3/7P/8/QBRNK1N1 w - - 0 1
2b1kqr1/p2p3p/3p4/p2PpP2/PpP2p2/6P1/8/RRB1KQ1N w - - 0 1
2qrkn1r/3p1p2/8/2Pp1p1p/5P2/2PP4/1P2P1PP/1RR1K1N1 w - - 0 1

[petero2]

I computed the basis such that for every non-pawn piece on any square, there is a corresponding set of white and black pawns that cancels out that piece/square.

To cancel out one piece you would need on average 32 other pieces (assuming that you would naively want to write it as a linear combination of a fixed set of 64 keys). But I guess you searched for solutions which were more sparse?

The basis vectors I computed have on average about 32 pawns in them. However it turns out that you don't need to test that many combinations of basis vectors to find positions with much fewer than 32 pawns. To find the position with hash value 0 I had to test roughly 100000 positions.