alpha-beta 剪枝

转载请注明原文链接：https://www.cnblogs.com/Multya/p/17929261.html

考虑一个树：

一棵树上只有叶子节点有值，有确定的根节点的位置

根据层数来划分叶子节点和根节点之间的链接节点

偶数层上的值取子节点的最大值，奇数取最小

因为叶子节点上的值确定，在有这么个规则之后整棵树上所有节点就定下来了吧

现在我遮住全部叶子节点，让你通过打开尽量少次数叶子节点，确定根节点的值

我们通过 alpha-beta 剪枝来实现

确定的事情：

一个节点上的值必定是长在它身上的所有叶子的值中的一个
max{ a, min{b,x} } 如果 b 比 a 小，无论 x 取什么，结果都是 a
min{ a, max{b,x} } 如果 b 比 a 大，无论 x 取什么，结果都是 a

为什么？我们放慢这个思考过程看看背后的逻辑

我们用一个区间来表示这个算式最后的结果的范围，下界是 a，上界是 b

我们知道计算最大最小的过程，其实就是一个单边的区间不断根据新的值刷新的过程：

假设计算 max{4,5,1}

第一个数是 4 暂定是表达式的值

然后 4 确定下界是 4 的区间，这个区间希望得到一个在这个区间内的数刷新区间下界和更新表达式的值。5 在这个区间内，所以它能刷新表达式和更新区间下界

1 不在这个区间内，所以它不能更新表达式和区间。所以表达式是最后更新状态下的 5，计算正确

刷新区间的操作也可以用求交集来实现，这样的话就省了判断的那一步，然后结果也可以用最后的下界来确定

所以可以变成这样：

求区间（4，+ $\infty$ ）∩（5，+ $\infty$ ）∩（1，+ $\infty$ ）的下界

这样我们就实现了用区间来求最大（最小）的功能

再看 max{ 4, min{3,1} }

第一个数是 4 暂定是表达式的值

然后 4 确定下界是 4 的区间，这个区间希望得到一个在这个区间内的数刷新区间下界和更新表达式的值。

这个区间希望表达式 min{3,1}得到一个大于 4 的数刷新区间下界和更新表达式的值（这个过程区间原封不动传递下去）

先计算表达式 min{3,1} 第一个数是 3，然后 5 确定表达式在小于 3 的区间内，希望得到一个小于 5 的值刷新表达式

但是这个区间内所有的数都不在上个表达式期望的大于 4 的数区间内（区间不重合），也就是这个表达式所有可能的值都不能刷新上个表达式的值，所以跳过计算这个子表达式

由于上个表达式所有数遍历完了，最后更新的数是 4，所以表达式值为 4

我们再来看完全用区间来实现的方法：（【】内计算得到一个数）所有都是闭区间哈，意会就行

求（4，+ $\infty$ ）∩ （ min{3,1} ，+ $\infty$ ）的下界

即求（4，+ $\infty$ ）∩ （【（- $\infty$ ，3）∩ （- $\infty$ ，1）的上界】，+ $\infty$ ）的下界

我们定义空区间的上界是正无穷，下界是负无穷，这样做的理由是使空区间对结果不产生任何贡献（因为都是取交集）

然后是关键的一步：根据上面的启发，我们把前面得到的区间套一层壳，也就是：

等价为求（4，+ $\infty$ ）∩ （【（4，+ $\infty$ ）∩【（- $\infty$ ，3）∩ （- $\infty$ ，1）的上界】的上界】，+ $\infty$ ）的下界

这个结果不变。因为【（4，+ $\infty$ ）∩【（- $\infty$ ，3）∩ （- $\infty$ ，1）的上界】的上界】的结果不是空集的话对上界没有影响，是空集的话没有贡献。

可以等价为（4，+ $\infty$ ）∩ （【（4，+ $\infty$ ）∩（- $\infty$ ，3）∩ （- $\infty$ ，1）的上界】，+ $\infty$ ）的下界，因为取交集，先后没有影响。

此时可以先通过判断（4，+ $\infty$ ）∩（- $\infty$ ，3）是空集来提前结束求值，得到最后区间（4，+ $\infty$ ）

像上面这样，如果把传递给子表达式期望的区间和子表达式结果的区间看成一回事的话，那就是 alpha-beta 剪枝的逻辑。回到最开始的那个树。这个区间能被固定在每一个节点身上，表示这个节点的状态：如果要刷新这个节点的值，要求新输入的值的区间范围。如果这个节点从未被刷新，那么这个节点的值就不会产生任何贡献来刷新上一个表达式的值。如果这个区间是一个空区间，那么所有的值都不能刷新这个节点的值，那么就没有必要继续给这个节点输入值了。

