most similar hashes of two positions

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
brtzsnr
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

most similar hashes of two positions

Post by brtzsnr » Wed Aug 12, 2015 6:16 pm

Based on the thread "Worst Advice" (http://www.talkchess.com/forum/viewtopic.php?t=57235) I propose the following challenge:

Find two distinct positions whose Polyglot keys (http://hgm.nubati.net/book_format.html) have the lowest Hamming distance (fewer distinct bits).

The challenge has two categories:

1. The positions can be crafted.
2. The positions must be reached from the starting position (standard chess rules) by a series of legal moves.

In case of a tie we count the lowest 32 bits. The competition runs until 31st of August (including).

The goal of the challenge is to decide whether the hash move validity checking is necessary. Polyglot keys are used in order to be able to verify the result and to eliminate poor choices of the Zobrist hash values.

Please post your FENs.

bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: most similar hashes of two positions

Post by bob » Wed Aug 12, 2015 6:43 pm

brtzsnr wrote:Based on the thread "Worst Advice" (http://www.talkchess.com/forum/viewtopic.php?t=57235) I propose the following challenge:

Find two distinct positions whose Polyglot keys (http://hgm.nubati.net/book_format.html) have the lowest Hamming distance (fewer distinct bits).

The challenge has two categories:

1. The positions can be crafted.
2. The positions must be reached from the starting position (standard chess rules) by a series of legal moves.

In case of a tie we count the lowest 32 bits. The competition runs until 31st of August (including).

The goal of the challenge is to decide whether the hash move validity checking is necessary. Polyglot keys are used in order to be able to verify the result and to eliminate poor choices of the Zobrist hash values.

Please post your FENs.
I am not sure what there is to decide. You can't represent all chess positions with just 64 bits. So far the best has been around 160 bits or so. mapping 2^160 positions into 2^64 bits clearly will have literally gazillions of positions with a hamming distance of zero. Something like 2^96 such positions roughly...

Collisions (false matches with 64 bit signatures) absolutely happen. If an illegal move will crash your engine, you'd better check 'em or suffer the occasional crash since these are just like death, taxes, and such, there is no escaping them.

mar
Posts: 2001
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: most similar hashes of two positions

Post by mar » Wed Aug 12, 2015 7:05 pm

brtzsnr wrote:Based on the thread "Worst Advice" (http://www.talkchess.com/forum/viewtopic.php?t=57235) I propose the following challenge:

Find two distinct positions whose Polyglot keys (http://hgm.nubati.net/book_format.html) have the lowest Hamming distance (fewer distinct bits).
Hamming distance is not a good measure of hash key quality (this has been shown to me by hgm some time ago).
Actually you can craft Zobrist hashes to maximize Hamming distance but such will perform very very badly.

brtzsnr
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

Re: most similar hashes of two positions

Post by brtzsnr » Wed Aug 12, 2015 7:38 pm

You can set all Zobrist keys to 0 and any two positions will have the same Zobrist hash. However the challenge is that everyone gets to use the same set of Zobrist keys, i.e. the Polyglot key.

Joost Buijs
Posts: 986
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: most similar hashes of two positions

Post by Joost Buijs » Wed Aug 12, 2015 7:39 pm

mar wrote:
brtzsnr wrote:Based on the thread "Worst Advice" (http://www.talkchess.com/forum/viewtopic.php?t=57235) I propose the following challenge:

Find two distinct positions whose Polyglot keys (http://hgm.nubati.net/book_format.html) have the lowest Hamming distance (fewer distinct bits).
Hamming distance is not a good measure of hash key quality (this has been shown to me by hgm some time ago).
Actually you can craft Zobrist hashes to maximize Hamming distance but such will perform very very badly.
Probably the best way to produce Zobrist keys is by digitizing electronic noise or some other physical phenomena.
I never found much difference in hashing performance between the several RNG's I have tried in my engine.
At the moment I use a very simple 64 bit KISS based on Marsaglia.

Code: Select all


struct Kiss64
{
public:
	Kiss64(void);
	u64_t c, x, y, z;
	u64_t Get();
};

Kiss64::Kiss64(void)
{
	c = 0x01b69ab0aff2f240ULL;
	x = 0x112210f4b16c1cb1ULL;
	y = 0x0507a1f38cb440c4ULL;
	z = 0x0003c9a83566fa12ULL;

	// shuffle a while
	for &#40;int i = 0; i < 315; i++) Get&#40;);
&#125;

u64_t Kiss64&#58;&#58;Get&#40;void&#41;
&#123;
	u64_t t;

	t = &#40;x << 58&#41; + c;
	c = x >> 6;
	x += t;
	c += &#40;x < t&#41; ? 1 &#58; 0;
	y ^= y << 13;
	y ^= y >> 17;
	y ^= y << 43;
	z = z * 0x19baffbedULL + 0x12d687; 

	return x + y + z;
&#125;


brtzsnr
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

Re: most similar hashes of two positions

Post by brtzsnr » Wed Aug 12, 2015 7:47 pm

So far the best hamming distance I found is 7.

First position has polyglot key 1904485766542989878,

[D]rnbqkb1r/1ppppp1p/6p1/p3N3/8/8/PPPP1PPP/RNBQKB1R w KQkq - 0 1

Second position has polyglot key 6515045885079009847

[D]rnbqkb1r/pp3ppp/4pn2/3p2N1/8/2p1P1P1/PP2BP1P/RNBQK2R b KQkq - 0 1


Edit: Found one with 7.

Joost Buijs
Posts: 986
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: most similar hashes of two positions

Post by Joost Buijs » Wed Aug 12, 2015 7:57 pm

Some time ago I wrote a Polyglot compatible book generator, it is not to difficult to add add a second set of Zobrist keys and keep track of 2 different hash keys.
When I reach a position where both keys disagree it is almost certain a collision. Maybe a nice experiment for a rainy day.
Last edited by Joost Buijs on Wed Aug 12, 2015 8:00 pm, edited 1 time in total.

mar
Posts: 2001
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: most similar hashes of two positions

Post by mar » Wed Aug 12, 2015 7:58 pm

Joost Buijs wrote:Probably the best way to produce Zobrist keys is by digitizing electronic noise or some other physical phenomena.
I never found much difference in hashing performance between the several RNG's I have tried in my engine.
At the moment I use a very simple 64 bit KISS based on Marsaglia.

Code: Select all


struct Kiss64
&#123;
public&#58;
	Kiss64&#40;void&#41;;
	u64_t c, x, y, z;
	u64_t Get&#40;);
&#125;;

Kiss64&#58;&#58;Kiss64&#40;void&#41;
&#123;
	c = 0x01b69ab0aff2f240ULL;
	x = 0x112210f4b16c1cb1ULL;
	y = 0x0507a1f38cb440c4ULL;
	z = 0x0003c9a83566fa12ULL;

	// shuffle a while
	for &#40;int i = 0; i < 315; i++) Get&#40;);
&#125;

u64_t Kiss64&#58;&#58;Get&#40;void&#41;
&#123;
	u64_t t;

	t = &#40;x << 58&#41; + c;
	c = x >> 6;
	x += t;
	c += &#40;x < t&#41; ? 1 &#58; 0;
	y ^= y << 13;
	y ^= y >> 17;
	y ^= y << 43;
	z = z * 0x19baffbedULL + 0x12d687; 

	return x + y + z;
&#125;

Yes xor-shift is nice (used as bit avalanche in some fast hashing functions).
I'm using a variant of Jenkins-style KISS PRNG, for another project of mine I'm using something even simpler
(not posting seed code but it's basically intializing internal state and then doing n scramble rounds - standard stuff):

Code: Select all

ULong Next64&#40;)
&#123;
	ULong tmp = keys&#91;0&#93;;
	keys&#91;0&#93; += RotateRight&#40; keys&#91;1&#93; ^ 0xcf14f4ebc5462216ull, 1 );
	return keys&#91;1&#93; += RotateRight&#40; tmp ^ 0x9576080c75ecfc58ull, 9 );
&#125;
Internal state is 2 64-bit values and they can even be zero. If the compiler can fold the rotations (Clang has/had? problems here because of the order of post-optimizations applied), it's also pretty fast.

Marsaglia was a very smart guy (RIP), I recently used his nice 1972 approach to get uniformly distributed random 3d points over unit sphere
(can be found here: http://projecteuclid.org/download/pdf_1 ... 1177692644)

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: most similar hashes of two positions

Post by syzygy » Wed Aug 12, 2015 8:03 pm

Joost Buijs wrote:Some time ago I wrote a Polyglot compatible book generator, it is not to difficult to add add a second set of Zobrist keys and keep track of 2 different hash keys.
When I reach a position where both keys disagree it is almost certain a collision. Maybe a nice experiment for a rainy day.
I don't think you have formulated this very carefully.

If you use two different sets of Zobrist key, then the two keys will disagree for almost all positions. And I'm not sure what you mean by a collision of a position (with itself?).

Joost Buijs
Posts: 986
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: most similar hashes of two positions

Post by Joost Buijs » Wed Aug 12, 2015 8:18 pm

syzygy wrote:
Joost Buijs wrote:Some time ago I wrote a Polyglot compatible book generator, it is not to difficult to add add a second set of Zobrist keys and keep track of 2 different hash keys.
When I reach a position where both keys disagree it is almost certain a collision. Maybe a nice experiment for a rainy day.
I don't think you have formulated this very carefully.

If you use two different sets of Zobrist key, then the two keys will disagree for almost all positions. And I'm not sure what you mean by a collision of a position (with itself?).
Well, what I meant is to store both keys with the position, when I add a new position that has already been seen before according to key1 and has not been seen according to key 2, or vice versa, it is almost certain a collision.
For me this is the easiest way, I can do this with a small modification. Since I use a binary tree which uses the first key as value it is not so easy to do it both ways.
Last edited by Joost Buijs on Wed Aug 12, 2015 8:30 pm, edited 1 time in total.

Post Reply