Answers.Body: <p>8 seconds for perft(6) is alright - and move generation is not particularly important in the grand scheme of things. There are 3000+ chess engines with perft speed around the same speed as yours. Move generation usually only takes around 10% of the time. Evaluation, pruning and move ordering are all significantly more important factors.</p>
  <p>However, one of the best things you can do to improve perft speed is to get rid of branched code. This does two things: First, branching is inherently slow, and the reason is somewhat complex but you can read about it <a href="https://stackoverflow.com/questions/9820319/why-is-a-cpu-branch-instruction-slow#:%7E:text=On%20a%20conditional%20branch%2C%20it,lowers%20utilisation%2C%20and%20therefore%20performance.">here</a>. In addition, Rust's compiler automatically &quot;vectorizes&quot; code, i.e. takes sequential code and &quot;parallelizes&quot; it. Again, a complicated topic, but you can read about it <a href="https://en.wikipedia.org/wiki/Automatic_vectorization" rel="nofollow noreferrer">here</a>. This results in a huge speed boost sometimes (and is partially the reason why the linter recommends iterating over a list by value, as it is able to very easily autovectorize it). However, branched code makes it significantly harder for the compiler to identify potential places to autovectorize.</p>
  <p>So, instead of using</p>
  <pre><code>if to_move == 0 {
      2
  } else if to_move == 1 {
      5
  } else {
      panic!(&quot;Invalid color!&quot;)
  }
  </code></pre>
  <p>use</p>
  <pre><code>const FOO: [u8; 2] = [2, 5];
  FOO[to_move as usize]
  </code></pre>
  <p>Finally, use a profiler! find out what parts of your code are slow and speed them up</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-30T01:51:52.140Z
Answers.LastActivityDate: 2022-11-30T01:51:52.140Z
Answers.UserDisplayName: AAce3
Body: <p>I'm building a toy chess engine. I have a <em>correct</em> but <em>slow</em> move generation. Doing perft on starting position to depth 6 with my engine takes 8 seconds and but takes stockfish 0.5 seconds on my computer. So that's an order of magnitude difference.</p>
  <p>I'd like to exposit the algorithms I've used so far to see if anyone can spot any obvious problems. How I've implemented move generation so far:</p>
  <ul>
  <li>Rust as programming language, so there should be little/no language overhead</li>
  <li>Bitboard representation with u64 for each piece type, white occupancy, black occupancy, board occupancy</li>
  <li>Non-sliding pieces uses look-up table to find attack mask</li>
  <li>Sliding pieces uses look-up tables generated through magic bitboards</li>
  <li>Moves are generated by piece type
  <ul>
  <li>pseudo-legal style -- I check for king-check during the make-move stage</li>
  <li>For each piece type, loop through the LSBs (<code>x &amp; -x</code>) of the bitboard</li>
  <li>Obtain the attack mask and generate a move structure (32-bits in size)</li>
  <li>Do this for all the piece types</li>
  <li>Generate move for enpassant if applicable</li>
  <li>Generate the moves for castling if applicable</li>
  <li>To elaborate, e.g. for the start position, the pawn bitboard has 8 bits set and I iterate through them to generate the 16 pawn moves.</li>
  </ul>
  </li>
  <li>For <code>make_move</code>
  <ul>
  <li>The move structure distinguishes between castling, enpassant, promotion, normal move so make_move is more efficient, no hunting through bitboards to see what type of move it is</li>
  <li>Do the bit operations needed to update the bitboards</li>
  <li>After doing <code>make_move</code> check if king is in check, and dispose move if it is</li>
  </ul>
  </li>
  <li>There is little/no dynamic memory allocation during the movegen/makemove process because I implement these using iterators, which incurs very little overhead in Rust. Almost all operations are on the stack.</li>
  <li>I've also tried zobrist hash generation, which also works properly according to Perft numbers. For the caching, I use a hash map with <code>(hash, depth)</code> as the key and <code>count</code> as the value, so the same position at the same depth is not calculated twice. This does not seem to make much difference in the performance.</li>
  </ul>
  <p>I can see that data structure improvements might make it a bit faster, or optimize for hardware instructions, but to observe more than an order of magnitude difference in speed, I must be using inferior algorithms. But none of my reading points to the answer.</p>
  <p>I'm happy to elaborate on anything else I've missed. Is there anything obvious in these algorithms that I can be doing instead?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-11-25T09:34:41.263Z
