Answers.Body: <p>Answering my own question here. I've managed to increase the speed of the move generation code, by implementing the <code>pinnedPices()</code> routine.</p>
  
  <p>The C++ version runs Perft (start_pos, 6) under ~3.5 secs, including hash updates.
  Here's some Java code for reference (messy indentation, sorry):</p>
  
  <pre><code>//return bitboard of pinned pieces for player side
  public static long pinnedBB(Board board, int side, int kingSQ){
      int opp =  side ^ 1;
      long occup = board.bitboards[side] | board.bitboards[opp];
      long pinned = 0L;
      long pinner = xrayRook(board, board.bitboards[side], 
              kingSQ, opp) &amp; (board.bitboards[Board.ROOK | opp] | board.bitboards[Board.QUEEN | opp]);
  
      while (pinner != 0) {
         int sq  = Long.numberOfTrailingZeros(pinner);
         pinned |= BitBoardGen.rectLookUp[sq][kingSQ] &amp; board.bitboards[side];
         pinner &amp;= pinner - 1;
      }
      pinner = xrayBishop(board, board.bitboards[side], 
          kingSQ, opp) &amp; (board.bitboards[Board.BISHOP | opp] | board.bitboards[Board.QUEEN | opp]);
  
      while (pinner != 0) {
         int sq  = Long.numberOfTrailingZeros(pinner);
         pinned |= BitBoardGen.rectLookUp[sq][kingSQ] &amp; board.bitboards[side];
         pinner &amp;= pinner - 1;
      }
      return pinned;
  }
  
  
  
    public static long xrayBishop(Board board, long blockers, int from, int side){
        int opp = side ^ 1;
        long occup = board.bitboards[side] | board.bitboards[opp];
        long attacks = bishopAttacks(board, occup, from, side);
         blockers &amp;= attacks;
         return attacks ^ bishopAttacks(board, occup ^ blockers, from, side);
   }
  
  
    public static long bishopAttacks(Board board, long occup, int from, int side){
      int opp = side ^ 1;
      long enemyOrEmpty = ~board.bitboards[side] &amp; ~board.bitboards[Board.KING | opp];
      long[] up_r = BitBoardGen.BITBOARD_DIRECTIONS[BitBoardGen.IDX_UP_RIGHT];
      long[] up_l = BitBoardGen.BITBOARD_DIRECTIONS[BitBoardGen.IDX_UP_LEFT];
      long[] down_r = BitBoardGen.BITBOARD_DIRECTIONS[BitBoardGen.IDX_DOWN_RIGHT];
      long[] down_l = BitBoardGen.BITBOARD_DIRECTIONS[BitBoardGen.IDX_DOWN_LEFT];
  
      long upward =  upwardAttackTargetsFrom(from, occup, up_r) | upwardAttackTargetsFrom(from, occup, up_l);
      long downward =  downwardAttackTargetsFrom(from, occup, down_r) | downwardAttackTargetsFrom(from, occup, down_l);
      return upward | downward;
  }
  </code></pre>
  
  <p>The <code>rectLookUp</code> matrix stores the pre-generated bitboards representing the squares between two given squares.</p>
  
  <p>Now, inside <code>moveGen()</code> you only need to test for illegal moves in these situations:</p>
  
  <p>a) ep capture   b) pinned piece    c) at check     d) king move</p>
  
  <p>Everything else will be legal, assuming your pseudo-legal generator is bug-free.
  You can improve it further for cases 'c'  and 'd' (checking only evasive moves for ex).</p>
  
  <p>Hope it helps someone, thanks!</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-28T21:24:27.727Z
