如果你第一次想做一个会下五子棋的程序多半会从最粗暴的思路开始让电脑走完每个空位看看哪里能直接赢哪里能堵住对手。这种贪心打法打个四五步还行一旦对面会做双三、做杀立刻原形毕露。原因很简单——五子棋的胜负不是看当前这一步谁能连成五子而是看谁能在未来几步抢先做成必胜形。于是这个项目会自然走向同一个方向基于博弈搜索算法的智能五子棋设计。这个项目本质上做的是这样一件事不让AI只看一步而是让它像人一样“心里面先摆几步棋”把所有可能的后续变化展开成一棵树再用胜负评估从枝叶往根部倒推最终选出一条对自己最有利的分支。它能解决的问题也很明确让AI具备中盘攻防判断力、能提前发现对手的杀招、能在有限时间内做出接近人类棋手的决策。适合谁来搞刚接触博弈算法的人、想搞明白搜索树怎么落地成程序的人、以及已经写出过一个基础五子棋对战逻辑但觉得AI太弱的人。整个项目不需要深度学习框架不需要GPU核心逻辑用纯数据结构和递归就能跑起来概念清楚之后大约几百行代码量级就能看到一个有模有样的对手。我在这个项目里试过好几版方案从最早的贪心评分到后来的极小极大搜索、α-β剪枝、评估函数调优最后再加上迭代加深和走法排序。过程中踩了不少坑也总结出一些不写代码就根本发现不了的经验。下面按我的实际开发顺序来复盘把每一步为什么要这么做、怎么做的、有哪些坑都摊开讲清楚。1. 为什么需要博弈搜索五子棋AI不是“猜格子”1.1 贪心局部打法的天花板最原始的AI写法是这样的遍历棋盘上所有空位对每个位置算一个“落点分”谁在这个位置落子后能形成的连线威胁最多、给对手的威胁堵得最死分数就最高。实测下来这种AI在开局前几步选择还算正常因为它会优先抢占中心附近。但进入中盘后问题非常明显它只看自己当前一步棋的“局部收益”完全看不到“这一步之后对手会怎么反制”。举个很典型的例子。黑棋在某处形成了一个活三白棋如果只顾着堵住这个活三的一端黑棋另一端一冲就变成冲四下一步直接成五。贪心AI在计算“堵哪边”时可能只看两种堵法当前局面的静态分值两者差不多于是随机选。但人眼一看就知道必须堵在能同时限制未来成五的一侧。这种判断依赖的是多步推演不是单步打分。另一个例子是进攻时的“做杀”。高手下棋会故意留出两个不同方向的眠三看起来当前没有直接成五的威胁但下一步无论对方怎么堵都能利用另一侧形成冲四活三。贪心AI对这类棋形的估值非常低因为它只统计当前棋盘上的连线数量不会把“未来两步的组合威胁”折算进来。所以结论很直接要让AI具备真正的攻防意识必须把搜索树展开让程序看到多步之后的变化。1.2 零和博弈与决策树的建模五子棋是标准的零和博弈黑白双方利益完全相反一方赢另一方必然输不存在双赢。这意味着我们可以把局面定义为一个数值估值正数代表对先手或当前方有利负数代表对对方有利而每一方落子时都试图让最终估值向自己一方倾斜。从当前局面出发轮到己方落子时可以选择若干个候选点每个候选点落子后又轮到对方选择以此类推就形成了一棵博弈树。树的根节点是当前局面叶子节点是到达搜索深度上限后的局面或者是已经分出胜负的局面。博弈搜索要做的就是假设双方都绝对理性每层都选择对自己最有利的分支把这个“最优结果”反推到根节点。如果完全没有限制地展开整棵博弈树复杂度是什么水平15×15标准棋盘第一手有225个空位第二手224个深度6层的理论分支数就是225×224×223×222×221×220这个数大得可以放弃思考。好在实际项目中我们用两个手段把树压小一是在生成候选点时不考虑全部空位只考虑已有棋子附近的点分支因子降到20到40左右二是用剪枝把不需要展开的分支直接砍掉。这两种手段缺一不可单纯缩小分支仍然不够剪枝才是真正让搜索深度提升的关键。两者配合深度6到8的搜索在一秒内完成是完全可以做到的。2. 核心搜索算法设计极小极大与α-β剪枝的落地2.1 负极大值框架如果严格按“己方取最大、对方取最小”来写代码里要区分当前层是谁在走逻辑略绕。更简洁的做法是负极大值框架。它的核心思想是当前节点价值的相反数等于下一层所有子节点价值的最大值。因为从当前方的角度看下一步轮到对方对方会选对对方最有利的分支而这个分支对当前方来说就是最不利的所以取相反数再取最大值。核心伪代码大概是这样的def negamax(board, depth, alpha, beta, player): # player 表示当前轮到谁走1 表示黑方-1 表示白方 # 搜索到叶子节点返回评估值从当前player角度看 if depth 0 or game_over(board): return evaluate(board, player) moves generate_moves(board, player) for move in sorted(moves, keymove_score): make_move(board, move) score -negamax(board, depth - 1, -beta, -alpha, -player) undo_move(board, move) if score beta: return beta # 剪枝 if score alpha: alpha score return alpha注意这个写法里alpha和beta传进去时都取了负数并且交换了位置。这意味着当前层搜索到的有效区间是[-beta, -alpha]对下一层来说它只需要判断子节点是否可能超出这个区间。一旦某个子节点分数超过了beta说明对方无论如何都不会让当前方达到这个分数当前方也没有继续搜索这个节点其他子分支的必要。负极大值本质上只是极小极大的一种等价改写但代码量少、不易出错是我个人最推荐在五子棋这类零和游戏里用的形式。2.2 剪枝逻辑为什么高效α-β剪枝的核心认知只有一句话当前方关心的分数区间越来越窄超出区间的分支不需要看。alpha的初始值是负无穷表示当前方能接受的最差分数下限beta初始值是正无穷表示对手允许给你的最好分数上限。搜索过程中alpha会被不断抬高因为当前方每发现一个更好的走法就说明他至少能拿到这个分数beta会被不断压低因为每层都有一个上限约束。什么时候剪枝关键判断是if score beta。如果某个子节点返回的分数已经高于当前节点的beta意味着这个节点的父节点对方那层根本不会选择当前这条分支因为继续往下搜也不会影响更上层的决策。于是整个节点可以直接截断后面的子节点全部不看了。剪枝效率最理想时可以比原始极小极大搜索节省大约一半的深度工作量但前提是节点访问顺序足够好。如果每次都先访问最差的走法alpha值和beta值迟迟不收敛剪枝就可能接近失效。这一点直接引出下面一个问题走法排序不是可选优化而是剪枝能否发挥效果的前提条件。2.3 剪枝的启动条件走法排序我先跑过一版完全不排序的搜索深度6结果慢得让人崩溃。后来加上简单的静态评估排序速度快了不止一个量级。原因就在于剪枝对顺序极度敏感好的顺序可以让alpha快速抬高、beta快速压低让更多节点被裁剪。候选走法生成之后我会先用一个快速的静态评分给它们重新排序。这个评分不需要和最终评估函数完全一致只需要大致正确就够。我常用的快速评分有两个来源该点落子后所形成的分数粗略统计该点四个方向上能形成的连线数量该点是否能直接形成活四、冲四、双三等关键威胁若能则排到最前面这一步排序加进去之后搜索速度提升非常明显。如果有余力还可以加入杀手走法和历史启发。杀手走法是指在同一深度层面上上次搜索中成功触发剪枝的那步棋历史启发则是全局统计哪步棋更容易触发剪枝给这些走法更高的优先级。这两个优化本质上是利用搜索过程中积累的经验把“最可能最有威胁”的落点提前尝试从而让剪枝更早发生。还有一个我后来加的优化置换表。五子棋搜索过程中不同的走法顺序可能到达相同的局面如果不做记录就会重复搜索。用Zobrist哈希把已经算过的局面缓存下来命中时直接返回结果。不过在棋盘中这个优化收益不如国际象棋明显因为五子棋的搜索树重叠程度相对较低如果你的深度保持在6到8走法排序做好之后置换表可以后面再加。3. 评估函数AI的“棋感”从哪来3.1 特征提取扫描模式而不是算死活评估函数是搜索的大脑。搜索树只知道“往深处走”但走到叶子节点后这个局面到底对谁有利、有多有利全靠评估函数给出一个数值。五子棋的评估不需要做复杂的死活分析更常见的做法是扫描盘面上的所有“线”统计每条线上出现了哪些棋形然后把棋形映射成分数求和。具体扫描方式是这样依次检查所有行、所有列、所有对角线包括两个方向对每一条线用一个滑窗提取连续的棋子段。如果一段连续的空格之间只存在同色棋子并且两端延伸出去还能有空格再接棋子我们就可以把这一段归类为某种棋形。比较常见的分类有活四四个同色棋子连续排列两端都有空位下一步必然成五冲四四个连续棋子只有一端是空的需要堵住活三三个连续棋子两端都有空位能发展成两个方向的活四眠三三个连续棋子只有一端能继续发展活二、眠二更基础的发展形状实际项目里我还会统计“一侧有棋、另一侧空出连续空格”这种延伸型棋形比如X_X、XX_这类。因为五子棋的威胁不一定是紧密聚集的中间隔一个空格也能组成形状。纯粹的连续串判断会漏掉很多关键棋形。3.2 权重表与位置加分每种棋形给多少分会直接影响AI的风格。我最初用的权重表核心是这样一组数字活四10000冲四5000活三800眠三80活二200眠二20为什么要给活四和冲四那么高的分因为看到活四几乎等同于看到必胜。对手虽然可以堵一端但另一端一定成五所以活四是决定性的分数。冲四虽然也需要应对但威胁比活四低一档给5000分合适。活三设定为800分是因为活三之后如果对手不马上处理下一手很可能变成双三或冲四活三属于即将转化的高威胁形。位置加分也很重要。五子棋中心的影响力远远大于边角。我用一个和棋盘中心距离有关的二次函数给每个落点加分越靠近中心加分越高越靠边加分越低。但这里有一个我踩过的坑纯中心加分会和搜索深度产生冲突。当搜索深度足够深时AI能通过搜索发现边角局部的杀棋却被位置加分拉去走中心。这在实战中表现得非常诡异明明看到一步冲四就能赢AI偏要先占中心点位原因是中心位置加分抵消了冲四个别棋子带来的劣势。后来我把位置加分的权重压到很低让它只作为同棋形之间的小幅微调而不是能和“杀形分数”抗衡的量级。这个改动让AI的走法一下子“像人”了。3.3 攻守平衡的调整逻辑评估函数里如果只统计当前方的棋形分数AI会变成一个狂攻不止的莽夫经常在局面明显危险时不顾防守。我的办法是对防守分数乘以一个系数在计算局面总分数时对手的威胁分数乘上防御系数r再减掉。市面上很多实现采用的r在1.0到1.3之间。默认1.0即攻守完全等权实测下来纯等权在前期容易白棋漏防因为先手黑白开局天然有进攻优势。我自己的实测经验是r取1.15左右比较稳AI会明显更注意堵对手的活三、防双三但不会因为防守过度而丧失进攻机会。如果把r调得很大比如1.8以上AI会变成纯防守型对手有什么威胁堵什么威胁结果往往是自己始终没有杀棋只能慢吞吞地等对手失误最终被对手先做成必胜形。所以攻守平衡的调整不是一个“越大越好”的问题而是基于AI面对的实际开局状态不断试出来的参数。需要说明的是这个r系数不是拍脑袋定的我用一组固定开局做了一批自对局测试统计胜率。比如黑棋开局花月、白棋开局斜月两边都跑同一版本的搜索逻辑固定搜索深度后调整r对比双方胜率和平均步数。最终选在胜率最高、均局步数适中这个区间。这类调参实验做起来不贵但回馈非常直接。4. 从零到可对战的完整实现流程4.1 棋盘点数、胜负检测与输入处理棋盘我用15×15的二维数组存储初始值0表示空1表示黑棋2表示白棋。整个项目里最基础的两个函数是落子和胜负检测。落子之后做胜负检测时不需要全盘扫描只需要沿着刚落的棋子向四个方向横、竖、左上到右下、右上到左下延伸统计连续同色棋子数量只要有一个方向达到5即可判定胜利。这里特别要注意标准五子棋规则里长连超过5在无禁手规则下是算赢的如果做有禁手规则则黑方长连视为禁手需要额外处理。我做的第一个版本是无禁手规则允许6连以上直接计赢程序逻辑很简单。后面如果想接入禁手必须在落子合法性判断和胜负判断里同时加入长连和三四四检测这是一个独立的复杂度块不要混一起写。输入处理我做了两种控制台版本接受命令行坐标输入带界面的版本利用鼠标点击映射到棋盘。控制台版本适合反复自动化测试界面版适合给人演示。从开发效率角度我建议先把控制台版跑通确认AI逻辑没问题后再接界面因为界面层和AI层耦合在一起时排查问题会非常痛苦。4.2 候选落点生成与快速评估候选落点生成是整个搜索性能的第一道闸门。我的做法是遍历整个棋盘找出所有已经落子位置周围两格范围内的空点去重后作为备选。为什么是两格而不是一格因为五子棋的棋子距离太远时对局面的影响几乎为零一格范围又可能漏掉间隔一子的棋形。实测下来两格是性能与覆盖率都合适的折中。每生成一个候选点还要给它一个快速评估分用于走法排序。我用一个简化的局部评分统计该点在四个方向上形成的连续棋子数量和潜在成五窗口再粗略估算它攻防的紧迫程度。这一步的心态是“不求准确但求别把好棋排到后面太远的地方”。如果你发现搜索深度上不去剪枝率低先检查这一步排序是不是太粗糙了。候选点生成还有一个细节如果当前局面是空盘直接返回中心点坐标。如果不加这个特判AI第一步会按照排序选择某个边角点虽然不算错但明显不符合常规开局习惯。加上这个特判后黑棋必然天元开局后续变化也更符合下棋逻辑。4.3 搜索主循环迭代加深与时间限制固定深度搜索有一个问题你没办法知道某个深度下的搜索到底需要多少时间。深度5很快深度6翻几倍深度7直接卡了这种波动在实时对战中很难接受。迭代加深的解法是从深度1开始逐层增加深度搜索每层都完整跑完如果超时就用上一层已经搜索出的最优走法作为落子结果。迭代加深看似会重复搜低层有额外开销但两种实际因素让它变得很合算一是低层的走法排序结果可以被高层重用高层搜索的剪枝效率因此明显提升二是时间控制非常顺手不会出现“这一步想了10秒下一步却秒落子”的不稳定情况。我的主循环大概是这样的结构best_move generate_moves(board)[0] for depth in range(1, max_depth 1): if time_is_up(): break try: score, move search_with_negamax(board, depth, timestamp) best_move move except TimeoutSignal: break return best_move如果允许时限设置为1秒通常会跑到深度8左右如果想展示棋力可以放宽到3秒深度能到10甚至更高。实测下来深度8的AI已经能让很多不熟悉五子棋的玩家感到吃力深度10以上在开局阶段基本能锁定多种必胜变化。执行搜索时还需要记录一下最优走法的更新方式。我在负极大值循环里每当alpha被更新时就同步更新当前层对应的落子坐标。这样搜索结束时最终的alpha值对应的就是最佳落点。注意不要在剪枝返回时误改落子坐标否则会出现在明明找到冲四的时候却乱走一步的情形。5. 实测调参三组参数把棋力从“乱下”练到“稳守反击”5.1 基准版本的对局表现我先把第一版AI搭起来参数是最初的评估权重表加候选点周围一格范围搜索深度固定为6没有走法排序攻守系数r1.0。跑了一组AI自对弈测试发现两个问题。一是开局选择很奇怪明明中心点已经被黑棋占住白棋第一手会走到边线附近原因是位置加分在整条对角线上的权重分布不均。二是我用人工下过几局AI在某方形成活三时会防守但如果对面直接“双活三”一步做成AI往往盯住其中一个活三就堵不会主动去判断双三是否已经形成必胜。问题的根源在于深度6的搜索在没做好排序时实际剪枝率很低算力被大量浪费在无效分支上导致关键杀棋在有限深度内根本没被发现。5.2 权重与搜索深度的联合优化第二轮调整里我把候选点范围扩大到周围两格给走法排序加上了静态快速评分攻守系数r调整到1.1同时把搜索深度从6提升到8。这次自对弈测试里AI中盘的防守明显更靠谱尤其对活三、冲四的响应基本不会出大错。但新问题又出现了AI过于“求稳”在局面有明显进攻机会时优先防守导致很多局最后发展成双方对耗最后赢棋是靠对方某一个失误而不是自己主动做出杀棋。我把评估函数里活三权重从500拉到800冲四和活四的比例也重新调过局面明显变得更加有攻击性。测试中白棋作为后手方胜率出现了明显上升说明AI不是只会在先手时抢杀后手也能通过防守反击寻找战机会。第三轮我加了一个组合棋形加分当盘面上同时出现两个具有方向扩展潜力的活三时额外加一笔组合分两个冲四同时存在时也额外加分。这一步对杀棋检测起到很大作用AI终于会主动往“双三做杀”的方向走了。5.3 搜索深度与候选范围的联动效应有一个误区值得提一下搜索深度不是越大越好。深度提升会导致每层节点数爆炸如果你同时把候选范围扩大到周围3格搜索时间可能直接翻好几倍而棋力提升并不明显。我的实测结果是候选点范围在2格、深度8整体棋力要优于候选点范围3格、深度7。因为候选点范围扩大引入大量远距离无关落点干扰了剪枝排序的效率导致真正的关键点反而被向后排。核心策略应当是把候选范围保持在能覆盖所有关键威胁的最小值然后把多余算力分配给增加深度。6. 常见问题与排查技巧实录6.1 搜索太慢每秒都像在“思考人生”如果你发现AI一局棋要思考好几秒甚至十几秒不要急着优化评估函数先检查三件事。第一走法排序是否真的生效了。排序没做好的α-β剪枝大概率退化成全节点搜索。在搜索入口打印一个剪枝统计变量看看实际访问节点数和理论节点数相比差多少如果剪枝率不到50%马上回头检查排序函数。第二候选点范围是不是太大了。我用2格作为默认几乎没遇到过必须展到3格的情况。第三每次搜索是否重新生成了候选点列表而没有复用生成结果。这个问题在前期代码里经常出现尤其当你的生成函数写得比较复杂导致每层节点都会做重复的全盘扫描时性能会平白无故掉好几倍。还有一个容易被忽视的问题胜负检测函数在全盘扫描时做了很多重复工作。如果你用的是“每次落子后全盘四个方向扫描”这种写法搜索深度6时胜负检测会占用大量的时间。更合理的写法是只检测当前落子点周围四个方向因为一个棋局中只有当前刚落下的棋子可能产生新的胜利。6.2 水平线危机与胜负错判搜索树有固定深度就一定会碰到“水平线问题”某些局面在深度边界外会形成杀棋但深度范围内看起来还很平静于是AI做出错误的判断。比如某一步落子后对方下一步能形成冲四活三但你再往下看两步就会赢回来搜索深度不够时AI可能只看到“对方冲四活三”这个糟糕结果错过了深层反杀。我的解决办法是在搜索入口加一个“胜负优先分支”如果当前节点存在立即成五或直接冲四活三的走法不进入通用搜索直接走这条分支。也就是说评估函数和搜索对“杀形”的敏感度由深度保证但对“一步杀”和“两步杀”这类必然转化需要在搜索外部单独侦查。做这一步之前AI经常会在明明可以直接成五的时候选择走一个活三让对手有机会堵掉胜机——这绝对是新手AI最常见也最让人咬牙切齿的问题。6.3 AI行为怪异如何判断是评估问题还是搜索问题AI突然走出一步毫无逻辑的棋不要急着怀疑是评估函数权重不对。我总结了一个快速排查流程把这一步搜出来的评估分和候选落点分数打印出来接着固定搜索深度只改评估函数的一个参数重新跑同一步。如果搜索分数变化剧烈而且新选择的落点符合你的预期多半是评估函数权重出了问题。如果无论怎么调权重落点选择始终很奇怪那大概率是搜索本身的bug。典型bug包括落子后忘记撤销、某个分支的alpha/beta更新出错、空盘特判没有生效、棋盘坐标和逻辑坐标翻转等等。我遇到过最隐蔽的问题是“历史启发表没有随搜索深度重置”。历史启发是以“全局哪个点剪枝多”为依据的但不同深度的开局阶段好的落点集合完全不同。如果不重置历史表AI会倾向于选择上一局深层搜索中表现好的点全然不顾当前盘面——感觉像是突然犯病。6.4 禁手、长连与平局的边界处理如果你做的是标准无禁手规则长连6连以上算赢程序判断“达到5个连续棋子”后直接结束完全没问题。但如果你打算接入有禁手规则事情会复杂不少。长连禁手意味着黑棋六连以上的形状判负三三禁手意味着黑棋同时形成两个活三判负四四禁手意味着同时形成两个冲四或活四判负。禁手检测必须在评估函数和胜负判断中同时生效。评估函数里如果不考虑禁手AI在搜索时会把禁手棋形算成优势导致黑棋主动走出禁手然后被判定输棋。胜负判断里如果不考虑禁手则黑棋可能在已有禁手形状时还认为自己有胜机产生自相矛盾的搜索结果。有禁手版本还有另一个连锁反应白棋可以利用黑棋禁手制造“逼禁”。比如白棋故意不堵某个黑棋活三实际上是在引诱黑棋形成禁手而输棋。这种策略对搜索深度非常敏感通常需要8以上的搜索深度才能稳定躲避或利用禁手局面如果你的AI主要面向普通玩家我个人建议默认采用无禁手规则把禁手作为进阶扩展而不是第一版的核心功能。7. 这个项目后续还可以怎么扩展在我自己完成的这个版本里AI已经有“看懂棋形、提前规划、主动做杀”的基本能力。继续往下走的扩展方向我认为至少有两条有意义。一条是蒙特卡洛树搜索。α-β剪枝依赖评估函数而评估函数需要人工设计棋形和权重这在实际项目里是很大的调参工作量。MCTS的做法不一样它通过随机模拟对局来估算胜率不需要一个人为定义的评估函数在某些局面下反而能发现人工棋形很难表达的策略。不过MCTS在五子棋上有个明显短板模拟随机对局得到的胜负信号方差很大需要很多模拟次数才能稳定实时性压力比α-β搜索大不少。另一条是用深度学习替代或配合评估函数。把评估函数换成一个小卷积网络输入棋盘局面输出局面估值。这样做的好处是评估信号更连续不需要手动设计棋形但需要额外整理训练数据我的经验是先用传统α-β框架跑通整个流程把深度学习作为一种升级路径去接而不是第一版就上否则光调试训练流程就会淹没掉博弈逻辑本身的学习。我个人感受最深的一点是人机对战类项目的终点往往不是“AI棋力有多强”而是“AI在有限算力下如何保持稳定的棋力表现”。剪枝、排序、评估、时间控制这几个模块每一个都在限制条件下做权衡你优化了一个另一个就可能成为瓶颈。这个项目的价值不在于最终能不能打赢你而在于它把一个抽象概念“搜索树”变成了一个你随时可以迭代、测试、调优的真实系统。如果你也准备写自己的五子棋AI我建议不要急着把模型搞得花哨先把搜索框架和评估体系搭扎实后续加什么技巧其实都是锦上添花。