博弈树（Game Tree）‌

博弈树，是指用于描述博弈过程中所有可能状态序列的树结构，其中节点代表游戏局面，边代表合法策略。‌

博弈树，也有人称之为搜索树，或者博弈搜索树，指的都是同一个对象。本文中统一称为“博弈树”。

以下是一棵节点有四个分枝的博弈树：

在井字棋中，博弈树要比上图大得多：

第一层（根节点）有九个分枝。

第二层的节点有八个分枝（去掉第一步选择的点）。

第三步的节点有七个分枝（去掉第一、第二点选择的点）。

以此类推。

语言的选择

在“井字棋”篇中，我们用 JavaScript(ES6) 来描述算法

“象棋”和“五子棋”的计算量大，所以采用C++编写搜索引擎，并编译成WASM供网页使用

class Modal 是井字棋搜索树的模型：

• 开始时（或reset后）指向根节点。
• player：当前决策方，0为先手方，1为后手方。
• depth：当前已经走过的步数。
• path：详细记录各步的落子点。
• values：棋盘上各个点的棋子方，-1为空，0为先手方，1为后手方。
• moves：当前节点可选择的所有可以选择的落子点。
• domove(move)：当前玩家在move位置落子，并返回是否形成三连。
• undomove()：返回上一个状态。
• isfinal(move)：判断当前玩家在move位置落子是否会形成三连。

当模型实现以上的属性和方法，就可以开始最优策略搜索了。

详细代码如下：

  
class Modal {
    constructor() {
        this.path = [];
        this.values = [];
        this.indexs = [];
        this.reset();
    }

    get MATE_VALUE() {
        return 100;
    }

    get player() {
        return this.path.length % 2;
    }
    
    get depth() {
        return this.path.length;
    }

    get moves() {
        var moves = [];
        for (var x of this.indexs) {
            if (this.values[x] == -1) {
                moves.push(x);
            }
        }
        return moves;
    }

    reset() {
        this.path = [];
        this.values = [-1,-1,-1,-1,-1,-1,-1,-1,-1];
        this.indexs = [0,1,2,3,4,5,6,7,8];
        for (var x=0; x<9; x++) {
            var y = Math.floor(Math.random() * 9);
            var temp = this.indexs[x];
            this.indexs[x] = this.indexs[y];
            this.indexs[y] = temp;
        }
    }

    isfinal(move) {
        const lines = [
            [[1,2],[3,6],[4,8]],
            [[0,2],[4,7]],
            [[0,1],[4,6],[5,8]],
            [[0,6],[4,5]],
            [[0,8],[1,7],[2,6],[3,5]],
            [[2,8],[3,4]],
            [[0,3],[2,4],[7,8]],
            [[6,8],[1,4]],
            [[0,4],[2,5],[6,7]],
        ];
        if (move < 0 || move >= 9) {
            throw new Error('isfinal error: index out of bounds.');
        }
        if (this.values[move] != -1) {
            throw new Error('isfinal error: data duplication.');
        }
        for (var x of lines[move]) {
            if (this.values[x[0]] == this.values[x[1]] && this.values[x[1]] == this.player) {
                return {score: this.MATE_VALUE-this.depth, points: [move, x[0], x[1]]};
            }
        }
        return {score: 0, points: [-1, -1, -1]};
    }

    undomove() {
        if (this.depth == 0) {
            throw new Error('undomove error: empty stack.');
        }
        var move = this.path.pop();
        this.values[move] = -1;
        return 0;
    }

    domove(move) {
        if (move < 0 || move >= 9) {
            return new Error('domove error: index out of bounds.');
        }
        if (this.values[move] != -1) {
            return new Error('domove error: data duplication.');
        }
        var result = this.isfinal(move);
        this.values[move] = this.player;
        this.path.push(move);
        return result;
    }
}