Static exchange Evaluation (SEE) optimization 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 &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;
}
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.