★ FEATURED ARTICLE 简介这是一份面向Python初学者与棋类算法爱好者的五子棋人机对战实现方案核心解决电脑走步的智能选取问题。程序采用极大极小值搜索并引入α-β剪枝提升搜索效率同时实现候选落点生成与评估函数设计评估函数直接决定AI棋力强弱。整体还包含先后手切换、胜负判断、棋盘绘制与信息显示等完整交互逻辑基于pygame构建界面适合作为算法课程设计或博弈树剪枝学习的练手项目。资源包共3个文件以2个py源码和1个txt说明为主源码承载游戏主逻辑与按钮交互说明文件辅助理解压缩包约15KB体量轻便易于阅读调试。目前已有4705人学习下载读者可从中获得可运行的完整代码、评估函数与剪枝实现思路以及先后手切换、重开与退出等交互细节的参考写法便于对照理解并二次改造。1. 五子棋 AI 的「聪明」是假象为什么 15×15 的棋盘能算出必胜手很多人第一次跑通五子棋人机对战时都会愣一下棋盘 15×15理论状态空间比宇宙原子数还多可电脑落子却快得不像话甚至能提前堵死你三步之后的杀招。这不是它「算得多」恰恰相反——它算得很少。真正让这套基于 α-β 剪枝的 Python 实现跑得动的是一个反直觉的事实绝大多数分支根本不需要展开因为对手不会配合你走那些蠢棋。α-β 剪枝的核心不是搜索更多而是用已经找到的「够好的解」当门槛把注定更差的分支整棵砍掉。搞懂这件事你才能明白为什么一个几百行的 pygame 项目能在普通笔记本上做到秒级响应也才能看懂后面那些看似随意的参数到底在权衡什么。2. 极大极小值把「我赢」翻译成一台机器能算的数2.1 从棋局到分数评估函数才是 AI 的灵魂搜索算法本身不聪明聪明的是它怎么给一个局面打分。五子棋的评估函数通常按「连子形态」给分活四、冲四、活三、眠三、活二依次递减因为活四基本等于赢了冲四只差一步活三再走一步就能变活四。常见的实现思路是扫描四个方向横、竖、两条斜线对每个空位或棋子统计连续同色数量和两端是否被封堵再查一张分值表。# 评估单个方向的连子形态返回该形态的分值 def score_direction(board, x, y, dx, dy, role): count 1 # 当前棋子本身 block 0 # 被封堵的端点数 empty -1 # 记录跳活三这类中间空位 # 正向延伸 for i in range(1, 5): nx, ny x dx * i, y dy * i if not in_board(nx, ny): block 1 break if board[nx][ny] role: count 1 elif board[nx][ny] 0: empty i break else: block 1 break # 反向延伸逻辑对称此处省略 return SHAPE_SCORE.get((count, block), 0)这段代码的关键在block和empty两个变量block统计两端被对方棋子或边界堵死的次数empty记录连续子中间是否夹着一个空位跳活三的判定依据。参数role决定评估的是己方还是对方同一套函数复用两次己方得分减去对方得分就是当前局面的净价值。分值表SHAPE_SCORE是整套 AI 的「价值观」改它比改搜索深度更能影响棋风——把活三调高AI 会变得激进抢攻把冲四调高它会优先做必杀。2.2 极大极小值的递归结构为什么 AI 要「替对手想」有了评估函数接下来要解决「我走一步之后对手会怎么回应」。极大极小值Minimax的思路是假设双方都绝对理性我方回合取所有走法里分值最高的Max 层对方回合取让我方分值最低的Min 层交替递归到指定深度再把叶子节点的评估值回传。这样得到的根节点分值就是「在对手全力阻挠下我能拿到的最好结果」。def minimax(board, depth, is_max, role, opp): if depth 0 or game_over(board): return evaluate(board, role, opp) if is_max: best -INF for move in gen_moves(board): board[move] role best max(best, minimax(board, depth - 1, False, role, opp)) board[move] 0 # 回溯撤销落子 return best else: best INF for move in gen_moves(board): board[move] opp best min(best, minimax(board, depth - 1, True, role, opp)) board[move] 0 return bestis_max标记当前是己方还是对方回合role和opp分别是我方和对方棋子颜色。注意board[move] 0这行回溯——搜索是在同一块棋盘上原地修改再撤销的不复制棋盘这是 Python 里省内存的关键。但纯 Minimax 有个致命问题分支因子太大。15×15 棋盘每层几十个候选点深度 4 就是几十的四次方根本跑不完。这就是 α-β 剪枝要登场的地方。3. α-β 剪枝为什么「够好的解」能砍掉整棵子树3.1 α 和 β 到底是什么两个边界值的物理含义α 是 Max 层当前已经找到的最好分值下界β 是 Min 层当前已经找到的最差分值上界。搜索过程中如果某个 Min 节点发现自己的 β 已经小于等于祖先 Max 节点的 α说明这条路走下去 Max 一定不会选它——因为 Max 在更上层已经有一个不差于它的选择。此时剩下的兄弟分支全部可以跳过这就是剪枝。def alphabeta(board, depth, alpha, beta, is_max, role, opp): if depth 0 or game_over(board): return evaluate(board, role, opp) if is_max: best -INF for move in gen_moves(board): board[move] role val alphabeta(board, depth - 1, alpha, beta, False, role, opp) board[move] 0 best max(best, val) alpha max(alpha, best) if beta alpha: # 剪枝Min 层不会让这个分支存活 break return best else: best INF for move in gen_moves(board): board[move] opp val alphabeta(board, depth - 1, alpha, beta, True, role, opp) board[move] 0 best min(best, val) beta min(beta, best) if beta alpha: # 对称剪枝 break return bestalpha和beta作为参数在递归中向下传递alpha max(alpha, best)在 Max 层不断抬高下界beta min(beta, best)在 Min 层不断压低上界。一旦beta alpha说明当前窗口已经空了继续搜没有意义。剪枝效率极度依赖走法顺序先搜好棋α 抬得快剪得就狠。所以工程上通常先对候选点按启发式排序比如优先搜靠近已有棋子的位置、优先搜评估分高的点。3.2 走法生成与排序剪枝效率的胜负手gen_moves如果返回全部 225 个空位剪枝再强也救不回来。实战做法是只考虑已有棋子周围两格内的空位把候选点从 225 压到几十个。再按「该点落子后的局部评估分」降序排列让高价值走法先被搜索。def gen_moves(board, role, opp): candidates set() for x in range(SIZE): for y in range(SIZE): if board[x][y] ! 0: # 只收集棋子周围 2 格内的空位 for dx in range(-2, 3): for dy in range(-2, 3): nx, ny x dx, y dy if in_board(nx, ny) and board[nx][ny] 0: candidates.add((nx, ny)) # 按落子后的局部得分降序好棋先搜剪枝更早触发 return sorted(candidates, keylambda m: local_score(board, m, role, opp), reverseTrue)local_score只评估该点四个方向的形态分不递归开销很小。排序带来的收益远超排序本身的成本——好的走法顺序能让 α-β 的有效分支因子从 b 降到约 √b相当于同样时间多搜一倍深度。这也是为什么很多实现里排序函数写得比搜索函数还讲究。4. 避坑与排查那些让 AI 变傻或卡死的细节4.1 现象AI 明明能赢却去堵无关位置原因通常是评估函数里己方和对方的权重没配平。如果只算己方连子分AI 会沉迷进攻如果对方权重过高它会过度防守。解决方法是让评估返回「己方总分 - 对方总分 × 防守系数」防守系数一般取 0.8 到 1.2 之间调。另一个常见原因是搜索深度太浅看不到两步之后的杀招把深度从 2 提到 4 通常能明显改善。4.2 现象落子后棋盘状态错乱AI 走出非法手这是回溯没写干净导致的。搜索时board[move] role之后无论走哪个分支返回前都必须board[move] 0。如果中途break剪枝也要保证撤销发生在 break 之前。血泪经验是把落子和撤销包成一对用 try/finally 或者干脆在循环开头就写好撤销别指望自己记得。4.3 现象AI 思考时间忽长忽短偶尔卡住几秒候选点没做范围限制或者排序失效导致剪枝退化。检查gen_moves是否真的只返回棋子附近的点以及排序键是否在每次调用时都重新计算。另一个隐蔽原因是game_over判定写得太重在每个叶子节点都全盘扫描五连改成只检查最后落子点周围四个方向能省大量时间。4.4 现象AI 第一手就下在天元旁边看起来很蠢空棋盘时gen_moves收集不到任何棋子周围的点候选集为空。需要特判如果棋盘为空直接返回中心点。这个坑几乎每个手写实现都会踩一次因为逻辑上「周围两格」在空盘上确实没有候选。4.5 现象改了评估分值表AI 行为没变化大概率是分值表被缓存或没重新加载也可能是搜索深度太浅叶子节点的评估根本没机会影响根节点决策。先确认深度至少为 2再打印几个叶子节点的评估值看分值表是否真的生效。如果用的是模块级常量改完记得重启进程。5. 从能跑到能打深度、剪枝与评估精度的三角权衡把 α-β 剪枝跑通只是起点真正决定这套五子棋 AI 强弱的是三个互相拉扯的旋钮搜索深度、剪枝效率、评估精度。深度每加一层理论棋力上一个台阶但耗时按分支因子指数增长剪枝效率靠走法排序和候选点裁剪来提升本质是「用启发式换时间」评估精度则决定叶子节点回传的值可不可信评估粗糙时加深搜索反而会把错误放大。一个实用的调参顺序是先把深度定在 4保证秒级响应再优化gen_moves的候选范围和排序观察同样深度下耗时下降多少最后微调评估分值表用固定开局对弈几十局看胜率变化。常见的实现思路是给不同深度设不同候选数浅层多留点、深层少留点因为深层本来就是用来验证浅层判断的。验证 AI 是否真的在变强别只看它跟你下——人会被自己的水平限制。更靠谱的做法是让两个不同参数的 AI 互相对弈固定开局、固定先后手跑一百局统计胜率。如果新参数胜率没有显著提升说明瓶颈不在你改的那个旋钮上。我一般会先确认搜索深度是否吃满、剪枝是否真的触发打印剪枝次数再去动评估函数否则很容易在错误的地方反复折腾。这套基于 α-β 剪枝的 Python 实现价值不在于它有多强而在于它把「搜索 评估 剪枝」这条经典链路完整地摊开在你面前每一行都能改、每一个参数都能看到后果。想真正吃透最好的办法是把源码拉下来先把深度改成 1 看它多蠢再一层层加上去亲眼看着剪枝次数和思考时间的变化。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
