最大最小值搜索（MaxMin Search）‌

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

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

正在完善内容 . . .

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

    get best() {
        const self = this;
        function min_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 = max_search();
                }
                self.undomove();
                if (score < bestscore) {
                    bestscore = score;
                }
            }
            return bestscore;
        }

        function max_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 = min_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 = min_search();
            this.undomove();
            if (score > bestscore) {
                bestmove = move;
                bestscore = score;
            }
        }
        return {move: bestmove, score: bestscore};
    }
}
  

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

  
function engine_test(count) {
    const engines = new MaxMin();
    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);
  

如果你是先手，有没有办法获胜呢？

以上的测试，已经穷举了所有的可能，确认不存在先手必胜的着法！

也就是说，如果双方都没有失误，井字棋是和棋。