Best way to debug perft?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Meni Rosenfeld
Posts: 10
Joined: Wed Mar 11, 2015 8:42 pm

Best way to debug perft?

Post by Meni Rosenfeld » Mon Jan 25, 2016 1:37 pm

An anecdote, and a question.

I had a bug in my move generating function. It was supposed to handle castling by examining a king move of two horizontal spaces (only if king never moved, not in check, and the square stepped over neither blocked nor threatened); then it was supposed to register it as a castle if the square is vacant, as are all the following squares up to a virgin rook.

But, due to incorrect branching logic, it skipped over the second half of the test if there is an opponent piece in the landing square. This allowed the king to capture two spaces horizontally in certain conditions.

This happens rarely, but it still created one extraneous line in perft(6) from starting position: 1. g3 d5 2. Bh3 Qd6 3. Bxc8 Kxc8

(I think it's interesting how only a single line creates this situation in depth 6. The black queen must move, but not block the white bishop; the black d pawn must move, but not block the queen; the white g pawn must move to release the bishop, but not block it later.)

Anyway, for my real question - the process from getting a wrong perft(6) result to finding the offending line was quite cumbersome for me. I used hgm's qperft with the command "perft 6 -2" to figure out the perft for each initial move, and compared it to my results (which required fiddling with a text editor and Excel to compare the numbers). Found that g3 has a discrepancy, and ran "perft 5 -2 FEN" with FEN being the code for the resulting board. Found the discrepancy and so on. By the time I got to searching for the bad 5th move, "perft 2 -2 FEN" no longer gave me a list of results per move, so I had to run perft on each possible move separately until I found the incorrect one.

So all in all doable, but I think it could have been much faster (and more fun) with a better tool. So, is there a better way to debug perft discrepancies?

I was thinking of a simple website or program with a graphical interface that allows you to either paste a FEN or choose from a few built-in test cases (like the ones on CPW). You also choose a depth and then it gives you a list of moves and their perft. You can also choose to have it sorted by perft for easy comparison. If you click on one of the moves (presumably, one that has a different perft from yours), you get the perft starting from it, and so on. This way you can quickly home in on the offending line(s).

Maybe it could also allow you to paste at every stage your own perft result, and it will automatically find the discrepancy.

Does such a tool exist? If not, is there demand for creating one?

User avatar
Evert
Posts: 2892
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Best way to debug perft?

Post by Evert » Mon Jan 25, 2016 1:58 pm

Meni Rosenfeld wrote: Anyway, for my real question - the process from getting a wrong perft(6) result to finding the offending line was quite cumbersome for me. I used hgm's qperft with the command "perft 6 -2" to figure out the perft for each initial move, and compared it to my results (which required fiddling with a text editor and Excel to compare the numbers). Found that g3 has a discrepancy, and ran "perft 5 -2 FEN" with FEN being the code for the resulting board. Found the discrepancy and so on. By the time I got to searching for the bad 5th move, "perft 2 -2 FEN" no longer gave me a list of results per move, so I had to run perft on each possible move separately until I found the incorrect one.
That's how I do it.
Not sure what you mean by 'By the time I got to searching for the bad 5th move, "perft 2 -2 FEN" no longer gave me a list of results per move', but that could just be because I'm unfamiliar with qperft. I always advance the position by one ply, then do a divided perft to a lower depth and compare results. This zooms in on the problematic position in 6 steps (at some point you need a list of legal moves in a given position, but that can be done by hand if necessary).
I was thinking of a simple website or program with a graphical interface that allows you to either paste a FEN or choose from a few built-in test cases (like the ones on CPW). You also choose a depth and then it gives you a list of moves and their perft. You can also choose to have it sorted by perft for easy comparison. If you click on one of the moves (presumably, one that has a different perft from yours), you get the perft starting from it, and so on. This way you can quickly home in on the offending line(s).

Maybe it could also allow you to paste at every stage your own perft result, and it will automatically find the discrepancy.

Does such a tool exist? If not, is there demand for creating one?
I don't know if it will be very useful, but it could be quite easily done, of course. This is the set of perft positions I use to debug my move generators (some of these are probably redundant), which also tells you very quickly where the problem is:

Code: Select all

typedef struct position_signature_t {
   const char *fen;
   int depth;
   uint64_t nodes;
} position_signature_t;

static position_signature_t perftests[] = {
   // Martin Sedlak's test positions
   // (http://www.talkchess.com/forum/viewtopic.php?t=47318)
   // avoid illegal ep
   { "3k4/3p4/8/K1P4r/8/8/8/8 b - - 0 1",         6, 1134888 },
   { "8/8/8/8/k1p4R/8/3P4/3K4 w - - 0 1",         6, 1134888 },
   { "8/8/4k3/8/2p5/8/B2P2K1/8 w - - 0 1",         6, 1015133 },
   { "8/b2p2k1/8/2P5/8/4K3/8/8 b - - 0 1",         6, 1015133 },
   // en passant capture checks opponent: 
   { "8/8/1k6/2b5/2pP4/8/5K2/8 b - d3 0 1",         6, 1440467 },
   { "8/5k2/8/2Pp4/2B5/1K6/8/8 w - d6 0 1",         6, 1440467 },
   // short castling gives check: 
   { "5k2/8/8/8/8/8/8/4K2R w K - 0 1",            6, 661072 },
   { "4k2r/8/8/8/8/8/8/5K2 b k - 0 1",            6, 661072 },
   // long castling gives check: 
   { "3k4/8/8/8/8/8/8/R3K3 w Q - 0 1",            6, 803711 },
   { "r3k3/8/8/8/8/8/8/3K4 b q - 0 1",            6, 803711 },
   // castling (including losing cr due to rook capture): 
   { "r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1",   4, 1274206 },
   { "r3k2r/7b/8/8/8/8/1B4BQ/R3K2R b KQkq - 0 1",    4, 1274206 },
   // castling prevented: 
   { "r3k2r/8/3Q4/8/8/5q2/8/R3K2R b KQkq - 0 1",   4, 1720476 },
   { "r3k2r/8/5Q2/8/8/3q4/8/R3K2R w KQkq - 0 1",   4, 1720476 },
   // promote out of check: 
   { "2K2r2/4P3/8/8/8/8/8/3k4 w - - 0 1",         6, 3821001 },
   { "3K4/8/8/8/8/8/4p3/2k2R2 b - - 0 1",         6, 3821001 },
   // discovered check: 
   { "8/8/1P2K3/8/2n5/1q6/8/5k2 b - - 0 1",         5, 1004658 },
   { "5K2/8/1Q6/2N5/8/1p2k3/8/8 w - - 0 1",         5, 1004658 },
   // promote to give check: 
   { "4k3/1P6/8/8/8/8/K7/8 w - - 0 1",            6, 217342 },
   { "8/k7/8/8/8/8/1p6/4K3 b - - 0 1",            6, 217342 },
   // underpromote to check: 
   { "8/P1k5/K7/8/8/8/8/8 w - - 0 1",            6, 92683 },
   { "8/8/8/8/8/k7/p1K5/8 b - - 0 1",            6, 92683 },
   // self stalemate: 
   { "K1k5/8/P7/8/8/8/8/8 w - - 0 1",            6, 2217 },
   { "8/8/8/8/8/p7/8/k1K5 b - - 0 1",            6, 2217 },
   // stalemate/checkmate: 
   { "8/k1P5/8/1K6/8/8/8/8 w - - 0 1",            7, 567584 },
   { "8/8/8/8/1k6/8/K1p5/8 b - - 0 1",            7, 567584 },
   // double check: 
   { "8/8/2k5/5q2/5n2/8/5K2/8 b - - 0 1",         4, 23527 },
   { "8/5k2/8/5N2/5Q2/2K5/8/8 w - - 0 1",         4, 23527 },

   // short castling impossible although the rook never moved away from its corner 
   { "1k6/1b6/8/8/7R/8/8/4K2R b K - 0 1", 5, 1063513 },
   { "4k2r/8/8/7r/8/8/1B6/1K6 w k - 0 1", 5, 1063513 },

   // long castling impossible although the rook never moved away from its corner 
   { "1k6/8/8/8/R7/1n6/8/R3K3 b Q - 0 1", 5, 346695 },
   { "r3k3/8/1N6/r7/8/8/8/1K6 w q - 0 1", 5, 346695 },

   // From the Wiki
   { "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -", 4, 4085603 },
   { "rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6", 3, 53392 },

   // Shortened form of the third position below
   { "8/7p/p5pb/4k3/P1pPn3/8/P5PP/1rB2RK1 b - d3 0 28", 4, 67197 },

   // Some FRC postions by Reinhard Scharnagl
   // (http://www.talkchess.com/forum/viewtopic.php?t=55274)
   // We have each of them twice, to get the number of moves at the root
   // correct too.
   { "r1k1r2q/p1ppp1pp/8/8/8/8/P1PPP1PP/R1K1R2Q w KQkq - 0 1", 1, 23 },
   { "r1k2r1q/p1ppp1pp/8/8/8/8/P1PPP1PP/R1K2R1Q w KQkq - 0 1", 1, 28 },
   { "8/8/8/4B2b/6nN/8/5P2/2R1K2k w Q - 0 1", 1, 34 },
   { "2r5/8/8/8/8/8/6PP/k2KR3 w K - 0 1", 1, 17 },
   { "4r3/3k4/8/8/8/8/6PP/qR1K1R2 w KQ - 0 1", 1, 19 },

   { "r1k1r2q/p1ppp1pp/8/8/8/8/P1PPP1PP/R1K1R2Q w KQkq - 0 1", 2, 522 },
   { "r1k2r1q/p1ppp1pp/8/8/8/8/P1PPP1PP/R1K2R1Q w KQkq - 0 1", 2, 738 },
   { "8/8/8/4B2b/6nN/8/5P2/2R1K2k w Q - 0 1", 2, 318 },
   { "2r5/8/8/8/8/8/6PP/k2KR3 w K - 0 1", 2, 242 },
   { "4r3/3k4/8/8/8/8/6PP/qR1K1R2 w KQ - 0 1", 2, 628 },

   { "r1k1r2q/p1ppp1pp/8/8/8/8/P1PPP1PP/R1K1R2Q w KQkq - 0 1", 5, 7096972 }, 
   { "r1k2r1q/p1ppp1pp/8/8/8/8/P1PPP1PP/R1K2R1Q w KQkq - 0 1", 5, 15194841 }, 
   { "8/8/8/4B2b/6nN/8/5P2/2R1K2k w Q - 0 1", 5, 3223406 }, 
   { "2r5/8/8/8/8/8/6PP/k2KR3 w K - 0 1", 5, 985298 }, 
   { "4r3/3k4/8/8/8/8/6PP/qR1K1R2 w KQ - 0 1", 5, 8992652 },

   // John Merlino's test positions, some of these take a long time, only do them
   // in debug mode.
#ifdef DEBUGMODE
   { "r3k2r/8/8/8/3pPp2/8/8/R3K1RR b KQkq e3 0 1", 6, 485647607 },
   { "r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1", 6, 706045033 },
   { "8/7p/p5pb/4k3/P1pPn3/8/P5PP/1rB2RK1 b - d3 0 28", 6, 38633283 },
   { "8/3K4/2p5/p2b2r1/5k2/8/8/1q6 b - - 1 67", 7, 493407574 },
   { "rnbqkb1r/ppppp1pp/7n/4Pp2/8/8/PPPP1PPP/RNBQKBNR w KQkq f6 0 3", 6, 244063299 },
   { "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -", 5, 193690690 },
   { "8/p7/8/1P6/K1k3p1/6P1/7P/8 w - -", 8, 8103790 },
   { "n1n5/PPPk4/8/8/8/8/4Kppp/5N1N b - -", 6, 71179139 },
   { "r3k2r/p6p/8/B7/1pp1p3/3b4/P6P/R3K2R w KQkq -", 6, 77054993 },

   { "8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -", 7, 178633661 },
   { "8/5p2/8/2k3P1/p3K3/8/1P6/8 b - -", 8, 64451405 },
   { "r3k2r/pb3p2/5npp/n2p4/1p1PPB2/6P1/P2N1PBP/R3K2R w KQkq -", 5, 29179893 },
#endif

   { NULL, 0, 0 }
};

elcabesa
Posts: 638
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Best way to debug perft?

Post by elcabesa » Mon Jan 25, 2016 2:03 pm

One way to simplify the search of bug in per ft is implementing the divide command. It's a modified perft that print the node count for each legal move in a position. You can find it in vajolet and other engine.

I don't know about a complete external tool

User avatar
cdani
Posts: 2037
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Best way to debug perft?

Post by cdani » Mon Jan 25, 2016 2:05 pm

Hi!
Many engines have a "divide" command, that can help a lot in those cases:

Code: Select all

Andscacs 0.85005 by Daniel Jose
divide 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
4865609
ms: 70  n/s: 69508700
Edit: Didn't seen Marco's post :-)
Last edited by cdani on Mon Jan 25, 2016 2:07 pm, edited 1 time in total.

