Differences

This shows you the differences between two versions of the page.

--- chess:programming:perft [2021/10/12 09:03] – [Start Positition] peter
+++ chess:programming:perft [2021/10/12 10:27] (current) – peter
@@ Line 1: / Line 1: @@
 ====== Chess - Programming - Perft ======
-**Perft** does a raw node count, up to some specified depth, by doing a full tree search.
+**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>
 ----
@@ Line 23: / Line 53: @@
 |4|197281|1576|0|0|0|469|8|206603|
 |5|4865609|82719|258|0|0|27351|347|5072212|
-|6|119060324|2812008|5248|0|0|809099|10828|124132536|
+|6|119060324|2812008|5248|0|0|798271|10828|124132536|
 |7|3195901860|3320034396| | | |32668081|435767| |
 |8|84998978956| | | | |959129557|9852036| |
@@ Line 30: / Line 60: @@
 |11|2097651003696806| | | | |39147687661803|1078854669486| |
 |12|62,854,969,236,701,747| | | | |1224448528652016|8361091858959| |
+|13|1,981,066,775,000,396,239| | | | | | | |
 ----
-^Depth^Nodes^Captures^E.p.^Castles^Promotions^Checks^Single Discovered Check Only^Direct and Discovered Checks^Double Discovered Checks^Checkmates^Total Nodes^
+=== Checks ===
-|1|20|0|0|0|0|0|0|0|0|0|20|
-|2|400|0|0|0|0|0|0|0|0|0|420|
-|3|8902|34|0|0|0|12|0|0|0|12|9322|
-|4|197281|1576|0|0|0|469|8|0|0|461|206603|
-|5|4865609|82719|258|0|0|27351|347|0|0|27004|5072212|
-|6|119060324|2812008|5248|0|0|809099|10828|46|0|798271|124132536|
-|7|3195901860|3320034396| | | |32668081|435767|1628|0|32668081| |
-|8|84998978956| | | | |959129557|9852036|147215|0|959129557| |
-|9|2439530234167| | | | |35695709940|400191963|5547221|10|35695709940| |
-|10|69352859712417| | | | |1078854669486|8790619155|302900733|879|1078854669486| |
-|11|2097651003696806| | | | |39147687661803|1078854669486|11721852393|57443|39147687661803| |
-|12|62,854,969,236,701,747| | | | |1224448528652016| | | |8361091858959| |
+^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|
 ----
@@ Line 105: / Line 169: @@
 |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>
 ----
@@ Line 142: / Line 225: @@
 |5|15833292|2046173|6512|0|329464|200568| |
 |6|706045033|210369132|212|10882006|81102984|26973664| |
 ----
+===== A very interesting FEN =====
+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 ====