Comments.Text: If you haven't already done it, I'd consider posting this question on this forum: http://talkchess.com/forum3/viewforum.php?f=7
Comments.UserDisplayName: emdio
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-11-25T15:25:30.653Z
Comments.Text: I am not a chess engine expert but you might gain some information if you use a code performance analyzer thing which shows which part of the code takes most of the time. I don't know if there is something like that for Rust but I remember using something like that on Visual Studio with C++. It shows which functions or which loops take how much CPU/GPU and how much time.
Comments.UserDisplayName: Minot
Tags: <engines><programming>
Title: Factors that contribute to slow move generation in building chess engine
ThreadText: # Factors that contribute to slow move generation in building chess engine
  
  (Asked by: username_0 on 2022-11-25)
  
  I'm building a toy chess engine. I have a *correct* but *slow* move generation. Doing perft on starting position to depth 6 with my engine takes 8 seconds and but takes stockfish 0.5 seconds on my computer. So that's an order of magnitude difference.
  
  I'd like to exposit the algorithms I've used so far to see if anyone can spot any obvious problems. How I've implemented move generation so far:
  
  * Rust as programming language, so there should be little/no language overhead
  * Bitboard representation with u64 for each piece type, white occupancy, black occupancy, board occupancy
  * Non-sliding pieces uses look-up table to find attack mask
  * Sliding pieces uses look-up tables generated through magic bitboards
  * Moves are generated by piece type
    + pseudo-legal style -- I check for king-check during the make-move stage
    + For each piece type, loop through the LSBs (`x & -x`) of the bitboard
    + Obtain the attack mask and generate a move structure (32-bits in size)
    + Do this for all the piece types
    + Generate move for enpassant if applicable
    + Generate the moves for castling if applicable
    + To elaborate, e.g. for the start position, the pawn bitboard has 8 bits set and I iterate through them to generate the 16 pawn moves.
  * For `make_move`
    + The move structure distinguishes between castling, enpassant, promotion, normal move so make\_move is more efficient, no hunting through bitboards to see what type of move it is
    + Do the bit operations needed to update the bitboards
    + After doing `make_move` check if king is in check, and dispose move if it is
  * There is little/no dynamic memory allocation during the movegen/makemove process because I implement these using iterators, which incurs very little overhead in Rust. Almost all operations are on the stack.
  * I've also tried zobrist hash generation, which also works properly according to Perft numbers. For the caching, I use a hash map with `(hash, depth)` as the key and `count` as the value, so the same position at the same depth is not calculated twice. This does not seem to make much difference in the performance.
  
  I can see that data structure improvements might make it a bit faster, or optimize for hardware instructions, but to observe more than an order of magnitude difference in speed, I must be using inferior algorithms. But none of my reading points to the answer.
  
  I'm happy to elaborate on anything else I've missed. Is there anything obvious in these algorithms that I can be doing instead?
  
  **Tags:** engines, programming
  
  > **Comments:**
  > **username_1**: If you haven't already done it, I'd consider posting this question on this forum: http://talkchess.com/forum3/viewforum.php?f=7  
  > **username_2**: I am not a chess engine expert but you might gain some information if you use a code performance analyzer thing which shows which part of the code takes most of the time. I don't know if there is something like that for Rust but I remember using something like that on Visual Studio with C++. It shows which functions or which loops take how much CPU/GPU and how much time.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2022-11-30. Score: 1 | Accepted answer
  
  8 seconds for perft(6) is alright - and move generation is not particularly important in the grand scheme of things. There are 3000+ chess engines with perft speed around the same speed as yours. Move generation usually only takes around 10% of the time. Evaluation, pruning and move ordering are all significantly more important factors.
  However, one of the best things you can do to improve perft speed is to get rid of branched code. This does two things: First, branching is inherently slow, and the reason is somewhat complex but you can read about it here. In addition, Rust's compiler automatically "vectorizes" code, i.e. takes sequential code and "parallelizes" it. Again, a complicated topic, but you can read about it here. This results in a huge speed boost sometimes (and is partially the reason why the linter recommends iterating over a list by value, as it is able to very easily autovectorize it). However, branched code makes it significantly harder for the compiler to identify potential places to autovectorize.
  So, instead of using
  if to_move == 0 {
      2
  } else if to_move == 1 {
      5
  } else {
      panic!("Invalid color!")
  }
  
  use
  const FOO: [u8; 2] = [2, 5];
  FOO[to_move as usize]
  
  Finally, use a profiler! find out what parts of your code are slow and speed them up
  
  
  ---
  
  