TalkChess.com

[Steven Edwards]

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.