极大极小值算法与Alpha-Beta剪枝：棋类博弈搜索核心解析

写一个会下棋的 AI 难吗如果只靠暴力枚举哪怕是一盘井字棋顶多 9! 种走法还能忍换到五子棋、国际象棋分支因子一下子爆炸普通程序根本算不完。这时候就得回到博弈树搜索的老套路极大极小值算法是骨架Alpha-Beta 剪枝是让骨架跑得动的核心优化。这两个概念是很多棋类 AI、策略游戏 AI、甚至决策系统的基础网上资料不少但大多只给一段伪代码没讲清楚“为什么这样做”“参数怎么传”“剪枝到底剪掉了什么”。这篇文章我会从头到尾把思路、伪代码、解题流程拆开揉碎讲一遍还会附上我自己实际写博弈程序时踩过的坑希望对刚接触博弈树搜索的同学有帮助也适合想复习算法细节的人。1. 初始思路先想清楚搜索要解决什么问题1.1 博弈树建模是第一步博弈类问题天然适合用树来建模。任何一个局面都是一个节点从当前局面出发当前玩家每一步合法操作都会产生一个子节点这个子节点又轮到对手操作继续往下展开直到分出胜负或者达到人为设定的搜索深度。这棵树就是博弈树。我最早接触极大极小值算法时第一反应是“这不就是暴力搜索所有可能走法嘛”确实如此但它的关键不在于暴力而在于如何从叶子节点往回倒推。叶子节点是终局可以直接打分我赢就是正分我输就是负分平局是零分。如果还没到终局就需要一个评估函数把一个局面换算成一个数值这个数值越正代表对我越有利。这里有个容易懵的地方博弈双方立场相反。极大极小值算法就是假设“我”永远是极大化玩家也就是每一层都试图让评估值最大“对手”是极小化玩家每一层都试图让评估值最小。也就是说走一步棋的时候不光要考虑我这步能得到多高的分数还要考虑对手下一步会想办法把这个分数压下去。1.2 为什么评估函数决定了算法上限评估函数是整个搜索算法的“视力”。搜索再深如果评估函数是瞎的最后选出来的棋也不会好。初学的时候很容易把注意力全放在剪枝上结果换了一个评估函数胜率反而大幅波动其实就是评估函数没设计好。评估函数本质上是对局面优势的量化。比如在棋类里最常见的做法是给每个棋子设定基础价值然后加上位置性的附加分比如控制中心格子加几分、吃掉对方一个活跃棋子减几分等。对于非棋类场景评估函数可以是任何能刻画“当前状态下谁占优”的指标比如资源数量差、距离目标的剩余步数等。需要注意评估函数必须和搜索深度配合。深度浅的时候评估函数必须更敏锐否则在一个平静的局面下看不出优劣深度深的时候评估函数反而不需要太精细因为搜索本身就能看到更远的战术变化。1.3 理想的剪枝目标把无用分支砍掉极大极小值搜索的问题在于分支因子太大往往导致计算量爆炸。Alpha-Beta 剪枝的意义就是在不影响最终决策的前提下把那些不可能影响根节点选择的子树整个砍掉。说直白点有一个分支已经能确定当前节点不可能是最优选择那它下面的子树完全没必要继续搜。理解剪枝的关键是意识到搜索顺序决定剪枝效率。如果每个节点都能先检查最可能产生最优结果的分支剪枝率会接近理论极限也就是可以把有效搜索范围压缩到原来的平方根量级。如果顺序很差剪枝几乎不发生Alpha-Beta 剪枝退化成完整极大极小值搜索。这也是为什么正经棋类引擎都要配合启发式排序先把吃子、将军、关键位置变化这类走法排在前面。2. 核心机制解析极大极小值算法与 Alpha-Beta 剪枝原理2.1 极大极小值算法的递推逻辑极大极小值算法的核心逻辑是一个自底向上的递推过程。叶子节点的值来自评估函数内部节点的值由它的所有子节点值决定如果是 MAX 节点当前玩家是最大化者节点值取所有子节点值的最大值如果是 MIN 节点对手是最小化者节点值取所有子节点值的最小值。为什么必须轮流转置 max/min因为棋类游戏是回合制的。我在这一回合拥有主动权肯定选让自己优势最大的走法但一旦我走完主动权到了对手手里他会选让我优势最小的走法。这种交替取最大、取最小的过程正好刻画了真实博弈中的攻防转换。实现极大极小值算法时常见做法是在递归函数里传一个布尔值is_maximizing根据它判断当前节点取 max 还是 min。初始调用从根节点开始根节点的角色由当前轮到谁走决定。如果是程序自己走根节点就是 MAX 节点如果是对手走根节点就是 MIN 节点。从复杂度上看完整极大极小值搜索的复杂度是 O(b^d)b 是平均分支因子d 是搜索深度。比如说五子棋平均分支因子约 20 到 30搜索深度 6 层那就是 20^6约 6400 万个节点单机跑起来已经比较吃力。这个复杂度说明在真实项目里极大极小值算法很少单用必须配合剪枝和优化。2.2 Alpha 和 Beta 到底在传递什么Alpha-Beta 剪枝的核心是两个边界值alpha 是当前 MAX 节点已经确保可以拿到的最低分数初始是负无穷beta 是当前 MIN 节点已经确保可以给出的最高分数初始是正无穷。搜索过程中alpha 只能不断变大表示 MAX 玩家的保底分数在抬高beta 只能不断变小表示 MIN 玩家的封顶分数在压低。当 alpha beta 时当前节点已经没有任何继续探索的价值因为 MAX 玩家至少能拿到 alpha 分而 MIN 玩家最多只愿意给出 beta 分且 beta 小于 alpha说明这条路径对任何一方都没有吸引力再往下搜只会浪费时间直接剪掉。我见过不少初学者把 alpha 和 beta 理解成“窗口”这个类比其实很贴切。每一步搜索都相当于在一个不断缩小的数值窗口里找答案。窗口没关闭时继续搜窗口一旦关闭也就是 alpha beta就立即停手。这个窗口的初始大小决定了剪枝效率窗口越大剪枝越晚窗口越小剪枝越早但窗口小到把正确答案也排除在窗口外结果就会出错。2.3 标准伪代码逐行拆解下面这份伪代码是最常见的 Alpha-Beta 剪枝实现采用递归形式返回当前局面的评估值。它同时也是一个完整的解题模板可以直接改造成实际代码。def alphabeta(node, depth, alpha, beta, maximizing_player): if depth 0 or node.is_terminal(): return evaluate(node) if maximizing_player: value float(-inf) for child in node.get_children(): value max(value, alphabeta(child, depth - 1, alpha, beta, False)) alpha max(alpha, value) if alpha beta: break return value else: value float(inf) for child in node.get_children(): value min(value, alphabeta(child, depth - 1, alpha, beta, True)) beta min(beta, value) if alpha beta: break return value这段代码有几个细节必须说清楚。第一alpha和beta在递归传递时是不对称的MAX 节点更新 alphaMIN 节点更新 beta但两个分支都会把当前最新的 alpha 和 beta 继续传给下一层。原因在于下一层的搜索需要知道本层上下文的边界信息也就是说MAX 节点在搜索某个子节点时已经知道了其他兄弟节点的保底分数它可以用这个信息提前判断是否应该继续搜下去。第二break语句只在两处出现一处在 MAX 节点一处在 MIN 节点但判断条件都是alpha beta。MAX 节点里这个叫 beta 剪枝因为当前节点值已经大于等于 beta 了再搜下去 MIN 玩家不会选择这条路MIN 节点里这个叫 alpha 剪枝因为当前节点值已经小于等于 alpha 了再搜下去 MAX 玩家也不会选择这条路。第三返回值是局面评估值不是走法本身。实际落地时需要另写一个包装函数在根节点遍历所有合法走法调用这次递归函数拿到每个走法对应的评估值然后从中选出最大值对应的走法。这个过程我会在后面的解题流程部分详细展开。2.4 负极大值表示法一种更简洁的等价写法在真正的博弈引擎里很多人不用上面的双分支写法而是用负极大值算法它利用了一个数学性质MAX 节点取最大值等价于 MIN 节点取负值再取最大值。这样代码可以合并成一个统一的分支结构更简洁也更容易维护。def negamax(node, depth, alpha, beta): if depth 0 or node.is_terminal(): return evaluate(node) value float(-inf) for child in node.get_children(): score -negamax(child, depth - 1, -beta, -alpha) value max(value, score) alpha max(alpha, score) if alpha beta: break return value负极大值版本的写法里alpha 和 beta 的传参是(-beta, -alpha)注意顺序颠倒了。原因在于子节点的视角是对方原本是最大值玩家的 alpha 边界在对方看来就要取负并变成 beta 边界。这个旋转逻辑初看很难接受但只要记住一句话子节点评估值的相反数就是父节点视角下的分数。这个版本在工程上特别实用因为它天然支持多玩家博弈的扩展代码量也少很多。3. 完整解题流程从题目到可运行的博弈搜索程序3.1 解题步骤概览用 Alpha-Beta 剪枝解决一个具体博弈问题通常分五个步骤定义局面状态、实现状态生成器和终结判断、设计评估函数、编写递归搜索、包装决策函数。很多人直接在第四步开始写递归前面几步很随意后面调试时才发现状态生成器漏了合法走法或者评估函数符号搞反排查起来非常痛苦。先从状态定义说起。状态必须能完整刻画当前局面并支持两个操作得到当前玩家的所有合法走法以及判断是否终结。如果状态设计不好后面每个环节都要跟着返工。一个实用的原则是用不可变数据或者深拷贝来传递状态避免递归过程中子节点互相污染。3.2 一个完整示例简化井字棋的决策流程我用一个简化版的井字棋来演示这个过程。井字棋棋盘是 3x3玩家分别是 X 和 O最先连成三点一线的一方获胜。给定一个局面要做的事就是选出最佳落子位置。状态表示用一维数组长度为 9每个位置有 0、1、2 三种状态0 代表空1 代表 X2 代表 O。状态生成器遍历数组把所有值为 0 的位置作为可落子位置每个位置生成一个新数组把当前位置改为当前玩家编号。终结判断检查八条胜利线如果任意一条线上是同一个非零玩家则返回获胜者如果数组中没有 0则返回平局。评估函数在这个例子里可以非常简单如果当前节点已经分出胜负返回一个固定的大分数比如获胜返回 10失败返回 -10平局返回 0。由于深度较浅不需要额外的位置评估。实际使用时为了鼓励快速取胜还可以给获胜分数减去当前深度让程序优先选择更快的胜法这个技巧叫深度惩罚。决策函数在根节点遍历所有合法走法对每个走法调用负极大值递归记录分数最高的走法并返回。这一步要注意程序视角和评估函数视角必须保持一致。如果评估函数是从 X 的角度打分那么轮到 O 搜索时就要通过负极大值的符号反转来体现立场。3.3 逐层理解递归调用过程假设当前轮到 X搜索深度设为 3。根节点调用negamax(node0, 3, -inf, inf)它会遍历 9 个空位。第一个空位落子后生成子节点 node1递归调用negamax(node1, 2, -inf, inf)注意此时视角翻转轮到 O 走。node1 内部遍历 O 的合法走法生成 node2再递归调用negamax(node2, 1, -inf, inf)轮到 X 走。node2 内部继续遍历 X 的走法到达深度 0返回评估值。假设 node2 的第一个走法让 X 直接连成三线评估值返回 10。回到 node2 的循环里score -10取最大后 value 是 -10这会更新 alpha 为 -10然后 break 条件判断alpha beta此时 alpha 是 -10beta 是正无穷不剪枝继续搜下一个走法。如果最后一个走法也都是 X 获胜value 保持 -10。接着回到 node1它是 O 的视角拿到 node2 的返回值 10取负后 score 是 -10value 更新为 -10alpha 也更新为 -10。由于 beta 还是正无穷继续看其他 O 的走法。这个例子中由于其中一边深度只有 3很多剪枝触发不了但整个流程的逻辑是清晰的每层的返回值都会经过符号翻转层数越多立场交替越明显。3.4 把伪代码改造成真代码的要点伪代码到实际代码之间的沟壑往往比想象中要大。第一个坑是递归深度限制。Python 默认递归深度约 1000如果搜索深度超过这个值必须手动设置sys.setrecursionlimit或者改写成迭代式搜索否则程序会在某次递归时直接崩溃。第二个坑是状态拷贝开销。如果每次生成子节点都深拷贝整个局面搜索速度快不起来。井字棋这种小棋盘问题不大但应用到围棋、黑白棋这类棋盘较大的游戏就必须用“落子-撤销”的增量更新方案也就是在原状态上临时落子、递归、然后撤销避免反复拷贝。第三个坑是评估函数的调用频率。评估函数在叶子节点被大量调用它的性能直接影响整体速度。比如说如果在评估函数里加了一个复杂的启发式算法每次搜索叶子节点都要算一遍速度会断崖式下降。我自己的习惯是评估函数只做简单算术不在里面做搜索或排序。4. 常见问题与排查技巧把踩过的坑一次说清4.1 剪枝从未触发搜索慢到无法接受这是 Alpha-Beta 刚开始跑时最常遇到的问题。如果你发现运行时间和完整极大极小值搜索一模一样说明剪枝一次都没触发。原因几乎总是搜索顺序问题程序每次都在搜索一个价值极差的分支导致 alpha 和 beta 边界始终无法收敛。解决办法是引入走法排序。在棋类程序里可以用静态启发先把吃子、将军、中心控制、上一步有响应价值的走法排在前面。即便排序不完全准确剪枝效率也能大幅提升。我见过一个简单的排序策略给每种走法预先设定一个权重值从高到低排序效果立竿见影搜索时间直接缩短了 60% 以上。还有一个容易被忽略的原因是 alpha、beta 初始值传错了。如果 MAX 节点初始 alpha 被设成一个很大的正数或者 MIN 节点初始 beta 被设成一个很小的负数窗口一开始就是关闭的第一层就直接剪光所有分支返回结果必然错误。确定初始值的方法是MAX 用负无穷MIN 用正无穷。4.2 搜索深度增加棋力反而下降这个现象在初学者项目里出现过很多次。理论上搜索越深棋力应该越强但实际测试时深度 4 比深度 2 胜率高的同时深度 5 可能反而输多赢少。这通常叫水平效应是搜索深度截断造成的。水平效应的本质是搜索在不稳定的局面处突然截止评估函数又无法识别潜在的后续威胁于是程序以为当前的估计已经足够好实际是片面的。典型例子是井字棋深一层能看到被双三连击浅一层只看到自己连成三线于是死守一个空位反而忽略对方的威胁。缓解方案有三种一是搜索到深度边界附近时额外做静态搜索只搜索吃子或将军相关的走法二是使用延伸搜索当出现关键走法时自动加深几层三是评估函数不要只看静态棋子价值要加入对威胁格子的敏感度。4.3 程序视角反了总在帮对手走棋如果程序屡屡走出“送分棋”优先怀疑视角问题。负极大值算法里视角翻转是靠返回值取负完成的但这里涉及的“立场”只有在递归各层之间保持一致才有效。排查方法是选一个简单终局比如井字棋只剩一步可以获胜的局面手动模拟程序搜索过程查看返回分数和选择的落子位置。如果程序在 MAX 层选了最小值对应的走法说明取 max 的逻辑被写成了取 min如果在返回时少了负号说明符号翻转失效。我建议在调试时临时打印每个合法走法的分数对照手工计算。一旦确认视角正确这类问题很快就能定位。4.4 搜索深度太深导致栈溢出递归式搜索遇到深度 20 以上或者搜索树规模极大时栈溢出风险很高。除了调高递归深度限制更根本的解决方法是改用迭代深化的方式让深度逐层增加每层都重新搜索一遍。这样做看似浪费时间但结合置换表缓存实际效率非常高。迭代加深还有一个额外好处可以随时用“当前已搜索完的最深结果”作为答案方便控制每步思考时间。很多棋类引擎都采用固定的思考时间限制时间到了立即返回当前最佳走法这就是迭代加深带来的灵活性。我提一下置换表。置换表是一个哈希表以局面哈希作为 key缓存该局面的搜索深度、评估值和对应走法。它解决的是不同路径可能到达相同局面的问题也就是所谓的“转换”。迭代加深配合置换表可以让不同深度之间的搜索结果互相复用大幅减少重复搜索。5. 工程实践中的进阶技巧让算法真正跑得更快5.1 启发式走法排序的常用套路Alpha-Beta 剪枝的效率高度依赖走法排序排序越好剪枝越早搜索树越窄。棋类程序里常见几种排序策略吃子走法优先用“被吃棋子价值 - 吃子棋子价值”做个简单贪心上次迭代加深搜索时的最佳走法优先这个叫“杀手走法”将军走法优先因为将军通常会给对手造成压力最后才是普通走法。到五子棋这类分支很多的游戏走法排序还可以加入对中心区域的偏好、对已有连子方向的延伸偏好。实测下来排序只要不太离谱搜索时间可以差一个数量级。为什么这么明显因为排在前面的走法一旦让 alpha 快速抬高后续大量分支会在很浅的深度就被剪掉。5.2 迭代加深与时间控制真实对局里每步棋允许思考的时间是有限的。用固定深度搜索容易超时用浅深度搜索又可能计算不足。解决办法是迭代加深从深度 1 开始搜搜完一层提高深度直到时间耗尽。迭代加深每层都从头开始看似浪费实际上配合置换表和杀手走法缓存后上一层的结果可以为下一层提供很好的走法排序所以总耗时比一次性搜到最大深度要节省很多。而且时间控制极其自然哪怕只来得及搜到深度 4也有一个“当前最优解”如果时间充裕继续搜到深度 5、6。我自己的实践经验是迭代加深写好后几乎不需要手动调搜索深度。设定一个时间阈值比如 1 秒或 3 秒程序自动决定搜索深度非常省心。5.3 评估函数设计的常见误区评估函数不是越复杂越好。评估设计得过于复杂又会引入噪声导致搜索在不同深度下对同一局面的判断不稳定。一个稳定的评估函数应该满足单调性同一局面的同一视角不会因为搜索深度的微小变化出现截然相反的价值判断。在设计评估函数时要明确它服务的对象是谁。常见误区包括忘了评估函数是给叶子节点打分不是给整条路径打分把搜索深度或到达该节点花掉的步数错误地混入评估值以及忽略了防守端的价值只奖励进攻导致程序只顾着进攻、忽视防守。还有一个很多人忽视的点评估函数的取值范围要和 alpha、beta 的初始值匹配。如果评估值理论上最大值才 100但初始 alpha 用了负 10000虽然在正确性上没影响但会让边界更新缓慢剪枝变得迟钝。把边界设置成贴近真实评估范围的上下限能让剪枝更快触发。5.4 从棋盘游戏到通用决策系统的迁移Alpha-Beta 剪枝不只适用于棋类。任何可以用博弈树建模的决策问题都可以套用这个框架。典型例子包括商业竞价的模拟两方轮流出价需要判断怎么出价能让最终收益最大资源分配问题多个决策者轮流选择资源需要考虑对手的反应甚至一些扑克类简化版 AI在限制信息完全可见时也可以用搜索方法来决策。迁移的关键是三个抽象接口状态表示、合法动作生成、评估函数。只要这三个接口定义清楚极大极小值和 Alpha-Beta 剪枝就能直接复用。这个抽象思维比算法本身更重要因为在实际工程中更多时间都花在接口设计和状态建模上。6. 几个值得动手实践的小项目如果看完上面的内容还是觉得“纸上得来终觉浅”我强烈建议挑下面几个项目动手练一练。第一个是井字棋它是最简博弈模型状态空间小到可以直接枚举所有局面适合验证算法正确性和剪枝逻辑。写完之后可以在节点计数上对比有剪枝和无剪枝的搜索节点数量直观感受剪枝威力。第二个是简化版黑白棋或五子棋这类游戏分支因子更大棋力差距更明显适合实践走法排序、迭代加深、置换表等进阶优化。五子棋的评估函数设计空间也很大可以用机器学习方法来学习评估值不过那是另一个话题。第三个是自写一个双人卡牌对战的简化版比如双方各有几张手牌轮流出牌比点数这种问题概念上和棋盘类完全一致但更能训练抽象建模能力因为它没有现成的棋盘结构可以参考。我个人在带新人入门时经常用井字棋起步然后要求把它扩展到 4x4 连珠棋靠这个方式强迫大家理解“如何将小棋盘改造成大棋盘而不破坏搜索框架”。经过这个台阶再上五子棋或其他博弈题就毫无压力。7. 最后分享一点个人经验我最初写 Alpha-Beta 剪枝时犯过最严重的错误是没有写节点计数导致完全无法判断剪枝是否生效。后来养成了习惯只要写递归搜索就在函数入口加一行全局计数器自增然后在根节点打印最终计数。这个习惯陪我排查了无数个蠢问题。如果你现在正在调试两三个小时没跑出结果的棋类程序我建议先别急着优化剪枝先用一个很小的搜索深度跑通全部流程确认每个返回值和手动计算一致再逐步加大深度。基础不稳后面每一层优化都会变成垃圾堆上的劣质补丁。动手写一个自己的棋类 AI是理解这类搜索算法最快的路。等你的程序能够在固定时间内给出稳定且合理的走法回看这段代码能发现你已经把递归、搜索、估值、优化这些概念全串起来了。能串起来才算真正掌握。