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<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!
  
  **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<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 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
      }
  
  ```
  
  
  ---
  
  