25,161
edits
Changes
avoiding too long titles, span ids repaired, some code optimizations
u64 Perft(int depth)
{
}
</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 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 values.
<pre>
u64 Perft(int depth/* assuming >= 1 */)
{
}
</pre>
==Perft function with pseudo move generatorPseudo Legal Moves==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 Below code can avoid that problem and run much faster:
<pre>
u64 Perft(int depth)
{
}
</pre>
==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>.
=Quotes=
