Perft(15)

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Perft(15)

Post by sje » Tue Feb 03, 2015 3:06 am

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

User avatar
Ajedrecista
Posts: 1418
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Perft(15).

Post by Ajedrecista » Tue Feb 03, 2015 10:32 am

Hello Steven:
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).
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: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.

User avatar
SMIRF
Posts: 91
Joined: Wed Mar 26, 2014 3:29 pm
Location: Buettelborn/Hessen/Germany
Contact:

Re: Perft(15).

Post by SMIRF » Tue Feb 03, 2015 10:38 am


User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Beyond perft(15)

Post by sje » Tue Feb 10, 2015 7:06 am

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
Posts: 6073
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

Re: Beyond perft(15)

Post by zullil » Tue Feb 10, 2015 10:18 am

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.
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." :D

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Beyond perft(15)

Post by sje » Thu Feb 12, 2015 2:51 am

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
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: Perft(15)

Post by mvk » Sat Feb 14, 2015 12:06 pm

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.
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?
[Account deleted]

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Perft(15)

Post by sje » Sat Feb 14, 2015 8:19 pm

mvk wrote:
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.
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.

User avatar
Ajedrecista
Posts: 1418
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Perft(15).

Post by Ajedrecista » Sun Feb 15, 2015 11:06 am

Hello Steven:
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.
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.

Post Reply