Answers.Body: <p>Your algorithm seems very wrong to me for SEE. It appears much closer to Quiescence Search instead.</p>
  
  <ul>
  <li>SEE is an unary tree. After finding a legal move, the SEE function returns. It doesn't need to check all possible moves for the best one; just one.</li>
  <li>You sort your moves in MVV/LVA order. Your ordering should just be on the least valuable attacking piece.</li>
  <li>You search all possible moves. SEE only searches captures on a square.</li>
  </ul>
  
  <p>To answer your question of:</p>
  
  <blockquote>
    <p>what to return "in check"</p>
  </blockquote>
  
  <p>SEE doesn't actually care about check. If you capture with your king and the opponent can capture with anything, then the value of the king should be large enough that <code>Math.max(0, evalPiece(foo.captured) - _see(sq, tfen, depth + 1, maxDepth, -color, chess))</code> has a greater score for not capturing with your king than capturing the king.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-07-31T16:15:32.480Z
Answers.LastActivityDate: 2016-07-31T16:15:32.480Z
Answers.UserDisplayName: ZirconiumX
Body: <p>Implementing SEE extensively in my chess AI but can't seem to speed it up. Just using depth and MaxDepth. I'd like to add heuristics similar to negascout, quiescence, lazy eval. Maybe something like alpha beta. Trade off minimal accuracy for performance. </p>
  
  <p>Another question is what to return "in check"</p>
  
  <pre><code>function _see(sq, fen, depth, maxDepth, color, chess) {
      "use strict";
      if (chess.fen() !== fen) {
          console.error("s fen/chess sync error");
          chess.load(fen);
      }
  
      if (chess.in_checkmate() || chess.game_over()) {
          return MATE;
      } else if (chess.in_check()) {
          return 0; // ????
      }
  
      var value = 0, moves, index, move_score, tfen, foo, bar;
  
      if (depth &lt; maxDepth) {
          moves = chess.moves({
              square: sq,
              verbose: true
          });
          if (moves.length &gt; 0) {
              counter.seeNodes = counter.seeNodes + 1;
              moves = _.chain(moves)
                  //only captures
                  .reject(function (e) {
                      return !e.hasOwnProperty('captured');
                  })
                  //material MVV
                  .sortBy(function (s) {
                      return evalPiece(s.piece);
                  })
                  //captures LVA
                  .sortBy(function (s) {
                      return -evalPiece(s.captured);
                  })
                  .value();
              //counter.sDepth = Math.max(depth, counter.sDepth);
              //counter.maxSDepth = Math.max(maxDepth, counter.maxSDepth);        console.error(JSON.stringify(moves));
  
              for (index = 0; index &lt; moves.length; index += 1) {
                  foo = chess.move(moves[index]);
                  if (foo === null) {
                      console.error("see move generated error, aborting loop");
                      break;
                  }
                  tfen = chess.fen();
                  value = Math.max(0, evalPiece(foo.captured) - _see(sq, tfen, depth + 1, maxDepth, -color, chess));
                  bar = chess.undo();
                  if (bar === null) {
                      console.error("see: bar=null");
                  }
              }
  
          }
  
      }
      return value;
  }
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-03-18T22:44:57.573Z
Comments.Text: Do you understand SEE is not a alpha-beta?
Comments.UserDisplayName: SmallChess
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-03-18T23:11:05.763Z
Comments.Text: Yes. Not sure how to speed it up. Throwing the idea of Alpha beta like concept used in the context of cut offs. Not sure what the answer is, just throwing out ideas and seeing what sticks.
Comments.UserDisplayName: Νικόλαος Μανωλακος
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-03-26T19:29:02.320Z
Comments.Text: actually found a SEE implementation with alpha-beta at http://www.talkchess.com/forum/viewtopic.php?t=40054
Comments.UserDisplayName: Νικόλαος Μανωλακος
Tags: <engines><programming>
Title: Static exchange Evaluation (SEE) optimization
ThreadText: # Static exchange Evaluation (SEE) optimization
  
  (Asked by: username_0 on 2016-03-18)
  
  Implementing SEE extensively in my chess AI but can't seem to speed it up. Just using depth and MaxDepth. I'd like to add heuristics similar to negascout, quiescence, lazy eval. Maybe something like alpha beta. Trade off minimal accuracy for performance.
  
  Another question is what to return "in check"
  
  ```
  function _see(sq, fen, depth, maxDepth, color, chess) {
      "use strict";
      if (chess.fen() !== fen) {
          console.error("s fen/chess sync error");
          chess.load(fen);
      }
  
      if (chess.in_checkmate() || chess.game_over()) {
          return MATE;
      } else if (chess.in_check()) {
          return 0; // ????
      }
  
      var value = 0, moves, index, move_score, tfen, foo, bar;
  
      if (depth < maxDepth) {
          moves = chess.moves({
              square: sq,
              verbose: true
          });
          if (moves.length > 0) {
              counter.seeNodes = counter.seeNodes + 1;
              moves = _.chain(moves)
                  //only captures
                  .reject(function (e) {
                      return !e.hasOwnProperty('captured');
                  })
                  //material MVV
                  .sortBy(function (s) {
                      return evalPiece(s.piece);
                  })
                  //captures LVA
                  .sortBy(function (s) {
                      return -evalPiece(s.captured);
                  })
                  .value();
              //counter.sDepth = Math.max(depth, counter.sDepth);
              //counter.maxSDepth = Math.max(maxDepth, counter.maxSDepth);        console.error(JSON.stringify(moves));
  
              for (index = 0; index < moves.length; index += 1) {
                  foo = chess.move(moves[index]);
                  if (foo === null) {
                      console.error("see move generated error, aborting loop");
                      break;
                  }
                  tfen = chess.fen();
                  value = Math.max(0, evalPiece(foo.captured) - _see(sq, tfen, depth + 1, maxDepth, -color, chess));
                  bar = chess.undo();
                  if (bar === null) {
                      console.error("see: bar=null");
                  }
              }
  
          }
  
      }
      return value;
  }
  
  ```
  
  **Tags:** engines, programming
  
  > **Comments:**
  > **username_1**: Do you understand SEE is not a alpha-beta?  
  > **username_0**: Yes. Not sure how to speed it up. Throwing the idea of Alpha beta like concept used in the context of cut offs. Not sure what the answer is, just throwing out ideas and seeing what sticks.  
  > **username_0**: actually found a SEE implementation with alpha-beta at http://www.talkchess.com/forum/viewtopic.php?t=40054  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2016-07-31. Score: 1
  
  Your algorithm seems very wrong to me for SEE. It appears much closer to Quiescence Search instead.
  
  * SEE is an unary tree. After finding a legal move, the SEE function returns. It doesn't need to check all possible moves for the best one; just one.
  * You sort your moves in MVV/LVA order. Your ordering should just be on the least valuable attacking piece.
  * You search all possible moves. SEE only searches captures on a square.
  
  To answer your question of:
  
  > what to return "in check"
  
  SEE doesn't actually care about check. If you capture with your king and the opponent can capture with anything, then the value of the king should be large enough that `Math.max(0, evalPiece(foo.captured) - _see(sq, tfen, depth + 1, maxDepth, -color, chess))` has a greater score for not capturing with your king than capturing the king.
  
  
  ---
  
  