unique positions for depth 9

[Sapling]

In preparation for TGCT depth 14 perft (with full stats) I've just generated a 340GB bin file containing the number of times each unique position occurs at depth 9.

Each element in the file contains:
[order] 8 bytes
[occurrences] 4 bytes
[board state] 26 bytes

I've 'verified' my file is correct by summing the number of occurrences for each unique position, which gives the correct result: 2,439,530,234,167 (the number of nodes for depth 9 perft )

The problem though, is that the file only contains 9,183,421,877 unique positions, and I've seen that both Paul Byrne and François Labelle have confirmed there to be 9,183,421,888 unique positions at depth 9 (only 11 more?!)
https://www.stmintz.com/ccc/index.php?id=344822
https://wismuth.com/chess/statistics-positions.html

I cannot understand how this could be, since it indicates that I've some how managed to find the exact number of nodes reachable, using a different set of positions, which seems very unlikely.

The only thing that is curious is that I've found there to be 10 double discovered checks possible at depth 9 where there were 0 at depth 8 https://grandchesstree.com/perft/0/results maybe this scenario could cause the discrepancy.

Additionally my algorithm matches both of the above perfectly up until depth 9. At depth 9 and beyond the approach is quite different since you'd need an insane amount of ram to calculate the unique positions in memory, instead you must do it in smaller batches then merge sort, which does introduce some additional complexity and potential for bugs outside of your core search routine.

I'm wondering if anyone else has been able to confirm these results? Or has the ability to? Or if anyone has a different program to mine that could calculate the number of unique positions up to depth 9 in memory that I could run on my system to confirm my results?

[Ajedrecista]

Hello Tim:

I can not answer your question, sadly. I see that the On-line Encyclopedia of Integer Sequences has registered the figure ending in 88:

https://oeis.org/A083276

I only know JetChess perft counter for counting unique positions, but it has a limit of 2^32 (1 GB of hash and 32 steps), this is below Positions(9).

I also tried TGCT standalone engine, only to get BMI2 exceptions. I guess that TGCT-win-64 needs BMI2 instructions, which I do not have in my almost Stone Age computer from 2010. Anyway, your efforts are much appreciated.

Good luck hunting the bugs (if any)!

Regards from Spain.

Ajedrecista.

[lithander]

maybe you had 11 hash collisions when counting unique positions and just comparing them by hash?

[Sapling]

Thanks @Ajedrecista, yes it needs BMI2 instructions, though I will be releasing a version that uses magic numbers instead of PEXT for the sliding piece attacks, which should work on your system.

maybe you had 11 hash collisions when counting unique positions and just comparing them by hash?

I think you are probably correct @lithander, still seems like a crazy coincidence that the total node count ended up the same. I'll try again tonight using a different set of hash keys, I'm also going to rent a VPS with >128GB of ram to try running in memory with a huge hash table, which should rule out issues writing to disk / the streaming merge sort when piecing the batches together.

[lithander]

if it's hash collision then just different keys won't do unless you combine them. (128bit instead of 64bit)

[petero2]

In preparation for TGCT depth 14 perft (with full stats) I've just generated a 340GB bin file containing the number of times each unique position occurs at depth 9.

...

I'm wondering if anyone else has been able to confirm these results? Or has the ability to? Or if anyone has a different program to mine that could calculate the number of unique positions up to depth 9 in memory that I could run on my system to confirm my results?

There is another verification here: https://www.talkchess.com/forum/viewtop ... 45&t=41032

My program requires Linux though. Does your program run in Linux?

My uncompressed depth 9 file is 411 GB so it would be inconvenient to transfer it to another computer. I suppose one way to determine a difference between our results would be to agree on a sort order for the positions, then use binary search to find an index in the sorted order of positions where there is a disagreement.

[petero2]

Hi Tim, I tried to send you an email containing the source code for my program that computes unique positions, but got an error saying that the attachment was not allowed by your organization.

[Sapling]

Thank you Peter! I'll message you on discord with another email address to try