False positive match with a 64 bit signature

[sje]

False positive match with a 64 bit signature

I've been running some more tests with a version of Symbolic equipped with transposition table instrumentation which is used to track false positive matches for signatures less than 128 bits long.

In the current run, a 128 bit mismatch with the bottom 64 bits matching occurred after 18+ billion probes:

Code: Select all

New LSB match high watermark: 64
PETBase: items: 536,870,912   probe: 18,321,249,894   match: 10,402,149,293   stash: 7,944,052,567   usage: 536,870,912   load: 1

[AlvaroBegue]

False positive match with a 64 bit signature

I've been running some more tests with a version of Symbolic equipped with transposition table instrumentation which is used to track false positive matches for signatures less than 128 bits long.

In the current run, a 128 bit mismatch with the bottom 64 bits matching occurred after 18+ billion probes:

Code: Select all

New LSB match high watermark: 64
PETBase: items: 536,870,912   probe: 18,321,249,894   match: 10,402,149,293   stash: 7,944,052,567   usage: 536,870,912   load: 1

How big is your hash table?

[bob]

False positive match with a 64 bit signature

I've been running some more tests with a version of Symbolic equipped with transposition table instrumentation which is used to track false positive matches for signatures less than 128 bits long.

In the current run, a 128 bit mismatch with the bottom 64 bits matching occurred after 18+ billion probes:

Code: Select all

New LSB match high watermark: 64
PETBase: items: 536,870,912   probe: 18,321,249,894   match: 10,402,149,293   stash: 7,944,052,567   usage: 536,870,912   load: 1

That's pretty much in line with the numbers I posted a while back. Only problem now is that 18B nodes can easily be searched in a single move... Fortunately, the paper Cozzie and I wrote showed that such a low rate will have zero impact so long as a false match can't cause a crash.

[AlvaroBegue]

How big is your hash table?

Oh, I guess that's what `items' means. So it's 2^29.

So one very naive estimate of how often you'll have a collision of 64-bit hashes in a hash table of size 2^29 is once every 2^35 bits (yup, just subtract 64-29). The argument is that after a while all entries are filled and every new position visited (which should be the majority of positions visited) will find something with 29 shared bits. The probability of the other 35 bits matching is 2^-35, so the time to a 64-bit collision should follow an exponential distribution with expected value 2^35 (~35 billion).

[Dann Corbit]

False positive match with a 64 bit signature

I've been running some more tests with a version of Symbolic equipped with transposition table instrumentation which is used to track false positive matches for signatures less than 128 bits long.

In the current run, a 128 bit mismatch with the bottom 64 bits matching occurred after 18+ billion probes:

Code: Select all

New LSB match high watermark: 64
PETBase: items: 536,870,912   probe: 18,321,249,894   match: 10,402,149,293   stash: 7,944,052,567   usage: 536,870,912   load: 1

That's pretty much in line with the numbers I posted a while back. Only problem now is that 18B nodes can easily be searched in a single move... Fortunately, the paper Cozzie and I wrote showed that such a low rate will have zero impact so long as a false match can't cause a crash.

It is important for projects like 100% correct perft counts using hash.

[bob]

False positive match with a 64 bit signature

I've been running some more tests with a version of Symbolic equipped with transposition table instrumentation which is used to track false positive matches for signatures less than 128 bits long.

In the current run, a 128 bit mismatch with the bottom 64 bits matching occurred after 18+ billion probes:

Code: Select all

New LSB match high watermark: 64
PETBase: items: 536,870,912   probe: 18,321,249,894   match: 10,402,149,293   stash: 7,944,052,567   usage: 536,870,912   load: 1

That's pretty much in line with the numbers I posted a while back. Only problem now is that 18B nodes can easily be searched in a single move... Fortunately, the paper Cozzie and I wrote showed that such a low rate will have zero impact so long as a false match can't cause a crash.

It is important for projects like 100% correct perft counts using hash.

I'm only interested in actual "chess".

[sje]

To see the growth over time, here is the track for the current run:

Code: Select all

