25,161
edits
Changes
Created page with "'''Home * Board Representation * Move Generation * Perft''' '''Perft''', ('''perf'''ormance '''t'''est, move path enumeration)<br/> a debugging function..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Move Generation]] * Perft'''
'''Perft''', ('''perf'''ormance '''t'''est, move path enumeration)<br/>
a 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=
A simple perft function in [[C]] looks as follows:
<pre>
typedef unsigned long long u64;
u64 Perft(int depth)
{
MOVE move_list[256];
int n_moves, i;
u64 nodes = 0;
if (depth == 0) return 1;
n_moves = GenerateLegalMoves(move_list);
for (i = 0; i < n_moves; i++) {
MakeMove(move_list[i]);
nodes += Perft(depth - 1);
UndoMove(move_list[i]);
}
return nodes;
}
</pre>
<span id="Bulk"></span>
=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 [[Make Move|makemove]]/[[Unmake Move|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:
<pre>
...
//__/* DELETE: if (depth == 0) return 1; */__//
n_moves = GenerateMoves(move_list);
__if (depth == 1) return n_moves;__
...
</pre>
=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.
=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:
<pre>
typedef unsigned long long u64;
u64 Perft(int depth)
{
MOVE move_list[256];
int n_moves, i;
u64 nodes = 0;
if (depth == 0) return 1;
n_moves = GenerateMoves(move_list);
for (i = 0; i < n_moves; i++) {
MakeMove(move_list[i]);
if (!IsIncheck())
nodes += Perft(depth - 1);
UndoMove(move_list[i]);
}
return nodes;
}
</pre>
<span id="History"></span>
=Perft History=
Supposably, perft was first implemented within the [[Cobol]] program [[RSCE-1]] by [[Rolf C. Smith#RCSmith|R.C. Smith]], submitted to the [https://en.wikipedia.org/wiki/United_States_Chess_Federation USCF] for evaluation, and subject of an [[Timeline#1978|1978]] [[Computerworld]] article <ref>[http://news.google.com/newspapers?nid=849&dat=19780417&id=h8lOAAAAIBAJ&sjid=DEoDAAAAIBAJ&pg=6180,1080528 Written in Cobol - Program Written as Chess Buff's Research Aid] by Brad Schultz, [[Computerworld]], April 17, 1978, Page 37</ref> . RSCE-1's purpose was not to play chess games, but position analysis, to find forced [[Checkmate|mates]], and to perform a move path enumeration of up to three [[Ply|plies]], with the [[Perft Results|perft(3) result]] of 8,902 from the [[Initial Position|initial position]] already mentioned <ref>[http://www.talkchess.com/forum/viewtopic.php?t=41373 Perft(3) from 1978, with a twist!] by [[Steven Edwards]], [[CCC]], December 08, 2011</ref> . [[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 <ref>[https://www.stmintz.com/ccc/index.php?id=335026 Distributed perft project] by [[Albert Bertilsson]], [[CCC]], December 09, 2003</ref> to calculate perft(11) of the [[Initial Position|initial position]], taking over a week to calculate <ref>[https://web.archive.org/web/20061014115710/http://www.albert.nu/programs/dperft/ Distributed Perft Project] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])</ref> . Exact Perft numbers have been computed and verified up to a depth of 13 by Edwards and are now available in the [https://en.wikipedia.org/wiki/On-Line_Encyclopedia_of_Integer_Sequences On-Line Encyclopedia of Integer Sequences] <ref>[http://oeis.org/A048987 A048987] from [https://en.wikipedia.org/wiki/On-Line_Encyclopedia_of_Integer_Sequences On-Line Encyclopedia of Integer Sequences] (OEIS)</ref> , 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''' <ref>[http://talkchess.com/forum/viewtopic.php?topic_view=threads&p=513308&t=47335 Re: Perft(14) estimates thread] by [[Peter Österlund]], [[CCC]], April 02, 2013</ref>, while [[Daniel Shawul]] proposed Perft estimation applying [[Monte-Carlo Tree Search|Monte carlo methods]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47740&start=2 MC methods] by [[Daniel Shawul]], [[CCC]], April 11, 2013</ref> <ref>[[Daniel Shawul|Daniel S. Abdi]] ('''2013'''). ''Monte carlo methods for estimating game tree size''. [https://dl.dropboxusercontent.com/u/55295461/perft/perft.pdf pdf]</ref>.
<span id="15"></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>
=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=
* [[Perft Results]]
=Publications=
* [[Aart Bik]] ('''2012'''). ''Computing Deep Perft and Divide Numbers for Checkers''. [[ICGA Journal#35_4|ICGA Journal, Vol. 35, No. 4]] » [[Checkers]]
* [[Daniel Shawul|Daniel S. Abdi]] ('''2013'''). ''Monte carlo methods for estimating game tree size''. [https://dl.dropboxusercontent.com/u/55295461/perft/perft.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47740&topic_view=flat&start=11 Re: MC methods] by [[Daniel Shawul]], [[CCC]], April 13, 2013</ref> » [[Monte-Carlo Tree Search]]
=Perft in other Games=
* [http://tonyjh.com/chess/technical/ Perft for other forms of Chess] by [[Tony Hecker]]
* [http://checker-board.blogspot.com/2009/02/perft-for-checkers.html Perft for Checkers] by [[Martin Fierz]]
* [http://www.aartbik.com/MISC/reversi.html Perft for Reversi/Othello] by [[Aart Bik]]
=Forum Posts=
<ref>[https://www.stmintz.com/ccc/index.php?terms=perft&search=1 Perft], search the [[CCC|CCC Archives]]</ref>
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=107258 Testing speed of "position visiting"] by [[Tom Kerrigan]], [[CCC]], April 23, 2000
* [https://www.stmintz.com/ccc/index.php?id=198498 Who is the champion in calculating perft?] by [[Uri Blass]], [[CCC]], November 22, 2001
* [https://www.stmintz.com/ccc/index.php?id=234025 Perft 5,6 {Fastest program is List}] by [[Dann Corbit]], [[CCC]], June 04, 2002 » [[List (Program)|List]]
* [https://www.stmintz.com/ccc/index.php?id=275133 Perft revisited] by [[Normand M. Blais]], [[CCC]], January 05, 2003
* [https://www.stmintz.com/ccc/index.php?id=326134 Highest perft for initial position?] by [[Albert Bertilsson]], [[CCC]], November 07, 2003
* [https://www.stmintz.com/ccc/index.php?id=335026 Distributed perft project] by [[Albert Bertilsson]], [[CCC]], December 09, 2003
* [https://www.stmintz.com/ccc/index.php?id=334499 Perft(10) verified] by [[Albert Bertilsson]], [[CCC]], December 09, 2003
* [https://www.stmintz.com/ccc/index.php?id=335527 Distributed perft, current standings and trends] by [[Albert Bertilsson]], [[CCC]], December 12, 2003
* [https://www.stmintz.com/ccc/index.php?id=336985 Hashing in distributed perft] by [[Steffen A. Jakob|Steffen Jakob]], [[CCC]], December 19, 2003
* [https://www.stmintz.com/ccc/index.php?id=388806 perft results (how accurate is accurate enough ?)] by [[Roman Hartmann]], [[CCC]], September 23, 2004
* [https://www.stmintz.com/ccc/index.php?id=394229 FRC Perft] by Jürgen Suntinger, [[CCC]], November 02, 2004
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=1377 perft question] by [[Sven Schüle]], [[Computer Chess Forums|Winboard Forum]], January 19, 2005
* [https://www.stmintz.com/ccc/index.php?id=466491 Perft vs Search Re: Cache size does matter] by [[Brian Richardson]], [[CCC]], December 03, 2005
* [https://www.stmintz.com/ccc/index.php?id=488816 Perft -- Test position and data] by [[Charles Roberson]], [[CCC]], February 23, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=20834 A perft faster than qperft?!] by [[Allard Siemelink]], [[CCC]], April 24, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=23634 Perft problems...] by [[Chris Tatham]], [[CCC]], September 10, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=27334 What is perft(x) exactly meaning?] by [[Jouni Uski]], [[CCC]], April 06, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=29425 Perft and mate] by [[Stefano Gemma]], [[CCC]], August 16, 2009 » [[Freccia]]
* [http://www.talkchess.com/forum/viewtopic.php?t=30754 Perft and insufficient material] by [[Sven Schüle]], [[CCC]], November 23, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=34025 Does perft include underpromotion?] by [[Rasjid Chan|Chan Rasjid]], [[CCC]], April 27, 2010
'''2011'''
* [http://www.talkchess.com/forum/viewtopic.php?t=38235 Perft 12 in progress] by [[Steven Edwards]], [[CCC]], February 27, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38862 Perft(12) count confirmed] by [[Steven Edwards]], [[CCC]], April 25, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=39678 Perft(13) betting pool] by [[Steven Edwards]], [[CCC]], July 10, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=40108 Fastest perft] by ethan ara, [[CCC]], August 19, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=41373 Perft(3) from 1978, with a twist!] by [[Steven Edwards]], [[CCC]], December 08, 2011 <ref>[http://news.google.com/newspapers?nid=849&dat=19780417&id=h8lOAAAAIBAJ&sjid=DEoDAAAAIBAJ&pg=6180,1080528 Written in Cobol - Program Written as Chess Buff's Research Aid] by Brad Schultz, [[Computerworld]], April 17, 1978, Page 37</ref>
'''2012'''
* [http://www.talkchess.com/forum/viewtopic.php?t=42512 estimating the number of possible stalemates in perft(n)] by [[Uri Blass]], [[CCC]], February 18, 2012 » [[Stalemate]]
* [http://www.talkchess.com/forum/viewtopic.php?t=42600 Shatranj perfts] by [[Paul Byrne]], [[CCC]], February 24, 2012 » [[Shatranj]]
* [http://www.talkchess.com/forum/viewtopic.php?t=45099 Perft and en_passant] by [[Harald Lüßen]], [[CCC]], September 11, 2012 » [[En passant]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46004 about perft, what is the proper way of doing it?] by Fred Piche, [[CCC]], November 14, 2012
'''2013'''
* [http://www.talkchess.com/forum/viewtopic.php?t=47318 A few positions to test movegen] by [[Martin Sedlak]], [[CCC]], February 24, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47335 Perft(14) estimates thread] by [[Steven Edwards]], [[CCC]], February 26, 2013
: [http://talkchess.com/forum/viewtopic.php?topic_view=threads&p=513308&t=47335 Re: Perft(14) estimates thread] by [[Peter Österlund]], [[CCC]], April 02, 2013 » 61,885,021,521,585,529,237
* [http://www.talkchess.com/forum/viewtopic.php?t=47740 Perft(15) estimates thread] by [[Steven Edwards]], [[CCC]], April 10, 2013
: [http://www.talkchess.com/forum/viewtopic.php?t=47740&start=2 MC methods] by [[Daniel Shawul]], [[CCC]], April 11, 2013 » [[Monte-Carlo Tree Search]]
: [http://www.talkchess.com/forum/viewtopic.php?t=47740&topic_view=flat&start=11 Re: MC methods] by [[Daniel Shawul]], [[CCC]], April 13, 2013
* [http://www.chessprogramming.net/computerchess/is-perft-speed-important/ Is Perft Speed Important?] by [[Steve Maughan]], [http://www.chessprogramming.net/ Computer Chess Programming], April 19, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48217 Perft search speed bottleneck] by Jim Jarvis, [[CCC]], June 07, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48387 Fast perft on GPU (upto 20 Billion nps w/o hashing)] by [[Ankan Banerjee]], [[CCC]], June 22, 2013 » [[GPU]], [[Kogge-Stone Algorithm]] <ref>[https://github.com/ankan-ban/perft_gpu ankan-ban/perft_gpu · GitHub]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=48423 A perft() benchmark] by [[Steven Edwards]], [[CCC]], June 26, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48491 gperft] by [[Paul Byrne]], [[CCC]], July 01, 2013
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=52965 perft/divide bug in roce38 and Sharper? [SOLVED]] by thedrunkard, [[Computer Chess Forums|Winboard Forum]], October 16, 2013 » [[ROCE]], [[Sharper]]
'''2014'''
* [http://www.talkchess.com/forum/viewtopic.php?t=53224 Perft(14) revisited] by [[Steven Edwards]], [[CCC]], August 08, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53406 Perft(14) Weekly Status Report] by [[Steven Edwards]], [[CCC]], August 24, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53408 Non recursive perft()] by [[Steven Edwards]], [[CCC]], August 24, 2014 » [[Iterative Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53439 OpenCL perft() Technical Issues] by [[Steven Edwards]], [[CCC]], August 26, 2014 » [[OpenCL]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53743 A method guaranteed to localize the toughest perft() bugs] by [[Steven Edwards]], [[CCC]], September 18, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54528 FRC / Chess960 Engine with "Divided" Command] by [[Steve Maughan]], [[CCC]], December 02, 2014 » [[Chess960]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54719 Handling integer overflow for certain perft() calculations] by [[Steven Edwards]], [[CCC]], December 22, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54767 Perft(14) verification] by [[Steven Edwards]], [[CCC]], December 28, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=54853 Perft(14) Weekly Status Reports for 2015] by [[Steven Edwards]], [[CCC]], January 04, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55195 Perft(15)] by [[Steven Edwards]], [[CCC]], February 09, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55274 Some Chess960/FRC positions to be confirmed] by [[Reinhard Scharnagl]], [[CCC]], February 09, 2015 » [[Chess960]]
* [http://www.talkchess.com/forum/viewtopic.php?t=55896 An MPI perft program] by [[Chao Ma]], [[CCC]], April 05, 2015 » [[Parallel Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=56523 Deep split perft()] by [[Steven Edwards]], [[CCC]], May 29, 2015 » [[Thread]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2855 Please comment on my Perft speeds] by ppyvabw, [[Computer Chess Forums|OpenChess Forum]], July 10, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56998 100 easy perft(7) test positions] by [[Steven Edwards]], [[CCC]], July 17, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57417 Perft using nullmove] by [[Lasse Hansen]], [[CCC]], August 29, 2015
* [http://www.open-chess.org/viewtopic.php?f=5&t=2913 Perft and hash with legal move generator] by [[Izak Pretorius|Peterpan]], [[Computer Chess Forums|OpenChess Forum]], November 12, 2015 » [[Transposition Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=58406 Auriga - distributed and collaborative Perft] by [[Giuseppe Cannella]], [[CCC]], November 28, 2015 <ref>[http://cinnamonchess.altervista.org/auriga Auriga] by [[Giuseppe Cannella]]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=58726 Perft(14) Weekly Status Reports for 2016] by [[Steven Edwards]], [[CCC]], December 29, 2015
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=59046 Best way to debug perft?] by Meni Rosenfeld, [[CCC]], January 25, 2016 » [[Debugging]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59567 Perft, leaf nodes?] by [[Luis Babboni]], [[CCC]], March 19, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60108 reverse perft] by [[Alexandru Mosoi]], [[CCC]], May 09, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60445 Perft for Xiangqi & Shogi] by [[Patrice Duhamel]], [[CCC]], June 12, 2016 » [[Chinese Chess|Xiangqi]], [[Shogi]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61119 yet another attempt on Perft(14)] by [[Ankan Banerjee]], [[CCC]], August 13, 2016
: [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
'''2017'''
* [http://www.open-chess.org/viewtopic.php?f=5&t=3063 Perft results?] by notachessplayer, [[Computer Chess Forums|OpenChess Forum]], January 01, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64983 perft(15)] by [[Ankan Banerjee]], [[CCC]], August 25, 2017 » [[Perft#15|Perft(15)]]
: [http://www.talkchess.com/forum/viewtopic.php?t=64983&start=4 Re: perft(15)] by [[Ankan Banerjee]], [[CCC]], August 25, 2017
: [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
=External Links=
* [http://oeis.org/A048987 A048987] from [https://en.wikipedia.org/wiki/On-Line_Encyclopedia_of_Integer_Sequences On-Line Encyclopedia of Integer Sequences] (OEIS)
* [https://wismuth.com/chess/statistics-games.html Statistics on chess games] by [[Mathematician#FLabelle|François Labelle]]
* [https://en.wikipedia.org/wiki/Performance_testing Performance testing from Wikipedia]
* [https://web.archive.org/web/20061014115710/http://www.albert.nu/programs/dperft/ Distributed Perft Project] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])
==Implementations==
* [http://home.hccnet.nl/h.g.muller/dwnldpage.html µ-Max Dowload Page - qperft] by [[Harm Geert Muller]] » [[Micro-Max]]
* [https://github.com/ankan-ban/perft_gpu ankan-ban/perft_gpu · GitHub] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48387 Fast perft on GPU (upto 20 Billion nps w/o hashing)] by [[Ankan Banerjee]], [[CCC]], June 22, 2013</ref>
* [http://cinnamonchess.altervista.org/auriga Auriga] by [[Giuseppe Cannella]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=58406 Auriga - distributed and collaborative Perft] by [[Giuseppe Cannella]], [[CCC]], November 28, 2015</ref>
* [https://github.com/Mk-Chan/BBPerft BBPerft: A fast, bitboard based chess perft result generator] by [[Manik Charan]] derived from [[WyldChess]]
* [http://brausch.org/home/chess/index.html Chess Engine OliThink - New Move Generator OliPerft (Pre OliThink 5)] by [[Oliver Brausch]] » [[OliThink]]
* [http://www.craftychess.com/documentation/craftydoc.html Crafty Command Documentation] by [[Robert Hyatt]], see perft <depth> » [[Crafty]]
* [http://www.rocechess.ch/perft.html perft, divide, debugging a move generator] from [[ROCE]] by [[Roman Hartmann]]
* [http://marcelk.net/rookie/nostalgia/v3/perft-random.epd perft-random.epd] by [[Marcel van Kervinck]] » [[Rookie]]
==Video Tutorial==
* A quick overview of the perft process by [[Jonathan Warkentin]], [https://en.wikipedia.org/wiki/YouTube YouTube] Videos
: {{#evu:https://www.youtube.com/watch?v=A0HJbwRwILk|alignment=left|valignment=top}}
* An example of debugging a perft error by [[Jonathan Warkentin]], [https://en.wikipedia.org/wiki/YouTube YouTube] Videos
: {{#evu:https://www.youtube.com/watch?v=bAONObdxF54|alignment=left|valignment=top}}
* Improving the perft speed & debugging tips by [[Jonathan Warkentin]], [https://en.wikipedia.org/wiki/YouTube YouTube] Videos
: {{#evu:https://www.youtube.com/watch?v=BIzAfg5sdqg|alignment=left|valignment=top}}
=References=
<references />
'''[[Move Generation|Up one level]]'''
'''Perft''', ('''perf'''ormance '''t'''est, move path enumeration)<br/>
a 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=
A simple perft function in [[C]] looks as follows:
<pre>
typedef unsigned long long u64;
u64 Perft(int depth)
{
MOVE move_list[256];
int n_moves, i;
u64 nodes = 0;
if (depth == 0) return 1;
n_moves = GenerateLegalMoves(move_list);
for (i = 0; i < n_moves; i++) {
MakeMove(move_list[i]);
nodes += Perft(depth - 1);
UndoMove(move_list[i]);
}
return nodes;
}
</pre>
<span id="Bulk"></span>
=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 [[Make Move|makemove]]/[[Unmake Move|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:
<pre>
...
//__/* DELETE: if (depth == 0) return 1; */__//
n_moves = GenerateMoves(move_list);
__if (depth == 1) return n_moves;__
...
</pre>
=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.
=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:
<pre>
typedef unsigned long long u64;
u64 Perft(int depth)
{
MOVE move_list[256];
int n_moves, i;
u64 nodes = 0;
if (depth == 0) return 1;
n_moves = GenerateMoves(move_list);
for (i = 0; i < n_moves; i++) {
MakeMove(move_list[i]);
if (!IsIncheck())
nodes += Perft(depth - 1);
UndoMove(move_list[i]);
}
return nodes;
}
</pre>
<span id="History"></span>
=Perft History=
Supposably, perft was first implemented within the [[Cobol]] program [[RSCE-1]] by [[Rolf C. Smith#RCSmith|R.C. Smith]], submitted to the [https://en.wikipedia.org/wiki/United_States_Chess_Federation USCF] for evaluation, and subject of an [[Timeline#1978|1978]] [[Computerworld]] article <ref>[http://news.google.com/newspapers?nid=849&dat=19780417&id=h8lOAAAAIBAJ&sjid=DEoDAAAAIBAJ&pg=6180,1080528 Written in Cobol - Program Written as Chess Buff's Research Aid] by Brad Schultz, [[Computerworld]], April 17, 1978, Page 37</ref> . RSCE-1's purpose was not to play chess games, but position analysis, to find forced [[Checkmate|mates]], and to perform a move path enumeration of up to three [[Ply|plies]], with the [[Perft Results|perft(3) result]] of 8,902 from the [[Initial Position|initial position]] already mentioned <ref>[http://www.talkchess.com/forum/viewtopic.php?t=41373 Perft(3) from 1978, with a twist!] by [[Steven Edwards]], [[CCC]], December 08, 2011</ref> . [[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 <ref>[https://www.stmintz.com/ccc/index.php?id=335026 Distributed perft project] by [[Albert Bertilsson]], [[CCC]], December 09, 2003</ref> to calculate perft(11) of the [[Initial Position|initial position]], taking over a week to calculate <ref>[https://web.archive.org/web/20061014115710/http://www.albert.nu/programs/dperft/ Distributed Perft Project] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])</ref> . Exact Perft numbers have been computed and verified up to a depth of 13 by Edwards and are now available in the [https://en.wikipedia.org/wiki/On-Line_Encyclopedia_of_Integer_Sequences On-Line Encyclopedia of Integer Sequences] <ref>[http://oeis.org/A048987 A048987] from [https://en.wikipedia.org/wiki/On-Line_Encyclopedia_of_Integer_Sequences On-Line Encyclopedia of Integer Sequences] (OEIS)</ref> , 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''' <ref>[http://talkchess.com/forum/viewtopic.php?topic_view=threads&p=513308&t=47335 Re: Perft(14) estimates thread] by [[Peter Österlund]], [[CCC]], April 02, 2013</ref>, while [[Daniel Shawul]] proposed Perft estimation applying [[Monte-Carlo Tree Search|Monte carlo methods]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47740&start=2 MC methods] by [[Daniel Shawul]], [[CCC]], April 11, 2013</ref> <ref>[[Daniel Shawul|Daniel S. Abdi]] ('''2013'''). ''Monte carlo methods for estimating game tree size''. [https://dl.dropboxusercontent.com/u/55295461/perft/perft.pdf pdf]</ref>.
<span id="15"></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>
=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=
* [[Perft Results]]
=Publications=
* [[Aart Bik]] ('''2012'''). ''Computing Deep Perft and Divide Numbers for Checkers''. [[ICGA Journal#35_4|ICGA Journal, Vol. 35, No. 4]] » [[Checkers]]
* [[Daniel Shawul|Daniel S. Abdi]] ('''2013'''). ''Monte carlo methods for estimating game tree size''. [https://dl.dropboxusercontent.com/u/55295461/perft/perft.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47740&topic_view=flat&start=11 Re: MC methods] by [[Daniel Shawul]], [[CCC]], April 13, 2013</ref> » [[Monte-Carlo Tree Search]]
=Perft in other Games=
* [http://tonyjh.com/chess/technical/ Perft for other forms of Chess] by [[Tony Hecker]]
* [http://checker-board.blogspot.com/2009/02/perft-for-checkers.html Perft for Checkers] by [[Martin Fierz]]
* [http://www.aartbik.com/MISC/reversi.html Perft for Reversi/Othello] by [[Aart Bik]]
=Forum Posts=
<ref>[https://www.stmintz.com/ccc/index.php?terms=perft&search=1 Perft], search the [[CCC|CCC Archives]]</ref>
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=107258 Testing speed of "position visiting"] by [[Tom Kerrigan]], [[CCC]], April 23, 2000
* [https://www.stmintz.com/ccc/index.php?id=198498 Who is the champion in calculating perft?] by [[Uri Blass]], [[CCC]], November 22, 2001
* [https://www.stmintz.com/ccc/index.php?id=234025 Perft 5,6 {Fastest program is List}] by [[Dann Corbit]], [[CCC]], June 04, 2002 » [[List (Program)|List]]
* [https://www.stmintz.com/ccc/index.php?id=275133 Perft revisited] by [[Normand M. Blais]], [[CCC]], January 05, 2003
* [https://www.stmintz.com/ccc/index.php?id=326134 Highest perft for initial position?] by [[Albert Bertilsson]], [[CCC]], November 07, 2003
* [https://www.stmintz.com/ccc/index.php?id=335026 Distributed perft project] by [[Albert Bertilsson]], [[CCC]], December 09, 2003
* [https://www.stmintz.com/ccc/index.php?id=334499 Perft(10) verified] by [[Albert Bertilsson]], [[CCC]], December 09, 2003
* [https://www.stmintz.com/ccc/index.php?id=335527 Distributed perft, current standings and trends] by [[Albert Bertilsson]], [[CCC]], December 12, 2003
* [https://www.stmintz.com/ccc/index.php?id=336985 Hashing in distributed perft] by [[Steffen A. Jakob|Steffen Jakob]], [[CCC]], December 19, 2003
* [https://www.stmintz.com/ccc/index.php?id=388806 perft results (how accurate is accurate enough ?)] by [[Roman Hartmann]], [[CCC]], September 23, 2004
* [https://www.stmintz.com/ccc/index.php?id=394229 FRC Perft] by Jürgen Suntinger, [[CCC]], November 02, 2004
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=1377 perft question] by [[Sven Schüle]], [[Computer Chess Forums|Winboard Forum]], January 19, 2005
* [https://www.stmintz.com/ccc/index.php?id=466491 Perft vs Search Re: Cache size does matter] by [[Brian Richardson]], [[CCC]], December 03, 2005
* [https://www.stmintz.com/ccc/index.php?id=488816 Perft -- Test position and data] by [[Charles Roberson]], [[CCC]], February 23, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=20834 A perft faster than qperft?!] by [[Allard Siemelink]], [[CCC]], April 24, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=23634 Perft problems...] by [[Chris Tatham]], [[CCC]], September 10, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=27334 What is perft(x) exactly meaning?] by [[Jouni Uski]], [[CCC]], April 06, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=29425 Perft and mate] by [[Stefano Gemma]], [[CCC]], August 16, 2009 » [[Freccia]]
* [http://www.talkchess.com/forum/viewtopic.php?t=30754 Perft and insufficient material] by [[Sven Schüle]], [[CCC]], November 23, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=34025 Does perft include underpromotion?] by [[Rasjid Chan|Chan Rasjid]], [[CCC]], April 27, 2010
'''2011'''
* [http://www.talkchess.com/forum/viewtopic.php?t=38235 Perft 12 in progress] by [[Steven Edwards]], [[CCC]], February 27, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38862 Perft(12) count confirmed] by [[Steven Edwards]], [[CCC]], April 25, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=39678 Perft(13) betting pool] by [[Steven Edwards]], [[CCC]], July 10, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=40108 Fastest perft] by ethan ara, [[CCC]], August 19, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=41373 Perft(3) from 1978, with a twist!] by [[Steven Edwards]], [[CCC]], December 08, 2011 <ref>[http://news.google.com/newspapers?nid=849&dat=19780417&id=h8lOAAAAIBAJ&sjid=DEoDAAAAIBAJ&pg=6180,1080528 Written in Cobol - Program Written as Chess Buff's Research Aid] by Brad Schultz, [[Computerworld]], April 17, 1978, Page 37</ref>
'''2012'''
* [http://www.talkchess.com/forum/viewtopic.php?t=42512 estimating the number of possible stalemates in perft(n)] by [[Uri Blass]], [[CCC]], February 18, 2012 » [[Stalemate]]
* [http://www.talkchess.com/forum/viewtopic.php?t=42600 Shatranj perfts] by [[Paul Byrne]], [[CCC]], February 24, 2012 » [[Shatranj]]
* [http://www.talkchess.com/forum/viewtopic.php?t=45099 Perft and en_passant] by [[Harald Lüßen]], [[CCC]], September 11, 2012 » [[En passant]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46004 about perft, what is the proper way of doing it?] by Fred Piche, [[CCC]], November 14, 2012
'''2013'''
* [http://www.talkchess.com/forum/viewtopic.php?t=47318 A few positions to test movegen] by [[Martin Sedlak]], [[CCC]], February 24, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47335 Perft(14) estimates thread] by [[Steven Edwards]], [[CCC]], February 26, 2013
: [http://talkchess.com/forum/viewtopic.php?topic_view=threads&p=513308&t=47335 Re: Perft(14) estimates thread] by [[Peter Österlund]], [[CCC]], April 02, 2013 » 61,885,021,521,585,529,237
* [http://www.talkchess.com/forum/viewtopic.php?t=47740 Perft(15) estimates thread] by [[Steven Edwards]], [[CCC]], April 10, 2013
: [http://www.talkchess.com/forum/viewtopic.php?t=47740&start=2 MC methods] by [[Daniel Shawul]], [[CCC]], April 11, 2013 » [[Monte-Carlo Tree Search]]
: [http://www.talkchess.com/forum/viewtopic.php?t=47740&topic_view=flat&start=11 Re: MC methods] by [[Daniel Shawul]], [[CCC]], April 13, 2013
* [http://www.chessprogramming.net/computerchess/is-perft-speed-important/ Is Perft Speed Important?] by [[Steve Maughan]], [http://www.chessprogramming.net/ Computer Chess Programming], April 19, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48217 Perft search speed bottleneck] by Jim Jarvis, [[CCC]], June 07, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48387 Fast perft on GPU (upto 20 Billion nps w/o hashing)] by [[Ankan Banerjee]], [[CCC]], June 22, 2013 » [[GPU]], [[Kogge-Stone Algorithm]] <ref>[https://github.com/ankan-ban/perft_gpu ankan-ban/perft_gpu · GitHub]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=48423 A perft() benchmark] by [[Steven Edwards]], [[CCC]], June 26, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48491 gperft] by [[Paul Byrne]], [[CCC]], July 01, 2013
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=52965 perft/divide bug in roce38 and Sharper? [SOLVED]] by thedrunkard, [[Computer Chess Forums|Winboard Forum]], October 16, 2013 » [[ROCE]], [[Sharper]]
'''2014'''
* [http://www.talkchess.com/forum/viewtopic.php?t=53224 Perft(14) revisited] by [[Steven Edwards]], [[CCC]], August 08, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53406 Perft(14) Weekly Status Report] by [[Steven Edwards]], [[CCC]], August 24, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53408 Non recursive perft()] by [[Steven Edwards]], [[CCC]], August 24, 2014 » [[Iterative Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53439 OpenCL perft() Technical Issues] by [[Steven Edwards]], [[CCC]], August 26, 2014 » [[OpenCL]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53743 A method guaranteed to localize the toughest perft() bugs] by [[Steven Edwards]], [[CCC]], September 18, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54528 FRC / Chess960 Engine with "Divided" Command] by [[Steve Maughan]], [[CCC]], December 02, 2014 » [[Chess960]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54719 Handling integer overflow for certain perft() calculations] by [[Steven Edwards]], [[CCC]], December 22, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54767 Perft(14) verification] by [[Steven Edwards]], [[CCC]], December 28, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=54853 Perft(14) Weekly Status Reports for 2015] by [[Steven Edwards]], [[CCC]], January 04, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55195 Perft(15)] by [[Steven Edwards]], [[CCC]], February 09, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55274 Some Chess960/FRC positions to be confirmed] by [[Reinhard Scharnagl]], [[CCC]], February 09, 2015 » [[Chess960]]
* [http://www.talkchess.com/forum/viewtopic.php?t=55896 An MPI perft program] by [[Chao Ma]], [[CCC]], April 05, 2015 » [[Parallel Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=56523 Deep split perft()] by [[Steven Edwards]], [[CCC]], May 29, 2015 » [[Thread]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2855 Please comment on my Perft speeds] by ppyvabw, [[Computer Chess Forums|OpenChess Forum]], July 10, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56998 100 easy perft(7) test positions] by [[Steven Edwards]], [[CCC]], July 17, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57417 Perft using nullmove] by [[Lasse Hansen]], [[CCC]], August 29, 2015
* [http://www.open-chess.org/viewtopic.php?f=5&t=2913 Perft and hash with legal move generator] by [[Izak Pretorius|Peterpan]], [[Computer Chess Forums|OpenChess Forum]], November 12, 2015 » [[Transposition Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=58406 Auriga - distributed and collaborative Perft] by [[Giuseppe Cannella]], [[CCC]], November 28, 2015 <ref>[http://cinnamonchess.altervista.org/auriga Auriga] by [[Giuseppe Cannella]]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=58726 Perft(14) Weekly Status Reports for 2016] by [[Steven Edwards]], [[CCC]], December 29, 2015
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=59046 Best way to debug perft?] by Meni Rosenfeld, [[CCC]], January 25, 2016 » [[Debugging]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59567 Perft, leaf nodes?] by [[Luis Babboni]], [[CCC]], March 19, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60108 reverse perft] by [[Alexandru Mosoi]], [[CCC]], May 09, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60445 Perft for Xiangqi & Shogi] by [[Patrice Duhamel]], [[CCC]], June 12, 2016 » [[Chinese Chess|Xiangqi]], [[Shogi]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61119 yet another attempt on Perft(14)] by [[Ankan Banerjee]], [[CCC]], August 13, 2016
: [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
'''2017'''
* [http://www.open-chess.org/viewtopic.php?f=5&t=3063 Perft results?] by notachessplayer, [[Computer Chess Forums|OpenChess Forum]], January 01, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64983 perft(15)] by [[Ankan Banerjee]], [[CCC]], August 25, 2017 » [[Perft#15|Perft(15)]]
: [http://www.talkchess.com/forum/viewtopic.php?t=64983&start=4 Re: perft(15)] by [[Ankan Banerjee]], [[CCC]], August 25, 2017
: [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
=External Links=
* [http://oeis.org/A048987 A048987] from [https://en.wikipedia.org/wiki/On-Line_Encyclopedia_of_Integer_Sequences On-Line Encyclopedia of Integer Sequences] (OEIS)
* [https://wismuth.com/chess/statistics-games.html Statistics on chess games] by [[Mathematician#FLabelle|François Labelle]]
* [https://en.wikipedia.org/wiki/Performance_testing Performance testing from Wikipedia]
* [https://web.archive.org/web/20061014115710/http://www.albert.nu/programs/dperft/ Distributed Perft Project] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])
==Implementations==
* [http://home.hccnet.nl/h.g.muller/dwnldpage.html µ-Max Dowload Page - qperft] by [[Harm Geert Muller]] » [[Micro-Max]]
* [https://github.com/ankan-ban/perft_gpu ankan-ban/perft_gpu · GitHub] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48387 Fast perft on GPU (upto 20 Billion nps w/o hashing)] by [[Ankan Banerjee]], [[CCC]], June 22, 2013</ref>
* [http://cinnamonchess.altervista.org/auriga Auriga] by [[Giuseppe Cannella]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=58406 Auriga - distributed and collaborative Perft] by [[Giuseppe Cannella]], [[CCC]], November 28, 2015</ref>
* [https://github.com/Mk-Chan/BBPerft BBPerft: A fast, bitboard based chess perft result generator] by [[Manik Charan]] derived from [[WyldChess]]
* [http://brausch.org/home/chess/index.html Chess Engine OliThink - New Move Generator OliPerft (Pre OliThink 5)] by [[Oliver Brausch]] » [[OliThink]]
* [http://www.craftychess.com/documentation/craftydoc.html Crafty Command Documentation] by [[Robert Hyatt]], see perft <depth> » [[Crafty]]
* [http://www.rocechess.ch/perft.html perft, divide, debugging a move generator] from [[ROCE]] by [[Roman Hartmann]]
* [http://marcelk.net/rookie/nostalgia/v3/perft-random.epd perft-random.epd] by [[Marcel van Kervinck]] » [[Rookie]]
==Video Tutorial==
* A quick overview of the perft process by [[Jonathan Warkentin]], [https://en.wikipedia.org/wiki/YouTube YouTube] Videos
: {{#evu:https://www.youtube.com/watch?v=A0HJbwRwILk|alignment=left|valignment=top}}
* An example of debugging a perft error by [[Jonathan Warkentin]], [https://en.wikipedia.org/wiki/YouTube YouTube] Videos
: {{#evu:https://www.youtube.com/watch?v=bAONObdxF54|alignment=left|valignment=top}}
* Improving the perft speed & debugging tips by [[Jonathan Warkentin]], [https://en.wikipedia.org/wiki/YouTube YouTube] Videos
: {{#evu:https://www.youtube.com/watch?v=BIzAfg5sdqg|alignment=left|valignment=top}}
=References=
<references />
'''[[Move Generation|Up one level]]'''
