简介适合用 Python 实现五子棋人机对战的算法学习者与游戏开发入门者可快速搭建一个可运行的 pygame 对弈程序。项目以极大极小搜索为核心电脑走步时使用 α-β 剪枝剪掉无关分支以提升搜索效率同时重点处理可落子点位获取与评估函数设计——评估函数的好坏直接决定电脑的“智能”程度也是这一实现中最值得细读的部分。代码完整覆盖先后手选择、胜负判定、棋局渲染及状态提示交互上支持先手/后手切换、重开一局以及退出等按钮运行于 PyCharm 2019.2可在窗口中直接开始人机对弈。压缩包内共 3 个文件含 2 个 Python 源码与 1 个说明文本整体仅 15KB体量小巧、结构清楚适合逐行阅读和二次修改。目前已有 4704 人学习下载无论用于理解博弈树搜索、完成课程设计还是作为毕业设计原型都具备不错的参考价值。1. 五子棋AI凭什么能赢你它根本不懂棋只是会省着枚举很多人在第一版五子棋人机对战跑通的那一刻会觉得AI有棋感它会堵你的活三、会自己找双活三甚至能提前三四步布置杀棋。但如果你把中间变量打出来看一眼会发现AI脑子里没有妙手这个概念只有一张张棋盘快照和一堆数字。所谓会下棋本质是把未来几步的所有走法枚举出来、各打一个分、取最高分——纯粹是枚举加打分。问题在于15×15的棋盘每一步可落点上百个枚举三层就是百万级节点枚举七层就是天文数字pygame 的渲染循环根本等不起。让枚举跑得动、跑得深、跑得准的关键正是α-β剪枝用一套上下界机制把搜索树上大量注定不会被选中的分支直接锯掉。搞懂这个机制你就明白了那句反直觉的话——AI算得越省反而算得越深。2. 博弈树五子棋的计算黑洞藏在候选点筛选里2.1 棋盘建模二维数组、四个方向向量与胜负判定搜索的第一步是棋盘怎么表示。这个资源里用的是经典的二维数组board[r][c]15×15 的网格里分别用0、1、2表示空、黑子、白子。为什么不选用更高级的位棋盘Python 的整数是无限精度的理论上 225 个 bit 也能存下一整盘棋位运算判定连五也很快但可读性差而且 pygame 渲染每一帧还是要拿到格子的具体状态。二维数组换来的是落子、悔棋、渲染三种操作都是直接的下标读写这对递归搜索里高频的落子→递归→悔子尤其重要——每一步都只需要两次 O(1) 的赋值没有任何拷贝开销。EMPTY, BLACK, WHITE 0, 1, 2 SIZE 15 # 横、竖、撇、捺四个基础方向 DIRS [(1, 0), (0, 1), (1, 1), (1, -1)] def create_board(): return [[EMPTY] * SIZE for _ in range(SIZE)] def count_line(board, r, c, dr, dc, color): 从 (r,c) 沿 (dr,dc) 数同色连子含落子点自身 cnt 1 for step in (1, 2, 3, 4): nr, nc r dr * step, c dc * step if 0 nr SIZE and 0 nc SIZE and board[nr][nc] color: cnt 1 else: break for step in (-1, -2, -3, -4): nr, nc r dr * step, c dc * step if 0 nr SIZE and 0 nc SIZE and board[nr][nc] color: cnt 1 else: break return cnt def check_win(board, r, c, color): 落子后只需检查这一颗棋子的四条线 for dr, dc in DIRS: if count_line(board, r, c, dr, dc, color) 5: return True return False这里的关键点在于DIRS只定义了四个方向而不是八个。横、竖、两条对角线是直线从(r,c)朝正方向数和朝反方向数的是同一条线四个基础方向配合双向延伸已经覆盖了所有可能成五的路径。count_line每次只从落子点出发往外数四步因为五子棋连五只需要看四格以内的延伸超过四格就算不上了。这个函数在胜负判定里被频繁调用但每次代价极小全盘扫描 225 个格子做胜负判断是完全没必要的浪费。2.2 候选点生成周围两格是第一层剪枝如果每次递归都把 225 个空位全部展开成子节点搜索树的分叉因子 B 等于当前空位数开局阶段是 200 以上中盘也有一百多。α-β 剪枝对分叉因子的平方根非常敏感B20 时理想有效分叉只有 4.5B200 时就是 14差出的数量级是致命的。所以决定搜索树大小的不只是深度还有候选点集怎么筛。这个资源采用的经典做法是只把距离任意已有棋子 2 格以内的空位当成候选。理由很朴素——五子棋的每一手要么在进攻要么在防守不可能下到离所有棋子超过两格的地方。无人区落子在开局之后的绝大部分局面里都是废棋把它从候选点里剔除等于在做第一层剪枝而且是在数据准备层的剪枝α-β 算法本身根本感知不到。def get_candidates(board): 返回距离已有棋子两格以内的所有空位set 天然去重 cand set() for r in range(SIZE): for c in range(SIZE): if board[r][c] ! EMPTY: # 以每个非空点为中心扫描 5x5 邻域 for dr in (-2, -1, 0, 1, 2): for dc in (-2, -1, 0, 1, 2): nr, nc r dr, c dc if 0 nr SIZE and 0 nc SIZE and board[nr][nc] EMPTY: cand.add((nr, nc)) return list(cand)return list(cand)这行看起来不起眼但它为后面的排序和递归遍历做了准备——后续搜索前要按启发式分数重排候选点set 本身无序必须先转成 list。这个函数的实际效果是把开局阶段上百个候选点压到十几到三十几个中盘更少。候选点数量直接决定搜索树的宽度宽度降下来深度才有提升的空间。很多性能调优的心得里都提到先广后深先把无关的棋形剔除干净再谈搜索算法本身。2.3 评估函数剪枝前叶子节点得先学会打分搜索树展开到限定深度后绝大多数叶子并不是终局不能让 AI 只知道赢或输必须给一个此刻谁占优的连续分数。最常见的做法是按棋型打分——把局面拆成一条条线识别线里包含的棋型乘以权重累加。典型的评分表长这样棋型典型分值含义五连100000已经赢了活四50000两端都空下一手必胜冲四10000一端被堵的四连只能强行冲活三5000两空端的三连威胁很大眠三1000一端被堵需要再补一手才有威胁活二500有发展潜力的种子眠二100半死不活但有后续可能这里的数量级差距不是随便拍脑袋定的。五连 10 万、活四 5 万、活三 5000隐含的决策哲学是宁可放弃几个活三的积累机会也要争取一次先手连五的机会因为搜到底之后胜负比形势更值钱。权重一旦失调AI 会变成要么极度保守、要么极度冒进。def evaluate(board, color): 从 color 视角给局面打分己方棋型得分 - 对手棋型得分 total 0 for r in range(SIZE): for c in range(SIZE): if board[r][c] ! EMPTY: continue for dr, dc in DIRS: # 假设这里放上己方棋子算出的棋型分记为正 total pattern_score(board, r, c, dr, dc, color) # 假设这里放上对手棋子算出的棋型分记为负 total - pattern_score(board, r, c, dr, dc, 3 - color) return total注意3 - color这个技巧黑是 1、白是 23 - 1 2、3 - 2 1一条表达式完成颜色翻转。同一个空位为什么既要给己方加又要给对手减因为防守和进攻是同一张棋盘上的双面算账——一个空位对己方是活三的缺口对对手可能也是活四的缺口减去对方的威胁等价于把防守量化进了分数。这个函数会在递归中被调用几十万次每次做全盘扫描其实很浪费成熟实现会做增量维护只更新最近落子点附近的局部得分。但增量维护的代码复杂度高容易引入 bug所以先写全盘扫描、跑通逻辑再谈优化是更稳妥的路线。3. α-β剪枝为什么这步棋可以不算反而让AI算得更深3.1 极大极小博弈先替自己选最好再替对手选最狠先写清楚朴素版在干什么。假设轮到黑方落子黑方要从所有合法落子里挑一个让最终评估值最大的但黑方落完子轮到白方白方会挑让黑方评估值最小的走法。于是我看一步实际上是我看到我方最优、对方最狠之后的结果。这段策略映射到递归里就是当前节点是 max 节点子节点是 min 节点再下一层又是 max交替进行。def minimax(board, depth, color): 朴素极大极小交替取 max / min必须展开整棵树 if depth 0 or check_terminal(board): return evaluate(board, BLACK) # 统一从黑方视角计分 moves get_candidates(board) if color BLACK: best -float(inf) for r, c in moves: board[r][c] BLACK score minimax(board, depth - 1, WHITE) board[r][c] EMPTY best max(best, score) return best else: best float(inf) for r, c in moves: board[r][c] WHITE score minimax(board, depth - 1, BLACK) board[r][c] EMPTY best min(best, score) return best这段代码能跑但问题巨大它必须展开整棵树的所有分支没有任何提前终止的机制。在候选点被压到 20 个、搜索 4 层的情况下节点数是 20 的 4 次方等于 16 万还能接受搜 6 层就是 6400 万pygame 里玩家落一子要等几十秒。这就是暴力枚举的算力天花板想要更深必须靠剪枝。3.2 α与β的物理含义用两个界把搜索树锯掉一半α-β 剪枝的核心是维护两个贯穿递归的值。α 表示己方已经能保证的最低分任何一个分支算出来低于 α己方根本不会选它这个分支不值得细看β 表示对手能忍让的最高分任何一个分支算出来等于或高于 β对手会提前走另一条更狠的路根本不会让局面发展到这里。每次子节点返回分数α 会上升、β 会下降一旦 α ≥ β说明上下界的矛盾已经不可调和剩下的兄弟节点无论算出什么结果都不可能被选中——直接 break不再展开。这就是这步棋可以不算的物理含义。剪枝不是玄学它建立在一个严格的逻辑之上已经有一个足够好的参考分支其他分支不可能推翻它。剪枝省掉的不是决策而是注定不会被决策的分支。以 B20 为例剪枝理想情况下的收益是这样的搜索深度暴力枚举节点数α-β理想节点数差距4 层20^4 ≈ 16 万20^2 ≈ 400约 400 倍6 层20^6 ≈ 6400 万20^3 ≈ 8000约 8000 倍8 层20^8 ≈ 256 亿20^4 ≈ 16 万约 16 万倍理想情况下α-β 的有效分叉因子从 B 降到根号 B同等深度下节点数呈指数级缩减。这个数学结论决定了为什么同样是枚举会剪枝的枚举能让 AI 多算好几层棋。3.3 负极大实现一套 alpha、beta 逻辑统一黑白双方上面的 minimax 代码把黑方和白方写成两个分支逻辑重复且容易改出不对称的 bug。实际实现里大多用负极大negamax形式让每个节点都从当前落子方的视角取 max递归时把对方视角翻转成负号。这样整棵搜索树只剩一套逻辑黑白双方共用同一个函数而 α-β 的边界更新也随之统一。def negamax(board, depth, alpha, beta, color): 负极大形式返回当前落子方视角的最佳分数 if depth 0: return evaluate_for_color(board, color) # 必须从 color 视角计分 best -float(inf) for r, c in get_candidates(board): board[r][c] color # 关键传给对方的 alpha/beta 取负并交换 score -negamax(board, depth - 1, -beta, -alpha, 3 - color) board[r][c] EMPTY if score best: best score if best alpha: alpha best if alpha beta: break # 剪枝对方不会让局面走到这里 return best第一眼看这函数会绕的地方全在递归调用那行-negamax(..., -beta, -alpha, ...)。拆开理解对方视角里的我的下界 α换算回我方视角是-α变成了上界对方视角里的对方上界 β换回我方视角是-β变成了下界。两个界取负之后交换位置正好把对方的 max翻转成了我方的 min而负号让返回值也翻转了视角。这套交换是负极大形式的精髓也是很多实现里剪枝边界写错的地方。根节点调用时alpha -inf、beta inf循环内一边更新best一边更新alpha搜完所有候选点后返回的best就是 AI 认为的最佳分对应的落子就是要走的那一手。在 pygame 的主循环里这个调用通常发生在玩家落子之后、渲染下一帧之前期间界面会短暂卡顿——卡顿长度由深度和剪枝效率共同决定。后续的优化方向基本都围绕让这个函数在更短时间里剪掉更多分支展开。4. 搜索顺序剪枝剪不干净多半是顺序问题而不是算法问题4.1 先搜好棋把有效分支因子往根号B压剪枝的发生有一个前提已经扫描过的分支中有一个足够好的参考值。如果最好的分支恰好排在候选点列表的最后面那么前面所有分支都要完整展开到叶子剪枝一次都不会触发。这就是为什么同一个 α-β 实现候选点排序不同性能会差几十倍到几百倍——算法本身没变变的只是剪刀下刀的顺序。实践中最简单有效的做法是进入递归之前用轻量级的启发式函数给候选点粗打分按分数从高到低搜索。这里的启发式不需要像完整评估函数那样精确只看如果落在这里能立刻形成多强的棋型。计算量比完整评估低一个数量级排序效果却很好。def sort_moves(board, moves, color): 按快速启发式分数对候选点降序排列好棋优先搜 def quick_score(pos): r, c pos total 0 for dr, dc in DIRS: # 只看以该点为中心两端各四格形成的棋型强度 total line_strength(board, r, c, dr, dc, color) total line_strength(board, r, c, dr, dc, 3 - color) * 0.9 return total return sorted(moves, keyquick_score, reverseTrue)注意这里有意的取舍给对手棋型打分时乘了 0.9 的系数让 AI 在排序阶段偏向进攻略多于防守。这不算严谨但很有效——排序只影响剪枝效率小偏差很快会在深层搜索里被纠正不需要为此付出太大计算量。相比之下评估函数里的偏差会直接传导到最终决策那才是真正需要精调的地方。4.2 置换表把算过的局面缓存起来避免重复深搜搜索树里有一个隐藏的浪费同一个局面可以通过不同的落子顺序到达。比如黑方先下 A 再下 B白方应对 C和黑方先下 B 再下 A白方应对 C在很多棋形下是等价的局面。如果没有缓存这两条路径会在子树里重复展开。置换表transposition table就是用哈希键存储已经算过的局面及其分数下次遇到同样局面直接取结果省掉一整棵子树的搜索。# 置换表条目核心在于三个 flag 表示分数的性质 # EXACT精确值直接用 # LOWER实际值 value只能用来抬升 alpha # UPPER实际值 value只能用来压降 beta TT_ENTRY (flag, value, depth)α-β 剪枝下缓存不是简单的存一个分数就行。因为剪枝发生时某个节点的分数并没有算完整——它可能只是一个下界或上界。如果把一个 LOWER 标记的分数当成精确值直接返回AI 会误以为这步棋顶多这个分而放弃它实际它可能好得多。这就是置换表最容易翻车的地方。Zobrist 哈希是配套的标准做法预先给每格、每种颜色生成一个随机数落子时异或进哈希键悔子时再异或回去整个局面键可以在 O(1) 时间内增量维护不需要每次从棋盘重新计算。4.3 深度与棋感8层搜索能覆盖多大的杀棋半径棋感这件事落在工程上其实就是深度和宽度的组合。8 层搜索意味着 AI 能看到我落子、对手落子交替 4 轮也就是自己 4 手棋的前景。五子棋绝大多数连续冲四胜VCF需要 3 到 6 步的连续冲四链8 层已经能覆盖其中相当一部分双活三等组合杀棋也基本落在 4 步以内的视野里。这就是为什么很多人把 8 层当作有棋感的门槛——低于这个深度AI 看不到杀棋的形成过程高过这个深度单步耗时又会让玩家失去耐心。要让 8 层在普通机器上跑进一秒只靠 α-β 本体还不够往往需要迭代加深先搜 2 层热身把上一层的最佳落子顺序作为下一层的初始顺序让剪枝在浅层先建立高质量的 α、β 参考值加深时剪枝效率自然提高。迭代加深看起来是多算了好几遍实际上浅层排序带来的剪枝收益远大于重复开销这个反直觉的点值得亲手验证。在 pygame 对局里迭代加深还有个现实好处可以随时按时间预算截断即使硬件慢也不会让玩家干等。5. 五子棋AI避坑为什么你的AI会眼瞎送杀5.1 只算己方棋型对手的五连近在眼前却视而不见现象AI 在局面领先时不去堵对手反而走了一手进攻棋然后对手下一手直接连五取胜。复盘时发现对手的活四已经摆在棋盘上好几轮了AI 始终没去管它。原因初版评估函数几乎只对当前搜索方的颜色计分甚至胜负判定也只检查落子者的颜色。黑方搜索时白方已经存在的连五在评估值里根本没有被扣分——它压根没被看到。搜索算法再智能也只会优化一个看不见威胁的目标函数。解决评估里必须做黑、白双方的棋型差分不能只看单色在递归入口先做胜势检查若当前局面已经有对手五连立刻返回极差分数而不是继续展开子节点。注意这个检查要放在所有候选点生成之前否则 AI 会以为还有应对手段继续认真地搜索一个已经输掉的局面。5.2 棋型识别不看两端把冲三当活三、把死四当活四现象AI 把一端已经被堵死的冲三当成活三去挡白浪费一手更糟的是自己总走所谓活三实际另一端被堵根本没有杀棋结果被对手反杀。原因连续子计数只看同色棋子长度而五子棋棋型的威胁等级完全由两端状态决定。两端都空的三连是活三一端被对方或棋盘边界堵住的三连只是冲三两个的威胁相差一个数量级。不看两端评估函数的分数就是失真的。解决数连子时把两端状态一并带回来生成如长度 左端状态 右端状态的棋型签名再映射到评分表。跳三中间空一格的三子也得单独建模——很多 AI 漏掉跳三导致它算不出某些杀棋路径这是实战里最常见的漏算来源之一。5.3 剪枝边界更新错位搜索变慢还偶发臭棋现象上了 α-β 之后搜索速度不仅没提升某些局面下反而更慢换一个深度参数AI 的走法剧烈跳变甚至走出明显送杀的臭棋。原因负极大实现里两个高频错误。一是递归返回后忘了把负号还原到 score 上就把 score 参与 alpha 更新导致 alpha 拿到一个被翻转视角的错误值二是把 alpha 的更新放在分数是否优于当前 best的判断之前让 alpha 被一个还不够好的中间值污染。这两个错误会让剪枝条件误触发把还可能有更好结果的分支当成必败分支直接锯掉。解决写一个调试开关在深度 ≤ 4 时让 α-β 版和朴素极大极小版对拍分数必须完全一致再跑一次自对弈确保引入剪枝后输赢结果不变。上线前在根节点打印剪枝次数——如果某个深度的剪枝数接近 0说明搜索顺序或边界更新出了问题剪枝根本没生效。5.4 深度不够却强行下先手棋被连续冲四带走现象AI 面对简单的双三杀棋表现正常但遇到跨多个子的 VCF 时会走一步看似合理的开发棋然后被对手连续冲四一路带走毫无还手之力。原因VCF 这类连续冲杀往往要走 5 到 6 步以上才见分晓。8 层搜索只覆盖 4 步交换评估函数在深度不够时会把暂时的劣势误判成最终的劣势AI 宁可选一个眼前分数均衡的防守也不选需要再赌一手进攻才翻盘的路线。这是浅层搜索固有的近视。解决不要盲目加深度而是做杀棋扩展。检测到己方或对方存在连续冲四链时把候选点强制收缩到冲四相关点并沿 VCF 路径单独加深搜索普通局面保持浅层快速响应。这是五子棋引擎从会下到会杀的分水岭也是这个资源里最值得继续深挖的优化点。6. 设计取舍AI的棋感是评估权重、搜索深度与搜索顺序的三角平衡6.1 权重的玄学数量级差就是决策哲学五连 10 万、活四 5 万、活三 5000——这些数字不是数学推导出来的它表达的是宁可放弃眼前积累也要追后面的杀棋这种策略偏好。把活三从 5000 改成 6000AI 会变得更喜欢做棋改成 4000AI 会更倾向于防守反击。评估权重本质上是开发者棋风的编码没有标准答案只有自对弈调出来的经验值。这部分是整个 AI 里最玄学、最需要反复验证的地方不要迷信网上某一份权重表要理解每个数量级差背后代表的行为倾向。6.2 深度不是越多越好深度高、评估糙AI 会在深算之后选择一条纸面上占优但实操里被反杀的路线因为深层的每步决策都建立在粗评估的误差累积上。相比之下浅层搜索配一个好排序和一个合理的评估函数往往比盲目加深更稳。好的工程习惯是先确认评估函数在关键棋型上没有系统性偏漏再考虑加深深度带来的棋感优势必须在评估函数可靠的前提下才成立。6.3 置换表是把双刃剑缓存节省了重复搜索的时间但缓存了错误边界会让 AI 自信地走出臭棋——这比没有缓存更糟。置换表要么完整实现 EXACT、LOWER、UPPER 三个标记位的语义要么干脆先不启用。我在做这个资源里的 AI 时栽得最狠的一次就是第一次加上置换表结果 AI 在必胜局面里反复横跳怎么调搜索深度都没用。从那以后我形成了习惯任何搜索优化上机前先让它在深度 3 自对弈一百局和朴素极大极小版的输赢结果对齐再谈加速。这个习惯帮我挡掉了至少三次优化翻车。希望帮到你。本文还有配套的精品资源点击获取
