Answers.Body: <p><strong>Q1</strong></p>
  
  <p>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.</p>
  
  <p>Why don't you use Stockfish? Do you know you can run perft on Stockfish?</p>
  
  <p>In Stockfish, run the following:</p>
  
  <pre><code>position fen r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1
  d
  perft 3
  </code></pre>
  
  <p>You should get the following:</p>
  
  <pre><code>Position: 1/1
  h2g1: 1160
  h2g3: 1320
  h2f4: 1444
  ....
  
  ===========================
  Total time (ms) : 2
  Nodes searched  : 27826
  Nodes/second    : 13913000
  </code></pre>
  
  <p>Now you just need to add a std::cout to the perft function in <code>search.cpp</code>.</p>
  
  <p>Find the function <code>uint64_t Search::perft(Position&amp; pos, Depth depth) {</code> in <code>search.cpp</code>, then use it to print out all the positions in your perft search.</p>
  
  <p>You can then compare your perft moves with Stockfish with the following Unix commands:</p>
  
  <pre><code>sort MyPerftMoves &gt; MySortedPerftMoves
  sort SFPerftMoves &gt; SFSortedPerftMoves
  diff MySortedPerftMoves SFSortedPerftMoves
  </code></pre>
  
  <p><strong>Q2</strong></p>
  
  <p>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:</p>
  
  <pre><code>// 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;
  }
  </code></pre>
  
  <p>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 <code>castlingRightsMask[from] | castlingRightsMask[to]</code>. Once you know your rights, you can just add it to your Zobrist key.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-09-27T00:55:25.370Z
Answers.Text: Thanks for your answer, I've found the problem reading this http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=234006&t=25096. I'm certainly will be back here when I start to code an advanced engine, thanks!
Answers.UserDisplayName: Fernando
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-24T14:02:53.707Z
Answers.Text: Stockfish uses now `go perft 3` in stead.
Answers.UserDisplayName: andersfylling
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-09-26T01:56:54.703Z
Answers.LastActivityDate: 2016-09-26T04:26:53.343Z
Answers.LastEditDate: 2016-09-26T04:26:53.343Z
Answers.UserDisplayName: SmallChess
Answers.Body: <p>Just to answer my own question, the bug I had is better explained here:</p>
  
  <p><a href="http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&amp;p=234034&amp;t=25096" rel="nofollow">http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&amp;p=234034&amp;t=25096</a></p>
  
  <p>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:</p>
  
  <pre><code>1  e2-e4 a7-a6 
  2  e4-e5 d7-d5 // ep square created at d6 
  3  c2-c3 // ep square destroyed        
  4 ..c7-c6
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>BoardState makeMove(move)
  
      //currentState is a ivar
      freezeState = currentState.clone
  
      //update currentState, board, ep square and castle rights
      if (move.castle_ks &amp;&amp; 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
  </code></pre>
  
  <p>Now it works</p>
  
  <pre><code>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){                  
              BoardState undo = board.makeMove(mv);               
              totalNodes += perft(depth - 1);         
              board.undoMove(mv, undo);
          }
          return totalNodes;
  }
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-09-27T00:53:34.480Z
Answers.LastActivityDate: 2016-09-27T00:53:34.480Z
Answers.UserDisplayName: Fernando
Answers.Body: <p>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 &amp; unmaking moves, and testing equality later. (I override the copy constructor &amp; equality operator for my Board class)</p>
  
  <pre><code>#if VALIDATEBOARD
      Board boardControl(_board);
  #endif
  
  _board.PopulateMoveList(moveList, moveCount, oppositionAttackTable);
  
  for (int moveIndex = 0; moveIndex &lt; moveCount; moveIndex++) {
  
          _board.DoMove(moves[moveIndex]);
          // DO SOMETHING WITH MOVE
          _board.UndoMove();
  
  #if VALIDATEBOARD
          assert(_board == boardControl);
  #endif
      }
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-17T11:08:08.193Z
Answers.LastActivityDate: 2018-10-17T11:08:08.193Z
Answers.UserDisplayName: Matt Parkins
Body: <p>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:</p>
  
  <h3>FEN r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1</h3>
  
  <pre><code>[fen "r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1"]
  </code></pre>
  
  <p>I wrote the following perft method:</p>
  
  <pre><code>    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;
      }
  </code></pre>
  
  <p>My perft (4) gives 1184480, it should be 1274206. In order to debug the position, I wrote this:</p>
  
  <pre><code>   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);
      }
  </code></pre>
  
  <p>When I run </p>
  
  <pre><code>Divide d = new Divide("r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1", 3);
  d.divide();
  </code></pre>
  
  <p>I got <code>Moves: 26</code> <code>Total: 1276215</code> and a very long output. I have 2 questions:</p>
  
  <p>a) How do I properly write/use a divide algorithm?</p>
  
  <p>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:</p>
  
  <p>At makeMove I backup the current state before applying the move</p>
  
  <pre><code>makeMove(move)
    prevState.x = currentState.x
    prevState.y = currentState.y
    ...
    if (move.isFoo)
        change currentState accordingly
    ...
  </code></pre>
  
  <p>At undoMove I just restore the currentState and undo the board:</p>
  
  <pre><code>undoMove(move)
    currentState.x = prevState.x
    currentState.y = prevState.y
    ...
    if (move.isFoo)
        undo board state accordingly
    ...
  </code></pre>
  
  <p>Maybe there's some flaw with the reasoning above, I can post the code if necessary. Thanks!</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-09-26T03:19:03.830Z
Comments.Text: Who wrote the `Perft` class?
Comments.UserDisplayName: SmallChess
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-09-26T03:30:00.603Z
Comments.Text: I did, it's very straightforward. I've rewritten the make/unmake moves, now this position is solved, but I'm having trouble with a much more complex one. I'll edit the post, thanks.
Comments.UserDisplayName: Fernando
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-09-26T04:28:58.457Z
Comments.Text: Thanks for your edit. How would you handle multiple recursion in your undoMove? You aren't saving your current board to something like a stack or a hash table? When your function reaches depth==3, your current board would have been corrupted?
Comments.UserDisplayName: SmallChess
Tags: <engines><computer-chess><performance><perft>
Title: Validate Engine moves using Perft and divide
ThreadText: # Validate Engine moves using Perft and divide
  
  (Asked by: username_0 on 2016-09-25)
  
  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 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 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!
  
  **Tags:** engines, computer-chess, performance, perft
  
  > **Comments:**
  > **username_1**: Who wrote the `Perft` class?  
  > **username_0**: I did, it's very straightforward. I've rewritten the make/unmake moves, now this position is solved, but I'm having trouble with a much more complex one. I'll edit the post, thanks.  
  > **username_1**: Thanks for your edit. How would you handle multiple recursion in your undoMove? You aren't saving your current board to something like a stack or a hash table? When your function reaches depth==3, your current board would have been corrupted?  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2016-09-26. Score: 2 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_0**: Thanks for your answer, I've found the problem reading this http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=234006&t=25096. I'm certainly will be back here when I start to code an advanced engine, thanks!  
  > **username_2**: Stockfish uses now `go perft 3` in stead.  
  
  ---
  
  ### Answer by username_0 on 2016-09-27. Score: 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 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 by username_3 on 2018-10-17. Score: 1
  
  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
      }
  
  
  ---
  
  