拓冰网站定制 
简介基于C实现的不围棋No-Go游戏完整源码是计算概论课程期末大作业的典型项目适合正在学习C、游戏编程或人工智能算法的学生参考。项目采用蒙特卡洛树搜索MCTS驱动AI同时提供MinMax对照实现界面基于OpenGL glut工具库。代码完整实现了不围棋规则气与提子判定、落子吃子判负、自杀判负、禁止空手pass以及黑棋首手禁占天元等细节并支持存档与Botzone在线对战。压缩包共57个文件含14个cpp源文件、14个头文件、17个bmp图片素材以及项目配置、存档、说明文档等整体仅2.2MB结构紧凑清晰。已有298人学习下载。通过学习源码读者可掌握MCTS与MinMax两种AI算法的落地写法、C图形界面搭建方法、围棋类棋局判定与博弈逻辑的完整实现思路便于在此基础上完成同类课程作业、毕业设计或进一步二次开发。1. 计算概论期末大作业的不围棋方案C规则、MCTS棋力、glut界面计算概论期末大作业里“不围棋”可能是最难让老师眼前一亮的题目规则看起来像围棋赢法却和围棋完全相反AI还得真有棋力。标题里的组合方案——用C写规则与搜索、用蒙特卡洛树搜索MCTS做AI决策、用OpenGL的glut工具库画棋盘棋子——是我见过最稳的一条路逻辑全部收在C层不依赖外部AI库报告好写演示也直观。这篇就照着这个组合从规则定义、MCTS落地到glut界面一步步讲透适合正在做这道大作业的学生也适合想最小成本把手伸进MCTS和OpenGL里的C从业者。2. 先让程序懂不围棋规则胜负判定、数据结构与提子实现2.1 不围棋的胜负判定与禁手三条规则先写进代码不围棋和围棋共用“气”和“提子”的体系一颗棋子看上下左右四个十字交叉点空着就算一口气一个连通块所有气的总和为零就把这个块从棋盘上提走。区别全在胜负目标上——围棋比谁围的地多不围棋则是“谁提掉对方的最后一颗棋子谁立刻获胜”。棋盘下满且没人被吃光判和。动手写代码前必须先把三条判定固化到程序里。第一条是自杀禁手落子后己方形成一个无气块且没有因为提掉对方而获得气这一步非法。第二条是提子优先落子点旁边的对方连通块若气为零先把它提掉再检查己方死活。第三条是终局判定提子后对方棋盘上的棋子数为零落子方直接胜。这里和围棋最大的差异在于不围棋每一步的胜负反馈都很强——模拟局很容易跑到终点这对MCTS是天然友好的条件。常见实现会把棋盘固定为9×9黑白轮流落子黑先。9×9意味着最多81手终局不会拖太长MCTS的随机模拟单局开销也很小。如果做19×19纯随机模拟的信号会被稀释得很厉害棋力会明显下降期末演示时容易翻车。先把规模锁在9×9后面想扩展再单独说。2.2 棋盘数据结构与提子判定一段可直接改的C实现棋盘用定长二维数组最省事。grid[r][c]取三个值0代表空1代表黑-1代表白。这里选-1而不是2是因为取对方颜色只需要-color后面提子判断能少写一个分支。BFS找连通块和气我一律用固定数组加方向偏移9×9规模下这种写法比并查集直观得多。#include queue #include vector #include cstring #include utility const int N 9; const int EMPTY 0, BLACK 1, WHITE -1; struct Board { int grid[N][N]; Board() { memset(grid, 0, sizeof(grid)); } // 返回包含(r,c)的连通块的所有坐标 std::vectorstd::pairint,int blockOf(int r, int c) const { const int dr[4] {-1, 1, 0, 0}; const int dc[4] {0, 0, -1, 1}; int color grid[r][c]; bool vis[N][N] {false}; std::queuestd::pairint,int q; std::vectorstd::pairint,int res; vis[r][c] true; q.push({r, c}); while (!q.empty()) { auto [x, y] q.front(); q.pop(); res.push_back({x, y}); for (int k 0; k 4; k) { int nx x dr[k], ny y dc[k]; if (nx 0 || nx N || ny 0 || ny N) continue; if (grid[nx][ny] color !vis[nx][ny]) { vis[nx][ny] true; q.push({nx, ny}); } } } return res; } };blockOf用BFS收集整个连通块后续提子需要知道“这一块具体有哪些坐标”只算气的个数不够用。注意vis数组在这里每次落子都会重新创建9×9棋盘上这个开销无所谓但MCTS跑上万次模拟时频繁分配二维数组会拖慢速度优化时可以改成int vis[N][N]加时间戳的写法清零成本从O(N²)降到O(1)。提子与落子合法性判断是整份代码最核心的函数我把它放在一个applyMove里返回值三种0合法继续、1非法禁手、2提掉对方最后一子获胜。先落子、再提对方、最后查己方这个顺序不能反。// 在(r,c)落 color 子返回 1 非法2 落子方直接获胜0 合法 int applyMove(Board b, int r, int c, int color) { if (b.grid[r][c] ! EMPTY) return 1; b.grid[r][c] color; int opp -color; const int dr[4] {-1, 1, 0, 0}; const int dc[4] {0, 0, -1, 1}; std::vectorstd::pairint,int removed; // 第一步提掉所有无气的对方连通块 for (int k 0; k 4; k) { int nr r dr[k], nc c dc[k]; if (nr 0 || nr N || nc 0 || nc N) continue; if (b.grid[nr][nc] ! opp) continue; auto block b.blockOf(nr, nc); bool alive false; for (auto [x, y] : block) { for (int t 0; t 4; t) { int nx x dr[t], ny y dc[t]; if (nx 0 nx N ny 0 ny N b.grid[nx][ny] EMPTY) { alive true; break; } } if (alive) break; } if (!alive) { for (auto [x, y] : block) removed.push_back({x, y}); } } for (auto [x, y] : removed) b.grid[x][y] EMPTY; // 第二步提子后对方棋盘为空直接获胜 int oppCount 0; for (int i 0; i N; i) for (int j 0; j N; j) if (b.grid[i][j] opp) oppCount; if (oppCount 0) return 2; // 第三步己方落子后无气判禁手并撤销整步 auto myBlock b.blockOf(r, c); for (auto [x, y] : myBlock) for (int t 0; t 4; t) { int nx x dr[t], ny y dc[t]; if (nx 0 nx N ny 0 ny N b.grid[nx][ny] EMPTY) return 0; // 还有气合法 } for (auto [x, y] : removed) b.grid[x][y] opp; // 还原被提子 b.grid[r][c] EMPTY; return 1; }这段逻辑的要点是“先提后查”有些棋形看起来是自杀但落子后先提掉对方一块己方就有了气这在围棋里是合法着法。另一个细节是撤销时必须把被提的对方棋子原样放回去同时清掉己方刚落的子否则棋盘状态被污染MCTS模拟的后续对局全是错的。这个还原动作是新人最容易漏的模拟结果一旦混入坏局面胜率统计整个失真。2.3 BFS算气还是并查集维护连通块选型理由与实现边界提子判断里最费时的就是blockOf每步最多81格全盘BFS一次也就几百次访问。MCTS跑一万次模拟每局平均几十手总调用次数在几十万量级这时的瓶颈反而不是算法复杂度而是数组分配和函数调用开销。并查集的路子适合把棋盘维护成动态连通结构每次落子只影响附近几个点合并连通块很快但“提子”操作要整块重置父指针写起来容易出错。以我的经验期末大作业完全没必要上并查集先用BFS版本把棋力跑通再用命令行自对弈验证正确性比一开始就追求性能实在。真要到优化阶段优先做两件事一是把vis数组换成时间戳复用省去逐次初始化的开销二是把applyMove改成原地试下再回滚避免每次模拟都复制整个Board。这两步做完单线程跑两三万次模拟已经足够应付9×9棋盘。3. 蒙特卡洛树搜索怎么落地四步循环、UCB参数与C核心类3.1 MCTS四步循环选择、扩展、模拟、回传如何分工蒙特卡洛树搜索把一次对局拆成四个阶段每个阶段各干一件事。第一步选择从根节点出发沿着子节点往下走每一步都挑“当前最值得看”的节点直到叶子。第二步扩展给叶子节点生成合法落子挂上子节点。第三步模拟从某个子节点开始黑白双方随机落子一路冲到终局。第四步回传把模拟结果从该节点一路传回根节点更新路径上每个节点的访问次数和胜利次数。不围棋特别适合这套流程原因是终局判定足够干净。随机模拟阶段不需要工程师设计“围空”“做眼”这些概念只要别下禁手走到有人被提光或棋盘填满胜负立刻见分晓。模拟局多了某个落点赢过多少次统计上就有区分度。树节点代表“一个具体棋面加轮到谁走”。根节点是当前真实棋面每个子节点代表“在父节点棋面上走一步合法棋之后的新棋面”。所以MCTS本质上是在拿“模拟次数”换“对棋面的评估精度”而不是像传统搜索那样硬算每步的精确收益。这也是为什么大家常把模拟阶段当黑匣子——它不需要多聪明只要终局判定正确统计就会自己说话。3.2 两个必调参数UCB的探索系数C和模拟次数N选择阶段用UCB公式给每个子节点打分UCB(child) child.wins / child.visits C * sqrt(log(parent.visits) / child.visits)前半部分是胜率代表这个节点已知的棋力后半部分是探索奖励访问次数越少的节点分数越高。C就是探索系数控制AI愿意试冷门棋的程度。C太大AI会频繁下一些明显不行的点棋力变弱C太小AI过早锁死一个分支错过更优解。我在9×9不围棋上常用1.4左右先手后手都试过这个值比较稳。参数常规取值调大的影响调小的影影响探索系数C0.72.0更多尝试冷门点落子更“散”更倾向已知高胜率分支模拟次数N500020000棋力提升单步耗时线性增加反应快棋力下降随机模拟规避禁手必须开启避免模拟局作废模拟局失真棋力不可信模拟次数直接决定单步耗时这个参数和机器性能强相关。我的经验是Release编译下9×9棋盘跑一万次模拟大概在0.2到0.5秒Debug编译会慢上好几倍。演示前先在目标机器上测一轮别到台上才暴露卡顿。调参的基本方法是让AI自己跟自己下几十局先手后手各统计一次胜率选一个延迟可接受且胜率不垮的N。网上搜MCTS相关笔记时也能看到一些默认值但机器不同抄过来的数字不一定适配你手上的代码。3.3 核心类与回溯更新给Node一份完整的棋面快照节点设计上我的选择是“每个节点保存一份完整棋面”而不是只保存一步棋。9×9棋盘81个整数拷贝一次开销很小换来的是回溯逻辑极其简单——模拟结束后顺着路径把胜负数传上去就行不需要反向走棋、撤销落点。这个取舍在16×16以上棋盘可能变奢侈但在本项目范围里是最省脑力的。#include cmath #include vector #include random struct MCTSNode { Board board; // 完整棋面快照 int player; // 该节点的落子方1 黑 -1 白模拟时从该节点算起 double wins 0.0; int visits 0; bool expanded false; std::vectorMCTSNode* children; MCTSNode* parent nullptr; double ucb(double C) const { if (visits 0) return 1e9; // 未访问节点永远优先 double exploit wins / visits; double explore C * std::sqrt(std::log(parent-visits) / visits); return exploit explore; } };visits初始为0时UCB分数给一个极大值保证每个孩子至少被选中一次这是MCTS的标准做法不然某些合法落点永远没机会被模拟到。wins用double而不是int是因为平局会按0.5计模拟结果不总是整数。主循环就是把这四步串起来MCTSNode* root new MCTSNode(); // 根节点棋面设为当前局 for (int sim 0; sim simulations; sim) { // 选择一直走到叶子 std::vectorMCTSNode* path; MCTSNode* cur root; while (cur-expanded !cur-children.empty()) { MCTSNode* best nullptr; double bestScore -1e9; for (MCTSNode* child : cur-children) { double s child-ucb(C); if (s bestScore) { bestScore s; best child; } } cur best; path.push_back(cur); } // 扩展展开第一个未扩展的节点 if (!cur-expanded) { // 生成所有合法落子创建子节点 for (int i 0; i N; i) for (int j 0; j N; j) { Board t cur-board; if (applyMove(t, i, j, cur-player) ! 1) { auto* child new MCTSNode(); child-board t; child-player -cur-player; child-parent cur; cur-children.push_back(child); } } cur-expanded true; // 如果叶子有多个孩子先选第一个进去模拟 if (!cur-children.empty()) { cur cur-children[0]; path.push_back(cur); } } // 模拟随机下到终局平局回传 0.5 double reward simulate(cur-board, root-player, cur-player); // 回传路径上所有节点更新统计 for (MCTSNode* n : path) { n-visits; n-wins reward; } }这个循环是“一个模拟”的完整过程。注意reward是以根节点落子方视角算的所以回传时路径每个节点都加同一个值。如果你用子节点视角算reward回传时要根据奇偶层数取正负两种约定都行但必须和wins的累计方式保持一致混用会让你调参时怀疑人生。平局返回0.5是我后来加上的不围棋棋盘不大平局不算罕见按0/1处理会让AI对某些稳妥局面产生错误偏好。模拟函数本身也要过滤禁手否则随机下出非法棋会提前“结束”一局统计出的奖励是脏的int simulate(Board b, int curPlayer, int rootPlayer) { int moves 0; while (moves N * N) { std::vectorint legal; for (int i 0; i N; i) for (int j 0; j N; j) { Board t b; if (applyMove(t, i, j, curPlayer) ! 1) legal.push_back(i * N j); } if (legal.empty()) return 0; // 无棋可下当前方输 int idx legal[rand() % legal.size()]; int r idx / N, c idx % N; int res applyMove(b, r, c, curPlayer); moves; if (res 2) return (curPlayer rootPlayer) ? 1 : 0; curPlayer -curPlayer; } return 0.5; // 棋盘填满且未分胜负 }模拟里对每个空点都拷贝一次Board再调用applyMove这是最简单的写法但不是最快的。实测里这个t的拷贝会在热路径上反复出现优化时可以改成“先试下、非法再回滚”的原地模式一台普通笔记本上能把十万次模拟的耗时压缩三分之一以上。先把功能做对再动手抠这个细节。4. 用OpenGL的glut库把棋盘画出来窗口初始化、绘制与鼠标交互4.1 glut窗口初始化glutMainLoop之前的调用顺序glut有一个怪脾气调用顺序错一个就黑屏或者窗口压根不出现。常规的初始化序列是固定的glutInit、glutInitDisplayMode、glutInitWindowSize、glutCreateWindow然后设置视图和回调最后glutMainLoop。这几行里最容易被忽略的是glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB)漏了GLUT_DOUBLE会让画面闪烁到没法看因为缓冲只有一个绘制一次就被交换一次。#include GL/glut.h int main(int argc, char** argv) { glutInit(argc, argv); glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB); glutInitWindowSize(720, 720); glutInitWindowPosition(80, 80); glutCreateWindow(不围棋 - MCTS); glClearColor(0.92f, 0.84f, 0.70f, 1.0f); // 木色背景 gluOrtho2D(-0.5, 9.5, -0.5, 9.5); // 棋盘映射到 0..8 glutDisplayFunc(display); glutMouseFunc(onMouse); glutMainLoop(); return 0; }gluOrtho2D设置了正交投影范围这里留出半格边距棋盘线画在0到8之间棋子中心正好落在整数坐标上。注意gluOrtho2D必须在窗口创建之后调用因为它依赖当前OpenGL上下文我把绘制棋盘背景色放在CreateWindow之后、回调注册之前习惯上是没问题的。glutMainLoop是阻塞调用它会一直在内部消息循环里转直到窗口关闭所以主循环之后不要放任何代码。4.2 绘制棋盘与棋子从glClear到glutSwapBuffers绘制回调里做的事情顺序很清楚清屏、画网格、画棋子、交换缓冲。双缓冲模式下glClear和glSwapBuffers必须成对出现只画不换窗口永远显示旧画面只换不清棋盘会叠成废纸。void display() { glClear(GL_COLOR_BUFFER_BIT); // 网格线 glColor3f(0.25f, 0.25f, 0.25f); glBegin(GL_LINES); for (int i 0; i N; i) { glVertex2f(i, 0.0f); glVertex2f(i, N - 1.0f); glVertex2f(0.0f, i); glVertex2f(N - 1.0f, i); } glEnd(); // 棋子 for (int r 0; r N; r) for (int c 0; c N; c) { if (board.grid[r][c] EMPTY) continue; if (board.grid[r][c] BLACK) glColor3f(0.10f, 0.10f, 0.10f); else glColor3f(0.95f, 0.95f, 0.95f); drawCircle(c, r, 0.40f); // 圆心(c,r)半径0.4 } glutSwapBuffers(); }drawCircle一般用GL_TRIANGLE_FAN画一个实心圆从圆心出发把圆周切几十个顶点连起来。黑子白子这种纯色绘制不需要纹理OpenGL基础绘制足够。想加“上一手标记”可以在该位置用glColor3f画一个高亮小方框或空心圆但记得上一次落子的坐标要单独存一个全局变量绘制时在这里多画一笔。4.3 鼠标点击坐标换算与AI落子的两种接法glut的鼠标回调拿到的坐标原点在窗口左上角y轴向下而正交投影里原点在左下角y轴向上。换算错位会让点击的列对、行反棋子落去对面棋盘。我常用的公式是void onMouse(int button, int state, int x, int y) { if (button ! GLUT_LEFT_BUTTON || state ! GLUT_DOWN) return; int row 8 - (int)(y * 9.0 / 720.0); // 行号翻转 int col (int)(x * 9.0 / 720.0); // 校验边界落子 }窗口尺寸是720×720棋盘逻辑坐标是0到8的9格所以一个像素步长对应9.0 / 720.0。行翻转是这里的经典陷阱我见过不少作业棋盘上下颠倒原因就是渲染时没翻、事件里也没翻两边各错一次反而看起来“正常”实际棋形是镜像的MCTS模拟和界面显示不一致AI会走出让观众一头雾水的棋。AI落子和glut主循环的配合另有一个坑鼠标回调里直接跑一万次MCTS模拟界面会僵住一两秒看起来像死机。常见做法有两种。第一种是把MCTS放在回调里同步执行简单但体验差适合赶进度第二种是用glutIdleFunc注册一个空闲函数每一帧只做几百次模拟攒够一定局数再落子界面不卡玩家能肉眼看到棋子在思考间隙出现。第二种要引入一个“是否轮到AI思考”的状态变量逻辑稍复杂但演示效果好不少我建议期末展示用这个。5. 期末大作业避坑记录glut安装、黑屏和MCTS卡顿怎么排查5.1 在Visual Studio里装glut头文件、lib和dll的翻车点现象照着网上的“opengl在visual studio中怎么安装”一类教程把freeglut下载回来解压放进项目编译时报“无法打开包含文件glut.h”或链接报LNK2019找不到glutInit。原因大部分教程只让你把头文件加到include目录却漏了库目录和dll的放置。glut要装齐三样glut.h、glut32.lib或freeglut.lib、glut32.dll或freeglut.dll。另外位数必须匹配64位工程配32位lib链接阶段一定报错。解决项目属性里分别配置包含目录和库目录#pragma comment(lib, glut32.lib)直接写在源码顶部也能跳过配置步骤dll放到exe同目录或放到系统PATH里。用VSCode的话除了c_cpp_properties.json配include路径还要在tasks.json的链接参数里把lib路径加进去很多人配了头文件提示、编译阶段又栽一次。这套环境问题本身不复杂但要按“头文件、lib、dll各就各位”的思路检查缺一个都不行。5.2 窗口能启动但画面一片黑或闪个不停现象窗口出来了但全黑或者画面一闪一闪、棋子拖影严重。原因黑屏往往是display函数里没有先调glClear或者绘制完没调glutSwapBuffers闪烁则是glutInitDisplayMode漏了GLUT_DOUBLE单缓冲模式下每次重绘都在用户眼前完成视觉上是闪的。解决先确认双缓冲模式已开然后检查display回调里是否每次都是“清屏→绘制→交换”三件套。另一个隐蔽问题是修改了棋盘全局变量后忘了调用glutPostRedisplay窗口不会主动重绘落子后画面纹丝不动看起来像交互失效。凡是外部事件改了游戏状态记得标记重绘。5.3 远程桌面或虚拟机里报 failed to initialize graphics backend for OpenGL现象代码在别人电脑上跑得好好的自己拿到远程桌面或虚拟机里一启动窗口没弹出来控制台甩出一行类似“failed to initialize graphics backend for opengl”的错误。原因远程桌面和多数虚拟机的默认图形环境不提供硬件OpenGL上下文glutCreateWindow拿不到渲染上下文直接失败退出。这不是代码逻辑的问题是运行环境缺GPU能力。解决演示前先在新机器上跑一个最简单的glut空窗口程序能起窗口再上完整项目。远程开会时不要指望机器上现跑OpenGL提前录制演示片段或换本地实体机是更稳的预案虚拟机里可以试着装虚拟显卡驱动或更替软件渲染后端但为了交一次作业去折腾底层图形栈很不划算。5.4 MCTS跑得太慢模拟次数一高就卡住现象AI每步要思考5到10秒点击落子后整个窗口像死机棋盘迟迟不更新。原因先看编译配置Debug模式下MCTS的模拟循环会慢3到5倍这是最常见的原因。其次是模拟函数内部的Board拷贝——每检查一个合法落点就复制一次完整棋盘遍历四五十个空位就多出几十次复制再把模拟次数拉到五万总开销直接爆掉。解决先切成Release跑一遍测速还是慢就砍模拟次数到5000看单步延迟是否可接受。代码层面把applyMove从“传值拷贝”改成“原地试下再回滚”合法落点检查的拷贝开销能削掉一大截。我自己的底线是单步不超过1秒否则期末演示时台下观众会失去耐心。5.5 棋面hash缓存误判命中后要二次校验现象为了省树节点内存我用64位Zobrist hash给棋面做缓存结果AI偶尔走出明显不合理的着法甚至把同一棋面按上一次的评估结果直接出招。原因64位hash不是零碰撞概率MCTS跑几十万次模拟后某对撞上的棋面复用了错误统计恰好后续又走了那条路表现就是“莫名送死”。另一个问题是节点池只增不减模拟局数上去之后内存涨个不停。解决hash只用来索引命中后拿完整棋面做一次memcmp确认再复用统计。更省心的做法是干脆以完整棋面对key9×9的Board拷贝才81字节直存直比换来的是正确性代价几乎可以忽略。内存问题则要在节点析构时正确处理父子关系树搜索结束后整棵释放避免递归深析构。6. 更实用的棋力进阶启发式模拟与命令行自对弈验证期末作业交到“能跑、能赢”还不够老师一旦追问“你的AI到底会不会下”棋力就是分水岭。两个改动性价比最高。第一个是给模拟阶段的随机落子加倾向性不要均匀随机先过滤掉落下去立刻没气的点再优先选择“能提掉对方棋子”的位置。这个启发式不需要围棋知识就一句话——优先提子、其次堵气模拟质量会明显提升因为随机对局里双方会更早碰撞出胜负MCTS拿到的信号不再是漫长的随机散步。第二个是给AI加固定思考时间而不是固定模拟次数。同样一万次模拟老笔记本要一秒新台式机只要零点三秒时间盒方案让AI在分配到的时段内尽量多跑棋力相对稳定。代码里用std::chrono记起步时刻循环里检查是否超时即可改动很小演示体验却稳很多。验证方法我强烈建议做一个命令行自对弈模式不启动glut窗口纯逻辑跑黑对黑、黑对白各两百局统计胜率差。这比肉眼观棋可靠得多。我自己的血泪经验是上学期拿纯UCT版本和加了“优先提子”启发式的版本对弈前五十局看不出明显差距两百局后才拉开四个百分点如果只拿几局结果拍板很容易把随机噪声当成棋力。// 命令行入口示例./gomoku_ai --selfplay 200 // 输出黑胜率与白胜率用于比较两个版本的棋力 for (int g 0; g games; g) { Board b; int player (g % 2 0) ? BLACK : WHITE; int rootPlayer player; while (true) { int move pickMCTS(b, player, timeLimitMs); int res applyMove(b, move / N, move % N, player); if (res 2) { blackWin (rootPlayer BLACK ? 1 : 0); break; } if (moves N * N) break; // 平局 player -player; } }自对弈是我每版AI上线前必走的流程它把棋力评估从“玄学”变成可重复的数据。终版前记得把所有调参结论写进实验记录C取多少、模拟多少次、启发式开关在哪、某配置下两百局胜率是多少。这份记录就是答辩现场最有说服力的材料。最后再说一句老实话别把模拟次数拉满到影响交互机器不带你赌希望帮到你。本文还有配套的精品资源点击获取 不围棋AI实现指南：C++规则、MCTS棋力与OpenGL界面
简介基于C实现的不围棋No-Go游戏完整源码是计算概论课程期末大作业的典型项目适合正在学习C、游戏编程或人工智能算法的学生参考。项目采用蒙特卡洛树搜索MCTS驱动AI同时提供MinMax对照实现界面基于OpenGL glut工具库。代码完整实现了不围棋规则气与提子判定、落子吃子判负、自杀判负、禁止空手pass以及黑棋首手禁占天元等细节并支持存档与Botzone在线对战。压缩包共57个文件含14个cpp源文件、14个头文件、17个bmp图片素材以及项目配置、存档、说明文档等整体仅2.2MB结构紧凑清晰。已有298人学习下载。通过学习源码读者可掌握MCTS与MinMax两种AI算法的落地写法、C图形界面搭建方法、围棋类棋局判定与博弈逻辑的完整实现思路便于在此基础上完成同类课程作业、毕业设计或进一步二次开发。1. 计算概论期末大作业的不围棋方案C规则、MCTS棋力、glut界面计算概论期末大作业里“不围棋”可能是最难让老师眼前一亮的题目规则看起来像围棋赢法却和围棋完全相反AI还得真有棋力。标题里的组合方案——用C写规则与搜索、用蒙特卡洛树搜索MCTS做AI决策、用OpenGL的glut工具库画棋盘棋子——是我见过最稳的一条路逻辑全部收在C层不依赖外部AI库报告好写演示也直观。这篇就照着这个组合从规则定义、MCTS落地到glut界面一步步讲透适合正在做这道大作业的学生也适合想最小成本把手伸进MCTS和OpenGL里的C从业者。2. 先让程序懂不围棋规则胜负判定、数据结构与提子实现2.1 不围棋的胜负判定与禁手三条规则先写进代码不围棋和围棋共用“气”和“提子”的体系一颗棋子看上下左右四个十字交叉点空着就算一口气一个连通块所有气的总和为零就把这个块从棋盘上提走。区别全在胜负目标上——围棋比谁围的地多不围棋则是“谁提掉对方的最后一颗棋子谁立刻获胜”。棋盘下满且没人被吃光判和。动手写代码前必须先把三条判定固化到程序里。第一条是自杀禁手落子后己方形成一个无气块且没有因为提掉对方而获得气这一步非法。第二条是提子优先落子点旁边的对方连通块若气为零先把它提掉再检查己方死活。第三条是终局判定提子后对方棋盘上的棋子数为零落子方直接胜。这里和围棋最大的差异在于不围棋每一步的胜负反馈都很强——模拟局很容易跑到终点这对MCTS是天然友好的条件。常见实现会把棋盘固定为9×9黑白轮流落子黑先。9×9意味着最多81手终局不会拖太长MCTS的随机模拟单局开销也很小。如果做19×19纯随机模拟的信号会被稀释得很厉害棋力会明显下降期末演示时容易翻车。先把规模锁在9×9后面想扩展再单独说。2.2 棋盘数据结构与提子判定一段可直接改的C实现棋盘用定长二维数组最省事。grid[r][c]取三个值0代表空1代表黑-1代表白。这里选-1而不是2是因为取对方颜色只需要-color后面提子判断能少写一个分支。BFS找连通块和气我一律用固定数组加方向偏移9×9规模下这种写法比并查集直观得多。#include queue #include vector #include cstring #include utility const int N 9; const int EMPTY 0, BLACK 1, WHITE -1; struct Board { int grid[N][N]; Board() { memset(grid, 0, sizeof(grid)); } // 返回包含(r,c)的连通块的所有坐标 std::vectorstd::pairint,int blockOf(int r, int c) const { const int dr[4] {-1, 1, 0, 0}; const int dc[4] {0, 0, -1, 1}; int color grid[r][c]; bool vis[N][N] {false}; std::queuestd::pairint,int q; std::vectorstd::pairint,int res; vis[r][c] true; q.push({r, c}); while (!q.empty()) { auto [x, y] q.front(); q.pop(); res.push_back({x, y}); for (int k 0; k 4; k) { int nx x dr[k], ny y dc[k]; if (nx 0 || nx N || ny 0 || ny N) continue; if (grid[nx][ny] color !vis[nx][ny]) { vis[nx][ny] true; q.push({nx, ny}); } } } return res; } };blockOf用BFS收集整个连通块后续提子需要知道“这一块具体有哪些坐标”只算气的个数不够用。注意vis数组在这里每次落子都会重新创建9×9棋盘上这个开销无所谓但MCTS跑上万次模拟时频繁分配二维数组会拖慢速度优化时可以改成int vis[N][N]加时间戳的写法清零成本从O(N²)降到O(1)。提子与落子合法性判断是整份代码最核心的函数我把它放在一个applyMove里返回值三种0合法继续、1非法禁手、2提掉对方最后一子获胜。先落子、再提对方、最后查己方这个顺序不能反。// 在(r,c)落 color 子返回 1 非法2 落子方直接获胜0 合法 int applyMove(Board b, int r, int c, int color) { if (b.grid[r][c] ! EMPTY) return 1; b.grid[r][c] color; int opp -color; const int dr[4] {-1, 1, 0, 0}; const int dc[4] {0, 0, -1, 1}; std::vectorstd::pairint,int removed; // 第一步提掉所有无气的对方连通块 for (int k 0; k 4; k) { int nr r dr[k], nc c dc[k]; if (nr 0 || nr N || nc 0 || nc N) continue; if (b.grid[nr][nc] ! opp) continue; auto block b.blockOf(nr, nc); bool alive false; for (auto [x, y] : block) { for (int t 0; t 4; t) { int nx x dr[t], ny y dc[t]; if (nx 0 nx N ny 0 ny N b.grid[nx][ny] EMPTY) { alive true; break; } } if (alive) break; } if (!alive) { for (auto [x, y] : block) removed.push_back({x, y}); } } for (auto [x, y] : removed) b.grid[x][y] EMPTY; // 第二步提子后对方棋盘为空直接获胜 int oppCount 0; for (int i 0; i N; i) for (int j 0; j N; j) if (b.grid[i][j] opp) oppCount; if (oppCount 0) return 2; // 第三步己方落子后无气判禁手并撤销整步 auto myBlock b.blockOf(r, c); for (auto [x, y] : myBlock) for (int t 0; t 4; t) { int nx x dr[t], ny y dc[t]; if (nx 0 nx N ny 0 ny N b.grid[nx][ny] EMPTY) return 0; // 还有气合法 } for (auto [x, y] : removed) b.grid[x][y] opp; // 还原被提子 b.grid[r][c] EMPTY; return 1; }这段逻辑的要点是“先提后查”有些棋形看起来是自杀但落子后先提掉对方一块己方就有了气这在围棋里是合法着法。另一个细节是撤销时必须把被提的对方棋子原样放回去同时清掉己方刚落的子否则棋盘状态被污染MCTS模拟的后续对局全是错的。这个还原动作是新人最容易漏的模拟结果一旦混入坏局面胜率统计整个失真。2.3 BFS算气还是并查集维护连通块选型理由与实现边界提子判断里最费时的就是blockOf每步最多81格全盘BFS一次也就几百次访问。MCTS跑一万次模拟每局平均几十手总调用次数在几十万量级这时的瓶颈反而不是算法复杂度而是数组分配和函数调用开销。并查集的路子适合把棋盘维护成动态连通结构每次落子只影响附近几个点合并连通块很快但“提子”操作要整块重置父指针写起来容易出错。以我的经验期末大作业完全没必要上并查集先用BFS版本把棋力跑通再用命令行自对弈验证正确性比一开始就追求性能实在。真要到优化阶段优先做两件事一是把vis数组换成时间戳复用省去逐次初始化的开销二是把applyMove改成原地试下再回滚避免每次模拟都复制整个Board。这两步做完单线程跑两三万次模拟已经足够应付9×9棋盘。3. 蒙特卡洛树搜索怎么落地四步循环、UCB参数与C核心类3.1 MCTS四步循环选择、扩展、模拟、回传如何分工蒙特卡洛树搜索把一次对局拆成四个阶段每个阶段各干一件事。第一步选择从根节点出发沿着子节点往下走每一步都挑“当前最值得看”的节点直到叶子。第二步扩展给叶子节点生成合法落子挂上子节点。第三步模拟从某个子节点开始黑白双方随机落子一路冲到终局。第四步回传把模拟结果从该节点一路传回根节点更新路径上每个节点的访问次数和胜利次数。不围棋特别适合这套流程原因是终局判定足够干净。随机模拟阶段不需要工程师设计“围空”“做眼”这些概念只要别下禁手走到有人被提光或棋盘填满胜负立刻见分晓。模拟局多了某个落点赢过多少次统计上就有区分度。树节点代表“一个具体棋面加轮到谁走”。根节点是当前真实棋面每个子节点代表“在父节点棋面上走一步合法棋之后的新棋面”。所以MCTS本质上是在拿“模拟次数”换“对棋面的评估精度”而不是像传统搜索那样硬算每步的精确收益。这也是为什么大家常把模拟阶段当黑匣子——它不需要多聪明只要终局判定正确统计就会自己说话。3.2 两个必调参数UCB的探索系数C和模拟次数N选择阶段用UCB公式给每个子节点打分UCB(child) child.wins / child.visits C * sqrt(log(parent.visits) / child.visits)前半部分是胜率代表这个节点已知的棋力后半部分是探索奖励访问次数越少的节点分数越高。C就是探索系数控制AI愿意试冷门棋的程度。C太大AI会频繁下一些明显不行的点棋力变弱C太小AI过早锁死一个分支错过更优解。我在9×9不围棋上常用1.4左右先手后手都试过这个值比较稳。参数常规取值调大的影响调小的影影响探索系数C0.72.0更多尝试冷门点落子更“散”更倾向已知高胜率分支模拟次数N500020000棋力提升单步耗时线性增加反应快棋力下降随机模拟规避禁手必须开启避免模拟局作废模拟局失真棋力不可信模拟次数直接决定单步耗时这个参数和机器性能强相关。我的经验是Release编译下9×9棋盘跑一万次模拟大概在0.2到0.5秒Debug编译会慢上好几倍。演示前先在目标机器上测一轮别到台上才暴露卡顿。调参的基本方法是让AI自己跟自己下几十局先手后手各统计一次胜率选一个延迟可接受且胜率不垮的N。网上搜MCTS相关笔记时也能看到一些默认值但机器不同抄过来的数字不一定适配你手上的代码。3.3 核心类与回溯更新给Node一份完整的棋面快照节点设计上我的选择是“每个节点保存一份完整棋面”而不是只保存一步棋。9×9棋盘81个整数拷贝一次开销很小换来的是回溯逻辑极其简单——模拟结束后顺着路径把胜负数传上去就行不需要反向走棋、撤销落点。这个取舍在16×16以上棋盘可能变奢侈但在本项目范围里是最省脑力的。#include cmath #include vector #include random struct MCTSNode { Board board; // 完整棋面快照 int player; // 该节点的落子方1 黑 -1 白模拟时从该节点算起 double wins 0.0; int visits 0; bool expanded false; std::vectorMCTSNode* children; MCTSNode* parent nullptr; double ucb(double C) const { if (visits 0) return 1e9; // 未访问节点永远优先 double exploit wins / visits; double explore C * std::sqrt(std::log(parent-visits) / visits); return exploit explore; } };visits初始为0时UCB分数给一个极大值保证每个孩子至少被选中一次这是MCTS的标准做法不然某些合法落点永远没机会被模拟到。wins用double而不是int是因为平局会按0.5计模拟结果不总是整数。主循环就是把这四步串起来MCTSNode* root new MCTSNode(); // 根节点棋面设为当前局 for (int sim 0; sim simulations; sim) { // 选择一直走到叶子 std::vectorMCTSNode* path; MCTSNode* cur root; while (cur-expanded !cur-children.empty()) { MCTSNode* best nullptr; double bestScore -1e9; for (MCTSNode* child : cur-children) { double s child-ucb(C); if (s bestScore) { bestScore s; best child; } } cur best; path.push_back(cur); } // 扩展展开第一个未扩展的节点 if (!cur-expanded) { // 生成所有合法落子创建子节点 for (int i 0; i N; i) for (int j 0; j N; j) { Board t cur-board; if (applyMove(t, i, j, cur-player) ! 1) { auto* child new MCTSNode(); child-board t; child-player -cur-player; child-parent cur; cur-children.push_back(child); } } cur-expanded true; // 如果叶子有多个孩子先选第一个进去模拟 if (!cur-children.empty()) { cur cur-children[0]; path.push_back(cur); } } // 模拟随机下到终局平局回传 0.5 double reward simulate(cur-board, root-player, cur-player); // 回传路径上所有节点更新统计 for (MCTSNode* n : path) { n-visits; n-wins reward; } }这个循环是“一个模拟”的完整过程。注意reward是以根节点落子方视角算的所以回传时路径每个节点都加同一个值。如果你用子节点视角算reward回传时要根据奇偶层数取正负两种约定都行但必须和wins的累计方式保持一致混用会让你调参时怀疑人生。平局返回0.5是我后来加上的不围棋棋盘不大平局不算罕见按0/1处理会让AI对某些稳妥局面产生错误偏好。模拟函数本身也要过滤禁手否则随机下出非法棋会提前“结束”一局统计出的奖励是脏的int simulate(Board b, int curPlayer, int rootPlayer) { int moves 0; while (moves N * N) { std::vectorint legal; for (int i 0; i N; i) for (int j 0; j N; j) { Board t b; if (applyMove(t, i, j, curPlayer) ! 1) legal.push_back(i * N j); } if (legal.empty()) return 0; // 无棋可下当前方输 int idx legal[rand() % legal.size()]; int r idx / N, c idx % N; int res applyMove(b, r, c, curPlayer); moves; if (res 2) return (curPlayer rootPlayer) ? 1 : 0; curPlayer -curPlayer; } return 0.5; // 棋盘填满且未分胜负 }模拟里对每个空点都拷贝一次Board再调用applyMove这是最简单的写法但不是最快的。实测里这个t的拷贝会在热路径上反复出现优化时可以改成“先试下、非法再回滚”的原地模式一台普通笔记本上能把十万次模拟的耗时压缩三分之一以上。先把功能做对再动手抠这个细节。4. 用OpenGL的glut库把棋盘画出来窗口初始化、绘制与鼠标交互4.1 glut窗口初始化glutMainLoop之前的调用顺序glut有一个怪脾气调用顺序错一个就黑屏或者窗口压根不出现。常规的初始化序列是固定的glutInit、glutInitDisplayMode、glutInitWindowSize、glutCreateWindow然后设置视图和回调最后glutMainLoop。这几行里最容易被忽略的是glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB)漏了GLUT_DOUBLE会让画面闪烁到没法看因为缓冲只有一个绘制一次就被交换一次。#include GL/glut.h int main(int argc, char** argv) { glutInit(argc, argv); glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB); glutInitWindowSize(720, 720); glutInitWindowPosition(80, 80); glutCreateWindow(不围棋 - MCTS); glClearColor(0.92f, 0.84f, 0.70f, 1.0f); // 木色背景 gluOrtho2D(-0.5, 9.5, -0.5, 9.5); // 棋盘映射到 0..8 glutDisplayFunc(display); glutMouseFunc(onMouse); glutMainLoop(); return 0; }gluOrtho2D设置了正交投影范围这里留出半格边距棋盘线画在0到8之间棋子中心正好落在整数坐标上。注意gluOrtho2D必须在窗口创建之后调用因为它依赖当前OpenGL上下文我把绘制棋盘背景色放在CreateWindow之后、回调注册之前习惯上是没问题的。glutMainLoop是阻塞调用它会一直在内部消息循环里转直到窗口关闭所以主循环之后不要放任何代码。4.2 绘制棋盘与棋子从glClear到glutSwapBuffers绘制回调里做的事情顺序很清楚清屏、画网格、画棋子、交换缓冲。双缓冲模式下glClear和glSwapBuffers必须成对出现只画不换窗口永远显示旧画面只换不清棋盘会叠成废纸。void display() { glClear(GL_COLOR_BUFFER_BIT); // 网格线 glColor3f(0.25f, 0.25f, 0.25f); glBegin(GL_LINES); for (int i 0; i N; i) { glVertex2f(i, 0.0f); glVertex2f(i, N - 1.0f); glVertex2f(0.0f, i); glVertex2f(N - 1.0f, i); } glEnd(); // 棋子 for (int r 0; r N; r) for (int c 0; c N; c) { if (board.grid[r][c] EMPTY) continue; if (board.grid[r][c] BLACK) glColor3f(0.10f, 0.10f, 0.10f); else glColor3f(0.95f, 0.95f, 0.95f); drawCircle(c, r, 0.40f); // 圆心(c,r)半径0.4 } glutSwapBuffers(); }drawCircle一般用GL_TRIANGLE_FAN画一个实心圆从圆心出发把圆周切几十个顶点连起来。黑子白子这种纯色绘制不需要纹理OpenGL基础绘制足够。想加“上一手标记”可以在该位置用glColor3f画一个高亮小方框或空心圆但记得上一次落子的坐标要单独存一个全局变量绘制时在这里多画一笔。4.3 鼠标点击坐标换算与AI落子的两种接法glut的鼠标回调拿到的坐标原点在窗口左上角y轴向下而正交投影里原点在左下角y轴向上。换算错位会让点击的列对、行反棋子落去对面棋盘。我常用的公式是void onMouse(int button, int state, int x, int y) { if (button ! GLUT_LEFT_BUTTON || state ! GLUT_DOWN) return; int row 8 - (int)(y * 9.0 / 720.0); // 行号翻转 int col (int)(x * 9.0 / 720.0); // 校验边界落子 }窗口尺寸是720×720棋盘逻辑坐标是0到8的9格所以一个像素步长对应9.0 / 720.0。行翻转是这里的经典陷阱我见过不少作业棋盘上下颠倒原因就是渲染时没翻、事件里也没翻两边各错一次反而看起来“正常”实际棋形是镜像的MCTS模拟和界面显示不一致AI会走出让观众一头雾水的棋。AI落子和glut主循环的配合另有一个坑鼠标回调里直接跑一万次MCTS模拟界面会僵住一两秒看起来像死机。常见做法有两种。第一种是把MCTS放在回调里同步执行简单但体验差适合赶进度第二种是用glutIdleFunc注册一个空闲函数每一帧只做几百次模拟攒够一定局数再落子界面不卡玩家能肉眼看到棋子在思考间隙出现。第二种要引入一个“是否轮到AI思考”的状态变量逻辑稍复杂但演示效果好不少我建议期末展示用这个。5. 期末大作业避坑记录glut安装、黑屏和MCTS卡顿怎么排查5.1 在Visual Studio里装glut头文件、lib和dll的翻车点现象照着网上的“opengl在visual studio中怎么安装”一类教程把freeglut下载回来解压放进项目编译时报“无法打开包含文件glut.h”或链接报LNK2019找不到glutInit。原因大部分教程只让你把头文件加到include目录却漏了库目录和dll的放置。glut要装齐三样glut.h、glut32.lib或freeglut.lib、glut32.dll或freeglut.dll。另外位数必须匹配64位工程配32位lib链接阶段一定报错。解决项目属性里分别配置包含目录和库目录#pragma comment(lib, glut32.lib)直接写在源码顶部也能跳过配置步骤dll放到exe同目录或放到系统PATH里。用VSCode的话除了c_cpp_properties.json配include路径还要在tasks.json的链接参数里把lib路径加进去很多人配了头文件提示、编译阶段又栽一次。这套环境问题本身不复杂但要按“头文件、lib、dll各就各位”的思路检查缺一个都不行。5.2 窗口能启动但画面一片黑或闪个不停现象窗口出来了但全黑或者画面一闪一闪、棋子拖影严重。原因黑屏往往是display函数里没有先调glClear或者绘制完没调glutSwapBuffers闪烁则是glutInitDisplayMode漏了GLUT_DOUBLE单缓冲模式下每次重绘都在用户眼前完成视觉上是闪的。解决先确认双缓冲模式已开然后检查display回调里是否每次都是“清屏→绘制→交换”三件套。另一个隐蔽问题是修改了棋盘全局变量后忘了调用glutPostRedisplay窗口不会主动重绘落子后画面纹丝不动看起来像交互失效。凡是外部事件改了游戏状态记得标记重绘。5.3 远程桌面或虚拟机里报 failed to initialize graphics backend for OpenGL现象代码在别人电脑上跑得好好的自己拿到远程桌面或虚拟机里一启动窗口没弹出来控制台甩出一行类似“failed to initialize graphics backend for opengl”的错误。原因远程桌面和多数虚拟机的默认图形环境不提供硬件OpenGL上下文glutCreateWindow拿不到渲染上下文直接失败退出。这不是代码逻辑的问题是运行环境缺GPU能力。解决演示前先在新机器上跑一个最简单的glut空窗口程序能起窗口再上完整项目。远程开会时不要指望机器上现跑OpenGL提前录制演示片段或换本地实体机是更稳的预案虚拟机里可以试着装虚拟显卡驱动或更替软件渲染后端但为了交一次作业去折腾底层图形栈很不划算。5.4 MCTS跑得太慢模拟次数一高就卡住现象AI每步要思考5到10秒点击落子后整个窗口像死机棋盘迟迟不更新。原因先看编译配置Debug模式下MCTS的模拟循环会慢3到5倍这是最常见的原因。其次是模拟函数内部的Board拷贝——每检查一个合法落点就复制一次完整棋盘遍历四五十个空位就多出几十次复制再把模拟次数拉到五万总开销直接爆掉。解决先切成Release跑一遍测速还是慢就砍模拟次数到5000看单步延迟是否可接受。代码层面把applyMove从“传值拷贝”改成“原地试下再回滚”合法落点检查的拷贝开销能削掉一大截。我自己的底线是单步不超过1秒否则期末演示时台下观众会失去耐心。5.5 棋面hash缓存误判命中后要二次校验现象为了省树节点内存我用64位Zobrist hash给棋面做缓存结果AI偶尔走出明显不合理的着法甚至把同一棋面按上一次的评估结果直接出招。原因64位hash不是零碰撞概率MCTS跑几十万次模拟后某对撞上的棋面复用了错误统计恰好后续又走了那条路表现就是“莫名送死”。另一个问题是节点池只增不减模拟局数上去之后内存涨个不停。解决hash只用来索引命中后拿完整棋面做一次memcmp确认再复用统计。更省心的做法是干脆以完整棋面对key9×9的Board拷贝才81字节直存直比换来的是正确性代价几乎可以忽略。内存问题则要在节点析构时正确处理父子关系树搜索结束后整棵释放避免递归深析构。6. 更实用的棋力进阶启发式模拟与命令行自对弈验证期末作业交到“能跑、能赢”还不够老师一旦追问“你的AI到底会不会下”棋力就是分水岭。两个改动性价比最高。第一个是给模拟阶段的随机落子加倾向性不要均匀随机先过滤掉落下去立刻没气的点再优先选择“能提掉对方棋子”的位置。这个启发式不需要围棋知识就一句话——优先提子、其次堵气模拟质量会明显提升因为随机对局里双方会更早碰撞出胜负MCTS拿到的信号不再是漫长的随机散步。第二个是给AI加固定思考时间而不是固定模拟次数。同样一万次模拟老笔记本要一秒新台式机只要零点三秒时间盒方案让AI在分配到的时段内尽量多跑棋力相对稳定。代码里用std::chrono记起步时刻循环里检查是否超时即可改动很小演示体验却稳很多。验证方法我强烈建议做一个命令行自对弈模式不启动glut窗口纯逻辑跑黑对黑、黑对白各两百局统计胜率差。这比肉眼观棋可靠得多。我自己的血泪经验是上学期拿纯UCT版本和加了“优先提子”启发式的版本对弈前五十局看不出明显差距两百局后才拉开四个百分点如果只拿几局结果拍板很容易把随机噪声当成棋力。// 命令行入口示例./gomoku_ai --selfplay 200 // 输出黑胜率与白胜率用于比较两个版本的棋力 for (int g 0; g games; g) { Board b; int player (g % 2 0) ? BLACK : WHITE; int rootPlayer player; while (true) { int move pickMCTS(b, player, timeLimitMs); int res applyMove(b, move / N, move % N, player); if (res 2) { blackWin (rootPlayer BLACK ? 1 : 0); break; } if (moves N * N) break; // 平局 player -player; } }自对弈是我每版AI上线前必走的流程它把棋力评估从“玄学”变成可重复的数据。终版前记得把所有调参结论写进实验记录C取多少、模拟多少次、启发式开关在哪、某配置下两百局胜率是多少。这份记录就是答辩现场最有说服力的材料。最后再说一句老实话别把模拟次数拉满到影响交互机器不带你赌希望帮到你。本文还有配套的精品资源点击获取