Changes

Jump to: navigation, search

Perft

1,847 bytes added, 07:48, 11 October 2021
→‎2020 ...
u64 Perft(int depth)
{
MOVE move_list[256]; int n_moves, i; u64 nodes = 0;
if (depth == 0) return 11ULL;
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>
=Speed up=
==<span id="Bulk"></span>Bulk-counting==Assuming the above code used a legal move generator. The algorithm is simple, short but it generates makes moves for every node even they are the leave (ends of branches). 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 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 Perft valuesand may make the task of collecting some extra information such as the number of captures and checks be almost impossible.
<pre>
u64 Perft(int depth/* assuming >= 1 */)
{
MOVE move_list[256]; int n_moves, i; u64 nodes = 0;  n_moves = GenerateLegalMoves(move_list);  if (depth == 1) return (u64) 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>
==Perft function with pseudo move generatorPseudo Legal Moves==To generate legal moves some programs have to make moves first, call a function to check if the function IsIncheck position incheck and then undo those moves. That makes the above Perft function to make and undo moves twice for all moves. Bellow Below code can avoid that problem and run much faster:
<pre>
u64 Perft(int depth)
{
MOVE move_list[256]; int n_moves, i; u64 nodes = 0;
if (depth == 0) return 11ULL;
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="Bulk"></span>
==Hashing==
=Divide=
The Divide command is often implemented as a variation of perftPerft, listing all moves and for each move, the perft of the decremented depth. However, some programs already give "divided" output for perftPerft. Below is output of [[Stockfish]] when computing perft 5 for start position:
<pre>
=Purposes=
Perft is mostly for debugging purposes. It works mainly with functions: move generators, make move, unmake move. They all are very basic and vital for chess engines. By comparing perft Perft results developers can find out if those functions work correctly or not. If they are incorrect developers can narrow quickly by comparing branches, then call Perft for wrong branches with lower depth, repeat until finding direct positions which give the wrong result.
Other purposes:
<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>
 
* [ Perft speed and depth questions] by [[Mark Buisseret]], [[CCC]], June 12, 2020
=Quotes=
* [[Perft Results]]
* [[Chess960 Perft Results]]
* [[Chinese Chess 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''. <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/strategy.php Perft for Checkers and Reversi/Othello] by [[Aart Bik]]
=Forum Posts=
* [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]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72669 LastEmperor - Chess960 perft tool] by [[Toni Helminen|JohnWoe]], [[CCC]], December 28, 2019 » [[Chess960 Perft Results]]
==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=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]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74153 Perft speed and depth questions] by [[Mark Buisseret]], [[CCC]], June 12, 2020* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75877 Place to find correct perft result from a fen position] by [[Elias Nilsson]], [[CCC]], November 20, 2020 » [[Perft Results]]'''2021'''* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76430 Chinese chess Xiangqi perft results] by [[Maksim Korzh]], [[CCC]], January 27, 2021 » [[Chinese Chess Perft Results]]* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77054 PERFT transposition table funny?!] by [[Martin Bryant]], [[CCC]], April 10, 2021 » [[Transposition Table]], [[Memory]]* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=77069 Perft 7 -> 1.6 trillion moves] by [[Michael Byrne|MikeB]], [[CCC]], April 12, 2021* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77350 Being silly with perft and legal move generation] by [[Jakob Progsch]], [[CCC]], May 19, 2021 » [[Move Generation#Legal|Legal Move Generation]], [[En passant]]* [http://talkchess.com/forum3/viewtopic.php?f=7&t=78119 Perft position to debug check-evasions via en passant capture] by [[Roland Tomasi]], [[CCC]], September 06, 2021* [http://talkchess.com/forum3/viewtopic.php?f=7&t=78241 Perft test] by [[Pierluigi Meloni]], [[CCC]], September 24, 2021* [http://talkchess.com/forum3/viewtopic.php?f=7&t=78230 Gigantua: 1.5 Giganodes per Second per Core move generator] by [[Daniel Infuehr]], [[CCC]], September 22, 2021* [http://talkchess.com/forum3/viewtopic.php?f=7&t=78352 Gigantua: 2 Gigamoves per Second per Core move generator - Sourcecode Release] by [[Daniel Infuehr]], [[CCC]], October 07, 2021
=External Links=
* [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])
==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/strategy.php Perft for Checkers and Reversi/Othello] by [[Aart Bik]]
==Implementations==
* [httphttps://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>
* [http://www.craftychess.com/documentation/craftydoc.html Crafty Command Documentation] by [[Robert Hyatt]], see perft <depth> » [[Crafty]]
* [https://github.com/abulmo/hqperft hqperft: Chess move generation based on (H)yperbola (Q)uintessence & range attacks] by [[Richard Delorme]] » [[Hyperbola Quintessence]]
* [https://github.com/jniemann66/juddperft GitHub - jniemann66/juddperft: Chess move generation engine] by [[Judd Niemann]]
* [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]]
Retrieved from "https://www.chessprogramming.org/Special:MobileDiff/19520...25869"

Navigation menu