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
Perft(15)
Moderators: hgm, Rebel, chrisw
-
- Posts: 1971
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
Re: Perft(15).
Hello Steven:
Regards from Spain.
Ajedrecista.
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.sje wrote: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).
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!sje wrote: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
Regards from Spain.
Ajedrecista.
-
- Posts: 91
- Joined: Wed Mar 26, 2014 4:29 pm
- Location: Buettelborn/Hessen/Germany
Re: Perft(15).
some estimations at: http://www.10x8.net/chess/P14.html
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Beyond perft(15)
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.
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.
-
- Posts: 6442
- Joined: Tue Jan 09, 2007 12:31 am
- Location: PA USA
- Full name: Louis Zulli
Re: Beyond perft(15)
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.sje wrote: 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.
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."
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Beyond perft(15)
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.
We will just have to wait fifteen or more years to see how helpful perft(15) and beyond will be.
-
- Posts: 589
- Joined: Tue Jun 04, 2013 10:15 pm
Re: Perft(15)
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 wrote: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.
[Account deleted]
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Perft(15)
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.mvk wrote: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 wrote: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.
-
- Posts: 1971
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
Re: Perft(15).
Hello Steven:
KBNK
And I wrote a possible solution/hack in that thread (get help from MonteCarlo perft).
Regards from Spain.
Ajedrecista.
I guess you are referring about things like the following one:sje wrote: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.
KBNK
And I wrote a possible solution/hack in that thread (get help from MonteCarlo perft).
Regards from Spain.
Ajedrecista.