Perft(15)

[sje]

Perft(15)

Looking ahead, what might be the best way of calculating perft(15)?

My first order estimate of perft(15) is 2*10^21 (about 2^71). Sixty-four bit integers will be too small for the upper level summations, so the software has be able to handle 128 bit sums. This includes having sixteen byte integers in each transposition table entry instead of eight byte integers. Each entry will have a sixteen byte hash as is used in the current software. The total entry length is therefore 32 bytes; each GiB of table storage will have 2^25 entries.

My experience with moving from eight byte hashes to sixteen byte hashes says that the same increase in the subtotal integer size will increase the running time by less than five percent.

The Perft(14) project calculates the perft(7) subtree total for each of the unique(7) (96,400,068) positions. The positions are divided into 964 work units of 100,000 positions each and one work unit with 68 positions. For Perft(15), the same work units could be used with a perft(8) subtree total calculated for each position. Alternatively, the unique(8) set of 988,187,354 positions could be generated with a perft(7) subtree total calculated for each. Other partitions are also possible.

My preference is to use the existing set of unique(7) work units; they have been well-tested and have been used to successfully calculate perft(7), perft(8), perft(9), and perft(10).

----

Summary of the unique(7) work unit set:

Record count = 96,400,068
Average record length = 67.19 bytes

Total length = 6,477,465,673 bytes
Average work unit length = 6,712,400 bytes

Total compressed length = 511,593,969 bytes
Average work unit compressed length = 530,149 bytes

[Ajedrecista]

Hello Steven:

Perft(15)

Looking ahead, what might be the best way of calculating perft(15)?

My first order estimate of perft(15) is 2*10^21 (about 2^71).

Here is a thread about estimates of Perft(15). Peter Österlund gave a very plausible estimate of circa 2.0151e+21; my estimate was very similar.

Sixty-four bit integers will be too small for the upper level summations, so the software has be able to handle 128 bit sums. This includes having sixteen byte integers in each transposition table entry instead of eight byte integers. Each entry will have a sixteen byte hash as is used in the current software. The total entry length is therefore 32 bytes; each GiB of table storage will have 2^25 entries.

My experience with moving from eight byte hashes to sixteen byte hashes says that the same increase in the subtotal integer size will increase the running time by less than five percent.

The Perft(14) project calculates the perft(7) subtree total for each of the unique(7) (96,400,068) positions. The positions are divided into 964 work units of 100,000 positions each and one work unit with 68 positions. For Perft(15), the same work units could be used with a perft(8) subtree total calculated for each position. Alternatively, the unique(8) set of 988,187,354 positions could be generated with a perft(7) subtree total calculated for each. Other partitions are also possible.

My preference is to use the existing set of unique(7) work units; they have been well-tested and have been used to successfully calculate perft(7), perft(8), perft(9), and perft(10).

----

Summary of the unique(7) work unit set:

Record count = 96,400,068
Average record length = 67.19 bytes

Total length = 6,477,465,673 bytes
Average work unit length = 6,712,400 bytes

Total compressed length = 511,593,969 bytes
Average work unit compressed length = 530,149 bytes

Perft(8) from unique(7) sounds reasonable, but the priority is to finish Perft(14) calculation. It seems like Perft(15) would need a serious distributed project. Good luck!

Regards from Spain.

Ajedrecista.

[SMIRF]

some estimations at: http://www.10x8.net/chess/P14.html

[sje]

Thinking beyond perft(15), it may be useful to introduce a more formal, automated way of distributing work units and collecting results. Because of the volume of data and the ancillary needs of administration, it might be a good idea to move to a client/server model which employs well-proven database tools. I had thought about doing this with perft(14) and I might yet make that transition.

Using 128 bit signatures and expanding the current 64 bit sums to 128 bits, we should be able to achieve perft(20) with confidence, if not with speed. But what may take months or years now might only take a single overnight run by a chess program 15 or 20 years from now. Just maybe the programmers of that day and the days thereafter will look back with gratitude to those who first generated the numbers used for validation of their programs.

[zullil]

Just maybe the programmers of that day and the days thereafter will look back with gratitude to those who first generated the numbers used for validation of their programs.

Probably not. And not because chess programmers are not a grateful bunch (well, mostly). Just can't imagine one would need perft(15) for validation during engine development. But then, maybe my imagination is limited.

I actually liked your earlier response better, when I asked why on earth you were doing this mechanical calculation. It was something like "why do people climb mountains."

[sje]

When I started, only the first three or four perft() values were known; had there been more, I would have been helped a lot.

We will just have to wait fifteen or more years to see how helpful perft(15) and beyond will be.

[mvk]

My first order estimate of perft(15) is 2*10^21 (about 2^71). Sixty-four bit integers will be too small for the upper level summations, so the software has be able to handle 128 bit sums. This includes having sixteen byte integers in each transposition table entry instead of eight byte integers.

Is this still true if you start the searches 7 or 8 ply from the root, as you do now? What is the highest sub-result you have found so far? In other words, why does the inner tree need to reserve space for overflows that only occur in the upper levels?

[sje]

My first order estimate of perft(15) is 2*10^21 (about 2^71). Sixty-four bit integers will be too small for the upper level summations, so the software has be able to handle 128 bit sums. This includes having sixteen byte integers in each transposition table entry instead of eight byte integers.

Is this still true if you start the searches 7 or 8 ply from the root, as you do now? What is the highest sub-result you have found so far? In other words, why does the inner tree need to reserve space for overflows that only occur in the upper levels?

The successor phases to the current work unit phase will require a 128 bit partial sum transposition entry component. Also, I'm interested in doing deep perft() calculations for positions starting with only a few men, and these can overflow 64 bit sums in a matter of seconds.

[Ajedrecista]

Hello Steven:

The successor phases to the current work unit phase will require a 128 bit partial sum transposition entry component. Also, I'm interested in doing deep perft() calculations for positions starting with only a few men, and these can overflow 64 bit sums in a matter of seconds.

I guess you are referring about things like the following one:

KBNK

And I wrote a possible solution/hack in that thread (get help from MonteCarlo perft).

Regards from Spain.

Ajedrecista.