简介：这是一份面向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 -1

place和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, radius=2, limit=12): 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, key=self.move_score, reverse=True)[:limit]

radius控制搜索的“视野”，通常取 2；取 1 会漏掉一些跳二、跳三的延伸点，取 3 候选点数量会明显膨胀。limit是每层保留的候选数，这是深度和广度的直接交换：limit=12配合深度 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(limit=12): 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 best

alpha是当前节点已经确保能拿到的下界，beta是父节点给出的上界。3 - player是黑白互换的小技巧（1→2，2→1）。返回值是分数，实际落子坐标由根节点单独记录——这一点很多人第一次写会漏，导致搜完不知道该下哪。

3.2 剪枝条件的几何含义

alpha >= beta的含义是：当前节点已经找到了一个分数，这个分数高到父节点（对手）绝不会允许局面走到这里，所以剩下的兄弟分支不用再看了。

举个具体场景。假设我在某一层已经找到一个能赢的走法，分数是WIN-1。这时候我换一个走法试，对方在我的下一步里会尽最大努力压低我的分数。如果对方在某条分支里已经能把我压到低于alpha的值，那我就知道这条分支对我没好处，可以直接放弃。而当某个对手节点的返回值已经低于我已知的下界时，再算别的分支也不可能让这个节点对对手更有利——因为对手是取最小值的，它的值只会更低。

这就是 α-β 剪枝的本质：它利用的是“对手不会配合我”这个假设，而这个假设在完美信息零和博弈里永远成立。

3.3 走法排序：剪枝效率的真正杠杆

理论剪枝效果极度依赖顺序。最好情况下（每层都先搜最优走法），时间复杂度从 O(b^d) 降到 O(b^(d/2))，等效于搜索深度翻倍；最坏情况下（每次最差的走法先搜），剪枝完全不生效，还多了一层比较开销。

实践中性价比最高的一步是把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 total

line_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, key=lambda x: (-score(x), x))，用位置作为第二关键字打破平局；置换表的键改用 Zobrist 哈希，用固定的随机数表对每个格子的每种颜色做异或，保证跨进程稳定。

6. 深度与广度的取舍：为什么不能一路加深下去

搜索深度从 4 加到 6，节点数在理想剪枝下大约涨 3 到 10 倍，棋力提升明显；从 6 加到 8，很多实现就开始卡在时间预算边缘，而且收益并不线性——因为深度越深，叶子节点的评估误差被放大的机会越多，这叫“奇数层效应”：搜到奇数层时，评估函数是在对手走完后的局面上算的，天然偏向对手，AI 会变得保守甚至自暴自弃。

工程上的应对是迭代加深只取偶数层结果，或者用静态搜索（quiescence search）在叶子节点继续展开“吃子”类强制走法直到局面平静。五子棋里的“吃子”对应的是冲四和活四这类必须应对的威胁，在叶子节点把它们展开完，能显著减少评估误差。

另一组取舍在候选点数量上。limit从 12 降到 8，同样时间内能多搜一层，但会漏掉一些冷门好点；从 12 升到 20，广度上去了，深度就得砍。我的经验是，在中低深度区间（4 到 6 层）优先保广度，因为浅层漏掉关键点的代价太大；深度上到 8 层以上再收紧候选数，让排序质量承担筛选工作。

最后是一个验证方法：不要靠“感觉这盘下得不错”来判断改动是否有效。准备一组固定的开局局面，让新旧两版各跑一遍，比较落子坐标和搜索节点数；再让两版互相对弈若干局，看胜率变化。这个流程比单盘观感可靠得多，也是我后来每次改动评估函数或剪枝顺序都会走一遍的固定动作。有次我只调了一个棋型分数，观感上觉得 AI 变强了，跑完这组对照才发现它只是变得更激进，对活三的防守反而退化了。

从那以后我每次动评估表或者候选点排序，都强制走一遍这组固定局面加互弈的对照，宁可多花二十分钟，也不信单盘的感觉。希望帮到你。

本文还有配套的精品资源，点击获取