Perft and mate

[stegemma]

Me too at start i have implemented the full nodes count and then i've changed so that the count match the way that Crafty does. Maybe could be interesting to have perft that gives two values: the nodes count at ply N and the full nodes count, up to ply N?

[abik]

In chess, a concise recursive implementation of perft() lends itself more naturally to skip higher leaf nodes (viz. for an internal mate, num_moves == 0, so the recursion is skipped, and the return value is zero).

Code: Select all

int64 perft(int depth) {
  if (depth == 0)  return 1;  // at leaf node
  int64 nodes = 0;
  int num_moves = generateMoves();
  for &#40;int i = 0; i < num_moves; i++) &#123;
    do_move&#40;i&#41;;
    nodes += perft&#40;depth-1, false&#41;;
    undo_move&#40;i&#41;;
  &#125;
  return nodes;
&#125;

If you want to *include* higher leaf nodes, an extra statement would be required (note that it would be wrong to initialize nodes with 1 since that would give an incorrect result when num_moves is nonzero!):

Code: Select all

if (num_moves == 0)
  return 1;

When I implemented perf for Reversi to verify a move generator for that game, this choice became more explicit, since the game allows for a situation without moves (where the player must pass, and the game is only over if *both* sides cannot move anymore). Here counting internal leaf nodes seems more intuitive, but skipping them (effectively only counting the number of move paths that reach the given depth) would be closer to chess perf. Since I could not find any prior perft for Reversi that favored one method over the other, I decided to simply report both numbers (see http://othello.dk/book/index.php/Aart_Bik).

Code: Select all

int64 perft(int depth, boolean passed) {
  if (depth == 0) {
    return 1;  // at leaf node
  }
  int64 nodes = 0;
  int num_moves = generateMoves();
  if (num_moves == 0) {
    if (passed) { // both sides passed (game over)
      return 1;   // choice between returning 1 (seems more natural for Reversi)
                   //   or returning 0 (more like chess perft by counting move paths up to given depth)
    }
    do_pass();
    nodes += perft(depth-1, true);
    undo_pass();
  } else {
    for &#40;int i = 0; i < num_moves; i++) &#123;
      do_move&#40;i&#41;;
      nodes += perft&#40;depth-1, false&#41;;
      undo_move&#40;i&#41;;
    &#125;
  &#125;
  return nodes;
&#125;

[Sven]

In chess, a concise recursive implementation of perft() lends itself more naturally to skip higher leaf nodes (viz. for an internal mate, num_moves == 0, so the recursion is skipped, and the return value is zero).

Code: Select all

int64 perft(int depth) {
  if (depth == 0)  return 1;  // at leaf node
  int64 nodes = 0;
  int num_moves = generateMoves();
  for &#40;int i = 0; i < num_moves; i++) &#123;
    do_move&#40;i&#41;;
    nodes += perft&#40;depth-1, false&#41;;
    undo_move&#40;i&#41;;
  &#125;
  return nodes;
&#125;

In this version you mean "nodes += perft(depth-1);" in line 7, of course. The second parameter belongs to your second paragraph.

Just a note: your version of generateMoves() has to return 0 in case of mate or draw. Otherwise code for mate/draw detection would have to be added prior to generateMoves(), like: "if (isMate() || isDraw()) return 0; // premature leaf node, not counted". Personally I would even prefer the latter, since I could use the same generateMoves() function as for the regular search where I would not like to include mate or draw detection code within generateMoves().

Also handling of illegal moves has to be added if generateMoves() produces pseudo-legal moves only.

Sven

[abik]

The second parameter belongs to your second paragraph.

Ah, thanks for noticing this sloppy copy-and-paste error. As for your other comments, the move generator in this pseudo-code obviously yields legal moves only and returns 0 for mate and stalemate (other forms of draws are ignored in perft afaik). As for all pseudo-code, your implementation mileage may vary.