Answers.Body: <p>Move generation has been tested to death in modern chess engines, and the current consensus is that the following two approaches are optimal for sliding pieces:</p>
  <ol>
  <li>A lookup table indexed by PEXT of the relevant occupancies (<a href="https://www.chessprogramming.org/BMI2#PEXTBitboards" rel="nofollow noreferrer">&quot;Fancy PEXT Bitboards&quot;</a>)</li>
  <li>A lookup table indexed by the higher order bits of the product of the Bitboard of relevant occupancies and a magic multiplier (<a href="https://www.chessprogramming.org/Magic_Bitboards" rel="nofollow noreferrer">&quot;Magic Bitboards&quot;</a>)</li>
  </ol>
  <p>Option 1 is preferred on CPUs which have a fast hardware PEXT (i.e. Intel Haswell and newer, no AMD CPUs at the time of writing). Otherwise, Option 2 is preferred.</p>
  <p>For example, stockfish offers bmi2 and popcnt builds: the former uses PEXT bitboards, the latter uses magic bitboards.</p>
  <h3>Kogge-stone</h3>
  <p>The Kogge-stone fill algorithm doesn't tend to be used in top engines for the simple reason that it benchmarks as being worse than the alternatives. I can offer a few reasons as to why this might be the case, but it is more important to recognise the fact that it <em>is</em> the case:</p>
  <ul>
  <li>They require a ludicrous number of CPU instructions. Each ray that must be cast (of which there are four) requires 5 shifts, 5 bitwise '&amp;'s, and 3 '|'s, while the lookup operations only require 3-5 instructions per slider.</li>
  <li>While Kogge-stone can in theory be vectorised, there tend to not be enough sliders on the board to take advantage of this. For example, there tend to only be 3 (or fewer) rook-like sliders on the board at any given time. This makes the parallelism not worth the speed tradeoff.</li>
  </ul>
  <h3> Actually improving move generation</h3>
  <p>A few things to note based on your code:</p>
  <ul>
  <li>Use <code>x &amp; (x - 1)</code> to clear the least significant bit: this is faster than <code>x &amp;= ~(1 &lt;&lt; from)</code></li>
  <li>Don't recompute the mask at every iteration: do it before the generation loop instead</li>
  <li>Use magic bitboards or PEXT bitboards: this is faster than Kogge-stone</li>
  <li>Make sure that hot move generation functions (like <code>GetRookMoves</code>) are inlined.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-03T00:51:34.673Z
