搜索算法

简单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）剪掉。

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

推断是会了，但是如何编写相关代码实现该功能呢？且听下回分解。