Changes

Jump to: navigation, search

Perft

1,463 bytes added, 20:56, 11 May 2020
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=
}
</pre>
<span id =Speed up="Bulk"></span>==Bulk-counting== Instead 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. Assuming the above code used a legal move generator, it would only need the following modification: 
<pre>
...//__/* DELETE: if (depth == 0) return 1typedef unsigned long long u64; */__//
u64 Perft(int depth){ MOVE move_list[256]; int n_moves , i; u64 nodes = GenerateMoves(move_list)0;
__if 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 n_movesnodes;__...}
</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 the 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;
}
</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>
=Perft History=
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 alsoResults=
* [[Perft Results]]
* [[Chess960 Perft Results]]
* [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=335026 Distributed perft project] by [[Albert Bertilsson]], [[CCC]], December 09, 2003
* [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.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=53406 Perft(14) Weekly Status Report] by [[Steven Edwards]], [[CCC]], August 24, 2014
* [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=
Retrieved from "https://www.chessprogramming.org/Special:MobileDiff/15332...19113"

Navigation menu