无论你是想给自己的五子棋小程序加点智能还是拿它练手算法基础这篇文章都值得读完。我用了大量业余时间调过好几个版本的五子棋AI从只会乱走的随机落子到能和你打得有来有回的小高手期间踩了不少坑也积累了非常多实用经验。下面我会把C实现五子棋AI的完整思路、关键算法、具体代码和调试技巧一次性讲清楚。就算你之前没写过棋类AI只要能跟上递归搜索那段思路也可以把代码跑起来。五子棋AI的核心其实就两件事评估局面和搜索棋路。评估局面向AI展示“哪些位置对我有利、哪些位置对对手有利”搜索棋路则是让AI向前看几步找到能最大化自己优势、同时压制对方的落子。两者缺一不可只有评估函数而不会搜索AI就是个一步棋的“近视眼”只会搜索而不会评估搜索再深也分不清好局面和坏局面。1. 架构设计与数据结构选型1.1 为什么用二维数组而不是位棋盘五子棋棋盘是15×15的格子总共225个位置。因为格子少我见过很多人用类似国际象棋的位棋盘来加速也就是用一个64位整数表示一条线。但实践下来二维数组反而更直接可靠。原因有三五子棋的棋型判断连五、活四、冲四等需要频繁检查横、竖、两条斜线四个方向二维数组的坐标计算和自然语言描述完全一致不容易出错。C的二维数组访问极快225个格子遍历一次的性能损耗几乎可以忽略不计。位棋盘虽然能加速某些位运算但引入的转换逻辑和调试复杂度往往会浪费更多时间。我推荐用最朴素的定义const int BOARD_SIZE 15; enum class Piece { Empty 0, Black 1, White 2 }; Piece board[BOARD_SIZE][BOARD_SIZE];这个枚举定义很重要它让整个棋盘状态的读写都变得可读。注意不要在初始化时直接把board清零后就用很多新手容易忽略每局开始要重置建议写一个resetBoard()函数把每个格子的值赋成Piece::Empty。1.2 坐标系统与“下一手棋”的封装为了方便后续的搜索和评估我习惯封装一个moveToXY和坐标生成器。这里有一个非常关键的设计决定AI的落子位置应当生成在一个“候选列表”里而不是每次都扫全棋盘。后者的复杂度是固定的225看起来不大但如果你在Alpha-Beta剪枝的递归中频繁扫描每层搜索的常数会明显拖慢速度。候选列表的生成逻辑很简单只需扫描那些“离已有棋子2格以内”的空位。这样可以大幅缩小搜索分支数从最初的225缩小到通常几十个甚至十几个这对剪枝效率提升是决定性的。有一个细节值得提棋盘坐标走斜线是最容易出现评估错误的点。我早期版本的评估函数只计算了横向和纵向结果AI完全不会防守斜向活三被一个简单双三打死。所以坐标遍历时一定要把两种斜向左上到右下、右上到左下都算全。2. 棋型识别与评估函数设计2.1 从“零”到评估哪些棋型值钱评估函数是AI的“审美观”它决定了AI认为什么局面好、什么局面差。五子棋没有国际象棋那么复杂的子力差异核心就是看棋型连接情况。我把棋型按价值从高到低排了个表这个表是整个评估体系的基础棋型典型示例估值参考连五XXXXX1000000活四XXXX100000冲四XXX_X 或 XXXX10000活三XXX5000眠三XX_X或 X_XX_800活二XX500眠二X_X80这里每个“_”代表一个空位。要注意实际判定时并不是看见“XXX”就一定是活三得看两端是否为空。如果一端被堵死那就是眠三价值会掉一个档次。这就是棋型识别里最琐碎但最重要的部分——必须同时看两端。我建议把所有棋型判断写成独立的辅助函数比如isLiveThree、isRushFour不要全都堆在一个大函数里。这样单个函数逻辑简单后面调试也轻松。2.2 方向聚合与攻防平衡评估函数要分别对黑方和白方给出分数然后合成一个总分。常用公式是int evaluate() { int blackScore evaluateFor(Piece::Black); int whiteScore evaluateFor(Piece::White); return blackScore - whiteScore; }这样做假设AI总是“黑方”分数越高说明黑方越有利。对于白方AI你只要把落子角色换掉或者直接把公式改成whiteScore - blackScore即可。evaluateFor的实现思路是遍历所有位置对每个位置沿四个方向检测棋型。但要注意一个效率问题同样的棋型会被重复计算四次。比如一行五个黑子横向检测时会被头尾不同的起点各算一遍分数爆表。解决办法是在检测棋型时约定一个方向规则例如只有“从当前点向左/上/左上/右上方向延伸”时才开始计算避免重复计数。攻防平衡是我花了很多时间调的点AI如果只看自己怎么进攻它会漏掉对方的活三甚至冲四。所以我最终采用的方式是同时计算己方和对方的评估分数并在搜索时综合考虑。也就是说评估函数并不只返回一个绝对分数而是返回双方分数的加权差。我常用的评估代码骨架长这样int evaluateFor(Piece side) { int score 0; for (int r 0; r BOARD_SIZE; r) { for (int c 0; c BOARD_SIZE; c) { if (board[r][c] ! side) continue; // 水平方向 score evaluateLine(r, c, 0, 1, side); // 垂直方向 score evaluateLine(r, c, 1, 0, side); // 对角线方向右下 score evaluateLine(r, c, 1, 1, side); // 对角线方向右上 score evaluateLine(r, c, -1, 1, side); } } return score; }注意这里的evaluateLine内部需要防止重复统计。我个人的经验是让每个棋型在“最左上角”的那个棋子处开始计算这样一整条线只会被计入一次。比如水平方向的连续五个黑子只在最左边那个黑子触发加分成右边的四个点由于左边还有棋子不会重复统计。3. 搜索算法核心极小化极大与Alpha-Beta剪枝3.1 递归搜索框架让AI“想”好几步只靠评估函数下棋的AI很弱因为它只看了一步选个当前评估分数最高的位置然后落子。真正的对抗性搜索要用极小化极大算法AI假设自己走一步后对手会在新局面上选对他最有利的一步然后AI再回应……这样你来我往直到达到设定的搜索深度。用递归伪代码表达就是int minimax(int depth, bool isMaximizing, Piece currentTurn) { if (depth 0) return evaluate(); // 检查胜负等终止条件 if (isMaximizing) { int best -INT_MAX; for (auto move : generateCandidates()) { board[move.r][move.c] currentTurn; best max(best, minimax(depth - 1, false, opponent(currentTurn))); board[move.r][move.c] Piece::Empty; } return best; } else { int best INT_MAX; for (auto move : generateCandidates()) { board[move.r][move.c] currentTurn; best min(best, minimax(depth - 1, true, opponent(currentTurn))); board[move.r][move.c] Piece::Empty; } return best; } }这个递归极其直观但直接这么写会很慢。原因很简单每个节点都生成几十个候选每层节点数量指数级爆炸。比如深度4平均每个节点40个候选那就是40的4次方256万次评估。依然很吃力。所以必须加剪枝。3.2 Alpha-Beta剪枝的落地细节Alpha-Beta剪枝的核心思想是既然搜索树在某一层已经发现了足够好的选项那么比它更差的分支就不用继续探索了。实现的本质是给递归函数传递两个参数alpha和beta。alpha表示当前已知的对执棋者最好的选择beta表示对手能接受的最坏结果。当某一分支的返回值已经让alpha beta就可以直接剪掉不再搜索。用负极大值形式写代码会简洁得多int negamax(int depth, int alpha, int beta, Piece curPlayer) { if (depth 0) return evaluateFor(curPlayer) - evaluateFor(opponent(curPlayer)); for (auto move : generateCandidates()) { board[move.r][move.c] curPlayer; int score -negamax(depth - 1, -beta, -alpha, opponent(curPlayer)); board[move.r][move.c] Piece::Empty; if (score alpha) { alpha score; if (alpha beta) break; // 剪枝 } } return alpha; }这里的-negamax和参数交换-beta, -alpha看起来有点绕但这是最标准的写法。关键在于evaluateFor(curPlayer) - evaluateFor(opponent(curPlayer))这个公式从当前玩家的视角看分数永远是“我比对手好多少”所以轮到对手时分数取反。剪枝的效率高度依赖候选排序。如果搜索先看的是好棋那么alpha会快速变大后面的垃圾棋很快触发alpha beta剪枝效果就特别好。如果先看的是烂棋alpha一直不涨那几乎等于没剪枝。所以下面一节讲的启发式排序不是优化项而是必须项。4. 启发式排序与候选点生成4.1 缩小候选范围不要扫全棋盘我一开始犯过傻每次递归都遍历全部225个格子生成候选。15×15的棋盘看似不大但在搜索深度高时多出来的每一分都是一层分支乘数。正确做法是只生成紧邻已有棋子的空位。具体实现维护一个lastMoves列表或直接扫描棋盘找到那些“周围八格内有棋子”的空格。这个操作每层递归都要做但每次只产生很少的空位通常在10~40之间。std::vectorMove generateCandidates() { std::vectorMove cands; bool nearPiece[BOARD_SIZE][BOARD_SIZE] {false}; for (int r 0; r BOARD_SIZE; r) { for (int c 0; c BOARD_SIZE; c) { if (board[r][c] Piece::Empty) continue; for (int dr -2; dr 2; dr) { for (int dc -2; dc 2; dc) { int nr r dr, nc c dc; if (inBoard(nr, nc) board[nr][nc] Piece::Empty) nearPiece[nr][nc] true; } } } } for (int r 0; r BOARD_SIZE; r) for (int c 0; c BOARD_SIZE; c) if (nearPiece[r][c]) cands.push_back({r, c}); return cands; }这里距离选择2格而不是1格是为了捕捉跳二这类间隔棋型。代价是候选点数稍多但评估阶段能识别更多有潜力的形状综合收益是正的。4.2 排序策略先按“评估分”从高到低Alpha-Beta的剪枝效果和候选顺序强相关。最朴素的排序法是先算每个候选位置在当前局面下的临时评估分然后从高到低排序。这个排序不需太准只要大致把好棋放前面就行。实现时可以用std::sort评分用单步评估函数。int scoreMove(Move m, Piece curPlayer) { board[m.r][m.c] curPlayer; int score evaluateFor(curPlayer) - evaluateFor(opponent(curPlayer)); board[m.r][m.c] Piece::Empty; return score; }排序后递归调用std::vectorMove cands generateCandidates(); std::sort(cands.begin(), cands.end(), [](Move a, Move b) { return scoreMove(a, curPlayer) scoreMove(b, curPlayer); });实测下来这个简单的排序就能让搜索缩小好几倍耗时推荐优先实现。等基础版本跑通后你可以进阶使用杀手启发——记录每层剪枝时导致剪枝的那手棋在下一次搜索同一深度时优先尝试它。这个技巧能显著提升深层的剪枝率代码量也不大。另外要注意搜索过程中你会在board上反复做临时落子和撤销。为了让排序评分不影响后续搜索状态每次scoreMove里落完子后必须立即恢复这虽然频繁但代价很小。5. 代码实现与调优经验5.1 完整搜索与主循环实现我这里的核心搜索函数采用“迭代加深”的办法而不是一次性固定深度。迭代加深的意思是先搜索深度1得出最佳着法再搜索深度2再得出更佳着法……直到到达时间限制或最大深度。好处是每个时间片段都有一个可用的结果不会因为某次搜索过深导致卡死。主循环参考这段int maxDepth 6; // 可以按需调整 Move bestMove; for (int d 1; d maxDepth; d) { int alpha -INT_MAX, beta INT_MAX; int bestScore -INT_MAX; std::vectorMove cands generateCandidates(); sortCandidates(cands); for (auto m : cands) { board[m.r][m.c] curPlayer; int score -negamax(d - 1, -beta, -alpha, opponent(curPlayer)); board[m.r][m.c] Piece::Empty; if (score bestScore) { bestScore score; bestMove m; } if (bestScore alpha) alpha bestScore; } }这段代码里有个细节bestMove每层都会更新但只有更深层的搜索结果才会作为最后返回值。这意味着如果你时间紧可以在某层搜索未完成时强制终止也会有一个相对不错的着法。我用实际测试告诉你不同深度的效果差异搜索深度1~2的AI基本是新手水平深度4能挡住大部分简单陷阱但会漏掉长线双活三深度6已经能轻松打赢普通娱乐玩家深度8则几乎不会犯低级错误开局和中盘表现接近强手。普通机器跑深度6已经满足绝大多数对局需求再往上升级主要是优化剪枝和评估速度。5.2 胜负判断的边界处理在negamax中如果你只依赖depth0作为终止条件会有个大问题棋盘上明明已经出现连五搜索还会继续往下算。正确做法是在进入递归前先检查当前落子是否能和已有棋子形成连五。一旦检测到连五就返回一个极大值或极小值提前结束该分支。bool checkWin(int r, int c, Piece player) { int dirs[4][2] {{0,1},{1,0},{1,1},{1,-1}}; for (auto dir : dirs) { int cnt 1; for (int k 1; ; k) { // 正方向 int nr r dir[0]*k, nc c dir[1]*k; if (!inBoard(nr, nc) || board[nr][nc] ! player) break; cnt; } for (int k 1; ; k) { // 反方向 int nr r - dir[0]*k, nc c - dir[1]*k; if (!inBoard(nr, nc) || board[nr][nc] ! player) break; cnt; } if (cnt 5) return true; } return false; }注意这个函数里的双循环我故意没有把正方向和反方向合并因为合并容易在坐标加减上出错。反方向用减号正方向用加号分开写逻辑更清楚。在搜索函数里落子后应立刻检查if (checkWin(move.r, move.c, curPlayer)) { board[move.r][move.c] Piece::Empty; return WIN_SCORE - depth; // 深度越浅获胜越好 }WIN_SCORE - depth是为了让AI在保证赢的前提下尽量赢得更快而不是绕一大圈赢这样棋风更自然。5.3 评估函数权重调参的独家经验评估权重的选择是整个AI效果的分水岭。网上很多代码直接把连五、活四、冲四等分数写成一成不变的大数但实战中你会发现它会非常“贪杀”明明该防守时却跑去进攻。我在调参时总结出了几个原则防守分和进攻分不能相等通常进攻分要略高于防守分但要控制比例。我最终用的比例大约是1.1~1.2倍进攻优势太大会导致见死不救。活三和冲四的分数差不要拉得太大。如果活三分是5000冲四分是50000AI会一直想冲四而忽略活三导致错过更隐蔽的连续进攻。评估函数里禁止负分叠加过多。很多实现会陷入“把所有眠二累加”导致的虚高我建议大量压缩低价值棋型的权重宁可不加分也不要让它们干扰高价值棋型的判断。我的主力权重表长这样棋型进攻权重防守权重连五10000001000000活四100000120000冲四2000025000活三80007000眠三15001800活二600400眠二100120注意活四防守权重高于进攻权重是因为当对手出现活四时AI必须优先应对而不是自己进攻但连五出现时输赢已定两者都是满分。每次改动权重表后我都建议跑大量对局验证不要只看几个典型局面。6. 常见问题与调试心得6.1 AI在优势局面下乱走这个问题十有八九出在评估函数的单向性。如果你只计算了AI自己棋型的分数AI就会觉得自己赢定了然后到处进攻却完全无视对手已经准备形成的连五。修复方法就是上一节说的评估函数必须同时计算双方分数并做差。当你看到AI明明领先却还在乱走优先检查它是否“看不到”对手的好棋。6.2 剪枝导致漏掉必胜手Alpha-Beta剪枝在正确实现下是不会漏掉最优解的但如果你把剪枝条件写错位置就会出问题。我踩过的一个典型错误是在排序后的候选循环里先更新bestScore再更新alpha但剪枝判断却用了旧的alpha值导致某个分支被误剪。正确写法是每算完一着都更新alpha再判断alpha beta。更隐蔽的一个坑是负极大值形式中评估函数的正负号必须一致。我调试时发现AI的同一手棋在不同深度结果完全不同后来定位到是评估函数在返回时说成“当前玩家优势”但递归时没有正确取反导致搜索树评估方向混乱。6.3 速度慢得离谱如果深度4就已经卡顿先检查两个地方候选点是否真的限定在棋子附近评估函数里是否做了重复扫描。我见过一个现场是从全棋盘每个点出发沿四个方向做棋型扫描然后每步都要遍历一遍225个点算下来每层就是900次扫描速度当然上不去。90%的速度问题都能靠“缩小候选排序剪枝”解决。剩下10%可以考虑用置换表缓存相同局面的评估结果。不过在五子棋里棋盘状态切换非常频繁置换表的命中率通常不像国际象棋那样高所以我个人认为基础玩家可以先不做。6.4 调试技巧用日志树而不是猜我调试搜索函数时最常用的办法是打印搜索树。在递归函数开头输出当前深度、坐标、alpha、beta和落子玩家然后手动验证某一步的分数是否合理。一开始觉得打印太多看不过来后来发现只需在可疑深度比如深度1、2打印就有奇效。另一个技巧是写一个简单的局面回放工具把AI认为的最佳路线按落子顺序展示在控制台棋盘上这样你能直观看到AI眼中的“进攻路线”和“防守路线”。当AI棋路很蠢时你往往能一眼看出它漏了什么形状。6.5 从命令行到图形界面的扩展许多开发者包括我早期都只做控制台版本黑底白字跑一步打印一行。如果你后续想接图形界面核心搜索代码完全不用改只需要把用户输入从键盘读取换成鼠标点击坐标映射把棋盘渲染换成任意画框库。数据格式保持(row, col)即可。我给一个扩展建议把当前AI的棋力、搜索深度、耗时统计用简单的文本面板展示出来。这在你调参时极有价值因为你能直观看到深度增加带来耗时爆炸或者某些权重设置导致AI突然变莽。最后的个人体会按这套方案我从零写出的第一个能正常对局的五子棋AI大概花了两天时间。现在回头想最大的瓶颈不是算法本身而是评估函数里那些无声的权重选择。你可能会花好几个晚上反复调权重只为了让AI不再“莫名其妙送死”。我想劝你一句先别追求一步到位的完美AI先把最小可用版本跑起来。哪怕AI第一步只会下在棋盘正中央第二步只会在周围随机落子只要它能完成“评估搜索落子”的循环后面所有优化都有落脚点。后续可以再从杀手的优化、局面的预剪枝、甚至简单的开局库开始慢慢把AI变强。调试中最大的快乐其实不是AI赢了而是你亲眼看着一个只会傻下中心的程序逐渐能和你纠缠、反击、设陷阱。等它终于能连续做几个活三逼你防守时你会觉得那些反复修改权重的夜晚全都值了。