Aart's Computer Reversi Page

Ongoing thoughts related to reversi programming can be found at Aart's blog. Excellent resources on reversi can be found at the Othello Wiki.

Perft for Reversi

The perft method originated in the chess programming community as a way to verify the move generator of an engine. The method traverses the game tree up to various, increasing depths to count all leaf nodes at each given depth. These results are compared with pre-computed values to isolate bugs and timings can be used to analyze the performance of the move generator. The perft method can be applied to other game engines as well, such as perft for checkers or, as done here, perft for reversi.

Pseudo-code for a reversi perft method is given below. Note that at the point marked with (*), neither player can move and the game is over. The implementation shown here includes such a higher leaf node in the perf count as well (in fact, a naive implementation that ignores game over situations would obtain the same count, as the players simply keep passing until a full-depth leaf node is reached). Alternatively, the code could return 0 to exclude higher leaf nodes in which the game is over, which would be closer the chess perft method, where higher leaf nodes are discarded (i.e. effectively only counting the number of move paths that reach the given depth).

int64 perft(int depth, boolean passed) {
  if (depth == 0) {
    return 1;  // at leaf node
  }
  int64 nodes = 0;
  generateMoves();
  if (num_moves == 0) {
    if (passed) { // both sides passed (game over)
      return 1;   // (*) see comment above
    }
    do_pass();
    nodes += perft(depth-1, true);
    undo_pass();
  } else {
    for (int i = 0; i < num_moves; i++) {
      do_move(i);
      nodes += perft(depth-1, false);
      undo_move(i);
    }
  }
  return nodes;
}

Below, some perft numbers for 8x8 reversi from the start position are given. At depths 9 and up, "passing" moves start to occur; at depths 11 and up, higher leaf nodes in which neither player can move start to occur. The table also shows the split of leaf nodes that reach full-depth or occur higher in the game tree.

 DEPTH  #LEAF NODES   #FULL-DEPTH  #HIGHER
==========================================
   1            4
   2           12
   3           56
   4          244
   5         1396
   6         8200
   7        55092
   8       390216
   9      3005288
  10     24571284
  11    212258800  =    212258572  +    228
  12   1939886636  =   1939886052  +    584
  13  18429641748  =  18429634780  +   6968 
  14 184042084512  = 184042061172  +  23340

Thanks to Jonathan Kreuzer (author of the excellent Pointy Stone application) for verifying my perft numbers.

Reversi for Android

Reversi for Android is a simple standalone reversi application that is available for free at the Android Market. It consists of a reversi engine together with a GUI. More information can be found at Aart's Android page.

Please note that this page is privately maintained by Aart Bik.