简介一套采用 C 语言实现的 Renju 规则五子棋 AI 源码面向对博弈树搜索与棋类 AI 感兴趣的中高级 C 开发者。代码整合了 Minimax、启发式评估、Alpha-Beta 剪枝、预评估、迭代加深、VCT/VCF、PVS、杀手启发式及动态多线程等策略在传统五子棋基础上加入 Renju 禁手规则兼具算法复杂度与实战价值。压缩包仅有 3 个 C 源文件体积约 11KB分别面向 Linux、Linux 竞赛场景与 Windows 平台便于跨平台对比、测试与移植改造。目前已有 466 人学习下载适合用于算法课程设计、竞赛准备或作为棋类 AI 入门进阶的参考。通过阅读源码可直观理解多层搜索优化如何协同工作掌握博弈树剪枝、启发式评估与迭代加深的工程实现细节同时还能学习如何为不同运行环境维护多版本代码以及如何在搜索过程中引入动态多线程策略对深入掌握棋类 AI 开发极有帮助。1. Renju规则五子棋AI连五就能赢的棋偏偏黑方被绑了手脚自己写完第一个五子棋 AI 时觉得连五就胜规则简单到可以用一张 15×15 的二维数组装下全部逻辑。直到把棋规换成 Renju连珠才发现真正的门槛不在搜索而在禁手同样是黑方走出双活三普通五子棋直接获胜Renju 里这手不但无效还要判负。白方没有禁手黑方却有双活三、双四、长连三条红线AI 的每一步落子都得先过了禁手判定这一关才有资格谈胜负。这篇笔记从「C语言 Renju规则 五子棋AI」三个词各自的技术分量展开先用代码实现禁手判定再把它嵌入 Alpha-Beta 搜索与评估函数最后落到那些让新手翻车、让老手头疼的边界情况。适合已经写过基础五子棋 AI、想往正规连珠规则靠拢的开发者也适合准备拿这个方向做课程设计或开源项目的朋友照着复现。2. 先把规则钉死Renju 禁手判定的数据模型2.1 黑方三条禁手红线双活三、双四、长连Renju 规则里黑方被限制根本原因是黑棋先行天然多一手优势禁手是在给先手方找平衡。具体到判定逻辑黑方在落子后形成的棋形中只要命中下面任意一条这手棋就是禁手禁手类型定义判定特征长连同方向连续黑子数 ≥ 6从落子点四方向延展统计双四同时形成两个或以上的四连含活四、冲四统计四连棋形数量双活三同时形成两个或以上的活三统计活三棋形数量有个容易被忽略的前提黑方落子后如果形成了五连那这手棋直接判胜不再进入禁手判断。代码里必须把五连检测放在禁手检测之前否则会出现「黑方六连被当作长连禁手」的尴尬误判。白方则完全不受禁手限制任何方向连成五子即白胜。2.2 用 C 语言实现禁手判定方向扫描与棋形计数棋盘用int board[15][15]0 表示空、1 表示黑、2 表示白。禁手判定的核心思路是先把黑子临时放到拟落子点然后沿横、竖、两个斜向四个方向分别扫描统计每个方向上形成的连续棋段最后汇总成禁手结论。#define BOARD_SIZE 15 #define EMPTY 0 #define BLACK 1 #define WHITE 2 // dr[4], dc[4] 对应横、竖、主对角线、副对角线 static const int dr[4] {0, 1, 1, -1}; static const int dc[4] {1, 0, 1, 1}; typedef struct { int black_five; // 是否形成五连 int four_count; // 四连棋形数量含冲四与活四 int live_three_count; // 活三棋形数量 } ShapeCount; // 判断 (row, col) 是否为黑方禁手 int is_forbidden(int board[BOARD_SIZE][BOARD_SIZE], int row, int col) { int i; ShapeCount sc; memset(sc, 0, sizeof(sc)); board[row][col] BLACK; // 临时落子 count_shapes(board, row, col, sc); // 对落子点做四边形扫描 board[row][col] EMPTY; // 恢复棋盘 if (sc.black_five) return 0; // 有五连直接胜不算禁手 if (sc.four_count 2) return 1; // 双四禁手 if (sc.live_three_count 2) return 1; // 双活三禁手 return 0; }这里count_shapes以落子点为中心沿四个方向做完整扫描统计落在同一条直线上的连续黑子段。参数说明row、col是拟落子的坐标board传入的是当前局面副本的指针函数内部对禁手判断使用的是「落子后局面」而非「落子前局面」这是禁手判定的关键差异——只有新形成的棋形才算数。2.3 棋形统计的边界细节活三与冲四的严格区分活三和冲四的定义直接决定判定结果。一个方向上的连续黑子段如果两端都有空位才是活三或活四如果只有一端通头另一端被白子或边界堵住就叫眠三或冲四。具体实现时每个方向的扫描结果要能区分「段长」和「两端空位情况」。typedef struct { int length; // 连续同色棋子长度 int open_ends; // 两端空位数量0/1/2 } LineSegment; // 沿 dir 方向扫描以 (r, c) 为中心的连续黑子段 static LineSegment scan_segment(int board[BOARD_SIZE][BOARD_SIZE], int r, int c, int dr, int dc) { LineSegment seg {0, 0}; int i; // 正方向数棋子 for (i 1; r i * dr BOARD_SIZE c i * dc BOARD_SIZE; i) { if (board[r i * dr][c i * dc] BLACK) seg.length; else break; } // 反方向数棋子 for (i 1; r - i * dr 0 c - i * dc 0; i) { if (board[r - i * dr][c - i * dc] BLACK) seg.length; else break; } // 计入落子点自身 seg.length 1; // 检查两端通头情况 if (r seg.length * dr ??? ) // 需要精确计算两端坐标 ... }完整实现还需要计算首尾两端的具体坐标来检测通头。我这里给出手写思路实际编码时用一个辅助坐标数组记录正方向、反方向各自延伸到的位置再判断边界外一格是空还是被占。open_ends是后面评估函数的核心输入禁手判定里把它映射为两端口 长度 3–4 的段归为活三/活四一端口 长度 4 归为冲四。3. 决策引擎把 Alpha-Beta 搜索和评估函数焊在一起3.1 极小化极大搜索让 AI 既当攻方又当守方五子棋是零和博弈黑方目标 max 自己棋型的价值白方目标 min 对方的棋型价值。搜素树里每个节点轮流切换走棋方黑方节点取子节点最大值白方节点取子节点最小值。C 语言实现时用一个递归函数深度控制在 4–6 层再配合 Alpha-Beta 剪枝砍掉明显劣势的分支把搜索节点数从指数级压到可接受范围。// min_max 搜索 Alpha-Beta 剪枝 int alpha_beta(int board[BOARD_SIZE][BOARD_SIZE], int depth, int alpha, int beta, int player) { if (depth 0) return evaluate(board, player); // 评估函数 // 生成候选点优先从上一手棋附近取 Candidate moves[MAX_CANDIDATES]; int move_count generate_moves(board, moves); for (int i 0; i move_count; i) { board[moves[i].row][moves[i].col] player; int score -alpha_beta(board, depth - 1, -beta, -alpha, 3 - player); board[moves[i].row][moves[i].col] EMPTY; if (score alpha) alpha score; if (alpha beta) break; // 剪枝 } return alpha; }player参数用 1 表示黑、2 表示白3 - player完成回合切换。负号翻转是因为每一层都站在当前走棋方的视角评估上一层取反后正好实现「己方得分 对方失分」。moves候选点由generate_moves生成最多保留 20–30 个这部分下一章展开。3.2 评估函数把「棋形」翻译成分数评估函数决定 AI 的棋感它必须同时计算黑、白两方的棋形价值并做差。「黑方视野」是标准做法最终评分 黑方总得分 − 白方总得分AI 落子时只要站在黑方视角取最大值即可。棋形分值参考起点备注五连1000000终局胜点值域上限锁定活四100000再走一手必胜冲四50000单端通头可被堵活三10000两头通威胁最强眠三1000单端通头活二500潜伏展开眠二100聊胜于无int evaluate(int board[BOARD_SIZE][BOARD_SIZE], int ai_player) { int black_score 0, white_score 0; // 遍历每个空点统计其周围四方向的棋形 for (int r 0; r BOARD_SIZE; r) { for (int c 0; c BOARD_SIZE; c) { if (board[r][c] BLACK) { black_score calc_point_value(board, r, c, BLACK); } else if (board[r][c] WHITE) { white_score calc_point_value(board, r, c, WHITE); } } } // AI 视角换算AI 执黑则黑分在前执白则反过来 return (ai_player BLACK) ? (black_score - white_score) : (white_score - black_score); }calc_point_value内部对每个棋子做四方向扫描命中哪张表就给哪个分值。AI 执黑时返回黑减白执白时反过来这样上层搜索无需关心颜色语义。注意评分表中五连分值是 1000000要远大于其他所有棋形的和避免 AI 为了抓小棋形放弃必杀。3.3 禁手判定和搜索的联动禁手点直接移出候选集搜索过程中每一层的合法落子列表都要经过禁手过滤。一种常见做法是在generate_moves生成候选点之后、进入递归之前逐个调is_forbidden过滤对黑方禁手点直接跳过白方不过滤因为没有禁手限制。int legal_move_count 0; for (int i 0; i move_count; i) { int r moves[i].row, c moves[i].col; if (player BLACK is_forbidden(board, r, c)) continue; legal[legal_move_count] moves[i]; // 只保留合法点 }过滤动作放在递归外层避免在每个深度重复做全局禁手扫描性能收益明显。但要注意禁手判断用的是「落子后的临时局面」所以这里传的board需要是当前局面的副本或者使用「落子 → 判断 → 恢复」的模式。内存紧张时可以只对拟落子点做局部扫描具体做法是把count_shapes的范围从全盘缩小到坐标邻域能省一半以上时间。4. C 语言怎么扛住搜索压力数据结构与候选点生成4.1 棋盘存储一维数组 历史栈的组合最省心15×15 的棋盘用int board[225]一维数组存比二维数组多一次索引换算但缓存友好性和 memset 重置速度都好很多。落子历史用栈记录每个元素存坐标、颜色和局面哈希悔棋和搜索回溯只要弹栈即可不用整盘复制。typedef struct { int row, col; int player; uint64_t hash; } MoveRecord; typedef struct { MoveRecord stack[225]; // 最多 225 手 int top; } MoveHistory; // 落子时压栈 void push_move(MoveHistory* hist, int row, int col, int player, uint64_t hash) { hist-stack[hist-top].row row; hist-stack[hist-top].col col; hist-stack[hist-top].player player; hist-stack[hist-top].hash hash; hist-top; }hash域用于 Zobrist 哈希局面求值后缓存结果能显著降低重复局面在搜索中的计算量。栈深上限 225 对 15×15 棋盘足够因为满盘最多 225 手。4.2 候选点生成只扫已有棋子周边两格全盘扫描 225 个空点来做搜索的代价可控但每轮都全盘扫4 层深度下耗时倍增。常规做法是只看已有棋子周围两格范围内的空点距离太远的点不可能产生即时威胁也不会对近期棋局有影响。实现时用一个bool in_candidates[225]标记数组去重。#define MAX_CANDIDATES 64 int generate_moves(int board[], int candidates[MAX_CANDIDATES][2]) { bool mark[225] {false}; int count 0; for (int i 0; i 225; i) { if (board[i] EMPTY) continue; int r i / 15, c i % 15; // 检查上下左右及四个斜向共两格范围 for (int dr -2; dr 2; dr) { for (int dc -2; dc 2; dc) { int nr r dr, nc c dc; if (nr 0 || nr 15 || nc 0 || nc 15) continue; int epos nr * 15 nc; if (board[epos] ! EMPTY || mark[epos]) continue; mark[epos] true; candidates[count][0] nr; candidates[count][1] nc; count; } } } return count; }候选点数上限 64 足够覆盖多数中盘场景。参数说明-2到2是邻域半径棋力要求高可以改到 3但搜索耗时随候选数线性增长一般 2 是性价比最高的起点。4.3 搜索深度与速度的实测平衡我自己习惯从 4 层开始试。纯 Alpha-Beta 加上候选排序先按评估函数打分再按分数从高到低搜在普通笔记本上单步耗时可控制在 1 秒内。若对弈时经常超时优先检查两件事候选点数是否过大、评估函数是否在每个节点做全盘扫描。把evaluate改成增量更新是性能提升最明显的一步但实现复杂度高只有棋力对速度有硬要求时再动。5. 绕不开的四个坑从禁手误判到搜索超时的排查5.1 五连被长连误判搜索里忘了「先看五连」现象黑方走出六连程序判定为长连禁手但按 Renju 规则黑方形成五连是获胜走法不能算禁手六连同时包含五连裁判实践里多数情况按黑胜处理。 原因is_forbidden里先统计长连四方向连续数 ≥6 就直接返回禁手没有检查black_five标志。 解决把五连检测提前只要任一方向连续黑子数等于 5 就直接返回「非禁手」只有长度 ≥6 且没有先形成五连时才判长连禁手。5.2 双活三误报同一个方向被数了两次现象测试某组棋形时AI 在天元附近走出看似双活三的手自己摆盘验证却是单活三眠三但程序仍报禁手。 原因count_shapes对横、竖、斜四个方向分别扫描如果某方向上的棋段被两个方向重复统计尤其是斜线交叉点活三计数会虚增。 解决统计棋形前先对每个坐标的去重或者直接按「段」为单位计数——每个连续段只在其主方向上统计一次跨方向的交叉点单独处理不重复加权。5.3 候选点排序成了性能杀手现象在深度 6 时某一步耗了 20 秒才返回明显卡顿。 原因候选点没有预排序Alpha-Beta 剪枝效率极低大量分支没被剪掉就进行了完整递归。 解决在递归前先对候选点做一次快速评估排序把高价值的棋点放在前面。只排前 10 个也可以因为剪枝主要依赖前几个分支提供较好的 alpha 初值。5.4 评估函数把白方的禁手也算进去现象AI 执白时明明白方可以双活三取胜却拒绝下这一手反而去堵黑方。 原因generate_moves的过滤写成了对所有player都执行is_forbidden白方也被错误地套用了禁手规则。 解决过滤条件改为if (player BLACK is_forbidden(...)) continue;白方完全跳过禁手判断。这条是最常见的白方「没赢下该赢的棋」的元凶调试时先查这个条件。6. 让 AI 真正能对弈验证棋力与调参的最后一公里要给这个 Renru 五子棋 AI 做「验收」我会跑三类验证排队先单元测禁手再做自对弈最后开命令行模式手动摆棋谱。第一类是禁手单测把已知棋形直接写进测试用例黑方在 (7,7) 落子形成双活三断言is_forbidden 1白方同样位置同样的形断言is_forbidden 0黑方形成五连但同线同时有六连断言非禁手。这些用例全绿说明规则逻辑大体正确。第二类是自对弈让 AI 执黑和执白分别启动跑 50 局统计胜负和每步耗时时长。观察重点执黑的胜率如果高于执白太多说明禁手约束没起作用白方如果赢不了黑方往往是白方没利用无禁手优势检查评估函数是否给了白方足够的进攻权重。第三类是命令行对弈交互式输入坐标AI 落子这样最快能复现「AI 为什么不下双活三」这类策略问题。命令行模式应该是代码里最早完成的功能调参和测试全靠它。调参的实操习惯不要一上来改深度先花时间摆几组典型局面记录 AI 的落子选择是否符合直觉。我一般从评估函数表开始调活四与冲四的比值不建议低于 2:1活三与眠三的比值保持在 10:1 左右否则 AI 会偏向防守而失去杀力。所有参数收敛后再尝试把深度从 4 层加到 5 层感受速度余量够不够。这个项目做到最后最大的教训是「规则和搜索要分开算账」搜索层只管找最好的合法点禁手判定作为一层独立过滤器不要混在评估函数里。否则有一天你会为了一个双活三的分值调半天最后发现 bug 出在计数逻辑上。希望帮到你。本文还有配套的精品资源点击获取