Answers.Body: <p>This appears fine to me. However, there are some things to note: </p>
  
  <p>1) Its important to be careful that you do not try playing the same move twice. Your "Storing in Move Generator" appears to accomplish this. </p>
  
  <p>2) It is generally a bad idea to save the SAME killer into multiple slots of your table. This reduces to effective size of your Killer Move table, and also makes it possible such that the following occurs: Your table contains {A, B, C, D} for a given depth. Move D is then found to refute 3 different lines of play (Awesome!), now your table contains {D, D, D, D}. If A, B, or C had any value, it is now lost.</p>
  
  <p>3) From personal experience, there is hardly any benefit to having more than two Killer moves for a given depth. In Ethereal, three-moves loses elo over two-moves, and two-moves is almost the same as one-move. I believe Stockfish uses two killers, although my information may be out of date.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-14T12:32:18.213Z
Answers.LastActivityDate: 2020-05-14T12:32:18.213Z
Answers.UserDisplayName: AndrewGrant
Body: <p>I implemented the killer move heuristic based on my understanding, but is it correct?<br/><br/>
  Inserting a killer move when a non-capture causes a beta cutoff (i is a Move pointer)</p>
  
  <pre><code>// Stuff
  if(val &gt;= beta){
          // Non capture move that causes a beta cutoff = Killer Move
          if(!GameObj.is_capture(*i, player))
              insert_killer(*i, depth);
          return beta;
      }
  </code></pre>
  
  <p>Actual Insertion By Shifting</p>
  
  <pre><code>void insert_killer(Move m, short depth){
  for(short i = 0; i &lt; KillerSize - 1; i++)
      // Shift the moves
      KillerMoves[depth][i] = KillerMoves[depth][i + 1];
  KillerMoves[depth][KillerSize - 1] = m;
  }
  </code></pre>
  
  <p>Storing in move generator</p>
  
  <pre><code>vector&lt;Move&gt; non_captures;
  vector&lt;Move&gt; captures;
  vector&lt;Move&gt; Killers;
  // Stuff
  if(!this-&gt;is_capture(move)){
      if (is_killer(depth, move))
          Killers.push_back(move);
      else
          non_captures.push_back(move);
  }
  // Stuff
  </code></pre>
  
  <p>Ordering in move generator</p>
  
  <pre><code>// Stuff
  vector&lt;Move&gt; all_moves;
  sort(captures.begin(), captures.end(), comparer);
  all_moves.reserve(captures.size() + non_captures.size() + Killers.size());
  all_moves.insert(all_moves.end(), captures.begin(), captures.end());
  if(!capture_only){
      all_moves.insert(all_moves.end(), Killers.begin(), Killers.end());
      all_moves.insert(all_moves.end(), non_captures.begin(), non_captures.end());
  }
  return all_moves;
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-06T10:55:21.427Z
Comments.Text: This question might be better suited for another community, like the Computer Science one. It involves code and optimizing the alpha-beta pruning algorithm, and there's not much that is chess specific.
Comments.UserDisplayName: Inertial Ignorance
Tags: <engines><programming>
Title: Is this implementation of Killer Move heuristic correct?
ThreadText: # Is this implementation of Killer Move heuristic correct?
  
  (Asked by: username_0 on 2020-05-05)
  
  I implemented the killer move heuristic based on my understanding, but is it correct?  
    
  Inserting a killer move when a non-capture causes a beta cutoff (i is a Move pointer)
  
  ```
  // Stuff
  if(val >= beta){
          // Non capture move that causes a beta cutoff = Killer Move
          if(!GameObj.is_capture(*i, player))
              insert_killer(*i, depth);
          return beta;
      }
  
  ```
  
  Actual Insertion By Shifting
  
  ```
  void insert_killer(Move m, short depth){
  for(short i = 0; i < KillerSize - 1; i++)
      // Shift the moves
      KillerMoves[depth][i] = KillerMoves[depth][i + 1];
  KillerMoves[depth][KillerSize - 1] = m;
  }
  
  ```
  
  Storing in move generator
  
  ```
  vector<Move> non_captures;
  vector<Move> captures;
  vector<Move> Killers;
  // Stuff
  if(!this->is_capture(move)){
      if (is_killer(depth, move))
          Killers.push_back(move);
      else
          non_captures.push_back(move);
  }
  // Stuff
  
  ```
  
  Ordering in move generator
  
  ```
  // Stuff
  vector<Move> all_moves;
  sort(captures.begin(), captures.end(), comparer);
  all_moves.reserve(captures.size() + non_captures.size() + Killers.size());
  all_moves.insert(all_moves.end(), captures.begin(), captures.end());
  if(!capture_only){
      all_moves.insert(all_moves.end(), Killers.begin(), Killers.end());
      all_moves.insert(all_moves.end(), non_captures.begin(), non_captures.end());
  }
  return all_moves;
  
  ```
  
  **Tags:** engines, programming
  
  > **Comments:**
  > **username_1**: This question might be better suited for another community, like the Computer Science one. It involves code and optimizing the alpha-beta pruning algorithm, and there's not much that is chess specific.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-05-14. Score: 2
  
  This appears fine to me. However, there are some things to note:
  
  1) Its important to be careful that you do not try playing the same move twice. Your "Storing in Move Generator" appears to accomplish this.
  
  2) It is generally a bad idea to save the SAME killer into multiple slots of your table. This reduces to effective size of your Killer Move table, and also makes it possible such that the following occurs: Your table contains {A, B, C, D} for a given depth. Move D is then found to refute 3 different lines of play (Awesome!), now your table contains {D, D, D, D}. If A, B, or C had any value, it is now lost.
  
  3) From personal experience, there is hardly any benefit to having more than two Killer moves for a given depth. In Ethereal, three-moves loses elo over two-moves, and two-moves is almost the same as one-move. I believe Stockfish uses two killers, although my information may be out of date.
  
  
  ---
  
  