简介一套基于C与OpenGLglut实现的不围棋No-Go游戏完整源码源自计算概论课程期末大作业适合C进阶学习、算法实践及博弈AI开发的读者参考。游戏严格遵循9×9棋盘、黑棋先手、禁止吃子、禁止自杀与禁止pass的不围棋规则并加入黑棋首手禁着中心点的附加平衡规则AI采用蒙特卡洛树搜索MCTS可在Windows 10平台直接编译运行。压缩包共57个文件、约2.2MB含14个cpp与14个h源码覆盖棋盘规则、MCTS智能体、OpenGL场景渲染、存档管理等模块、17张bmp图片资源及Visual Studio工程文件sln/vcxproj目录划分清晰。目前已有298人浏览学习对希望掌握MCTS原理、不围棋规则建模或OpenGL交互界面的读者而言这份源码提供了可直接运行的完整样例可快速上手二次开发也可作为课程设计或竞赛项目的参考底稿。1. 不围棋期末大作业表面是反五子棋实则是三个模块的缝合题不围棋的规则一句话就能讲完在 15×15 棋盘上黑白交替落子谁先让自己连成五个同色棋子谁就输。这题目是“计算概论”期末大作业里的经典缝合型用 C 写完棋盘规则和搜索逻辑再用 OpenGL 的 glut 工具库把界面撑起来AI 用蒙特卡洛树搜索MCTS做决策。很多同学在这三块里轮流翻车MCTS 搜了半天出不了第一手glut 窗口点了没反应或者 AI 明明能赢却偏偏下出“送死手”。这篇笔记就顺着规则判定、MCTS 的 C 实现、glut 窗口三块讲清楚重点是能直接照着改的参数和踩过的坑适合要交大作业或者想拿一个完整项目练 C 数据结构和图形界面配合的人。2. 规则与架构把“谁落谁输”翻译成能判定的 C 函数动代码之前先把不围棋的规则锁死。这个棋在民间变体不少有的版本带禁手不许下出长连、双三、双四有的版本只管五连。期末时间有限我一般建议做简化版——只判断“落子后同色棋子在横、竖、两条斜线方向上连续数是否达到 5”达到就判负。理由很实在完整禁手规则会让合法动作集合变得非常复杂MCTS 的动作筛选和模拟走子都得跟着改工作量直接翻倍。只要在 README 里写清楚“本作业采用简化版不围棋规则长连判负不做禁手”评分老师不会挑理。2.1 棋盘与胜负判定四方向连子计数一次落子定胜负棋盘用二维数组最直接。15×15 的大小刚好覆盖五连的判断又不会让搜索空间大到离谱。数组里 0 表示空位1 表示黑棋2 表示白棋。胜负判定的核心是每次落子后只以这个落点为中心沿四个方向朝两边数连续同色棋子的数量。四个方向分别是水平、竖直、主对角线、副对角线。// board.h 里的核心判定函数 const int SIZE 15; int grid[SIZE][SIZE]; // 0 空位1 黑棋2 白棋 bool in_range(int x, int y) { return x 0 x SIZE y 0 y SIZE; } // 判断 (x, y) 落下一颗 color 棋子后是否构成五连及以上 bool forms_five(int x, int y, int color) { int dx[4] {1, 1, 0, 1}; int dy[4] {0, 1, 1, -1}; for (int dir 0; dir 4; dir) { int cnt 1; // 落子本身算一颗 for (int step 1;; step) { int nx x step * dx[dir]; int ny y step * dy[dir]; if (!in_range(nx, ny) || grid[nx][ny] ! color) break; cnt; } for (int step 1;; step) { int nx x - step * dx[dir]; int ny y - step * dy[dir]; if (!in_range(nx, ny) || grid[nx][ny] ! color) break; cnt; } if (cnt 5) return true; } return false; }函数里最关键的是 5而不是 5。我见过不少同学写成 5导致长连六颗、七颗时不判负AI 和玩家都会在明明输了的局里继续走。改成 5之后规则就很干净只要这一手让自己连出五颗及以上立刻结束。由于每次只查落点周边复杂度和棋盘大小无关只和连子长度相关可以认为是一次 O(1) 级别的查询MCTS 里模拟几千局时这个开销不能小看。2.2 模块怎么拆board、mcts、renderer 三个类各管哪摊不围棋这种项目最容易死磕在“所有代码堆在一个 main.cpp 里”。等 MCTS 和 glut 接进来全局变量互相踩改一个功能崩三个地方。我一般把项目拆成三块Board负责棋盘状态、落子、胜负判定、是否下满MCTS只负责给定当前局面返回一个落子坐标Renderer负责 OpenGL 绘制和鼠标回调。三个类之间单向依赖MCTS 调用 Board 的只读接口Renderer 也调用 Board 的只读接口MCTS 和 Renderer 互不感知。// board.h 的核心接口AI 和界面都只跟它打交道 enum MoveResult { MOVE_OK, MOVE_LOSE, MOVE_FULL }; class Board { public: MoveResult apply(int x, int y, int color); // 落子并判断是否被判负 bool is_full() const; // 棋盘是否下满 void clear(); // 新一局开始时清盘 int at(int x, int y) const; // 读某位置棋子颜色 private: int grid[SIZE][SIZE]; };apply的返回值要设计得明确MOVE_OK表示落子成功且没有成五MOVE_LOSE表示落子后自己构成了五连落子方判负MOVE_FULL表示棋盘已满落子无效。有了这个返回值main 里的状态流转就很直观。界面层和 AI 层都不要自己去数棋盘统一通过at()读状态否则容易出现逻辑各写一份、判定结果对不上的情况。期末评分时“模块划分清晰”通常是独立的加分项比你多写一个启发式函数管用得多。2.3 交互状态机玩家落子、AI 计算、胜负展示的时序界面和 AI 的配合需要一个小小的状态机否则鼠标回调和 MCTS 计算会乱套。我习惯用三个状态PLAYER_TURN等待玩家落子AI_TURN表示 AI 正在思考或即将落子GAME_OVER表示有一方已经判负。玩家落子成功且没有输状态切到AI_TURNAI 落子成功且没有输状态切回PLAYER_TURN。enum GameState { PLAYER_TURN, AI_TURN, GAME_OVER }; GameState state PLAYER_TURN;这里有个看起来小、实际影响很大的点AI 计算期间必须禁止鼠标落子。否则玩家疯狂点棋盘逻辑上会同时出现多次落子AI 搜索用的局面和界面显示的局面错位最后保存的棋谱根本没法复盘。解决方式很简单在鼠标回调开头就检查state ! PLAYER_TURN直接返回。这个状态机在项目里值不了多少行代码但没有它后面接上 glut 的异步回调时会非常痛苦。3. MCTS 算法落地从 UCT 公式到能跑的 C 搜索循环蒙特卡洛树搜索核心思想是“不评估局面只统计胜负”。传统博弈 AI 像 Alpha-beta 剪枝要写启发式评估函数告诉程序“黑棋目前多活二所以好一点”。不围棋恰恰最难写这种评估局面接近时谁优谁劣很难量化而终局条件又极其清晰——谁成五谁输。MCTS 不吃这一套它靠大量随机对局来估计每个落子的胜率从当前节点出发反复做“选择、扩展、模拟、回传”四步循环访问次数越多的节点越有可能是好手。3.1 蒙特卡洛树搜索四步循环以及为什么适合“无启发式”的游戏四步循环里选择是沿着已有搜索树用 UCB1 公式挑访问价值最高的子节点往下走直到某个叶子节点扩展是给这个叶子节点生成合法的后续落子候选并挑一个加入树中模拟是从新节点开始用极快的随机走子一直下到分出胜负或棋盘下满回传是把这局结果沿着路径写回每个节点更新访问次数和累计胜利数。四个步骤里模拟最耗费时间也是整个搜索的性能瓶颈。MCTS 适合不围棋的第二个理由是它对“搜索宽度”的容忍度比 Alpha-beta 高。不围棋每步合法落子最多 225 个Alpha-beta 想要效果好必须配合强剪枝和良好走子排序MCTS 靠随机模拟就能给出像样的落子建议代码量少一个数量级。对“计算概论”这种课程项目MCTS 是性价比最高的方案。第三个理由藏在“无启发式”里树不依赖人工知识给 AI 换一种变体规则比如棋盘改成 19×19不需要改搜索逻辑只改棋盘大小就行。3.2 节点数据结构与 UCB1别再每步重建整棵树MCTS 节点的 C 结构不复杂但有一个关键的工程决策不要每走一手都从零建树。玩家落子后上一轮搜索树里已经包含了对当前局面的研究对应落子的那个子节点以及它的整棵子树可以直接继承下来。我每次第一次写 MCTS 都忍不住每步重建结果 30 手之后 AI 耗时肉眼可见地翻倍。正确的做法是玩家落子后在旧树的根节点子节点里找到那个坐标把它提升为新根释放其它子树。// mcts.h 中的节点结构 struct Node { int x, y; // 本节点对应的落子坐标根节点记为 -1, -1 int color; // 这一手棋的颜色根节点为 0 Node* parent; std::vectorNode* children; int visits; // 访问次数 double wins; // 从本节点视角累计的胜局数 }; // UCB1 公式子节点访问 0 次时返回无穷大保证每个候选点先被探索一遍 double ucb1(Node* child, int totalVisits, double c) { if (child-visits 0) return 1e9; double exploit child-wins / child-visits; double explore c * std::sqrt(std::log((double)totalVisits) / child-visits); return exploit explore; } // 选择阶段在所有子节点里挑 UCB1 值最高的 Node* best_child(Node* node, double c) { double bestScore -1e18; Node* best nullptr; for (Node* child : node-children) { double score ucb1(child, node-visits, c); if (score bestScore) { bestScore score; best child; } } return best; }UCB1 公式的常数c控制“探索”和“利用”的平衡。c取小一些AI 会更倾向走已经验证出高胜率的分支取大一些AI 更愿意尝试没怎么走过的点。不围棋我习惯取 1.4这是很多棋类 MCTS 实现里的常用起点值。注意wins的视角如果节点代表黑棋落子那么黑棋赢就记 1 分白棋赢记 0 分平局记 0.5 分。这个视角在回传时要一致否则整棵树的分数都是乱的AI 会表现为“越下越蠢”。3.3 模拟走子与两个必要的优化过滤送死手与限制模拟深度模拟阶段的随机走子不能完全随机。不围棋的特殊性在于如果随机模拟里某个落子会立刻让自己形成五连它直接决定了这一局的胜负而这些“送死手”在实际搜索里根本不应该进入候选。如果不过滤MCTS 会被大量立刻判负的模拟带偏导致 AI 明明有安全落点却总是选中那些让对手躺赢的位置。// 从某个局面开始随机模拟到终局colorToMove 表示当前轮到的颜色 int simulate(Board board, int colorToMove) { int cur colorToMove; while (!board.is_full()) { // legal_moves 必须忽略会让当前玩家立刻成五的落点 std::vectorstd::pairint,int candidates legal_moves(board, cur); if (candidates.empty()) return DRAW; // 局面下满视为平局 auto mv candidates[rand() % candidates.size()]; MoveResult res board.apply(mv.first, mv.second, cur); if (res MOVE_LOSE) return opponent(cur); // cur 落子成五判负 cur opponent(cur); } return DRAW; }这里有两个很容易遗漏的点。第一legal_moves不只是检查“坐标在棋盘内且为空”还要检查“落在这里不会让cur成五”。我见过一种笨办法在 simulate 里先 apply 再调forms_five若成五就撤销。这样也能工作但每次随机走子都要经历一遍完整的 apply 和撤销速度慢不少。更干净的做法是写一个apply_safe(move, color)接口落子后立刻查forms_five如果成五就回滚并把这个坐标从候选里剔除。第二rand()一定要记得先srand(time(nullptr))否则每次运行 AI 的模拟序列完全一样棋局固定看起来像“AI 只会背棋谱”。这是新手写 MCTS 最容易踩的随机数坑。模拟深度也要设防。不围棋棋盘 225 个空位如果模拟时一直下到填满才结束一盘模拟可能要执行上百次 apply搜索几千次模拟的耗时就很可观。我一般给模拟设定一个深度上限比如 30 步或剩余空位数的最小值到顶就按平局处理。这个限制对棋力影响很小因为不围棋大部分对局在几十手内就会分出胜负继续随机走下去只会增加噪声。配合根节点复用MCTS 在 15×15 棋盘上做 3000 次模拟单步耗时在普通笔记本上能压在一到两秒左右界面不会卡到让人想砸键盘。4. OpenGL glut 界面初始化、鼠标坐标换算与 AI 交替走棋界面这一块看起来是纯体力活但坑特别密集尤其是环境配置和坐标换算。glut 是 OpenGL 的一个工具库负责窗口管理、事件回调和简单绘制正好够画一个静态的棋盘加棋子不用自己写 X11 或 Win32 窗口代码。用 glut 的好处是代码短、上课讲过、系统跨平台缺点是它非常老派很多现代习惯用 freeglut 替代但接口基本一致。下面以 Windows Visual Studio 的常见做法为准因为“计算概论”的评测环境大多跑在这上面。4.1 Visual Studio 里安装 glut三件套、路径与链接器配置glut 在老版本 Visual Studio 里是“下载三个文件、复制到对应目录、改链接配置”的三步曲。三个文件是glut.h、glut32.lib和glut32.dll用 freeglut 的话对应文件名稍有不同接口兼容。常见做法是把glut.h放进 VS 的 include 目录glut32.lib放进 lib 目录glut32.dll和生成的 exe 放同一个目录。在较新版本的 VS 里也可以把这三个文件放进项目目录在项目属性里单独指定头文件路径和库目录好处是换一台电脑不用往系统目录里乱塞东西。项目里还需要配置链接器。右键项目打开“链接器 → 输入 → 附加依赖项”加上glut32.lib和opengl32.lib。如果用了glu相关函数还要加glu32.lib。这一步漏掉最常见的报错风格是“无法解析的外部符号__imp_glutInit”看着吓人实际就是链接器没找到库。用 vscode 配 c 环境时思路一样includePath 指向 glut.h 所在目录tasks.json 的 args 里加-lglut32 -lopengl32但 Visual Studio 下做课程作业更省心不推荐期末阶段折腾 vscode 交叉编译的问题。4.2 画棋盘与鼠标坐标换算窗口是上原点OpenGL 是下原点glut 主程序的结构非常固定先初始化 glut 和显示模式再创建窗口然后注册回调函数最后进入glutMainLoop。一个典型的 main 长这样int main(int argc, char** argv) { glutInit(argc, argv); // 必须先于创建窗口调用 glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB); glutInitWindowSize(640, 640); glutCreateWindow(不围棋 MCTS - 计算概论期末大作业); init_board(); glutDisplayFunc(on_render); // 重绘回调 glutMouseFunc(on_mouse); // 鼠标回调 glutReshapeFunc(on_reshape); // 窗口大小变化 glutMainLoop(); // 进入事件循环不返回 return 0; }绘制回调里只做一件事画网格、画所有棋子、交换缓冲区。不要在这里跑 MCTS。鼠标回调的坐标换算是个经典坑点glut 传给鼠标回调的 (x, y) 是以窗口左上角为原点、y 轴向下为正OpenGL 正交投影里默认 y 轴向上。不翻转直接映射你点棋盘上方的一个交叉点棋子会落在下方。void on_mouse(int button, int state, int mouseX, int mouseY) { if (button ! GLUT_LEFT_BUTTON || state ! GLUT_DOWN) return; if (state ! PLAYER_TURN) return; // AI 思考时忽略点击 int winW glutGet(GLUT_WINDOW_WIDTH); int winH glutGet(GLUT_WINDOW_HEIGHT); int gx (int)std::floor((mouseX * SIZE) / (double)winW); int gy (int)std::floor(((winH - mouseY) * SIZE) / (double)winH); // 翻转Y if (board.at(gx, gy) ! EMPTY) return; MoveResult res board.apply(gx, gy, BLACK); if (res MOVE_LOSE) { gameState GAME_OVER; winner WHITE; // 玩家落子成五白方 AI 胜 } else { gameState AI_TURN; request_ai_move(); } glutPostRedisplay(); // 请求重绘让绘制回调在下一轮被调用 }计算交叉点的网格坐标时用floor(mouseX * SIZE / winW)而不是四舍五入原因是交叉点的有效区域是格子的中心点四舍五入会把鼠标移到格子边缘时错误映射到相邻交叉点。glutPostRedisplay本身只是“请求”重绘真正的绘制发生在下一轮事件循环。不要为了省事直接在鼠标回调里调用on_render()那会破坏 glut 的事件循环高频率点击时可能出现画面撕裂或闪烁。4.3 AI 计算时的界面策略同步阻塞还是后台线程MCTS 搜索几千次模拟在性能好的机器上也要一到两秒这段时间窗口会失去响应。最省事的做法是同步阻塞在request_ai_move()里直接调用 MCTS 搜索等它返回再落子期间界面卡住鼠标显示为“程序未响应”。这在期末验收是能过关的老师点一下鼠标等一两秒出现 AI 落子属于可接受范围。但如果你想做得好看一点可以用一个最简单的后台线程MCTS 在线程里算算完后置一个标志位主线程里挂一个glutTimerFunc每秒轮询几次标志位为真就应用落子并重绘。后台线程的注意点OpenGL 的所有绘制函数只能在主线程调用不要在子线程里碰glutPostRedisplay或任何绘图命令。子线程只负责计算把结果写进一个共享的aiMoveX / aiMoveY / aiDone变量。因为读写都很简单用std::atomicbool就能保证安全不需要上锁。这个方案代码量不大但答辩时能加分因为展示了你意识到图形 API 的线程模型限制。5. 不围棋 MCTS glut 的避坑指南5 条能直接抄的排错经验这一章从我自己和周围同学的项目里挑出最常翻车的 5 类问题每一条都是“现象 → 原因 → 解决”的结构。照着排查能省下大量在论坛里翻帖子问“为什么我的 glut 崩了”的时间。5.1 glut 初始化失败或黑窗口先写 glutInit再谈画棋盘现象程序运行到glutCreateWindow时直接崩溃终端甚至弹出failed to initialize graphics backend for opengl或者出现一个黑窗口没有任何棋盘内容。原因最常见的是漏掉glutInit(argc, argv)或者glutInitDisplayMode写成了GLUT_SINGLE。glut 内部的状态初始化全部依赖glutInit它要在任何窗口相关调用之前执行。黑窗口通常是绘制回调里没有把背景色填充成棋盘色或者忘了在绘制最后调用glutSwapBuffers()用GLUT_DOUBLE时尤其常见。解决把glutInit严格放在 main 开头绘制回调按“清屏 → 画网格 → 画棋子 →glutSwapBuffers”的顺序写一个环节都不能省。5.2 MCTS 卡几十秒不出棋根节点复用比重建更重要现象前十几手 AI 落子还挺快越到后面越卡最后一手能转上十几秒甚至无响应。原因每步都在当前局面重新建一棵完整的 MCTS 树越往后搜索树越大重复计算的浪费累积到肉眼可见。另一个常见原因是模拟的深度限制没有生效递归的simulate直冲棋盘下满225 手全模拟完单次模拟的耗时就被拉高了。解决实现根节点复用玩家落子后从旧树里把对应子节点提权并释放其它节点给simulate加深度上限达到上限直接返回平局不再继续递归。改完会发现最慢的步是开局那几步后面反而越来越快。5.3 AI 开局就送输过滤“落子即输”点不是靠启发式学出来现象AI 明明有很多安全落点可选却偏偏走到某个位置让自己形成五连一开局就送掉。原因模拟里的随机走子没有排除“当前玩家落子会成五”的点导致大量模拟在起始几步就立刻结束统计结果被严重污染。更隐蔽的是连扩展阶段也把这个节点加入了树AI 在树上已经把这个“送死手”当作合法节点反复选择。解决在legal_moves和生成子节点的阶段就统一过滤掉会让自己成五的点。过滤逻辑不要散落在多个函数里最好在Board层给一个generate_safe_moves(color)的接口MCTS 和界面都调它。这一条不改之后所有棋力优化都是白费。5.4 鼠标点击位置对不上棋盘高 DPI 和窗口坐标系两个坑叠加现象在 4K 屏幕或系统开启屏幕缩放DPI 缩放的笔记本上点击棋盘的交叉点棋子落在相邻位置窗口拉成非正方形后错位更明显。原因两层。第一层是 glut 鼠标回调的 y 轴方向上一章已经讲过的“上原点”问题第二层是 Windows 高分屏下应用程序默认不感知 DPI 缩放glutGet(GLUT_WINDOW_WIDTH)拿到的是物理像素而鼠标坐标是缩放后的逻辑值两者不一致。解决y 轴翻转公式照写winH - mouseY然后在 main 里加一句SetProcessDPIAware()保证窗口尺寸和鼠标坐标在同一个坐标系下。这句在 Windows 下很不起眼但对高分屏用户是救命级别的修复。5.5 棋盘不刷新或画面撕裂渲染函数里别做 MCTS 计算现象点击落子后棋盘没有任何变化要拖动窗口才看到棋子出现或者 AI 思考时窗口白屏思考结束才一次性画完。原因在on_render里做了重活比如把 MCTS 搜索写在绘制回调里来回调用或者鼠标回调里直接调用绘制函数绕过了 glut 的事件循环。解决严格执行“绘制回调只负责绘制”的约定。AI 计算放到request_ai_move()里同步或后台线程算完后只调glutPostRedisplay()请求重绘。渲染里禁止出现任何循环搜索、遍历超万个节点的逻辑。这样窗口在 AI 思考时至少保持上次的画面状态不会白屏。6. 进阶调试技巧用自对弈调 UCB 参数给自己画一张败因热力图MCTS 写对了之后真正影响棋力的其实是三个参数c的取值、每次搜索的模拟次数、以及时机的终局处理。我做的第一个不围棋项目AI 总是走一些“看似安全实则缓慢”的点单步模拟次数到 5000 才勉强有攻击性。后来我在 main 里留了一个force_mode的入口不创建窗口、不初始化 glut直接让 AI 执黑执白各跑一局静默输出结果。这个自对弈开关是调试 MCTS 最顺手的工具十分钟能跑几十局不用盯着棋盘看。调参从c开始。先把模拟次数固定住比如 2000 次跑一组c 1.0、1.4、2.0、2.5的自对弈每档跑十局统计黑棋胜率。你会很直观地发现几个数值之间的棋风差异。然后固定c把模拟次数从 500 增到 5000同样统计胜率找一个“再增加模拟次数胜率提升不明显”的拐点。对期末作业来说这个拐点通常落在 2000 到 3000 次之间单步耗时可接受。另外一个值得做的验证手段是败因热力图让 AI 自对弈若干局凡是出现判负的落点在棋盘上涂一个红色标记。把它全部叠在一张棋盘图里你会看到失败点几乎都集中在对角线的某些位置上——那里长连最容易形成也是 AI 的致命弱点。我最后的收尾习惯是在提交代码前把“自对弈统计模式”保留下来做一个命令行参数--bench。答辩时如果老师问“你凭什么说 AI 是有效果的”直接现场跑一组自对弈胜率统计比嘴上说一万句都管用。这个项目做完你带着的不仅是一个能跑的游戏更是一整套“规则解析 → 搜索算法 → 图形界面 → 统计验证”的工程思路。希望帮到你。如果时间再充裕一点我会建议你给棋盘加一个简单的棋盘坐标显示把 A1 到 O15 的标记画在边缘这样复盘棋谱时能直接说“AI 在 G7 落了子”而不是指着屏幕比划。这一个装饰性改动在期末验收时非常讨喜因为演示复盘看起来专业得多。本文还有配套的精品资源点击获取
不围棋AI实战：C++实现蒙特卡洛树搜索与OpenGL界面
简介一套基于C与OpenGLglut实现的不围棋No-Go游戏完整源码源自计算概论课程期末大作业适合C进阶学习、算法实践及博弈AI开发的读者参考。游戏严格遵循9×9棋盘、黑棋先手、禁止吃子、禁止自杀与禁止pass的不围棋规则并加入黑棋首手禁着中心点的附加平衡规则AI采用蒙特卡洛树搜索MCTS可在Windows 10平台直接编译运行。压缩包共57个文件、约2.2MB含14个cpp与14个h源码覆盖棋盘规则、MCTS智能体、OpenGL场景渲染、存档管理等模块、17张bmp图片资源及Visual Studio工程文件sln/vcxproj目录划分清晰。目前已有298人浏览学习对希望掌握MCTS原理、不围棋规则建模或OpenGL交互界面的读者而言这份源码提供了可直接运行的完整样例可快速上手二次开发也可作为课程设计或竞赛项目的参考底稿。1. 不围棋期末大作业表面是反五子棋实则是三个模块的缝合题不围棋的规则一句话就能讲完在 15×15 棋盘上黑白交替落子谁先让自己连成五个同色棋子谁就输。这题目是“计算概论”期末大作业里的经典缝合型用 C 写完棋盘规则和搜索逻辑再用 OpenGL 的 glut 工具库把界面撑起来AI 用蒙特卡洛树搜索MCTS做决策。很多同学在这三块里轮流翻车MCTS 搜了半天出不了第一手glut 窗口点了没反应或者 AI 明明能赢却偏偏下出“送死手”。这篇笔记就顺着规则判定、MCTS 的 C 实现、glut 窗口三块讲清楚重点是能直接照着改的参数和踩过的坑适合要交大作业或者想拿一个完整项目练 C 数据结构和图形界面配合的人。2. 规则与架构把“谁落谁输”翻译成能判定的 C 函数动代码之前先把不围棋的规则锁死。这个棋在民间变体不少有的版本带禁手不许下出长连、双三、双四有的版本只管五连。期末时间有限我一般建议做简化版——只判断“落子后同色棋子在横、竖、两条斜线方向上连续数是否达到 5”达到就判负。理由很实在完整禁手规则会让合法动作集合变得非常复杂MCTS 的动作筛选和模拟走子都得跟着改工作量直接翻倍。只要在 README 里写清楚“本作业采用简化版不围棋规则长连判负不做禁手”评分老师不会挑理。2.1 棋盘与胜负判定四方向连子计数一次落子定胜负棋盘用二维数组最直接。15×15 的大小刚好覆盖五连的判断又不会让搜索空间大到离谱。数组里 0 表示空位1 表示黑棋2 表示白棋。胜负判定的核心是每次落子后只以这个落点为中心沿四个方向朝两边数连续同色棋子的数量。四个方向分别是水平、竖直、主对角线、副对角线。// board.h 里的核心判定函数 const int SIZE 15; int grid[SIZE][SIZE]; // 0 空位1 黑棋2 白棋 bool in_range(int x, int y) { return x 0 x SIZE y 0 y SIZE; } // 判断 (x, y) 落下一颗 color 棋子后是否构成五连及以上 bool forms_five(int x, int y, int color) { int dx[4] {1, 1, 0, 1}; int dy[4] {0, 1, 1, -1}; for (int dir 0; dir 4; dir) { int cnt 1; // 落子本身算一颗 for (int step 1;; step) { int nx x step * dx[dir]; int ny y step * dy[dir]; if (!in_range(nx, ny) || grid[nx][ny] ! color) break; cnt; } for (int step 1;; step) { int nx x - step * dx[dir]; int ny y - step * dy[dir]; if (!in_range(nx, ny) || grid[nx][ny] ! color) break; cnt; } if (cnt 5) return true; } return false; }函数里最关键的是 5而不是 5。我见过不少同学写成 5导致长连六颗、七颗时不判负AI 和玩家都会在明明输了的局里继续走。改成 5之后规则就很干净只要这一手让自己连出五颗及以上立刻结束。由于每次只查落点周边复杂度和棋盘大小无关只和连子长度相关可以认为是一次 O(1) 级别的查询MCTS 里模拟几千局时这个开销不能小看。2.2 模块怎么拆board、mcts、renderer 三个类各管哪摊不围棋这种项目最容易死磕在“所有代码堆在一个 main.cpp 里”。等 MCTS 和 glut 接进来全局变量互相踩改一个功能崩三个地方。我一般把项目拆成三块Board负责棋盘状态、落子、胜负判定、是否下满MCTS只负责给定当前局面返回一个落子坐标Renderer负责 OpenGL 绘制和鼠标回调。三个类之间单向依赖MCTS 调用 Board 的只读接口Renderer 也调用 Board 的只读接口MCTS 和 Renderer 互不感知。// board.h 的核心接口AI 和界面都只跟它打交道 enum MoveResult { MOVE_OK, MOVE_LOSE, MOVE_FULL }; class Board { public: MoveResult apply(int x, int y, int color); // 落子并判断是否被判负 bool is_full() const; // 棋盘是否下满 void clear(); // 新一局开始时清盘 int at(int x, int y) const; // 读某位置棋子颜色 private: int grid[SIZE][SIZE]; };apply的返回值要设计得明确MOVE_OK表示落子成功且没有成五MOVE_LOSE表示落子后自己构成了五连落子方判负MOVE_FULL表示棋盘已满落子无效。有了这个返回值main 里的状态流转就很直观。界面层和 AI 层都不要自己去数棋盘统一通过at()读状态否则容易出现逻辑各写一份、判定结果对不上的情况。期末评分时“模块划分清晰”通常是独立的加分项比你多写一个启发式函数管用得多。2.3 交互状态机玩家落子、AI 计算、胜负展示的时序界面和 AI 的配合需要一个小小的状态机否则鼠标回调和 MCTS 计算会乱套。我习惯用三个状态PLAYER_TURN等待玩家落子AI_TURN表示 AI 正在思考或即将落子GAME_OVER表示有一方已经判负。玩家落子成功且没有输状态切到AI_TURNAI 落子成功且没有输状态切回PLAYER_TURN。enum GameState { PLAYER_TURN, AI_TURN, GAME_OVER }; GameState state PLAYER_TURN;这里有个看起来小、实际影响很大的点AI 计算期间必须禁止鼠标落子。否则玩家疯狂点棋盘逻辑上会同时出现多次落子AI 搜索用的局面和界面显示的局面错位最后保存的棋谱根本没法复盘。解决方式很简单在鼠标回调开头就检查state ! PLAYER_TURN直接返回。这个状态机在项目里值不了多少行代码但没有它后面接上 glut 的异步回调时会非常痛苦。3. MCTS 算法落地从 UCT 公式到能跑的 C 搜索循环蒙特卡洛树搜索核心思想是“不评估局面只统计胜负”。传统博弈 AI 像 Alpha-beta 剪枝要写启发式评估函数告诉程序“黑棋目前多活二所以好一点”。不围棋恰恰最难写这种评估局面接近时谁优谁劣很难量化而终局条件又极其清晰——谁成五谁输。MCTS 不吃这一套它靠大量随机对局来估计每个落子的胜率从当前节点出发反复做“选择、扩展、模拟、回传”四步循环访问次数越多的节点越有可能是好手。3.1 蒙特卡洛树搜索四步循环以及为什么适合“无启发式”的游戏四步循环里选择是沿着已有搜索树用 UCB1 公式挑访问价值最高的子节点往下走直到某个叶子节点扩展是给这个叶子节点生成合法的后续落子候选并挑一个加入树中模拟是从新节点开始用极快的随机走子一直下到分出胜负或棋盘下满回传是把这局结果沿着路径写回每个节点更新访问次数和累计胜利数。四个步骤里模拟最耗费时间也是整个搜索的性能瓶颈。MCTS 适合不围棋的第二个理由是它对“搜索宽度”的容忍度比 Alpha-beta 高。不围棋每步合法落子最多 225 个Alpha-beta 想要效果好必须配合强剪枝和良好走子排序MCTS 靠随机模拟就能给出像样的落子建议代码量少一个数量级。对“计算概论”这种课程项目MCTS 是性价比最高的方案。第三个理由藏在“无启发式”里树不依赖人工知识给 AI 换一种变体规则比如棋盘改成 19×19不需要改搜索逻辑只改棋盘大小就行。3.2 节点数据结构与 UCB1别再每步重建整棵树MCTS 节点的 C 结构不复杂但有一个关键的工程决策不要每走一手都从零建树。玩家落子后上一轮搜索树里已经包含了对当前局面的研究对应落子的那个子节点以及它的整棵子树可以直接继承下来。我每次第一次写 MCTS 都忍不住每步重建结果 30 手之后 AI 耗时肉眼可见地翻倍。正确的做法是玩家落子后在旧树的根节点子节点里找到那个坐标把它提升为新根释放其它子树。// mcts.h 中的节点结构 struct Node { int x, y; // 本节点对应的落子坐标根节点记为 -1, -1 int color; // 这一手棋的颜色根节点为 0 Node* parent; std::vectorNode* children; int visits; // 访问次数 double wins; // 从本节点视角累计的胜局数 }; // UCB1 公式子节点访问 0 次时返回无穷大保证每个候选点先被探索一遍 double ucb1(Node* child, int totalVisits, double c) { if (child-visits 0) return 1e9; double exploit child-wins / child-visits; double explore c * std::sqrt(std::log((double)totalVisits) / child-visits); return exploit explore; } // 选择阶段在所有子节点里挑 UCB1 值最高的 Node* best_child(Node* node, double c) { double bestScore -1e18; Node* best nullptr; for (Node* child : node-children) { double score ucb1(child, node-visits, c); if (score bestScore) { bestScore score; best child; } } return best; }UCB1 公式的常数c控制“探索”和“利用”的平衡。c取小一些AI 会更倾向走已经验证出高胜率的分支取大一些AI 更愿意尝试没怎么走过的点。不围棋我习惯取 1.4这是很多棋类 MCTS 实现里的常用起点值。注意wins的视角如果节点代表黑棋落子那么黑棋赢就记 1 分白棋赢记 0 分平局记 0.5 分。这个视角在回传时要一致否则整棵树的分数都是乱的AI 会表现为“越下越蠢”。3.3 模拟走子与两个必要的优化过滤送死手与限制模拟深度模拟阶段的随机走子不能完全随机。不围棋的特殊性在于如果随机模拟里某个落子会立刻让自己形成五连它直接决定了这一局的胜负而这些“送死手”在实际搜索里根本不应该进入候选。如果不过滤MCTS 会被大量立刻判负的模拟带偏导致 AI 明明有安全落点却总是选中那些让对手躺赢的位置。// 从某个局面开始随机模拟到终局colorToMove 表示当前轮到的颜色 int simulate(Board board, int colorToMove) { int cur colorToMove; while (!board.is_full()) { // legal_moves 必须忽略会让当前玩家立刻成五的落点 std::vectorstd::pairint,int candidates legal_moves(board, cur); if (candidates.empty()) return DRAW; // 局面下满视为平局 auto mv candidates[rand() % candidates.size()]; MoveResult res board.apply(mv.first, mv.second, cur); if (res MOVE_LOSE) return opponent(cur); // cur 落子成五判负 cur opponent(cur); } return DRAW; }这里有两个很容易遗漏的点。第一legal_moves不只是检查“坐标在棋盘内且为空”还要检查“落在这里不会让cur成五”。我见过一种笨办法在 simulate 里先 apply 再调forms_five若成五就撤销。这样也能工作但每次随机走子都要经历一遍完整的 apply 和撤销速度慢不少。更干净的做法是写一个apply_safe(move, color)接口落子后立刻查forms_five如果成五就回滚并把这个坐标从候选里剔除。第二rand()一定要记得先srand(time(nullptr))否则每次运行 AI 的模拟序列完全一样棋局固定看起来像“AI 只会背棋谱”。这是新手写 MCTS 最容易踩的随机数坑。模拟深度也要设防。不围棋棋盘 225 个空位如果模拟时一直下到填满才结束一盘模拟可能要执行上百次 apply搜索几千次模拟的耗时就很可观。我一般给模拟设定一个深度上限比如 30 步或剩余空位数的最小值到顶就按平局处理。这个限制对棋力影响很小因为不围棋大部分对局在几十手内就会分出胜负继续随机走下去只会增加噪声。配合根节点复用MCTS 在 15×15 棋盘上做 3000 次模拟单步耗时在普通笔记本上能压在一到两秒左右界面不会卡到让人想砸键盘。4. OpenGL glut 界面初始化、鼠标坐标换算与 AI 交替走棋界面这一块看起来是纯体力活但坑特别密集尤其是环境配置和坐标换算。glut 是 OpenGL 的一个工具库负责窗口管理、事件回调和简单绘制正好够画一个静态的棋盘加棋子不用自己写 X11 或 Win32 窗口代码。用 glut 的好处是代码短、上课讲过、系统跨平台缺点是它非常老派很多现代习惯用 freeglut 替代但接口基本一致。下面以 Windows Visual Studio 的常见做法为准因为“计算概论”的评测环境大多跑在这上面。4.1 Visual Studio 里安装 glut三件套、路径与链接器配置glut 在老版本 Visual Studio 里是“下载三个文件、复制到对应目录、改链接配置”的三步曲。三个文件是glut.h、glut32.lib和glut32.dll用 freeglut 的话对应文件名稍有不同接口兼容。常见做法是把glut.h放进 VS 的 include 目录glut32.lib放进 lib 目录glut32.dll和生成的 exe 放同一个目录。在较新版本的 VS 里也可以把这三个文件放进项目目录在项目属性里单独指定头文件路径和库目录好处是换一台电脑不用往系统目录里乱塞东西。项目里还需要配置链接器。右键项目打开“链接器 → 输入 → 附加依赖项”加上glut32.lib和opengl32.lib。如果用了glu相关函数还要加glu32.lib。这一步漏掉最常见的报错风格是“无法解析的外部符号__imp_glutInit”看着吓人实际就是链接器没找到库。用 vscode 配 c 环境时思路一样includePath 指向 glut.h 所在目录tasks.json 的 args 里加-lglut32 -lopengl32但 Visual Studio 下做课程作业更省心不推荐期末阶段折腾 vscode 交叉编译的问题。4.2 画棋盘与鼠标坐标换算窗口是上原点OpenGL 是下原点glut 主程序的结构非常固定先初始化 glut 和显示模式再创建窗口然后注册回调函数最后进入glutMainLoop。一个典型的 main 长这样int main(int argc, char** argv) { glutInit(argc, argv); // 必须先于创建窗口调用 glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB); glutInitWindowSize(640, 640); glutCreateWindow(不围棋 MCTS - 计算概论期末大作业); init_board(); glutDisplayFunc(on_render); // 重绘回调 glutMouseFunc(on_mouse); // 鼠标回调 glutReshapeFunc(on_reshape); // 窗口大小变化 glutMainLoop(); // 进入事件循环不返回 return 0; }绘制回调里只做一件事画网格、画所有棋子、交换缓冲区。不要在这里跑 MCTS。鼠标回调的坐标换算是个经典坑点glut 传给鼠标回调的 (x, y) 是以窗口左上角为原点、y 轴向下为正OpenGL 正交投影里默认 y 轴向上。不翻转直接映射你点棋盘上方的一个交叉点棋子会落在下方。void on_mouse(int button, int state, int mouseX, int mouseY) { if (button ! GLUT_LEFT_BUTTON || state ! GLUT_DOWN) return; if (state ! PLAYER_TURN) return; // AI 思考时忽略点击 int winW glutGet(GLUT_WINDOW_WIDTH); int winH glutGet(GLUT_WINDOW_HEIGHT); int gx (int)std::floor((mouseX * SIZE) / (double)winW); int gy (int)std::floor(((winH - mouseY) * SIZE) / (double)winH); // 翻转Y if (board.at(gx, gy) ! EMPTY) return; MoveResult res board.apply(gx, gy, BLACK); if (res MOVE_LOSE) { gameState GAME_OVER; winner WHITE; // 玩家落子成五白方 AI 胜 } else { gameState AI_TURN; request_ai_move(); } glutPostRedisplay(); // 请求重绘让绘制回调在下一轮被调用 }计算交叉点的网格坐标时用floor(mouseX * SIZE / winW)而不是四舍五入原因是交叉点的有效区域是格子的中心点四舍五入会把鼠标移到格子边缘时错误映射到相邻交叉点。glutPostRedisplay本身只是“请求”重绘真正的绘制发生在下一轮事件循环。不要为了省事直接在鼠标回调里调用on_render()那会破坏 glut 的事件循环高频率点击时可能出现画面撕裂或闪烁。4.3 AI 计算时的界面策略同步阻塞还是后台线程MCTS 搜索几千次模拟在性能好的机器上也要一到两秒这段时间窗口会失去响应。最省事的做法是同步阻塞在request_ai_move()里直接调用 MCTS 搜索等它返回再落子期间界面卡住鼠标显示为“程序未响应”。这在期末验收是能过关的老师点一下鼠标等一两秒出现 AI 落子属于可接受范围。但如果你想做得好看一点可以用一个最简单的后台线程MCTS 在线程里算算完后置一个标志位主线程里挂一个glutTimerFunc每秒轮询几次标志位为真就应用落子并重绘。后台线程的注意点OpenGL 的所有绘制函数只能在主线程调用不要在子线程里碰glutPostRedisplay或任何绘图命令。子线程只负责计算把结果写进一个共享的aiMoveX / aiMoveY / aiDone变量。因为读写都很简单用std::atomicbool就能保证安全不需要上锁。这个方案代码量不大但答辩时能加分因为展示了你意识到图形 API 的线程模型限制。5. 不围棋 MCTS glut 的避坑指南5 条能直接抄的排错经验这一章从我自己和周围同学的项目里挑出最常翻车的 5 类问题每一条都是“现象 → 原因 → 解决”的结构。照着排查能省下大量在论坛里翻帖子问“为什么我的 glut 崩了”的时间。5.1 glut 初始化失败或黑窗口先写 glutInit再谈画棋盘现象程序运行到glutCreateWindow时直接崩溃终端甚至弹出failed to initialize graphics backend for opengl或者出现一个黑窗口没有任何棋盘内容。原因最常见的是漏掉glutInit(argc, argv)或者glutInitDisplayMode写成了GLUT_SINGLE。glut 内部的状态初始化全部依赖glutInit它要在任何窗口相关调用之前执行。黑窗口通常是绘制回调里没有把背景色填充成棋盘色或者忘了在绘制最后调用glutSwapBuffers()用GLUT_DOUBLE时尤其常见。解决把glutInit严格放在 main 开头绘制回调按“清屏 → 画网格 → 画棋子 →glutSwapBuffers”的顺序写一个环节都不能省。5.2 MCTS 卡几十秒不出棋根节点复用比重建更重要现象前十几手 AI 落子还挺快越到后面越卡最后一手能转上十几秒甚至无响应。原因每步都在当前局面重新建一棵完整的 MCTS 树越往后搜索树越大重复计算的浪费累积到肉眼可见。另一个常见原因是模拟的深度限制没有生效递归的simulate直冲棋盘下满225 手全模拟完单次模拟的耗时就被拉高了。解决实现根节点复用玩家落子后从旧树里把对应子节点提权并释放其它节点给simulate加深度上限达到上限直接返回平局不再继续递归。改完会发现最慢的步是开局那几步后面反而越来越快。5.3 AI 开局就送输过滤“落子即输”点不是靠启发式学出来现象AI 明明有很多安全落点可选却偏偏走到某个位置让自己形成五连一开局就送掉。原因模拟里的随机走子没有排除“当前玩家落子会成五”的点导致大量模拟在起始几步就立刻结束统计结果被严重污染。更隐蔽的是连扩展阶段也把这个节点加入了树AI 在树上已经把这个“送死手”当作合法节点反复选择。解决在legal_moves和生成子节点的阶段就统一过滤掉会让自己成五的点。过滤逻辑不要散落在多个函数里最好在Board层给一个generate_safe_moves(color)的接口MCTS 和界面都调它。这一条不改之后所有棋力优化都是白费。5.4 鼠标点击位置对不上棋盘高 DPI 和窗口坐标系两个坑叠加现象在 4K 屏幕或系统开启屏幕缩放DPI 缩放的笔记本上点击棋盘的交叉点棋子落在相邻位置窗口拉成非正方形后错位更明显。原因两层。第一层是 glut 鼠标回调的 y 轴方向上一章已经讲过的“上原点”问题第二层是 Windows 高分屏下应用程序默认不感知 DPI 缩放glutGet(GLUT_WINDOW_WIDTH)拿到的是物理像素而鼠标坐标是缩放后的逻辑值两者不一致。解决y 轴翻转公式照写winH - mouseY然后在 main 里加一句SetProcessDPIAware()保证窗口尺寸和鼠标坐标在同一个坐标系下。这句在 Windows 下很不起眼但对高分屏用户是救命级别的修复。5.5 棋盘不刷新或画面撕裂渲染函数里别做 MCTS 计算现象点击落子后棋盘没有任何变化要拖动窗口才看到棋子出现或者 AI 思考时窗口白屏思考结束才一次性画完。原因在on_render里做了重活比如把 MCTS 搜索写在绘制回调里来回调用或者鼠标回调里直接调用绘制函数绕过了 glut 的事件循环。解决严格执行“绘制回调只负责绘制”的约定。AI 计算放到request_ai_move()里同步或后台线程算完后只调glutPostRedisplay()请求重绘。渲染里禁止出现任何循环搜索、遍历超万个节点的逻辑。这样窗口在 AI 思考时至少保持上次的画面状态不会白屏。6. 进阶调试技巧用自对弈调 UCB 参数给自己画一张败因热力图MCTS 写对了之后真正影响棋力的其实是三个参数c的取值、每次搜索的模拟次数、以及时机的终局处理。我做的第一个不围棋项目AI 总是走一些“看似安全实则缓慢”的点单步模拟次数到 5000 才勉强有攻击性。后来我在 main 里留了一个force_mode的入口不创建窗口、不初始化 glut直接让 AI 执黑执白各跑一局静默输出结果。这个自对弈开关是调试 MCTS 最顺手的工具十分钟能跑几十局不用盯着棋盘看。调参从c开始。先把模拟次数固定住比如 2000 次跑一组c 1.0、1.4、2.0、2.5的自对弈每档跑十局统计黑棋胜率。你会很直观地发现几个数值之间的棋风差异。然后固定c把模拟次数从 500 增到 5000同样统计胜率找一个“再增加模拟次数胜率提升不明显”的拐点。对期末作业来说这个拐点通常落在 2000 到 3000 次之间单步耗时可接受。另外一个值得做的验证手段是败因热力图让 AI 自对弈若干局凡是出现判负的落点在棋盘上涂一个红色标记。把它全部叠在一张棋盘图里你会看到失败点几乎都集中在对角线的某些位置上——那里长连最容易形成也是 AI 的致命弱点。我最后的收尾习惯是在提交代码前把“自对弈统计模式”保留下来做一个命令行参数--bench。答辩时如果老师问“你凭什么说 AI 是有效果的”直接现场跑一组自对弈胜率统计比嘴上说一万句都管用。这个项目做完你带着的不仅是一个能跑的游戏更是一整套“规则解析 → 搜索算法 → 图形界面 → 统计验证”的工程思路。希望帮到你。如果时间再充裕一点我会建议你给棋盘加一个简单的棋盘坐标显示把 A1 到 O15 的标记画在边缘这样复盘棋谱时能直接说“AI 在 G7 落了子”而不是指着屏幕比划。这一个装饰性改动在期末验收时非常讨喜因为演示复盘看起来专业得多。本文还有配套的精品资源点击获取