Difference between revisions of "Perft"

From Chessprogramming wiki
Jump to: navigation, search
(2020 ...)
(2020 ...)
(40 intermediate revisions by 2 users not shown)
Line 11: Line 11:
 
u64 Perft(int depth)
 
u64 Perft(int depth)
 
{
 
{
    MOVE move_list[256];
+
  MOVE move_list[256];
    int n_moves, i;
+
  int n_moves, i;
    u64 nodes = 0;
+
  u64 nodes = 0;
  
    if (depth == 0) return 1;
+
  if (depth == 0)  
 +
    return 1ULL;
  
    n_moves = GenerateLegalMoves(move_list);
+
  n_moves = GenerateLegalMoves(move_list);
    for (i = 0; i < n_moves; i++) {
+
  for (i = 0; i < n_moves; i++) {
        MakeMove(move_list[i]);
+
    MakeMove(move_list[i]);
        nodes += Perft(depth - 1);
+
    nodes += Perft(depth - 1);
        UndoMove(move_list[i]);
+
    UndoMove(move_list[i]);
    }
+
  }
    return nodes;
+
  return nodes;
 
}
 
}
 
</pre>
 
</pre>
  
 
=Speed up=
 
=Speed up=
==Bulk-counting==
+
==<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 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. The algorithm is simple, short but it 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 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 and may make the task of collecting some extra information such as the number of captures and checks be almost impossible.  
  
 
<pre>
 
<pre>
typedef unsigned long long u64;
+
u64 Perft(int depth /* assuming >= 1 */)
 +
{
 +
  MOVE move_list[256];
 +
  int n_moves, i;
 +
  u64 nodes = 0;
  
u64 Perft(int depth)
+
  n_moves = GenerateLegalMoves(move_list);
{
+
 
    MOVE move_list[256];
+
  if (depth == 1)
     int n_moves, i;
+
     return (u64) n_moves;
    u64 nodes = 0;
 
  
    n_moves = GenerateLegalMoves(move_list);
+
  for (i = 0; i < n_moves; i++) {
    for (i = 0; i < n_moves; i++) {
+
    MakeMove(move_list[i]);
        if (depth == 1) nodes++;
+
    nodes += Perft(depth - 1);
        else {
+
    UndoMove(move_list[i]);
          MakeMove(move_list[i]);
+
  }
          nodes += Perft(depth - 1);
+
  return nodes;
          UndoMove(move_list[i]);
 
        }
 
    }
 
    return nodes;
 
 
}
 
}
 
</pre>
 
</pre>
  
==Perft function with pseudo move generator==
+
==Pseudo 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 code can avoid that problem and run much faster:
+
To generate legal moves some programs have to make moves first, call a function to check if the position incheck and then undo those moves. That makes the above Perft function to make and undo moves twice for all moves. Below code can avoid that problem and run much faster:
 
<pre>
 
<pre>
typedef unsigned long long u64;
 
 
 
u64 Perft(int depth)
 
u64 Perft(int depth)
 
{
 
{
    MOVE move_list[256];
+
  MOVE move_list[256];
    int n_moves, i;
+
  int n_moves, i;
    u64 nodes = 0;
+
  u64 nodes = 0;
  
    if (depth == 0) return 1;
+
  if (depth == 0)  
 +
    return 1ULL;
  
    n_moves = GenerateMoves(move_list);
+
  n_moves = GenerateMoves(move_list);
    for (i = 0; i < n_moves; i++) {
+
  for (i = 0; i < n_moves; i++) {
        MakeMove(move_list[i]);
+
    MakeMove(move_list[i]);
        if (!IsIncheck())
+
    if (!IsIncheck())
            nodes += Perft(depth - 1);
+
      nodes += Perft(depth - 1);
        UndoMove(move_list[i]);
+
    UndoMove(move_list[i]);
    }
+
  }
    return nodes;
+
  return nodes;
 
}
 
}
 
</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. Below is output of [[Stockfish]] when computing perft 5 for start position:
  
==Hashing==
+
<pre>
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.
+
go perft 5
 +
a2a3: 181046
 +
b2b3: 215255
 +
c2c3: 222861
 +
d2d3: 328511
 +
e2e3: 402988
 +
f2f3: 178889
 +
g2g3: 217210
 +
h2h3: 181044
 +
a2a4: 217832
 +
b2b4: 216145
 +
c2c4: 240082
 +
d2d4: 361790
 +
e2e4: 405385
 +
f2f4: 198473
 +
g2g4: 214048
 +
h2h4: 218829
 +
b1a3: 198572
 +
b1c3: 234656
 +
g1f3: 233491
 +
g1h3: 198502
  
 +
Nodes searched: 4865609
 +
</pre>
  
=Divide=  
+
=Purposes=
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 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 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:
 +
* give a quick glance at how good/bad their generators/make/unmake functions are, compared with the speed of other engines
 +
* calculate branch factors
 +
* a factor to estimate how the complexity of chess variants, by comparing branch factors or Perft results at a given depth for their starting positions
  
<span id="History"></span>
+
=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]] 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>.
 
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>.
  
Line 95: Line 122:
 
<span id="15"></span>
 
<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>.
 
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>
 
  
 +
=Quotes=
 +
