Difference between revisions of "Perft"
(→Bulk-counting) |
|||
Line 27: | Line 27: | ||
</pre> | </pre> | ||
+ | |||
+ | =Speed up= | ||
==Bulk-counting== | ==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. | 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. | ||
Line 79: | Line 81: | ||
− | =Hashing= | + | ==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 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. | ||
Revision as of 03:51, 25 April 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.
Contents
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.
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].
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.
Results
Publications
- Aart Bik (2012). Computing Deep Perft and Divide Numbers for Checkers. ICGA Journal, Vol. 35, No. 4 » Checkers
- Daniel S. Abdi (2013). Monte carlo methods for estimating game tree size. [16] » Monte-Carlo Tree Search
Perft in other Games
- Perft for other forms of Chess by Tony Hecker
- Perft for Checkers by Martin Fierz
- Perft for Checkers and Reversi/Othello by Aart Bik
Forum Posts
1995 ...
- Re: Speed of Move Generator by Steven Edwards, rgcc, August 16, 1995 » Spector
- Re: complete opening tree stats by Robert Hyatt, rgcc, February 05, 1998 » Crafty
2000 ...
- Testing speed of "position visiting" by Tom Kerrigan, CCC, April 23, 2000
- Experiments with crafty perft command by Guy Macon, rgcc, December 10, 2000
- Who is the champion in calculating perft? by Uri Blass, CCC, November 22, 2001
- Perft 5,6 {Fastest program is List} by Dann Corbit, CCC, June 04, 2002 » List
- Perft revisited by Normand M. Blais, CCC, January 05, 2003
- perft question by Joel Veness, CCC, January 12, 2003
- Perft by Andreas Herrmann, Winboard Forum, February 18, 2003
- Highest perft for initial position? by Albert Bertilsson, CCC, November 07, 2003
- Distributed perft project by Albert Bertilsson, CCC, December 09, 2003
- Perft(10) verified by Albert Bertilsson, CCC, December 09, 2003
- Distributed perft, current standings and trends by Albert Bertilsson, CCC, December 12, 2003
- Hashing in distributed perft by Steffen Jakob, CCC, December 19, 2003
- perft records by Peter Fendrich, CCC, September 06, 2004
- perft results (how accurate is accurate enough ?) by Roman Hartmann, CCC, September 23, 2004
- FRC Perft by Jürgen Suntinger, CCC, November 02, 2004
2005 ...
- perft question by Sven Schüle, Winboard Forum, January 19, 2005
- Perft vs Search Re: Cache size does matter by Brian Richardson, CCC, December 03, 2005
- Perft -- Test position and data by Charles Roberson, CCC, February 23, 2006
- A perft faster than qperft?! by Allard Siemelink, CCC, April 24, 2008
- Perft problems... by Chris Tatham, CCC, September 10, 2008
- What is perft(x) exactly meaning? by Jouni Uski, CCC, April 06, 2009
- Perft and mate by Stefano Gemma, CCC, August 16, 2009 » Freccia
- Perft and insufficient material by Sven Schüle, CCC, November 23, 2009
2010 ...
- Does perft include underpromotion? by Chan Rasjid, CCC, April 27, 2010
2011
- Perft 12 in progress by Steven Edwards, CCC, February 27, 2011
- Perft(12) count confirmed by Steven Edwards, CCC, April 25, 2011
- Perft(13) betting pool by Steven Edwards, CCC, July 10, 2011
- Fastest perft by ethan ara, CCC, August 19, 2011
- Perft(3) from 1978, with a twist! by Steven Edwards, CCC, December 08, 2011 [17]
2012
- estimating the number of possible stalemates in perft(n) by Uri Blass, CCC, February 18, 2012 » Stalemate
- Shatranj perfts by Paul Byrne, CCC, February 24, 2012 » Shatranj
- Perft and en_passant by Harald Lüßen, CCC, September 11, 2012 » En passant
- about perft, what is the proper way of doing it? by Fred Piche, CCC, November 14, 2012
2013
- A few positions to test movegen by Martin Sedlak, CCC, February 24, 2013
- Perft(14) estimates thread by Steven Edwards, CCC, February 26, 2013
- Re: Perft(14) estimates thread by Peter Österlund, CCC, April 02, 2013 » 61,885,021,521,585,529,237
- Perft(15) estimates thread by Steven Edwards, CCC, April 10, 2013
- MC methods by Daniel Shawul, CCC, April 11, 2013 » Monte-Carlo Tree Search
- Re: MC methods by Daniel Shawul, CCC, April 13, 2013
- Is Perft Speed Important? by Steve Maughan, Computer Chess Programming, April 19, 2013
- Perft search speed bottleneck by Jim Jarvis, CCC, June 07, 2013
- Fast perft on GPU (upto 20 Billion nps w/o hashing) by Ankan Banerjee, CCC, June 22, 2013 » GPU, Kogge-Stone Algorithm [18]
- A perft() benchmark by Steven Edwards, CCC, June 26, 2013
- gperft by Paul Byrne, CCC, July 01, 2013
- perft/divide bug in roce38 and Sharper? [SOLVED] by thedrunkard, Winboard Forum, October 16, 2013 » ROCE, Sharper
2014
- Perft and Captures by CDaley11, OpenChess Forum, January 24, 2013 » Captures
- Perft(14) revisited by Steven Edwards, CCC, August 08, 2014
- Perft(14) Weekly Status Report by Steven Edwards, CCC, August 24, 2014
- Non recursive perft() by Steven Edwards, CCC, August 24, 2014 » Iterative Search
- OpenCL perft() Technical Issues by Steven Edwards, CCC, August 26, 2014 » OpenCL
- A method guaranteed to localize the toughest perft() bugs by Steven Edwards, CCC, September 18, 2014
- FRC / Chess960 Engine with "Divided" Command by Steve Maughan, CCC, December 02, 2014 » Chess960
- Handling integer overflow for certain perft() calculations by Steven Edwards, CCC, December 22, 2014
- Perft(14) verification by Steven Edwards, CCC, December 28, 2014
2015 ...
- Perft(14) Weekly Status Reports for 2015 by Steven Edwards, CCC, January 04, 2015
- Perft(15) by Steven Edwards, CCC, February 09, 2015
- Some Chess960/FRC positions to be confirmed by Reinhard Scharnagl, CCC, February 09, 2015 » Chess960
- An MPI perft program by Chao Ma, CCC, April 05, 2015 » Parallel Search
- Deep split perft() by Steven Edwards, CCC, May 29, 2015 » Thread
- Please comment on my Perft speeds by ppyvabw, OpenChess Forum, July 10, 2015
- 100 easy perft(7) test positions by Steven Edwards, CCC, July 17, 2015
- Perft using nullmove by Lasse Hansen, CCC, August 29, 2015
- Perft and hash with legal move generator by Peterpan, OpenChess Forum, November 12, 2015 » Transposition Table
- Auriga - distributed and collaborative Perft by Giuseppe Cannella, CCC, November 28, 2015 [19]
- Perft(14) Weekly Status Reports for 2016 by Steven Edwards, CCC, December 29, 2015
2016
- Best way to debug perft? by Meni Rosenfeld, CCC, January 25, 2016 » Debugging
- Perft, leaf nodes? by Luis Babboni, CCC, March 19, 2016
- reverse perft by Alexandru Mosoi, CCC, May 09, 2016
- Perft for Xiangqi & Shogi by Patrice Duhamel, CCC, June 12, 2016 » Xiangqi, Shogi
- yet another attempt on Perft(14) by Ankan Banerjee, CCC, August 13, 2016
- Re: yet another attempt on Perft(14) by Ankan Banerjee, CCC, September 09, 2016
2017 ...
- Perft results? by notachessplayer, OpenChess Forum, January 01, 2017
- perft(15) by Ankan Banerjee, CCC, August 25, 2017 » Perft(15)
- 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
- No standard specification for Perft by Michael Sherwin, CCC, April 19, 2019
- You gotta love Perft... just not too much! by Martin Bryant, CCC, July 27, 2019
- Shogi Perft numbers by Toni Helminen, CCC, August 14, 2019 » Shogi
2020 ...
- Where to enter/read position into hash table in perft? by Marcel Vanthoor, CCC, March 28, 2020 » Transposition Table
- Count the number of nodes of perft(14) and beyond by Marc-Philippe Huget, CCC, April 04, 2020
- magic bitboard perft by Richard Delorme, CCC, April 11, 2020 » Magic Bitboards
External Links
- A048987 from On-Line Encyclopedia of Integer Sequences (OEIS)
- Statistics on chess games by François Labelle
- Performance testing from Wikipedia
- Distributed Perft Project (Wayback Machine)
Implementations
- µ-Max Dowload Page - qperft by Harm Geert Muller » Micro-Max
- ankan-ban/perft_gpu · GitHub [20]
- Auriga by Giuseppe Cannella [21]
- BBPerft: A fast, bitboard based chess perft result generator by Manik Charan derived from WyldChess
- Chess Engine OliThink - New Move Generator OliPerft (Pre OliThink 5) by Oliver Brausch » OliThink
- Crafty Command Documentation by Robert Hyatt, see perft <depth> » Crafty
- hqperft: Chess move generation based on (H)yperbola (Q)uintessence & range attacks by Richard Delorme » Hyperbola Quintessence
- perft, divide, debugging a move generator from ROCE by Roman Hartmann
- perft-random.epd by Marcel van Kervinck » Rookie
Video Tutorial
- A quick overview of the perft process by Jonathan Warkentin, YouTube Videos
- An example of debugging a perft error by Jonathan Warkentin, YouTube Videos
- Improving the perft speed & debugging tips by Jonathan Warkentin, YouTube Videos
References
- ↑ Written in Cobol - Program Written as Chess Buff's Research Aid by Brad Schultz, Computerworld, April 17, 1978, Page 37
- ↑ Perft(3) from 1978, with a twist! by Steven Edwards, CCC, December 08, 2011
- ↑ Re: Speed of Move Generator by Steven Edwards, rgcc, August 16, 1995
- ↑ Re: complete opening tree stats by Robert Hyatt, rgcc, February 05, 1998
- ↑ Distributed perft project by Albert Bertilsson, CCC, December 09, 2003
- ↑ Distributed Perft Project (Wayback Machine)
- ↑ A048987 from On-Line Encyclopedia of Integer Sequences (OEIS)
- ↑ Re: Perft(14) estimates thread by Peter Österlund, CCC, April 02, 2013
- ↑ MC methods by Daniel Shawul, CCC, April 11, 2013
- ↑ Daniel S. Abdi (2013). Monte carlo methods for estimating game tree size. pdf
- ↑ Re: yet another attempt on Perft(14) by Ankan Banerjee, CCC, September 09, 2016
- ↑ ankan-ban/perft_gpu · GitHub
- ↑ DGX-1 for AI Research | NVIDIA
- ↑ Re: Perft(15): comparison of estimates with Ankan's result by Ankan Banerjee, CCC, August 26, 2017
- ↑ Re: perft(15) by Ankan Banerjee, CCC, August 25, 2017
- ↑ Re: MC methods by Daniel Shawul, CCC, April 13, 2013
- ↑ Written in Cobol - Program Written as Chess Buff's Research Aid by Brad Schultz, Computerworld, April 17, 1978, Page 37
- ↑ ankan-ban/perft_gpu · GitHub
- ↑ Auriga by Giuseppe Cannella
- ↑ Fast perft on GPU (upto 20 Billion nps w/o hashing) by Ankan Banerjee, CCC, June 22, 2013
- ↑ Auriga - distributed and collaborative Perft by Giuseppe Cannella, CCC, November 28, 2015