数据结构与算法分析：专题内容——人工智能中的寻路7之AlphaBeta（代码详解）

一、算法描述

在考虑到对手的可能走法之后，Minimax算法能够较为恰当地找出玩家的最优走法。但是，在生成博弈树时，这个信息却没有使用！我们看看早先介绍的BoardEvaluation评分函数。回忆一下下图Minimax的探测：
在这里插入图片描述
这是从初始状态开始，玩家X走了两步，玩家O走了一步之后，生成的博弈树的一部分。我们可以注意到，Minimax算法的性能非常低下，即使每一个子搜索都能够表示一个负棋面状态。总共有36个节点需要评价。
Minimax并不会利用玩家O第一步走在左上角避免被秒杀这个事实。AlphaBeta算法使用一个固定的策略来从搜索树中剪除无效的搜索，而不是在搜索中采取特殊的策略来使用信息。使用AlphaBeta算法的博弈树等价扩展如下图所示。
在这里插入图片描述

二、复杂度分析

在这里插入图片描述

虽然得到的走法和Minimax的走法很类似，但是主要的改进就是大量节省了时间，大量的状态被从博弈树中剪除掉了。
因为AlphaBeta返回的结果和Minimax以及NegMax计算出来的几乎相同，那么唯一能够看出AlphaBeta好处的地方就是检查生成的博弈树的规模。这个任务是非常复杂的，因为如果对手的最优走法首先被评价，AlphaBeta能够节省大量的时间。当每个局面状态有b个可行走法时，追寻深度为d的AlphaBeta算法可能搜索的状态数目大约为 $b^d$ 。如果走法是按照某种顺序降序排列，那么我们仍然需要评价所有的b个子节点（因为我们要选择最优的走法），但是，最好情况下我们只需要评价对手的第一种走法。在AlphaBeta追寻深度为2的图中，由于走法有序，在评价了一些走法之后，就能够进行剪枝，所以在这棵博弈树下，走法排序并不是最优的。
最好情况下，AlphaBeta在每一级为玩家评价b个局面状态，但是只评价对手的一个局面状态。所以，在博弈树的第d级，AlphaBeta只需要评价b1b*……b1个局面状态，而不是扩展出bbb*……bb个局面状态。所以局面状态的总数是bd/2，节省了巨大的开销。
AlphaBeta并不会试图简单地最小化状态的数目，AlphaBeta扩展的数目有可能和Minimax一样多，但是这种情况下，AlphaBeta扩展的深度是Minimax的两倍。
从经验上来比较Minimax和AlphaBeta，我们构建了一个一字棋初始棋面状态的集合，这些棋面状态至少能够走k步。然后定义追寻深度为d=9-k，保证所有可能的走法都会探测到，然后对比Minimax和AlphaBeta。结果见下表。我们看到AlphaBeta算法剪除掉了大量的状态。

k	Minimax状态数	AlphaBeta状态数	减少程度	波动范围
1	549,945	27,565	95%	±1.3%
2	549,936	47,508	91%	±6.8%
3	549,864	112,086	80%	±10.2%

每个比较都说明了AlphaBeta的巨大改进。而且有些情况能够解释为什么AlphaBeta如此优秀，例如这个局面状态：
在这里插入图片描述
AlphaBeta只需扩展47的局面状态（Minimax需要扩展8232个，节省了99.4%）来告知玩家X应该选择中间的方块。但是，能够得到这样大的性能改进的前提是可行走法有序，并且最优走法排在最前面。因为我们的一字棋的解不会排序走法，可能会得到一些异常结果。例如，将上面的棋面旋转180°：
在这里插入图片描述
那么AlphaBeta只需要探测960个局面状态（节省了88.3%）。

三、适用情况

