Perft, (performance test, move path enumeration)
a debugging function to walk the move generation tree of strictly legal moves to count all the leaf nodes of a certain depth, which can be compared to predetermined values and used to isolate bugs. In perft, nodes are only counted at the end after the last makemove. Thus "higher" terminal nodes (e.g. mate or stalemate) are not counted, instead the number of move paths of a certain depth. Perft ignores draws by repetition, by the fifty-move rule and by insufficient material. By recording the amount of time taken for each iteration, it's possible to compare the performance of different move generators or the same generator on different machines, though this must be done with caution since there are variations to perft.

Instead of counting nodes at "depth 0", legal move generators can take advantage of the fact that the number of moves generated at "depth 1" represents the accurate perft value for that branch. Therefore they can skip the last makemove/undomove, which gives much faster results and is a better indicator of the raw move generator speed (versus move generator + make/unmake). However, this can cause some confusion when comparing perft values. Assuming the above code used a legal move generator, it would only need the following modification:

Perft can receive another speed boost by hashing node counts, with a small chance for inaccurate results. Sometimes this is used as a sanity check to make sure the hash table and keys are working correctly.

Perft function with pseudo move generator

To generate legal moves some programs have to make moves first, call the function IsIncheck and then undo those moves. That makes above Perft function to make and undo moves twice for all moves. Bellow code can avoid that problem and run much faster:

Supposably, perft was first implemented within the Cobol program RSCE-1 by R.C. Smith, submitted to the USCF for evaluation, and subject of an 1978Computerworld article ^{[1]} . RSCE-1's purpose was not to play chess games, but position analysis, to find forced mates, and to perform a move path enumeration of up to three plies, with the perft(3) result of 8,902 from the initial position already mentioned ^{[2]} . Ken Thompson may have calculated perft(3) and perft(4) earlier than this date with Belle. Steven Edwards was the first to compute perft(5) through perft(9), and has since been actively involved in Perft computations.

In December 2003, Albert Bertilsson started a distributed project ^{[3]} to calculate perft(11) of the initial position, taking over a week to calculate ^{[4]} . Exact Perft numbers have been computed and verified up to a depth of 13 by Edwards and are now available in the On-Line Encyclopedia of Integer Sequences^{[5]} , and are given under Initial Position Summary. A so far unverified claim for perft(14) of 61,885,021,521,585,529,237 was given by Peter Österlund in April 2013^{[6]}, while Daniel Shawul proposed Perft estimation applying Monte carlo methods^{[7]}^{[8]}.
In August 2017, Ankan Banerjee, who already confirmed Peter Österlund's perft(14) in September 2016 ^{[9]}, computed perft(15) of 2,015,099,950,053,364,471,960 with his GPU perft program ^{[10]}, running it several days two times with different zobrist keys on a cluster of Nvidia DGX-1 server systems ^{[11]}. His program starts exploring the tree in depth first manner on CPU. When a certain depth is reached a GPU function (kernel) is launched to compute perft of the subtree in breadth first manner ^{[12]}. Ankan Banerjee dedicated his computations in honor to Steven Edwards - whose tireless efforts for verifying perft(14) encouraged him to verify perft(14) and take up the challenge to compute perft(15) ^{[13]}.

Divide

The Divide command is often implemented as a variation of perft, listing all moves and for each move, the perft of the decremented depth. However, some programs already give "divided" output for perft.

## Table of Contents

Home * Board Representation * Move Generation * PerftPerft, (performancetest, move path enumeration)a debugging function to walk the move generation tree of strictly legal moves to count all the leaf nodes of a certain depth, which can be compared to predetermined values and used to isolate bugs. In perft, nodes are only counted at the end after the last makemove. Thus "higher" terminal nodes (e.g. mate or stalemate) are not counted, instead the number of move paths of a certain depth. Perft ignores draws by repetition, by the fifty-move rule and by insufficient material. By recording the amount of time taken for each iteration, it's possible to compare the performance of different move generators or the same generator on different machines, though this must be done with caution since there are variations to perft.

## Perft function