Daniel Anulliero
Posts: 620
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: Best way to debug perft?

Post by Daniel Anulliero » Mon Jan 25, 2016 2:05 pm

Very cool tool here :
http://www.zipproth.de/jetchess/
bests
dany

Meni Rosenfeld
Posts: 10
Joined: Wed Mar 11, 2015 8:42 pm

Re: Best way to debug perft?

Post by Meni Rosenfeld » Mon Jan 25, 2016 3:00 pm

Evert wrote:Not sure what you mean by 'By the time I got to searching for the bad 5th move, "perft 2 -2 FEN" no longer gave me a list of results per move'
I was referring to the divide feature, and my issue seems indeed specific to qperft - it does offer a divide, but for some reason divide is not working with a depth of 2, so I have to try each move separately once I reach that point.
Daniel Anulliero wrote:Very cool tool here :
http://www.zipproth.de/jetchess/
Thanks! This indeed helps. However, it falls short of my ideal tool in that there seems to be no way to choose a move from the list and execute it. I would have to use an external tool to make the move and import the FEN. Still, it's an improvement over using command-line tools.

Daniel Anulliero
Posts: 620
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: Best way to debug perft?

Post by Daniel Anulliero » Mon Jan 25, 2016 3:17 pm

Meni Rosenfeld wrote:
Evert wrote:Not sure what you mean by 'By the time I got to searching for the bad 5th move, "perft 2 -2 FEN" no longer gave me a list of results per move'
I was referring to the divide feature, and my issue seems indeed specific to qperft - it does offer a divide, but for some reason divide is not working with a depth of 2, so I have to try each move separately once I reach that point.
Daniel Anulliero wrote:Very cool tool here :
http://www.zipproth.de/jetchess/
Thanks! This indeed helps. However, it falls short of my ideal tool in that there seems to be no way to choose a move from the list and execute it. I would have to use an external tool to make the move and import the FEN. Still, it's an improvement over using command-line tools.
You can make à move with winboard or arena and then copy paste the new Fen in Jet chess 😉

