Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Chess - Programming - Perft ======

**Perft**, standing for Performance Test, does a raw node count, up to some specified depth, by doing a full tree search.

  * By recording the amount of time taken to complete a Perft Test, it is possible to check the performance.

Draws by threefold repetition are ignored.

----

===== Perft Function =====

A simple perft function might look as follows:

<code cpp>
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]);
      nodes += Perft(depth - 1);
      UndoMove(move_list[i]);
  }
  
  return nodes;
}
</code>

----

===== Perft Values =====

==== Start Positition ====

Perft against normal opening position:

<code>
FEN-string: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
</code>

^Depth^Nodes^Captures^E.p.^Castles^Promotions^Checks^Checkmates^Total Nodes^
|1|20|0|0|0|0|0|0|20|
|2|400|0|0|0|0|0|0|420|
|3|8902|34|0|0|0|12|0|9322|
|4|197281|1576|0|0|0|469|8|206603|
|5|4865609|82719|258|0|0|27351|347|5072212|
|6|119060324|2812008|5248|0|0|798271|10828|124132536|
|7|3195901860|3320034396| | | |32668081|435767| |
|8|84998978956| | | | |959129557|9852036| |
|9|2439530234167| | | | |35695709940|400191963| |
|10|69352859712417| | | | |1078854669486|8790619155| |
|11|2097651003696806| | | | |39147687661803|1078854669486| |
|12|62,854,969,236,701,747| | | | |1224448528652016|8361091858959| |
|13|1,981,066,775,000,396,239| | | | | | | |

----

=== Checks ===

^Depth^Direct Check Only^Single Discovered Check Only^Direct and Discovered Checks^Double Discovered Checks^Total^
|1|0|0|0|0|0|
|2|0|0|0|0|0|
|3|12|0|0|0|12|
|4|461|0|0|0|461|
|5|26998|6|0|0|27004|
|6|797896|329|46|0|798271|
|7|32648427|18026|1628|0|32668081|
|8|958135303|847039|147215|0|959129557|
|9|35653060996|37101713|5547221|10|35695709940|
|10|1077020493859|1531274015|302900733|879|1078854669486|
|11|39068470901662|67494850305|11721852393|57443|39147687661803|
|12| | | | |1224448528652016|

<WRAP info>
**NOTE:** Definitions are:

  * **Direct Check**: When a piece which moved gives check.
    * A check given by one piece when another friendly piece moves out of the way. 
    * This excludes cases where the check happens because an enemy pawn gets captured En Passant.
  * **Discovered Check**: When a piece which didn't move gives check.
  * **Double Check**: When two pieces give check. Split into two categories: "direct and discovered check" and "double discovered check". 
    * A double check is a discovered check where the moving piece also gives check.
    * This definition excludes cases where a king is under two discovered attacks.
    * Also in general the expression "the moving piece" sounds awkward, because two pieces move during castling.

</WRAP>

----

=== Check Mates ===

^Depth^Direct Checkmate Only^Single Discovered Checkmate Only^Direct and Discovered Checkmate^Double Discovered Checkmate^Total^
|1|0|0|0|0|0|
|2|0|0|0|0|0|
|3|0|0|0|0|0|
|4|8|0|0|0|8|
|5|347|0|0|0|347|
|6|10828|0|0|0|10828|
|7|435767|0|0|0|435767|
|8|9852032|4|0|0|9852036|
|9|399421379|1869|768715|0|400191963|
|10|8771693969|598058|18327128|0|8790619155|
|11|360675926605|60344676|1553739626|0|362290010907|
|12| | | | |8361091858959|

----

==== Perft Estimates ====

^Depth^Nodes^
|13|1.9810e+18|
|14|6.187e+19|
|15|2.015e+21|
|16|6.507e+22|
|17|2.175e+24|
|18|7.214e+25|
|19|2.462e+27|
|20|8.350e+28|

<WRAP info>
**NOTE:** These estimates are done by randomly pruning the game tree.
</WRAP>


----

==== Good Test Position ====


The startposition is not a very good test position as it does not uncover flaws that might still be hidden regarding promotion or castling.

  * Therefore the following position should be a better test.

<code>
FEN-string: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1 
</code>

^Depth^Nodes^Captures^E.p.^Castles^Promotions^Checks^Checkmates^Total Nodes^
|1|48|8|0|2|0|0|0|48|
|2|2039|351|1|91|0|3|0|2087|
|3|97862|17102|45|3162|0|993|1|99949|
|4|4085603|757163|1929|128013|15172|25523|43|4185552|
|5|193690690|35043416|73365|4993637|8392|3309887|30171|197876242|
|6|8031647685| | | | | | |8229523927|

----

==== Discover promotion bugs ====

The following position does not look very realistic but nevertheless helps to uncover promotion bugs.

<code>
FEN-string: n1n5/PPPk4/8/8/8/8/4Kppp/5N1N b - - 0 1 
</code>

^Depth^Nodes^Total Nodes^
|1|24|24|
|2|496|520|
|3|9483|10003|
|4|182838|192841|
|5|3605103|3797944|
|6|71179139|74977083|

----

==== Position 1 ====

This position is very good because it catches many possible bugs:

<code>
Position r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
</code>

^Depth^Perft Value^
|1|48|
|2|2039|
|3|97862|
|4|4085603|
|5|193690690|
|6|8031647685|
</code>

----

==== Position 2 ====

<code>
FEN-string: 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -
</code>

^Depth^Nodes^Captures^E.p.^Castles^Promotions^Checks^Checkmates^Total Nodes^
|1|14|1|0|0|0|2|0|
|2|191|14|0|0|0|10|0|
|3|2812|209|2|0|0|267|0|
|4|43238|3348|123|0|0|1680|17|
|5|674624|52051|1165|0|0|52950|0|
|6|11030083|940350|33325|0|7552|452473|2733|
|7|178633661|14519036|294874|0|140024|12797406|87|

----

==== Position 3 ====

<code>
FEN-string: r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1

Or mirrored (with the same perft results):

FEN-string: r2q1rk1/pP1p2pp/Q4n2/bbp1p3/Np6/1B3NBn/pPPP1PPP/R3K2R b KQ - 0 1
</code>

^Depth^Nodes^Captures^E.p.^Castles^Promotions^Checks^Checkmates^Total Nodes^
|1|6|0|0|0|0|0| |
|2|264|87|0|6|48|10| |
|3|9467|1021|4|0|120|38| |
|4|422333|131393|0|7795|60032|15492| |
|5|15833292|2046173|6512|0|329464|200568| |
|6|706045033|210369132|212|10882006|81102984|26973664| |


----

===== A very interesting FEN =====

18 queens with only 6 captures:

<code>
k1qrq3/rq4Qq/3q1Q2/Q6q/3Q4/1Q4Q1/R1q1Q2Q/KQR2q1q/
</code>

----

===== Other FENs useful for finding bugs =====

<code>
Position 8/3K4/2p5/p2b2r1/5k2/8/8/1q6 b - 1 67
Perft(1) = 50
Perft(2) = 279

Position 8/7p/p5pb/4k3/P1pPn3/8/P5PP/1rB2RK1 b - d3 0 28
Perft(6) = 38633283

Position rnbqkb1r/ppppp1pp/7n/4Pp2/8/8/PPPP1PPP/RNBQKBNR w KQkq f6 0 3
Perft(5) = 11139762

Position 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -
Perft(6) = 11030083
Perft(7) = 178633661
</code>


----

==== References ====

http://web.archive.org/web/20120420061542/http://www.rocechess.ch/perft.html