Coincidental perft(7) results

[sje]

Coincidental perft(7) results

Consider the following two positions, both from the unique(7) set:
[d]rnb1kbnr/ppp1pppp/6q1/3pB3/8/3P4/PPP1PPPP/RNQ1KBNR b KQkq - 5 4[/d]
[d]rnbk1bnr/pppp1ppp/4p3/7Q/4P2q/P7/1PPPBPPP/RNB1K1NR b KQ - 4 4[/d]
Both have the same perft(7) subtotal: 82,553,447,078

There are tens of thousands of such examples, evidence of the Birthday Paradox at work.

https://en.wikipedia.org/wiki/Birthday_problem

[stegemma]

I don't know if the birthday paradox works here. The perft(N) of a position should be in this range:

minimum = min^N
maximum = max^N

where min is the minimum of moves in any position of the full perft(N) tree and max the maximum. For sample, in a position with KP vs K:

minimum = (3+3)^N
maximum = (28+8+8)^N

if N is not high enough to let the pawn to promote:

minimum = (3+3)^N
maximum = (1+8+8)^N or (2+8+8)

So, if you have two different positions, the perft(N) value of each is two maybe different ranges but still the probability to have similar value should be the same to have two identical values a=b:

minimum'<= a <= maximum'
minimum''<= b <= maximum''

So, the birthday paradox would apply only if the ranges of possibile values are the same for all positions. The same is for birthday days of human: if we let anybody to born with different probability in any month maybe the probability to have two equal born days would change.

[sje]

With the 51+ million perft(7) results so far, the observed range falls in the 0..3*10^11 interval. Of course, unlike birthdays the distribution is not uniform; a non-uniform distribution will only increase the probability of a match.

The position pair I selected has the maximum matched perft(7) value seen so far.

I've tossed the intermediate data files, but I seem to remember that the odds against a match of any randomly selected position were about 3,000 to one. I'd guess that of the matches seen so far, perhaps about six of them were actually triplets, not pairs.

Positions with a perft(7) of zero (checkmates) were not included in the results.

[stegemma]

With the 51+ million perft(7) results so far, the observed range falls in the 0..3*10^11 interval. Of course, unlike birthdays the distribution is not uniform; a non-uniform distribution will only increase the probability of a match.

The position pair I selected has the maximum matched perft(7) value seen so far.

I've tossed the intermediate data files, but I seem to remember that the odds against a match of any randomly selected position were about 3,000 to one. I'd guess that of the matches seen so far, perhaps about six of them were actually triplets, not pairs.

Positions with a perft(7) of zero (checkmates) were not included in the results.

Because positions start from a common root, they could share the same perft in greater number of cases than expected. Your work is very interesting (and maybe somehow annoying for some people) but I know how do you can do it... you're not using fast computers, you are simply coming back from the future

[vittyvirus]

Hi,
First of all, thanks for your extremely interesting work!
Why don't you try also counting the number of promotions, ep captures, etc. in your perft program and perhaps then create a test suite on that?
And why is Symbolic private?

[sje]

Why don't you try also counting the number of promotions, ep captures, etc. in your perft program and perhaps then create a test suite on that?
And why is Symbolic private?

1) Adding more statistics gathering would slow down the progress on the main goal.
2) Symbolic is private only for as long as I'm alive.

[sje]

Because positions start from a common root, they could share the same perft in greater number of cases than expected.

If one were to pack 51 million people into a room, how many would share their birthmillisecond with another? With about 32 billion milliseconds in a year, that question is closely related to the current state of the Perft(14) project.

[stegemma]

Because positions start from a common root, they could share the same perft in greater number of cases than expected.

If one were to pack 51 million people into a room, how many would share their birthmillisecond with another? With about 32 billion milliseconds in a year, that question is closely related to the current state of the Perft(14) project.

Yes but if we put in that room 51 million of twins...

[sje]

Yes but if we put in that room 51 million of twins...

Perhaps if the production facility's frequency was higher than 1 KHz. Having seen the action in real time, I'd suggest that the cycle rate was at least 10^5 times slower.

[Robert Pope]

Because positions start from a common root, they could share the same perft in greater number of cases than expected.

If one were to pack 51 million people into a room, how many would share their birthmillisecond with another? With about 32 billion milliseconds in a year, that question is closely related to the current state of the Perft(14) project.

Yes but if we put in that room 51 million of twins...

Unless you are packing it full of siamese twins, that actually decreases the odds!