User avatar
stegemma
Posts: 830
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Contact:

Re: Best way to debug perft?

Post by stegemma » Mon Jan 25, 2016 5:53 pm

In the past I've simply embedded qperft code in my engine, so that I have called the qperft function at any node, to compare with mine perft count. This was useful to find some kind of bug. There must be a thread in this forum, on the way I've converted qperft from C to C++.

This solution could be the slowest but it worked, for me.
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

Meni Rosenfeld
Posts: 10
Joined: Wed Mar 11, 2015 8:42 pm

Re: Best way to debug perft?

Post by Meni Rosenfeld » Mon Jan 25, 2016 10:23 pm

stegemma wrote:In the past I've simply embedded qperft code in my engine, so that I have called the qperft function at any node, to compare with mine perft count. This was useful to find some kind of bug. There must be a thread in this forum, on the way I've converted qperft from C to C++.

This solution could be the slowest but it worked, for me.
Is there some perft implementation in C# I can use?

jwes
Posts: 772
Joined: Sat Jul 01, 2006 5:11 am

Re: Best way to debug perft?

Post by jwes » Mon Jan 25, 2016 11:33 pm

I don't think there is such a tool, but I would like someone to write it. Perhaps it could be added to winboard or written using the pythonchess library.

The way I see it working is that one would configure two engines, a known good engine and the one to test. An epd file would be loaded and divide would be run to depth n on both engines for each position. The results would be compared and if there is a difference in counts for a move, that move would be made and divide would be run to depth n-1 on both engines for that position. This would be repeated until there is a move on one list that is not on the other or the results are the same.

Post Reply