Alpha-Beta剪枝与极大极小值算法：博弈树搜索原理与实战优化

前段时间我接了个小活儿帮朋友把一个只会乱下的井字棋程序调成“至少不输”的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 的第一个孩子是 3MIN 候选值 v 3于是 β min(∞, 3) 3。第二个孩子 17v 3 不变β 仍是 3。第三个孩子 8v 还是 3。A 返回 3根节点收到后更新 α max(-∞, 3) 3。此时 α 3。第二步搜索 B。 B 是 MIN 节点α 3β ∞。B 的第一个孩子是 9MIN 候选 v 9β 9。这时的检查条件是 β α9 3 不成立所以不能剪。继续第二个孩子 7v 7β 7。注意 β 已经降到 7它仍然大于 α3所以还是不能剪。继续第三个孩子 12v 7β 7。B 返回 7。根节点更新 α max(3, 7) 7。此时 α 7。第三步搜索 C。 C 是 MIN 节点α 7β ∞。C 的第一个孩子是 14v 14β min(∞, 14) 14。检查 β α14 7 不成立继续。第二个孩子是 5v 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 层更新的是 alphaMIN 层更新的是 beta。这两个不能换。调用根节点时alpha -∞beta ∞。如果你写反最典型的症状就是剪枝数量几乎没有搜索节点数跟没剪枝时一模一样但结果碰巧还是对的因为退化成普通极大极小值。有时候结果错了那就更惨。第二为什么剪枝检查放在alpha max(...)和beta min(...)之后因为剪枝依赖的是“已经更新完的当前界”。你也可以在每个孩子返回值出来之后立刻判断if value beta: breakMAX 层或if value alpha: breakMIN 层效果等价。两种写法都行但别混在一起写容易乱。第三这个版本只返回分数不返回走法。在实战里根节点需要知道“我该走哪一步”所以我们要在根节点外面再包一层调用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 章那棵小树在手边摆好代码跑完日志出来对着 α、β 的每一步变化看一眼确认完全一致才敢继续往下加功能。这个习惯帮我挡掉了无数次改完走法排序结果变得不如不改的尴尬情况。等核心正确了再上走法排序、迭代加深、置换表你会发现每一步优化都能稳定看到搜索节点数下降也就能享受“同样的时间搜得更深一层”的乐趣了。