AlphaBeta搜索（AlphaBeta Search）‌

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

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

正在完善内容 . . .

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

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

        if (this.depth > 8) {
            return {move: -1, score: -1};
        }
        var bestmove = -1;
        var alpha = -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 = -alpha_beta_search(-this.MATE_VALUE, -alpha);
            this.undomove();
            if (score > alpha) {
                bestmove = move;
                alpha = score;
            }
        }
        return {move: bestmove, score: alpha};
    }
}
  

测试一下“AlphaBeta搜索”：

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

AlphaBeta搜索的优势

很明显，AlphaBeta搜索，比最大最小值搜索、负最大值搜索的速度要快得多！

在后续章节，我们将继续讨论优化方法，让搜索运行得更快速些。