Answers.LastActivityDate: 2016-10-28T23:08:46.303Z
Answers.LastEditDate: 2016-10-28T23:08:46.303Z
Answers.UserDisplayName: Fernando
Answers.Body: <p><strong>A:</strong> Let's use bishop for our example. <code>xrayBishopAttacks</code> works if we have the following position<a href="https://i.sstatic.net/pX5jR.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/pX5jR.png" alt="enter image description here"></a>:</p>
  
  <p>but it <strong>doesn't</strong> work if you have this:</p>
  
  <p><a href="https://i.sstatic.net/V8eT8.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/V8eT8.png" alt="enter image description here"></a></p>
  
  <p>The f3 knight is not pinned because there is something else behind it. <code>obstructed</code> takes this into consideration.</p>
  
  <p><strong>B:</strong> Once you get the pinned pieces, you can just do XAND to check if the piece you want to move is pinned. If it's pinned, you can't move it.</p>
  
  <p>************** <strong>EDIT</strong> **************</p>
  
  <p>You won't find <code>obstructed()</code> because it's just a pseudocode function. You're expected to implement pinning in <code>obstructed()</code> yourself.</p>
  
  <p>Forget the pseudocode, you should study Stockfish. Goto <a href="https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp" rel="nofollow noreferrer">https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp</a></p>
  
  <p>Find <code>bool Position::legal(Move m) const</code></p>
  
  <p>Check the following:</p>
  
  <pre><code>// A non-king move is legal if and only if it is not pinned or it
  // is moving along the ray towards or away from the king.
  return   !(pinned_pieces(us) &amp; from)
      ||  aligned(from, to_sq(m), square&lt;KING&gt;(us));
  </code></pre>
  
  <p>This is <strong>exactly</strong> what I'm talking about.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-25T12:34:28.993Z
Answers.Text: The problem is that I coudn't find the code for `obstructed()`, and regarding point B, what if I move the piece in the direction of the pin?
Answers.UserDisplayName: Fernando
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-25T14:16:28.920Z
Answers.Text: @Fernando For point B, the function `obstructed()` is supposed to handle that. Whoever wrote this was lazy to expand it.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-25T14:22:22.517Z
Answers.Text: @Fernando EDITED. Please take a look!
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-25T16:45:20.537Z
Answers.Text: So what obstructed do is to return true if all squares betwen A and B are empty?
Answers.UserDisplayName: Fernando
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-25T21:23:28.787Z
Answers.Text: I think I figured it out, `obstructed()` returns the bitboard value with bits between two given squares. So I'm going to use the 'rectangular lookup' described here https://chessprogramming.wikispaces.com/Square+Attacked+By#Obstructed. I'll update the post as soon as I solve it. Thanks!
Answers.UserDisplayName: Fernando
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-25T23:57:09.467Z
Answers.Text: @Fernando Keep us posted!
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-16T11:41:59.153Z
Answers.Text: Re B: you can move pinned pieces, just not off of the pin-plane.
Answers.UserDisplayName: Matt Parkins
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-25T10:40:07.413Z
Answers.LastActivityDate: 2016-10-25T14:22:10.300Z
Answers.LastEditDate: 2016-10-25T14:22:10.300Z
Answers.UserDisplayName: SmallChess
Body: <p>This post is a follow up of this one: <a href="https://chess.stackexchange.com/questions/15705/c-vs-java-engine-move-generation-performance/15713#15713">C++ vs Java Engine move generation performance</a></p>
  
  <p>My goal here is to improve the performance of my move generator, which finishes perft (start_pos, 6) in 8.5 secs.
  That's too slow for C++ code (the same Java code runs in 11 secs).</p>
  
  <p>The bottleneck is the check for validity, which in turn tests if the king is in check. This is running for every move,
  and given that most moves are legal, it's a total waste of time. As pointed out by Student T, we should restricted
  this test for king in check, pinned pieces and en passant captures.</p>
  
  <p>The king in check or walking to check cases are easy, this post is about pinned pieces  code.
  So, the <a href="https://chessprogramming.wikispaces.com/Checks+and+Pinned+Pieces+(Bitboards)" rel="nofollow noreferrer"> cpwiki code</a> goes like this:</p>
  
  <pre><code>pinned = 0;
  pinner = xrayRookAttacks(occupiedBB, ownPieces, squareOfKing) &amp; opRQ;
  while ( pinner ) {
     int sq  = bitScanForward(pinner);
     pinned |= obstructed(sq, squareOfKing) &amp; ownPieces;
     pinner &amp;= pinner - 1;
  }
  
  pinner = xrayBishopAttacks(occupiedBB, ownPieces, squareOfKing) &amp; opBQ;
  while ( pinner ) {
     int sq  = bitScanForward(pinner);
     pinned |= obstructed(sq, squareOfKing) &amp; ownPieces;
     pinner &amp;= pinner - 1;
  }
  </code></pre>
  
  <p>And here's the code for xrayRookAttacks():</p>
  
  <pre><code>U64 xrayRookAttacks(U64 occ, U64 blockers, enumSquare rookSq) {
     U64 attacks = rookAttacks(occ, rookSq);
     blockers &amp;= attacks;
     return attacks ^ rookAttacks(occ ^ blockers, rookSq);
  }
  </code></pre>
  
  <p><strong>Questions:</strong></p>
  
  <p>a) What is <code>obstructed()</code> doing?</p>
  
  <p>b) After getting the <code>pinned</code> set, how exactly do I use it to test for a valid move?</p>
  
  <p>Thank you all!</p>
  
