简介基于α-β剪枝实现五子棋人机对战的Python小游戏面向正在学习博弈树搜索、想通过具体项目理解极大极小值算法与剪枝策略的Python开发者也适合作为人工智能课程设计或算法练手项目。资源包含完整可运行的py源码与配套说明共3个文件压缩包仅15KB两个py文件分别承载主程序与按钮交互界面txt文件对代码结构及运行环境做了简要说明体量小巧但功能完整。程序核心聚焦电脑端走子逻辑通过极大极小值搜索选取最优落子并利用α-β剪枝大幅压缩搜索分支同时精心设计评估函数使AI在对局中具备一定智能除核心算法外还实现了先后手选择、胜负判断、棋盘状态显示与鼠标样式切换并支持快速重开与退出人机交互闭环完整。目前已有4704人学习下载对梳理搜索优化细节、调试评估函数、理解剪枝阈值如何影响棋力具有直接的代码级参考价值。1. 五子棋 AI 的胜负手α-β剪枝如何破解搜索爆炸一个棋盘在第一步落子时有上百个空位第二步有上百个减一如果 AI 每次都往前看 8 步需要评估的棋局数量是百的八次方即千万亿级别。而一个用 Python 写的五子棋人机对战程序总共不过几百行代码却能在不到一秒的时间里给出落子这个反差的来源就是 α-β剪枝。它不是让搜索变快而是大量剪掉“不值得算”的分支让有限算力集中在真正关键的棋局上。这份资源的核心不是 pygame 绘制棋盘的部分而是那个藏在递归函数里的搜索算法理解它你就看穿了一切「人机对战」类程序背后的博弈内核。本文从博弈树建立开始逐步拆解剪枝条件、评估函数和排序启发最后落到几个真实的踩坑记录上帮你彻底搞懂为什么 α-β剪枝能 work。2. 博弈树五子棋 AI 眼中棋盘的“未来展开”2.1 一个递归从当前棋盘生成所有未来五子棋的规则极其简单黑白双方轮流落子谁先连成五子谁赢。但这简单的规则组合出的棋局数量非常惊人AI 要对未来做决策就得先从当前局面出发推演对手的每一步步法。这种推演展开后是一棵标准的博弈树根节点是当前棋盘第一层是己方可选的落点第二层是这些落点之后对手的可选落点依此类推。在 Python 中生成这棵树的代码并不需要显式建树结构用递归就能完成。一个典型的极小化极大搜索函数大致长这样def minimax(board, depth, is_maximizing): # 到达深度边界或分出胜负时返回局面评估分 winner check_winner(board) if winner AI_PLAYER: return 10000 depth # 优先用更少的步数取胜 if winner HUMAN_PLAYER: return -10000 - depth if depth 0 or not get_empty_cells(board): return evaluate(board) empty_cells get_empty_cells(board) if is_maximizing: best_score -float(inf) for row, col in empty_cells: board[row][col] AI_PLAYER score minimax(board, depth - 1, False) board[row][col] EMPTY best_score max(best_score, score) return best_score else: best_score float(inf) for row, col in empty_cells: board[row][col] HUMAN_PLAYER score minimax(board, depth - 1, True) board[row][col] EMPTY best_score min(best_score, score) return best_score这段代码里最关键的动作是试摆子和撤销落子把棋子放到某个空位、递归评估、再取出来。这样整个搜索过程只在同一个棋盘实例上运行不需要复制数组内存开销保持在最低。每个节点返回的分数代表这个局面对于当前棋手的“利害程度”正数越大越有利负数越小越危险。值得注意的是深度参数递减的写法。基础版本中每层都要减去 1但很多实际实现会在“有活三、冲四等关键棋形”时不减深度这是为保证连招不被深度截断打断。不过决策树仍然存在指数爆炸问题15×15 棋盘第一层有 225 个候选落点第二层有 224 个哪怕只搜 4 层需要评估的节点也达到数亿级纯递归完全不可用。这也是为什么要引入剪枝。2.2 收益向上传递MAX 层取最大MIN 层取最小博弈树从根节点往下看轮到 AI 落子时它追求自己的最大利益轮到对手时对方追求 AI 的最小利益这种交替关系就是极小化极大minimax的核心。小明回合取 max 值对手回合取 min 值一层层把叶子节点的评估分向上聚合最终根节点得到“当前局面下最优走法能带来的收益”。这是零和博弈的设定对 AI 好的一步棋对对手就是差的一步棋不存在双赢。于是每个节点的值不是单纯由它自己决定而是由它所有子节点中的最大或最小值决定。搜索深度为 2 时AI 层的每个候选落子都会先看一下对手会怎么回应再选一个对手回应后对自己仍然最有利的位置——这就形成了“我下一步对手下一步我再看结果”的两层前瞻。深度越大这种前瞻越长棋风也就越稳健。2.3 深度限制与截断评估不完整的棋局怎么打分博弈树理论上可以一直展开到棋盘填满但那样复杂度不可接受实战中必须人为截断。到不了终局的节点没有胜负可判只能靠评估函数打分这个分是对“当前棋盘谁更占优”的经验性估计。评估函数是 α-β剪枝搜索的性能上限来源之一。它在同一个棋盘上用 4 个方向扫描所有连子模式每发现一个白方活三、黑方冲四、白方双活二等形状就累加对应分值。这些分值是配置参数不同权重组合会显著改变 AI 下棋风格有的偏防守有的偏进攻。注意一个隐藏问题评估只基于当前盘面静态算分不包含这个局面之后的发展潜力因此得分高的局面未必真的稳赢只是统计意义上更优。3. α-β剪枝的机制搜索树是怎么“缩一半”的3.1 剪枝的本质看到邻居更差这棵树就不用再看了极小化极大搜索存在大量冗余很多子节点算出来的值根本不会影响根节点的选择结果。α-β剪枝的核心思想是维护两个边界值——α 表示 MAX 层到目前为止能确保的最低分β 表示 MIN 层到目前为止能接受的最高分。只要某个节点的返回值越过了这条边界就不再继续搜索它的剩余子节点。形象地说你已经在左边兄弟分支找到了一个保底 10 分的走法现在看右边分支它的第一个子节点就给你一个 5 分的结果。因为 MIN 层会选最小的值右边分支的最高上限已经被第一个子节点压到 5不可能超过 10。此时整个右边分支的价值已经封顶继续往下搜只会看到更差的结果所以直接放弃。这个过程就叫 α 剪枝。反过来在 MIN 层发现某分支的下限已经高于当前 β 值时发生 β 剪枝。一个实现示例def alpha_beta(board, depth, alpha, beta, is_maximizing): winner check_winner(board) if winner AI_PLAYER: return 10000 depth if winner HUMAN_PLAYER: return -10000 - depth if depth 0: return evaluate(board) empty_cells get_ordered_moves(board) # 按启发分数排序 if is_maximizing: best_score -float(inf) for row, col in empty_cells: board[row][col] AI_PLAYER score alpha_beta(board, depth - 1, alpha, beta, False) board[row][col] EMPTY best_score max(best_score, score) alpha max(alpha, best_score) if alpha beta: # 剪枝条件 break return best_score else: best_score float(inf) for row, col in empty_cells: board[row][col] HUMAN_PLAYER score alpha_beta(board, depth - 1, alpha, beta, True) board[row][col] EMPTY best_score min(best_score, score) beta min(beta, best_score) if beta alpha: break return best_score代码中alpha beta这一行就是剪枝发生点。注意剪枝不是发生在发现一次越界就永远剪掉某个分支而是当前节点下对剩余子节点的循环提前终止。alpha 和 beta 在递归返回上层后修改仍然保留这保证了剪枝判断的连续性。与基础 minimax 相比α-β剪枝在最优排序下能把搜索节点数从 O(b^d) 降到 O(b^(d/2))这相当于让你在同样时间内能多搜一倍的深度。对五子棋这种分支因子巨大的棋类来说每多一层深度棋力就有质的提升。需要注意这个复杂度提升严重依赖节点排序质量如果每次都先把最差的分支排进来剪枝几乎不会发生性能又会退回到 naive minimax这就是下一节要讲的排序启发。3.2 参数传递α 和 β 不是结果是上下文很多初学实现容易混淆的一点是alpha 和 beta 不参与最终节点的得分计算它们只是搜索过程中传递的上下文约束。每一层的调用都在用父级已有的边界值来限制本层搜索的上限和下限一但当前分支的返回值突破了某一边界就直接放弃剩余搜索。这条信息只对当前层有效返回上一层后那个值会被用来更新父级边界。这个设计让 α-β 搜索天然适合用递归实现因为每次调用都有自己的局部变量不需要全局状态。实践里要注意一个常见误区有些人会把 alpha 的更新写为alpha max(alpha, score)放到循环外、在全部子节点搜完之后才统一更新那样做会导致剪枝条件检查时 alpha 仍停留在旧值错过本来可以剪掉的节点。alpha 的更新必须在每个子节点返回后立刻发生才能保证后续子节点能利用最新的边界信息剪枝。3.3 一个推演实例从 4 步搜索看节点减少用一棵简化的两层子树推演剪枝的效果。设 AI 是 MAX 层根节点下有 A、B、C 三个可选落子。A 节点下有 3 个子节点返回 [15, 8, 10]按极小化取最大后 A 得 15。此时 α 被更新为 15。接下来搜索 B 节点第一个子节点返回 7由于 MIN 层会取最小值B 节点的最终值无论如何不会超过 7而 7 α 15于是 B 的剩余两个子节点全部被剪掉不做任何评估。这一剪看似只省了 2 次评估但注意每个 B 子节点本身也是深层级子树的根。如果搜索深度再加上 4 层每一个被剪掉的第一层节点背后都藏着成百上千个的后代节点。剪枝的收益是指数级的这也是为什么它是博弈搜索里最基础也最重要的一根支柱。4. 五子棋专属的启发式搜索评估函数与落子排序4.1 评估函数的核心模式连子“活”“冲”加权通用博弈搜索里的评估函数只是一个函数但五子棋的评估函数想要发挥作用必须准确捕捉棋形的危险程度和潜力。一个简单的模式打分函数把各条线上连续的己方棋子数量与两端是否畅通结合形成“活四”“冲四”“活三”“眠三”等模式分别加权求和。def evaluate_line(line, player): # line 是棋盘某一行/列/斜线上的棋子序列片段 score 0 for pattern, points in { (player, player, player, player, EMPTY): 100000, # 活四 (EMPTY, player, player, player, player): 100000, (player, player, player, player, EMPTY, EMPTY): 80000, # 冲四 (EMPTY, player, player, player, EMPTY): 50000, # 活三 (EMPTY, player, player, EMPTY): 2000, # 活二 }.items(): count sum(1 for i in range(len(line) - len(pattern) 1) if tuple(line[i:i len(pattern)]) pattern) score count * points return score这个实现依赖模式匹配把固定形状的棋子序列映射到对应分值。分值权重是一种“玄学”般的调参过程不同权重决定 AI 更喜欢成型的进攻还是提前布防。很多实战棋手下棋时会发现 AI 常有“很奇怪”的防守落点这往往是评估函数里某个模式分数设置过高导致的例如给活三 50000 分后AI 会不惜一切代价破坏对方潜在活三成型。4.2 排序启发先搜最好的分支才能剪更多α-β剪枝的效率极度依赖搜索顺序。如果每个节点都从最可能产生好结果的分支开始搜上层的 α 和 β 就会很快逼近实际的最优值后续大量分支被边界条件剪掉。如果顺序是反的每一个分支搜完都要完整展开剪枝几乎不触发性能回到 naive minimax。因此在正式进入 α-β 递归前需要先对所有空位按「单步评估分」排序得到get_ordered_moves()返回的序列。排序的常用做法是对每个空位执行「假设在此落子后的局部打分」按分数从高到低排序。这个局部打分与全局评估不同它只计算这一步棋周围的八方向关联棋形比如落子后形成活三加 500堵住对方冲四加 3000 等。这一步自身的计算成本比完整搜索低得多却能让剪枝率大幅提升收益非常明显。对深度较大的搜索排序优先级的轻微错配会带来几十倍的性能差距所以任何实现都应该把排序看作搜索的一部分而不是可有可无的优化。4.3 棋盘表示与胜负检测的常见实现细节五子棋棋盘通常用一个二维列表表示board[row][col]存 0空、1黑、2白。搜索过程中同一次递归深度会反复对这个列表做读和写所以查找空位不能全套遍历而是维护一个empty_cells列表或者把搜索范围限制在已有棋子周围的扩展区域。这样做除了加速搜索还能避免 AI 下到距离其他棋子过远、毫无联系的孤立点这类点在任何棋局评估里都不会是好棋。胜负检查更是搜索核心中的核心每次落子后立刻检查四个方向x 正方向和负方向加起来看是否连成五子。检查时机要放在递归进入叶子节点之后因为人机对战模式下check_winner几乎每层每节点都要执行它的效率直接决定搜索整体的上限。比较快的实现是检查最近落子点为中心、十字和两条斜线上的连续长度这样不需要扫描全盘。5. 避坑记录α-β剪枝写五子棋 AI 的几个血泪经验5.1 评估函数漏掉跳活三AI 变成“睁眼瞎”现象AI 在某些局面下会忽略明显的冲四威胁或者主动去堵一个无关紧要的角落仿佛没有看见对方三连子。根源是评估函数只匹配了固定连续的模式没有覆盖“中间隔一格”的跳活三比如X _ X X _这种形状。而五子棋里这类形状非常常见它是活三的变体与普通活三的威胁等级相当漏掉后 AI 对威胁的感知出现盲区。解决扩展模式库加入单跳和多跳的匹配同时注意检查两个方向。另一种做法是使用位棋盘把每一行的棋子分布编码成整数用位运算判断连子模式速度和覆盖率都能兼顾。但位运算的代码可读性较差调试时容易翻车建议先写朴素版本验证行为再考虑优化。5.2 对称位置重复评估拖垮性能现象同样的搜索深度某些局面跑得飞快某些局面慢到像死循环两者棋盘形状几乎一样。根源是搜索没有考虑对称性去重。五子棋棋盘关于中心对称很多位置在翻折之后是完全等价的但当前 AI 仍会分别搜索这些节点导致成倍的重复计算。解决在最外层的落子候选里加入对称性过滤。例如只保留每一对对称坐标中较小的一个或者对空位列表按坐标排序后做一次镜像去重。实现简单、效果明显尤其在开局阶段能节省不少搜索时间。深度更大时还可以引入置换表把已经算过分数的棋盘哈希值缓存起来遇到相同局面直接复用结果这是更进一步的优化手段。5.3 α、β初始化范围不当导致剪枝失效现象深度改成 6 后AI 落子反而变慢很多每次走棋要等上十几秒像是退化成了没加剪枝的版本。根源看代码初始 alpha 和 beta 应该取负无穷和正无穷但有人在递归函数里把 alpha、beta 参数写成了默认值导致每层递归覆盖掉父级传入的边界剪枝条件永远不会触发。解决严格检查剪枝参数的传递链路alpha、beta 只应该由父级传入子层更新后通过返回值影响父层判断不能在子层内重新初始化。每次修改剪枝代码后用一个固定的小棋盘跑一遍对照测试对比剪枝前后节点访问数是否明显较少低于 30% 就要检查参数传递是否有问题。5.4 胜负判定方向遗漏AI 赢棋不下连五现象AI 明明已经四子连排最后一步却跑去防守把必赢的关键一子浪费掉。根源胜负检查只写了横向和纵向漏掉了两条斜线方向于是即使已经四连AI 也判断不出“再下一步就能赢”。在 α-β 搜索的叶子节点里这样的错判会直接让搜索结果失真AI 对获胜局面的打分不足自然选择其他动作。解决检查棋子时同时扫横、竖、主对角线和副对角线四个方向。同时注意连五的判断条件是“任意一方连线达到 5 颗”不要漏掉超过 5 颗的情况比如 6 连、7 连仍然应该判定为胜利这个细节会影响搜索边界情况下的胜负判断正确性。6. 设计取舍你想要“算得深”还是“算得准”每个五子棋 AI 实现最终都面临一个选择是加大搜索深度还是改进评估函数。深度直接决定 AI 能看到多远的未来每多一层防守和进攻的连续计算就更可靠但深度每增加 1节点数就可能翻几倍就算有 α-β剪枝Python 这种解释型语言在 6 层以上也会明显吃力。评估函数决定叶子节点打分的质量评分准即使只搜 2 层也能有像样的棋感评分不准深度再大也可能在叶子层就把局面算偏根节点累加后仍然走出糟糕的一步。我一般这么理解这个取舍搜索深度更像上限评估函数更像底线。很多开源实现会在开局和中盘用 4 层深度加位置排序在终盘阶段改用专门的必胜判断逻辑——因为终盘棋子数量多每层分支因子变小可以安全提高深度。这种分层思考比单纯堆一个全局参数更符合五子棋的棋理。具体到这份资源建议先跑通 4 层版本观察它对中盘活三的处理是否自然再逐步加深并对比每一步的关键节点数以此验证排序和剪枝是否真的生效。五子棋 AI 项目里还有一个绕不开的参数AI 执黑还是执白。执黑开局优势大评估函数里进攻分可以略高执白要更重视防守分数的权重这种不对称性会让同一套搜索逻辑在两种颜色下有不同表现。把这些权重做成可配置项比写死在代码里更容易调优也能让你对不同策略下的棋风差异有直观体验。从那以后我每次写博弈搜索都会强制自己先跑一遍基准测试记录剪枝前和剪枝后的节点访问数如果没有明显的下降就说明还有逻辑问题没暴露。希望帮到你。本文还有配套的精品资源点击获取