Difference between revisions of "Perft"

From Chessprogramming wiki
Jump to: navigation, search
(21 intermediate revisions by 2 users not shown)
Line 2: Line 2:
  
 
'''Perft''', ('''perf'''ormance '''t'''est, move path enumeration)<br/>
 
'''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.
+
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=  
 
=Perft function=  
Line 26: Line 26:
 
}
 
}
 
</pre>
 
</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:
+
=Speed up=
 +
==Bulk-counting==
 +
Assuming the above code used a legal move generator, it could improve speed significantly: 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.  
 +
 
 
<pre>
 
<pre>
...
+
typedef unsigned long long u64;
//__/* DELETE: if (depth == 0) return 1; */__//
 
  
n_moves = GenerateMoves(move_list);
+
u64 Perft(int depth)
 +
{
 +
    MOVE move_list[256];
 +
    int n_moves, i;
 +
    u64 nodes = 0;
  
__if (depth == 1) return n_moves;__
+
    n_moves = GenerateLegalMoves(move_list);
...
+
    for (i = 0; i < n_moves; i++) {
 +
        if (depth == 1) nodes++;
 +
        else {
 +
          MakeMove(move_list[i]);
 +
          nodes += Perft(depth - 1);
 +
          UndoMove(move_list[i]);
 +
        }
 +
    }
 +
    return nodes;
 +
}
 
</pre>
 
</pre>
  
=Hashing=
+
==Perft function with pseudo move generator==
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.
+
To generate legal moves some programs have to make moves first, call the function IsIncheck and then undo those moves. That makes the above Perft function to make and undo moves twice for all moves. Bellow code can avoid that problem and run much faster:
 
 
=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>
 
<pre>
 
typedef unsigned long long u64;
 
typedef unsigned long long u64;
Line 65: Line 77:
 
}
 
}
 
</pre>
 
</pre>
 +
 +
<span id="Bulk"></span>
 +
 +
 +
==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>
 
<span id="History"></span>
 
=Perft History=  
 
=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.
+
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]] suggested the move path enumeration in 1995 as implemented in [[Spector]] <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/M8V1AzkfOok/YV9lcfOlfgIJ Re: Speed of Move Generator] by [[Steven Edwards]], [[Computer Chess Forums|rgcc]], August 16, 1995</ref> and has since been actively involved in Perft computations, while the term "Perft" was likely coined by a [[Crafty]] command, despite its initial implementation was not conform to the above definition <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/2nqtCdHC-r0/ENqomE2u51kJ Re: complete opening tree stats] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], February 05, 1998</ref>.
  
 
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>.  
 
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>.  
Line 73: Line 97:
 
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>.
 
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>
 
<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=  
+
 
 +
=Results=  
 
* [[Perft Results]]
 
* [[Perft Results]]
 +
* [[Chess960 Perft Results]]
  
 
=Publications=  
 
=Publications=  
 
* [[Aart Bik]] ('''2012'''). ''Computing Deep Perft and Divide Numbers for Checkers''. [[ICGA Journal#35_4|ICGA Journal, Vol. 35, No. 4]] » [[Checkers]]
 
* [[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]]
+
* [[Daniel Shawul|Daniel S. Abdi]] ('''2013'''). ''Monte carlo methods for estimating game tree size''. <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=  
 
=Perft in other Games=  
Line 89: Line 113:
  
 
=Forum Posts=  
 
=Forum Posts=  
<ref>[https://www.stmintz.com/ccc/index.php?terms=perft&search=1 Perft], search the [[CCC|CCC Archives]]</ref>
+
==1995 ...==
 +
* [https://groups.google.com/d/msg/rec.games.chess.computer/M8V1AzkfOok/YV9lcfOlfgIJ Re: Speed of Move Generator] by [[Steven Edwards]], [[Computer Chess Forums|rgcc]], August 16, 1995 » [[Spector]]  
 +
* [https://groups.google.com/d/msg/rec.games.chess.computer/2nqtCdHC-r0/ENqomE2u51kJ Re: complete opening tree stats] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], February 05, 1998 » [[Crafty]]
 
==2000 ...==  
 
==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=107258 Testing speed of "position visiting"] by [[Tom Kerrigan]], [[CCC]], April 23, 2000
 +
* [https://groups.google.com/d/msg/rec.games.chess.computer/ek5fbFf4ajc/lrPxv2kDHgkJ Experiments with crafty perft command] by Guy Macon, [[Computer Chess Forums|rgcc]], December 10, 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=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=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=275133 Perft revisited] by [[Normand M. Blais]], [[CCC]], January 05, 2003
 +
* [https://www.stmintz.com/ccc/index.php?id=276596 perft question] by [[Joel Veness]], [[CCC]], January 12, 2003
 +
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=41318 Perft] by [[Andreas Herrmann]], [[Computer Chess Forums|Winboard Forum]], February 18, 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=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=335026 Distributed perft project] by [[Albert Bertilsson]], [[CCC]], December 09, 2003
Line 100: Line 129:
 
* [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=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=336985 Hashing in distributed perft] by [[Steffen A. Jakob|Steffen Jakob]], [[CCC]], December 19, 2003
 +
* [https://www.stmintz.com/ccc/index.php?id=386249 perft records] by [[Peter Fendrich]], [[CCC]], September 06, 2004
 
* [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=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
 
* [https://www.stmintz.com/ccc/index.php?id=394229 FRC Perft] by Jürgen Suntinger, [[CCC]], November 02, 2004
Line 138: Line 168:
 
* [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]]
 
* [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'''
 
