Perft(n) as a benchmark

[sje]

Perft(n) as a benchmark

Back in the early days of personal computers in the mid 1970s there were a few informal benchmarks in use in the enthusiast community. Perhaps the very first one was the Sieve of Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes run to 8191 (2^13 - 1), which was soon followed by the Eight Queens Problem http://en.wikipedia.org/wiki/Eight_queens_puzzle. Both were quite challenging for the early eight bit machines. Since the same program source was not always used, the benchmarking process also measured the skills of the programming and also the efficiency of the programming language implementation.

Back in the late 1980s (1987, perhaps) I ran perft(7) on a 16 MHz Motorola 68020 system and got the correct answer of 3,195,901,860 after about 36 hours of CPU time. I believe I was the first to calculate perft(7), or at least to publish it. The program was written in C and used bitboards but did not use transposition table assistance. Calculating perft(7) on my 2006 Mac Pro takes just over three seconds not counting time used for initialization and termination of the transposition tables.

Today we have perft(n) runs which take from weeks to months to complete. However, as perft(n) is highly tractable to parallelization, we can expect much shorter elapsed times as more expansive multi-CPU, multi-core hardware becomes available even without much in the way of chip level technological advances.

Who will be the first to calculate perft(14)? Already we have computing systems which could produce the sum in under a day. An amateur-run distributed computing network might get an answer within an hour. In twenty five years we have seen the perft(7) calculation time shortened by a factor of about 40,000 although a good part of this was due to algorithmic improvements.

[Ajedrecista]

Hello Steven:

Perft(n) as a benchmark

Back in the early days of personal computers in the mid 1970s there were a few informal benchmarks in use in the enthusiast community. Perhaps the very first one was the Sieve of Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes run to 8191 (2^13 - 1), which was soon followed by the Eight Queens Problem http://en.wikipedia.org/wiki/Eight_queens_puzzle. Both were quite challenging for the early eight bit machines. Since the same program source was not always used, the benchmarking process also measured the skills of the programming and also the efficiency of the programming language implementation.

Back in the late 1980s (1987, perhaps) I ran perft(7) on a 16 MHz Motorola 68020 system and got the correct answer of 3,195,901,860 after about 36 hours of CPU time. I believe I was the first to calculate perft(7), or at least to publish it. The program was written in C and used bitboards but did not use transposition table assistance. Calculating perft(7) on my 2006 Mac Pro takes just over three seconds not counting time used for initialization and termination of the transposition tables.

Today we have perft(n) runs which take from weeks to months to complete. However, as perft(n) is highly tractable to parallelization, we can expect much shorter elapsed times as more expansive multi-CPU, multi-core hardware becomes available even without much in the way of chip level technological advances.

Who will be the first to calculate perft(14)? Already we have computing systems which could produce the sum in under a day. An amateur-run distributed computing network might get an answer within an hour. In twenty five years we have seen the perft(7) calculation time shortened by a factor of about 40,000 although a good part of this was due to algorithmic improvements.

It seems interesting although the benchmark will depend a lot in the used perft counter and the hardware, as you stated. I do not know if I am going off-topic, but I share the results I got back in January 2012, using JetChess 1.0.0.0 (single core, 32-bit) in an Intel i5-760 at 2.8 GHz:

Code: Select all

Hash = 64 MB:

Perft(1) ---> Time:    0 ms (0:00:00.000).
Perft(2) ---> Time:    0 ms (0:00:00.000).
Perft(3) ---> Time:    0 ms (0:00:00.000).
Perft(4) ---> Time:    1 ms (0:00:00.001).
Perft(5) ---> Time:   23 ms (0:00:00.023).
Perft(6) ---> Time:  320 ms (0:00:00.320).
Perft(7) ---> Time: 3.864 s (0:00:03.864).

Code: Select all

Hash = 256 MB:

Perft(8) ---> Time: 56.260 s (0:00:56.260).

Code: Select all

Hash = 1 GB:

 Perft(9) ---> Time:   764.290 s (0:12:44.290).
Perft(10) ---> Time: 10607.827 s (2:56:47.827).

Other example can be read at JetChess website.

It would be nice that some people post their results, including the perft guru Paul Byrne.

Regards from Spain.

Ajedrecista.

[sje]

Subtract nine seconds from each of the following for transposition table setup time:

Code: Select all

Depth: 8   Count: 84,998,978,956   Elapsed: 47.8063  (1.77799e+09 Hz / 5.62434e-10 s)
Depth: 9   Count: 2,439,530,234,167   Elapsed: 422.862  (5.76909e+09 Hz / 1.73337e-10 s)
Depth: 10   Count: 69,352,859,712,417   Elapsed: 5142.79  (1.34855e+10 Hz / 7.4154e-11 s)