简介这是一份面向Python初学者与算法练习者的五子棋人机对战项目代码围绕pygame界面、极大极小值搜索与α-β剪枝展开适合用来理解博弈树搜索如何落地到可交互小游戏。压缩包共3个文件以2个py源码和1个txt说明为主约15KB体量轻便便于在PyCharm等环境直接阅读与调试。已有4707人学习下载说明其在课程设计、算法实验和自学练手中具有一定参考价值。代码重点呈现电脑走步的选取逻辑包括候选落子点生成、棋局评估函数设计、搜索效率优化以及先后手切换、胜负判断和棋盘信息显示等完整流程读者可据此梳理人机对战的核心链路理解评估函数为何直接影响AI的“智能”程度并对照实现自己的剪枝策略与界面交互。1. 会下棋和算得动是两件事五子棋 AI 的搜索空间有多大先给一个反直觉的结论一个能赢过大部分初学者的五子棋 AI核心决策代码往往不到两百行而要让它再强一个档次难度上升的幅度远超代码行数的增长。卡住人的地方在于“算不完”而不是“不会下”。python 五子棋 人机对战 pygame 这套组合里pygame 只负责画棋盘和收鼠标点击真正的分量全压在一个函数上给定当前局面返回一个落子坐标。没有神经网络没有机器学习靠的是 α-β 剪枝把一棵原本会指数增长的博弈树砍到在一秒内跑完的程度。搞懂这套机制你就明白为什么“多搜两层”比“换个更聪明的评分”往往更有效也明白为什么剪枝顺序写错会让 AI 下出让人哭笑不得的棋。2. 棋局状态机15×15 的棋盘怎么变成一棵可搜索的树博弈搜索的一切前提是你能把“棋盘”变成“可以反复前进后退的状态”。这一步做得好不好直接决定了后面能不能在递归里做撤销undo也决定了每秒钟能展开多少个节点。很多人在这里随手写了个二维列表加copy.deepcopy然后在搜索深度到 6 的时候发现程序跑了十几秒还没出结果这不是算法慢而是数据结构选错了。2.1 一维数组表示与落子撤销棋盘的本质是 225 个格子的定长序列一维数组比二维列表在索引计算上更省也更容易做哈希。空位、黑子、白子分别用 0、1、2 表示越界统一当作“墙”这样棋型匹配时不用处处写边界判断。BOARD_SIZE 15 EMPTY, BLACK, WHITE 0, 1, 2 class Board: def __init__(self): # 一维数组索引 row * 15 col self.cells [EMPTY] * (BOARD_SIZE * BOARD_SIZE) self.history [] # 落子栈用于撤销 def place(self, idx, player): self.cells[idx] player self.history.append(idx) # 只记录位置颜色可从棋盘反推 def undo(self): idx self.history.pop() self.cells[idx] EMPTY def get(self, r, c): # 越界一律返回 -1作为“墙”参与棋型匹配 if 0 r BOARD_SIZE and 0 c BOARD_SIZE: return self.cells[r * BOARD_SIZE c] return -1place和undo是搜索的两条腿递归进入时落子回溯返回时撤销。这里没有用深拷贝是因为一次深拷贝 225 个元素的列表在深度 6、分支 12 的情况下会被调用上万次开销比搜索本身还大。用落子栈做原地修改单次操作是 O(1)这是搜索能跑到几万节点每秒的基础。提示undo必须严格后进先出任何在中途抛异常的分支都会让棋盘状态和history脱节表现为“AI 落子落在已经有棋子的位置”这类 bug 极难从棋谱上看出来。2.2 候选点生成把 225 个空位压到几十个如果每一层都把全部空位当成候选第一层 225 个分支第二层 224 个深度 4 就是 225×224×223×222 约 25 亿个节点任何剪枝都救不回来。真正有效的做法是利用五子棋的局部性有价值的落子几乎总在已有棋子的附近。def gen_moves(self, radius2, limit12): cand set() for idx, v in enumerate(self.cells): if v EMPTY: continue r, c divmod(idx, BOARD_SIZE) # 只收集已有棋子周围 radius 格内的空点 for dr in range(-radius, radius 1): for dc in range(-radius, radius 1): nr, nc r dr, c dc if 0 nr BOARD_SIZE and 0 nc BOARD_SIZE: ni nr * BOARD_SIZE nc if self.cells[ni] EMPTY: cand.add(ni) # 按启发式打分排序后截断排序质量决定剪枝效率 return sorted(cand, keyself.move_score, reverseTrue)[:limit]radius控制搜索的“视野”通常取 2取 1 会漏掉一些跳二、跳三的延伸点取 3 候选点数量会明显膨胀。limit是每层保留的候选数这是深度和广度的直接交换limit12配合深度 6节点数大约在十万级纯 Python 也能在一秒内跑完。move_score这里不需要很精确常见做法是统计该点四个方向上相邻棋子的数量和颜色形成“我方连子加分、对方连子也加分”的粗排序。它的作用不是选出最好的点而是把最可能引发剪枝的点排在前面这一点在下一章会看到它的真正价值。2.3 终局判定与搜索的边界条件搜索必须能识别“已经结束”的局面否则会在胜负已分之后继续往下算白白浪费节点甚至因为评估函数在终局局面上的打分不如实际胜负值导致 AI 错过必胜手。def is_win(self, idx, player): r, c divmod(idx, BOARD_SIZE) for dr, dc in ((1, 0), (0, 1), (1, 1), (1, -1)): cnt 1 for sign in (1, -1): nr, nc r dr * sign, c dc * sign while self.get(nr, nc) player: cnt 1 nr dr * sign nc dc * sign if cnt 5: return True return False这里只检查刚落下的那颗子因为棋局是逐步推进的之前的局面已经被检查过。四个方向分别沿正负两个方向延伸计数遇到墙-1或异色自然停止。搜索的终局分数要设得足够大且带深度修正赢棋分数写成WIN - depth这种形式让 AI 在多个必胜路径里选最快的那条输棋写成-WIN depth让它尽量拖延。如果所有胜负都返回同一个值AI 会在必胜局面下漫无目的地绕圈观感上就像“它在故意耍我”。3. α-β 剪枝为什么砍掉的分支不影响结果这是整套系统里最值得讲透的一步。α-β 剪枝最反直觉的地方在于它砍掉了大量分支但返回的结果和完整搜索完全一致。它不是近似算法不是启发式赌一把而是数学上可证明的等价变换。理解了这个等价性你才知道该往哪个方向优化。3.1 极大极小先把“对抗”翻译成递归五子棋是零和博弈我的收益就是你的损失。所以不需要分别写“我方最大化”和“对方最小化”两个函数用负极大值negamax形式统一每个节点都返回“当前走子方视角下的最优分数”父子之间取负号即可互换视角。def negamax(board, depth, alpha, beta, player): # 到达叶子节点或分出胜负返回当前走子方视角的分数 if depth 0 or game_over(board): return evaluate(board, player) best -INF for move in board.gen_moves(limit12): board.place(move, player) # 子节点是对方视角取负号换回自己视角 score -negamax(board, depth - 1, -beta, -alpha, 3 - player) board.undo() if score best: best score if best alpha: alpha best if alpha beta: break # 剪枝这个分支对方根本不会让我走到 return bestalpha是当前节点已经确保能拿到的下界beta是父节点给出的上界。3 - player是黑白互换的小技巧1→22→1。返回值是分数实际落子坐标由根节点单独记录——这一点很多人第一次写会漏导致搜完不知道该下哪。3.2 剪枝条件的几何含义alpha beta的含义是当前节点已经找到了一个分数这个分数高到父节点对手绝不会允许局面走到这里所以剩下的兄弟分支不用再看了。举个具体场景。假设我在某一层已经找到一个能赢的走法分数是WIN-1。这时候我换一个走法试对方在我的下一步里会尽最大努力压低我的分数。如果对方在某条分支里已经能把我压到低于alpha的值那我就知道这条分支对我没好处可以直接放弃。而当某个对手节点的返回值已经低于我已知的下界时再算别的分支也不可能让这个节点对对手更有利——因为对手是取最小值的它的值只会更低。这就是 α-β 剪枝的本质它利用的是“对手不会配合我”这个假设而这个假设在完美信息零和博弈里永远成立。3.3 走法排序剪枝效率的真正杠杆理论剪枝效果极度依赖顺序。最好情况下每层都先搜最优走法时间复杂度从 O(b^d) 降到 O(b^(d/2))等效于搜索深度翻倍最坏情况下每次最差的走法先搜剪枝完全不生效还多了一层比较开销。排序策略深度 6 的节点数经验量级说明随机顺序十万到百万级剪枝基本失效等于裸极大极小按邻子数量粗排数万级实现成本极低见效明显按棋型分值精排一万级以内需要评估函数配合收益最大置换表命中再降三到五成复用不同顺序到达的同一局面实践中性价比最高的一步是把gen_moves里的move_score从“数邻居”升级成“数棋型”这个点能形成活三还是冲四直接决定它该排多前。因为 AI 在大多数层里最想试的永远是那些能立刻制造威胁的点。这条优化没有任何数学风险纯粹是让好分支先出现属于稳赚不赔的买卖。3.4 窗口传参与负号的常见误区递归调用里写的是-negamax(..., -beta, -alpha, ...)注意两个参数都取负并且顺序交换。这不是笔误而是因为视角翻转后原来的上界变成了子节点的下界。写成-negamax(..., -alpha, -beta, ...)会让窗口变成非法区间alpha beta剪枝条件在第一层就恒成立搜索直接返回一个错误分数。这种错误的可怕之处在于它不会报错程序照常运行只是 AI 的棋力莫名其妙地崩了而且崩得不规律有时候还挺像那么回事。这是典型的“玄学 bug”靠读棋谱是读不出来的只能靠打印每层的 alpha/beta 区间和节点数来核对。另外根节点要单独处理它需要记录具体是哪一步拿到了最优分而 negamax 只返回分数。常见做法是在根节点显式循环候选点、手动维护best_move而不是把根节点也塞进递归。4. 评估函数AI 的“棋感”是怎么被量化的搜索只负责“把评估函数用对”真正的棋力上限由评估函数决定。一个只看子力数量的评估函数配上深度 10 的搜索下出来的棋依然幼稚而一个能准确识别活三、冲四、双威胁的评估函数深度 4 就已经相当能打。4.1 把“活三”“冲四”翻译成模式串五子棋的棋型本质上是一段连续线上的局部形状。把每条线横、竖、两条斜线共 4 个方向抽成一个字符串用 0 表示空、1 表示己方、2 表示对方或墙棋型识别就变成了子串匹配。# 键为模式串值为该棋型的分数数字含义1 己方0 空2 对方/墙 SHAPE_SCORES { 11111: 1000000, # 五连直接获胜 011110: 100000, # 活四两端可成五无法阻挡 011112: 10000, # 冲四一端被封 211110: 10000, 01110: 8000, # 活三下一步可变活四 010110: 8000, # 跳活三同样具备威胁 001112: 1000, # 眠三 011010: 1000, 001100: 500, # 活二 001010: 300, } def line_score(line): # 两端补墙保证边界棋型也能被匹配到 s 2 .join(str(x) for x in line) 2 total 0 for pat, score in SHAPE_SCORES.items(): total s.count(pat) * score return totalline_score逐行扫描整条线统计每种棋型出现次数并累加。两端补2是关键细节如果不补1111在棋盘边缘会匹配不到任何模式AI 就会对边线上的四连视而不见。4.2 进攻分减防守分双向评估的必要性只算自己的棋型AI 会变成一个只顾进攻、不断漏防、最终输掉棋局的对手。正确的做法是同一套模式表跑两遍一遍把自己当 1一遍把对方当 1然后做差。def evaluate(board, player): opp 3 - player my_total, opp_total 0, 0 for line in iter_all_lines(board): my_total line_score([1 if v player else (0 if v EMPTY else 2) for v in line]) opp_total line_score([1 if v opp else (0 if v EMPTY else 2) for v in line]) # 防守权重略高于进攻避免 AI 沉迷进攻不设防 return my_total - int(opp_total * 1.1)1.1这个系数是调出来的不是算出来的。取值大于 1 会让 AI 更保守小于 1 会让它更激进。不同棋力的人类对手适合不同系数这也是为什么很多实现里这个值被写成可调参数——它本质上是在调 AI 的性格。注意evaluate返回的是“当前走子方”的分数而 negamax 在每层都会切换走子方。如果这里误写成固定按黑棋视角算白棋的搜索会整体符号反转表现为 AI 一旦执白就疯狂送子。4.3 全盘评估与增量更新的取舍上面的evaluate每次都要扫全盘 15 行、15 列、29 条主对角线、29 条副对角线约 88 条线、每条平均 15 个格子单次调用上千次操作。在深度 6、节点数万的情况下光是评估就能吃掉大部分时间。常见的优化思路是增量评估落子时只重算经过该点的 4 条线把分数差值累加到一个全局变量上。这样单次落子/撤销的评估成本从 O(棋盘) 降到 O(4×15)。但增量更新有代价一旦撤销逻辑和落子逻辑不对称比如漏算了被覆盖的那颗子误差会一直累积下去最后 AI 的评分完全失真。血泪经验是先写全盘评估把功能跑通确认棋力正常再改增量版本并且保留一个开关随时能切回全盘评估做对比。如果两者在相同局面下分数差异超过阈值就说明增量逻辑有 bug。4.4 威胁检测比棋型分数更直接的信号棋型分数是静态的但有些局面靠分数表达不出来比如“双活三”和“活三加冲四”这种组合威胁。这类局面在分数上看可能只比单个活三高一点实际上已经是必胜。处理方式是在评估函数里加一条显式规则统计当前局面上达到活三及以上级别的棋型数量如果有两个及以上且分属不同方向直接给一个远超普通棋型的分数。这条规则粗糙但在实战里极有效因为它把“组合威胁”这个人类棋手最依赖的判断用几行代码近似了出来。5. 避坑与排查那些让 AI 下出“臭棋”的实现细节功能跑通只是开始真正折磨人的是那些“程序不报错但棋力诡异”的问题。下面几条是按踩坑频率排的每条都给出可复现的现象和定位方法。5.1 现象AI 落子位置已经有棋子或落在棋盘外原因通常是搜索过程中落子与撤销不配对。递归里有return提前退出、或者剪枝break之后忘了undo都会让棋盘状态比实际多出几颗子。另一种情况是best_move在根节点用局部变量记录但因为异常分支没有赋值最后返回了初始化的-1。解决办法是把落子/撤销包成上下文管理器或者用try/finally保证一定执行撤销。同时在根节点返回前加一道断言assert board.cells[best_move] EMPTY。这类断言在开发期开着能省下大量排查时间。5.2 现象AI 每一步都要想十几秒界面卡死无响应pygame 是单线程事件循环搜索直接跑在主循环里界面必然假死。更糟的是 Windows 上窗口会显示“未响应”用户以为程序崩了。解决分两层一是把搜索放进独立线程主线程继续跑pygame.event.get()和绘制通过一个共享变量传回结果二是给搜索加时间预算用迭代加深——先搜深度 2再搜深度 4每层结束后检查是否超时超时就返回上一层的结果。迭代加深看似重复劳动但因为上一层的结果可以用来给这一层排序实际总开销通常只比直接搜最深一层多百分之二三十换来的是“任何时候被打断都有一个可用的答案”。5.3 现象AI 明明能赢却选择和棋或者必胜局面下反复绕圈原因是终局分数没有带深度修正。所有胜利都返回同一个WIN搜索就失去了“尽快结束”的偏好在多个必胜分支里随机游走。解决是把返回值写成WIN - depth赢和-WIN depth输深度越小分数越高。这样 AI 会自动选最短的取胜路径也会在被将死时选最长的抵抗路线。5.4 现象AI 执着于进攻对对手的活三完全不设防这是评估函数只算单方棋型的典型症状。表现很规律AI 会一直做自己的活二、活三直到对手冲四才反应过来但那时已经晚了。解决是双向评估并把防守分乘一个略大于 1 的系数。另一个更细的调整是对手的活三在评分上要略高于自己的活三因为五子棋先手方天然占优后手必须更重视防守。这个不对称是很多实现忽略的细节。5.5 现象同一局面下 AI 前后两次给出的落子不一样如果搜索本身是确定性的结果应该稳定。出现抖动通常是两个原因候选点用了set且没有稳定排序导致相同分数的点在排序后的位置随机或者置换表用了 Python 内置hash()而字符串哈希在进程间有随机化。解决是把候选点排序改成sorted(cand, keylambda x: (-score(x), x))用位置作为第二关键字打破平局置换表的键改用 Zobrist 哈希用固定的随机数表对每个格子的每种颜色做异或保证跨进程稳定。6. 深度与广度的取舍为什么不能一路加深下去搜索深度从 4 加到 6节点数在理想剪枝下大约涨 3 到 10 倍棋力提升明显从 6 加到 8很多实现就开始卡在时间预算边缘而且收益并不线性——因为深度越深叶子节点的评估误差被放大的机会越多这叫“奇数层效应”搜到奇数层时评估函数是在对手走完后的局面上算的天然偏向对手AI 会变得保守甚至自暴自弃。工程上的应对是迭代加深只取偶数层结果或者用静态搜索quiescence search在叶子节点继续展开“吃子”类强制走法直到局面平静。五子棋里的“吃子”对应的是冲四和活四这类必须应对的威胁在叶子节点把它们展开完能显著减少评估误差。另一组取舍在候选点数量上。limit从 12 降到 8同样时间内能多搜一层但会漏掉一些冷门好点从 12 升到 20广度上去了深度就得砍。我的经验是在中低深度区间4 到 6 层优先保广度因为浅层漏掉关键点的代价太大深度上到 8 层以上再收紧候选数让排序质量承担筛选工作。配置深度每层候选单步耗时纯 Python 量级适用场景轻量410数十毫秒网页演示、低配设备均衡612半秒到一秒桌面人机对战强力810数秒允许思考时间的对局最后是一个验证方法不要靠“感觉这盘下得不错”来判断改动是否有效。准备一组固定的开局局面让新旧两版各跑一遍比较落子坐标和搜索节点数再让两版互相对弈若干局看胜率变化。这个流程比单盘观感可靠得多也是我后来每次改动评估函数或剪枝顺序都会走一遍的固定动作。有次我只调了一个棋型分数观感上觉得 AI 变强了跑完这组对照才发现它只是变得更激进对活三的防守反而退化了。从那以后我每次动评估表或者候选点排序都强制走一遍这组固定局面加互弈的对照宁可多花二十分钟也不信单盘的感觉。希望帮到你。本文还有配套的精品资源点击获取
