Answers.Body: <p>Disclaimer: I can't support my claims with numbers. I don't have your engine to profile. It is mostly gut feelings.</p>
  
  <p>It looks like a performance killer is a castling test.</p>
  
  <p>Testing for <code>canCastle*S</code> (it <em>looks</em> like it is about King and Rook didn't move, and nothing is in between) is way cheaper than testing for King becoming exposed, so swap the tests order. C++ will short-circuit logical <code>and</code>.</p>
  
  <p>BTW, for castling you need to test against <code>inCheck</code> at three squares:</p>
  
  <pre><code>if (canCastleKS &amp;&amp; !inCheck(e_file) &amp;&amp; !inCheck(f_file) &amp;&amp; !inCheck(g_file)) {
      ....
  }
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-24T05:07:31.397Z
Answers.Text: This makes no sense because checking for castling is really just checking for the bitboard on the f1,g1,f8,g8,a8,b8,b1,c1 squares. This can be done quickly with bitboard AND. Furthermore, there're lots of positions this check is not even needed because 1: already castled 2: some pieces in the squares between.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-24T05:14:03.467Z
Answers.Text: @StudentT The positions where the check is not needed is exactly what I am talking about. OTOH I am not really sure that bitboard AND is cheap. OP said (and I have no reason to doubt it) that the bottleneck is in `atCheck`.
Answers.UserDisplayName: user58697
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-24T05:16:17.353Z
Answers.Text: In my answer, I also believed consistently checking for the king positions is a slowdown. However, I'm not sure it's related to castling. It's more to do that it's called for every move, even moves that can't possibly be illegal.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-24T12:26:05.403Z
Answers.Text: It´s not the castle test. The problem is checking for validity after every move, which in turn check for 'king in check' condition.
Answers.UserDisplayName: Fernando
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-24T04:57:50.690Z
Answers.LastActivityDate: 2016-10-24T04:57:50.690Z
Answers.UserDisplayName: user58697
Answers.Body: <p>Your code looks fine. We can't really give you the exact cause, but we can give you some hints.</p>
  
  <p><strong>Q: How did you generate sliding pieces?</strong></p>
  
  <p>Sliding piece generation is typically the slowest because we need to check the enemy pieces. Stockfish uses <strong>magic bitboard</strong>, which is also used by Houdini and Komodo.</p>
  
  <p><strong>Q: How did you generate legal moves?</strong></p>
  
  <p>Stockfish always generate <strong>pseudo-legal</strong> moves and <a href="https://stackoverflow.com/questions/7197369/chess-programming-no-ai-moves-validation/8589734#8589734">only check when it's necessary</a>.</p>
  
  <p><strong>Q: How did you undo your move?</strong></p>
  
  <p>Stockfish can easily undo a move by <strong>zorbrist hashing</strong>. Hash value can be updated efficiently.</p>
  
  <p>------------------------ <strong>EDIT</strong> ------------------------</p>
  
  <p>Your sliding generation and undo look okay to me. I think the bottleneck is your legal move generation. Look at this recent thread:</p>
  
  <p><a href="http://talkchess.com/forum/viewtopic.php?t=61797" rel="nofollow noreferrer">http://talkchess.com/forum/viewtopic.php?t=61797</a></p>
  
  <blockquote>
    <p>How do you ensure legality:<br>
    a) by making/unmaking each move and testing whether it leaves the king in check, or<br>
    b) by only doing this for the small set of moves that could actually be illegal (king moves, check evasions, ep captures, and moves of pinned pieces), or<br>
    c) by doing clever move generation that knows how to avoid generating illegal moves?<br>
    Only in case of a) I'd say you should spend effort to improve speed, since that could be done an order of magnitude faster, e.g. like b). Otherwise I'd keep it as it is, provided it is correct Smile</p>
  </blockquote>
  
  <p><strong>Sven Schule</strong> is a respected engine programmer, we should trust his words. Your implementation looks like <strong>exactly</strong> his point a.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-23T16:54:58.073Z
