perft

perft

Game tree size is defined as the total number of games that can be played from the initial position. This number is also equal to the number of leaf nodes in a game tree. The partial game tree size computed from any position and up to a certain depth d is informally known as perft(d). In the area of computer chess programming, perft is used to verify correct implementation of move generation and to some extent for comparing efficiency.

Introductory reference: https://chessprogramming.wikispaces.com/Perft

Some results

• perft(1) = 20

• perft(13) = 1,981,066,775,000,396,239 (approx 2*10^18)

See https://chessprogramming.wikispaces.com/Perft+Results for details.

Monte Carlo estimation

Daniel S. Abdi 2013, Monte carlo methods for estimating game tree size. (Wish there was a table of actual peft vs. MC estimate for chess.)

In 2013, Peter Österlund, who is the lead developer on the Droidfish app, gave a good estimate for perft(15):

mean  : 2.0150985437710440e+21
stddev: 0.0000017422002093e+21

This corresponds to approximately 1.34e12 random walks.

For an estimator, that's still a lot of computing!

Functional model

What is the best statistical fit between the exponent n (e.g. 21) and depth d (e.g. 15) to obtain a rough expression for perft(d)?

def perft( d, b=1.482020089256456, c=-0.95940122737613365 ):
    '''Chess perft(d) given depth d and estimated regression parameters.'''
    return 10**((b*d) + c)

This Python function gives excellent results: see https://git.io/perft for details. It predicts the following, given depth d:

16 5.66135255176e+22
17 1.71767221265e+24
18 5.21147164591e+25
19 1.58117692748e+27
20 4.79734064746e+28
21 1.45552827693e+30
22 4.41611868038e+31
23 1.33986433025e+33
24 4.06519061962e+34
25 1.23339165025e+36
26 3.74214915177e+37
27 1.13537985045e+39
28 3.44477826119e+40
29 1.04515658473e+42
30 3.17103802855e+43

---

Revision date : 2017-08-27