简介：一份以纯C语言实现的Renju规则五子棋AI程序包，主要面向对博弈树搜索和棋类AI感兴趣的开发者、算法学习者及竞赛选手，可帮助读者解决五子棋AI的走棋决策、搜索效率与规则适配等实际问题。程序将Minimax、启发式评估、Alpha-Beta剪枝、预评估、迭代加深、VCT/VCF、PVS、杀手启发式搜索等多种经典算法整合在一起，并给出动态多线程处理思路，便于对照代码理解各算法在真实对弈中的分工与衔接，也能直接作为二次开发或继续优化的基础。压缩包体积很小，仅11KB，共3个文件，全部为C源代码，分别提供Linux普通版、Linux竞赛版与Windows版，既能覆盖不同运行环境，也方便对比差异、学习跨平台代码的组织方式。目前已有466人学习浏览，适合想掌握棋类AI核心搜索策略或准备相关算法比赛的读者。通过研读这三份源码，可以快速理清Renju规则下从局面评估到搜索剪枝再到落子输出的完整实现链路，并对算法调优与工程化简有更具体的认识。
1. 这个C语言Renju规则五子棋AI，到底能给你什么
五子棋AI大家都见过，但加上Renju禁手之后，连棋盘的胜负判断都得重写。这篇笔记要拆的就是一个用C语言写的Renju规则五子棋AI，它既能下棋，也能判断黑棋的三三、四四和长连。这个项目最难的地方不是搜索算法，而是让黑棋AI在禁手约束下不犯浑。它解决的核心问题有两个：一是15x15棋盘上的胜负判定怎么写得又快又稳，二是黑棋的禁手检测怎么精确到不误判。适合想给棋类程序加AI的开发者，或者想从零看一次C语言实现搜索算法的人。
2. 从棋盘表示开始：15x15数组加上哨兵边界
2.1 棋盘数据结构与落子流程
在C语言里表示棋盘最直接的做法就是二维数组。用0表示空，1表示黑棋，2表示白棋。15x15刚好是Renju的标准棋盘尺寸。我习惯在数组两边各多开两格当边界缓冲，这样后面做方向扫描的时候就不用每次判断下角标是否越界。
#define BOARD_SIZE 15 #define PADDING 2 #define CELL (BOARD_SIZE + PADDING * 2) int board[CELL][CELL]; // 实际用行列 2..16 存棋 void init_board() { for (int i = 0; i < CELL; ++i) for (int j = 0; j < CELL; ++j) board[i][j] = 0; } // 落子：1黑2白，成功返回1，失败返回0 int put_piece(int r, int c, int player) { if (r < 0 || r >= BOARD_SIZE || c < 0 || c >= BOARD_SIZE) return 0; int rr = r + PADDING, cc = c + PADDING; if (board[rr][cc] != 0) return 0; board[rr][cc] = player; return 1; }这个写法和你平时见到的直接开15x15的区别在于：棋盘坐标从0到14，但实际存储的索引从2到16。这样做之后，后面在胜负判定和禁手检测里，用固定方向向量遍历时，即使从边界棋子出发，访问的也是哨兵位置而不是数组越界。哨兵位不是有效的棋子，所以扫描的时候把它们当作挡墙就行。
为什么要用二维数组而不是把棋盘压成一维长度为225的数组？因为数组的索引运算更直观，而且后面写禁手检测时，需要频繁访问某个方向的邻格，二维表达board[r+dr][c+dc]比board[(r+dr)*COL + (c+dc)]容易读。C语言的二维数组在内存里本来就是连续的，性能没损失，这点不用纠结。
棋盘点位转换是另一个细节。命令行程序里用户通常输入类似“A1”“H8”这样的坐标。我在资源包里写了一个专门的转换函数：
int parse_coord(const char *s, int *r, int *c) { if (!s || !s[0] || !s[1]) return 0; int col = s[0] - 'A'; if (col < 0 || col > 14) col = s[0] - 'a'; if (col < 0 || col > 14) return 0; int row = atoi(s + 1) - 1; if (row < 0 || row >= 15) return 0; *r = row; *c = col; return 1; }注意：这一步很容易踩坑，因为用户可能输入小写“a1”，也可能输入带空格的“a 1”。我的做法是先把字符串去空格，再统一转大写或直接做两次判断。具体怎么写不重要，重要的是你必须明确：存储坐标（算法内部）和用户坐标（显示层面）是两个体系，不要混着用。
2.2 五子连珠判定：方向向量与四种扫描
胜负判定的本质是：以每个位置为起点，沿着水平、垂直、左右对角四个方向，找连续同色棋子的长度。这里有一个容易漏的细节：你必须检查正向和反向，比如从（r,c）出发向右数，同时也要向左数，加起来才是这条线的连子数。
我一般用四个方向向量：dir[4][2] = {{0,1},{1,0},{1,1},{1,-1}}。对于每个点，沿每个方向正走4步加负走4步，统计同色数，若达到5就赢。
int dirs[4][2] = {{0,1},{1,0},{1,1},{1,-1}}; int count_dir(int r, int c, int dr, int dc, int player) { int rr = r + dr, cc = c + dc, cnt = 0; while (board[rr][cc] == player) { cnt++; rr += dr; cc += dc; } return cnt; } int check_win(int r, int c, int player) { for (int i = 0; i < 4; ++i) { int dr = dirs[i][0], dc = dirs[i][1]; int total = 1 + count_dir(r,c,dr,dc,player) + count_dir(r,c,-dr,-dc,player); if (total >= 5) return 1; } return 0; }注意，这里我没有加越界检查，因为前面开了哨兵位，而且哨兵位初始化为0，不会等于player，循环自然终止。如果不用哨兵，你就得写出类似“cc + dc >= 0 && cc + dc < BOARD_SIZE”的判断，一旦写错就是数组越界崩溃。这也是后面我要讲的第一个坑。
在AI代码里，check_win的调用非常频繁。每模拟一步棋都要判断一次，如果每次都遍历全盘15x15，搜索深度6、候选点几十个，虽然也行，但白白浪费。更常用的做法是只检查刚落下的那一子：
int check_win_around(int r, int c, int player) { for (int i = 0; i < 4; ++i) { int dr = dirs[i][0], dc = dirs[i][1]; int total = 1 + count_dir(r,c,dr,dc,player) + count_dir(r,c,-dr,-dc,player); if (total >= 5) return 1; } return 0; }它和check_win的差别仅仅在于入参是落子点而不是整个棋盘，但足以把单步判断的耗时节减到原来的1/15。这个优化在C语言版AI里非常关键，因为后面我们还要叠加禁手检测，多一次全盘扫描就多一层负担。
这里还有一个我踩过的认知上的小坑：很多人觉得“连五就赢，长连也算赢”，但在Renju规则里，黑棋长连是算输的。所以check_win_around在给黑棋用的时候，返回值只能表示“连成了五子以上”，是否胜利必须再走一套禁手判定。简单说就是：白棋只要total >= 5就赢，黑棋必须total == 5且没有禁手才能赢。这个逻辑我在第4章会详细说。
我见过不少人第一次写count_dir，把dr和dc写反，导致只能检测横竖方向，斜线永远赢不了。排查方法很简单：找一个线下测试，在棋盘上斜着摆五颗子，调用check_win_around，看是否返回1。如果这个用例不过，优先检查方向列表的第四个元素是不是{1,-1}，很多人写成{-1,1}，在二维数组里这两种写法指向不同的方向，一个是从左上到右下，另一个是从右上到左下。
3. 评估函数与搜索：让AI从“会下”到“会算”
3.1 评估函数：给每个棋形打分
评估函数是棋类AI的灵魂。一个直白的做法是：扫描棋盘的每一行、每一列、每个对角线，把连续的棋子序列切出来，然后根据棋形给分数。比如活四接近必胜给100000，冲四给10000，活三给5000等。
int eval_point(int r, int c, int player) { int score = 0; for (int i = 0; i < 4; ++i) { int dr = dirs[i][0], dc = dirs[i][1]; int cnt = 1; int open_end = 0; // 正向数 int rr = r + dr, cc = c + dc; while (board[rr][cc] == player) { cnt++; rr += dr; cc += dc; } if (board[rr][cc] == 0) open_end++; // 反向数 rr = r - dr; cc = c - dc; while (board[rr][cc] == player) { cnt++; rr -= dr; cc -= dc; } if (board[rr][cc] == 0) open_end++; if (cnt >= 5) score += 1000000; else if (cnt == 4 && open_end == 2) score += 100000; else if (cnt == 4 && open_end == 1) score += 10000; else if (cnt == 3 && open_end == 2) score += 5000; else if (cnt == 3 && open_end == 1) score += 1000; else if (cnt == 2 && open_end == 2) score += 500; else if (cnt == 2 && open_end == 1) score += 100; } return score; }这个eval_point只是把单个方向的分值累加，还没有考虑禁手和全局配合。实际项目里，评估函数还会区分“我方棋形”和“对方棋形”，最终分数是己方总分的权重乘以一个系数减去对方总分。我常见做法是：评估时把自己下在某个位置后的局面分数，和对手下在同一个位置后的局面分数分别算，差作为这个点的价值。
注意，这个函数在AI搜索里是静态评估的基础。你可以在深度为0的时候调用，也可以在搜索内部用来排序着法，让alpha-beta剪枝更高效。在Renju规则下，黑棋的评估函数还要额外加一层判断：如果某个点对黑棋是禁手，它的分数应该直接置为负无穷，不管形状多漂亮。
3.2 极小化极大搜索：Alpha-Beta怎么剪
有了评估函数，AI就能对局面打分。但真正让它“会算”的是搜索。极小化极大搜索是棋类AI的标配：轮到AI走棋时，AI选择得分最高的着法；轮到对手走棋时，对手会选得分最低的着法（因为对AI来说，对手的收益就是AI的损失）。
int alphabeta(int depth, int alpha, int beta, int player, int last_r, int last_c) { if (depth == 0) return evaluate_board(); // 检查胜负 if (last_r >= 0 && check_win_around(last_r, last_c, !player)) return player == AI_PLAYER ? -2000000 + depth : 2000000 - depth; generate_moves(moves_r, moves_c, &count); for (int i = 0; i < count; ++i) { int r = moves_r[i], c = moves_c[i]; put_piece(r, c, player); int score = -alphabeta(depth - 1, -beta, -alpha, !player, r, c); remove_piece(r, c); if (score >= beta) return score; if (score > alpha) alpha = score; } return alpha; }这段代码里的generate_moves是关键。常见做法不是扫描所有空点，而是只扫描有棋子周围两格以内的空点。这样候选点通常只有三五十个，而不是225个。这个范围叫“候选生成半径”。
Alpha-Beta剪枝的核心是：如果某个着法已经导致score >= beta，那么对手一定不会选择这个分支，直接剪掉。参数alpha和beta的初始值通常是负无穷和正无穷。注意这里使用-alphabeta的技巧，省去了每层判断min/max的麻烦。
生成着法的实现：
void generate_moves(int *moves_r, int *moves_c, int *count) { *count = 0; for (int r = 0; r < BOARD_SIZE; ++r) for (int c = 0; c < BOARD_SIZE; ++c) { if (board[r+PADDING][c+PADDING] == 0 && has_neighbor(r,c)) moves_r[(*count)] = r, moves_c[(*count)++] = c; } }has_neighbor就是检查以(r,c)为中心的5x5区域内是否存在棋子。这里用5x5而不是2格，是因为有些棋形需要隔一步才有威胁，比如“跳三”里的跳跃空位。如果只查旁边一圈，会漏掉一些关键的延伸。
搜索深度怎么选？我一般默认4，快速模式2，难缠模式6。因为是C语言，6层的alpha-beta搜索在一台普通机器上通常能在1秒内结束；但如果评估函数太复杂，就可能卡顿。所以要配合时间限制和迭代加深，这个我放到第6章讲。
搜索顺序也很重要。如果候选点按照“离最后落子近的先搜索”，剪枝效率会大幅提升。另一个技巧是把评估值排序，先走分数高的着法。我自己写AI的时候，会在生成着法后先调用eval_point对每个候选点打分，然后按分数降序排序。这个排序虽然增加了一点开销，但能让alpha-beta剪枝更早遇到好棋，整体提速非常明显。
4. Renju禁手检测：黑棋的三三、四四和长连怎么判
4.1 三三禁手：两个活三同时出现才算
Renju规则里，黑棋禁手有三三、四四和长连。最常见的误判就是三三。什么叫“活三”？简单说，落子后形成三连，并且两端都未被封堵，下一步可以变成活四的三个子。如果一端被封堵，那是“眠三”，不算。
检测三三禁手的方法是：模拟黑棋落在某个空点上，然后检查这个点形成的所有方向上，有多少个“活三”。如果同时在两个或两个以上的方向上形成了活三，就是三三禁手。要注意，四个方向上同一个活三如果共用中间点，比如十字形的三三，也算禁手。
我一般写一个is_open_three函数，判断某个方向上是否为活三。逻辑是：从落子点出发，向正反方向统计连续黑子数，并记录两端是否为空。活三的判断条件有多种，通常需要分析棋形结构，比如“三连加两个端空位”和“有一端隔一个空位还有子”。为了避免误判，我见过最稳妥的方法是枚举这个方向上所有可能的“三”形状，然后检查是否能形成活四。
这里给一个简化版的核心逻辑：
int is_open_three(int r, int c, int dr, int dc, int player) { // 假设当前已经落下一子，判断该方向上是否形成活三 // 先统计以(r,c)为中心的正反连续子数 int cnt = 1, safe = 0; // safe表示端空数量 for (int sign = -1; sign <= 1; sign += 2) { int rr = r + dr * sign, cc = c + dc * sign; while (board[rr][cc] == player) { cnt++; rr += dr * sign; cc += dc * sign; } // 如果下一格是空位，并且再下一格在棋盘内或者是空位，算一个开放端 if (board[rr][cc] == 0) { int rr2 = rr + dr * sign, cc2 = cc + dc * sign; if (rr2 >= 2 && rr2 < 16 && cc2 >= 2 && cc2 < 16 && board[rr2][cc2] == 0) safe++; } } return (cnt == 3 && safe == 2); }注意这里的rr2判断必须限定在棋盘真实范围内，因为哨兵位虽然为0，但不能当空位计算。这是最容易出错的地方。你想想，如果边界外被当成空位，那所有靠边的三都成了活三，三三禁手就会泛滥。
提示：三三禁手的检测必须在“落子后”进行。从空盘角度去数永远数不出正确结果，因为禁手判断是基于这一步棋后的形状。
4.2 四四禁手与长连：先走四再判断
四四禁手指的是黑棋在一步落子后同时形成两个“四”。这里的“四”包括活四和冲四，国际规则中双四禁手里的“四”指的是所有能连成五的四，所以冲四也算。检测方法类似：看四个方向上是否有两个或以上方向的“四”形状。
长连禁手就是同一方向出现6个或以上黑子。检测很简单，在check_win里如果玩家是黑棋，连子数>=6则算禁手，不算胜利。
实际编码时，禁手检测往往和AI搜索紧密结合。因为黑棋的AI有禁手，它在搜索时不能选择禁手点，否则直接判负。所以搜索生成着法时，如果玩家是黑棋，要先调用is_forbidden判断该点是否为禁手，是则跳过。白棋没有禁手，可以直接下。
int is_forbidden(int r, int c) { // 先落子模拟 board[r+PADDING][c+PADDING] = BLACK; int long_connect = 0, four_count = 0, three_count = 0; for (int i = 0; i < 4; ++i) { int cnt = count_line(r, c, dirs[i][0], dirs[i][1], BLACK); if (cnt >= 6) long_connect = 1; if (is_four(r, c, dirs[i][0], dirs[i][1], BLACK)) four_count++; if (is_open_three(r, c, dirs[i][0], dirs[i][1], BLACK)) three_count++; } board[r+PADDING][c+PADDING] = EMPTY; if (long_connect) return 1; if (four_count >= 2) return 1; if (three_count >= 2) return 1; return 0; }注意，在模拟禁手时，必须在临时棋盘上操作，不要污染真实局面。我的办法是直接落子再悔棋，因为落子和悔棋都很快。但如果搜索里有很多禁手判断，可以用一份临时棋盘拷贝。
这里要提一个细节：三三和四四的判定不能用同一个is_open_three函数去检测四，因为“四”可以是被封一头的冲四，而“三”必须是开放三。四四禁手要求两个四，但冲四也算四，所以即使一个被堵住的四和一个活四同时出现，也判禁手。长连则必须达到6，五连是不算禁手的。
“四”的检测相对简单：统计连续4子且两端至少有一端是空位即可。活四两端都空，冲四一端空，两者都算一个“四”。
如果你拿到的是一份不带禁手检测的五子棋AI，把它改成Renju规则，工作主要就落在这一章。我通常的步骤是先写一个rule_test.c，手工摆出三三、四四、长连的棋形，验证检测函数的输出，再接入AI搜索。比如三三禁手测试棋形：黑棋在(7,7)处，左右两边各有一个活三点，落子(7,7)后应返回禁手。
5. 避坑指南：五子棋AI的四个经典翻车现场
5.1 棋盘越界：哨兵位不是万能的
现象：程序下到棋盘边缘时，经常随机崩溃，或者出现“负坐标”的恶心错误。
原因：虽然加了哨兵，但你在count_dir里用的是整个CELL大小，没有限制哨兵位不能落子。如果落子函数没有正确映射坐标，可能把棋子放到哨兵位置，导致扫描死循环。另一个常见原因是在解析用户输入时，没做范围检查，直接用了越界坐标。
解决：落子前严格检查0 <= r < 15 && 0 <= c < 15，并且哨兵位永远设为0，不要给哨兵位赋值。另外在count_dir里可以加一个abs(rr-r) <= 5的防御性判断，防止循环意外跑远。
5.2 禁手误判：把眠三当活三
现象：AI在黑棋时明明可以轻松取胜，却总是避开某些点位，甚至走出弱手。后来发现它把那些点位判成三三禁手了。
原因：is_open_three里没有正确识别“一端被自己的棋子堵住后，另一端的空位”。比如两颗黑棋一端是空，另一端也是空，但紧挨着白色棋子，这三连并不能形成活四，因为被白子隔断了。很多人写活三判断时只数连续三子，却忘了检查两端延伸出去是否还能落子。
解决：在判断空位时，不仅要看当前相邻格是否为空，还要看再下一格是否棋盘内且为空。只有两端都能延展开，才叫活三。这个我建议用单元测试用例覆盖，比如在棋盘上手动摆出“假活三”进行验证。
5.3 搜索超时：深度一涨，响应秒停
现象：AI思考时间从0.5秒变成5秒，甚至卡死不落子。
原因：搜索深度从4调到6之后，若没有剪枝或者剪枝不充分，状态数增长上百倍。另外，候选生成范围太大，把所有空点都放进去了。我在调试时打过日志，发现6层搜索展开了几十万个节点。
解决：限制最大搜索深度，并把候选点限制在有棋子周围2格内。还有一个关键：在递归函数里每层都检查当前耗时，超过预设时间立刻返回当前最好分数。这个技巧在比赛里很常用，我一般会用clock()函数记录每次搜索的开始时间，在每层递归开头判断是否超时。
5.4 评估函数“近视”：贪吃眼前冲四，漏掉后续连杀
现象：AI会为了一个冲四的分数去走棋，结果被对手反手一个活三直接带走。
原因：评估函数给冲四的分数太高，搜索深度不够，看不到后续的威胁。还有一个原因是排序逻辑不对，alpha-beta剪枝时总是先搜索最差的着法，导致剪枝率低。
解决：降低冲四的静态分数，让搜索更依赖深度而非贪心；同时对对手的威胁进行惩罚，比如对手形成活三时，AI的分数要减去一个大值。这个调参没有标准答案，我一般用自对弈来对比不同参数获胜率。另外，把评估函数的对手视角纳入计算，也就是评估当前局面时，必须同时算一遍己方和对方的最佳棋形，然后求差，而不是只算自己。
6. 进阶调优：迭代加深、置换表与开局库
迭代加深是让AI在时间限制内最大化深度。简单说，先搜索深度1，记录最佳着法；然后深度2，再深度3，直到时间用完。因为深度高的搜索会利用前面深度的着法排序，效率通常不差。我一般把限制时间设为1秒，在每层搜索前检查一下总耗时，超时就返回上一层的最佳着法。
置换表就是哈希缓存：把棋盘状态用Zobrist哈希压缩成一个64位整数，存下这个局面在之前搜索中的评估值和最佳着法。下次遇到相同局面，直接拿结果，避免重复搜索。C语言实现置换表要小心碰撞，我一般开一个八百万项的哈希表，用线性探测。注意，当深度、alpha或beta不同时，置换表里存的评估值不一定直接可用，通常需要存下当时的搜索深度，只使用相同深度或更深的条目。
开局库也很实用。五子棋的开局变化并不多，尤其是前三手的固定套路。把常见开局的前5步存成一个二维数组，AI在开局阶段直接从库里取，省掉搜索。我在资源包里也带了十几行常见开局表，但我觉得真正需要的是自己整理一套适合你AI风格的开局库。比如你的AI偏防守，就多存一些稳健的开局；如果你只想让黑棋AI不落下风，那开局库至少要覆盖黑棋最常见的几种应对。
验证AI有没有变强，我一般会写一个自对弈脚本：让两个不同参数的AI互下100局，统计黑棋胜率和白棋胜率。注意Renju规则下黑棋有禁手，统计时要把黑棋禁手导致的负计入白胜。我吃过亏，因为黑棋胜率过高时，我以为是AI变强了，实际是规则没生效。从那以后，我每次改完评估函数或搜索逻辑，都强制跑一遍自对弈，至少50局，确认没有异常。这个习惯帮我避开过很多隐蔽回归。希望帮到你。
本文还有配套的精品资源，点击获取