Answers.Text: Thanks, I've update the post with more info. I commented the `isAtCheck()` routine, the time went down to 6 secs, so I should improve on that. What do you mean by undo a move by zobrist hashing?
Answers.UserDisplayName: Fernando
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-24T04:39:50.880Z
Answers.Text: @Fernando Updated. Please take a look.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-24T12:30:52.093Z
Answers.Text: That´s it, if I disable the legality checks it runs perft (6) in 2 secs, Can you help me to implement pinned pieces detection? I didn't understand the cpwiki code for that.
Answers.UserDisplayName: Fernando
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-24T12:33:29.750Z
Answers.Text: @Fernando I think we should start a new question for it. Do you want to accept my answer and we can discuss with a new question? Other people can join too.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-24T13:31:24.377Z
Answers.Text: Here it is: http://chess.stackexchange.com/questions/15714/detect-pinned-pieces-code  Thanks!
Answers.UserDisplayName: Fernando
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2016-10-23T04:59:02.770Z
Answers.LastActivityDate: 2020-01-25T23:54:52.547Z
Answers.LastEditDate: 2020-01-25T23:54:52.547Z
Answers.UserDisplayName: SmallChess
Body: <p>I've just finished translating my Java Engine to C++11, expecting great speed improvements in move generation. The code is very straightforward and uses a pre-generate bitboards approach. I also generate only legal moves, ie, inside generateMoves() I check to see if the king is in check.</p>
  
  <p>As a quick test, I ran Perft (6) from the starting position. The Java version finishes the test on ~11 seconds. The C++ version takes ~8.5 seconds (my perft stops at depth 1, and zobrist keys are being updated on makeMove and undoMove).</p>
  
  <p>The same test on Stockfish runs under 1 second.</p>
  
  <p>I was expecting the C++ version to be at least twice as faster as the Java one, and of course, somewhat slower than Stockfish. </p>
  
  <p>After some investigation, it's clear that checking if the king is in check, for every move, is the major bottleneck. What can I do about this? I was trying to understand how to work with pinned pieces (<a href="https://chessprogramming.wikispaces.com/Checks+and+Pinned+Pieces+(Bitboards)" rel="nofollow">https://chessprogramming.wikispaces.com/Checks+and+Pinned+Pieces+(Bitboards)</a>), but I'm not sure how to follow. For example, what does <code>obstructed()</code> do in the link above?</p>
  
  <p>NOTE: I already compiled it with the -O2 optimization flag.</p>
  
  <p>EDIT: Here is some more details on the code:</p>
  
  <p><strong>Q: How did you generate sliding pieces?</strong></p>
  
  <p>I use the classfical bitboard approach, at program start I generate attack masks for all pieces:</p>
  
  <pre><code>void MoveGen::bishopMoves(Board&amp; board, int side, MoveList&amp; moves){
      int opp = side ^ 1;
      U64 bishops = board.bitboards[Board::BISHOP | side];
      U64 occup = board.bitboards[side] | board.bitboards[opp];
      U64 enemyOrEmpty = ~board.bitboards[side] &amp; ~board.bitboards[Board::KING | opp];
  
      U64 *up_r = BitBoardGen::BITBOARD_DIRECTIONS[BitBoardGen::IDX_UP_RIGHT];
      U64 *up_l = BitBoardGen::BITBOARD_DIRECTIONS[BitBoardGen::IDX_UP_LEFT];
      U64 *down_r = BitBoardGen::BITBOARD_DIRECTIONS[BitBoardGen::IDX_DOWN_RIGHT];
      U64 *down_l = BitBoardGen::BITBOARD_DIRECTIONS[BitBoardGen::IDX_DOWN_LEFT];
  
      while (bishops != 0){
          int from = numberOfTrailingZeros(bishops);
          U64 upward =  upwardMoveTargetsFrom(from, occup, up_r, enemyOrEmpty) | upwardMoveTargetsFrom(from, occup, up_l, enemyOrEmpty);
          U64 downward =  downwardMoveTargetsFrom(from, occup, down_r, enemyOrEmpty) | downwardMoveTargetsFrom(from, occup, down_l, enemyOrEmpty);
          add_moves(board, from, upward | downward, Move::NO_FLAGS, moves);
          bishops &amp;= bishops - 1;
      }
  }
  
   //handle blocking
  U64 MoveGen::upwardMoveTargetsFrom(int from, U64 occup, U64 dir_mask[], U64 enemyOrEmpty){
      U64 ray = dir_mask[from];
      U64 blocker = occup &amp; ray;
  
      if (blocker != 0){
          int sq = numberOfTrailingZeros(blocker);
          ray^= dir_mask[sq];
      } 
      return ray &amp; enemyOrEmpty;
  }
  </code></pre>
  
  <p><strong>Q: How did you generate legal moves?</strong></p>
  
  <p>I only generate legal moves, so I check if the king is in check while generating moves. This is probably one of the problems, since most moves don't leave the king in check.</p>
  
  <p>The generateAllMoves code:</p>
  
  <pre><code>MoveList genLegalMoves()
     valid = ()
     moves = getPseudoLegalForAllPieces (may leave the king in check)
     for move in moves
        board.applyMove(move) //its a local makemove, no zorbist involved
        atCheck = isAtCheck()  //dumb code, be more selective here?
        board.removeMove(move)//its a local undomove, no zorbist involved
  
        if !atCheck:
           valid.add(move)
  
    atCheck = isAtCheck() //again for castling
    if (! atCheck and canCastleKS)
       valid.add(castleKS)
    if (! atCheck and canCastleQS)
       valid.add(castleQS)
    return valid   
  </code></pre>
  
  <p><strong>Q: How did you undo your move?</strong></p>
  
  <p>My makeMove is like the following (this is fast):</p>
  
  <pre><code>int makeMove(int move):
      int undo = board.state
      incremental update zobrist key
      update board.board[]
      update board.bitboards
      update board.state
      return undo
  
  void undoMove(int move, int undo):
      board.state = undo
      incremental undo zobrist key
      update board.board[]
      update board.bitboards
  </code></pre>
  
  <p>And finally, my <code>isAtCheck()</code> code goes like:</p>
  
  <pre><code>boolean isAtCheck(int side):
      locate king square
      get all opponent attacks mask 
      return kingSquare &amp; attacksMask
  </code></pre>
  
  <p>EDIT 2: I have changed the code to a pseudo-legal generator. The problem now is that I have to go to depth 0 to count only legal moves, and now it's taking ~16 seconds.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-10-23T09:49:08.103Z
