Validate Engine moves using Perft and divide

Question

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<Move> 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<Move> 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!

Answer 1

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& 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 > MySortedPerftMoves
sort SFPerftMoves > 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->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
{
    int cr = castlingRightsMask[from] | castlingRightsMask[to];
    k ^= Zobrist::castling[st->castlingRights & cr];
    st->castlingRights &= ~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.

Answer 2

Just to answer my own question, the bug I had is better explained here:

http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=234034&t=25096

My make/undo/perft code are correct, the problem was that the board state (castle rights and ep square) were being destroyed in the recursion. For example:

1  e2-e4 a7-a6 
2  e4-e5 d7-d5 // ep square created at d6 
3  c2-c3 // ep square destroyed        
4 ..c7-c6

Now when you undo the move c2-c3 the ep square at d6 is gone. The same happens for castle states. Some solutions are given in the link, I did the following:

BoardState makeMove(move)

    //currentState is a ivar
    freezeState = currentState.clone

    //update currentState, board, ep square and castle rights
    if (move.castle_ks && currentState.player == WHITE)
        currentState.white_castle_ks = false
        currentState.white_castle_qs = false
    else if (mv.pawnJump)
       currentState.epSquare = ...
    ...

    return freezeState

void undoMove(move, prevState)
    // undo state
    currentState.white_castle_ks = prevState.white_castle_ks
    currentState.white_castle_qs = prevState.white_castle_qs
    ...

   //undo board

Now it works

public long perft(int depth){

        List<Move> moves = board.getAllMoves(board.state.currentPlayer);
        int n_moves = moves.size();
        long totalNodes = 0L;

        if (depth == 1)                 
            return n_moves;     

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

Answer 3

Regarding B, the classic trap is not undoing all the changes one makes to the board in the unmake move. One thing that I do when debugging is to make a copy of the board before making & unmaking moves, and testing equality later. (I override the copy constructor & equality operator for my Board class)

#if VALIDATEBOARD
    Board boardControl(_board);
#endif

_board.PopulateMoveList(moveList, moveCount, oppositionAttackTable);

for (int moveIndex = 0; moveIndex < moveCount; moveIndex++) {

        _board.DoMove(moves[moveIndex]);
        // DO SOMETHING WITH MOVE
        _board.UndoMove();

#if VALIDATEBOARD
        assert(_board == boardControl);
#endif
    }