决策树与博弈树：从概念到剪枝优化
说实话，决策树和博弈树这两个概念，在我刚入行那会儿总觉得离实际开发很远。直到有一次做AI下棋程序，才真正体会到它们的威力。今天咱们就来聊聊这个话题。
一、决策树的基本概念
决策树，说白了就是一种树形结构。每个内部节点代表一个决策点，每个分支代表一个选择，叶子节点就是最终结果。
我举个例子你就明白了。比如你要决定周末去哪玩：
- 先看天气（根节点）
- 天气好 → 去公园（分支1）
- 天气不好 → 去商场（分支2）
- 到了公园，再决定是散步还是野餐（子节点）
这就是一个典型的决策树。每个节点都在问一个问题，根据答案走向不同的分支。
核心要点：决策树的关键在于「分而治之」——把一个大问题拆成一系列小决策。
二、博弈树：当决策遇到对手
博弈树是决策树的升级版。区别在哪？决策树只有你一个人在决策，博弈树里有对手在跟你对着干。
我记得第一次写五子棋AI时，就遇到了这个问题。你走一步，对手走一步，双方都想赢。这时候就需要博弈树来建模。
博弈树的特点：
- 节点代表游戏状态
- 边代表玩家走法
- 层数交替：MAX层（我方）和MIN层（对手）
- 叶子节点是终局状态（赢/输/平）
小技巧：写博弈树时，我习惯把评估函数单独抽出来。这样换游戏规则时，只需要改评估函数，树的结构不用动。
三、极小极大算法
极小极大算法是博弈树的核心算法。它的思路其实很朴素：
「我走一步，要选对我最有利的。但对手也会走对他最有利的，也就是对我最不利的。」
所以算法是这样工作的：
- MAX层：选子节点中评估值最大的
- MIN层：选子节点中评估值最小的
- 递归进行，直到叶子节点
来看个简单代码实现：
int minimax(Node* node, int depth, bool isMax) {
// 到达叶子节点或指定深度
if (depth == 0 || node->isLeaf()) {
return evaluate(node);
}
if (isMax) {
int best = -INF;
for (int i = 0; i < node->childCount; i++) {
int val = minimax(node->children[i], depth-1, false);
best = max(best, val);
}
return best;
} else {
int best = INF;
for (int i = 0; i < node->childCount; i++) {
int val = minimax(node->children[i], depth-1, true);
best = min(best, val);
}
return best;
}
}注意：极小极大算法有个致命问题——搜索空间爆炸。比如国际象棋，平均每步有35种走法，搜索10步就是35^10 ≈ 2.7×10^15种状态。这谁受得了？
四、Alpha-Beta剪枝原理
Alpha-Beta剪枝就是来解决上面那个问题的。它的核心思想是：有些分支根本不用看。
为什么会这样？你想想看：
- 假设MAX层已经找到一个走法，评估值是10
- 现在看另一个分支，发现对手（MIN层）能走到评估值5
- 那MAX层肯定不会选这个分支，因为5比10差
- 所以这个分支剩下的子节点都不用看了
这就是剪枝。Alpha是MAX层当前最好的值，Beta是MIN层当前最好的值。
剪枝规则：
- 如果某个节点的值 ≤ Alpha，剪掉（对MAX层没用）
- 如果某个节点的值 ≥ Beta，剪掉（对MIN层没用）
代码实现：
int alphaBeta(Node* node, int depth, int alpha, int beta, bool isMax) {
if (depth == 0 || node->isLeaf()) {
return evaluate(node);
}
if (isMax) {
int best = -INF;
for (int i = 0; i < node->childCount; i++) {
int val = alphaBeta(node->children[i], depth-1, alpha, beta, false);
best = max(best, val);
alpha = max(alpha, best);
if (beta <= alpha) {
break; // Beta剪枝
}
}
return best;
} else {
int best = INF;
for (int i = 0; i < node->childCount; i++) {
int val = alphaBeta(node->children[i], depth-1, alpha, beta, true);
best = min(best, val);
beta = min(beta, best);
if (beta <= alpha) {
break; // Alpha剪枝
}
}
return best;
}
}实际效果：Alpha-Beta剪枝在理想情况下，能把搜索量从O(b^d)降到O(b^(d/2))。也就是说，同样的计算量，搜索深度可以翻倍。我在做棋类AI时，这个优化直接让程序从「弱鸡」变成了「能打」。
五、知识体系总览
下面这张图把本章的核心内容串起来了：
我的经验：Alpha-Beta剪枝的效果跟节点搜索顺序关系很大。如果每次都能先搜到好的分支，剪枝效率会高很多。我一般会先用启发式评估给子节点排个序，好的放前面。这样剪枝率能到90%以上。
六、避坑指南
做博弈树相关项目时，有几个坑我踩过：
- 评估函数设计不当：我曾经写过一个五子棋评估函数，只算了当前局面，没考虑潜在威胁。结果AI像个瞎子，明明对手要赢了还看不见。
- 搜索深度不够：深度太浅，AI只能看到眼前几步。我建议至少搜到6层以上，配合Alpha-Beta剪枝，性能完全扛得住。
- 忘记处理平局：有些游戏平局是常态，评估函数里一定要给平局一个合理的分值，不然AI会乱走。
特别注意：Alpha-Beta剪枝不会改变搜索结果！它只是砍掉了那些「肯定不会被选」的分支。如果你发现剪枝后结果变了，那一定是代码写错了。
好了，决策树和博弈树的核心内容就这些。从决策树到博弈树，再到极小极大算法和Alpha-Beta剪枝，每一步都是环环相扣的。理解了这个脉络，写AI程序时心里就有底了。
公众号:蓝海资料掘金营，微信deep3321