AlphaBeta算法也是搜索最好的走法，它能够记住如果玩家O走在左上角，那么玩家X的得分不会超过2这样的信息。对于玩家O的后续每一步，AlphaBeta会决定是否玩家X有至少一步这样的走法，这步走法能够比玩家O第一步要好。因此，博弈树只扩展了16个节点（相比Minimax节省了50%的开销）。更重要的是，如果这个部分的结果无关紧要，那么算法就不需要预计算可能的走法并且修改状态。
AlphaBeta选择Minimax也同样会选择的走法，但是会节省大量的开销。和之前描述的其他寻路算法一样，AlphaBeta算法也假设对手不会犯错，这样避免了搜索那些对局面没有影响的部分。AlphaBeta递归地搜索博弈树，并且维护两个值，α和β，如果α＜β，那么表示玩家α有胜利的机会。值α表示已经为玩家找到的最坏局面状态（如果没有找到即负无穷），并且声明玩家的走法能够保证不低于这个下界。α越大表示玩家能够表现得越好，如果α等于正无穷，那么玩家能够找到一步绝杀，并且搜索中值。β值表示现在的最好局面状态（如果没有找到即正无穷），即我们玩家能够达到的最好局面状态。β越小表示对手在限制玩家方面表现得越好。因为AlphaBeta算法有一个最大追寻深度，所以任何决定都受这个深度限制。
上图的博弈树给出了执行时候的[α,β]值；最开始为[-∞，∞]。使用追寻深度为2的搜索，仅仅只考虑玩家X接下来会采取的一步走法，AlphaBeta试着为玩家O找出最优走法。因为AlphaBeta是递归的，我们能够追寻其进程，对博弈树进行遍历。AlphaBeta指导玩家O首先应该占住左上角的位置。在评价了玩家X的5个可行走法之后，很明显玩家X只能保证α最小等于-2（使用一字棋的BoardEvaluation静态评估函数）。当AlphaBeta考虑O的第二步时，其[α,β]值现在是[-2，∞]，即“O做出最坏的决定能够达到的状态得分为-2，最好的决定可能赢得比赛”。当评价完玩家X的第一步对策，AlphaBeta发现X已经赢得比赛，所以将不会再考虑X的更多走法。
回忆一下AlphaBeta搜索是基于NegMax。AlphaBeta保证不会搜索无用节点。下图是在图Minimax的基础上进行追寻深度为3的搜索，我们可以看到AlphaBeta是如何剪枝的，Minimax的博弈树需要156个节点，而AlphaBeta博弈树只扩展了66个节点。
在这里插入图片描述
初始位置为节点n，玩家O需要考虑6个可行走法。在轮到玩家或者对手时都可以进行键值。在上图的搜索中，有两个这样的例子。

轮到玩家
假设玩家O在下在左列中间的位置，X于是下在顶行中间的位置（搜索树中这是根节点的最左边的孙子节点）。现在，从O的角度来看，O能够得到的最好的分数是-1。当X走在底行中间，我们决定是否O能够赢得比赛时，将会用到这个值。这个时候[α,β]是[-∞,-1]。当O走在顶行的中间时，AlphaBeta进行评价，得到分数为1，因为这个值大于-1，所以在这个层级上的O剩余三个走法都可以忽略。
轮到对手
假设玩家O在下在左列中间的位置，X于是下在右上角，那么将会立刻赢得比赛。AlphaBeta将不会考虑X的其他两个可行走法，因为在以玩家O上一步走法为根节点的子树中，其剩余的搜索节点都会剪除。

搜索将会剪掉那些确定会失败的子树。当基于Minimax扩展出AlphaBeta时，存在两种剪枝的方法，α剪枝和β剪枝，当基于NegMax扩展出简单的AlphaBeta时，那么只有一种剪枝的方法。因为AlphaBeta是递归的，那么[α,β]表示玩家的获胜机会大小，[-β,α]表示对手获胜机会的大小。在递归调用AlphaBeta时，会轮流从玩家和对手的角度来考虑问题。AlphaBeta会返回Minimax（如果是基于NegMax扩展，返回和NegMax相同的结果）相同的结果，但是它只会很少地扩展博弈树。AlphaBeta仍然使用深度的限制，这样来看，它的行为非常类似于深度优先搜索。

四、算法实现

输入输出和Minimax相同。主要的区别是AlphaBeta将会利用已经计算过的状态来决定是否继续搜索特定的子树。
AlphaBeta实现基于NegMax扩展。一旦当前局面状态下，玩家不能保证一个更好的位置（α剪枝）或者对手不能强迫玩家走到一个更坏的位置（β剪枝），那么搜索终止。

