“五子棋AI”这几个字听起来像是一个小玩具但真动手用C写一个能下、能防守、还能杀棋的程序你会发现它几乎把博弈论、搜索算法、数据结构、性能优化全都卷进来了。它不像深度学习模型那样需要海量数据和显卡而是靠一套精密的搜索树和评估函数在纯逻辑层面把“棋感”做出来。这篇文我打算用做过类似项目的人的口吻把C五子棋AI的算法拆开讲透从棋盘怎么存、五连怎么判、评估函数怎么打分到Alpha-Beta剪枝、候选点生成、迭代加深每一层怎么选、为什么选、踩过哪些坑尽量让想动手复现的人少走弯路。无论你是刚学算法的学生还是想拿这个练手C工程能力这篇都适用。1. 五子棋AI怎么拆整体设计与方案选型在写第一行代码之前我强烈建议先想清楚一个问题你做的五子棋AI是“什么量级”的AI。它决定了你要用多大搜索深度、要不要做开局库、要不要支持禁手规则以及整个代码结构会复杂到什么程度。别一上来就奔着“最强”去五子棋在棋盘只有15x15、但搜索空间依然恐怖的情况下真正决定AI水平的是评估函数和搜索策略的组合质量而不是单靠搜索深度。1.1 核心需求解析这到底是个什么项目从标题看“C 五子棋AI 算法及实现”它的核心目标是用C实现一个自动下棋程序。这个程序要么作为玩家对战的AI要么作为研究博弈算法的载体。需要的核心能力包括棋盘状态的存储与更新、落子合法性与胜负判定、AI决策模块评估当前局面并选出最佳落点以及对外接口人机对战时的输入输出。其中最容易低估的是“胜负判定”和“评估函数”的耦合关系。很多新手一开始只做判赢写一个连五检测就跑后来加AI才发现评估函数也要识别连五、活四、冲四、活三这些棋型这两套逻辑其实可以共用一套扫描器。我建议在开放设计时就把棋型识别抽成公共模块否则后面会重复维护两套差不多但又不一样的代码改一处漏一处调试起来非常痛苦。1.2 方案选型为什么选极小化极大与Alpha-Beta剪枝五子棋AI的主流方案几乎绕不开极小化极大搜索Minimax。它的核心逻辑是轮到AI下时AI要选一个使自己收益最大化的点轮到对手下时对手会选一个使AI收益最小化的点这种轮流博弈的树形展开就是博弈树。但是朴素的Minimax有个致命问题搜索树呈指数膨胀。假设每层有20个候选点、搜索6层节点数就是20的6次方6400万这个量级在C里还能勉强扛但很吃力。所以必须搭配Alpha-Beta剪枝——它能在不影响最终结果的前提下把大量不可能被选中的分支剪掉实操中能把有效搜索量降低到原来的几分之一甚至让同样的时间能多下一到两层深度。这也是为什么几乎所有实战五子棋AI都选择“Minimax Alpha-Beta”这对组合而不是蒙特卡洛树搜索。MCTS在围棋上很成功但五子棋棋型结构清晰、评估函数能做到很准经典搜索反而更高效、更可控。1.3 整体架构模块划分与数据流一个清爽的五子棋AI项目通常划分成四层表示层、规则层、评估层、搜索层。表示层负责棋盘和棋子数据规则层负责走法生成、合法性校验、胜负判断评估层把棋盘局面变成分值搜索层在分值之上做博弈树搜索。数据流是单向的搜索层从规则层拿到候选走法扩展局面后调评估层打分再把局面回传给规则层做下一步走法生成。划分清晰之后你的代码可以分别测试比如单独给评估函数写单测单独验证胜负判定排查问题时会非常省力。我见过不少人把胜负判定放在搜索函数里面直接写四层循环短是短了但项目一扩展就崩。一个简单的判断标准如果某个模块以后可能被单独复用比如禁手判断、开局库、棋局回放就把它单独拎出来。五子棋AI这种规模的项目保持模块边界比追求代码量少更重要。2. 棋盘表示与落子规则一切AI的地基棋盘表示是整个AI的地基。这听起来像废话但选错了数据结构后面所有搜索和评估的性能瓶颈都会提前到来。五子棋通常用15x15棋盘常见的表示方式有三种二维数组、一维数组、紧凑位棋盘。对五子棋来说二维数组最简单一维数组在性能上更友好位棋盘则适合做非常高强度的计算。2.1 棋盘数据结构怎么设计大部分人用vectorvectorint board(15, vectorint(15, 0))0空、1黑、2白方便是方便缺点也很明显内存不连续、缓存命中率低、每次访问多一次指针间接跳转。搜索层每秒要调用几十万次棋盘状态判断时这个开销会被放大。我更推荐用一维数组比如std::arrayint, 225或者int board[225]下标pos row * 15 col。这样棋盘数据在内存中连续排布遍历和拷贝都极快搜索时做“模拟落子”只需要存一个回退值不用复制整个棋盘。实测在纯Minimax搜索中相同深度下一维数组比二维vector的实现能快出20%-30%这个差别在接近时间线时非常关键。如果要更进一步可以用一个uint64_t的位棋盘表示单色棋子分布配合预处理的位操作判断五连。但位棋盘在五子棋里收益不像国际象棋那么大因为五子棋棋盘225格超过64位必须拆成多块复杂度反而上升我建议新手先用一维数组等搜索优化到瓶颈时再考虑位玩法。2.2 胜负判定高效判断五连五连判断最简单的写法是落子后从该点出发沿四个方向水平、垂直、两条对角线检查是否连续满五个同色棋子。但要注意直接数“以落子开始往两边数”会漏掉一种情况新落子不在五连的正中间而是作为延伸的一部分所以正确做法是“从落子点向两个方向累计连续同色棋子数再判断总和是否大于等于5”。高效的实现可以写成八方向扫描先把四个方向的正反两个朝向加起来。判断时不用全盘扫描只检查落子点周围即可因为只有新落子可能改变胜负状态。代码上可以复用一套“在指定方向统计连续子”的函数bool checkWin(const vectorint board, int pos, int player) { constexpr int dirs[4][2] {{1,0},{0,1},{1,1},{1,-1}}; for (auto d : dirs) { int count 1; for (int sign -1; sign 1; sign 2) { int nr pos / 15 d[0] * sign; int nc pos % 15 d[1] * sign; while (nr 0 nr 15 nc 0 nc 15 board[nr * 15 nc] player) { count; nr d[0] * sign; nc d[1] * sign; } } if (count 5) return true; } return false; }边界处理最容易出错尤其对角线的nr和nc必须同时判断越界。很多Bug都来自只检查行越界不检查列越界。2.3 落子合法性、禁手与边界落子合法性不仅包括“该位置为空”还取决于你支持哪种规则。如果你做无禁手规则一手交换或自由开局AI的黑白策略只需要围绕棋型。如果做有禁手的标准规则黑棋还要判断三三禁、四四禁、长连禁这会让走法生成和评估函数都复杂一层。禁手判断是五子棋AI里第二大坑。它的本质不是“数棋型是否成立”而是判断“落子后是否同时形成两个及以上活三或冲四”。实现时要小心活三、冲四、活四这些棋型的定义在不同规则里有差异一旦评估层面的棋型模型和禁手判断层面不一致AI会出现“自己算出胜利却反复不下”的诡异行为。我建议要么一开始就明确做无禁手版本先把主线走通再把禁手作为增量功能加。很多AI对战平台对禁手规则要求并不严格无禁手版本的市场也同样大不必为了炫技把自己卡在第一步。3. 评估函数AI的棋感从哪来评估函数决定了AI的“眼光”好不好。搜索再深如果评估函数只盯着连子数量AI一样会走出低级棋。好的评估函数本质是对各种棋型建模给出一个相对合理的评分表然后聚合出当前局面的分值。要注意评估函数是给“某一方视角”算分的搜索层需要一个“当前轮到谁”的视角切换——最好评估函数返回一个以“当前搜索方”为正方向的分值或者返回黑方视角分再由搜索层做符号转换否则Minimax的取大取小逻辑很容易写错。3.1 棋型识别与评分体系五子棋的基础棋型就几种连五、活四、冲四、活三、眠三、活二、眠二。它们之间是递进关系连五必赢活四下一步必赢冲四对方必须挡活三是下一步能变冲四或活四的威胁。一个经典的评分表可以这样设棋型分值说明连五1000000已经获胜活四100000两头都没被堵必赢冲四10000有一头被堵对方必应活三5000两头通畅的三连眠三500只有一端能发展的三连活二500两端通畅的二连这里注意配合形状眠二50一端受阻的二连比分必须拉开量级比如连五远大于所有棋型之和。经验准则是某个棋型的分值应该在“任何组合加总”后仍然无法超过更高一级棋型。否则AI会出现“为了一堆小棋型放弃一个活三”的反智决策这种问题很难通过搜索深度弥补只能在评估函数里根治。3.2 对局反转与“空点”的评估方式评估棋盘局面有一种常见做法把黑白双方分别扫描一遍算黑方总分为bg_score白方总分为wg_score当前局面分就是black_score - white_score假设正值利于黑方。搜索时如果轮到白方走搜索层会取所有走法中“black_score - white_score”最小的一步。扫描时要注意棋型识别里最经典的新手坑是把“活三”判断成“眠三”。活三必须满足“两端延伸后都能继续形成四”的条件不能只数“三连是否被堵”。严谨的做法是对每一段连续的棋子序列数它两端的空位和控制力如果两端都是空位才算活三。还有一个更微观的坑某个落点在两端各产生一个二连它们实际共享同一个延伸点棋理上不算真正的“双活”但简单扫描器会误判成高分。这类误判会让AI出现“花式送棋”的迷惑操作。3.3 评估函数的性能与局部更新评估函数在搜索里会被调用得极其频繁百万次是常态。每次全盘扫描225个格点、还要处理多个方向开销非常大。我建议只要没到搜索的叶子节点尽量不做全盘重算而是维护一个增量式的局部影响缓存落子时只重新评估以该点为中心、半径为4的菱形区域内的棋型。因为五子棋的影响范围不会超过五连长度半径4格之外的老棋型结构完全不受影响。这样增量更新能把单次评估的开销从O(225)降到O(常数)在8层搜索下收益非常可观。一个常见的妥协方案是搜索到第N层时做精细全盘评估浅层用“点数启发方式”简化评估。说到底评估函数是个效率与精度的权衡场你不需要一开始就做到完美但要预留清晰的打分表结构和增量计算接口方便后面回头调权重。4. 搜索核心极小化极大与Alpha-Beta剪枝搜索模块是整个AI的心脏。没有搜索的AI只能算“一步棋贪心”有了搜索AI才会去“想两步、三步”也就是会考虑对手的最佳应对。这一章我会把Minimax和Alpha-Beta的关系讲透然后给出一个可以直接落地的C实现骨架。4.1 极小化极大搜索博弈树是怎么展开的极小化极大搜索的模型是树根是当前局面轮到AI走AI层取“子局面评分最大值”下一层轮到对手走对手层取“子局面评分最小值”如此交替。到了叶子节点达到限定深度或分出胜负用评估函数打分并回溯。写成递归核心逻辑很简洁int minimax(int depth, bool maximizingPlayer) { if (depth 0 || gameOver()) return evaluate(); vectorint moves generateMoves(); if (maximizingPlayer) { int best -INF; for (int move : moves) { makeMove(move); best max(best, minimax(depth - 1, false)); undoMove(move); } return best; } else { int best INF; for (int move : moves) { makeMove(move); best min(best, minimax(depth - 1, true)); undoMove(move); } return best; } }这个写法就是朴素的Minimax。它的问题在于完全没有利用“子局面的上下界排除”机会——很多分支还没算完就能断定它不可能被选择但程序依然傻傻地全算完了。对于五子棋这种每层候选点几十个、深层节点爆炸的情况必须上剪枝。4.2 Alpha-Beta剪枝把无用分支直接扔掉Alpha-Beta剪枝的核心思想是在递归过程中维护两个值alpha是当前路径上“轮到Max方至少能保证”的下界beta是“轮到Min方至多允许”的上界。当某个节点发现它已经让局面分值超出对方的接受范围时它后面所有兄弟节点都不需要再算了。在极大层如果当前分支的best已经大于等于父节点的beta则剪断。在极小层如果best已经小于等于父节点的alpha则剪断。具体代码如下int alphaBeta(int depth, int alpha, int beta, bool maximizingPlayer) { if (depth 0 || gameOver()) return evaluate(); vectorint moves generateMoves(); if (maximizingPlayer) { int best -INF; for (int move : moves) { makeMove(move); best max(best, alphaBeta(depth - 1, alpha, beta, false)); undoMove(move); alpha max(alpha, best); if (alpha beta) break; } return best; } else { int best INF; for (int move : moves) { makeMove(move); best min(best, alphaBeta(depth - 1, alpha, beta, true)); undoMove(move); beta min(beta, best); if (alpha beta) break; } return best; } }剪枝效果极度依赖走法排列顺序。如果把最好的走法排在最前面剪枝效率极高如果把烂走法排前面几乎剪不动。所以Alpha-Beta必须搭配走法启发排序否则你写出来的剪枝只会在理论上好看跑起来依旧卡成PPT。4.3 置换表与迭代加深的组合效果在Alpha-Beta基础上再进一步就是置换表Transposition Table。五子棋搜索中同一局面可能通过不同落子顺序到达比如先下A再下B和先下B再下A得到的棋盘状态完全一样。如果每次都从头搜索这是巨大的重复计算。置换表用哈希记录已经算过的局面和对应分值下次遇到相同局面直接返回存储结果典型工程实现可以用unordered_mapuint64_t, TTEntry或自定义开放式哈希表。Zobrist哈希是记录棋盘状态的标配做法对每个格子的黑白空三种状态各分配一个随机数落子时执行异或操作更新哈希值整局可以增量维护。实现不过瘾的话再叠加迭代加深——先搜1层记录最佳走法然后用这个走法作为下一层搜索的“优先走法”。迭代加深看起来很蠢每层都重复搜但它带来了三个好处一是时间可控游戏AI必须在限时内给出走法二是上一层的最佳走法可以直接作为下一层的候选排序首项显著提升剪枝效率三是浅层搜索结果可以填充置换表深层的搜索也因此受益。5. 启发式搜索与候选点生成让AI少算一半搜索速度的瓶颈不在搜索本身而在“搜索了谁”。如果你每次从225个格点里挑所有空点展开Alpha-Beta再强也救不回来。五子棋里高价值落子点高度集中在现有棋子附近所以候选点生成几乎是必需的剪枝前置步骤。5.1 候选点生成的几种常见策略最粗糙但有效的方法是只取所有已有棋子周围半径2格内的空点作为候选。原理很简单离所有棋子都很远的空点在当前局面下不可能产生立即的攻防价值。再精细一点可以给候选点打分排序统计该点周边四个方向上“这个点落下去后能形成的最强棋型是什么”按棋型强度排序。还有一种更激进的做法叫“进攻/防守双候选表”把所有能帮助当前方形成活三以上棋型的点标记为进攻候选把所有能阻止对方形成活三以上棋型的点标记为防守候选。搜索层优先展开同时具备双重属性的点因为这些点通常是真正的胜负手。这个策略对五子棋AI的水平提升特别明显能让同样的深度下棋力上涨一大截。5.2 走法排序剪枝率的天花板前面提过Alpha-Beta的剪枝效率几乎完全取决于走法排序质量。排序的核心原则是优先搜索“让当前局面迅速定性”的走法既有可能是杀棋的点也有可能是必须被防守的点。实现时可以在候选点生成阶段就利用评估函数给每个候选点算一个快速启发分然后按这个分排序。排序剪枝的实测效果差距巨大无序时同等时间只能搜4层采用启发排序后能稳搜6层。层数多了两层AI棋力表现会有一个质的飞跃。这里有个小技巧不用对每个走法都做完整评估排序可以先粗略算一个“单点铃型值”比如该点周围四方向上形成的连续子数和空位组合的粗估值排序后再交给评估函数精算。实测这种“先粗后精”的排序比全精算排序要快不少因为精算函数的常数项太高排序阶段不值得为每个点都跑一遍全棋型扫描。5.3 杀棋检测VCF/VCT的花样实现思路老手五子棋AI通常还会做杀棋搜索——VCF连续冲四取胜和VCT连续活三取胜。它们本质上是在搜索中限制走法类别只搜索冲四、活三等强制应手。这样可以在非常有限的候选点集合里展开几十步甚至上百步找到一条“迫使对手必然输掉”的路线。实现杀棋检测时可以用“强制序列”来辅助全搜索在全搜索的某个深度分支上如果检测到当前方有冲四或活三的强制棋型就把该分支强制切到杀棋搜索模块里跑几步快速判断。这样能让AI在高端局面下做出“先连冲几手再绝杀”的表演而不是四平八稳地只靠评估函数慢慢磨。杀棋搜索的意义在于它不靠评估分数而是靠“我能不能赢”的确定性判断这对五子棋AI的最终棋力提升极其关键。6. C实现的关键细节与性能调优算法懂了C工程细节没做好性能一样上不去。五子棋AI搜索是典型的计算密集型场景几个小小的数据结构决策就能让代码快几倍或者慢几倍。这一章聊我真正踩过、也真正改出效果的关键点。6.1 位运算与零拷贝性能调优中真正有效的两件事第一件事是用一维数组并尽量减少拷贝。搜索层每模拟一步棋通常只需要修改一个位置的值不需要为了保存局面拷贝整个棋盘。保存走法历史的做法是用一个moveHistory栈记录落子位置回溯时反转即可。如果一次要同时保存快照可以考虑std::arrayint,225的值拷贝但尽量别用vectorvectorint去反复拷贝。第二件事是合理使用位运算。五子棋的哈希更新直接异或Zobrist值棋型扫描里判断空位用整数比较候选点生成的遍历可以用预计算的距离数组替代实时计算。这些都是基础技巧但它们叠加起来效果巨大。我见过从“普通实现”切换到“一维数组增量哈希小对象分配池”之后同样的搜索深度耗时降到原来一半以下。6.2 走法容器与内存池别让vector反复扩容AI搜索会在瞬间生成大量走法列表。如果每个递归层都新建一个vectorint走法容器分配器会频繁申请和释放内存造成严重抖动。我建议用固定容量的std::arrayint, MAX_MOVES加上手动计数或者实现一个小型内存池在搜索开始时一次性分配好空间递归过程中复用。走法容器的大小怎么估算五子棋棋盘225格候选点半径2格内一般不会超过60个但边界和密集局面可能让你多留一点余量设成64或者128都安全。这种“小而固定”的内存策略在递归深度达8层以上时性能优势和稳定性都会体现出来。6.3 递归深度与超时控制游戏AI必须考虑时间线你不可能让对手等一分钟。常用的做法是迭代加深设置时间阈值例如每次思考限制在2秒内循环加深搜索层数每层搜索前检查时间是否超标超标就返回上一层的最佳走法。时间控制函数可以用std::chrono::steady_clock注意它是不受系统时间调整影响的时钟。另一个实用策略是“紧急剪枝”如果某层搜索时间已经超过预期可以在余下的走法排序中选择跳过部分低分走法。这是一个近似搜索的降级策略可以保证AI始终在限时内落子。我自己的实现里会设一个“危险时间点”超过它之后把候选走法裁剪到前6个实测能避免AI在残局时思考过久导致超时判负。7. 常见问题与排查技巧实录写五子棋AI最耗时间的地方不是实现而是“AI为什么要走这一步”。这一章是我自己的踩坑记录和排查思路把这些情况提前列给你你遇到的很大一部分问题其实别人都遇到过。7.1 AI死活不防守只知道进攻这是一个经典症状AI明明看到对方已经活三了还在自己造二连。回到评估函数你很可能把进攻分和防守分从同一个评分表里取了但防守分本质上应该是“对方从此点所得收益在己方视角下的负值”。如果你直接算“白方总分-黑方总分”要确保白方的防守点会被正确计为“白方在该点落子后的分数增益”。很多新手在评估时只计算“当前放谁落子的分”却忘了对防守评分做对称化处理。排查方法很简单构造一个只有“对方活三己方无关棋型”的棋盘局面把候选点按评估分排序输出看看防守点排第几。如果防守点排在末尾说明评分表权重失衡最常见是活三分值给得偏低。把活三、冲四分值再拉开一个数量级就基本好了。7.2 搜索太慢剪枝率到底怎么查剪枝率是衡量搜索效率的核心指标计算公式是“实际评估节点数 / 理论展开节点数”。你可以在递归入口加一个全局计数器跑几个固定棋局观察剪枝率。剪枝率低于60%通常意味着走法排序很差或者候选点集合太大。排查顺序是先看候选点生成是否限制了半径再看启发排序是否生效最后看Alpha-Beta的窗口有没有传错。有一个高发Bug是alpha和beta在递归回传时用错了变量导致剪枝条件永不成立搜索退化成全遍历Minimax。直接在递归入口打印alpha、beta和当前走法序号几盘棋就能定位出来。7.3 AI走法不稳定同一步棋前后不一致同局面下两次搜索给出不同走法多半不是因为AI“学到了”而是因为候选点排序不稳定或置换表没有被正确清理。如果你用过置换表一定要检查条目里的深度字段和局面哈希有没有重复使用。常见的错误是搜索深度8的结果被浅层搜索深度2的旧条目覆盖导致深层搜索读到陈旧分值。走法不稳定还有一个来源是评估函数里用了随机数作为微扰。有些AI为了增加变化性会故意加随机性但如果你期望它稳定复现同一棋步就要把随机种子固定并且把随机微扰限制在得分差距很小的走法集合内。7.4 复盘与调试一套实用的Log方案调试五子棋AI最怕黑盒。我的习惯是给搜索过程加一套“复盘日志”每层记录当前局面哈希、候选走法及其排序、alpha和beta值、最终选择走法。落子后保存完整棋局再配合一个简单的棋谱回放工具人就能直观看到AI在哪一刻开始犯傻。对单步走法分析可以用“局面-走法-评分”三元组把某一步的所有候选走法打印成表列出走法坐标、启发分、评估分。如果某个点明明是杀棋却没进入候选列表那就是候选点生成逻辑的问题如果进了列表却排在后边那就是排序或剪枝的问题如果排在前边却没被选那就是评估函数对该棋型漏算。按这个流程排查大多数AI“迷之操作”都能在半小时内定位而不是靠瞎猜。最后再分享一个个人经验五子棋AI项目最忌讳“求大求全”。先把无禁手、非开局库、固定深度3层的版本跑通再一步一步往上加启发、置换表、迭代加深每个改动都用固定棋局做回归测试。我就是这么一路踩过来的这个过程里学到的博弈搜索、C性能调试、剪枝策略迁移到其他棋类AI或者决策类程序里都完全够用。现在你再回头看“C五子棋AI”这个标题它其实是一个可以越挖越深的经典工程题目。
“五子棋AI”这几个字听起来像是一个小玩具但真动手用C写一个能下、能防守、还能杀棋的程序你会发现它几乎把博弈论、搜索算法、数据结构、性能优化全都卷进来了。它不像深度学习模型那样需要海量数据和显卡而是靠一套精密的搜索树和评估函数在纯逻辑层面把“棋感”做出来。这篇文我打算用做过类似项目的人的口吻把C五子棋AI的算法拆开讲透从棋盘怎么存、五连怎么判、评估函数怎么打分到Alpha-Beta剪枝、候选点生成、迭代加深每一层怎么选、为什么选、踩过哪些坑尽量让想动手复现的人少走弯路。无论你是刚学算法的学生还是想拿这个练手C工程能力这篇都适用。1. 五子棋AI怎么拆整体设计与方案选型在写第一行代码之前我强烈建议先想清楚一个问题你做的五子棋AI是“什么量级”的AI。它决定了你要用多大搜索深度、要不要做开局库、要不要支持禁手规则以及整个代码结构会复杂到什么程度。别一上来就奔着“最强”去五子棋在棋盘只有15x15、但搜索空间依然恐怖的情况下真正决定AI水平的是评估函数和搜索策略的组合质量而不是单靠搜索深度。1.1 核心需求解析这到底是个什么项目从标题看“C 五子棋AI 算法及实现”它的核心目标是用C实现一个自动下棋程序。这个程序要么作为玩家对战的AI要么作为研究博弈算法的载体。需要的核心能力包括棋盘状态的存储与更新、落子合法性与胜负判定、AI决策模块评估当前局面并选出最佳落点以及对外接口人机对战时的输入输出。其中最容易低估的是“胜负判定”和“评估函数”的耦合关系。很多新手一开始只做判赢写一个连五检测就跑后来加AI才发现评估函数也要识别连五、活四、冲四、活三这些棋型这两套逻辑其实可以共用一套扫描器。我建议在开放设计时就把棋型识别抽成公共模块否则后面会重复维护两套差不多但又不一样的代码改一处漏一处调试起来非常痛苦。1.2 方案选型为什么选极小化极大与Alpha-Beta剪枝五子棋AI的主流方案几乎绕不开极小化极大搜索Minimax。它的核心逻辑是轮到AI下时AI要选一个使自己收益最大化的点轮到对手下时对手会选一个使AI收益最小化的点这种轮流博弈的树形展开就是博弈树。但是朴素的Minimax有个致命问题搜索树呈指数膨胀。假设每层有20个候选点、搜索6层节点数就是20的6次方6400万这个量级在C里还能勉强扛但很吃力。所以必须搭配Alpha-Beta剪枝——它能在不影响最终结果的前提下把大量不可能被选中的分支剪掉实操中能把有效搜索量降低到原来的几分之一甚至让同样的时间能多下一到两层深度。这也是为什么几乎所有实战五子棋AI都选择“Minimax Alpha-Beta”这对组合而不是蒙特卡洛树搜索。MCTS在围棋上很成功但五子棋棋型结构清晰、评估函数能做到很准经典搜索反而更高效、更可控。1.3 整体架构模块划分与数据流一个清爽的五子棋AI项目通常划分成四层表示层、规则层、评估层、搜索层。表示层负责棋盘和棋子数据规则层负责走法生成、合法性校验、胜负判断评估层把棋盘局面变成分值搜索层在分值之上做博弈树搜索。数据流是单向的搜索层从规则层拿到候选走法扩展局面后调评估层打分再把局面回传给规则层做下一步走法生成。划分清晰之后你的代码可以分别测试比如单独给评估函数写单测单独验证胜负判定排查问题时会非常省力。我见过不少人把胜负判定放在搜索函数里面直接写四层循环短是短了但项目一扩展就崩。一个简单的判断标准如果某个模块以后可能被单独复用比如禁手判断、开局库、棋局回放就把它单独拎出来。五子棋AI这种规模的项目保持模块边界比追求代码量少更重要。2. 棋盘表示与落子规则一切AI的地基棋盘表示是整个AI的地基。这听起来像废话但选错了数据结构后面所有搜索和评估的性能瓶颈都会提前到来。五子棋通常用15x15棋盘常见的表示方式有三种二维数组、一维数组、紧凑位棋盘。对五子棋来说二维数组最简单一维数组在性能上更友好位棋盘则适合做非常高强度的计算。2.1 棋盘数据结构怎么设计大部分人用vectorvectorint board(15, vectorint(15, 0))0空、1黑、2白方便是方便缺点也很明显内存不连续、缓存命中率低、每次访问多一次指针间接跳转。搜索层每秒要调用几十万次棋盘状态判断时这个开销会被放大。我更推荐用一维数组比如std::arrayint, 225或者int board[225]下标pos row * 15 col。这样棋盘数据在内存中连续排布遍历和拷贝都极快搜索时做“模拟落子”只需要存一个回退值不用复制整个棋盘。实测在纯Minimax搜索中相同深度下一维数组比二维vector的实现能快出20%-30%这个差别在接近时间线时非常关键。如果要更进一步可以用一个uint64_t的位棋盘表示单色棋子分布配合预处理的位操作判断五连。但位棋盘在五子棋里收益不像国际象棋那么大因为五子棋棋盘225格超过64位必须拆成多块复杂度反而上升我建议新手先用一维数组等搜索优化到瓶颈时再考虑位玩法。2.2 胜负判定高效判断五连五连判断最简单的写法是落子后从该点出发沿四个方向水平、垂直、两条对角线检查是否连续满五个同色棋子。但要注意直接数“以落子开始往两边数”会漏掉一种情况新落子不在五连的正中间而是作为延伸的一部分所以正确做法是“从落子点向两个方向累计连续同色棋子数再判断总和是否大于等于5”。高效的实现可以写成八方向扫描先把四个方向的正反两个朝向加起来。判断时不用全盘扫描只检查落子点周围即可因为只有新落子可能改变胜负状态。代码上可以复用一套“在指定方向统计连续子”的函数bool checkWin(const vectorint board, int pos, int player) { constexpr int dirs[4][2] {{1,0},{0,1},{1,1},{1,-1}}; for (auto d : dirs) { int count 1; for (int sign -1; sign 1; sign 2) { int nr pos / 15 d[0] * sign; int nc pos % 15 d[1] * sign; while (nr 0 nr 15 nc 0 nc 15 board[nr * 15 nc] player) { count; nr d[0] * sign; nc d[1] * sign; } } if (count 5) return true; } return false; }边界处理最容易出错尤其对角线的nr和nc必须同时判断越界。很多Bug都来自只检查行越界不检查列越界。2.3 落子合法性、禁手与边界落子合法性不仅包括“该位置为空”还取决于你支持哪种规则。如果你做无禁手规则一手交换或自由开局AI的黑白策略只需要围绕棋型。如果做有禁手的标准规则黑棋还要判断三三禁、四四禁、长连禁这会让走法生成和评估函数都复杂一层。禁手判断是五子棋AI里第二大坑。它的本质不是“数棋型是否成立”而是判断“落子后是否同时形成两个及以上活三或冲四”。实现时要小心活三、冲四、活四这些棋型的定义在不同规则里有差异一旦评估层面的棋型模型和禁手判断层面不一致AI会出现“自己算出胜利却反复不下”的诡异行为。我建议要么一开始就明确做无禁手版本先把主线走通再把禁手作为增量功能加。很多AI对战平台对禁手规则要求并不严格无禁手版本的市场也同样大不必为了炫技把自己卡在第一步。3. 评估函数AI的棋感从哪来评估函数决定了AI的“眼光”好不好。搜索再深如果评估函数只盯着连子数量AI一样会走出低级棋。好的评估函数本质是对各种棋型建模给出一个相对合理的评分表然后聚合出当前局面的分值。要注意评估函数是给“某一方视角”算分的搜索层需要一个“当前轮到谁”的视角切换——最好评估函数返回一个以“当前搜索方”为正方向的分值或者返回黑方视角分再由搜索层做符号转换否则Minimax的取大取小逻辑很容易写错。3.1 棋型识别与评分体系五子棋的基础棋型就几种连五、活四、冲四、活三、眠三、活二、眠二。它们之间是递进关系连五必赢活四下一步必赢冲四对方必须挡活三是下一步能变冲四或活四的威胁。一个经典的评分表可以这样设棋型分值说明连五1000000已经获胜活四100000两头都没被堵必赢冲四10000有一头被堵对方必应活三5000两头通畅的三连眠三500只有一端能发展的三连活二500两端通畅的二连这里注意配合形状眠二50一端受阻的二连比分必须拉开量级比如连五远大于所有棋型之和。经验准则是某个棋型的分值应该在“任何组合加总”后仍然无法超过更高一级棋型。否则AI会出现“为了一堆小棋型放弃一个活三”的反智决策这种问题很难通过搜索深度弥补只能在评估函数里根治。3.2 对局反转与“空点”的评估方式评估棋盘局面有一种常见做法把黑白双方分别扫描一遍算黑方总分为bg_score白方总分为wg_score当前局面分就是black_score - white_score假设正值利于黑方。搜索时如果轮到白方走搜索层会取所有走法中“black_score - white_score”最小的一步。扫描时要注意棋型识别里最经典的新手坑是把“活三”判断成“眠三”。活三必须满足“两端延伸后都能继续形成四”的条件不能只数“三连是否被堵”。严谨的做法是对每一段连续的棋子序列数它两端的空位和控制力如果两端都是空位才算活三。还有一个更微观的坑某个落点在两端各产生一个二连它们实际共享同一个延伸点棋理上不算真正的“双活”但简单扫描器会误判成高分。这类误判会让AI出现“花式送棋”的迷惑操作。3.3 评估函数的性能与局部更新评估函数在搜索里会被调用得极其频繁百万次是常态。每次全盘扫描225个格点、还要处理多个方向开销非常大。我建议只要没到搜索的叶子节点尽量不做全盘重算而是维护一个增量式的局部影响缓存落子时只重新评估以该点为中心、半径为4的菱形区域内的棋型。因为五子棋的影响范围不会超过五连长度半径4格之外的老棋型结构完全不受影响。这样增量更新能把单次评估的开销从O(225)降到O(常数)在8层搜索下收益非常可观。一个常见的妥协方案是搜索到第N层时做精细全盘评估浅层用“点数启发方式”简化评估。说到底评估函数是个效率与精度的权衡场你不需要一开始就做到完美但要预留清晰的打分表结构和增量计算接口方便后面回头调权重。4. 搜索核心极小化极大与Alpha-Beta剪枝搜索模块是整个AI的心脏。没有搜索的AI只能算“一步棋贪心”有了搜索AI才会去“想两步、三步”也就是会考虑对手的最佳应对。这一章我会把Minimax和Alpha-Beta的关系讲透然后给出一个可以直接落地的C实现骨架。4.1 极小化极大搜索博弈树是怎么展开的极小化极大搜索的模型是树根是当前局面轮到AI走AI层取“子局面评分最大值”下一层轮到对手走对手层取“子局面评分最小值”如此交替。到了叶子节点达到限定深度或分出胜负用评估函数打分并回溯。写成递归核心逻辑很简洁int minimax(int depth, bool maximizingPlayer) { if (depth 0 || gameOver()) return evaluate(); vectorint moves generateMoves(); if (maximizingPlayer) { int best -INF; for (int move : moves) { makeMove(move); best max(best, minimax(depth - 1, false)); undoMove(move); } return best; } else { int best INF; for (int move : moves) { makeMove(move); best min(best, minimax(depth - 1, true)); undoMove(move); } return best; } }这个写法就是朴素的Minimax。它的问题在于完全没有利用“子局面的上下界排除”机会——很多分支还没算完就能断定它不可能被选择但程序依然傻傻地全算完了。对于五子棋这种每层候选点几十个、深层节点爆炸的情况必须上剪枝。4.2 Alpha-Beta剪枝把无用分支直接扔掉Alpha-Beta剪枝的核心思想是在递归过程中维护两个值alpha是当前路径上“轮到Max方至少能保证”的下界beta是“轮到Min方至多允许”的上界。当某个节点发现它已经让局面分值超出对方的接受范围时它后面所有兄弟节点都不需要再算了。在极大层如果当前分支的best已经大于等于父节点的beta则剪断。在极小层如果best已经小于等于父节点的alpha则剪断。具体代码如下int alphaBeta(int depth, int alpha, int beta, bool maximizingPlayer) { if (depth 0 || gameOver()) return evaluate(); vectorint moves generateMoves(); if (maximizingPlayer) { int best -INF; for (int move : moves) { makeMove(move); best max(best, alphaBeta(depth - 1, alpha, beta, false)); undoMove(move); alpha max(alpha, best); if (alpha beta) break; } return best; } else { int best INF; for (int move : moves) { makeMove(move); best min(best, alphaBeta(depth - 1, alpha, beta, true)); undoMove(move); beta min(beta, best); if (alpha beta) break; } return best; } }剪枝效果极度依赖走法排列顺序。如果把最好的走法排在最前面剪枝效率极高如果把烂走法排前面几乎剪不动。所以Alpha-Beta必须搭配走法启发排序否则你写出来的剪枝只会在理论上好看跑起来依旧卡成PPT。4.3 置换表与迭代加深的组合效果在Alpha-Beta基础上再进一步就是置换表Transposition Table。五子棋搜索中同一局面可能通过不同落子顺序到达比如先下A再下B和先下B再下A得到的棋盘状态完全一样。如果每次都从头搜索这是巨大的重复计算。置换表用哈希记录已经算过的局面和对应分值下次遇到相同局面直接返回存储结果典型工程实现可以用unordered_mapuint64_t, TTEntry或自定义开放式哈希表。Zobrist哈希是记录棋盘状态的标配做法对每个格子的黑白空三种状态各分配一个随机数落子时执行异或操作更新哈希值整局可以增量维护。实现不过瘾的话再叠加迭代加深——先搜1层记录最佳走法然后用这个走法作为下一层搜索的“优先走法”。迭代加深看起来很蠢每层都重复搜但它带来了三个好处一是时间可控游戏AI必须在限时内给出走法二是上一层的最佳走法可以直接作为下一层的候选排序首项显著提升剪枝效率三是浅层搜索结果可以填充置换表深层的搜索也因此受益。5. 启发式搜索与候选点生成让AI少算一半搜索速度的瓶颈不在搜索本身而在“搜索了谁”。如果你每次从225个格点里挑所有空点展开Alpha-Beta再强也救不回来。五子棋里高价值落子点高度集中在现有棋子附近所以候选点生成几乎是必需的剪枝前置步骤。5.1 候选点生成的几种常见策略最粗糙但有效的方法是只取所有已有棋子周围半径2格内的空点作为候选。原理很简单离所有棋子都很远的空点在当前局面下不可能产生立即的攻防价值。再精细一点可以给候选点打分排序统计该点周边四个方向上“这个点落下去后能形成的最强棋型是什么”按棋型强度排序。还有一种更激进的做法叫“进攻/防守双候选表”把所有能帮助当前方形成活三以上棋型的点标记为进攻候选把所有能阻止对方形成活三以上棋型的点标记为防守候选。搜索层优先展开同时具备双重属性的点因为这些点通常是真正的胜负手。这个策略对五子棋AI的水平提升特别明显能让同样的深度下棋力上涨一大截。5.2 走法排序剪枝率的天花板前面提过Alpha-Beta的剪枝效率几乎完全取决于走法排序质量。排序的核心原则是优先搜索“让当前局面迅速定性”的走法既有可能是杀棋的点也有可能是必须被防守的点。实现时可以在候选点生成阶段就利用评估函数给每个候选点算一个快速启发分然后按这个分排序。排序剪枝的实测效果差距巨大无序时同等时间只能搜4层采用启发排序后能稳搜6层。层数多了两层AI棋力表现会有一个质的飞跃。这里有个小技巧不用对每个走法都做完整评估排序可以先粗略算一个“单点铃型值”比如该点周围四方向上形成的连续子数和空位组合的粗估值排序后再交给评估函数精算。实测这种“先粗后精”的排序比全精算排序要快不少因为精算函数的常数项太高排序阶段不值得为每个点都跑一遍全棋型扫描。5.3 杀棋检测VCF/VCT的花样实现思路老手五子棋AI通常还会做杀棋搜索——VCF连续冲四取胜和VCT连续活三取胜。它们本质上是在搜索中限制走法类别只搜索冲四、活三等强制应手。这样可以在非常有限的候选点集合里展开几十步甚至上百步找到一条“迫使对手必然输掉”的路线。实现杀棋检测时可以用“强制序列”来辅助全搜索在全搜索的某个深度分支上如果检测到当前方有冲四或活三的强制棋型就把该分支强制切到杀棋搜索模块里跑几步快速判断。这样能让AI在高端局面下做出“先连冲几手再绝杀”的表演而不是四平八稳地只靠评估函数慢慢磨。杀棋搜索的意义在于它不靠评估分数而是靠“我能不能赢”的确定性判断这对五子棋AI的最终棋力提升极其关键。6. C实现的关键细节与性能调优算法懂了C工程细节没做好性能一样上不去。五子棋AI搜索是典型的计算密集型场景几个小小的数据结构决策就能让代码快几倍或者慢几倍。这一章聊我真正踩过、也真正改出效果的关键点。6.1 位运算与零拷贝性能调优中真正有效的两件事第一件事是用一维数组并尽量减少拷贝。搜索层每模拟一步棋通常只需要修改一个位置的值不需要为了保存局面拷贝整个棋盘。保存走法历史的做法是用一个moveHistory栈记录落子位置回溯时反转即可。如果一次要同时保存快照可以考虑std::arrayint,225的值拷贝但尽量别用vectorvectorint去反复拷贝。第二件事是合理使用位运算。五子棋的哈希更新直接异或Zobrist值棋型扫描里判断空位用整数比较候选点生成的遍历可以用预计算的距离数组替代实时计算。这些都是基础技巧但它们叠加起来效果巨大。我见过从“普通实现”切换到“一维数组增量哈希小对象分配池”之后同样的搜索深度耗时降到原来一半以下。6.2 走法容器与内存池别让vector反复扩容AI搜索会在瞬间生成大量走法列表。如果每个递归层都新建一个vectorint走法容器分配器会频繁申请和释放内存造成严重抖动。我建议用固定容量的std::arrayint, MAX_MOVES加上手动计数或者实现一个小型内存池在搜索开始时一次性分配好空间递归过程中复用。走法容器的大小怎么估算五子棋棋盘225格候选点半径2格内一般不会超过60个但边界和密集局面可能让你多留一点余量设成64或者128都安全。这种“小而固定”的内存策略在递归深度达8层以上时性能优势和稳定性都会体现出来。6.3 递归深度与超时控制游戏AI必须考虑时间线你不可能让对手等一分钟。常用的做法是迭代加深设置时间阈值例如每次思考限制在2秒内循环加深搜索层数每层搜索前检查时间是否超标超标就返回上一层的最佳走法。时间控制函数可以用std::chrono::steady_clock注意它是不受系统时间调整影响的时钟。另一个实用策略是“紧急剪枝”如果某层搜索时间已经超过预期可以在余下的走法排序中选择跳过部分低分走法。这是一个近似搜索的降级策略可以保证AI始终在限时内落子。我自己的实现里会设一个“危险时间点”超过它之后把候选走法裁剪到前6个实测能避免AI在残局时思考过久导致超时判负。7. 常见问题与排查技巧实录写五子棋AI最耗时间的地方不是实现而是“AI为什么要走这一步”。这一章是我自己的踩坑记录和排查思路把这些情况提前列给你你遇到的很大一部分问题其实别人都遇到过。7.1 AI死活不防守只知道进攻这是一个经典症状AI明明看到对方已经活三了还在自己造二连。回到评估函数你很可能把进攻分和防守分从同一个评分表里取了但防守分本质上应该是“对方从此点所得收益在己方视角下的负值”。如果你直接算“白方总分-黑方总分”要确保白方的防守点会被正确计为“白方在该点落子后的分数增益”。很多新手在评估时只计算“当前放谁落子的分”却忘了对防守评分做对称化处理。排查方法很简单构造一个只有“对方活三己方无关棋型”的棋盘局面把候选点按评估分排序输出看看防守点排第几。如果防守点排在末尾说明评分表权重失衡最常见是活三分值给得偏低。把活三、冲四分值再拉开一个数量级就基本好了。7.2 搜索太慢剪枝率到底怎么查剪枝率是衡量搜索效率的核心指标计算公式是“实际评估节点数 / 理论展开节点数”。你可以在递归入口加一个全局计数器跑几个固定棋局观察剪枝率。剪枝率低于60%通常意味着走法排序很差或者候选点集合太大。排查顺序是先看候选点生成是否限制了半径再看启发排序是否生效最后看Alpha-Beta的窗口有没有传错。有一个高发Bug是alpha和beta在递归回传时用错了变量导致剪枝条件永不成立搜索退化成全遍历Minimax。直接在递归入口打印alpha、beta和当前走法序号几盘棋就能定位出来。7.3 AI走法不稳定同一步棋前后不一致同局面下两次搜索给出不同走法多半不是因为AI“学到了”而是因为候选点排序不稳定或置换表没有被正确清理。如果你用过置换表一定要检查条目里的深度字段和局面哈希有没有重复使用。常见的错误是搜索深度8的结果被浅层搜索深度2的旧条目覆盖导致深层搜索读到陈旧分值。走法不稳定还有一个来源是评估函数里用了随机数作为微扰。有些AI为了增加变化性会故意加随机性但如果你期望它稳定复现同一棋步就要把随机种子固定并且把随机微扰限制在得分差距很小的走法集合内。7.4 复盘与调试一套实用的Log方案调试五子棋AI最怕黑盒。我的习惯是给搜索过程加一套“复盘日志”每层记录当前局面哈希、候选走法及其排序、alpha和beta值、最终选择走法。落子后保存完整棋局再配合一个简单的棋谱回放工具人就能直观看到AI在哪一刻开始犯傻。对单步走法分析可以用“局面-走法-评分”三元组把某一步的所有候选走法打印成表列出走法坐标、启发分、评估分。如果某个点明明是杀棋却没进入候选列表那就是候选点生成逻辑的问题如果进了列表却排在后边那就是排序或剪枝的问题如果排在前边却没被选那就是评估函数对该棋型漏算。按这个流程排查大多数AI“迷之操作”都能在半小时内定位而不是靠瞎猜。最后再分享一个个人经验五子棋AI项目最忌讳“求大求全”。先把无禁手、非开局库、固定深度3层的版本跑通再一步一步往上加启发、置换表、迭代加深每个改动都用固定棋局做回归测试。我就是这么一路踩过来的这个过程里学到的博弈搜索、C性能调试、剪枝策略迁移到其他棋类AI或者决策类程序里都完全够用。现在你再回头看“C五子棋AI”这个标题它其实是一个可以越挖越深的经典工程题目。
