负最大值搜索（NegaMax Search）‌

“井字棋”的搜索树很小，每轮搜索，都是直达终盘（棋子已经填满，或有一方获胜）才结束。

在“中国象棋”或“五子棋”中，搜索树非常庞大，要完全搜索是不可能的，一般情况是给定一个深度，如果时间允许，深度逐步加深。

正在完善内容 . . .

  
class NegaMax extends Modal {
    constructor() {
        super();
    }

    get best() {
        const self = this;
        function nega_search() {
            if (self.depth > 8) {
                return 0;
            }
            var bestscore = -self.MATE_VALUE;
            for (var move of self.moves) {
                var score = self.domove(move).score;
                if (score == 0) {
                    score = -nega_search();
                }
                self.undomove();
                if (score > bestscore) {
                    bestscore = score;
                }
            }
            return bestscore;
        }

        if (this.depth > 8) {
            return {move: -1, score: -1};
        }
        var bestmove = -1;
        var bestscore = -this.MATE_VALUE;
        for (var move of this.moves) {
            var score = this.domove(move).score;
            if (score != 0) {
                this.undomove();
                return {move: move, score: score};
            }
            score = -nega_search();
            this.undomove();
            if (score > bestscore) {
                bestmove = move;
                bestscore = score;
            }
        }
        return {move: bestmove, score: bestscore};
    }
}
  

测试一下“负最大值搜索”：

  
function engine_test(count) {
    const engines = new NegaMax();
    var n = 0;
    while (n++ < count) {
        engine.reset();
        var final = false;
        while (!final) {
            var move = engine.best.move;
            var result = engine.domove(move);
            if (result.score == 0) {
                if (engine.depth == 9) {
                    final = true;
                }
            } else {
                final = true;
            }
        }
        var x = n.toString().padStart(3, ' ');
        var depth = engine.depth;
        var path = engine.path;
        console.log(`${x}: depth: ${depth}, path:[${path}]`);
    }
}

engine_test(10);