模型介绍
Alpha-Beta 剪枝是极小化极大算法（Minimax）的优化版本，用于两人零和博弈的决策树搜索。它通过剪枝来减少需要评估的节点数量，同时保证找到与 Minimax 算法相同的最优解。
核心思想：
- Alpha：MAX 玩家能保证的最低分数（下界）；
- Beta：MIN 玩家能保证的最高分数（上界）；
- 当发现某个分支不可能影响最终决策时，立即停止搜索该分支。
历史背景
Alpha-Beta 剪枝算法由 John McCarthy 在 \(1956\) 年提出，后来由多位研究者独立发现和完善。它已经成为博弈树搜索中最基础且最重要的优化技术，广泛应用于国际象棋、围棋等游戏的 AI 中。
核心原理与证明
Minimax 算法回顾
在两人零和博弈中：
- MAX 玩家试图最大化分数；
- MIN 玩家试图最小化分数；
- 每个节点的值由其子节点的值决定。
Minimax(node, depth, maximizingPlayer):if depth == 0 or node是终端节点:return 评估函数(node) if maximizingPlayer:value = -∞for 每个子节点:value = max(value, Minimax(child, depth-1, false))return valueelse:value = +∞for 每个子节点:value = min(value, Minimax(child, depth-1, true))return value
Alpha-Beta剪枝原理
- 关键观察：不需要搜索所有分支就能确定某些分支不会影响最终结果；
- 定义：
- \(\alpha\)：MAX 玩家在当前路径上能保证的最低分数；
- \(\beta\)：MIN 玩家在当前路径上能保证的最高分数；
- 剪枝条件：
- 在 MAX 节点：如果某个子节点的值 \(\ge\beta\)，可以剪掉剩余子节点；
- 在 MIN 节点：如果某个子节点的值 \(\le\alpha\)，可以剪掉剩余子节点。
算法正确性证明
- 定理：Alpha-Beta 剪枝不会影响 Minimax 算法的最终结果
- 证明：
- 情况1（MAX节点剪枝）：假设在 MAX 节点，当前 \(\alpha=5,\beta=8\)，已经搜索到某个子节点返回 \(7\)，此时发现另一个子节点返回 \(9(\ge\beta)\)。由于 MIN 玩家在父节点不会选择让 MAX 获得 \(\ge8\) 的分支，因此这个 \(\ge9\) 的分支不会被选择，可以安全剪枝。
- 情况2（MIN节点剪枝）：假设在 MIN 节点，当前 \(\alpha=5,\beta=8\)，已经搜索到某个子节点返回 \(6\)，此时发现另一个子节点返回 \(4(\le\alpha)\)。由于 MAX 玩家在父节点不会选择让 MIN 获得 \(le5\) 的分支，因此这个 \(\le4\) 的分支不会被选择，可以安全剪枝。
- 归纳证明：
- 基础：在叶子节点，评估值准确；
- 归纳：假设所有已搜索分支的值正确；
- 剪枝只发生在确定不会影响决策的情况下；
- 因此最终结果与完整 Minimax 相同。
代码实现
基础 Alpha-Beta 实现
#include <bits/stdc++.h>
#define int long longusing namespace std;// 博弈树节点
struct GameNode {int value; // 对于叶子节点是实际值，对于内部节点是计算值bool is_leaf;vector<GameNode*> children;GameNode(int val, bool leaf = false) : value(val), is_leaf(leaf) {}
};// 创建示例博弈树
GameNode* createExampleTree() {/*构建如下博弈树：MAX/ | \MIN MIN MIN/|\ |\ |\3 5 1 2 9 0 8*/// 叶子节点vector<GameNode*> leaves = {new GameNode(3, true), new GameNode(5, true), new GameNode(1, true),new GameNode(2, true), new GameNode(9, true), new GameNode(0, true),new GameNode(8, true)};// MIN节点GameNode* min1 = new GameNode(0);min1->children = {leaves[0], leaves[1], leaves[2]};GameNode* min2 = new GameNode(0);min2->children = {leaves[3], leaves[4]};GameNode* min3 = new GameNode(0);min3->children = {leaves[5], leaves[6]};// MAX节点（根节点）GameNode* root = new GameNode(0);root->children = {min1, min2, min3};return root;
}// Alpha-Beta搜索算法
int alphaBeta(GameNode* node, int depth, int alpha, int beta, bool maximizingPlayer) {// 叶子节点或达到深度限制if (node->is_leaf || depth == 0) {cout << "评估节点，返回值: " << node->value << endl;return node->value;}if (maximizingPlayer) {int value = INT_MIN;cout << "MAX节点，alpha=" << alpha << ", beta=" << beta << endl;for (GameNode* child : node->children) {value = max(value, alphaBeta(child, depth - 1, alpha, beta, false));alpha = max(alpha, value);cout << "MAX更新: value=" << value << ", alpha=" << alpha << endl;// Alpha剪枝if (alpha >= beta) {cout << "Alpha剪枝发生在MAX节点，alpha=" << alpha << " >= beta=" << beta << endl;break;}}node->value = value;return value;} else {int value = INT_MAX;cout << "MIN节点，alpha=" << alpha << ", beta=" << beta << endl;for (GameNode* child : node->children) {value = min(value, alphaBeta(child, depth - 1, alpha, beta, true));beta = min(beta, value);cout << "MIN更新: value=" << value << ", beta=" << beta << endl;// Beta剪枝if (beta <= alpha) {cout << "Beta剪枝发生在MIN节点，beta=" << beta << " <= alpha=" << alpha << endl;break;}}node->value = value;return value;}
}// 基础使用示例
void basicExample() {GameNode* root = createExampleTree();int result = alphaBeta(root, 3, INT_MIN, INT_MAX, true);cout << "最终结果: " << result << endl;
}
棋类游戏应用示例
#include <bits/stdc++.h>
#define int long long// 简单的井字棋实现
class TicTacToe {private:vector<vector<char>> board;char current_player;public:TicTacToe() : board(3, vector<char>(3, ' ')), current_player('X') {}// 评估函数int evaluate() {// 检查行for (int i = 0; i < 3; i++) {if (board[i][0] == board[i][1] && board[i][1] == board[i][2]) {if (board[i][0] == 'X')return 10;else if (board[i][0] == 'O')return -10;}}// 检查列for (int i = 0; i < 3; i++) {if (board[0][i] == board[1][i] && board[1][i] == board[2][i]) {if (board[0][i] == 'X')return 10;else if (board[0][i] == 'O')return -10;}}// 检查对角线if (board[0][0] == board[1][1] && board[1][1] == board[2][2]) {if (board[0][0] == 'X')return 10;else if (board[0][0] == 'O')return -10;}if (board[0][2] == board[1][1] && board[1][1] == board[2][0]) {if (board[0][2] == 'X')return 10;else if (board[0][2] == 'O')return -10;}return 0; // 平局}// 检查游戏是否结束bool isGameOver() {if (evaluate() != 0) return true;// 检查是否还有空位for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (board[i][j] == ' ') return false;}}return true;}// 获取所有合法移动vector<pair<int, int>> getLegalMoves() {vector<pair<int, int>> moves;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (board[i][j] == ' ') {moves.push_back({i, j});}}}return moves;}// 执行移动void makeMove(int i, int j) {board[i][j] = current_player;current_player = (current_player == 'X') ? 'O' : 'X';}// 撤销移动void undoMove(int i, int j) {board[i][j] = ' ';current_player = (current_player == 'X') ? 'O' : 'X';}// Alpha-Beta搜索找到最佳移动pair<int, int> findBestMove() {int best_val = INT_MIN;pair<int, int> best_move = {-1, -1};vector<pair<int, int>> moves = getLegalMoves();for (auto move : moves) {makeMove(move.first, move.second);int move_val = alphaBeta(0, false, INT_MIN, INT_MAX);undoMove(move.first, move.second);if (move_val > best_val) {best_val = move_val;best_move = move;}}return best_move;}private:// Alpha-Beta搜索核心int alphaBeta(int depth, bool is_max, int alpha, int beta) {int score = evaluate();// 如果游戏结束，返回评估值if (score == 10) return score - depth; // 倾向于快速获胜if (score == -10) return score + depth; // 倾向于延迟失败if (isGameOver()) return 0;if (is_max) {int best = INT_MIN;vector<pair<int, int>> moves = getLegalMoves();for (auto move : moves) {makeMove(move.first, move.second);best = max(best, alphaBeta(depth + 1, false, alpha, beta));undoMove(move.first, move.second);alpha = max(alpha, best);if (beta <= alpha) break; // Beta剪枝}return best;} else {int best = INT_MAX;vector<pair<int, int>> moves = getLegalMoves();for (auto move : moves) {makeMove(move.first, move.second);best = min(best, alphaBeta(depth + 1, true, alpha, beta));undoMove(move.first, move.second);beta = min(beta, best);if (beta <= alpha) break; // Alpha剪枝}return best;}}
};
变种题目与解法
变种 1：带移动排序的 Alpha-Beta
- 优化思路：先搜索可能更好的移动，增加剪枝机会
class OrderedAlphaBeta {private:// 移动排序函数vector<pair<int, int>> orderMoves(const vector<pair<int, int>>& moves,TicTacToe& game, bool is_max) {vector<pair<int, int>> ordered = moves;// 简单启发式：中心位置和角落位置更有价值auto heuristic = [](int i, int j) {if (i == 1 && j == 1) return 3; // 中心if (i == 0 || i == 2 || j == 0 || j == 2) return 2; // 边缘return 1; // 其他};sort(ordered.begin(), ordered.end(),[&](const pair<int, int>& a, const pair<int, int>& b) {return heuristic(a.first, a.second) > heuristic(b.first, b.second);});return ordered;}public:int alphaBetaWithOrdering(TicTacToe& game, int depth, bool is_max,int alpha, int beta) {int score = game.evaluate();if (score != 0 || game.isGameOver()) return score;vector<pair<int, int>> moves = game.getLegalMoves();moves = orderMoves(moves, game, is_max);if (is_max) {int best = INT_MIN;for (auto move : moves) {game.makeMove(move.first, move.second);int val = alphaBetaWithOrdering(game, depth + 1, false, alpha, beta);game.undoMove(move.first, move.second);best = max(best, val);alpha = max(alpha, best);if (beta <= alpha) break;}return best;} else {int best = INT_MAX;for (auto move : moves) {game.makeMove(move.first, move.second);int val = alphaBetaWithOrdering(game, depth + 1, true, alpha, beta);game.undoMove(move.first, move.second);best = min(best, val);beta = min(beta, best);if (beta <= alpha) break;}return best;}}
};
变种 2：迭代加深的 Alpha-Beta
- 优化思路：逐步增加搜索深度，结合时间控制
class IterativeDeepeningAlphaBeta {private:TicTacToe& game;int time_limit; // 毫秒public:IterativeDeepeningAlphaBeta(TicTacToe& g, int limit = 5000): game(g), time_limit(limit) {}pair<int, int> findBestMoveWithTimeLimit() {auto start_time = chrono::steady_clock::now();pair<int, int> best_move = {-1, -1};int depth = 1;while (true) {auto current_time = chrono::steady_clock::now();auto elapsed = chrono::duration_cast<chrono::milliseconds>(current_time - start_time);if (elapsed.count() > time_limit) break;int best_val = INT_MIN;vector<pair<int, int>> moves = game.getLegalMoves();for (auto move : moves) {game.makeMove(move.first, move.second);int move_val = alphaBeta(depth, false, INT_MIN, INT_MAX);game.undoMove(move.first, move.second);if (move_val > best_val) {best_val = move_val;best_move = move;}}depth++;}cout << "搜索深度: " << depth - 1 << endl;return best_move;}private:int alphaBeta(int depth, bool is_max, int alpha, int beta) {int score = game.evaluate();if (score != 0 || depth == 0 || game.isGameOver()) {return score;}vector<pair<int, int>> moves = game.getLegalMoves();if (is_max) {int best = INT_MIN;for (auto move : moves) {game.makeMove(move.first, move.second);best = max(best, alphaBeta(depth - 1, false, alpha, beta));game.undoMove(move.first, move.second);alpha = max(alpha, best);if (beta <= alpha) break;}return best;} else {int best = INT_MAX;for (auto move : moves) {game.makeMove(move.first, move.second);best = min(best, alphaBeta(depth - 1, true, alpha, beta));game.undoMove(move.first, move.second);beta = min(beta, best);if (beta <= alpha) break;}return best;}}
};
变种 3：记忆化 Alpha-Beta（Transposition Table）
- 优化思路：缓存已搜索位置的结果
class MemoizedAlphaBeta {private:struct TTEntry {int depth;int value;int flag; // 0=精确值, 1=下界, 2=上界};unordered_map<string, TTEntry> transposition_table;string getBoardKey(const TicTacToe& game) {// 简化版：实际应用中需要更好的哈希函数string key;// 这里应该实现一个合适的棋盘状态哈希return key;}public:int alphaBetaWithTT(TicTacToe& game, int depth, bool is_max,int alpha, int beta) {string key = getBoardKey(game);// 检查换位表auto it = transposition_table.find(key);if (it != transposition_table.end() && it->second.depth >= depth) {TTEntry& entry = it->second;if (entry.flag == 0) return entry.value;if (entry.flag == 1 && entry.value >= beta) return entry.value; // 下界if (entry.flag == 2 && entry.value <= alpha) return entry.value; // 上界}int score = game.evaluate();if (score != 0 || depth == 0 || game.isGameOver()) {return score;}int original_alpha = alpha;int original_beta = beta;vector<pair<int, int>> moves = game.getLegalMoves();if (is_max) {int best = INT_MIN;for (auto move : moves) {game.makeMove(move.first, move.second);best = max(best, alphaBetaWithTT(game, depth - 1, false, alpha, beta));game.undoMove(move.first, move.second);alpha = max(alpha, best);if (beta <= alpha) break;}// 存储到换位表TTEntry entry;entry.depth = depth;entry.value = best;if (best <= original_alpha)entry.flag = 2; // 上界else if (best >= original_beta)entry.flag = 1; // 下界elseentry.flag = 0; // 精确值transposition_table[key] = entry;return best;} else {int best = INT_MAX;for (auto move : moves) {game.makeMove(move.first, move.second);best = min(best, alphaBetaWithTT(game, depth - 1, true, alpha, beta));game.undoMove(move.first, move.second);beta = min(beta, best);if (beta <= alpha) break;}// 存储到换位表TTEntry entry;entry.depth = depth;entry.value = best;if (best <= original_alpha)entry.flag = 2; // 上界else if (best >= original_beta)entry.flag = 1; // 下界elseentry.flag = 0; // 精确值transposition_table[key] = entry;return best;}}
};