25,161
edits
Changes
no edit summary
'''Perft''', ('''perf'''ormance '''t'''est, move path enumeration)<br/>
a [[Debugging|debugging ]] function to walk the move generation tree of strictly [[Legal Move|legal moves]] to count all the [[Leaf Node|leaf nodes]] of a certain [[Depth|depth]], which can be compared to [[Perft Results|predetermined values]] and used to isolate [[Engine Testing#bugs|bugs]]. In perft, nodes are only counted at the end after the last [[Make Move|makemove]]. Thus "higher" [[Terminal Node|terminal nodes]] (e.g. mate or stalemate) are not counted, instead the number of move paths of a certain depth. Perft ignores draws by [[Repetitions|repetition]], by the [[Fifty-move Rule|fifty-move rule]] and by [[Material#InsufficientMaterial|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=
==Hashing==
Perft can receive another speed boost by [[Hash Table|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.
=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.
<span id="History"></span>
In '''August 2017''', [[Ankan Banerjee]], who already confirmed Peter Österlund's perft('''14''') in September 2016 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=61119&start=30 Re: yet another attempt on Perft(14)] by [[Ankan Banerjee]], [[CCC]], September 09, 2016</ref>, computed perft('''15''') of 2,015,099,950,053,364,471,960 with his [[GPU]] perft program <ref>[https://github.com/ankan-ban/perft_gpu ankan-ban/perft_gpu · GitHub]</ref>, running it several days two times with different [[Zobrist Hashing|zobrist keys]] on a cluster of [https://en.wikipedia.org/wiki/Nvidia_DGX-1 Nvidia DGX-1] server systems <ref>[https://www.nvidia.com/en-us/data-center/dgx-1/ DGX-1 for AI Research | NVIDIA]</ref>. His program starts exploring the tree in [[Depth-First|depth first]] manner on CPU. When a certain depth is reached a GPU function (kernel) is launched to compute perft of the subtree in [[Best-First|breadth first]] manner <ref>[http://www.talkchess.com/forum/viewtopic.php?t=64983&start=9 Re: Perft(15): comparison of estimates with Ankan's result] by [[Ankan Banerjee]], [[CCC]], August 26, 2017</ref>. 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) <ref>[http://www.talkchess.com/forum/viewtopic.php?t=64983&start=4 Re: perft(15)] by [[Ankan Banerjee]], [[CCC]], August 25, 2017</ref>.
<span id="Divide"></span>
=Results=
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73558 Count the number of nodes of perft(14) and beyond] by [[Marc-Philippe Huget]], [[CCC]], April 04, 2020
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73625 magic bitboard perft] by [[Richard Delorme]], [[CCC]], April 11, 2020 » [[Magic Bitboards]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73577 Perft speed optimization] by [[Marcel Vanthoor]], [[CCC]], April 06, 2020
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73812 Request for InDoubleCheck PERFTS EPDs] by [[Chris Whittington]], [[CCC]], May 02, 2020 » [[Double Check]]
=External Links=