Comments.Text: In addition to -O2, you need -DNDEBUG to turn off those asserts.
Comments.UserDisplayName: Pete Becker
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-10-24T02:07:57.930Z
Comments.Text: Already did, I only have those 2 asserts, so no change in performance.
Comments.UserDisplayName: Fernando
Tags: <engines><stockfish><programming><performance>
Title: C++ vs Java Engine move generation performance
ThreadText: # C++ vs Java Engine move generation performance
  
  (Asked by: username_0 on 2016-10-23)
  
  I've just finished translating my Java Engine to C++11, expecting great speed improvements in move generation. The code is very straightforward and uses a pre-generate bitboards approach. I also generate only legal moves, ie, inside generateMoves() I check to see if the king is in check.
  
  As a quick test, I ran Perft (6) from the starting position. The Java version finishes the test on ~11 seconds. The C++ version takes ~8.5 seconds (my perft stops at depth 1, and zobrist keys are being updated on makeMove and undoMove).
  
  The same test on Stockfish runs under 1 second.
  
  I was expecting the C++ version to be at least twice as faster as the Java one, and of course, somewhat slower than Stockfish.
  
  After some investigation, it's clear that checking if the king is in check, for every move, is the major bottleneck. What can I do about this? I was trying to understand how to work with pinned pieces (<https://chessprogramming.wikispaces.com/Checks+and+Pinned+Pieces+(Bitboards)>), but I'm not sure how to follow. For example, what does `obstructed()` do in the link above?
  
  NOTE: I already compiled it with the -O2 optimization flag.
  
  EDIT: Here is some more details on the code:
  
  **Q: How did you generate sliding pieces?**
  
  I use the classfical bitboard approach, at program start I generate attack masks for all pieces:
  
  ```
  void MoveGen::bishopMoves(Board& board, int side, MoveList& moves){
      int opp = side ^ 1;
      U64 bishops = board.bitboards[Board::BISHOP | side];
      U64 occup = board.bitboards[side] | board.bitboards[opp];
      U64 enemyOrEmpty = ~board.bitboards[side] & ~board.bitboards[Board::KING | opp];
  
      U64 *up_r = BitBoardGen::BITBOARD_DIRECTIONS[BitBoardGen::IDX_UP_RIGHT];
      U64 *up_l = BitBoardGen::BITBOARD_DIRECTIONS[BitBoardGen::IDX_UP_LEFT];
      U64 *down_r = BitBoardGen::BITBOARD_DIRECTIONS[BitBoardGen::IDX_DOWN_RIGHT];
      U64 *down_l = BitBoardGen::BITBOARD_DIRECTIONS[BitBoardGen::IDX_DOWN_LEFT];
  
      while (bishops != 0){
          int from = numberOfTrailingZeros(bishops);
          U64 upward =  upwardMoveTargetsFrom(from, occup, up_r, enemyOrEmpty) | upwardMoveTargetsFrom(from, occup, up_l, enemyOrEmpty);
          U64 downward =  downwardMoveTargetsFrom(from, occup, down_r, enemyOrEmpty) | downwardMoveTargetsFrom(from, occup, down_l, enemyOrEmpty);
          add_moves(board, from, upward | downward, Move::NO_FLAGS, moves);
          bishops &= bishops - 1;
      }
  }
  
   //handle blocking
  U64 MoveGen::upwardMoveTargetsFrom(int from, U64 occup, U64 dir_mask[], U64 enemyOrEmpty){
      U64 ray = dir_mask[from];
      U64 blocker = occup & ray;
  
      if (blocker != 0){
          int sq = numberOfTrailingZeros(blocker);
          ray^= dir_mask[sq];
      } 
      return ray & enemyOrEmpty;
  }
  
  ```
  
  **Q: How did you generate legal moves?**
  
  I only generate legal moves, so I check if the king is in check while generating moves. This is probably one of the problems, since most moves don't leave the king in check.
  
  The generateAllMoves code:
  
  ```
  MoveList genLegalMoves()
     valid = ()
     moves = getPseudoLegalForAllPieces (may leave the king in check)
     for move in moves
        board.applyMove(move) //its a local makemove, no zorbist involved
        atCheck = isAtCheck()  //dumb code, be more selective here?
        board.removeMove(move)//its a local undomove, no zorbist involved
  
        if !atCheck:
           valid.add(move)
  
    atCheck = isAtCheck() //again for castling
    if (! atCheck and canCastleKS)
       valid.add(castleKS)
    if (! atCheck and canCastleQS)
       valid.add(castleQS)
    return valid   
  
  ```
  
  **Q: How did you undo your move?**
  
  My makeMove is like the following (this is fast):
  
  ```
  int makeMove(int move):
      int undo = board.state
      incremental update zobrist key
      update board.board[]
      update board.bitboards
      update board.state
      return undo
  
  void undoMove(int move, int undo):
      board.state = undo
      incremental undo zobrist key
      update board.board[]
      update board.bitboards
  
  ```
  
  And finally, my `isAtCheck()` code goes like:
  
  ```
  boolean isAtCheck(int side):
      locate king square
      get all opponent attacks mask 
      return kingSquare & attacksMask
  
  ```
  
  EDIT 2: I have changed the code to a pseudo-legal generator. The problem now is that I have to go to depth 0 to count only legal moves, and now it's taking ~16 seconds.
  
  **Tags:** engines, stockfish, programming, performance
  
  > **Comments:**
  > **username_1**: In addition to -O2, you need -DNDEBUG to turn off those asserts.  
  > **username_0**: Already did, I only have those 2 asserts, so no change in performance.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2016-10-23. Score: 4 | Accepted answer
  
  Your code looks fine. We can't really give you the exact cause, but we can give you some hints.
  
  **Q: How did you generate sliding pieces?**
  
  Sliding piece generation is typically the slowest because we need to check the enemy pieces. Stockfish uses **magic bitboard**, which is also used by Houdini and Komodo.
  
  **Q: How did you generate legal moves?**
  
  Stockfish always generate **pseudo-legal** moves and [only check when it's necessary](https://stackoverflow.com/questions/7197369/chess-programming-no-ai-moves-validation/8589734#8589734).
  
  **Q: How did you undo your move?**
  
  Stockfish can easily undo a move by **zorbrist hashing**. Hash value can be updated efficiently.
  
  ------------------------ **EDIT** ------------------------
  
  Your sliding generation and undo look okay to me. I think the bottleneck is your legal move generation. Look at this recent thread:
  
  <http://talkchess.com/forum/viewtopic.php?t=61797>
  
  > How do you ensure legality:  
  > a) by making/unmaking each move and testing whether it leaves the king in check, or  
  > b) by only doing this for the small set of moves that could actually be illegal (king moves, check evasions, ep captures, and moves of pinned pieces), or  
  > c) by doing clever move generation that knows how to avoid generating illegal moves?  
  > Only in case of a) I'd say you should spend effort to improve speed, since that could be done an order of magnitude faster, e.g. like b). Otherwise I'd keep it as it is, provided it is correct Smile
  
  **Sven Schule** is a respected engine programmer, we should trust his words. Your implementation looks like **exactly** his point a.
  
  > **Comments:**
  > **username_0**: Thanks, I've update the post with more info. I commented the `isAtCheck()` routine, the time went down to 6 secs, so I should improve on that. What do you mean by undo a move by zobrist hashing?  
  > **username_3**: @username_0 Updated. Please take a look.  
  > **username_0**: That´s it, if I disable the legality checks it runs perft (6) in 2 secs, Can you help me to implement pinned pieces detection? I didn't understand the cpwiki code for that.  
  > **username_3**: @username_0 I think we should start a new question for it. Do you want to accept my answer and we can discuss with a new question? Other people can join too.  
  > **username_0**: Here it is: http://chess.stackexchange.com/questions/15714/detect-pinned-pieces-code  Thanks!  
  
  ---
  
  ### Answer by username_2 on 2016-10-24. Score: 2
  
  Disclaimer: I can't support my claims with numbers. I don't have your engine to profile. It is mostly gut feelings.
  
  It looks like a performance killer is a castling test.
  
  Testing for `canCastle*S` (it *looks* like it is about King and Rook didn't move, and nothing is in between) is way cheaper than testing for King becoming exposed, so swap the tests order. C++ will short-circuit logical `and`.
  
  BTW, for castling you need to test against `inCheck` at three squares:
  
  ```
  if (canCastleKS && !inCheck(e_file) && !inCheck(f_file) && !inCheck(g_file)) {
      ....
  }
  
  ```
  
  > **Comments:**
  > **username_3**: This makes no sense because checking for castling is really just checking for the bitboard on the f1,g1,f8,g8,a8,b8,b1,c1 squares. This can be done quickly with bitboard AND. Furthermore, there're lots of positions this check is not even needed because 1: already castled 2: some pieces in the squares between.  
  > **username_2**: @StudentT The positions where the check is not needed is exactly what I am talking about. OTOH I am not really sure that bitboard AND is cheap. OP said (and I have no reason to doubt it) that the bottleneck is in `atCheck`.  
  > **username_3**: In my answer, I also believed consistently checking for the king positions is a slowdown. However, I'm not sure it's related to castling. It's more to do that it's called for every move, even moves that can't possibly be illegal.  
  > **username_0**: It´s not the castle test. The problem is checking for validity after every move, which in turn check for 'king in check' condition.  
  
  ---
  
  