观察区间动向的话会发现有关区间的操作有以下几种：

把值改写为区间
区间取交集
取区间一端的数传递回去
把一个区间传递给子表达式内提前取交集

再看 max{ 4, min{3,1} }，这次我们加上树的形状和叶子节点遮挡的特性

自行画图：有 4 3 1 三个节点，一个根节点，两个链接节点，三个叶子节点

开始。打开叶子 4，更新所连接的父节点

这里将每个节点区间初始化为全体实数，因为是 MAX 层，刷新这个节点的区间为（4，+ $\infty$ ）

传递（4，+ $\infty$ ）给链接 3 和 1 的链接节点（此时我们还不知道 3 和 1）

链接节点打开叶子 3，因为是 MAX 层，产生区间（- $\infty$ ，3）

原来已经有集合了，取交集为空集，提前结束运算，不做任何贡献，不传递值回去

这样就完成了任务，只打开了 4 和 3 就知道了根节点的值是 4

如果把前面的值用负号在 min 层取反，那么所有的层的操作逻辑都变成一样的了

alpha-beta 剪枝的算法的代码：

//意义：目前棋盘的最值评分 分数的正负取决于一开始的isBlackNow
int abSearch(int floor, int alpha, int beta, bool isBlackNow, Coord &searchResult) {
    int tmpScore, moveCount = 0;
    Coord tempSearchResult{};
    //优化1
    std::vector<ScoreCoord> possibleMove = generatePossibleMove(isBlackNow);
    for (auto &now: possibleMove) {
		//优化2
        moveCount++;
        if (moveCount > 8) break; //只搜索前8个可能的落子点
        int x = now.coord.x, y = now.coord.y;
        m_map[x][y] = isBlackNow ? BLACK_CHESS : WHITE_CHESS;
        //优化3
        if (someoneWin({x, y})) {//如果有人赢了 必定是下这个子的人赢了
            searchResult = {x, y};
            tmpScore = evaluateAll(isBlackNow);//返回这个局面最高的得分，也就是赢局的分数
            m_map[x][y] = NO_CHESS;
            return tmpScore;
        }
        //单层搜索
        if (floor == 1) {//如果只看这一步子 那就是这一步子所有可能的得分中的最大值
            tmpScore = evaluateAll(isBlackNow);
            m_map[x][y] = NO_CHESS;
            if (tmpScore > alpha) {
                alpha = tmpScore;
                searchResult = {x, y};
            }
            continue;
        }
        tmpScore = -abSearch(floor - 1, -beta, -alpha, !isBlackNow, tempSearchResult);//不然得分就是我下了之后的对方的所能得到的最高分取负
        m_map[x][y] = NO_CHESS;
        if (tmpScore >= beta) {
            return beta;
        }
        if (tmpScore > alpha) {//取对方尽所有努力后得到最大值中的最小的一个 取负值后变成最大的一个
            alpha = tmpScore;
            searchResult = {x, y};
        }
    }
    return alpha;
}

抽象出来的伪代码：

//意义：目前棋盘的最值评分 分数的正负取决于一开始的isBlackNow
int abSearch(int floor, int alpha, int beta, bool isBlackNow, Coord &searchResult) {
    possibleMove = generatePossibleMove();
    for (auto &now: possibleMove) {
	    downOneStep();
        if (someoneWin()) {//如果有人赢了 必定是下这个子的人赢了
            saveSearchResult();
            restoreLastStep();
            return evaluateScore();
        }
        //单层搜索
        if (floor == 1) {//如果只看这一步子 那就是这一步子所有可能的得分中的最大值
            tmpScore = evaluateScore();
            restoreLastStep();
            if (tmpScore > alpha) {
                alpha = tmpScore;
                saveSearchResult();
            }
            continue;
        }
        tmpScore = -abSearch(floor - 1, -beta, -alpha, !isBlackNow, tempSearchResult);//不然得分就是我下了之后的对方的所能得到的最高分取负
        restoreLastStep();
        if (tmpScore >= beta) {
            return beta;
        }
        if (tmpScore > alpha) {//取对方尽所有努力后得到最大值中的最小的一个 取负值后变成最大的一个
            alpha = tmpScore;
            saveSearchResult();
        }
    }
    return alpha;
}

🪴 Cyril

探索

alpha-beta 剪枝

关系图谱

反向链接