简介这是一份用Python实现的AI五子棋项目面向Python开发者、AI算法初学者以及博弈编程爱好者重点演示极大极小值搜索与Alpha-Beta剪枝如何从理论变为可运行的人机对战程序。压缩包内共12个文件包含两个主要Python脚本、一个编译后的pyc文件、项目配置文件xml/iml、说明文档doc/pdf及gitignore等整体仅150KB结构紧凑。其中Python源码覆盖棋盘判定、AI落子、图形界面与主程序入口配合外文论文和中文文档可对照学习搜索树展开、局面评估、剪枝条件以及缓存优化等实现细节。已有3016人学习下载资源轻量但完整既能作为课程设计或毕业设计的参考也适合该项目的爱好者下载后直接运行、改写和二次开发。通过实际代码理解Minimax与Alpha-Beta剪枝比抽象阅读算法描述更直观尤其适合希望夯实AI基础的学习者。1. 从零复现一个会下五子棋的AI极大极小值搜索不是黑匣子期末要交课程设计翻了几天资料最后选中了这份带论文、带源码的Python AI五子棋项目。它不是神经网络那种黑匣子而是用决策树里最经典的极大极小值搜索Minimax配合Alpha-Beta剪枝让程序在15×15棋盘上和人正经对弈。整份代码结构清晰适合正在做算法课设、想搞懂搜索策略实战、又不想碰强化学习那么重内容的Python开发者。压缩包里除了主程序还附了一篇英文参考论文和一份中文项目文档写报告时能直接对着抄结构和公式。下面我把这份资源从算法原理拆到代码实现再讲调参时最容易翻车的几个位置你有多少基础都能跟得上。2. 先立住算法极大极小值搜索与Alpha-Beta剪枝的实现边界五子棋是典型的双人零和博弈AI赢人类就输棋盘上任意局面都能用一个数值表示“AI赢的可能性”。极大极小值搜索正是基于这个前提AI回合是MAX层在所有合法落子里选评估值最大的人类回合是MIN层假设对手会选让AI最难受的落子也就是评估值最小的。两层交替向下展开直到搜到设定深度或分出胜负。这套逻辑天然适配五子棋因为它的评估函数好定义——胜负由五连决定中间局面则用活三、冲四、眠三这些局部棋形近似刻画。相比围棋那种全局性强、局部评估误差大的棋类五子棋的局部棋形与最终胜负相关度高所以不需要太深的搜索就能下出“像样”的棋。一个容易被忽略的前提Minimax假设对手每一步都回应最优AI在算的是“最坏情况下我能保住多少”。它不赌对手失误宁可把对手想得足够强这就是为什么Minimax搜索出来的棋看起来特别稳该防一定防不贪侥幸。理解这一点后面调评估函数时你才不会疑惑“AI怎么这么怂”。2.1 MAX/MIN交替决策树里的攻防角色怎么切换Minimax的递归结构很固定每一层先判断当前轮到谁轮到AI就取子节点分数的最大值轮到对手就取最小值。递归过程模拟的是双方轮流落子搜索深度就是往后看了几步棋。# 伪代码展示核心结构 def minimax(board, depth, is_maximizing, ai_player): if depth 0 or game_over(board): return evaluate(board, ai_player) if is_maximizing: best -float(inf) for move in get_moves(board): board[move] ai_player best max(best, minimax(board, depth - 1, False, ai_player)) board[move] 0 return best else: best float(inf) for move in get_moves(board): board[move] 3 - ai_player # 对手落子 best min(best, minimax(board, depth - 1, True, ai_player)) board[move] 0 return best逻辑说明max层把分数越推越高min层把分数越压越低递归自然形成攻防交替。每次落子后必须复位棋盘这是回溯的本质少了这一步搜索树会“污染”。参数说明ai_player用1表示黑棋、2表示白棋3 - ai_player就是对手编号depth是剩余搜索层数每深入一层减1归零时调用评估函数。2.2 Alpha-Beta剪枝两个边界值如何把搜索量降一个数量级Minimax的硬伤是复杂度随深度指数增长分支因子B、深度D时最坏要搜B的D次方个节点。Alpha-Beta剪枝通过维护两个边界值提前放弃没希望的分支Alpha是MAX层已经确定能拿到的最优下界初始为负无穷Beta是MIN层已经确定能接受的最优上界初始为正无穷。搜索过程中只要beta不大于alpha当前分支无论再展开多少层都不会影响父节点决策直接剪掉。这里的关键认知是剪枝不改变搜索结果只改变搜索量。它只是把“算完整棵树再比较”换成“边算边比较没希望的分支提前终止”。理想情况下配合良好的走法排序复杂度能从O(B^D)降到约O(B^(D/2))相当于同样时间多搜一倍的深度。不少初学者以为剪枝是近似优化其实不是被剪掉的分支一定不影响根节点的最终选择。用数字举例根节点是MAX层已搜完第一个分支拿到评估值3Alpha更新为3。接着搜第二个分支它是MIN层第一个叶节点返回2。因为MIN会选数值最小的节点所以这个分支里MIN最多只能拿出2而MAX已经在别处拿到了至少3的保证剩下的几十个节点就不用看了直接剪枝这就是alpha beta发生的瞬间。2.3 递归效率的隐藏前提终局检查必须放在入口实际落地Alpha-Beta时递归函数入口处要先检查棋盘是否有五连有就直接返回大分值不再向下展开。这一条看着简单实际项目里我见过不少实现把它放到了depth 0才判断结果AI在“再走一步就五连”的局面上反应迟钝问题就出在终局检查的位置太晚。另一个隐藏细节是评估值的符号统一。整棵搜索树返回的分数都站在AI视角正值对AI有利负值对AI不利符号不能在中途反转。MIN层如果写错方向比如也取了最大值AI会表现得像在帮对手走棋。这两个位置是我评估“一个人是不是真懂了Minimax”的快速判断标准也是后面第4章会展开的两个高频翻车点。3. 把项目跑起来文件结构、评估函数与搜索主循环逐段拆解3.1 压缩包文件清单先分清主程序和依赖库解压后第一件事是弄清楚每个文件干嘛的按我实际跑通的顺序整理成了一张表文件/目录类型作用GOAI_RUN.py主程序游戏循环、AI决策入口、人机交互graphics.py依赖库graphics教学绘图库负责棋盘渲染与鼠标点击references/wagnervirag_2001.pdf参考资料与搜索算法相关的英文论文论文内容.doc文档项目配套论文含算法与实现说明pycache/graphics.cpython-36.pyc缓存原环境Python 3.6编译产物可整个删掉.idea/IDE配置PyCharm项目文件对运行无影响运行顺序很直接先确认环境有tkinter然后直接跑GOAI_RUN.pygraphics.py会被当作本地模块导入不需要pip安装。但如果你当前Python版本和原来的3.6差得远建议先删掉__pycache__整个目录让解释器重新生成当前版本的缓存文件。老项目带着旧pyc在新环境里报ModuleNotFoundError的情况太常见了。3.2 棋盘表示与候选点生成为什么不该遍历全部361个点棋盘用15×15的二维列表0表示空、1表示黑棋、2表示白棋board[r][c]直接索引渲染时按坐标换算像素这个选择最朴素也最好调试。真正影响搜索性能的是候选点生成——如果每层递归都把全盘空点当作分支深度4时最坏要展开361的4次方量级路径个人电脑直接卡死。工程上的常见做法是只取“最后一次落子周围两格以内的空点”作为候选。五子棋的棋子有聚集性离最近一子太远的点既威胁不到对方也形成不了自己的攻势在深层搜索里几乎不会成为最优解。def generate_moves(board, last_move, radius2): 生成候选落子只扫描最近落子周围 radius 格内的空点 if last_move is None: return [(7, 7)] # 空棋盘时先落天元 moves set() r0, c0 last_move for r in range(max(0, r0 - radius), min(15, r0 radius 1)): for c in range(max(0, c0 - radius), min(15, c0 radius 1)): if board[r][c] 0: moves.add((r, c)) return list(moves)逻辑说明last_move是上一手坐标range边界用max和min裁剪防止数组越界。返回list而不是set方便后面排序和遍历。参数说明radius取2时候选点最多约24个足够覆盖绝大多数局部攻防取3搜索量明显上升适合开局阶段。我见过有人在开局强制全盘搜索、中后盘切回radius2效果不错但要多维护一个阶段判断。3.3 评估函数棋形打分是整份代码的“棋感来源”评估函数决定了AI的棋力上限也是最容易改出“玄学”效果的地方。不要把它当黑匣子拆开看就是四步沿四个方向数同色连子长度、统计两端封堵情况、映射成棋形名称、按棋形累加分数。SHAPE_SCORE { FIVE: 100000, # 五连直接赢 LIVE4: 50000, # 活四对手挡不住 RUSH4: 5000, # 冲四逼对手应 LIVE3: 1000, # 活三下一步可能成四 SLEEP3: 200, # 眠三威胁减半 LIVE2: 100, # 活二潜在发展 SLEEP2: 20, # 眠二 } def count_line(board, r, c, dr, dc, player): 从(r,c)出发沿(dr,dc)双向数同色连子返回长度和封堵数 length 0 blocked 0 rr, cc r, c while 0 rr 15 and 0 cc 15 and board[rr][cc] player: length 1 rr dr cc dc if 0 rr 15 and 0 cc 15 and board[rr][cc] ! 0: blocked 1 rr, cc r - dr, c - dc while 0 rr 15 and 0 cc 15 and board[rr][cc] player: length 1 rr - dr cc - dc if 0 rr 15 and 0 cc 15 and board[rr][cc] ! 0: blocked 1 return length, blocked def classify(length, blocked): 把连子长度和封堵数映射成棋形名 if length 5: return FIVE if blocked 0: if length 4: return LIVE4 if length 3: return LIVE3 if length 2: return LIVE2 if blocked 1: if length 4: return RUSH4 if length 3: return SLEEP3 if length 2: return SLEEP2 return NONE def evaluate_board(board, ai_player): 整盘打分AI总分减去对手总分的加权值 directions [(1, 0), (0, 1), (1, 1), (1, -1)] ai_score 0 human_score 0 for r in range(15): for c in range(15): player board[r][c] if player 0: continue for dr, dc in directions: # 只统计以当前点为起点的连子避免同一条线重复计数 if 0 r - dr 15 and 0 c - dc 15 and board[r - dr][c - dc] player: continue length, blocked count_line(board, r, c, dr, dc, player) shape classify(length, blocked) if player ai_player: ai_score SHAPE_SCORE[shape] else: human_score SHAPE_SCORE[shape] return ai_score - int(human_score * 1.2)逻辑说明evaluate_board扫描所有非空格子沿横、竖、两条对角线统计连子。起点判断是关键当前格子的前一个位置不是同色棋子时才把它当作连子起点防止同一条五连线被重复计分。参数说明human_score乘1.2是把对手威胁放大两成让AI防守更敏感想更激进就调低这个系数想更稳健就调高。这是整份代码里性价比最高的调参位置。3.4 搜索主循环递归、剪枝与最佳落子回传搜索主循环把前面的概念全部串起来。找到最佳走法的逻辑是先枚举AI这一步的候选落子每落一子就调用递归搜索评估后续局面最后取分数最高的那个位置返回。递归内部通过is_maximizing在MAX层和MIN层之间切换alpha和beta随递归向上传递。def minimax(board, depth, alpha, beta, is_maximizing, last_move, ai_player): winner check_winner(board) if winner ai_player: return 100000 depth if winner ! 0: return -100000 - depth if depth 0: return evaluate_board(board, ai_player) moves generate_moves(board, last_move, radius2) # 走法排序让alpha-beta尽早遇到好分支 moves.sort( keylambda m: score_position( board, m[0], m[1], ai_player if is_maximizing else (3 - ai_player) ), reverseTrue, ) if is_maximizing: max_eval -float(inf) for r, c in moves: board[r][c] ai_player val minimax(board, depth - 1, alpha, beta, False, (r, c), ai_player) board[r][c] 0 max_eval max(max_eval, val) alpha max(alpha, val) if beta alpha: break # 剪枝 return max_eval else: opponent 3 - ai_player min_eval float(inf) for r, c in moves: board[r][c] opponent val minimax(board, depth - 1, alpha, beta, True, (r, c), ai_player) board[r][c] 0 min_eval min(min_eval, val) beta min(beta, val) if beta alpha: break # 剪枝 return min_eval def find_best_move(board, ai_player, last_move, depth4): best_move None best_val -float(inf) for r, c in generate_moves(board, last_move, radius2): board[r][c] ai_player val minimax(board, depth - 1, -float(inf), float(inf), False, (r, c), ai_player) board[r][c] 0 if val best_val: best_val val best_move (r, c) return best_move逻辑说明check_winner做四方向五连扫描返回胜方编号score_position是3.3里评估函数的单点版本只统计某个候选点对四个方向棋形的贡献用来排序已经足够。find_best_move枚举AI第一步落子逐层调用minimax最后返回评估值最高的落子位置。参数说明depth是总搜索深度我调试时从2、3、4逐级试。depth2时AI只会应冲四和保活三相当于入门depth4能看到“先活三再反冲四”的两步交换棋力明显上来depth6以上必须依赖候选点裁剪和走法排序否则单步耗时在普通笔记本上会超过10秒。搜索结束后递归落子必须复位成0漏掉这一步棋盘上会出现“幽灵棋子”AI后半盘会突然乱下。提示调试时如果发现AI下棋时快时慢优先查两处——递归里board是否正常回退以及走法排序是否真的生效。这两处占了我此前调这个项目时踩坑的七成。4. 调参避坑深度、候选点与UI层的五个常见问题4.1 落子慢得像卡死候选点和深度先查这两处现象AI每一步要算十几秒看起来像程序无响应。原因搜索深度设太高同时候选点没有裁剪。depth4配全盘候选点时状态数直接爆炸个人电脑基本不可用。某些实现还在递归里重复调用全盘扫描的get_moves更是雪上加霜。解决把generate_moves限定为radius2的局部候选再把find_best_move的depth从2开始向上调。我给自己定的约束是单步搜索超过2秒就降一档深度。同时在每层搜索入口打印当前候选点数量如果始终超过100个说明候选生成逻辑漏了裁剪。4.2 AI只会攻不会守评估函数漏了对手分数现象AI每次都往自己的冲四处落子对手都活三了也不去堵整盘棋像在自嗨。原因评估函数只统计了AI一方的棋形分数。五子棋是零和博弈最好的进攻往往就是防守——你在对手活三上堵一下自己的子同时可能构成反攻。只算单方分数AI就对对手的威胁视而不见。解决把评估函数改成“AI总分 - 对手总分”。乘1.2的系数是攻防倾向的旋钮想稳就调高想凶就调低。至少保证对手的冲四、活三分值能抵消你的单方棋形得分AI才会在进攻和防守之间真正做权衡。4.3 剪枝没生效走法排序是剪枝的前置条件现象加了alpha-beta后搜索节点数没有明显下降每步还是很慢。原因剪枝效率高度依赖走法排序。如果第一层就把最差的走法排在最前alpha更新极慢剪枝基本不触发。很多教程只讲剪枝原理不讲它有个隐含前提——好走法要先搜。解决在展开moves之前按score_position做一次降序排序。粗糙的启发式排序就能让剪枝效率提升一个数量级。我的实测数据是不排序时depth4可能展开上万节点排序后通常两三千就结束。排序逻辑就是3.4代码块里的moves.sort别嫌它占那一行耗时。4.4 graphics窗口打不开先清理缓存再查tkinter现象运行GOAI_RUN.py时直接报错提示graphics模块导入失败或者窗口闪一下就消失。原因压缩包里的__pycache__/graphics.cpython-36.pyc是Python 3.6的编译产物在Python 3.10及以上环境里加载旧字节码会失败。graphics.py本身依赖tkinter如果装的是精简版Python或缺系统组件导入就会中断。解决先删除整个__pycache__目录让解释器重新生成当前版本的缓存文件。再确认tkinter可用命令行执行python -c import tkinter无报错。Windows用官方安装包默认带tkinterLinux服务端发行版可能要单独装python3-tk。4.5 AI主动送棋MIN层取反和终局检查位置现象AI单步看起来正常但经常主动把棋送到对手的枪口上比如给对手制造活三机会。原因两个典型错误。一是MIN层写错方向对手回合也取了最大值等于AI在替对手走棋二是终局检查放在depth 0处搜索深度为奇数或偶数时对“再走一步就赢”的局面的判断会不一致。解决给minimax加一行调试打印在搜索入口输出当前回合和层数肉眼确认MAX层对应AI先手、MIN层对应对手。终局检查必须放在递归函数入口处、深度判断之前。再用半小时写一个测试摆一个已知的“两步杀”局面让AI走如果AI抓不住优先怀疑终局检查位置而不是评估函数。5. 让AI再强一档走法排序与迭代加深的落地技巧先说一个反直觉的结论同样的代码框架里决定棋力上限的往往不是评估函数写得有多细腻而是搜索深度和剪枝效率的配合。评估函数粗糙一点没关系只要搜索多一层AI就能多算一步交换棋力立刻上一个台阶。所以最后这两个技巧都围绕“限定时间内搜得更深”展开。第一个技巧是迭代加深。与其固定depth4不如从depth2开始逐层加深每层之间检查耗时超时就把上一层的最佳走法返回。这么做还有一个副产品上一层算出的最佳走法会作为下一层排序的首选因为浅层和深层搜索的最优走法高度相关第一分支就命中好走法时alpha-beta收敛会非常快。代码就是包一层循环def find_best_move_iterative(board, ai_player, last_move, max_time2.0): start time.time() best None for depth in range(2, 8): candidate find_best_move(board, ai_player, last_move, depthdepth) best candidate if time.time() - start max_time: break return best逻辑说明每完成一层就暂存一份结果超时后直接返回上一深度算出的走法。它不追求单层最优只保证在限定时间里把当前搜得最深的一步交还给交互逻辑下棋过程不会出现让人干等的长停顿。第二个技巧是给排序函数加攻防权重。许多实现里的排序只按当前玩家视角打分导致AI在攻防转换时慢半拍。我的做法是对AI和对手的候选点分别打分取加权差作为排序键让搜索层优先看“同时威胁对手”的着法。排序不需要精确计算它只影响剪枝效率所以别在这一步消耗太多开销。如果你打算拿这份资源交课程设计我建议把评估函数单独拆成模块论文里附两张搜索节点统计图一张是不排序depth4的数据一张是排序后的。这组对比是Alpha-Beta剪枝价值最直观的证明答辩时也最好讲。从那以后我每次改完评估函数都要先跑一组AI先后手各20手的对照记录每手耗时和剪枝命中率再谈增强。希望这个习惯和你这次跑通的代码都能帮到你。本文还有配套的精品资源点击获取 从零复现五子棋AI：极大极小值搜索与Alpha-Beta剪枝实战解析
简介这是一份用Python实现的AI五子棋项目面向Python开发者、AI算法初学者以及博弈编程爱好者重点演示极大极小值搜索与Alpha-Beta剪枝如何从理论变为可运行的人机对战程序。压缩包内共12个文件包含两个主要Python脚本、一个编译后的pyc文件、项目配置文件xml/iml、说明文档doc/pdf及gitignore等整体仅150KB结构紧凑。其中Python源码覆盖棋盘判定、AI落子、图形界面与主程序入口配合外文论文和中文文档可对照学习搜索树展开、局面评估、剪枝条件以及缓存优化等实现细节。已有3016人学习下载资源轻量但完整既能作为课程设计或毕业设计的参考也适合该项目的爱好者下载后直接运行、改写和二次开发。通过实际代码理解Minimax与Alpha-Beta剪枝比抽象阅读算法描述更直观尤其适合希望夯实AI基础的学习者。1. 从零复现一个会下五子棋的AI极大极小值搜索不是黑匣子期末要交课程设计翻了几天资料最后选中了这份带论文、带源码的Python AI五子棋项目。它不是神经网络那种黑匣子而是用决策树里最经典的极大极小值搜索Minimax配合Alpha-Beta剪枝让程序在15×15棋盘上和人正经对弈。整份代码结构清晰适合正在做算法课设、想搞懂搜索策略实战、又不想碰强化学习那么重内容的Python开发者。压缩包里除了主程序还附了一篇英文参考论文和一份中文项目文档写报告时能直接对着抄结构和公式。下面我把这份资源从算法原理拆到代码实现再讲调参时最容易翻车的几个位置你有多少基础都能跟得上。2. 先立住算法极大极小值搜索与Alpha-Beta剪枝的实现边界五子棋是典型的双人零和博弈AI赢人类就输棋盘上任意局面都能用一个数值表示“AI赢的可能性”。极大极小值搜索正是基于这个前提AI回合是MAX层在所有合法落子里选评估值最大的人类回合是MIN层假设对手会选让AI最难受的落子也就是评估值最小的。两层交替向下展开直到搜到设定深度或分出胜负。这套逻辑天然适配五子棋因为它的评估函数好定义——胜负由五连决定中间局面则用活三、冲四、眠三这些局部棋形近似刻画。相比围棋那种全局性强、局部评估误差大的棋类五子棋的局部棋形与最终胜负相关度高所以不需要太深的搜索就能下出“像样”的棋。一个容易被忽略的前提Minimax假设对手每一步都回应最优AI在算的是“最坏情况下我能保住多少”。它不赌对手失误宁可把对手想得足够强这就是为什么Minimax搜索出来的棋看起来特别稳该防一定防不贪侥幸。理解这一点后面调评估函数时你才不会疑惑“AI怎么这么怂”。2.1 MAX/MIN交替决策树里的攻防角色怎么切换Minimax的递归结构很固定每一层先判断当前轮到谁轮到AI就取子节点分数的最大值轮到对手就取最小值。递归过程模拟的是双方轮流落子搜索深度就是往后看了几步棋。# 伪代码展示核心结构 def minimax(board, depth, is_maximizing, ai_player): if depth 0 or game_over(board): return evaluate(board, ai_player) if is_maximizing: best -float(inf) for move in get_moves(board): board[move] ai_player best max(best, minimax(board, depth - 1, False, ai_player)) board[move] 0 return best else: best float(inf) for move in get_moves(board): board[move] 3 - ai_player # 对手落子 best min(best, minimax(board, depth - 1, True, ai_player)) board[move] 0 return best逻辑说明max层把分数越推越高min层把分数越压越低递归自然形成攻防交替。每次落子后必须复位棋盘这是回溯的本质少了这一步搜索树会“污染”。参数说明ai_player用1表示黑棋、2表示白棋3 - ai_player就是对手编号depth是剩余搜索层数每深入一层减1归零时调用评估函数。2.2 Alpha-Beta剪枝两个边界值如何把搜索量降一个数量级Minimax的硬伤是复杂度随深度指数增长分支因子B、深度D时最坏要搜B的D次方个节点。Alpha-Beta剪枝通过维护两个边界值提前放弃没希望的分支Alpha是MAX层已经确定能拿到的最优下界初始为负无穷Beta是MIN层已经确定能接受的最优上界初始为正无穷。搜索过程中只要beta不大于alpha当前分支无论再展开多少层都不会影响父节点决策直接剪掉。这里的关键认知是剪枝不改变搜索结果只改变搜索量。它只是把“算完整棵树再比较”换成“边算边比较没希望的分支提前终止”。理想情况下配合良好的走法排序复杂度能从O(B^D)降到约O(B^(D/2))相当于同样时间多搜一倍的深度。不少初学者以为剪枝是近似优化其实不是被剪掉的分支一定不影响根节点的最终选择。用数字举例根节点是MAX层已搜完第一个分支拿到评估值3Alpha更新为3。接着搜第二个分支它是MIN层第一个叶节点返回2。因为MIN会选数值最小的节点所以这个分支里MIN最多只能拿出2而MAX已经在别处拿到了至少3的保证剩下的几十个节点就不用看了直接剪枝这就是alpha beta发生的瞬间。2.3 递归效率的隐藏前提终局检查必须放在入口实际落地Alpha-Beta时递归函数入口处要先检查棋盘是否有五连有就直接返回大分值不再向下展开。这一条看着简单实际项目里我见过不少实现把它放到了depth 0才判断结果AI在“再走一步就五连”的局面上反应迟钝问题就出在终局检查的位置太晚。另一个隐藏细节是评估值的符号统一。整棵搜索树返回的分数都站在AI视角正值对AI有利负值对AI不利符号不能在中途反转。MIN层如果写错方向比如也取了最大值AI会表现得像在帮对手走棋。这两个位置是我评估“一个人是不是真懂了Minimax”的快速判断标准也是后面第4章会展开的两个高频翻车点。3. 把项目跑起来文件结构、评估函数与搜索主循环逐段拆解3.1 压缩包文件清单先分清主程序和依赖库解压后第一件事是弄清楚每个文件干嘛的按我实际跑通的顺序整理成了一张表文件/目录类型作用GOAI_RUN.py主程序游戏循环、AI决策入口、人机交互graphics.py依赖库graphics教学绘图库负责棋盘渲染与鼠标点击references/wagnervirag_2001.pdf参考资料与搜索算法相关的英文论文论文内容.doc文档项目配套论文含算法与实现说明pycache/graphics.cpython-36.pyc缓存原环境Python 3.6编译产物可整个删掉.idea/IDE配置PyCharm项目文件对运行无影响运行顺序很直接先确认环境有tkinter然后直接跑GOAI_RUN.pygraphics.py会被当作本地模块导入不需要pip安装。但如果你当前Python版本和原来的3.6差得远建议先删掉__pycache__整个目录让解释器重新生成当前版本的缓存文件。老项目带着旧pyc在新环境里报ModuleNotFoundError的情况太常见了。3.2 棋盘表示与候选点生成为什么不该遍历全部361个点棋盘用15×15的二维列表0表示空、1表示黑棋、2表示白棋board[r][c]直接索引渲染时按坐标换算像素这个选择最朴素也最好调试。真正影响搜索性能的是候选点生成——如果每层递归都把全盘空点当作分支深度4时最坏要展开361的4次方量级路径个人电脑直接卡死。工程上的常见做法是只取“最后一次落子周围两格以内的空点”作为候选。五子棋的棋子有聚集性离最近一子太远的点既威胁不到对方也形成不了自己的攻势在深层搜索里几乎不会成为最优解。def generate_moves(board, last_move, radius2): 生成候选落子只扫描最近落子周围 radius 格内的空点 if last_move is None: return [(7, 7)] # 空棋盘时先落天元 moves set() r0, c0 last_move for r in range(max(0, r0 - radius), min(15, r0 radius 1)): for c in range(max(0, c0 - radius), min(15, c0 radius 1)): if board[r][c] 0: moves.add((r, c)) return list(moves)逻辑说明last_move是上一手坐标range边界用max和min裁剪防止数组越界。返回list而不是set方便后面排序和遍历。参数说明radius取2时候选点最多约24个足够覆盖绝大多数局部攻防取3搜索量明显上升适合开局阶段。我见过有人在开局强制全盘搜索、中后盘切回radius2效果不错但要多维护一个阶段判断。3.3 评估函数棋形打分是整份代码的“棋感来源”评估函数决定了AI的棋力上限也是最容易改出“玄学”效果的地方。不要把它当黑匣子拆开看就是四步沿四个方向数同色连子长度、统计两端封堵情况、映射成棋形名称、按棋形累加分数。SHAPE_SCORE { FIVE: 100000, # 五连直接赢 LIVE4: 50000, # 活四对手挡不住 RUSH4: 5000, # 冲四逼对手应 LIVE3: 1000, # 活三下一步可能成四 SLEEP3: 200, # 眠三威胁减半 LIVE2: 100, # 活二潜在发展 SLEEP2: 20, # 眠二 } def count_line(board, r, c, dr, dc, player): 从(r,c)出发沿(dr,dc)双向数同色连子返回长度和封堵数 length 0 blocked 0 rr, cc r, c while 0 rr 15 and 0 cc 15 and board[rr][cc] player: length 1 rr dr cc dc if 0 rr 15 and 0 cc 15 and board[rr][cc] ! 0: blocked 1 rr, cc r - dr, c - dc while 0 rr 15 and 0 cc 15 and board[rr][cc] player: length 1 rr - dr cc - dc if 0 rr 15 and 0 cc 15 and board[rr][cc] ! 0: blocked 1 return length, blocked def classify(length, blocked): 把连子长度和封堵数映射成棋形名 if length 5: return FIVE if blocked 0: if length 4: return LIVE4 if length 3: return LIVE3 if length 2: return LIVE2 if blocked 1: if length 4: return RUSH4 if length 3: return SLEEP3 if length 2: return SLEEP2 return NONE def evaluate_board(board, ai_player): 整盘打分AI总分减去对手总分的加权值 directions [(1, 0), (0, 1), (1, 1), (1, -1)] ai_score 0 human_score 0 for r in range(15): for c in range(15): player board[r][c] if player 0: continue for dr, dc in directions: # 只统计以当前点为起点的连子避免同一条线重复计数 if 0 r - dr 15 and 0 c - dc 15 and board[r - dr][c - dc] player: continue length, blocked count_line(board, r, c, dr, dc, player) shape classify(length, blocked) if player ai_player: ai_score SHAPE_SCORE[shape] else: human_score SHAPE_SCORE[shape] return ai_score - int(human_score * 1.2)逻辑说明evaluate_board扫描所有非空格子沿横、竖、两条对角线统计连子。起点判断是关键当前格子的前一个位置不是同色棋子时才把它当作连子起点防止同一条五连线被重复计分。参数说明human_score乘1.2是把对手威胁放大两成让AI防守更敏感想更激进就调低这个系数想更稳健就调高。这是整份代码里性价比最高的调参位置。3.4 搜索主循环递归、剪枝与最佳落子回传搜索主循环把前面的概念全部串起来。找到最佳走法的逻辑是先枚举AI这一步的候选落子每落一子就调用递归搜索评估后续局面最后取分数最高的那个位置返回。递归内部通过is_maximizing在MAX层和MIN层之间切换alpha和beta随递归向上传递。def minimax(board, depth, alpha, beta, is_maximizing, last_move, ai_player): winner check_winner(board) if winner ai_player: return 100000 depth if winner ! 0: return -100000 - depth if depth 0: return evaluate_board(board, ai_player) moves generate_moves(board, last_move, radius2) # 走法排序让alpha-beta尽早遇到好分支 moves.sort( keylambda m: score_position( board, m[0], m[1], ai_player if is_maximizing else (3 - ai_player) ), reverseTrue, ) if is_maximizing: max_eval -float(inf) for r, c in moves: board[r][c] ai_player val minimax(board, depth - 1, alpha, beta, False, (r, c), ai_player) board[r][c] 0 max_eval max(max_eval, val) alpha max(alpha, val) if beta alpha: break # 剪枝 return max_eval else: opponent 3 - ai_player min_eval float(inf) for r, c in moves: board[r][c] opponent val minimax(board, depth - 1, alpha, beta, True, (r, c), ai_player) board[r][c] 0 min_eval min(min_eval, val) beta min(beta, val) if beta alpha: break # 剪枝 return min_eval def find_best_move(board, ai_player, last_move, depth4): best_move None best_val -float(inf) for r, c in generate_moves(board, last_move, radius2): board[r][c] ai_player val minimax(board, depth - 1, -float(inf), float(inf), False, (r, c), ai_player) board[r][c] 0 if val best_val: best_val val best_move (r, c) return best_move逻辑说明check_winner做四方向五连扫描返回胜方编号score_position是3.3里评估函数的单点版本只统计某个候选点对四个方向棋形的贡献用来排序已经足够。find_best_move枚举AI第一步落子逐层调用minimax最后返回评估值最高的落子位置。参数说明depth是总搜索深度我调试时从2、3、4逐级试。depth2时AI只会应冲四和保活三相当于入门depth4能看到“先活三再反冲四”的两步交换棋力明显上来depth6以上必须依赖候选点裁剪和走法排序否则单步耗时在普通笔记本上会超过10秒。搜索结束后递归落子必须复位成0漏掉这一步棋盘上会出现“幽灵棋子”AI后半盘会突然乱下。提示调试时如果发现AI下棋时快时慢优先查两处——递归里board是否正常回退以及走法排序是否真的生效。这两处占了我此前调这个项目时踩坑的七成。4. 调参避坑深度、候选点与UI层的五个常见问题4.1 落子慢得像卡死候选点和深度先查这两处现象AI每一步要算十几秒看起来像程序无响应。原因搜索深度设太高同时候选点没有裁剪。depth4配全盘候选点时状态数直接爆炸个人电脑基本不可用。某些实现还在递归里重复调用全盘扫描的get_moves更是雪上加霜。解决把generate_moves限定为radius2的局部候选再把find_best_move的depth从2开始向上调。我给自己定的约束是单步搜索超过2秒就降一档深度。同时在每层搜索入口打印当前候选点数量如果始终超过100个说明候选生成逻辑漏了裁剪。4.2 AI只会攻不会守评估函数漏了对手分数现象AI每次都往自己的冲四处落子对手都活三了也不去堵整盘棋像在自嗨。原因评估函数只统计了AI一方的棋形分数。五子棋是零和博弈最好的进攻往往就是防守——你在对手活三上堵一下自己的子同时可能构成反攻。只算单方分数AI就对对手的威胁视而不见。解决把评估函数改成“AI总分 - 对手总分”。乘1.2的系数是攻防倾向的旋钮想稳就调高想凶就调低。至少保证对手的冲四、活三分值能抵消你的单方棋形得分AI才会在进攻和防守之间真正做权衡。4.3 剪枝没生效走法排序是剪枝的前置条件现象加了alpha-beta后搜索节点数没有明显下降每步还是很慢。原因剪枝效率高度依赖走法排序。如果第一层就把最差的走法排在最前alpha更新极慢剪枝基本不触发。很多教程只讲剪枝原理不讲它有个隐含前提——好走法要先搜。解决在展开moves之前按score_position做一次降序排序。粗糙的启发式排序就能让剪枝效率提升一个数量级。我的实测数据是不排序时depth4可能展开上万节点排序后通常两三千就结束。排序逻辑就是3.4代码块里的moves.sort别嫌它占那一行耗时。4.4 graphics窗口打不开先清理缓存再查tkinter现象运行GOAI_RUN.py时直接报错提示graphics模块导入失败或者窗口闪一下就消失。原因压缩包里的__pycache__/graphics.cpython-36.pyc是Python 3.6的编译产物在Python 3.10及以上环境里加载旧字节码会失败。graphics.py本身依赖tkinter如果装的是精简版Python或缺系统组件导入就会中断。解决先删除整个__pycache__目录让解释器重新生成当前版本的缓存文件。再确认tkinter可用命令行执行python -c import tkinter无报错。Windows用官方安装包默认带tkinterLinux服务端发行版可能要单独装python3-tk。4.5 AI主动送棋MIN层取反和终局检查位置现象AI单步看起来正常但经常主动把棋送到对手的枪口上比如给对手制造活三机会。原因两个典型错误。一是MIN层写错方向对手回合也取了最大值等于AI在替对手走棋二是终局检查放在depth 0处搜索深度为奇数或偶数时对“再走一步就赢”的局面的判断会不一致。解决给minimax加一行调试打印在搜索入口输出当前回合和层数肉眼确认MAX层对应AI先手、MIN层对应对手。终局检查必须放在递归函数入口处、深度判断之前。再用半小时写一个测试摆一个已知的“两步杀”局面让AI走如果AI抓不住优先怀疑终局检查位置而不是评估函数。5. 让AI再强一档走法排序与迭代加深的落地技巧先说一个反直觉的结论同样的代码框架里决定棋力上限的往往不是评估函数写得有多细腻而是搜索深度和剪枝效率的配合。评估函数粗糙一点没关系只要搜索多一层AI就能多算一步交换棋力立刻上一个台阶。所以最后这两个技巧都围绕“限定时间内搜得更深”展开。第一个技巧是迭代加深。与其固定depth4不如从depth2开始逐层加深每层之间检查耗时超时就把上一层的最佳走法返回。这么做还有一个副产品上一层算出的最佳走法会作为下一层排序的首选因为浅层和深层搜索的最优走法高度相关第一分支就命中好走法时alpha-beta收敛会非常快。代码就是包一层循环def find_best_move_iterative(board, ai_player, last_move, max_time2.0): start time.time() best None for depth in range(2, 8): candidate find_best_move(board, ai_player, last_move, depthdepth) best candidate if time.time() - start max_time: break return best逻辑说明每完成一层就暂存一份结果超时后直接返回上一深度算出的走法。它不追求单层最优只保证在限定时间里把当前搜得最深的一步交还给交互逻辑下棋过程不会出现让人干等的长停顿。第二个技巧是给排序函数加攻防权重。许多实现里的排序只按当前玩家视角打分导致AI在攻防转换时慢半拍。我的做法是对AI和对手的候选点分别打分取加权差作为排序键让搜索层优先看“同时威胁对手”的着法。排序不需要精确计算它只影响剪枝效率所以别在这一步消耗太多开销。如果你打算拿这份资源交课程设计我建议把评估函数单独拆成模块论文里附两张搜索节点统计图一张是不排序depth4的数据一张是排序后的。这组对比是Alpha-Beta剪枝价值最直观的证明答辩时也最好讲。从那以后我每次改完评估函数都要先跑一组AI先后手各20手的对照记录每手耗时和剪枝命中率再谈增强。希望这个习惯和你这次跑通的代码都能帮到你。本文还有配套的精品资源点击获取