简介围绕五子棋人机对战展开的Python实战项目适合已掌握基础语法、希望理解博弈树搜索与极大极小算法的学习者参考。程序用pygame搭建可视棋盘完成先手/后手切换、落子与胜负判断、重开退出等交互核心落在AI走步的选取以极大极小值搜索枚举候选点位借助评估函数对不同棋型打分再用α-β剪枝压缩搜索分支、提高决策效率是理解剪枝优化与启发式评估的完整范例。压缩包共3个文件以2个py源码和1个txt说明为主前者承载棋盘绘制、事件响应与搜索算法后者记录代码要点与运行说明整体仅15KB轻量易读。已有4700余人学习下载。读者可据此拆解候选点生成、评估函数设计与剪枝边界条件的写法对照源码复现完整对战流程也便于在课程设计或算法练习中直接改造。1. 分支因子 200 并不致命致命的是你搜了不该搜的分支很多人第一次用 python 写五子棋人机对战都会在 pygame 上摆一个 15×15 的棋盘然后得出同一个判断候选点不过两三百个暴力搜就是了。真跑起来才发现深度 6 就要等十几秒深度 8 直接把窗口卡成「无响应」。五子棋的局面数确实没有象棋那么吓人但按 200 的层数连续乘下去第 8 层就是 2.56×10¹⁸ 量级——这个数字跟棋力没有任何关系只跟你的耐心有关系。真正让这类程序从「能跑」变成「像个人」的是 α-β 剪枝这一套东西。它的反直觉之处在于剪枝不损失任何精度。同样搜 8 层剪枝前后选出的着法完全一致只是剪枝版本少算了绝大多数的节点。理想排序下有效分支因子从 b 降到 √b8 层的搜索量相当于不剪枝的 4 层。剩下的全部工作都是想办法让实际排序逼近理想排序。2. 棋盘与棋型评估函数怎么把一盘棋压成一个数字搜索解决的是「选哪一步」评估函数解决的是「这个局面到底谁好」。而五子棋的评估有个天然优势它几乎不需要什么玄妙的全局判断胜负信息高度集中在局部棋形上。这就决定了实现路线——把棋盘切成一个个五格窗口逐个打分再求和。2.1 一维数组加哨兵绕开每一次边界判断最直接的写法是board[y][x]的二维列表然后在每个方向扫描时判断0 nx 15。问题在于评估函数会被调用几十万次每次调用里又有 900 次窗口扫描、每次扫描 5 个格子——边界判断的开销会直接压过计算本身。更麻烦的是以边界为中心的棋型会被截断_XXXX贴在边上到底算不算活四代码里全是分支。常见的实现思路是给棋盘外套一圈「墙」把二维压成一维。墙的取值和空、黑、白都不同扫描时墙天然终止棋型不需要任何 ifSIZE, PAD 15, 4 # 窗口长 5任一方向最多外扩 4 格所以 PAD 取 4 W SIZE PAD * 2 # 23 EMPTY, BLACK, WHITE, WALL 0, 1, 2, 3 # 四个方向横、竖、右下、左下。各扫一遍正向即可覆盖全部八向 DIRS (1, W, W 1, W - 1) def new_board(): b [WALL] * (W * W) for y in range(SIZE): base (y PAD) * W PAD b[base:base SIZE] [EMPTY] * SIZE return b def idx(x, y): return (y PAD) * W (x PAD)PAD 取 4 不是随手定的一个五格窗口从中心向任意一侧最多延伸 4 格而对角方向的步长是W±1从角点出发走 4 步刚好落在哨兵区最外沿不会越界。这个数字改小一位对角扫描就会静默读到列表另一端的数据——这种 bug 不会崩只会让 AI 莫名其妙地在棋盘另一头落子。哨兵方案还顺手解决了「撤销落子」的对称性问题落子是board[p] color撤销是board[p] EMPTY不需要保存任何历史状态因为墙永远不会被覆盖。2.2 五格滑窗加 1024 项查表棋型识别的最简实现五子棋的棋型判定有个非常好的性质任何一手棋的威胁都可以分解成「包含这个点的若干五格窗口」。反过来说把全盘所有五格窗口扫一遍并累加分数就得到了一个覆盖全部棋型的评估。一个五格窗口只有 5 个格子每格 4 种状态空、黑、白、墙总共 4⁵ 1024 种组合。这意味着可以预先把 1024 种组合的分数全部算好运行时只做查表# 0~5 子的基础分。四和五之间必须留出巨大断层让「活四」压过任何三个三 PATTERN (0, 1, 12, 180, 2400, 200000) def build_window_table(): tbl [0] * 1024 for code in range(1024): c, cells code, [] for _ in range(5): cells.append(c 3) c 2 if WALL in cells: # 窗口含墙这个窗口不成立 continue nb, nw cells.count(BLACK), cells.count(WHITE) if nb and nw: # 黑白同窗谁也成不了五 continue if nb: tbl[code] PATTERN[nb] elif nw: tbl[code] -PATTERN[nw] return tbl WT build_window_table() # 模块加载时算一次之后全是 O(1) 查表code的构造方式是把 5 个格子按2 bit一位打包所以code 3取最低位格子右移 2 位取下一个。评估函数就变成纯查表循环def evaluate(board): 以黑方为正、白方为负的静态局面分。 score 0 for d in DIRS: for y in range(SIZE): base (y PAD) * W PAD for x in range(SIZE): p base x code (board[p] | board[p d] 2 | board[p 2 * d] 4 | board[p 3 * d] 6 | board[p 4 * d] 8) score WT[code] return score900 次查表加法纯 python 大约几百微秒足够在搜索里当叶子节点用。有意思的是这个粗糙的查表法自动区分了活四和冲四_XXXX_会产生两个各含 4 子的窗口得 4800OXXXX_只有一个窗口成立另一个黑白混杂直接为 0得 2400。同样__XXX__是三个三子窗540OXXX_只有一个180。你什么都没做窗口的重叠计数就把「两端是否被堵」编码进去了。注意这张表是按「每个窗口独立计分」来的它没法表达「双活三」这种组合威胁——两个活三加起来 1080仍然低于一个冲四的 2400。所以静态评估在杀棋判断上天然不可靠这部分只能交给搜索深度去补。2.3 增量更新与整盘重算的分界线评估函数写完之后一个很自然的优化冲动是「只算落子点周围变化的窗口」。这在理论上完全可行落一子只影响 4 个方向上的 16 个窗口增量更新的代价是整盘重算的 1/56。但在实操里增量评估有两个坑。第一分数是整数累加增量更新一旦在某条回溯路径上漏减一次误差会一直累积下去表现出来就是 AI 在中局突然走一步完全看不懂的棋——这种 bug 极难定位因为单步看代码都是对的。第二候选点排序本身就需要对每个候选点做局部评估那部分开销本来就在整盘重算的相对成本没有想象中高。我一般的做法是叶子节点整盘重算着法排序用局部评估。前者保证正确性后者保证剪枝率两边各取所需。等真到了需要榨性能的时候再考虑把evaluate换成「维护一个每方每方向的棋型计数表」那是另一个量级的工程。3. 极大极小与 α-β被剪掉的分支凭什么可以扔评估函数给了我们给局面打分的能力但一步棋的好坏不能只看落子后的静态分——对手会回应。极大极小的本质就是把这个「回应」递归展开我方选最大对方选最小。3.1 negamax用一次符号翻转干掉一半代码教科书式的写法是两个函数互相调用max_value和min_value。实际写起来会发现两边代码几乎完全一样只是比较方向相反。Negamax 把它压成一个函数NEG_INF, POS_INF -(1 30), (1 30) WIN_SCORE 1 24 def negamax(board, depth, alpha, beta, color, ply): color: 当前该谁走BLACK1 / WHITE2 返回值站在 color 视角的局面分越大对 color 越有利 ply: 距离根节点的层数用于「越快赢越好」 if depth 0: # evaluate 是黑正白负白方视角要取反 return evaluate(board) if color BLACK else -evaluate(board) best NEG_INF for move in ordered_moves(board, color): board[move] color if is_win(board, move, color): board[move] EMPTY return WIN_SCORE - ply # 越早赢分越高避免 AI 拖着不杀 val -negamax(board, depth - 1, -beta, -alpha, 3 - color, ply 1) board[move] EMPTY if val best: best val if best alpha: alpha best if alpha beta: break # 剪枝点 return best关键在-negamax(..., -beta, -alpha, ...)这一行子节点是从对手视角打分的取负号转回自己视角同时 alpha 和 beta 也要取负并交换——因为「我至少能拿到的分」在对手眼里就是「他最多能让我拿到的分」。这三处符号只要有一处写反AI 就会开始主动送子而且代码看上去毫无问题。WIN_SCORE - ply也是必要的。如果成五就直接返回一个常数AI 会在「三步后赢」和「五步后赢」之间随机选——搜索认为两者分数一样。减去 ply 让最短的胜利路径得分最高这在残局里非常明显。3.2 α ≥ β 的几何意义剪掉的永远不是正确答案α-β 剪枝最容易被误解的一点是很多人以为它是一种「近似」用精度换速度。恰恰相反在同样的搜索深度下剪枝与不剪枝的结果完全一致。它的正确性只依赖一条假设——对手永远会选择对你最不利的那一步。把这条假设翻译成代码就明白了。设当前节点 N 是「我方」节点它的父节点 P 是「对方」节点。P 在遍历自己的子节点时已经找到了一个分支使得我方最多只能拿到 β 分。现在 P 走到 N 这条分支N 的第一个子节点就让我方拿到了 α ≥ β 分。此时N 是极大节点后面的兄弟着法只会让我方分数更高不会更低但对手在 P 那里已经有一个让我方只能拿 β 分的选择而 β ≤ α对手是理性的他一定会选那个 β绝不会走到 N 这条让我方拿 α 的路。所以在 P 眼里N 的剩余分支算不算都一样直接扔掉。这就是 beta 剪枝在极大节点上表现为alpha beta提前返回。对偶地极小节点上会发生 alpha 剪枝。整个剪枝的能量来源不是「猜」而是「对手不会配合你」这条铁律。由此可以推出一条工程上的重要结论剪枝率完全取决于你多快能找到那个「足够好的分支」。如果第一个被搜索的着法就是最佳着法α 立刻被抬到最高后面的兄弟全部被剪掉有效分支因子降到 √b如果最佳着法排在最后一个节点都剪不掉还额外付出了比较开销。这就是为什么几乎所有实战实现里着法排序的代码量都超过搜索本身。3.3 排序、迭代加深与杀手着法剪枝率是被喂出来的排序的原料有三类成本从低到高静态局部评估。对每个候选点算「我下这里的收益」和「对手下这里的收益」加权求和。后者其实就是封堵价值权重给 1.5 到 2 倍比较合适def point_score(board, pos, color): 假设 color 落在 pos取 4 个方向上「包含 pos 的最强五格窗」分数之和。 只用于排序用 abs 抹平黑白视角差异精度不重要。 total 0 for d in DIRS: best 0 for k in range(5): code 0 for j in range(5): q pos - k * d j * d code | (color if q pos else board[q]) (2 * j) v abs(WT[code]) if v best: best v total best return total def ordered_moves(board, color, limit12): cand gen_moves(board) scored [(point_score(board, p, color) * 2 point_score(board, p, 3 - color), p) for p in cand] scored.sort(reverseTrue) return [p for _, p in scored[:limit]]注意limit这个截断。它不是可选项——候选点动辄一百多个不截断的话第一层就要展开一百多个分支剪枝再强也救不回来。截到 10~16 是个经验区间太小会漏掉唯一的防守点太大则前几个节点的排序开销吃掉剪枝收益。置换表命中。如果某个着法在上一轮迭代里被证明是最佳着法这一轮优先搜它。这不是启发式是实打实的信息复用。杀手着法。在同一层同一个 ply的兄弟节点里如果某个着法刚刚引发过剪枝那么它在其它兄弟节点里也很可能引发剪枝。维护一个killer[ply] [move1, move2]的小表排序时把它们提到最前。至于迭代加深它的作用经常被误解成「省时间」。它真正的作用是给下一层提供排序信息先搜深度 2 拿一个最佳着法深度 4 时优先搜它深度 6 时再优先搜深度 4 的结果。深度每加 2排序质量就改善一轮所以总耗时的增长远低于 2 倍。很多人写迭代加深是为了显示「思考中」的进度条其实附带的好处比进度条大得多。4. 搜索工程化候选点、置换表与算杀4.1 候选点生成半径 2 的邻域假设什么时候会翻车全盘 225 个空点都当候选等于把分支因子从 12 强行拉到 200。五子棋的常识是远离已有棋子的点几乎没有价值因为任何棋型都需要连续的棋子。所以标准做法是只取已有棋子邻域内的空点def gen_moves(board, radius2): cand set() for p, v in enumerate(board): if v ! BLACK and v ! WHITE: continue for dy in range(-radius, radius 1): row p dy * W for dx in range(-radius, radius 1): q row dx if board[q] EMPTY: cand.add(q) return cand半径取 2 而不是 1是因为「跳活三」这类棋型X_XX的第二手可能落在距现有棋子 2 格的位置。半径 1 会让 AI 看不见隔一格的连接表现出来就是不知道该往哪延伸。但这个假设有明确的失效场景开局第一手。空棋盘上没有任何棋子gen_moves返回空集合搜索会直接返回None程序就卡在那儿。第一手必须硬编码成天元或者在候选集为空时退化成全盘扫描。这个坑几乎所有实现都踩过一次。另一个失效场景是防守。如果 AI 只在自己的棋子邻域里找点对手在远处布下的活三可能被完全忽略。所以gen_moves必须扫双方的棋子不能只扫自己的——上面那段代码没有区分v是黑是白正是因为这个。4.2 Zobrist 哈希与置换表同一个局面不搜第二遍五子棋的着法可交换性极强先下 A 再下 B和先下 B 再下 A到达的是同一个局面。不处理的话这个局面会在搜索树里被反复展开十几次。Zobrist 哈希的做法是给「每个位置 × 每种颜色」预分配一个 64 位随机数局面的哈希值就是所有已落子的随机数异或和import random ZOB [[random.getrandbits(64) for _ in range(W * W)] for _ in range(3)] def zobrist(board): h 0 for p, v in enumerate(board): if v BLACK or v WHITE: h ^ ZOB[v][p] return h异或的两个性质正好对上需求落子是h ^ ZOB[color][pos]撤销是同一个表达式异或两次还原所以增量维护只需要一行不需要重算整盘。置换表就是个dict但要存三样东西值、深度、边界类型TT {} def tt_probe(key, depth, alpha, beta): e TT.get(key) if e is None or e[depth] depth: return None # 深度不够这个结果不能信 if e[flag] EXACT: return e[value] if e[flag] LOWER and e[value] beta: return e[value] # 下界已经够高可以直接剪 if e[flag] UPPER and e[value] alpha: return e[value] return Noneflag是必须的。搜索返回的值有三种语义精确值搜完了所有着法、下界发生了 beta 剪枝真实值只会更高、上界所有着法都不够好。只存值不存边界类型会在剪枝节点上把「至少这么大」当成「正好这么大」用棋力会莫名其妙地退化——而且退化得很隐蔽因为你很难从某一步棋看出问题。深度检查同样不能省。浅层搜索存进去的条目如果被深层搜索直接拿来用等于凭空缩短了搜索深度AI 会漏掉需要更深才能看到的杀棋。规则很简单条目深度必须 ≥ 当前需求深度才能复用。4.3 VCF 算杀把分支因子从 30 压到 1有一个残酷的事实一个「四三杀」需要至少 4 层搜索才能看到而 4 层在纯 python 里已经要几百毫秒。残局里这类组合极多全靠主搜索去挖性能撑不住。VCFVictory by Continuous Four连续冲四取胜换个思路不搜所有着法只搜「冲四」这一类强制着法。冲四的特点是对手的应手几乎是唯一的——他必须挡在成五点上否则下一手就输了。于是分支因子从 30 掉到 1等效于把 10 层搜索压缩到一瞬间def vcf(board, color, depth, deadline): 我冲四 → 对手唯一挡 → 我再冲四…… 一旦链断就返回 None。 for p in four_moves(board, color): # 只生成能形成「四」的点 board[p] color if is_win(board, p, color): board[p] EMPTY return p blocks block_points(board, p, color) # 成五点冲四通常恰好一个 if len(blocks) ! 1: board[p] EMPTY continue board[blocks[0]] 3 - color win vcf(board, color, depth - 1, deadline) if depth 1 else None board[blocks[0]] EMPTY board[p] EMPTY if win: return p return None这段代码的定位应该是主搜索的前置过滤器每步棋先跑 3~5 层的 VCF找到杀就直接走找不到再进主搜索。它的开销极小收益极大——很多「AI 明明有杀却走了别的」的观感问题加一个 VCF 就解决了。对手视角的 VCF 也要跑一遍。如果对手存在 VCF 杀那么当前所有不破坏这条杀链的着法都是必败的可以直接从候选里剔除。这一步做不做决定了 AI 会不会「眼睁睁看着对面连四」——这是人机对战里最容易被人类玩家抓到并觉得「这 AI 很蠢」的行为。5. 排查清单AI 落子反常的五种典型翻车搜索能跑起来、能看到 AI 落子离「棋力正常」还有很长的路。下面这五类问题我都真实遇到过症状相似但根因完全不同。5.1 搜索层符号、撤销与胜负分值现象一AI 主动送子明明自己这边有活三却去堵一个无关的空点。原因negamax 叶子节点的符号翻转写错了。evaluate是「黑正白负」的固定视角negamax 需要的是「当前行棋方视角」。如果叶子直接return evaluate(board)那么白方节点拿到的分数符号是反的它会把自己的好局面当成坏局面于是选择「让自己变差」的着法。 解决叶子统一写成return evaluate(board) if color BLACK else -evaluate(board)。更省事的写法是把棋盘视角翻转后传参但那样每层都要拷一份数组不划算。现象二AI 有三连能赢却绕路或者赢了之后还在继续下。原因胜负分值和评估分量级不匹配。PATTERN[5]是 200000而全盘评估累加下来很容易超过这个数一个活四 4800几十个窗口加起来上万很常见于是一个「五连」在评估里可能还不如「两个活四」值钱。 解决让WIN_SCORE远大于任何可能的评估值——1 24是个安全的选择全盘 900 个窗口 × 最大单项 200000 也就 1.8 亿塞得下。同时用WIN_SCORE - ply做最短胜修正。现象三搜索跑几分钟后 AI 开始乱下越到后面越离谱。原因make/unmake 不对称。某条提前返回的分支比如成五直接return忘了把board[move]还原成EMPTY棋盘上就多了一个幽灵子。一次两次看不出来几百次之后棋盘上已经堆满了不存在的棋子评估函数读到的东西和真实局面完全脱节。 解决所有落子/撤销都包在try/finally里或者干脆封装成上下文管理器。用异常做超时中断时尤其要小心——异常从深层冒泡上来中间每一层的board[move] EMPTY都不会执行必须在finally里还原。5.2 评估层与界面层候选点漏防、窗口卡死现象四对手摆出活三AI 不堵反而去扩展自己的二。原因候选点截断把防守点排到了外面。如果用「自己的进攻分」单独排序对手的活三点在自己眼里分值很低因为那格空着我方下下去没什么收益排到第 20 位被limit12截掉。 解决排序分必须是「进攻 防守」的加权和point_score(board, p, color) * 2 point_score(board, p, 3 - color)防守项权重不能低于 1.5。另一个兜底措施如果对手存在活四或冲四直接跳过排序只考虑封堵点。现象五窗口一拖动就提示「无响应」或者思考期间界面完全定格。原因搜索跑在 pygame 的主线程里。pygame 的事件队列需要主线程持续调用pygame.event.get()来泵一旦主线程陷入一个几秒的纯计算循环系统就会判定窗口失去响应。 解决搜索挪到子线程主线程保持 60 帧的事件循环跨线程只传「棋盘快照」和「最终着法」绝不传 pygame 的 Surface、Font 对象——它们不是线程安全的跨线程绘制偶发崩溃而且崩得毫无规律。至于「帧率抖动」那是 python 的固有代价纯计算线程在 GIL 下并不能真正并行主线程只能靠字节码间隔抢时间片。想要稳定 60 帧得把搜索换成独立进程代价是棋盘要序列化过去。这个取舍值不值取决于你更在意界面流畅还是代码简洁。6. 固定深度还是固定时间一个必须提前做的取舍写完搜索之后几乎所有实现都会遇到同一个问题depth到底填几。填 4中局一秒内出结果但看不见四三杀填 8残局能杀开局直接卡死。很多人选择折中填 6然后在某局棋里被一个 12 层的杀棋打得毫无还手之力。问题的根源是固定深度这个参数本身就是错的维度。搜索耗时并不由深度决定而是由「该深度下还剩多少候选点」决定——开局候选点稀疏深度 8 很快中局棋盘上几十颗子候选点密集深度 6 就可能超时。同一个depth在不同局面上意味着完全不同的耗时。正确的做法是固定时间让深度自适应。这里的关键是迭代加深的一个细节超时的那一层必须整层丢弃只保留上一层的完整结果。如果拿半层搜索的结果去比较你得到的是一个「部分分支搜了 8本文还有配套的精品资源点击获取