Answers.Text: Thanks for your answer. I updated my code to use x & (x - 1) and I've switched to doing legal move generation instead of pseudo-legal (I'm convinced it's faster now). Although, I'm a bit confused by what you mean by don't recompute the mask at every iteration? Which mask? Also, I have made it a habit to inline every short function I write.
Answers.UserDisplayName: Noah Gavitt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-03T00:52:31.170Z
Answers.Text: Nevermind, I realize you mean the (empty | (turn ? bPiece : wPieces)) mask.
Answers.UserDisplayName: Noah Gavitt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-02T23:23:10.730Z
Answers.LastActivityDate: 2020-05-02T23:23:10.730Z
Answers.LastEditDate: 2020-06-17T09:59:59.497Z
Answers.UserDisplayName: konsolas
Body: <h2>Introduction</h2>
  <p>I'm in the process of rewriting my chess engine for better performance. I've started with the move generation function first. I've been looking at this person's article (<a href="https://peterellisjones.com/posts/generating-legal-chess-moves-efficiently/" rel="nofollow noreferrer">Their Article</a>) about generating moves quickly. At the bottom, they have their list of tips for better performance. They claim using these tips gives them about 100 million nodes per second from the starting position, while qperft (<a href="http://home.hccnet.nl/h.g.muller/dwnldpage.html" rel="nofollow noreferrer">qperft download</a>) does 190 million (qperft does 290 million on my pc). While the fastest I have gotten from my move generation function has been about 10 million nodes per second.</p>
  <h2>QPerft Output on my PC</h2>
  <pre><code>From the starting position.
  Quick Perft by H.G. Muller
  Perft mode: No hashing, bulk counting in horizon nodes
  
  perft( 1)=           20 ( 0.000 sec)
  perft( 2)=          400 ( 0.000 sec)
  perft( 3)=         8902 ( 0.000 sec)
  perft( 4)=       197281 ( 0.000 sec)
  perft( 5)=      4865609 ( 0.016 sec)
  perft( 6)=    119060324 ( 0.414 sec)
  
  119060324 / 0.414 ~= 290 million
  </code></pre>
  <h2>The Tips</h2>
  <ol>
  <li>Use SIMD instructions to do bitwise operations on multiple bitboards at the same time.</li>
  <li>Use Kogge-Stone Generators for calculating moves for multiple sliding pieces at the same time.</li>
  <li>Use the o^(o-2r) trick for calculating moves for single sliding pieces.</li>
  </ol>
  <h2>Problem</h2>
  <p>The problem I am having is I don't understand how to use these tips.</p>
  <h2>Problems with Tip #1</h2>
  <p>Their main tip for performance gain is to use SIMD (Single Instruction Multiple Data) instructions to do operations on multiple bitboards at the same time. The problem is I don't see how these are useful for generating moves. This is an example of how I've been generating moves (rooks for example).</p>
  <pre><code>Bitboard rooks = turn ? pieces[WROOK] : pieces[BROOK];
  Square from = 0, to = 0;
  
  while (rooks != 0) {
      _BitScanForward64(&amp;from, rooks);
      
      // GetRookMoves uses magic bitboards (a lookup table using the _pext_u64 instruction for speed).
      // As far as I am aware magic bitboards are faster than Kogge-Stone Generators.
      // &amp; (empty | (turn ? bPieces : wPieces) is to only get the moves that are on empty squares or capture squares.
      Bitboard rookMoves = GetRookMoves(start, full) &amp; (empty | (turn ? bPieces : wPieces));
      
      while (rookMoves != 0) {
          _BitScanForward64(&amp;to, rookMoves);
          
          // I am using a 32-bit integer to store all the information about the move
          moves[moveCount++] = /* move information (rook, from, to, etc...) */;
  
          // This is ofc to remove the move we have just looked at
          rookMoves &amp;= ~(ONE &lt;&lt; to);
      }
      
      // This is ofc to remove the rook we have just looked at
      rooks &amp;= ~(ONE &lt;&lt; from)
  }
  </code></pre>
  <p>I don't see where using SIMD instructions could help in this move generation function as I don't see any bitboard operations that can be done together. Am I missing some obvious way where using SIMD instructions would actually help or am I just doing the move generation wrong in the first place?</p>
  <h2>Problems with Tip #2</h2>
  <p>Their isn't much of a problem with tip #2. I am just wondering if magic bitboards are actually faster or if Kogge-Stone Generators with SIMD instructions are somehow faster. Also, Kogge-Stone is for calculating the moves for multiple sliding pieces at a time for legal move generation (I think). However, I am doing pseudo legal move generation because I think it is faster and easier.</p>
  <h2>Problems with Tip #3</h2>
  <p>The problem with tip #3 is the same as number 2. Isn't it faster to use magic bitboards?</p>
  