#include <iostream>
#include <vector>
#include <memory>
#include <limits>
#include <algorithm>// Forward declarations
class IGameState;
class IGameMove;
class IPlayer;
class IEvaluation;// Interface for game state
class IGameState {
public:virtual std::shared_ptr<IGameState> copy() = 0;virtual ~IGameState() = default;
};// Interface for game move
class IGameMove {
public:virtual void execute(std::shared_ptr<IGameState> state) = 0;virtual void undo(std::shared_ptr<IGameState> state) = 0;virtual ~IGameMove() = default;
};// Interface for player
class IPlayer {
public:virtual std::vector<std::shared_ptr<IGameMove>> validMoves(std::shared_ptr<IGameState> state) = 0;virtual int eval(std::shared_ptr<IGameState> state) = 0;virtual ~IPlayer() = default;
};// Evaluation interface
class IEvaluation {
public:virtual std::shared_ptr<IGameMove> bestMove(std::shared_ptr<IGameState> state,std::shared_ptr<IPlayer> player,std::shared_ptr<IPlayer> opponent) = 0;virtual ~IEvaluation() = default;
};// Move evaluation class
class MoveEvaluation {
public:std::shared_ptr<IGameMove> move;int score;explicit MoveEvaluation(int score) : move(nullptr), score(score) {}MoveEvaluation(std::shared_ptr<IGameMove> m, int s) : move(m), score(s) {}static int minimum() { return std::numeric_limits<int>::min(); }static int maximum() { return std::numeric_limits<int>::max(); }
};// AlphaBeta evaluation class
class AlphaBetaEvaluation : public IEvaluation {
private:std::shared_ptr<IGameState> state;int ply;MoveEvaluation alphabeta(int ply, std::shared_ptr<IPlayer> player,std::shared_ptr<IPlayer> opponent,int alpha, int beta) {// Get valid movesauto moves = player->validMoves(state);// If leaf node or no moves available, return evaluationif (ply == 0 || moves.empty()) {return MoveEvaluation(player->eval(state));}// Initialize best move with alphaMoveEvaluation best(alpha);// Try each move and update alphafor (const auto& move : moves) {// Execute movemove->execute(state);// Recursively evaluate positionMoveEvaluation me = alphabeta(ply - 1, opponent, player, -beta, -alpha);// Undo movemove->undo(state);// Update alpha if better move foundif (-me.score > alpha) {alpha = -me.score;best = MoveEvaluation(move, alpha);}// Pruning conditionif (alpha >= beta) {return best;}}return best;}public:explicit AlphaBetaEvaluation(int searchPly) : ply(searchPly) {}std::shared_ptr<IGameMove> bestMove(std::shared_ptr<IGameState> s,std::shared_ptr<IPlayer> player,std::shared_ptr<IPlayer> opponent) override {state = s->copy();MoveEvaluation move = alphabeta(ply, player, opponent,MoveEvaluation::minimum(),MoveEvaluation::maximum());return move.move;}
};// Example implementations for testing
class TicTacToeState : public IGameState {
public:std::vector<int> board;TicTacToeState() : board(9, 0) {}std::shared_ptr<IGameState> copy() override {auto newState = std::make_shared<TicTacToeState>();newState->board = this->board;return newState;}
};class TicTacToeMove : public IGameMove {
public:int position;int player; // 1 or -1TicTacToeMove(int pos, int p) : position(pos), player(p) {}void execute(std::shared_ptr<IGameState> state) override {auto gameState = std::dynamic_pointer_cast<TicTacToeState>(state);gameState->board[position] = player;}void undo(std::shared_ptr<IGameState> state) override {auto gameState = std::dynamic_pointer_cast<TicTacToeState>(state);gameState->board[position] = 0;}
};class TicTacToePlayer : public IPlayer {
private:int playerMark;public:explicit TicTacToePlayer(int mark) : playerMark(mark) {}std::vector<std::shared_ptr<IGameMove>> validMoves(std::shared_ptr<IGameState> state) override {auto gameState = std::dynamic_pointer_cast<TicTacToeState>(state);std::vector<std::shared_ptr<IGameMove>> moves;for (int i = 0; i < 9; i++) {if (gameState->board[i] == 0) {moves.push_back(std::make_shared<TicTacToeMove>(i, playerMark));}}return moves;}int eval(std::shared_ptr<IGameState> state) override {auto gameState = std::dynamic_pointer_cast<TicTacToeState>(state);// Check for win conditionsconst std::vector<std::vector<int>> lines = {{0,1,2}, {3,4,5}, {6,7,8}, // rows{0,3,6}, {1,4,7}, {2,5,8}, // columns{0,4,8}, {2,4,6}           // diagonals};for (const auto& line : lines) {int sum = 0;for (int pos : line) {sum += gameState->board[pos];}if (sum == 3 * playerMark) return 1000;if (sum == -3 * playerMark) return -1000;}return 0;}
};int main() {// Create initial game stateauto gameState = std::make_shared<TicTacToeState>();// Create playersauto player1 = std::make_shared<TicTacToePlayer>(1);  // X playerauto player2 = std::make_shared<TicTacToePlayer>(-1); // O player// Create evaluator with search depth of 4AlphaBetaEvaluation evaluator(4);// Make some moves to set up a game stategameState->board = {1, 0, -1,0, 1, 0,-1, 0, 0};// Get best move for player1auto bestMove = evaluator.bestMove(gameState, player1, player2);if (bestMove) {auto move = std::dynamic_pointer_cast<TicTacToeMove>(bestMove);std::cout << "Best move for Player 1 (X): position " << move->position << std::endl;// Execute the move to show the resulting boardmove->execute(gameState);std::cout << "\nResulting board:\n";for (int i = 0; i < 9; i++) {char symbol = gameState->board[i] == 1 ? 'X' : gameState->board[i] == -1 ? 'O' : '.';std::cout << symbol;if (i % 3 == 2) std::cout << "\n";}} else {std::cout << "No valid moves available\n";}return 0;
}