A simple perft function in C looks as follows:## Bulk-counting

Instead of counting nodes at "depth 0", legal move generators can take advantage of the fact that the number of moves generated at "depth 1" represents the accurate perft value for that branch. Therefore they can skip the last makemove/undomove, which gives much faster results and is a better indicator of the raw move generator speed (versus move generator + make/unmake). However, this can cause some confusion when comparing perft values. Assuming the above code used a legal move generator, it would only need the following modification:## Hashing

Perft can receive another speed boost by hashing node counts, with a small chance for inaccurate results. Sometimes this is used as a sanity check to make sure the hash table and keys are working correctly.## Perft function with pseudo move generator

To generate legal moves some programs have to make moves first, call the function IsIncheck and then undo those moves. That makes above Perft function to make and undo moves twice for all moves. Bellow code can avoid that problem and run much faster:## Perft History

Supposably, perft was first implemented within the Cobol program RSCE-1 by R.C. Smith, submitted to the USCF for evaluation, and subject of an 1978 Computerworld article^{[1]}. RSCE-1's purpose was not to play chess games, but position analysis, to find forced mates, and to perform a move path enumeration of up to three plies, with the perft(3) result of 8,902 from the initial position already mentioned^{[2]}. Ken Thompson may have calculated perft(3) and perft(4) earlier than this date with Belle. Steven Edwards was the first to compute perft(5) through perft(9), and has since been actively involved in Perft computations.In

December 2003, Albert Bertilsson started a distributed project^{[3]}to calculate perft(11) of the initial position, taking over a week to calculate^{[4]}. Exact Perft numbers have been computed and verified up to a depth of 13 by Edwards and are now available in the On-Line Encyclopedia of Integer Sequences^{[5]}, and are given under Initial Position Summary. A so far unverified claim for perft(14) of 61,885,021,521,585,529,237 was given by Peter Österlund inApril 2013^{[6]}, while Daniel Shawul proposed Perft estimation applying Monte carlo methods^{[7]}^{[8]}.In

August 2017, Ankan Banerjee, who already confirmed Peter Österlund's perft(14) in September 2016^{[9]}, computed perft(15) of 2,015,099,950,053,364,471,960 with his GPU perft program^{[10]}, running it several days two times with different zobrist keys on a cluster of Nvidia DGX-1 server systems^{[11]}. His program starts exploring the tree in depth first manner on CPU. When a certain depth is reached a GPU function (kernel) is launched to compute perft of the subtree in breadth first manner^{[12]}. Ankan Banerjee dedicated his computations in honor to Steven Edwards - whose tireless efforts for verifying perft(14) encouraged him to verify perft(14) and take up the challenge to compute perft(15)^{[13]}.## Divide

The Divide command is often implemented as a variation of perft, listing all moves and for each move, the perft of the decremented depth. However, some programs already give "divided" output for perft.## See also

## Publications

2012).Computing Deep Perft and Divide Numbers for Checkers. ICGA Journal, Vol. 35, No. 4 » Checkers2013).Monte carlo methods for estimating game tree size. pdf^{[14]}» Monte-Carlo Tree Search## Perft in other Games

## Forum Posts

^{[15]}## 2000 ...

## 2005 ...

## 2010 ...

2011^{[16]}20122013Re: Perft(14) estimates thread by Peter Österlund, CCC, April 02, 2013 » 61,885,021,521,585,529,237

MC methods by Daniel Shawul, CCC, April 11, 2013 » Monte-Carlo Tree Search

Re: MC methods by Daniel Shawul, CCC, April 13, 2013

^{[17]}2014## 2015 ...

^{[18]}2016Re: yet another attempt on Perft(14) by Ankan Banerjee, CCC, September 09, 2016

2017Re: perft(15) by Ankan Banerjee, CCC, August 25, 2017

Re: Perft(15): comparison of estimates with Ankan's result by Ankan Banerjee, CCC, August 26, 2017

## External Links

## Implementations

^{[19]}^{[20]}## Video Tutorial

## References

2013).Monte carlo methods for estimating game tree size. pdf## What links here?

Up one level