by [[Robert Hyatt]] in a forum post, June 12, 2020 <ref>[http://talkchess.com/forum3/viewtopic.php?f=7&t=74153 Re: Perft speed and depth questions] by [[Mark Buisseret]], [[Computer Chess Forums|CCRL Discussion Board]], June 12, 2020</ref> :
 +
I believe I was the first to use this. Back in the 80's. We rewrote the move generator in Cray Blitz in assembly language. It was a pain to debug. I decided on the "perft" approach solely to test/debug the move generator. We'd run two versions, one FORTRAN, one assembly, and we tested and debugged until they matched.
 +
I carried this over into Crafty as early versions went through several different approaches on move generation. Starting with the Slate/Atkin approach, then rotated bit boards (which took some time to debug), and the magic. It was really intended solely for that purpose. Then several started to use it as a benchmark for speed. I never followed that path since move generation is a very small part of the overall CPU time burned.
 +
Speed here is not so important. I doubt anyone's move generator takes more than 10% of total search time, which means a 20% improvement in perft numbers is only a 2% overall speed gain. I would not worry about anything but matching the node counts exactly...
  
 
=Results=  
 
=Results=  
 
* [[Perft Results]]
 
* [[Perft Results]]
 
* [[Chess960 Perft Results]]
 
* [[Chess960 Perft Results]]
 +
* [[Chinese Chess 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''.  <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=
 
* [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=  
 
=Forum Posts=  
Line 203: Line 230:
 
* [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=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=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 ...==
 
==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=73493 Where to enter/read position into hash table in perft?] by [[Marcel Vanthoor]], [[CCC]], March 28, 2020 » [[Transposition Table]]
Line 209: Line 237:
 
* [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=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=73812 Request for InDoubleCheck PERFTS EPDs] by [[Chris Whittington]], [[CCC]], May 02, 2020 » [[Double Check]]
* [http://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=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]]
 +
* [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
 +
* [http://talkchess.com/forum3/viewtopic.php?f=7&t=80952 My Perft Results] by [[JoAnn Peeler]], [[CCC]], November 04, 2022
 +
* [https://talkchess.com/viewtopic.php?t=83392 Perft(16) estimate after averaging MC samples.] by Ajedrecista, [[CCC]], February 26, 2024
  
 
=External Links=  
 
=External Links=  
Line 216: Line 255:
 
* [https://en.wikipedia.org/wiki/Performance_testing Performance testing from Wikipedia]
 
* [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])
 
* [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==
 
==Implementations==
* [http://home.hccnet.nl/h.g.muller/dwnldpage.html µ-Max Dowload Page - qperft] by [[Harm Geert Muller]] » [[Micro-Max]]
+
* [https://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>
 
* [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://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>
Line 224: Line 267:
 
* [http://www.craftychess.com/documentation/craftydoc.html Crafty Command Documentation] by [[Robert Hyatt]], see perft <depth> » [[Crafty]]
 
* [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/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://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]]
 
* [http://marcelk.net/rookie/nostalgia/v3/perft-random.epd perft-random.epd] by [[Marcel van Kervinck]] » [[Rookie]]

Revision as of 04:07, 16 March 2024

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 the following:

typedef unsigned long long u64;

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

  if (depth == 0) 
    return 1ULL;

  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. The algorithm is simple, short but it 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 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 and may make the task of collecting some extra information such as the number of captures and checks be almost impossible.

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;

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

Pseudo Legal Moves

To generate legal moves some programs have to make moves first, call a function to check if the position incheck and then undo those moves. That makes the above Perft function to make and undo moves twice for all moves. Below code can avoid that problem and run much faster:

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

  if (depth == 0) 
    return 1ULL;

  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. Below is output of Stockfish when computing perft 5 for start position:

go perft 5
a2a3: 181046
b2b3: 215255
c2c3: 222861
d2d3: 328511
e2e3: 402988
f2f3: 178889
g2g3: 217210
h2h3: 181044
a2a4: 217832
b2b4: 216145
c2c4: 240082
d2d4: 361790
e2e4: 405385
f2f4: 198473
g2g4: 214048
h2h4: 218829
b1a3: 198572
b1c3: 234656
g1f3: 233491
g1h3: 198502

Nodes searched: 4865609

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

  • give a quick glance at how good/bad their generators/make/unmake functions are, compared with the speed of other engines
  • calculate branch factors
  • a factor to estimate how the complexity of chess variants, by comparing branch factors or Perft results at a given depth for their starting positions

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].

Quotes

by Robert Hyatt in a forum post, June 12, 2020 [16] :

I believe I was the first to use this. Back in the 80's. We rewrote the move generator in Cray Blitz in assembly language. It was a pain to debug. I decided on the "perft" approach solely to test/debug the move generator. We'd run two versions, one FORTRAN, one assembly, and we tested and debugged until they matched.
I carried this over into Crafty as early versions went through several different approaches on move generation. Starting with the Slate/Atkin approach, then rotated bit boards (which took some time to debug), and the magic. It was really intended solely for that purpose. Then several started to use it as a benchmark for speed. I never followed that path since move generation is a very small part of the overall CPU time burned.
Speed here is not so important. I doubt anyone's move generator takes more than 10% of total search time, which means a 20% improvement in perft numbers is only a 2% overall speed gain. I would not worry about anything but matching the node counts exactly...

Results

Publications

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

Perft in other Games

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: Perft speed and depth questions by Mark Buisseret, CCRL Discussion Board, June 12, 2020
  17. Re: MC methods by Daniel Shawul, CCC, April 13, 2013
  18. Written in Cobol - Program Written as Chess Buff's Research Aid by Brad Schultz, Computerworld, April 17, 1978, Page 37
  19. ankan-ban/perft_gpu · GitHub
  20. Auriga by Giuseppe Cannella
  21. Fast perft on GPU (upto 20 Billion nps w/o hashing) by Ankan Banerjee, CCC, June 22, 2013
  22. Auriga - distributed and collaborative Perft by Giuseppe Cannella, CCC, November 28, 2015

Up one level