前段时间我接了个小活儿：帮朋友把一个只会乱下的井字棋程序调成“至少不输”的AI。第一反应当然是暴力枚举——把所有可能棋局都算一遍不就行了？原型写出来一跑，九宫格还能忍，一旦把棋盘换成稍微复杂点的棋类，分支因子和深度同时上去，局面数量直接爆炸。也就是在那个时候，我认认真真把 Alpha-Beta剪枝算法 和 极大极小值算法 从头捋了一遍，才发现这两个东西是成对出现的：剪枝是长在极大极小搜索这棵树上的一把剪刀，离开后者谈前者就是空中楼阁。
这篇文章写给三类人：打算写井字棋、五子棋、吃子棋这类小博弈AI的；做课设时被博弈树搜索折磨的；以及刷算法题时看到极大极小搜索相关题目就卡住的同学。我不打算给你一堆谁也看不懂的数学推导，而是按我自己调试程序时的真实路径来走：先搞懂为什么必须剪，再搞懂剪枝的本质，然后逐步拆伪代码、解题流程、实战优化，最后把我踩过的坑原样端出来。
1. 博弈树的组合爆炸：一个井字棋就能让暴力枚举露馅
先想清楚我们面对的问题到底是什么。下棋这类双人零和博弈，天然可以展开成一棵树：根节点是当前棋盘局面，每条边是一个合法走法，下一层是对手所有可能的应招，再下一层又是你的回手……一直到分出胜负或者达到我们规定的搜索深度。这棵树叫博弈树。
博弈树的规模由两个因素决定：分支因子 b 和深度 d，叶子节点数量大约是 b^d。这样说很抽象，我举几个例子你就明白了。
井字棋的终局数大约是 9! = 362880，这数字看着不大，所以全枚举勉强能跑。但一旦你把它改成六子棋、或者让棋盘稍微大一点，局面数立刻失控。五子棋在 15×15 棋盘上，初始分支因子接近 200，如果搜索深度到 10 层，200^10 就是一个连计算机都绝望的数字。国际象棋更夸张，统计意义上的分支因子约 35，五十个回合意味着 35^100 量级，全宇宙的原子加起来都不够存这些局面。
所以“把所有可能棋局都算出来”这条路，从工程上就是走不通的。那怎么办？两个办法组合起来：
第一，我们不一定要走到终局才判断优劣。可以设计一个“评估函数”，对当前未结束的局面给一个分数，分数正数表示对我方有利，负数表示对我方不利。这样我们就可以把搜索限制在有限深度内，到底后用评估函数代替“真实终局结果”。
第二，我们不需要真的把每个分支都搜到底。在搜索过程中，很多分支根据已有信息就已经能判断“不可能被选中”了，直接跳过即可。这就是 Alpha-Beta 剪枝。
于是你会看到，这三件事是一个递进关系：评估函数解决“怎么给局面打分”，极大极小值算法解决“在双方都理性时，我该选哪个走法”，Alpha-Beta 剪枝解决“哪些分支根本不用搜”。下面先解决中间这个问题。
2. 极大极小值算法：让程序学会“如果我是他，他会怎么选”
博弈树搜索的第一步，是理解什么叫“站在对手角度思考”。
假设我是 MAX 方，我追求分数最大化；对方是 MIN 方，对方追求分数最小化——这就是一个零和博弈：我赢一分，对方就输一分。基于这个设定，每个节点都可以归类：
- MAX 节点：轮到我走，我会从所有子节点里挑分数最大的那个；
- MIN 节点：轮到对手走，对手会从所有子节点里挑分数最小的那个。
递归地把这个过程从叶子节点一层层往上推，就是极大极小值算法。名字非常直白：上一层取极大，下一层取极小，交替进行。
给你一个生活化的类比。假设你要从两个箱子里选一个，选完之后由对手从箱子里再拿掉一些钱给他自己，最后剩下的才是你的。你不会只看箱子表面有多少钱，而是会想：“如果我选 A 箱，对手会怎么让我难受？如果我选 B 箱，对手又会怎么让我难受？然后我挑那个‘最难受的情况里稍微好一点’的箱子。”这个过程就是你不断把对手的“极小值”喂给上一层自己的“极大值”。
套到代码里就是：递归函数返回到达当前节点时，站在 MAX 方视角能拿到的分数。如果当前节点是 MAX 型，就对所有子节点的返回值取 max；如果是 MIN 型，就取 min。叶子节点直接返回评估函数的结果。这样一路返回到根节点，根节点得到的分数就是“双方都足够理性”的前提下，当前局面对我方的优势估计。
不过这里马上要面对一个问题：大部分真实棋类根本搜不到终局。你要是真等到分出胜负才搜完，搜索空间早爆了。所以实战中你会设定一个深度上限 depth，搜到 depth 为 0 时就停下来，调用评估函数给个静态分数。这个静态分数不需要很精确，只要相对局势强弱有意义就行：我子多、位置好，就返回正分；对方子多、有威胁，就返回负分。
到这里，极大极小值已经能给出正确的决策了。但它有一个明显的缺点：它会把整棵树全部搜完，哪怕很多分支在数学上已经不可能改变根节点的结论。想象一棵树有十万个叶子，其中九万九千九百个都在重复证明同一件事——“这个分支不可能赢过我已经发现的那个走法”。极大极小值算法会老老实实把它们全看一遍，而 Alpha-Beta 剪枝要做的，就是把这场无意义的加班取消掉。
3. Alpha-Beta剪枝的本质：α是你能保住的下限，β是对手压住的上限
先直接给结论：Alpha-Beta 剪枝并没有改变极大极小值的决策结果，它只是把“已经确定不会影响根选择的那些分支”提前丢掉。它靠两个量完成这件事：
- α（alpha）：当前已经搜索过的分支里，MAX 方至少能保证拿到的分数下界。初始值是负无穷。
- β（beta）：当前已经搜索过的分支里，MIN 方最多能让分数压到的上界。初始值是正无穷。
随着搜索进行，这两个值会不断收紧。MAX 节点负责抬高 α，MIN 节点负责压低 β。一旦出现 α >= β，就说明双方的底线已经“没有交集”了：MAX 已经有把握拿到至少 α 分，而 MIN 在这个分支里已经证明自己能压到低于 α 分。这个分支再搜下去也没有意义，因为它不可能被最终选中。于是剪枝。
这句话值得反复咀嚼。我打个比方：你手里已经有一个稳拿 7 分的方案（α=7）。现在你看另一个分支，发现对手在里面已经能把你的收益压到 5 分以下（β=5）。那这个分支剩下的所有招数你还需要关心吗？不需要了。因为哪怕后面有再奇怪的变化，对手只要坚持“最小化”的理性策略，这个分支在你视角里就不可能超过 5 分，永远超不过你已有的 7 分。
所以剪枝的具体方向是：
- 在 MAX 节点里，逐个搜索孩子，每拿到一个孩子返回值就尝试更新 α。如果某个孩子返回后 α >= β，那这个节点的后面几个兄弟全部剪掉。
- 在 MIN 节点里，逐个搜索孩子，每拿到一个孩子返回值就尝试更新 β。如果某个孩子返回后 β <= α，那这个节点的后面几个兄弟全部剪掉。
再强调一遍：剪枝是安全的。你剪掉的分支，在“双方都按理性最优来下”的前提下，绝不可能给出比当前界更好的结果。它不是启发式猜测，是严格的数学剪枝，不影响根节点最终选中的最优走法，只影响效率。
还有一个细节经常被问：剪枝条件到底用 > 还是 >=？
从正确性上讲，两者都能让最终选出的分数一致。实用中绝大多数写法都用 >=（MAX 层）和 <=（MIN 层），这样可以在相等情况下也剪掉分支，效率更高。唯一的差别是：当多个走法分数相同时，用 >= 可能倾向于保留先搜索到的那个走法，用 > 可能更晚才更新到后面的等价走法。这个差别不影响分数，但会影响“棋风偏好”，比如同样赢，一个先手赢还是后手赢的问题。后面我讲踩坑时会再提到。
4. 拿一棵三层小树手算一遍：看着 α 和 β 一步步变化
前面讲概念，可能还有人觉得虚。我们来手算一棵很小的树，把 α、β 的变化一行一行过一遍。完成这一步之后，你就再也不会把参数传反。
这棵树长这样：
根（MAX） / | \ A B C / | \ / | \ / | \ 3 17 8 9 7 12 14 5 2每个叶子节点上的数字，是对 MAX 方的静态评估分数。A、B、C 都是 MIN 节点，根是 MAX 节点。
先不加剪枝，只看极大极小值的结果。A 节点要取最小值，min(3, 17, 8) = 3。B 节点 min(9, 7, 12) = 7。C 节点 min(14, 5, 2) = 2。根节点取最大值，max(3, 7, 2) = 7。所以最佳走法是走 B，根节点的收益是 7。
下面看带剪枝的搜索过程。初始时 α = -∞，β = +∞。
第一步，进入根节点，开始搜索 A。 A 是 MIN 节点，当前 α = -∞，β = +∞。A 的第一个孩子是 3，MIN 候选值 v = 3，于是 β = min(+∞, 3) = 3。第二个孩子 17，v = 3 不变，β 仍是 3。第三个孩子 8，v 还是 3。A 返回 3，根节点收到后更新 α = max(-∞, 3) = 3。此时 α = 3。
第二步，搜索 B。 B 是 MIN 节点，α = 3，β = +∞。B 的第一个孩子是 9，MIN 候选 v = 9，β = 9。这时的检查条件是 β <= α？9 <= 3 不成立，所以不能剪。继续第二个孩子 7，v = 7，β = 7。注意 β 已经降到 7，它仍然大于 α=3，所以还是不能剪。继续第三个孩子 12，v = 7，β = 7。B 返回 7。根节点更新 α = max(3, 7) = 7。此时 α = 7。
第三步，搜索 C。 C 是 MIN 节点，α = 7，β = +∞。C 的第一个孩子是 14，v = 14，β = min(+∞, 14) = 14。检查 β <= α？14 <= 7 不成立，继续。第二个孩子是 5，v = min(14, 5) = 5，β = min(14, 5) = 5。现在检查 β <= α？5 <= 7 成立，于是 C 的第三个孩子 2 直接跳过，剪掉。C 返回当前候选值 5。
根节点拿到的 C 的返回值是 5，比已有的 7 小，所以最终仍然选择 B。搜索结束。
这里有一个初学者最容易疑惑的点：C 的真实值明明是 min(14, 5, 2) = 2，但剪枝版本里 C 返回的却是 5，这不会导致根节点误判吗？
不会。因为 C 是一个 MIN 节点，在搜索完 14 和 5 之后，C 的分数已经“被对手压到” 5 这个水平。第三个孩子不管是 2、100、还是 1000，只要对手是理性的，C 的最终值都不可能超过 5。既然 5 已经低于根节点的 α=7，那么 C 这个分支无论再搜出什么，都不可能打败已经搜索到的 B 分支。C 返回的“5”只是一个安全的保守上界，不是精确值，但这个保守值足以让根节点做出正确决定。这也是剪枝为什么敢剪的原因：宁可少知道一点，也不影响最终结论。
我建议你把这个小树原封不动地写进你的调试代码里，用打印日志的方式跟踪每个节点的 α、β，如果你的代码跑出来的过程和上面的记录完全一致，就说明你的搜索框架写的方向是对的。这个动作很小，但价值极大，能省掉后面无数玄学调错时间。
5. 伪代码逐行拆：从“只返回分数”到“真能选走法”
看完手算，现在可以上伪代码了。下面这个版本是“只返回分数”的经典结构，也是绝大多数教材里的样子：
INF = 10**9 def alpha_beta(node, depth, alpha, beta, maximizing): # 到达叶子节点：返回静态评估分数 if depth == 0 or node.is_terminal(): return evaluate(node, depth) if maximizing: value = -INF for child in node.children(): value = max(value, alpha_beta(child, depth-1, alpha, beta, False)) alpha = max(alpha, value) if beta <= alpha: break # MAX 节点触发 beta 剪枝 return value else: value = INF for child in node.children(): value = min(value, alpha_beta(child, depth-1, alpha, beta, True)) beta = min(beta, value) if beta <= alpha: break # MIN 节点触发 alpha 剪枝 return value这个版本看着简单，但有几个地方你必须想透，否则一到实战就会出问题。
第一，MAX 层更新的是 alpha，MIN 层更新的是 beta。这两个不能换。调用根节点时，alpha = -∞，beta = +∞。如果你写反，最典型的症状就是：剪枝数量几乎没有，搜索节点数跟没剪枝时一模一样，但结果碰巧还是对的（因为退化成普通极大极小值）。有时候结果错了，那就更惨。
第二，为什么剪枝检查放在alpha = max(...)和beta = min(...)之后？因为剪枝依赖的是“已经更新完的当前界”。你也可以在每个孩子返回值出来之后立刻判断if value >= beta: break（MAX 层）或if value <= alpha: break（MIN 层），效果等价。两种写法都行，但别混在一起写，容易乱。
第三，这个版本只返回分数，不返回走法。在实战里，根节点需要知道“我该走哪一步”，所以我们要在根节点外面再包一层调用：
def best_move(board, depth): best_score = -INF best = None for move in board.legal_moves(): board.do(move) score = alpha_beta(board, depth-1, -INF, INF, False) board.undo(move) if score > best_score: best_score = score best = move return best注意这里为什么要额外包一层，而不是直接改递归函数让它返回走法？因为在剪枝过程中，被剪掉的分支本来就没有必要保留完整的走法信息，我们真正关心的只有根节点这一层“哪个孩子的分数最大”。把“返回分数”和“根节点选走法”分离，代码更干净，也更好调试。
还有一个更简洁的写法叫负极大值（Negamax），利用零和博弈的对称性把 MAX 和 MIN 两种情况合并成一种：
def negamax(state, depth, alpha, beta): if depth == 0 or state.is_terminal(): return evaluate_from_current_side(state, depth) best = -INF for move in state.legal_moves(): state.do(move) score = -negamax(state, depth-1, -beta, -alpha) state.undo(move) best = max(best, score) if best >= beta: return best if best > alpha: alpha = best return best这个写法的核心是：在当前行动方看来，自己下一步之后，局面就变成对手做主，而“自己的收益”在对手眼里要取负号。所以递归时，返回值取负，且把 alpha、beta 交换位置后传下去。客观地说，这个写法代码少了很多，但理解起来门槛更高。新手上手先写标准极大极小，跑通之后再换负极大值不迟。
需要特别提一下：负极大值版本里的评估函数，必须返回“当前行动方”视角的分数。如果评估函数写了“MAX 方视角”，负极大值就会变成 AI 自己帮对手想办法，这属于负极大值最经典的翻车点。
6. 套到题目上的完整解题流程：状态、评估、搜索、顶层调用一个都不能少
把算法看懂，和能把它用到一道题、一个项目上，中间还隔着一层“解题流程”。我按自己写博弈搜索时的习惯，拆成五个步骤，照着这套流程走，基本不会漏东西。
6.1 第一步：状态表示与走法生成
先想清楚游戏状态怎么存。数组、二维矩阵、位运算都行，原则是：能够快速判断合法走法、快速执行一步、快速撤回一步。用位运算存棋盘的优点是快，但代码难读；用数组存则直观，适合课设和调试。我建议先保证“做对”，再考虑“做快”。走法生成函数对应伪代码里的children()，它在每一层都会被调用无数次，如果这一步写得太慢，整个递归全慢在重复枚举上。
还有个小建议：如果你的游戏状态本身是只读的，不要在递归里每次copy()一份新局面再往下传。正确做法是do / undo，也就是走一步、递归、再回退。这样能把内存分配和拷贝开销压到最低。
6.2 第二步：终局判断与评估函数
搜索到叶子节点时，第一件事是判断游戏是否已经结束，不是直接跑评估函数。如果当前局面已经分出胜负，直接返回一个足够大的正负分，比如 ±10^6。只有游戏还没结束，才调用评估函数打静态分数。
评估函数怎么设计？最简单的是按棋子的数量差、位置分、威胁数量来算。你不必追求一开始就非常精准，先让程序能把明显好的局面和明显坏的局面区分开，后面再迭代。有一点要特别注意：评估函数必须站在同一视角返回分数。你定成“正数对 MAX 有利”，那么整个搜索路径上都要保持不变，别在中途改视角。
如果你搜到的胜利有深有浅，还要处理“同样会赢，但我想赢得更快”的问题。常见做法是把胜利分数与搜索深度耦合：MAX 方获胜时返回WIN - depth，深度越小分数越高，这样 AI 会优先选择最快的取胜路线；MIN 方获胜时返回-WIN + depth，同样让对手越快赢的路线分数越差。这是实战中很重要但教科书很少细讲的细节。
6.3 第三步：递归搜索框架
把前面伪代码抄到你的具体状态上。建议在最开始就封装一个统一的搜索入口，比如search(board, depth, alpha, beta, maximizing)，不要在多个地方复制粘贴递归逻辑。调试时，我会额外打印“当前深度、当前节点、alpha、beta、候选分数、是否触发剪枝”，肉眼观察小规模局面是否符合手算结果。
6.4 第四步：顶层调用
也就是根节点的best_move。前面说过，根节点要额外遍历所有合法走法，逐个调用search，然后把分数最高的那个走法作为落子返回。如果你想让根节点也能在必赢时更早停下，可以在这里也检查一下剪枝条件，但绝大多数情况下不剪根节点也没关系。
6.5 第五步：手动推演验证
这也是我最推荐的一步。找一个规模足够小的局面，比如那颗三层小树，或一个三连棋残局，用手算和程序跑两遍，对比最终走法和分数是否一致。再打印搜索节点数的统计：加入剪枝后，节点数应当明显变少。如果剪枝前后节点数一样，大概率是 alpha、beta 更新方向错了，回去查第 5 章提到的那几个关键点。
7. 真正影响效率的实战三件套：走法排序、迭代加深与置换表
剪枝本身已经很强了，但实际项目里它还远远不够。我按实战里性价比从高到低排序，三件事是必须做的。
7.1 走法排序：剪枝效率完全由搜索顺序决定
Alpha-Beta 剪枝的效率非常依赖孩子的搜索顺序。如果第一个搜索的孩子恰好是最优走法，那么后面所有兄弟都能很快被剪掉，搜索量接近理论最优；如果顺序很差，最优走法排在最后，那前面的分支几乎每个都要搜到底，剪枝退化成普通极大极小值。
这就是为什么走法排序如此重要。明明同一个搜索算法，排序不同，速度可能差出几十倍甚至上百倍。常用启发式包括：先搜索吃子、先搜索能让对手被迫回应的威胁走法、优先棋盘中心附近的位置、先用上一次浅层搜索结果排出的主变化作为首选走法。这些都是经验排序，不需要保证绝对正确，只要“大概率把好招往前放”，剪枝效率就能起飞。
7.2 迭代加深：用有限时间尽量多搜一层
迭代加深的思路极其简单：先搜深度 1，再搜深度 2，再搜深度 3……一直搜到时间限制用完为止。每一层搜索都用上一层找到的最优走法作为本层的第一个候选走法，这样既给走法排序提供了一个天然的好起点，又能保证任何时间中断搜索，手头都有一个“当前允许深度下能找到的最好走法”。
这个技巧在你没有明确固定深度、而是有一个时间预算的比赛场景下特别好用。即使总时间不变，迭代加深也能比“一次性搜到固定深度”更强，因为它天然带了一个排序预热过程，前面浅层搜索的结果让后面的深层搜索变得非常便宜。
7.3 置换表：别把同一个局面反复搜两遍
博弈树里有大量局面会通过不同走法顺序到达。比如井字棋里，“先走中间再走左上”和“先走左上再走中间”到达的是同一个局面。用哈希表把这个局面在某深度下的搜索结果缓存起来，下次再遇到就直接返回，能省掉很多重复搜索。
棋类项目里最常用的是 Zobrist 哈希，它支持快速增量更新：走一步、改几个哈希值、撤销一步、再改回来。缓存条目里至少要有：局面哈希、搜索深度、分数、分数类型（精确值 / 下界 / 上界）、最佳走法。分数类型特别关键，因为剪枝产生的很多结果是“我至少能拿到 X”或“对方最多能压到 X”，这种上下界信息不能直接当精确值复用，需要配合比较后才能决定是否替换缓存。
这个三件套确实会增加代码量，但收益非常可观。通常我的迭代顺序是：先把搜索核心写对，然后加走法排序，再叠加迭代加深和置换表。每一步都要重新跑一遍正确性验证，避免优化把 bug 带进来。
8. 我踩过的坑和一条最想留下的经验
最后说点实际踩坑经历。前面讲的是“正确方法”，这里反过来，把容易出错的位置标出来。
第一个坑：alpha、beta 更新方向写反。我自己有一次调试一个吃子棋 AI，搜索节点数始终没有下降，打印日志才发现 MIN 层一直在更新 alpha 而不是 beta，导致剪枝条件永远不成立。这种现象非常隐蔽，因为结果不一定会错，只是效率极低，暴力的极大极小值也会给出同样的正确走法，所以很容易被忽略。后来我用三层小树手算对比日志，一眼就抓到了问题。
第二个坑：用整型最大值当正无穷。早期我图省事写INF = int(1e9)还觉得够大，后来在负极大值版本里，-negamax(...)一取负就溢出，程序直接乱套。更好的做法是用10**9这种“够大但不至于一取负就爆”的值，或者直接用 Python 这种大整数语言自带的数值类型。
第三个坑：剪枝条件用>而不是>=，或者反过来。症状是：效率和棋风异常。用>会少剪一些等价分支，结果仍然正确但偏慢；用>=则可能在多走法同分时更倾向先搜到的那个走法。这个小差别通常不需要纠结，但你得知道它的存在。
第四个坑：叶子节点只调评估函数，不检查胜负。有一回我搜到已经连成五五子棋的局面，评估函数却给了一个基数值，AI 不在制胜点上补最后一子，反而去别处落子。原因就是终局判断写在了评估函数后面，优先级反了。后来我改成：进入叶节点先判胜负，再考虑评估函数，问题立刻消失。
第五个坑：负极大值版本的评估视角。负极大值要求评估函数站在“当前行动方”的视角返回分数。如果你从旧的极大极小代码里直接把评估函数拷过来，它很可能仍然是 MAX 视角，结果就是 AI 每一步都在帮对手找最优解，越下越差。
如果只让我留一条经验，那就是：先把搜索核心写对，再用小树手算验证，最后才叠加优化。我后来每次写博弈搜索，都会先把第 4 章那棵小树在手边摆好，代码跑完日志出来，对着 α、β 的每一步变化看一眼，确认完全一致，才敢继续往下加功能。这个习惯帮我挡掉了无数次改完走法排序结果变得不如不改的尴尬情况。等核心正确了，再上走法排序、迭代加深、置换表，你会发现每一步优化都能稳定看到搜索节点数下降，也就能享受“同样的时间，搜得更深一层”的乐趣了。