Tags: <engines><software><programming><performance>
Title: Chess Engine: Faster Move Generation
ThreadText: # Chess Engine: Faster Move Generation
  
  (Asked by: username_0 on 2020-05-01)
  
  ## Introduction
  
  I'm in the process of rewriting my chess engine for better performance. I've started with the move generation function first. I've been looking at this person's article ([Their Article](https://peterellisjones.com/posts/generating-legal-chess-moves-efficiently/)) about generating moves quickly. At the bottom, they have their list of tips for better performance. They claim using these tips gives them about 100 million nodes per second from the starting position, while qperft ([qperft download](http://home.hccnet.nl/h.g.muller/dwnldpage.html)) does 190 million (qperft does 290 million on my pc). While the fastest I have gotten from my move generation function has been about 10 million nodes per second.
  
  ## QPerft Output on my PC
  
  ```
  From the starting position.
  Quick Perft by H.G. Muller
  Perft mode: No hashing, bulk counting in horizon nodes
  
  perft( 1)=           20 ( 0.000 sec)
  perft( 2)=          400 ( 0.000 sec)
  perft( 3)=         8902 ( 0.000 sec)
  perft( 4)=       197281 ( 0.000 sec)
  perft( 5)=      4865609 ( 0.016 sec)
  perft( 6)=    119060324 ( 0.414 sec)
  
  119060324 / 0.414 ~= 290 million
  
  ```
  
  ## The Tips
  
  1. Use SIMD instructions to do bitwise operations on multiple bitboards at the same time.
  2. Use Kogge-Stone Generators for calculating moves for multiple sliding pieces at the same time.
  3. Use the o^(o-2r) trick for calculating moves for single sliding pieces.
  
  ## Problem
  
  The problem I am having is I don't understand how to use these tips.
  
  ## Problems with Tip #1
  
  Their main tip for performance gain is to use SIMD (Single Instruction Multiple Data) instructions to do operations on multiple bitboards at the same time. The problem is I don't see how these are useful for generating moves. This is an example of how I've been generating moves (rooks for example).
  
  ```
  Bitboard rooks = turn ? pieces[WROOK] : pieces[BROOK];
  Square from = 0, to = 0;
  
  while (rooks != 0) {
      _BitScanForward64(&from, rooks);
      
      // GetRookMoves uses magic bitboards (a lookup table using the _pext_u64 instruction for speed).
      // As far as I am aware magic bitboards are faster than Kogge-Stone Generators.
      // & (empty | (turn ? bPieces : wPieces) is to only get the moves that are on empty squares or capture squares.
      Bitboard rookMoves = GetRookMoves(start, full) & (empty | (turn ? bPieces : wPieces));
      
      while (rookMoves != 0) {
          _BitScanForward64(&to, rookMoves);
          
          // I am using a 32-bit integer to store all the information about the move
          moves[moveCount++] = /* move information (rook, from, to, etc...) */;
  
          // This is ofc to remove the move we have just looked at
          rookMoves &= ~(ONE << to);
      }
      
      // This is ofc to remove the rook we have just looked at
      rooks &= ~(ONE << from)
  }
  
  ```
  
  I don't see where using SIMD instructions could help in this move generation function as I don't see any bitboard operations that can be done together. Am I missing some obvious way where using SIMD instructions would actually help or am I just doing the move generation wrong in the first place?
  
  ## Problems with Tip #2
  
  Their isn't much of a problem with tip #2. I am just wondering if magic bitboards are actually faster or if Kogge-Stone Generators with SIMD instructions are somehow faster. Also, Kogge-Stone is for calculating the moves for multiple sliding pieces at a time for legal move generation (I think). However, I am doing pseudo legal move generation because I think it is faster and easier.
  
  ## Problems with Tip #3
  
  The problem with tip #3 is the same as number 2. Isn't it faster to use magic bitboards?
  
  **Tags:** engines, software, programming, performance
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-05-02. Score: 4
  
  Move generation has been tested to death in modern chess engines, and the current consensus is that the following two approaches are optimal for sliding pieces:
  
  1. A lookup table indexed by PEXT of the relevant occupancies (["Fancy PEXT Bitboards"](https://www.chessprogramming.org/BMI2#PEXTBitboards))
  2. A lookup table indexed by the higher order bits of the product of the Bitboard of relevant occupancies and a magic multiplier (["Magic Bitboards"](https://www.chessprogramming.org/Magic_Bitboards))
  
  Option 1 is preferred on CPUs which have a fast hardware PEXT (i.e. Intel Haswell and newer, no AMD CPUs at the time of writing). Otherwise, Option 2 is preferred.
  
  For example, stockfish offers bmi2 and popcnt builds: the former uses PEXT bitboards, the latter uses magic bitboards.
  
  ### Kogge-stone
  
  The Kogge-stone fill algorithm doesn't tend to be used in top engines for the simple reason that it benchmarks as being worse than the alternatives. I can offer a few reasons as to why this might be the case, but it is more important to recognise the fact that it *is* the case:
  
  * They require a ludicrous number of CPU instructions. Each ray that must be cast (of which there are four) requires 5 shifts, 5 bitwise '&'s, and 3 '|'s, while the lookup operations only require 3-5 instructions per slider.
  * While Kogge-stone can in theory be vectorised, there tend to not be enough sliders on the board to take advantage of this. For example, there tend to only be 3 (or fewer) rook-like sliders on the board at any given time. This makes the parallelism not worth the speed tradeoff.
  
  ### Actually improving move generation
  
  A few things to note based on your code:
  
  * Use `x & (x - 1)` to clear the least significant bit: this is faster than `x &= ~(1 << from)`
  * Don't recompute the mask at every iteration: do it before the generation loop instead
  * Use magic bitboards or PEXT bitboards: this is faster than Kogge-stone
  * Make sure that hot move generation functions (like `GetRookMoves`) are inlined.
  
  > **Comments:**
  > **username_0**: Thanks for your answer. I updated my code to use x & (x - 1) and I've switched to doing legal move generation instead of pseudo-legal (I'm convinced it's faster now). Although, I'm a bit confused by what you mean by don't recompute the mask at every iteration? Which mask? Also, I have made it a habit to inline every short function I write.  
  > **username_0**: Nevermind, I realize you mean the (empty | (turn ? bPiece : wPieces)) mask.  
  
  ---
  
  