New LSB match high watermark: 2
PETBase: items: 536,870,912   probe: 1   match: 0   stash: 0   usage: 0   load: 0
New LSB match high watermark: 9
PETBase: items: 536,870,912   probe: 4   match: 0   stash: 0   usage: 0   load: 0
New LSB match high watermark: 11
PETBase: items: 536,870,912   probe: 1,101   match: 12   stash: 1,073   usage: 1,073   load: 1.99676e-06
New LSB match high watermark: 12
PETBase: items: 536,870,912   probe: 1,209   match: 13   stash: 1,181   usage: 1,181   load: 2.19978e-06
New LSB match high watermark: 13
PETBase: items: 536,870,912   probe: 1,777   match: 19   stash: 1,742   usage: 1,741   load: 3.24287e-06
New LSB match high watermark: 14
PETBase: items: 536,870,912   probe: 26,763   match: 5,809   stash: 20,937   usage: 20,937   load: 3.89982e-05
New LSB match high watermark: 29
PETBase: items: 536,870,912   probe: 42,988   match: 14,998   stash: 27,972   usage: 27,972   load: 5.21019e-05
New LSB match high watermark: 32
PETBase: items: 536,870,912   probe: 142,097   match: 52,752   stash: 89,329   usage: 89,329   load: 0.000166388
New LSB match high watermark: 33
PETBase: items: 536,870,912   probe: 196,436   match: 74,576   stash: 121,843   usage: 121,843   load: 0.00022695
New LSB match high watermark: 35
PETBase: items: 536,870,912   probe: 1,107,120   match: 470,202   stash: 636,953   usage: 636,902   load: 0.00118632
New LSB match high watermark: 36
PETBase: items: 536,870,912   probe: 1,223,920   match: 524,210   stash: 699,760   usage: 699,689   load: 0.00130327
New LSB match high watermark: 39
PETBase: items: 536,870,912   probe: 2,288,618   match: 1,022,963   stash: 1,265,865   usage: 1,265,604   load: 0.00235737
New LSB match high watermark: 41
PETBase: items: 536,870,912   probe: 7,425,256   match: 3,844,205   stash: 3,584,079   usage: 3,580,715   load: 0.0066696
New LSB match high watermark: 45
PETBase: items: 536,870,912   probe: 27,745,212   match: 15,802,077   stash: 11,972,749   usage: 11,936,025   load: 0.0222326
New LSB match high watermark: 47
PETBase: items: 536,870,912   probe: 78,811,596   match: 45,609,433   stash: 33,298,848   usage: 33,096,876   load: 0.0616477
New LSB match high watermark: 51
PETBase: items: 536,870,912   probe: 186,897,743   match: 107,411,393   stash: 79,702,822   usage: 78,366,234   load: 0.145968
New LSB match high watermark: 52
PETBase: items: 536,870,912   probe: 606,913,432   match: 347,089,742   stash: 260,570,035   usage: 233,468,489   load: 0.434869
New LSB match high watermark: 53
PETBase: items: 536,870,912   probe: 624,426,682   match: 357,079,397   stash: 268,109,969   usage: 239,038,305   load: 0.445244
New LSB match high watermark: 54
PETBase: items: 536,870,912   probe: 1,567,518,297   match: 901,786,172   stash: 667,639,536   usage: 434,567,740   load: 0.809445
New LSB match high watermark: 55
PETBase: items: 536,870,912   probe: 2,389,449,919   match: 1,376,203,623   stash: 1,016,403,455   usage: 499,305,122   load: 0.930028
New LSB match high watermark: 56
PETBase: items: 536,870,912   probe: 2,586,117,443   match: 1,489,653,331   stash: 1,099,902,583   usage: 507,377,949   load: 0.945065
New LSB match high watermark: 58
PETBase: items: 536,870,912   probe: 3,162,834,605   match: 1,821,672,667   stash: 1,345,424,245   usage: 522,668,404   load: 0.973546
New LSB match high watermark: 64
PETBase: items: 536,870,912   probe: 18,321,249,894   match: 10,402,149,293   stash: 7,944,052,567   usage: 536,870,912   load: 1

[sje]

Again, on a different run after 18+ billion probes:

Code: Select all

New LSB match high watermark: 64
PETBase: items: 536,870,912   probe: 18,713,854,731   match: 10,297,295,060   stash: 8,444,618,547   usage: 536,870,912   load: 1

The case of 65 bits matching has not yet been sighted, but I'm sure it will occur sooner or later.