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:

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;
}

Perft Values

Start Positition

Perft against normal opening position:

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

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

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.

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

NOTE: These estimates are done by randomly pruning the game tree.

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.

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

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.

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

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:

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

Depth	Perft Value
1	48
2	2039
3	97862
4	4085603
5	193690690
6	8031647685

</code>

Position 2

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

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

Position 3

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

Depth	Nodes	Captures	E.p.	Castles	Promotions	Checks
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:

k1qrq3/rq4Qq/3q1Q2/Q6q/3Q4/1Q4Q1/R1q1Q2Q/KQR2q1q/

Other FENs useful for finding bugs

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

References

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

Wiki

Table of Contents