Validate Engine moves using Perft and divide I'm developing a small Engine in Java, before trying something more elaborate in C/C++. Right now I'm running some perft tests (the 'perf_talkchess' file), but as expected it has some bugs. Consider this position:

FEN r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1

[fen "r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1"]


I wrote the following perft method:

    public long perft(int depth){

        List&lt;Move&gt; moves = board.getAllMoves(board.state.currentPlayer);
        int n_moves = moves.size();
        long totalNodes = 0L;

        if (depth == 1){            
            return n_moves;
        }

        for (Move mv : moves){                      
            board.makeMove(mv);
            totalNodes += perft(depth - 1);         
            board.undoMove(mv);
        }
        return totalNodes;
    }


My perft (4) gives 1184480, it should be 1274206. In order to debug the position, I wrote this:

   public void divide(){

        List&lt;Move&gt; moves = board.getAllMoves(board.state.currentPlayer);

        for (Move m : moves){
            board.makeMove(m);
            //ignore the 0 arg
            Perft p = new Perft(board.toFEN(), depth, 0);
            p.run();
            board.undoMove(m);
            System.out.println(m + ":" + p.result);
            total += p.result;
        }
        System.out.println("Moves: " + moves.size());
        System.out.println("Total: " + total);
    }


When I run 

Divide d = new Divide("r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1", 3);
d.divide();


I got Moves: 26 Total: 1276215 and a very long output. I have 2 questions:

a) How do I properly write/use a divide algorithm?

b) How do I handle the castle state inside the make/unmake methods? What are the general traps to avoid regarding castle rights? I guess I'm screwing up the undo move code. What I do now is the following:

At makeMove I backup the current state before applying the move

makeMove(move)
  prevState.x = currentState.x
  prevState.y = currentState.y
  ...
  if (move.isFoo)
      change currentState accordingly
  ...


At undoMove I just restore the currentState and undo the board:

undoMove(move)
  currentState.x = prevState.x
  currentState.y = prevState.y
  ...
  if (move.isFoo)
      undo board state accordingly
  ...


Maybe there's some flaw with the reasoning above, I can post the code if necessary. Thanks!
Q1

I wouldn't code up a new divide function because if you have a bug in your code, your new function will also be buggy.

Why don't you use Stockfish? Do you know you can run perft on Stockfish?

In Stockfish, run the following:

position fen r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1
d
perft 3


You should get the following:

Position: 1/1
h2g1: 1160
h2g3: 1320
h2f4: 1444
....

===========================
Total time (ms) : 2
Nodes searched  : 27826
Nodes/second    : 13913000


Now you just need to add a std::cout to the perft function in search.cpp.

Find the function uint64_t Search::perft(Position&amp; pos, Depth depth) { in search.cpp, then use it to print out all the positions in your perft search.

You can then compare your perft moves with Stockfish with the following Unix commands:

sort MyPerftMoves &gt; MySortedPerftMoves
sort SFPerftMoves &gt; SFSortedPerftMoves
diff MySortedPerftMoves SFSortedPerftMoves


Q2

You should use Zobrist hashing if you haven't. This is the standard technique for board representation in chess. In Stockfish, the code below does the trick for castling:

// Update castling rights if needed
if (st-&gt;castlingRights &amp;&amp; (castlingRightsMask[from] | castlingRightsMask[to]))
{
    int cr = castlingRightsMask[from] | castlingRightsMask[to];
    k ^= Zobrist::castling[st-&gt;castlingRights &amp; cr];
    st-&gt;castlingRights &amp;= ~cr;
}


Your move representation should be able to tell you what castling move it is, and what castling rights (queen side? king side?) it has. This is implemented in Stockfish as castlingRightsMask[from] | castlingRightsMask[to]. Once you know your rights, you can just add it to your Zobrist key.