Tags: <engines><programming><illegal-move><performance><pins>
Title: Detect pinned pieces code
ThreadText: # Detect pinned pieces code
  
  (Asked by: username_0 on 2016-10-24)
  
  This post is a follow up of this one: C++ vs Java Engine move generation performance
  My goal here is to improve the performance of my move generator, which finishes perft (start_pos, 6) in 8.5 secs.
  That's too slow for C++ code (the same Java code runs in 11 secs).
  The bottleneck is the check for validity, which in turn tests if the king is in check. This is running for every move,
  and given that most moves are legal, it's a total waste of time. As pointed out by Student T, we should restricted
  this test for king in check, pinned pieces and en passant captures.
  The king in check or walking to check cases are easy, this post is about pinned pieces  code.
  So, the  cpwiki code goes like this:
  pinned = 0;
  pinner = xrayRookAttacks(occupiedBB, ownPieces, squareOfKing) & opRQ;
  while ( pinner ) {
     int sq  = bitScanForward(pinner);
     pinned |= obstructed(sq, squareOfKing) & ownPieces;
     pinner &= pinner - 1;
  }
  
  pinner = xrayBishopAttacks(occupiedBB, ownPieces, squareOfKing) & opBQ;
  while ( pinner ) {
     int sq  = bitScanForward(pinner);
     pinned |= obstructed(sq, squareOfKing) & ownPieces;
     pinner &= pinner - 1;
  }
  
  And here's the code for xrayRookAttacks():
  U64 xrayRookAttacks(U64 occ, U64 blockers, enumSquare rookSq) {
     U64 attacks = rookAttacks(occ, rookSq);
     blockers &= attacks;
     return attacks ^ rookAttacks(occ ^ blockers, rookSq);
  }
  
  Questions:
  a) What is obstructed() doing?
  b) After getting the pinned set, how exactly do I use it to test for a valid move?
  Thank you all!
  
  **Tags:** engines, programming, illegal-move, performance, pins
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2016-10-25. Score: 5 | Accepted answer
  
  A: Let's use bishop for our example. xrayBishopAttacks works if we have the following position:
  but it doesn't work if you have this:
  
  The f3 knight is not pinned because there is something else behind it. obstructed takes this into consideration.
  B: Once you get the pinned pieces, you can just do XAND to check if the piece you want to move is pinned. If it's pinned, you can't move it.
  ************** EDIT **************
  You won't find obstructed() because it's just a pseudocode function. You're expected to implement pinning in obstructed() yourself.
  Forget the pseudocode, you should study Stockfish. Goto https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp
  Find bool Position::legal(Move m) const
  Check the following:
  // A non-king move is legal if and only if it is not pinned or it
  // is moving along the ray towards or away from the king.
  return   !(pinned_pieces(us) & from)
      ||  aligned(from, to_sq(m), square(us));
  
  This is exactly what I'm talking about.
  
  > **Comments:**
  > **username_0**: The problem is that I coudn't find the code for `obstructed()`, and regarding point B, what if I move the piece in the direction of the pin?  
  > **username_1**: @username_0 For point B, the function `obstructed()` is supposed to handle that. Whoever wrote this was lazy to expand it.  
  > **username_1**: @username_0 EDITED. Please take a look!  
  > **username_0**: So what obstructed do is to return true if all squares betwen A and B are empty?  
  > **username_0**: I think I figured it out, `obstructed()` returns the bitboard value with bits between two given squares. So I'm going to use the 'rectangular lookup' described here https://chessprogramming.wikispaces.com/Square+Attacked+By#Obstructed. I'll update the post as soon as I solve it. Thanks!  
  > **username_1**: @username_0 Keep us posted!  
  > **username_2**: Re B: you can move pinned pieces, just not off of the pin-plane.  
  
  ---
  
  ### Answer by username_0 on 2016-10-28. Score: 4
  
  Answering my own question here. I've managed to increase the speed of the move generation code, by implementing the pinnedPices() routine.
  The C++ version runs Perft (start_pos, 6) under ~3.5 secs, including hash updates.
  Here's some Java code for reference (messy indentation, sorry):
  //return bitboard of pinned pieces for player side
  public static long pinnedBB(Board board, int side, int kingSQ){
      int opp =  side ^ 1;
      long occup = board.bitboards[side] | board.bitboards[opp];
      long pinned = 0L;
      long pinner = xrayRook(board, board.bitboards[side], 
              kingSQ, opp) & (board.bitboards[Board.ROOK | opp] | board.bitboards[Board.QUEEN | opp]);
  
      while (pinner != 0) {
         int sq  = Long.numberOfTrailingZeros(pinner);
         pinned |= BitBoardGen.rectLookUp[sq][kingSQ] & board.bitboards[side];
         pinner &= pinner - 1;
      }
      pinner = xrayBishop(board, board.bitboards[side], 
          kingSQ, opp) & (board.bitboards[Board.BISHOP | opp] | board.bitboards[Board.QUEEN | opp]);
  
      while (pinner != 0) {
         int sq  = Long.numberOfTrailingZeros(pinner);
         pinned |= BitBoardGen.rectLookUp[sq][kingSQ] & board.bitboards[side];
         pinner &= pinner - 1;
      }
      return pinned;
  }
  
  
  
    public static long xrayBishop(Board board, long blockers, int from, int side){
        int opp = side ^ 1;
        long occup = board.bitboards[side] | board.bitboards[opp];
        long attacks = bishopAttacks(board, occup, from, side);
         blockers &= attacks;
         return attacks ^ bishopAttacks(board, occup ^ blockers, from, side);
   }
  
  
    public static long bishopAttacks(Board board, long occup, int from, int side){
      int opp = side ^ 1;
      long enemyOrEmpty = ~board.bitboards[side] & ~board.bitboards[Board.KING | opp];
      long[] up_r = BitBoardGen.BITBOARD_DIRECTIONS[BitBoardGen.IDX_UP_RIGHT];
      long[] up_l = BitBoardGen.BITBOARD_DIRECTIONS[BitBoardGen.IDX_UP_LEFT];
      long[] down_r = BitBoardGen.BITBOARD_DIRECTIONS[BitBoardGen.IDX_DOWN_RIGHT];
      long[] down_l = BitBoardGen.BITBOARD_DIRECTIONS[BitBoardGen.IDX_DOWN_LEFT];
  
      long upward =  upwardAttackTargetsFrom(from, occup, up_r) | upwardAttackTargetsFrom(from, occup, up_l);
      long downward =  downwardAttackTargetsFrom(from, occup, down_r) | downwardAttackTargetsFrom(from, occup, down_l);
      return upward | downward;
  }
  
  The rectLookUp matrix stores the pre-generated bitboards representing the squares between two given squares.
  Now, inside moveGen() you only need to test for illegal moves in these situations:
  a) ep capture   b) pinned piece    c) at check     d) king move
  Everything else will be legal, assuming your pseudo-legal generator is bug-free.
  You can improve it further for cases 'c'  and 'd' (checking only evasive moves for ex).
  Hope it helps someone, thanks!
  
  
  ---
  
  