数据结构与算法分析：专题内容——人工智能中的寻路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算法剪除掉了大量的状态。

每个比较都说明了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 moves
        auto moves = player->validMoves(state);
        
        // If leaf node or no moves available, return evaluation
        if (ply == 0 || moves.empty()) {
            return MoveEvaluation(player->eval(state));
        }

        // Initialize best move with alpha
        MoveEvaluation best(alpha);

        // Try each move and update alpha
        for (const auto& move : moves) {
            // Execute move
            move->execute(state);
            
            // Recursively evaluate position
            MoveEvaluation me = alphabeta(ply - 1, opponent, player, -beta, -alpha);
            
            // Undo move
            move->undo(state);

            // Update alpha if better move found
            if (-me.score > alpha) {
                alpha = -me.score;
                best = MoveEvaluation(move, alpha);
            }

            // Pruning condition
            if (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 -1
    
    TicTacToeMove(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 conditions
        const 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 state
    auto gameState = std::make_shared<TicTacToeState>();
    
    // Create players
    auto player1 = std::make_shared<TicTacToePlayer>(1);  // X player
    auto player2 = std::make_shared<TicTacToePlayer>(-1); // O player
    
    // Create evaluator with search depth of 4
    AlphaBetaEvaluation evaluator(4);
    
    // Make some moves to set up a game state
    gameState->board = {
        1, 0, -1,
        0, 1, 0,
        -1, 0, 0
    };
    
    // Get best move for player1
    auto 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 board
        move->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;
}

五、引用及参考文献

1.《算法设计手册》