简介：基于α-β剪枝实现五子棋人机对战的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 执黑还是执白。执黑开局优势大，评估函数里进攻分可以略高；执白要更重视防守分数的权重，这种不对称性会让同一套搜索逻辑在两种颜色下有不同表现。把这些权重做成可配置项，比写死在代码里更容易调优，也能让你对不同策略下的棋风差异有直观体验。从那以后，我每次写博弈搜索都会强制自己先跑一遍基准测试，记录剪枝前和剪枝后的节点访问数，如果没有明显的下降，就说明还有逻辑问题没暴露。希望帮到你。
本文还有配套的精品资源，点击获取
