搜索算法

简单Minimax搜索

Minimax搜索

象棋属于零和博弈，有红方和黑方，双方的收益总和为0，一方的优势总是伴随着另一方的劣势。此时，我们可以使用Minimax进行搜索。

为了方便理解，我们暂且把Maximizing Player称为“红方”，把Minimizing Player称为“黑方”（实际上则不一定），我们的评估函数暂时返回的是相对于红方的分数（分高说明红方优势，分低说明红方劣势）。

博弈的双方都想让收益最大化，红方想让分数尽量高，黑方想让分数尽量低，这样就能最大程度上保证自己这方的优势，同时让对方占到的优势最小。

举个例子，红方在一个局面有两种走法。一种走法可以吃掉对方的车，此时的分数是+500，另一种走法是送掉自己的车，此时的分数是-500。红方当然会选择对自己有利的走法，即第一种，所以该节点的分数就是+500。

伪代码如下：

int minimax(int depth, bool isMaximizingPlayer) { // 层数, 是否红方
    if (depth == 0 || isGameOver()) { // 搜索到叶子节点或游戏结束，直接返回评估
        return evaluate();
    }

    if (isMaximizingPlayer) { // 如果当前是红方
        int maxEval = INT_MIN; // 初始化为负无穷，方便程序找出所有走法中分数的最大值
        for (Move move : getPossibleMoves()) { // 走法生成
            makeMove(move); // 走子
            int eval = minimax(depth - 1, false); // 向下一层搜索，获得该走法对应的子节点的分数
            undoMove(move); // 恢复到走子前的局面
            maxEval = std::max(maxEval, eval);
        }
        return maxEval;
    } else { // 如果当前是黑方
        int minEval = INT_MAX;  // 初始化为正无穷，方便程序找出所有走法中分数的最小值
        for (Move move : getPossibleMoves()) { // 走法生成
            makeMove(move); // 走子
            int eval = minimax(depth - 1, true); // 向下一层搜索，获得该走法对应的子节点的分数
            undoMove(move); // 恢复到走子前的局面
            minEval = std::min(minEval, eval); // 取最小值
        }
        return minEval;
    }
}

Alpha-Beta剪枝的过程介绍

上面实现的简单Minimax搜索，效率其实是很低的。我们这时就要引入一种新的搜索策略——Alpha-Beta剪枝，这种剪枝方法可以在不改变结果的前提下大大减少搜索的节点数。

Alpha-Beta剪枝（带注解）

上文我们提到过，红方的目的是使得分尽量高，也就是说当前节点的分数是所有子节点分数的最大值，黑方则相反。

参考右图，我们可以举个例子说明一下Alpha-Beta剪枝的原理。

引擎搜完叶子节点的5和6，可以推断出这两个节点的父节点（图中ID：2）的分数是min(5,6)=5。这个节点的父节点在MAX层上（图中ID：1），是取其子节点分数的最大值，所以它的分数至少是5。子节点的分数只有>5才有搜下去的必要，否则不会比“ID：2”这一路线更优。

接下来我们继续搜索“ID：3”这一路线，搜完叶子节点的“7”和“4”之后，由于“ID：3”处在MIN层，其分数是取其子节点分数的最小值，所以这个节点的分数必然≤4，不可能比“ID：2”这一条路线更优，没有再搜下去的必要了，我们可以把后续的子节点（即灰色的5）剪掉。

其它灰色的部分也是同理，大家可自行按照上面的步骤推断。

根据理论推断是会了，但这仍是纸上谈兵，如何编写相关代码实现该功能呢？且听下回分解。

Alpha-Beta剪枝的代码实现

为了用代码实现Alpha-Beta剪枝，我们需要引入alpha和beta两个量，alpha是红方能保证至少获得的分数，beta是黑方能保证至多获得的分数（这里的分数都是从红方视角看的）。也就是说，最优走法的分数必然≥alpha而且≤beta。

在最开始调用“alphaBeta”函数的时候，我们应该把alpha设为负无穷，把beta设为正无穷。

当我们搜索一个节点的时候，我们需要接受从父节点传来的alpha和beta值，接着判断该节点处于MAX层还是MIN层。

这里还是举一个例子方便读者理解，假设我们处于MAX层（即红方），父节点传递的alpha值是5，beta值是8。

因为当前节点的分数是从子节点的分数中取最大值得到的，所以我们在搜索的时候可以保证当前节点的分数≥子节点的分数，应该根据子节点的分数更新alpha的值。如果我们此时搜到一个子节点，分数为10，此时当前节点的分数必定≥10。但我们不要忘了，上一层是MIN，取的是子节点中的最小分数。若当前节点的分数超过了beta，必然不会比其父节点之前搜过的某个子节点分数低，不会被父节点采纳；若当前节点的分数等于beta，必然不会比其父节点之前搜过的某个子节点更优。我们可以直接使用break跳出循环，进行Beta剪枝，同时返回目前搜过的子节点的最大分数（目前的搜索代码中，这里返回值不重要，只需要保证该节点不被父节点采纳即可）。

判断当前节点的分数是否≥beta，可以等同于判断alpha≥beta，因为alpha就是按照子节点的分数进行更新的。

MIN层同理，这里不再赘述。

伪代码如下：

int alphaBeta(int depth, int alpha, int beta, bool isMaximizingPlayer) {
    if (depth == 0 || isGameOver()) {
        return evaluate();
    }

    if (isMaximizingPlayer) { // 如果当前是红方
        int maxEval = INT_MIN; // 初始化为负无穷，方便程序找出所有走法中分数的最大值
        for (Move move : getPossibleMoves()) { // 走法生成
            makeMove(move); // 走子
            int eval = alphaBeta(depth - 1, alpha, beta, false); // 向下一层搜索，获得该走法对应的子节点的分数
            undoMove(move); // 恢复到走子前的局面
            maxEval = std::max(maxEval, eval); // 取最大值
            alpha = std::max(alpha, eval);
            if (beta <= alpha)
                break; // Beta剪枝
        }
        return maxEval;
    } else { // 如果当前是黑方
        int minEval = INT_MAX;  // 初始化为正无穷，方便程序找出所有走法中分数的最小值
        for (Move move : getPossibleMoves()) { // 走法生成
            makeMove(move); // 走子
            int eval = alphaBeta(depth - 1, alpha, beta, true); // 向下一层搜索，获得该走法对应的子节点的分数
            undoMove(move); // 恢复到走子前的局面
            minEval = std::min(minEval, eval); // 取最小值
            beta = std::min(beta, eval);
            if (beta <= alpha)
                break; // Alpha剪枝
        }
        return minEval;
    }
}