简介基于α-β剪枝策略实现的井字棋游戏Python源码与文档说明是面向计算机专业课程设计、毕业设计及算法学习者的完整项目。项目以极小极大值搜索算法为核心通过α-β剪枝有效减少搜索空间直观展示博弈树求解与剪枝优化过程代码结构清晰、便于理解与二次开发。压缩包共含8个文件包括2个Python脚本、2个Markdown文档及4张流程示意图整体仅116KB轻量易用可快速运行验证。目前已有395人学习下载项目曾获导师指导并高分通过适合用于课设作业、期末大作业及算法实践参考。下载后可获得可直接运行的源码、配套说明文档与图示帮助掌握对抗搜索与剪枝策略的实现细节也可在此基础上拓展功能。1. 井字棋的 α-β 剪枝这套源码在解决什么、值不值得读基于 α-β 剪枝策略实现的井字棋游戏本质是把“极小极大值搜索算法”从理论课搬进能独立运行的 Python 工程。很多人搜过井字棋源码也见过 minimax 递归但真正讲清楚 alpha/beta 两个参数怎么传、为什么估值函数只要 -1/0/1 就够了、剪枝边界写错会翻车的资料并不多。这套源码加文档说明正好兜住这三件事棋盘用二维列表表示胜负判定直接查行、列和对角线AI 用带剪枝的极小极大决策。适合三类人刚开始学搜索算法的学生想在课程设计里交出一份能演示、能答辩的 Python 代码以及第一次写 minimax、想看清剪枝到底剪在哪里的开发者。如果你已经写过朴素极小极大也值得看——后面避坑部分的五个问题大多在网上搜不到现成答案。2. 极小极大值搜索算法与估值函数3×3 棋盘上的分数是怎么传上来的2.1 零和博弈与井字棋估值方法为什么三个整数就够描述输赢两个人交替落子没有随机因素也没有隐藏信息——井字棋是教科书里最小的完全信息零和博弈。所谓零和指一方的收益严格等于另一方的损失表现在得分上只需要压缩成一个整数AI 赢是 1人类赢是 -1平局是 0。你不需要设计“角比边更值钱”的局面打分因为对井字棋来说终局判断本身就已经能给到全局结论这是这套 α-β 实现能保持干净代码量的根本原因。把估值函数限制在终局还有另一个好处中间层的搜索完全靠叶子节点回传分数不需要人工调整棋形权重。很多第一次做 AI 的人在这里陷入玄学调参给角、边、中心各加一个权重最后发现 AI 的表现还不如不加权重稳定。井字棋的搜索深度最多九层完整极小极大在毫秒内就能出结果静态局面评估在井字棋里几乎是不必要的。量化一下规模3×3 棋盘所有合法与非法摆放大约有 3 的 9 次方也就是 19683 个状态完整对局路径约 9! 362880 条去掉提前结束的盘面实际对局数量还要少。任何一台普通机器不剪枝也能在可感知的短时间内走完整棵树。换句话说在这个项目里加 α-β 剪枝图的不是救性能而是把原理讲清楚。把这个最小场景吃透再去碰五子棋那种必须靠剪枝才能活的项目过渡会自然很多。2.2 搜索树与极大极小Max/Min 交替时的返回值约定极小极大搜索的思路可以浓缩成一句话轮到 AI 走的时候AI 选分数最大的分支轮到人类走的时候人类会替 AI 选分数最小的分支因为人类的目标是让 AI 的收益最小化。代码上对应的伪代码如下def minimax(board, maximizing): winner game_over(board) if winner is not None: return winner if maximizing: # 当前层是 AI 决策 best -float(inf) for move in empty_cells(board): 落子给 AI best max(best, minimax(board, False)) 恢复棋盘 return best else: # 当前层是人类决策 best float(inf) for move in empty_cells(board): 落子给人类 best min(best, minimax(board, True)) 恢复棋盘 return best注意这里的maximizing参数表示“当前这一层轮到谁决策”不是“刚才谁走完”。人类走完之后递归进入 AI 层maximizing为 TrueAI 走完之后递归进入人类层maximizing为 False。角色随深度交替这就是“极大极小”名字的由来极大层取 max极小层取 min。还有一个约定特别容易写错返回值始终从 AI 的视角定义。也就是说无论在 max 层还是 min 层返回 1 都表示“这个局面终局是 AI 赢”返回 -1 表示人类赢。很多教材写法会按“当前行动方视角”统一翻符号比如走到 min 层就把结果乘 -1写熟练了没问题但对新手很容易在递归超过两层之后把正负弄反。这套源码采用的是固定 AI 视角后面避坑章节我会再展开讲为什么这种写法的容错度更高。2.3 α-β 剪枝的数学条件什么时候删掉半边树不会影响结果朴素极小极大必须完整遍历所有分支才能拿到准确分数。α-β 剪枝利用的观察是很多分支的分数根本不可能被父节点选中提前停下来不影响根节点结论。α 是当前 max 节点已经拿到的最好下界可以理解为“AI 至少能拿到的分数”β 是当前 min 节点已经拿到的最差上界理解为“人类最多只愿意给到这个分数”。初始时 α 是负无穷β 是正无穷。搜索从左到右扫描分支时max 层不断抬高 αmin 层不断压低 β。一旦出现beta alpha说明当前节点的区间已经空掉了——继续看这个节点剩下的兄弟分支父节点也不会改变选择。这时候直接 break丢掉还没扫完的子树。剪枝不影响结果的证明思路也很直白假设在 min 节点已经拿到 β而某个尚未扫描的分支至少能给 max 节点 α并且 α 已经不小于 β。min 节点若是选了那个分支最终得分至少是 α比当前 β 还差或一样差min 节点不会这么选所以那个分支不存在最优解。走法顺序越好剪枝越早剪掉的节点越多顺序很差时剪枝可能只省掉一小部分树。井字棋规模太小剪枝前后差异肉眼不一定看得见所以最好用代码里加计数器的方式实测而不是听信网上随便写的“提升几十倍”。3. α-β 剪枝的 Python 落地方案核心递归函数与 alpha/beta 参数含义3.1 棋盘数据结构与玩家编号用整数代替 X/O 的理由这套源码把棋盘做成 3×3 二维列表空白格、人类、AI 分别用 0、-1、1 表示EMPTY 0 HUMAN_PLAYER -1 AI_PLAYER 1 def empty_cells(board): return [(r, c) for r in range(3) for c in range(3) if board[r][c] EMPTY]使用整数而不是字符串 X / O 有三个直接好处。第一胜负判断可以直接用board[i][0] board[i][1] board[i][2]比较不用考虑大小写和字符常量第二终局返回值可以直接复用玩家编号AI 赢就返回 1人类赢返回 -1平局返回 0省去一层映射第三需要做矩阵运算或把局面转成哈希键时整数比字符串更省空间。打印给玩家看的时候再把它转成可视化字符即可逻辑与显示分离后面加网页版界面时不用碰搜索代码。empty_cells返回的是所有空位坐标的列表它同时承担走法生成职责。井字棋的走法就是“选一个空格落子”没有任何吃子、跳子或禁手规则所以走法生成器只需要遍历 3×3 找值为 0 的位置。这个函数在递归里会被调用很多次保持轻量很重要如果你把它改成先收集再过滤的复杂流程node_count 对比实验里的耗时差距会失真。3.2 递归函数 alphabeta最小可运行的剪枝实现与参数说明下面是这套源码中最核心的搜索函数也是整个项目要演示的主角def alphabeta(board, depth, alpha, beta, maximizing): winner game_over(board) if winner is not None: return winner # 返回 AI 视角分数1 / -1 / 0 if maximizing: value -float(inf) for r, c in empty_cells(board): board[r][c] AI_PLAYER value max(value, alphabeta(board, depth 1, alpha, beta, False)) board[r][c] EMPTY # 恢复棋盘保证兄弟分支看到的仍是原局面 alpha max(alpha, value) if beta alpha: break # 剪枝min 层不会再选这个分支 return value else: value float(inf) for r, c in empty_cells(board): board[r][c] HUMAN_PLAYER value min(value, alphabeta(board, depth 1, alpha, beta, True)) board[r][c] EMPTY beta min(beta, value) if beta alpha: break return value逻辑说明函数每次进入一个新节点都先调用game_over判断是否到达终局。井字棋的终局只有三情况——某方三子连线或棋盘满且无人连线判断函数game_over返回None表示对局未结束返回其他值表示直接得到这一层的分数。如果未终局max 分支枚举所有空位轮流落 AI 的棋子对每个子局面递归调用递归返回后在当前分支取得最大值min 分支对称取最小值。参数说明depth在当前版本不参与截断逻辑只用于调试打印和后续改成迭代加深时使用alpha和beta分别在 max 层和 min 层更新并且只通过函数参数传递。参数表如下参数初始值在递归里的作用depth0记录当前搜索深度井字棋最深 9不截断alpha-infmax 节点已探索到的下界只在 max 层更新betainfmin 节点已探索到的上界只在 min 层更新maximizingTrue / False当前层是否轮到 AI 决策这里必须强调一点恢复棋盘的那行board[r][c] EMPTY要写在递归调用之后、循环体结束之前。它是回溯搜索的“后悔药”保证同一层的不同分支都是从同一个棋盘状态出发试验。如果你把这个赋值写在if外面或者循环外面递归树会被上一层污染。3.3 根节点调用与 best_movealpha/beta 初值为什么要用正负无穷剪枝函数本身不决定 AI 最终走哪步棋它只返回一个局面分数。真正选出一步棋的是根节点的best_movedef best_move(board): best_score -float(inf) best None for r, c in empty_cells(board): board[r][c] AI_PLAYER score alphabeta(board, 0, -float(inf), float(inf), False) board[r][c] EMPTY if score best_score: best_score score best (r, c) return best这里在根节点显式遍历所有空位落子后调用alphabeta看这步棋会导致什么局面。调用时maximizing传 False表示 AI 落子之后轮到人类决策人类会选对 AI 最不利的分支返回值依然是“从 AI 视角看这个局面的终局分数”。选出分数最大的那个落子位置返回。很多网上的 α-β 实现会把初始值写成alpha-1, beta1因为在井字棋里分数只有 ±1/0看起来能省几行。但这么做会把边界参数和估值函数的取值范围耦合在一起一旦你把估值函数换成静态启发式分数可能跑到上千就会忘记改这两个初值。用负无穷和正无穷作初值时估值函数无论怎么变都不用回头改调用方。递归内部也用-float(inf)而不是-1同样是这个原因。根节点为什么不剪枝因为井字棋根节点最多 9 个空位每个都要真正落子试一遍才知道哪个最好即使不剪枝也只是多算几个分支对总耗时影响可以忽略。如果你想在更复杂的棋类里优化这一步通常会在 best_move 里维护一个全局最优值再配合走法排序让高评分分支优先被扫描从而让更多分支被剪掉。这套源码保持根节点写法朴素是为了先保证正确性再谈效率。4. 完整井字棋工程棋盘表示、胜负判断与人机对弈主循环4.1 走法生成与先手策略空位扫描顺序为什么会决定 AI 的第一手走法生成器已经在上文给出了就是empty_cells按行优先返回空格坐标。这里有个很容易被忽略的细节走法扫描顺序会直接影响 α-β 剪枝的效果也影响 AI 在多个等优走法里的偏好。井字棋只要双方都完美结果一定是平局这是游戏本身的博弈论结论跟剪枝无关。因此 AI 在开局时经常会有多个分数同为 0 的候选分支。best_move遍历empty_cells得到的是从左到右、从上到下的顺序AI 默认会选先扫到的那个也就是大概率落在(0,0)角。但这并不代表 AI“算错了”只是它在多个最优解里按扫描顺序取了一个。如果你希望 AI 开局优先占中心一个常见做法是给empty_cells的结果按“中心 → 角 → 边”排序CENTER (1, 1) CORNERS [(0, 0), (0, 2), (2, 0), (2, 2)] EDGES [(0, 1), (1, 0), (1, 2), (2, 1)] def ordered_empty_cells(board): cells empty_cells(board) cells.sort(keylambda pos: 0 if pos CENTER else (1 if pos in CORNERS else 2)) return cells走法排序不会改变结论只会改变剪枝命中率和同分局面下的第一步偏好。在井字棋这个规模里两种写法跑出来的 node_count 差别不大但如果你准备把源码改造成五子棋走法排序是剪枝性能的第一杠杆比调 alpha/beta 初值有用得多。4.2 人机交互主循环坐标校验、非法落子重试与胜负输出人机对弈部分的核心代码可以这样组织SYMBOLS {EMPTY: , AI_PLAYER: X, HUMAN_PLAYER: O} def print_board(board): for r in range(3): print( | .join(SYMBOLS[board[r][c]] for c in range(3))) if r 2: print(-------) def parse_input(text): parts text.strip().split() if len(parts) ! 2: raise ValueError(需要输入两个数字例如 1 2) r, c int(parts[0]) - 1, int(parts[1]) - 1 if not (0 r 3 and 0 c 3): raise ValueError(坐标越界有效范围是 1~3) return r, c def main(): board [[EMPTY] * 3 for _ in range(3)] human_turn True while game_over(board) is None: print_board(board) if human_turn: while True: try: r, c parse_input(input(请落子(行 列比如 1 2): )) except ValueError as e: print(解析失败:, e) continue if board[r][c] ! EMPTY: print(这个位置已经有棋子换一个位置) continue board[r][c] HUMAN_PLAYER break else: r, c best_move(board) board[r][c] AI_PLAYER print(fAI 落子在第 {r1} 行第 {c1} 列) human_turn not human_turn print_board(board) winner game_over(board) if winner AI_PLAYER: print(AI 胜) elif winner HUMAN_PLAYER: print(你赢了) else: print(平局) if __name__ __main__: main()逻辑说明主循环以game_over(board) is None作为持续条件只要没有分出胜负或满盘就让人类和 AI 轮流落子。人类输入的行列从 1 开始编号内部转换成 0 基索引parse_input负责解析和越界检查非法输入被try/except捕获后重新询问。落子前检查board[r][c] ! EMPTY这是避免覆盖已有棋子的关键判断。AI 回合直接调用best_move得到坐标后落子。这里要注意human_turn的切换位置人类落子后置 FalseAI 落子后置 True。如果开局想改成 AI 先手只需把human_turn的初始值改成 False其余逻辑无需变动。这个主循环是纯文本控制台版本依赖零第三方库Python 3.6 之后的版本都能直接跑。4.3 node_count 计数器用剪枝前后对比验证效率剪枝对不对最直观的验证方式是给搜索函数加一个全局计数器统计递归调用次数node_count 0 def alphabeta(board, depth, alpha, beta, maximizing): global node_count node_count 1 # 其余逻辑保持不变在best_move第一次调用前把node_count置 0AI 走完一步后打印这个值你就能看到每次决策实际搜索了多少个节点。再做一个对照实验去掉函数里的if beta alpha: break两处剪枝跑同样的开局对比 node_count。你会发现带剪枝的调用次数明显下降而最终选出的走子与朴素版本完全一致。这个对照实验是整套源码里最值得动手跑一遍的部分因为“剪枝不影响结果”这句话只有亲眼看计数器才真正可信。我在本地默认开局跑出来的结果通常是剪枝后调用次数少一半以上但因为走法顺序、初始棋局不同数值会有波动。建议你以自己的实测为准不要在实验报告里照抄网上的某个固定数字。把 node_count 打出来还有一个额外好处写课程设计文档时它可以作为“算法优化有效性”的直接证据比光贴原理截图有说服力得多。5. α-β 剪枝常见问题与避坑五个让 AI 翻车的细节5.1 终局分数符号反转AI 把对手的“胜利”当成自己的现象AI 明明看到对手下一步能连成三却不去堵反而走了无关位置或者更离谱AI 主动走出一步立刻送对方赢棋的结果。原因实现时按“当前行动方视角”给终局分数翻了符号。典型写法是在 min 层做return -value在 max 层做return value把返回值理解成“当前层决策者的收益”。这种视角在伪码里很漂亮一旦递归深度超过两层正负号交替出现极容易漏掉某一段导致方向整体颠倒。另一种常见诱因是估值函数里把人类赢写成 1、AI 赢写成 -1方向写反。解决全工程统一从 AI 视角定义分数game_over返回的整数本身就是收益min 层不要再乘 -1。也就是说终局为 AI 胜时不管正在搜索哪一层返回值永远是 1人类胜永远是 -1平局 0。这样符号逻辑只存在于一个地方排查起来最省事。如果你确实喜欢“当前行动方视角”请把符号翻转收敛到一个函数里并保证每个递归出口都经过它不要散落到多个分支里。5.2 忘记恢复棋盘共享列表把整棵搜索树变成脏数据现象AI 走第二步后棋盘上莫名其妙多了三四个棋子打印出来的局面出现重复落子搜索速度也突然变慢。原因整个递归过程共享同一个 board 列表。递归函数在某个分支落子后如果没有在返回前恢复成 EMPTY兄弟分支看到的棋盘就不是原局面等价于把一步棋的错误复制给了整棵子树。这个问题在best_move的根循环里也会发生——第一次循环落子后忘了复位第二个候选分支从脏局面开始试。解决严格按照“落子 → 递归 → 取返回值 → 恢复棋盘 → 更新 alpha/beta → 判断剪枝”的顺序写。恢复棋盘的代码必须紧跟在递归调用之后中间不要插入 return、continue 或额外的分支判断。想彻底免除这类问题可以把棋盘转成不可变表示例如 9 字符字符串XOX 或元组递归时创建新对象回溯由不可变性天然保证。对井字棋来说拷贝开销可以忽略推荐新手用不可变表示来调试成熟后再切回原地回溯以提升性能。5.3 alpha/beta 写成成员变量递归分支间的状态泄漏现象剪枝表现异常“积极”某些明明应该被检查的分支直接跳过AI 选出的走子不是最优解运行结果间歇性错误跟手动调试时的局面有关。原因把 alpha 和 beta 保存成self.alpha、self.beta或全局变量而不是作为函数参数传递。递归的深层分支修改了 alpha/beta 后回到外层分支时没有恢复外层剪枝条件参考的是别的层级写进来的错误值。α-β 剪枝的正确性依赖“每个节点使用当前分支路径传下来的边界”一旦状态共享这个前提就不成立了。解决坚持用函数参数传递 alpha 和 beta。递归调用本身会为每一层创建独立的作用域天然具备保存和恢复语义。如果你想把搜索封装成类可以在类里维护棋盘和计数器但 alpha/beta 仍然要作为局部变量传入递归函数不要挂到self上。记录日志时为方便可以复制一份到局部变量再打印千万不要直接修改类字段来替代参数。5.4 depth 参数变成深度限制井字棋里先别这么干现象给递归加了if depth max_depth: return evaluate(board)之后AI 开始犯低级错误明明两步能获胜它不走甚至放任对手连成三。原因井字棋整棵树深度最多 9 层完全展开本来就是毫秒级加深度截断毫无必要。更要命的是如果截断时你的evaluate只对终局返回 ±1/0对中间局面一律返回 0那 AI 就等于在“黑匣子”状态下做决策所有截断节点都看成平局搜索自然丢失了远方的胜负信息。解决在井字棋中不要设置 max_depth让搜索走完整棵树depth参数只保留作为调试信息和迭代加深的扩展口。如果你未来把这段代码改造成五子棋那时再引入深度截断并且必须设计一个连续型静态评估函数能反映当前局面的棋形优势。到那个阶段评估函数的设计质量比剪枝本身更影响 AI 强弱别指望一个 0 值闯天下。5.5 剪枝比较用不用效率损失比你以为的大现象程序结果跟朴素 minimax 一致看着没问题但 node_count 并没有降下来多少把棋盘规模换大一点搜索明显卡顿。原因剪枝条件写成if beta alpha而不是if beta alpha。两者在多数分支上结果一样唯一的差别出现在 beta 恰好等于 alpha 的边界情形。严格小于会继续展开那块分支虽然最终结论仍是同一个最优值因为继续搜也不可能得到更好的结果但那些节点全部白走了。在井字棋 9 层的规模下浪费看起来不大换成五子棋后这种边界分支会成倍累积效率差距立刻显现。解决一律写成if beta alpha。“等于”时剪枝不但正确而且必要。理由很简单max 层已经拿到了一个等于 beta 的分支min 层愿意接受的上限就是 beta其他分支再好也不会被选中剪掉它们不会改变根节点结论。为了代码可读性可以把这条边界判断封装成if beta alpha: break并在注释里写明“边界剪枝合法因为存在等值解”。6. 从井字棋到五子棋搜索抽象、深层遍历与最终验证6.1 扩展方向把搜索逻辑抽象成通用 GameState井字棋的 α-β 实现最值得带走的收获是“搜索算法与棋类规则解耦”的设计思路。要做成通用版本先抽象一个接口class GameState: def legal_moves(self): ... # 返回合法走法列表 def apply(self, move): ... # 返回落子后的新状态 def is_terminal(self): ... # 是否终局 def payoff(self): ... # 从 MAX 玩家视角返回终局分数alpha-beta 函数只需要调用这四个方法不关心棋盘是 3×3 还是 15×15。井字棋的board二维列表可以改造成这个接口的一份实现五子棋再新写一份。改造时有一个明显差异需要记住维度井字棋五子棋搜索树深度最多 9 层可完整展开通常两百手以上必须截断估值函数终局 ±1/0 足够需要中间局面的静态评估剪枝作用教学演示为主没有剪枝基本跑不动走法排序可有可无直接决定剪枝多少必备验证手段可穷举全部终局只能抽样对局加统计评估如果你只是想把井字棋做成网页版跑在浏览器里搜索部分完全不用动只要把打印棋盘和输入输出的地方替换成 HTML 界面。常见做法是用 Flask 起一个本地服务前端传坐标到后端/move接口后端调用best_move返回落子位置再配合 JavaScript 渲染棋盘。6.2 验证方法让剪枝版与朴素版对局并跑对称性测试我拿到任何带搜索的棋类源码第一件事不是看效果而是跑等价性验证。具体到这套井字棋两个验证值得做第一让带剪枝的 AI 和去掉了剪枝的朴素 AI 对弈一百局断言胜负结果完全一致第二把棋盘旋转 90 度、镜像翻转后再让 AI 决策断言落子位置也对应旋转镜像。这两项都通过你的 alpha-beta 实现才算可信。另一个实用技巧是给根节点走法排序后跑 node_count 对比验证剪枝效率确实随走法顺序变化。如果你未来深入五子棋方向还会遇到迭代加深和置换表那时核心搜索框架仍然和今天这套代码一脉相承。我的习惯是每次改造一个参数就重跑一遍对照实验确认剪枝没改变胜负结论才开始调性能。这个审计习惯帮我避开过不少“看起来快了但走错的 AI”希望你也能把自己的搜索代码当成可验证的实验对象而不是一段玄学黑匣子。希望帮到你。本文还有配套的精品资源点击获取