'''2014'''
 +
* [http://www.open-chess.org/viewtopic.php?f=5&t=2238 Perft and Captures] by [[Christian Daley|CDaley11]], [[Computer Chess Forums|OpenChess Forum]], January 24, 2013 » [[Captures]]
 
* [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=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=53406 Perft(14) Weekly Status Report] by [[Steven Edwards]], [[CCC]], August 24, 2014
Line 165: Line 196:
 
* [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 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  
 
: [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'''
+
'''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.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 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=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  
 
: [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  
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70530 No standard specification for Perft] by [[Michael Sherwin]], [[CCC]], April 19, 2019
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=71379 You gotta love Perft... just not too much!] by [[Martin Bryant]], [[CCC]], July 27, 2019
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=71550 Shogi Perft numbers] by [[Toni Helminen]], [[CCC]], August 14, 2019 » [[Shogi]]
 +
==2020 ...==
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73493 Where to enter/read position into hash table in perft?] by [[Marcel Vanthoor]], [[CCC]], March 28, 2020 » [[Transposition Table]]
 +
* [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=  
 
=External Links=  
Line 197: Line 237:
 
<references />
 
<references />
 
'''[[Move Generation|Up one level]]'''
 
'''[[Move Generation|Up one level]]'''
 +
[[Category:Videos]]

Revision as of 19:56, 11 May 2020

Home * Board Representation * Move Generation * Perft

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.

Perft function

A simple perft function in C looks as follows:

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;
}


Speed up

Bulk-counting

Assuming the above code used a legal move generator, it could improve speed significantly: 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.

typedef unsigned long long u64;

u64 Perft(int depth)
{
    MOVE move_list[256];
    int n_moves, i;
    u64 nodes = 0;

    n_moves = GenerateLegalMoves(move_list);
    for (i = 0; i < n_moves; i++) {
        if (depth == 1) nodes++;
        else {
           MakeMove(move_list[i]);
           nodes += Perft(depth - 1);
           UndoMove(move_list[i]);
        }
    }
    return nodes;
}

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 the above Perft function to make and undo moves twice for all moves. Bellow code can avoid that problem and run much faster:

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;
}


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.


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.


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 suggested the move path enumeration in 1995 as implemented in Spector [3] and has since been actively involved in Perft computations, while the term "Perft" was likely coined by a Crafty command, despite its initial implementation was not conform to the above definition [4].

In December 2003, Albert Bertilsson started a distributed project [5] to calculate perft(11) of the initial position, taking over a week to calculate [6] . 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 [7] , 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 [8], while Daniel Shawul proposed Perft estimation applying Monte carlo methods [9] [10]. In August 2017, Ankan Banerjee, who already confirmed Peter Österlund's perft(14) in September 2016 [11], computed perft(15) of 2,015,099,950,053,364,471,960 with his GPU perft program [12], running it several days two times with different zobrist keys on a cluster of Nvidia DGX-1 server systems [13]. 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 [14]. 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) [15].


Results

Publications

Perft in other Games

Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...

2011

2012

2013

Re: 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

2014

2015 ...

2016

Re: yet another attempt on Perft(14) by Ankan Banerjee, CCC, September 09, 2016

2017 ...

Re: 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

2020 ...

External Links

Implementations

Video Tutorial

References

  1. Written in Cobol - Program Written as Chess Buff's Research Aid by Brad Schultz, Computerworld, April 17, 1978, Page 37
  2. Perft(3) from 1978, with a twist! by Steven Edwards, CCC, December 08, 2011
  3. Re: Speed of Move Generator by Steven Edwards, rgcc, August 16, 1995
  4. Re: complete opening tree stats by Robert Hyatt, rgcc, February 05, 1998
  5. Distributed perft project by Albert Bertilsson, CCC, December 09, 2003
  6. Distributed Perft Project (Wayback Machine)
  7. A048987 from On-Line Encyclopedia of Integer Sequences (OEIS)
  8. Re: Perft(14) estimates thread by Peter Österlund, CCC, April 02, 2013
  9. MC methods by Daniel Shawul, CCC, April 11, 2013
  10. Daniel S. Abdi (2013). Monte carlo methods for estimating game tree size. pdf
  11. Re: yet another attempt on Perft(14) by Ankan Banerjee, CCC, September 09, 2016
  12. ankan-ban/perft_gpu · GitHub
  13. DGX-1 for AI Research | NVIDIA
  14. Re: Perft(15): comparison of estimates with Ankan's result by Ankan Banerjee, CCC, August 26, 2017
  15. Re: perft(15) by Ankan Banerjee, CCC, August 25, 2017
  16. Re: MC methods by Daniel Shawul, CCC, April 13, 2013
  17. Written in Cobol - Program Written as Chess Buff's Research Aid by Brad Schultz, Computerworld, April 17, 1978, Page 37
  18. ankan-ban/perft_gpu · GitHub
  19. Auriga by Giuseppe Cannella
  20. Fast perft on GPU (upto 20 Billion nps w/o hashing) by Ankan Banerjee, CCC, June 22, 2013
  21. Auriga - distributed and collaborative Perft by Giuseppe Cannella, CCC, November 28, 2015

Up one level