简介这是一份面向C与AI算法学习的完整工程基于C实现不围棋NoGo游戏源码源自计算概论课程期末大作业。项目以蒙特卡洛树搜索MCTS作为核心AI算法界面使用OpenGL的glut工具库构建同时包含Minmax对照实现不围棋规则特殊落子若提掉对方棋子反而判负且禁止自杀与空手对棋类程序设计和搜索算法均具较高训练价值。压缩包共57个文件、约2.2MB以14个cpp源文件和14个h头文件为主体配合17张bmp界面图片以及sln、vcxproj、filters等Visual Studio工程配置工程内已划分游戏规则、图形渲染、AI策略、存档管理等模块并附Botzone平台适配目录便于在线评测和二次拓展。目前已有297人学习下载适合作为课程设计参考或C/游戏AI入门的完整案例。1. 不围棋期末大作业为什么选C、MCTS和GLUT这套组合期末验收现场AI对着空棋盘乱下、被老师随手一子逼到提子禁手这是不围棋大作业最典型的翻车画面。不围棋的规则是“落子不能提子、不能自杀、不能重复局面”它恰好是蒙特卡洛树搜索MCTS最擅长的小棋盘对抗场景界面用OpenGL的glut工具库几十行就能画出棋盘并实时显示落子。这套“C核心算法 MCTS决策 GLUT显示”的方案适合两类人C入门阶段想找一份能写进简历的大作业的以及被期末答辩逼着必须让AI有“智能感”的学生。下面按我搭这套东西的先后顺序讲从规则、算法、界面到编译排错全部给可复现的步骤。2. 不围棋规则与棋盘模型合法性判定要先于AI写好2.1 落子合法性的三个条件提子禁手、自杀禁手、劫禁不围棋不是一个“吃子”游戏而是一个“不能提子”的游戏。双方轮流落子任何一手棋如果导致对方棋子被提掉、导致己方落子块无气自杀、导致局面与历史局面重复这手棋就不合法谁先下不出合法棋谁输。这是整个大作业的地基MCTS的随机模拟、界面落子、终局判定全部依赖这层合法性判断它写错一个条件后面AI再聪明也是空中楼阁。最容易写错的地方是“提子禁手”。写惯了围棋代码的人会惯性思维地去找“能提掉对方多少子”但不围棋恰恰反过来落子后只要让任何一个相邻对方棋串的气变成0这手就是禁手。判定时先临时落子然后检查四邻对方棋串无气则非法己方连通块无气则非法。下面是可编译的核心代码用邻接点出发统计“棋串的气”不是单子的气。const int N 9; // 9路棋盘改成19路也通用 const int EMPTY 0; int grid[N][N]; // 0空 1黑 2白 int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; bool outOfBound(int x, int y) { return x 0 || x N || y 0 || y N; } // 统计以 (x,y) 为起点的同色连通块的气数 // visited 必须每次独立传入不能在多个棋串之间复用 int countLiberty(int x, int y, int color, bool visited[][N]) { if (outOfBound(x, y)) return 0; if (visited[x][y]) return 0; if (grid[x][y] EMPTY) return 1; // 空点算一口气 if (grid[x][y] ! color) return 0; // 异色棋子阻断 visited[x][y] true; int lib 0; for (int d 0; d 4; d) lib countLiberty(x dx[d], y dy[d], color, visited); return lib; } bool isLegalMove(int x, int y, int player) { if (outOfBound(x, y)) return false; if (grid[x][y] ! EMPTY) return false; grid[x][y] player; // 临时落子 // 条件一不能提掉任何相邻的对方棋串 for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (outOfBound(nx, ny)) continue; if (grid[nx][ny] EMPTY || grid[nx][ny] player) continue; bool visited[N][N] {false}; if (countLiberty(nx, ny, grid[nx][ny], visited) 0) { grid[x][y] EMPTY; // 恢复棋盘 return false; // 提子禁手 } } // 条件二己方连通块必须有气 bool visited[N][N] {false}; if (countLiberty(x, y, player, visited) 0) { grid[x][y] EMPTY; return false; // 自杀禁手 } grid[x][y] EMPTY; return true; }这段代码的逻辑顺序是固定的先查提子再查自杀顺序反了会漏掉“落子同时提掉对方又让自己无气”的边界情况。countLiberty的visited必须每个棋串单独建复用同一个visited会导致第二个棋串的气被第一个棋串的访问标记挡住误判成无气AI就会漏掉大量合法点。递归深度不会超过棋盘总格数81层不用担心爆栈。第三个条件“劫禁”也可以叫“局面重复禁手”在9路棋盘上用最简单的方式实现每下一步把整个棋盘序列化成一个字符串存进历史数组落子后检查当前序列化结果是否在历史中出现过。不围棋没有围棋那种单点劫争的局部判断全局查重虽然笨但绝对正确期末答辩时反而好解释。2.2 棋盘表示二维数组加状态快照棋盘数据结构我建议用最朴素的int grid[N][N]二维数组不搞链表、不做Zobrist哈希。理由很简单MCTS每轮模拟要频繁拷贝棋盘二维数组的拷贝就是一个memcpy调试时在监视窗口里看数组内容也直观链表棋盘在9路上毫无性能收益只会增加写崩的概率。class Board { public: int grid[N][N]; void reset() { for (int i 0; i N; i) for (int j 0; j N; j) grid[i][j] EMPTY; } void apply(int move, int player) { grid[move / N][move % N] player; history.push_back(snapshot()); // 落子后记录快照 } bool isLegal(int x, int y, int player) { if (!isLegalMove(x, y, player)) return false; string cur snapshot(); for (const string s : history) if (s cur) return false; // 局面重复劫禁 return true; } bool hasAnyLegalMove(int player) { for (int i 0; i N; i) for (int j 0; j N; j) if (isLegal(i, j, player)) return true; return false; } string snapshot() { string s; for (int i 0; i N; i) for (int j 0; j N; j) s.push_back(0 grid[i][j]); return s; } private: vectorstring history; // 全部历史局面 };快照字符串的长度是81个字符9路棋盘上一局最多81手历史数组最多存81个字符串内存占用可以忽略。这里有一个常规做法值得说明history记录的是“落子之后”的局面判断劫禁时要把当前局面和history里的全部快照比对而不是只比上一手。有的同学只比较“上一手局面”遇到连环劫或者更复杂的重复形状就会漏判。2.3 终局判定谁无棋可下谁负不围棋的胜负判定有几个变体有的数子、有的比目数为了避免答辩被问倒建议在代码注释里明确写死自己采用的规则。我采用的标准是“轮流落子轮到某方时无任何合法着法该方判负”。这个规则不需要数子不需要判断死活和MCTS的模拟逻辑天然吻合代码实现就是遍历所有空点调isLegal。bool isGameOver(int player) { return !board.hasAnyLegalMove(player); }终局判定在MCTS里是模拟函数终止的天然条件双方不断随机落子总有一方率先落入无棋可下的局面。注意“无合法着法”必须实时计算不能靠手数上限猜因为不围棋的禁手规则会让棋局提前结束。我在最初版本里用“棋盘下满就结束”的围棋思路结果AI频繁在不该结束的局面下虚晃一枪。3. 把MCTS写进不围棋AI四阶段实现与可调参数3.1 为什么MCTS比极小化搜索更适合不围棋不围棋的局面评估函数极难写没有吃子收益没有稳定的子力价值一个棋串的优势要等棋局末尾才显现。用Alpha-Beta剪枝需要给每个局面打一个“好坏分”这个分数写不好AI就是带着偏见在搜索。MCTS的思路完全不同——它不需要人工设计评估函数只靠“随机模拟到底谁赢谁输”来累积统计信号搜索越深胜率统计越可靠。不围棋9路棋盘每步合法着法通常在40到60个之间比围棋的200多个小得多随机模拟的信噪比更高。这是MCTS能在这道大作业里胜出的根本原因规则简单、分支因子小、模拟速度快。相比之下如果老师布置的是19路不围棋纯MCTS收敛会明显变慢那是另一个课题了。3.2 UCT选择先访问没试过的孩子MCTS四阶段的第一步是“选择”。从根节点出发每层都要在子节点里挑一个“最值得继续探索”的挑法用UCB1公式wins/visits c * sqrt(log(parentVisits) / visits)。前一项是胜率代表这个节点表现好后一项是探索项访问次数少的孩子会得到更高的探索分值。c是探索常数c越大AI越爱尝试冷门着法。struct Node { int move; // 落到棋盘上的位置-1表示根节点 int player; // 轮到该节点落子的玩家 int wins, visits; // wins表示该节点玩家视角的获胜次数 vectorNode* children; }; double uctValue(Node* node, double c) { if (node-visits 0) return 1e9; // 未访问的孩子优先 double exploit (double)node-wins / node-visits; double explore c * sqrt(log((double)node-parent-visits) / node-visits); return exploit explore; } Node* selectChild(Node* node, double c) { Node* best nullptr; double bestVal -1e9; for (Node* child : node-children) { double val uctValue(child, c); if (val bestVal) { bestVal val; best child; } } return best; }未访问孩子返回1e9这个写法是MCTS的通用做法保证每个合法着法“先被试一轮”再进入胜率筛选。c的建议值在0.5到1.0之间我习惯取0.7比围棋常用的1.414小。原因是9路不围棋的模拟结果方差大探索系数太大会让AI反复去试那些随机模拟里偶尔赢过、实际很差的位置反而拖慢收敛。这里调参有点玄学但“从0.7起步看AI是否会频繁下出低级坏棋”是可执行的判断标准。3.3 扩展、随机模拟与反向传播选择到叶子节点后如果该节点还有合法着法可下就做“扩展”——把它的全部合法着法生成子节点如果局势已经结束就直接进入反向传播。扩展完立刻随机挑一个孩子对拷贝棋盘继续“模拟”双方随机落子直到某一方无棋可下然后回溯沿途把胜率信息一层层传回根节点。bool simulate(Board sim, int startPlayer) { int cur startPlayer; while (sim.hasAnyLegalMove(cur)) { vectorint moves sim.legalMoves(cur); int m moves[rand() % moves.size()]; sim.apply(m, cur); cur (cur BLACK) ? WHITE : BLACK; } return cur ! startPlayer; // startPlayer无棋可下 对方胜 } void backup(Node* node, bool startPlayerWon) { while (node) { node-visits; if (startPlayerWon (node-player node-parent ? ... )) { // 见下方说明 } node node-parent; } }backup里的胜负归属是新手最容易写错的地方。我的做法是让simulate返回“开始模拟的那个玩家是否获胜”然后在回溯时逐层比较如果当前节点的player正好是模拟的起始玩家胜利记到wins否则不记。这样根节点统计的就是“轮到AI下时AI赢了多少次”选择阶段直接读根节点的孩子胜率即可。写的时候别用全局变量记录胜负一旦递归路径长一点就会串数据。模拟阶段用到的就是c随机数这里有个高频坑用rand()不设种子每局AI的第一步永远一样。最省事的做法是srand((unsigned)time(0))但如果你的编译器支持C11标准优先用std::mt19937rand()的低位随机性在取模时会暴露明显周期。3.4 主循环迭代次数与思考时间怎么配合搜索主循环决定AI“想多久”。两种控制方案固定迭代次数或固定时间预算。期末演示建议用时间预算因为答辩现场机器性能未知固定次数在慢机器上可能卡死十几秒。int bestMove(Board rootBoard, int aiPlayer, double timeLimit) { Node* root new Node(); clock_t start clock(); int iter 0; while (true) { Board sim rootBoard; // 每次迭代拷贝棋盘 Node* node root; while (!node-children.empty()) { // 选择阶段 node selectChild(node, 0.7); sim.apply(node-move, node-player); } vectorint moves sim.legalMoves(node-player); if (!moves.empty()) { // 扩展阶段 for (int m : moves) node-children.push_back(new Node(m, opponent(node-player))); node node-children[rand() % moves.size()]; sim.apply(node-move, node-player); } bool won simulate(sim, node-player); // 模拟阶段 backup(node, won); // 反向传播 iter; if ((iter % 200 0) (clock() - start) timeLimit * CLOCKS_PER_SEC) break; } Node* best root-children[0]; for (Node* c : root-children) if (c-visits best-visits) best c; // 选访问次数最多的 return best-move; }选“访问次数最多”而不是“胜率最高”的孩子这是MCTS的经典收尾方式。胜率最高的节点可能只被访问过几次统计意义不足访问次数多说明AI反复验证过它值得探索。每次迭代都从根节点重新走一遍选择路径拷贝棋盘的频率很高9路棋盘81个int的拷贝开销可以忽略千万別为省拷贝去动界面正在显示的棋盘后面避坑章会细说。参数方面9路不围棋单步建议给1.0到1.5秒迭代次数通常在2000到5000次之间。迭代上限设一个兜底值比如20000防止timeLimit判断因clock()精度问题失效导致无限循环。参数建议值说明探索常数 c0.5 ~ 1.0越大越爱尝试冷门着法不围棋建议偏小单步思考时间1.0 ~ 1.5 秒超过2秒演示观感明显变差迭代次数上限2000 ~ 5000与时间预算同时生效双保险随机模拟最大步数无限制依赖终局判定自然结束不需要截断4. 用OpenGL的glut画出棋盘和落子反馈4.1 glut窗口初始化与回调函数注册界面部分用glut工具库因为期末大作业追求“稳定跑通”而不是“技术前沿”。glut的窗口生命周期极短初始化、注册回调、进入主循环三件事做完就再也不用管窗口消息了。回调机制是C函数指针最典型的应用场景glutDisplayFunc和glutMouseFunc接受的必须是全局函数或静态成员函数不能直接传普通成员函数。Game game; // 全局对象让回调函数能访问到棋盘状态 void onDisplay() { game.render(); } void onMouse(int button, int state, int x, int y) { game.handleMouse(button, state, x, y); } int main(int argc, char** argv) { glutInit(argc, argv); glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB); glutInitWindowSize(600, 600); glutCreateWindow(不围棋 - MCTS AI); glClearColor(0.92f, 0.84f, 0.65f, 1.0f); // 木纹底色 glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluOrtho2D(-0.5, N - 0.5, -0.5, N - 0.5); // 坐标原点在左下角 glutDisplayFunc(onDisplay); glutMouseFunc(onMouse); game.reset(); glutMainLoop(); return 0; }GLUT_DOUBLE是双缓冲模式配合glutSwapBuffers使用避免绘制棋盘时画面闪烁。gluOrtho2D把世界坐标映射到窗口交叉点落在整数坐标0到N-1上棋子圆心就在整数坐标位置这样鼠标换算时可以直接四舍五入到最近的交叉点。4.2 绘制棋盘、棋子和最后一步的标记渲染函数每帧做三件事画网格线、画所有棋子、画最后一步的高亮标记。最后一步的标记特别重要答辩时老师能一眼看到AI刚下在哪比口头解释“它刚才下在那边”直观得多。void Game::render() { glClear(GL_COLOR_BUFFER_BIT); glColor3f(0.2f, 0.2f, 0.2f); glLineWidth(1.5f); glBegin(GL_LINES); for (int i 0; i N; i) { glVertex2f(i, 0); glVertex2f(i, N - 1); glVertex2f(0, i); glVertex2f(N - 1, i); } glEnd(); for (int x 0; x N; x) { for (int y 0; y N; y) { if (grid[x][y] EMPTY) continue; if (grid[x][y] BLACK) glColor3f(0.0f, 0.0f, 0.0f); else glColor3f(1.0f, 1.0f, 1.0f); glBegin(GL_TRIANGLE_FAN); // 画圆 for (int k 0; k 20; k) { float ang k * 2.0f * 3.14159f / 20; glVertex2f(x 0.38f * cos(ang), y 0.38f * sin(ang)); } glEnd(); } } if (lastMove 0) { // 高亮最后一步 int lx lastMove / N, ly lastMove % N; glColor3f(0.8f, 0.1f, 0.1f); glRectf(lx - 0.1f, ly - 0.1f, lx 0.1f, ly 0.1f); } glutSwapBuffers(); // 双缓冲交换 }棋子用GL_TRIANGLE_FAN画成20个扇形的圆视觉效果足够平滑别用GL_POLYGON一次画整个圆某些显卡驱动在凹陷多边形上会有填充瑕疵。画完必须调用glutSwapBuffers否则双缓冲模式下画面永远不更新这是新手最常见的“为什么glutDisplayFunc没效果”的原因。4.3 鼠标交互与坐标换算glut的鼠标回调里x和y是窗口像素坐标原点在左上角而gluOrtho2D的世界坐标原点在左下角y方向必须翻转。棋盘交叉点在世界坐标里落在整数位置像素坐标按格宽缩放后四舍五入即可得到行列号。void Game::handleMouse(int button, int state, int x, int y) { if (button ! GLUT_LEFT_BUTTON || state ! GLUT_DOWN) return; float cell (float)windowWidth / N; int col (int)floor((float)x / cell 0.5f); int row (int)floor((float)(windowHeight - y) / cell 0.5f); if (row 0 || row N || col 0 || col N) return; if (!board.isLegal(row, col, HUMAN_PLAYER)) return; board.apply(row * N col, HUMAN_PLAYER); lastMove row * N col; glutPostRedisplay(); // 请求重绘 // 玩家落子后 AI 使用 MCTS 决策 int aiMove ai.bestMove(board, AI_PLAYER, 1.2); board.apply(aiMove, AI_PLAYER); lastMove aiMove; glutPostRedisplay(); }坐标换算里“0.5再floor”是四舍五入取最近的交叉点不加这个偏移鼠标点在格子中间偏左的位置会被错误地归到左边交叉点整个落子手感会偏移半格。y方向翻转漏掉的人更多症状是点击棋盘上方棋子却出现在下方答辩时特别显眼。我在最早版本里就漏了翻转调试时一度怀疑是glut坐标bug其实是窗口坐标和世界坐标的约定差异。5. 编译、运行与避坑这台大作业最容易翻车的地方5.1 glut环境配置Unresolved external symbol与运行缺DLL现象在VS2010或VSCode配置C环境后代码编译通过但链接阶段报unresolved external symbol __glutCreateWindow8或者编译运行都正常把exe拷到另一台机器上运行时提示找不到glut32.dll。原因glut的链接错误几乎都是库没配对。__glutCreateWindow8这种带下划线和数字的符号是32位stdcall修饰如果你链接的库是64位的或者根本忘了在“附加依赖项”里加glut库就会报这个错。运行缺DLL则是因为glut库是以动态库形式分发的exe启动时需要在当前目录或系统目录找到对应DLL。解决确认自己的编译器是32位还是64位去找配套的glut或freeglut版本在项目属性的“VC目录”里把头文件目录、库目录分别指到glut的include和lib在“链接器-输入-附加依赖项”里写清楚库名。发布演示版时把glut32.dll放到exe同目录而不是只放到系统目录换机器演示才不会当场掉链子。现在更省事的做法是用freeglut替代glutAPI完全兼容省掉大量老glut在64位环境下的兼容问题。5.2 MCTS思考太久界面未响应像死机现象点击落子后glut窗口立刻失去响应标题栏出现“未响应”十几秒后才恢复AI下出的一手在玩家看来毫无道理。原因glutMainLoop是单线程事件循环在鼠标回调里直接调用MCTS搜索搜索期间整个窗口的事件处理被阻塞。如果迭代次数设成几万次而每轮模拟又不小心在拷贝整个棋盘单步决策就会拖到十几秒。这是MCTS项目里最典型的血泪经验算法正确但没控制思考时间。解决先把迭代次数压到1500到3000验证AI行为后再逐步增加时间预算方案里用clock()每200次迭代检查一次到时就跳出循环别用sleep之类的粗糙方案。更进一步的方案是开一个独立线程跑搜索但期末大作业不建议碰多线程Windows上线程与glut的交互是另一个大坑先把单线程限时做好就足够演示了。5.3 随机数种子固定AI第一步永远一样现象每次启动程序AI先手时总是落同一个位置调试时重跑同一局棋局走势完全一致无法通过多次运行验证AI稳定性。原因最常见的是srand()没调用或者把srand(0)写死在初始化里。rand()的伪随机序列由种子决定种子固定序列就固定MCTS的模拟和扩展阶段全用rand()于是整局棋变成“可完全重放”的确定过程。解决程序入口统一设置srand((unsigned)time(0))编译器支持C11就用std::mt19937加random_device种子。反过来调试期想复现某个AI坏棋的时候固定种子反而是后悔药——把种子打印出来看到坏棋后拿同一个种子重跑比每次都不一样好排查得多。5.4 棋盘数组越界边缘棋子随机消失或访问冲突现象棋盘边缘的棋子显示位置错乱或者落子后程序偶发崩溃调试器停在某个赋值语句上报0xC0000005访问冲突。原因两个高频来源。第一用字符串字面量初始化棋盘数组比如char grid[9][9]却写成一行9个字符加结尾\0总共10字节越界写到了下一行第二鼠标坐标换算在点击窗口边缘时算出row或col等于N然后直接访问grid[N][N]写飞。这类越界在Debug版可能不立刻崩到了Release版才随机炸排查成本极高。解决棋盘初始化一律用循环逐格赋0不要用字符串所有数组访问前先做边界判断鼠标回调里已经写了row0||rowN的检查业务代码里同样要养成先判边界的习惯。另一次血泪教训是countLiberty函数里直接访问未经边界判断的邻点棋盘边缘的棋子一旦落子就崩溃。5.5 提子误判明明能下的点被判禁手现象AI在某一步突然不下了或者玩家下一手被界面静默拒绝而人工对照规则发现这手完全合法。更隐蔽的是反过来的非法落子通过了isLegal的检查导致AI吃掉对方棋子。原因提子判定里visited数组在多个棋串之间复用。countLiberty是递归函数visited记录“已经统计过的点”如果对两个相邻的对方棋串传同一个visited第二个棋串的气会被第一个棋串走过的点挡住误判为无气。自杀判定也容易错落子后要从落子点出发统计整个己方连通块的气而不是只数落子点四周有几个空点。解决每个棋串单独建visited数组代码里写bool visited[N][N] {false};然后传入不要复用外层变量。己方连通块的气数统计要覆盖所有相连的己方棋子最简单的验证方法是构造“落子点被己方棋子包围但整体还有一口气”的用例跑一遍isLegal确认返回true。这个用例在答辩时讲出来能直接证明你理解不围棋规则不只是抄了代码。6. 让AI更强验证方法、启发式模拟与调参习惯6.1 先跑AI对AI用胜率说话MCTS写完后别急着让人对弈先做自动化验证让你的MCTS AI和纯随机落子AI对战固定先后手各下20局统计胜率。如果胜率不到90%说明合法性判断或MCTS回溯逻辑还有bug不要继续调参。这个验证方法也用于每次改完MCTS代码后的回归测试比人工下棋快得多也更客观。6.2 给随机模拟加启发式偏好纯随机的模拟阶段收敛偏慢一个低成本提升是让模拟过程中的随机落子偏向“靠近中心、不与对方棋子相邻”的位置。实现时给每个合法着法打一个分值中心距离近加分邻点靠近对方棋子减分按分值加权选择。注意启发强度别加太猛模拟阶段如果太“聪明”会变成固定套路搜索丧失MCTS靠大量随机对局发现新可能性的优势。我一般把偏好权重控制在让“较差着法仍有15%左右的被选概率”。6.3 调参习惯一次只动一个变量MCTS的参数耦合性很强探索常数、迭代次数、时间预算、启发权重互相影响。乱调的结果是AI表现时好时坏像黑匣子一样不可控。我现在每写一个版本第一件事是跑一轮AI对随机AI的胜率记录然后只改一个参数再跑一轮前后对比。迭代次数优先于探索常数探索常数优先于启发权重这个顺序基本能定位到绝大多数问题。这个从“能跑”到“稳定变强”的过程本身就是一份比代码更有说服力的作业说明希望帮到你。本文还有配套的精品资源点击获取