拓冰网站定制 
简介基于C实现的不围棋游戏完整源码系计算概论期末大作业适合学习游戏编程、蒙特卡洛树搜索与OpenGL交互的学生也可作为课程设计或AI博弈入门范例。不围棋规则中落子若吃掉对方棋子或自杀均判负禁止空手黑棋首手不可落于棋盘中心botzone版无此限制判定逻辑集中在GameRule模块。压缩包共57个文件、2.2MB含14个cpp与14个h源码文件覆盖游戏场景、AI策略、棋盘渲染与存档管理另有17张bmp界面素材、Visual Studio工程文件、README及许可证等目录分工明确。除MCTS主AI外还提供Minmax对照实现与botzone比赛版代码便于对比不同博弈搜索策略OpenGL glut界面及按钮、菜单模块均具复用价值。已有297人浏览学习源码可编译运行并二次开发。1. 不围棋期末作业真正的难点不在 OpenGL而在 MCTS 的状态管理用“计算概论期末大作业基于C实现的不围棋游戏源码”作为题目本质上是让你在一个学期里把三件事串起来用 C 写棋盘逻辑用蒙特卡洛树搜索MCTS做 AI再用 OpenGL 的 glut 工具库把界面画出来。很多同学拿到题目的第一反应是“OpenGL 好难”其实画棋盘、画棋子加起来不过几十行代码真正会让你翻车的反而是“气”的计算、MCTS 的胜负回传以及没想清楚时偶发的非法落子。这里从一个可复现的角度把不围棋核心规则、MCTS 实现要点、glut 界面整合和常见坑位都过一遍适合正在做类似作业的人也适合想用 C 小游戏项目练手的人。2. 不围棋规则与棋盘实现先把“气”算清楚2.1 用 9x9 二维数组表示棋盘不围棋也叫 NoGo规则与围棋很接近但不完全一样你不能落子在一个会导致自己棋子没气的位置也就是禁止自杀。提子依然存在如果你落子后把对手的一整块棋的气全部堵死对方棋子会被提掉你自己的新棋子反而因此获得气。所以判断落子是否合法不是只看落子点本身有没有气还要看提子后的局面。棋盘大小我建议先用 9x9。9 路棋盘对 MCTS 最友好搜索速度快OpenGL 窗口也不需要开很大。数据结构用一个std::vectorstd::vectorint就够了0 表示空点1 表示黑棋2 表示白棋。不要一开始就做 19 路那是给自己找麻烦。这一层可以先定义一个清晰的 Board 接口class Board { public: static const int SIZE 9; enum { EMPTY 0, BLACK 1, WHITE 2 }; std::vectorstd::vectorint grid; Board() : grid(SIZE, std::vectorint(SIZE, EMPTY)) {} // 在副本上模拟落子返回新棋盘 Board makeMove(int r, int c, int color) const; // 计算某个连通区块的气数 int countLiberties(int r, int c) const; // 判断某个位置是否合法 bool isLegalMove(int r, int c, int color) const; // 获取某个颜色方所有合法落子点 std::vectorstd::pairint,int getLegalMoves(int color) const; // 判断某方是否无棋可下 bool hasNoLegalMoves(int color) const; };makeMove返回新棋盘而不是修改原棋盘这条很重要。MCTS 每走一步都要在某个局面下尝试大量落子如果在原棋盘上改来改去回溯时很容易出错。值拷贝虽然慢一点但 9x9 棋盘只有 81 个整数拷贝成本可以忽略。2.2 合法着法判定临时落子、提子、再查气判断一个落子是否合法标准动作就是三步先把棋子放上去再检查对手有没有被提掉的棋子最后检查落子后己方连通块的气数。如果某个对手连通块气数为 0要先从棋盘上移除否则它会占着位置导致你自己的棋块气数算错。下面是makeMove和isLegalMove的核心实现Board Board::makeMove(int r, int c, int color) const { Board next *this; next.grid[r][c] color; int opponent (color BLACK) ? WHITE : BLACK; const int dr[] {-1, 1, 0, 0}; const int dc[] {0, 0, -1, 1}; // 遍历当前落子的四个邻居找到相邻的对手连通块 for (int d 0; d 4; d) { int nr r dr[d], nc c dc[d]; if (nr 0 || nr SIZE || nc 0 || nc SIZE) continue; if (next.grid[nr][nc] ! opponent) continue; // 用 BFS 收集同一个对手连通块 std::vectorstd::pairint,int block; std::vectorstd::vectorbool visited(SIZE, std::vectorbool(SIZE, false)); std::queuestd::pairint,int q; q.push({nr, nc}); visited[nr][nc] true; while (!q.empty()) { auto [x, y] q.front(); q.pop(); block.push_back({x, y}); for (int d2 0; d2 4; d2) { int nx x dr[d2], ny y dc[d2]; if (nx 0 nx SIZE ny 0 ny SIZE !visited[nx][ny] next.grid[nx][ny] opponent) { visited[nx][ny] true; q.push({nx, ny}); } } } // 数这个连通块的气气为 0 就提掉 int liberties 0; for (auto [x, y] : block) { for (int d2 0; d2 4; d2) { int nx x dr[d2], ny y dc[d2]; if (nx 0 nx SIZE ny 0 ny SIZE next.grid[nx][ny] EMPTY) { liberties; } } } if (liberties 0) { for (auto [x, y] : block) { next.grid[x][y] EMPTY; } } } return next; } bool Board::isLegalMove(int r, int c, int color) const { if (grid[r][c] ! EMPTY) return false; Board after makeMove(r, c, color); return after.countLiberties(r, c) 0; }countLiberties需要做一次洪水填充把整个同色连通块找出来然后数它周围空点的个数。很多人会漏掉“提子后再查气”这个顺序直接在落子前用手工数气一旦遇到吃子判断就会出错。实战里最稳的做法就是上面这样把落子后的完整局面算出来再查气永远不猜。2.3 终局判定与随机对局模拟不围棋的终局条件非常简单轮到某方落子时它没有任何合法着法立刻判负。所以终局判定可以直接复用getLegalMovesbool Board::hasNoLegalMoves(int color) const { return getLegalMoves(color).empty(); } std::vectorstd::pairint,int Board::getLegalMoves(int color) const { std::vectorstd::pairint,int moves; for (int r 0; r SIZE; r) { for (int c 0; c SIZE; c) { if (isLegalMove(r, c, color)) { moves.push_back({r, c}); } } } return moves; }这段逻辑很简单但要注意性能每生成一次合法着法列表都要对棋盘上所有空点调用isLegalMove而makeMove内部又有 BFS 和提子所以 9x9 棋盘上生成一次列表可能要跑几万次基础操作。对 MCTS 的模拟来说这个代价还能接受但不要在 AI 思考的循环里反复生成同一份列表。更合理的做法是在扩展节点时把该节点的untriedMoves缓存下来之后模拟阶段每次都从getLegalMoves重新生成也是一种成本。为了验证规则实现得对不对可以先写一个纯控制台自对弈循环随机玩家对随机玩家走一步打印一步看是否有非法落子、是否能正常终局。这一步不过关不要碰 OpenGL 和 MCTS。3. 用蒙特卡洛树搜索实现不围棋 AI核心循环与参数调整3.1 MCTS 四步循环选择、扩展、模拟、回传蒙特卡洛树搜索的核心思路是把当前局面作为根节点反复做“随机对局”来估计每个落子的胜率。整个循环可以被拆成四个阶段所有 MCTS 实现都是这四个阶段的循环选择从根节点出发按照 UCT 公式选择一个子节点再从这个子节点往下选直到到达一个还没有被完全展开的节点。扩展在这个节点上取出一个还没有试过的合法落子创建出一个新的子节点。模拟从新子节点的局面开始让黑白双方随机落子直到一方无棋可下。回传把模拟结果沿着访问过的路径一路往回更新每个节点的访问次数加 1胜负累计值按视角调整。迭代次数决定了 AI 的棋力。9x9 不围棋上几百次迭代能跑通但棋力很弱1000 到 3000 次迭代是性能和棋力都比较均衡的范围。MCTS 不需要人工写评估函数但它需要大量模拟来平滑随机噪声。3.2 节点结构与 UCT 公式的 C 实现每个节点要保存当前棋盘状态、轮到谁下棋、父节点、子节点列表、未被尝试的着法列表、访问次数和累计胜场。为了简化不围棋是二人零和游戏节点里的wins可以只从当前玩家的视角保存回传时翻转即可。struct MCTSNode { Board board; int player; // 当前轮到谁落子 MCTSNode* parent; std::vectorMCTSNode* children; std::vectorstd::pairint,int untriedMoves; // 还没扩展过的合法着法 int visits; double wins; MCTSNode(const Board b, int p, MCTSNode* par nullptr) : board(b), player(p), parent(par), visits(0), wins(0.0) { untriedMoves board.getLegalMoves(player); } bool fullyExpanded() const { return untriedMoves.empty(); } MCTSNode* bestChild(double c) const { MCTSNode* best nullptr; double bestValue -1e9; for (MCTSNode* child : children) { double exploit child-wins / child-visits; double explore c * sqrt(2.0 * log(visits) / child-visits); double value exploit explore; if (value bestValue) { bestValue value; best child; } } return best; } };bestChild里用到的 UCT 公式采用了“胜率 探索项”。exploit是子节点在过往模拟中的胜率explore让那些访问次数比较少的分支也能被探索到。c是探索常数一般取sqrt(2)约 1.414。我在不围棋上习惯取 1.2因为不围棋随机模拟的方差大探索太猛会让前期选择变得不稳定。主循环可以写成一个函数迭代指定次数。模拟函数里还要注意随机数生成器的复用double simulate(const Board board, int startingPlayer) { Board simBoard board; int player startingPlayer; int steps 0; const int MAX_STEPS 200; static std::mt19937 rng(static_castunsigned(time(nullptr))); while (steps MAX_STEPS) { auto moves simBoard.getLegalMoves(player); if (moves.empty()) { // 当前玩家无棋可下输掉对局 return (player startingPlayer) ? 0.0 : 1.0; } std::uniform_int_distribution dist(0, moves.size() - 1); auto mv moves[dist(rng)]; simBoard simBoard.makeMove(mv.first, mv.second, player); player (player Board::BLACK) ? Board::WHITE : Board::BLACK; steps; } return 0.5; // 超出步数限制按平局处理 }随机引擎必须定义在函数外面或者用static否则每走一步都重新创建随机数装置速度会很差而且同一个棋盘上每次模拟可能拿到完全相同的随机序列。3.3 随机模拟策略与迭代次数的取舍完全随机模拟的噪声很大所以在有限迭代次数下MCTS 的棋力不会特别强。最简单的改进是在模拟阶段使用加权随机某个落子之后自己连通块的气数越多落子概率越高。这个启发式能显著提升模拟质量。我们把这个改进留在第六节再做。先看最基本的 MCTS 入口函数。它的流程是创建根节点 → 迭代selection → expansion → simulation → backpropagation→ 选择访问次数最高的子节点作为己方落子。这里我通过对比根节点和最佳子节点的棋盘差异来反推落子位置std::pairint,int mctsGetMove(const Board rootBoard, int aiPlayer, int iterations) { MCTSNode root(rootBoard, aiPlayer, nullptr); for (int i 0; i iterations; i) { MCTSNode* node root; // 选择一直往下走直到节点未被完全展开 while (!node-children.empty() node-fullyExpanded()) { node node-bestChild(1.2); } // 扩展 MCTSNode* leaf nullptr; if (!node-untriedMoves.empty()) { auto mv node-untriedMoves.back(); node-untriedMoves.pop_back(); Board nextBoard node-board.makeMove(mv.first, mv.second, node-player); int nextPlayer (node-player Board::BLACK) ? Board::WHITE : Board::BLACK; leaf new MCTSNode(nextBoard, nextPlayer, node); node-children.push_back(leaf); } else { leaf node; } // 模拟 double reward simulate(leaf-board, leaf-player); // 回传 while (leaf ! nullptr) { leaf-visits; leaf-wins reward; reward 1.0 - reward; leaf leaf-parent; } } // 选访问次数最高的子节点而不是胜率最高的 MCTSNode* best nullptr; int bestVisits -1; for (MCTSNode* child : root.children) { if (child-visits bestVisits) { bestVisits child-visits; best child; } } for (int r 0; r Board::SIZE; r) { for (int c 0; c Board::SIZE; c) { if (root.board.grid[r][c] ! best-board.grid[r][c]) { return {r, c}; } } } return {0, 0}; }这个实现里有个隐藏问题如果根节点已经没有任何合法着法root.children为空best会是空指针。更好的做法是给节点加一个move字段在扩展时记录对应着法最后直接返回best-move这样也省去了棋盘对比的代码。棋盘对比只是给初学者提供一个最直接的理解路径。4. 用 OpenGL glut 把界面画出来显示、鼠标与 AI 调度4.1 freeglut 环境配置与窗口初始化glut 本身已经比较老现在大家在 Windows 上基本都是用 freeglut 来替代。头文件通常写#include GL/glut.h但在 CMake 项目里需要显式找到 OpenGL 和 GLUTcmake_minimum_required(VERSION 3.10) project(nogo) find_package(OpenGL REQUIRED) find_package(GLUT REQUIRED) add_executable(nogo main.cpp board.cpp mcts.cpp) target_link_libraries(nogo ${OPENGL_LIBRARIES} ${GLUT_LIBRARIES} )Visual Studio 用户则需要在“链接器 → 输入 → 附加依赖项”里加入freeglut.lib opengl32.lib glu32.lib。比起这些配置更麻烦的是运行期找不到freeglut.dll所以把对应的 DLL 放到 exe 同目录是最快的解决办法。窗口初始化是非常固定的模板int main(int argc, char** argv) { glutInit(argc, argv); glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGBA); glutInitWindowSize(600, 600); glutInitWindowPosition(100, 100); glutCreateWindow(NoGo - C MCTS OpenGL); glClearColor(0.9f, 0.9f, 0.9f, 1.0f); glutDisplayFunc(display); glutMouseFunc(mouse); glutTimerFunc(0, aiTimer, 0); glutMainLoop(); return 0; }GLUT_DOUBLE是为了使用双缓冲display末尾要调用glutSwapBuffers()。不要漏掉glutMouseFunc否则鼠标事件永远不会被响应。4.2 绘制棋盘和棋子网格、留白、棋盘坐标绘制这一步的核心不是 OpenGL 有多复杂而是把棋盘坐标和像素坐标映射好。我通常把窗口固定为 600x600棋盘区域 500x500左上角和左侧留 50 像素空白。网格间距是 500 / (9 - 1) 62.5。为了让棋子落在格点上需要把行列换算成像素位置再用TRIANGLE_FAN画圆const int WINDOW_W 600; const int WINDOW_H 600; const int BOARD_OFFSET 50; const int BOARD_PIX 500; int step BOARD_PIX / (Board::SIZE - 1); void drawStone(int x, int y, int color) { float r step * 0.42f; if (color Board::BLACK) { glColor3f(0.1f, 0.1f, 0.1f); } else { glColor3f(0.95f, 0.95f, 0.95f); } glBegin(GL_TRIANGLE_FAN); glVertex2f(x, y); for (int i 0; i 32; i) { float angle 2.0f * 3.14159265f * i / 32; glVertex2f(x cos(angle) * r, y sin(angle) * r); } glEnd(); }注意glOrtho建立的坐标系。初始化时要设置一个与鼠标坐标兼容的投影void reshape(int w, int h) { glViewport(0, 0, w, h); glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluOrtho2D(0, w, 0, h); glMatrixMode(GL_MODELVIEW); }display函数里先画网格再画所有棋子。绘制顺序是棋盘底色、网格线、棋子这样棋子会压住网格线。glutPostRedisplay()每次棋盘变化后都要调用否则画面不会更新。4.3 鼠标回调中的坐标换算与落子流程鼠标回调拿到的是窗口像素坐标但x从左往右y从上往下和 OpenGL 的左下角原点不一致。这里必须先翻转yvoid mouse(int button, int state, int x, int y) { if (button ! GLUT_LEFT_BUTTON || state ! GLUT_DOWN) return; int glX x; int glY WINDOW_H - y; int col (glX - BOARD_OFFSET step / 2) / step; int row (glY - BOARD_OFFSET step / 2) / step; if (row 0 row Board::SIZE col 0 col Board::SIZE currentPlayer Board::BLACK) { if (gameBoard.isLegalMove(row, col, Board::BLACK)) { gameBoard gameBoard.makeMove(row, col, Board::BLACK); currentPlayer Board::WHITE; glutPostRedisplay(); if (gameBoard.hasNoLegalMoves(Board::WHITE)) { // 黑方获胜显示文字或弹窗这里省略 } } } }step / 2是做四舍五入的常用技巧。因为鼠标不可能精确点到格点中心所以把像素偏移加上半格再整除。4.4 接缝问题把 MCTS 放进 UI 循环的两种方式一个常见的认知是 AI 思考时界面必然卡死。其实常用的方案有两种同步阻塞和轮询异步。如果你的迭代次数只有 500 次直接在鼠标回调里调用mctsGetMove也能勉强接受因为棋盘小、耗时不到一秒。如果想要界面不卡可以用glutTimerFunc把 MCTS 的迭代拆成多次。每一帧只跑几十次迭代等累计次数够了再落子void aiTimer(int) { const int MAX_ITERATIONS 2000; const int ITERATIONS_PER_FRAME 50; static MCTSNode* root nullptr; static int remaining 0; static bool initialized false; if (!initialized) { // 递归创建根节点的逻辑需要另外实现这里只演示外部循环 initialized true; remaining MAX_ITERATIONS; } if (remaining 0) { for (int i 0; i ITERATIONS_PER_FRAME; i) { // 在这里执行一轮 MCTS 迭代访问全局 root 节点 // mctsIteration(root); } remaining - ITERATIONS_PER_FRAME; glutTimerFunc(10, aiTimer, 0); } else { // 从 root 中选最佳孩子落子并释放整个树 } }这种轮询方案比std::thread更稳定因为glutMainLoop本身是单线程的你不需要考虑锁和共享数据竞争。期末作业里如果不想引入线程轮询是最好的折中。5. 从编译到运行的常见问题排查避坑指南5.1 glut.h 找不到或链接报 unresolved external symbol现象编译时报fatal error C1083: Cannot open include file: GL/glut.h或者链接时一堆unresolved external symbol。原因glut 不是标准 OpenGL 的一部分默认 Visual Studio 也不会自动带上头文件和库。老式 SGI glut 在 64 位 Windows 上经常出问题需要换成 freeglut。解决把 freeglut 的 include 目录加进“附加包含目录”lib 目录加进“附加库目录”然后链接freeglut.lib opengl32.lib glu32.lib。如果运行时报找不到 DLL把 freeglut.dll 放到 exe 同目录下面。CMake 用户用我前面写的find_package即可这种方式能少踩很多坑。5.2 鼠标点击位置和棋子位置偏移现象明明点在这个空格附近棋子却落在了旁边一格甚至落在棋盘外。原因最常见的是没有把鼠标事件的y翻转成 OpenGL 坐标。窗口坐标和 OpenGL 坐标系的 y 轴方向相反。还有可能是gluOrtho2D的参数和窗口大小不一致。解决鼠标回调里先算y WINDOW_H - y再换成棋盘行号。网格绘制的step和鼠标处理的step必须来自同一个全局变量不要一个用62另一个用WINDOW / SIZE。窗口大小变化时reshape里要更新WINDOW_W/H否则棋盘被拉伸点击映射也会漂。5.3 AI 永远下同一个点或返回非法着法现象AI 每次思考后都走同一步或者走出的位置原本已经有棋子。原因问题往往出在 MCTS 根节点没有正确生成合法着法列表。比如untriedMoves在构造时调用getLegalMoves但此时棋盘状态还未同步导致列表为空。另一个原因是在回传时胜负值没有按视角翻转所有节点的胜率均匀化后谁访问次数多谁被选而某些无用分支占了多数访问。解决先在控制台程序里单独测试MCTSNode构造打印untriedMoves.size()。对于 9x9 空棋盘黑棋和getLegalMoves的数量都应该大于 50。然后调试回传逻辑可以在每次回传时打印路径长度和奖励值检查是否是 1、0、1、0 交替。5.4 程序运行几分钟后内存暴涨现象每走一步 AI 都要用几千个节点几回合之后内存占用持续上升。原因MCTS 每棵树有几百万次节点创建如果每次决策后不释放旧树内存会一直累积。new MCTSNode创建的子节点不会自动被删除。解决在拿到最佳落子后写一个递归释放函数一次性删除整棵树void deleteTree(MCTSNode* node) { for (MCTSNode* child : node-children) { deleteTree(child); } delete node; }在主函数里每轮 AI 决策结束后都要调用并且把指针置空。也可以把节点改成std::unique_ptr但递归释放的代码更好理解也更容易被改成手动内存池。5.5 AI 思考时间过长棋盘像卡死现象点击落子后窗口冻结几秒甚至几十秒。原因迭代次数太大或者simulate每次模拟都重新创建std::random_device随机数生成的开销非常大。还有一个隐藏原因getLegalMoves每次都要遍历所有空点并调用isLegalMove在模拟循环里这一步被反复执行如果棋盘已经接近中盘耗时已经很可观。解决随机数引擎改成全局static std::mt19937不要每次新建。迭代次数先设为 300 跑通再逐步调大。如果希望保持界面流畅用前面写的glutTimerFunc轮询方案让 AI 分帧思考。不要在mouse回调里直接跑 2000 次迭代那是死等。6. 让 MCTS 更聪明的几个小技巧从“能跑”走向“能赢”基础 MCTS 虽然能走棋但你会发现它经常走出一些没意义的棋比如把自己棋子的气一下子堵成 1 口。原因在于随机模拟没有偏向性很多模拟在中盘就崩坏了胜率统计被大量垃圾对局污染。要提升棋力最有效的方法是改模拟策略。第一个技巧是“气数加权随机”。在simulate中不要等概率随机选合法落子而是让落子后己方连通块气数越多的点被选中的概率越高。这样模拟出来的对局更像两个人类在正常下棋最终胜负也更贴近真实实力auto moves simBoard.getLegalMoves(player); if (moves.empty()) break; std::vectorint weights; int totalWeight 0; for (auto mv : moves) { Board after simBoard.makeMove(mv.first, mv.second, player); int lib after.countLiberties(mv.first, mv.second); int w lib * lib 1; weights.push_back(w); totalWeight w; } int rnd std::uniform_int_distribution(0, totalWeight - 1)(rng); int cumulative 0; pairint,int move moves[0]; for (size_t i 0; i moves.size(); i) { cumulative weights[i]; if (rnd cumulative) { move moves[i]; break; } } simBoard simBoard.makeMove(move.first, move.second, player);第二个技巧是最终选子时看“访问次数”而不是“胜率”。在 MCTS 迭代不足时某个子节点可能因为前几次模拟运气好而胜率是 1.0但实际风险很大。访问次数高的节点经过了更多验证作为最终着法更稳。第三个技巧是做个自对弈验证脚本。不要只靠肉眼观察直接让两个 AI 互相下 10 局黑白互换统计合法落子数量和胜负分布。这比任何单元测试都更能证明你的 MCTS 树、合法着法判断和终局逻辑是可靠的。我自己的习惯是先把棋盘逻辑写到控制台可以跑通再套上 MCTS最后才是 OpenGL。每次改动只动一个模块跑一轮自对弈确定没退化再继续。这套顺序也建议你照做它能帮你把“计算概论期末大作业基于C实现的不围棋游戏源码”这个题目拆成几块可以独立验证的小任务。希望帮到你。本文还有配套的精品资源点击获取 C++实现不围棋游戏：MCTS状态管理与OpenGL界面整合实战
简介基于C实现的不围棋游戏完整源码系计算概论期末大作业适合学习游戏编程、蒙特卡洛树搜索与OpenGL交互的学生也可作为课程设计或AI博弈入门范例。不围棋规则中落子若吃掉对方棋子或自杀均判负禁止空手黑棋首手不可落于棋盘中心botzone版无此限制判定逻辑集中在GameRule模块。压缩包共57个文件、2.2MB含14个cpp与14个h源码文件覆盖游戏场景、AI策略、棋盘渲染与存档管理另有17张bmp界面素材、Visual Studio工程文件、README及许可证等目录分工明确。除MCTS主AI外还提供Minmax对照实现与botzone比赛版代码便于对比不同博弈搜索策略OpenGL glut界面及按钮、菜单模块均具复用价值。已有297人浏览学习源码可编译运行并二次开发。1. 不围棋期末作业真正的难点不在 OpenGL而在 MCTS 的状态管理用“计算概论期末大作业基于C实现的不围棋游戏源码”作为题目本质上是让你在一个学期里把三件事串起来用 C 写棋盘逻辑用蒙特卡洛树搜索MCTS做 AI再用 OpenGL 的 glut 工具库把界面画出来。很多同学拿到题目的第一反应是“OpenGL 好难”其实画棋盘、画棋子加起来不过几十行代码真正会让你翻车的反而是“气”的计算、MCTS 的胜负回传以及没想清楚时偶发的非法落子。这里从一个可复现的角度把不围棋核心规则、MCTS 实现要点、glut 界面整合和常见坑位都过一遍适合正在做类似作业的人也适合想用 C 小游戏项目练手的人。2. 不围棋规则与棋盘实现先把“气”算清楚2.1 用 9x9 二维数组表示棋盘不围棋也叫 NoGo规则与围棋很接近但不完全一样你不能落子在一个会导致自己棋子没气的位置也就是禁止自杀。提子依然存在如果你落子后把对手的一整块棋的气全部堵死对方棋子会被提掉你自己的新棋子反而因此获得气。所以判断落子是否合法不是只看落子点本身有没有气还要看提子后的局面。棋盘大小我建议先用 9x9。9 路棋盘对 MCTS 最友好搜索速度快OpenGL 窗口也不需要开很大。数据结构用一个std::vectorstd::vectorint就够了0 表示空点1 表示黑棋2 表示白棋。不要一开始就做 19 路那是给自己找麻烦。这一层可以先定义一个清晰的 Board 接口class Board { public: static const int SIZE 9; enum { EMPTY 0, BLACK 1, WHITE 2 }; std::vectorstd::vectorint grid; Board() : grid(SIZE, std::vectorint(SIZE, EMPTY)) {} // 在副本上模拟落子返回新棋盘 Board makeMove(int r, int c, int color) const; // 计算某个连通区块的气数 int countLiberties(int r, int c) const; // 判断某个位置是否合法 bool isLegalMove(int r, int c, int color) const; // 获取某个颜色方所有合法落子点 std::vectorstd::pairint,int getLegalMoves(int color) const; // 判断某方是否无棋可下 bool hasNoLegalMoves(int color) const; };makeMove返回新棋盘而不是修改原棋盘这条很重要。MCTS 每走一步都要在某个局面下尝试大量落子如果在原棋盘上改来改去回溯时很容易出错。值拷贝虽然慢一点但 9x9 棋盘只有 81 个整数拷贝成本可以忽略。2.2 合法着法判定临时落子、提子、再查气判断一个落子是否合法标准动作就是三步先把棋子放上去再检查对手有没有被提掉的棋子最后检查落子后己方连通块的气数。如果某个对手连通块气数为 0要先从棋盘上移除否则它会占着位置导致你自己的棋块气数算错。下面是makeMove和isLegalMove的核心实现Board Board::makeMove(int r, int c, int color) const { Board next *this; next.grid[r][c] color; int opponent (color BLACK) ? WHITE : BLACK; const int dr[] {-1, 1, 0, 0}; const int dc[] {0, 0, -1, 1}; // 遍历当前落子的四个邻居找到相邻的对手连通块 for (int d 0; d 4; d) { int nr r dr[d], nc c dc[d]; if (nr 0 || nr SIZE || nc 0 || nc SIZE) continue; if (next.grid[nr][nc] ! opponent) continue; // 用 BFS 收集同一个对手连通块 std::vectorstd::pairint,int block; std::vectorstd::vectorbool visited(SIZE, std::vectorbool(SIZE, false)); std::queuestd::pairint,int q; q.push({nr, nc}); visited[nr][nc] true; while (!q.empty()) { auto [x, y] q.front(); q.pop(); block.push_back({x, y}); for (int d2 0; d2 4; d2) { int nx x dr[d2], ny y dc[d2]; if (nx 0 nx SIZE ny 0 ny SIZE !visited[nx][ny] next.grid[nx][ny] opponent) { visited[nx][ny] true; q.push({nx, ny}); } } } // 数这个连通块的气气为 0 就提掉 int liberties 0; for (auto [x, y] : block) { for (int d2 0; d2 4; d2) { int nx x dr[d2], ny y dc[d2]; if (nx 0 nx SIZE ny 0 ny SIZE next.grid[nx][ny] EMPTY) { liberties; } } } if (liberties 0) { for (auto [x, y] : block) { next.grid[x][y] EMPTY; } } } return next; } bool Board::isLegalMove(int r, int c, int color) const { if (grid[r][c] ! EMPTY) return false; Board after makeMove(r, c, color); return after.countLiberties(r, c) 0; }countLiberties需要做一次洪水填充把整个同色连通块找出来然后数它周围空点的个数。很多人会漏掉“提子后再查气”这个顺序直接在落子前用手工数气一旦遇到吃子判断就会出错。实战里最稳的做法就是上面这样把落子后的完整局面算出来再查气永远不猜。2.3 终局判定与随机对局模拟不围棋的终局条件非常简单轮到某方落子时它没有任何合法着法立刻判负。所以终局判定可以直接复用getLegalMovesbool Board::hasNoLegalMoves(int color) const { return getLegalMoves(color).empty(); } std::vectorstd::pairint,int Board::getLegalMoves(int color) const { std::vectorstd::pairint,int moves; for (int r 0; r SIZE; r) { for (int c 0; c SIZE; c) { if (isLegalMove(r, c, color)) { moves.push_back({r, c}); } } } return moves; }这段逻辑很简单但要注意性能每生成一次合法着法列表都要对棋盘上所有空点调用isLegalMove而makeMove内部又有 BFS 和提子所以 9x9 棋盘上生成一次列表可能要跑几万次基础操作。对 MCTS 的模拟来说这个代价还能接受但不要在 AI 思考的循环里反复生成同一份列表。更合理的做法是在扩展节点时把该节点的untriedMoves缓存下来之后模拟阶段每次都从getLegalMoves重新生成也是一种成本。为了验证规则实现得对不对可以先写一个纯控制台自对弈循环随机玩家对随机玩家走一步打印一步看是否有非法落子、是否能正常终局。这一步不过关不要碰 OpenGL 和 MCTS。3. 用蒙特卡洛树搜索实现不围棋 AI核心循环与参数调整3.1 MCTS 四步循环选择、扩展、模拟、回传蒙特卡洛树搜索的核心思路是把当前局面作为根节点反复做“随机对局”来估计每个落子的胜率。整个循环可以被拆成四个阶段所有 MCTS 实现都是这四个阶段的循环选择从根节点出发按照 UCT 公式选择一个子节点再从这个子节点往下选直到到达一个还没有被完全展开的节点。扩展在这个节点上取出一个还没有试过的合法落子创建出一个新的子节点。模拟从新子节点的局面开始让黑白双方随机落子直到一方无棋可下。回传把模拟结果沿着访问过的路径一路往回更新每个节点的访问次数加 1胜负累计值按视角调整。迭代次数决定了 AI 的棋力。9x9 不围棋上几百次迭代能跑通但棋力很弱1000 到 3000 次迭代是性能和棋力都比较均衡的范围。MCTS 不需要人工写评估函数但它需要大量模拟来平滑随机噪声。3.2 节点结构与 UCT 公式的 C 实现每个节点要保存当前棋盘状态、轮到谁下棋、父节点、子节点列表、未被尝试的着法列表、访问次数和累计胜场。为了简化不围棋是二人零和游戏节点里的wins可以只从当前玩家的视角保存回传时翻转即可。struct MCTSNode { Board board; int player; // 当前轮到谁落子 MCTSNode* parent; std::vectorMCTSNode* children; std::vectorstd::pairint,int untriedMoves; // 还没扩展过的合法着法 int visits; double wins; MCTSNode(const Board b, int p, MCTSNode* par nullptr) : board(b), player(p), parent(par), visits(0), wins(0.0) { untriedMoves board.getLegalMoves(player); } bool fullyExpanded() const { return untriedMoves.empty(); } MCTSNode* bestChild(double c) const { MCTSNode* best nullptr; double bestValue -1e9; for (MCTSNode* child : children) { double exploit child-wins / child-visits; double explore c * sqrt(2.0 * log(visits) / child-visits); double value exploit explore; if (value bestValue) { bestValue value; best child; } } return best; } };bestChild里用到的 UCT 公式采用了“胜率 探索项”。exploit是子节点在过往模拟中的胜率explore让那些访问次数比较少的分支也能被探索到。c是探索常数一般取sqrt(2)约 1.414。我在不围棋上习惯取 1.2因为不围棋随机模拟的方差大探索太猛会让前期选择变得不稳定。主循环可以写成一个函数迭代指定次数。模拟函数里还要注意随机数生成器的复用double simulate(const Board board, int startingPlayer) { Board simBoard board; int player startingPlayer; int steps 0; const int MAX_STEPS 200; static std::mt19937 rng(static_castunsigned(time(nullptr))); while (steps MAX_STEPS) { auto moves simBoard.getLegalMoves(player); if (moves.empty()) { // 当前玩家无棋可下输掉对局 return (player startingPlayer) ? 0.0 : 1.0; } std::uniform_int_distribution dist(0, moves.size() - 1); auto mv moves[dist(rng)]; simBoard simBoard.makeMove(mv.first, mv.second, player); player (player Board::BLACK) ? Board::WHITE : Board::BLACK; steps; } return 0.5; // 超出步数限制按平局处理 }随机引擎必须定义在函数外面或者用static否则每走一步都重新创建随机数装置速度会很差而且同一个棋盘上每次模拟可能拿到完全相同的随机序列。3.3 随机模拟策略与迭代次数的取舍完全随机模拟的噪声很大所以在有限迭代次数下MCTS 的棋力不会特别强。最简单的改进是在模拟阶段使用加权随机某个落子之后自己连通块的气数越多落子概率越高。这个启发式能显著提升模拟质量。我们把这个改进留在第六节再做。先看最基本的 MCTS 入口函数。它的流程是创建根节点 → 迭代selection → expansion → simulation → backpropagation→ 选择访问次数最高的子节点作为己方落子。这里我通过对比根节点和最佳子节点的棋盘差异来反推落子位置std::pairint,int mctsGetMove(const Board rootBoard, int aiPlayer, int iterations) { MCTSNode root(rootBoard, aiPlayer, nullptr); for (int i 0; i iterations; i) { MCTSNode* node root; // 选择一直往下走直到节点未被完全展开 while (!node-children.empty() node-fullyExpanded()) { node node-bestChild(1.2); } // 扩展 MCTSNode* leaf nullptr; if (!node-untriedMoves.empty()) { auto mv node-untriedMoves.back(); node-untriedMoves.pop_back(); Board nextBoard node-board.makeMove(mv.first, mv.second, node-player); int nextPlayer (node-player Board::BLACK) ? Board::WHITE : Board::BLACK; leaf new MCTSNode(nextBoard, nextPlayer, node); node-children.push_back(leaf); } else { leaf node; } // 模拟 double reward simulate(leaf-board, leaf-player); // 回传 while (leaf ! nullptr) { leaf-visits; leaf-wins reward; reward 1.0 - reward; leaf leaf-parent; } } // 选访问次数最高的子节点而不是胜率最高的 MCTSNode* best nullptr; int bestVisits -1; for (MCTSNode* child : root.children) { if (child-visits bestVisits) { bestVisits child-visits; best child; } } for (int r 0; r Board::SIZE; r) { for (int c 0; c Board::SIZE; c) { if (root.board.grid[r][c] ! best-board.grid[r][c]) { return {r, c}; } } } return {0, 0}; }这个实现里有个隐藏问题如果根节点已经没有任何合法着法root.children为空best会是空指针。更好的做法是给节点加一个move字段在扩展时记录对应着法最后直接返回best-move这样也省去了棋盘对比的代码。棋盘对比只是给初学者提供一个最直接的理解路径。4. 用 OpenGL glut 把界面画出来显示、鼠标与 AI 调度4.1 freeglut 环境配置与窗口初始化glut 本身已经比较老现在大家在 Windows 上基本都是用 freeglut 来替代。头文件通常写#include GL/glut.h但在 CMake 项目里需要显式找到 OpenGL 和 GLUTcmake_minimum_required(VERSION 3.10) project(nogo) find_package(OpenGL REQUIRED) find_package(GLUT REQUIRED) add_executable(nogo main.cpp board.cpp mcts.cpp) target_link_libraries(nogo ${OPENGL_LIBRARIES} ${GLUT_LIBRARIES} )Visual Studio 用户则需要在“链接器 → 输入 → 附加依赖项”里加入freeglut.lib opengl32.lib glu32.lib。比起这些配置更麻烦的是运行期找不到freeglut.dll所以把对应的 DLL 放到 exe 同目录是最快的解决办法。窗口初始化是非常固定的模板int main(int argc, char** argv) { glutInit(argc, argv); glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGBA); glutInitWindowSize(600, 600); glutInitWindowPosition(100, 100); glutCreateWindow(NoGo - C MCTS OpenGL); glClearColor(0.9f, 0.9f, 0.9f, 1.0f); glutDisplayFunc(display); glutMouseFunc(mouse); glutTimerFunc(0, aiTimer, 0); glutMainLoop(); return 0; }GLUT_DOUBLE是为了使用双缓冲display末尾要调用glutSwapBuffers()。不要漏掉glutMouseFunc否则鼠标事件永远不会被响应。4.2 绘制棋盘和棋子网格、留白、棋盘坐标绘制这一步的核心不是 OpenGL 有多复杂而是把棋盘坐标和像素坐标映射好。我通常把窗口固定为 600x600棋盘区域 500x500左上角和左侧留 50 像素空白。网格间距是 500 / (9 - 1) 62.5。为了让棋子落在格点上需要把行列换算成像素位置再用TRIANGLE_FAN画圆const int WINDOW_W 600; const int WINDOW_H 600; const int BOARD_OFFSET 50; const int BOARD_PIX 500; int step BOARD_PIX / (Board::SIZE - 1); void drawStone(int x, int y, int color) { float r step * 0.42f; if (color Board::BLACK) { glColor3f(0.1f, 0.1f, 0.1f); } else { glColor3f(0.95f, 0.95f, 0.95f); } glBegin(GL_TRIANGLE_FAN); glVertex2f(x, y); for (int i 0; i 32; i) { float angle 2.0f * 3.14159265f * i / 32; glVertex2f(x cos(angle) * r, y sin(angle) * r); } glEnd(); }注意glOrtho建立的坐标系。初始化时要设置一个与鼠标坐标兼容的投影void reshape(int w, int h) { glViewport(0, 0, w, h); glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluOrtho2D(0, w, 0, h); glMatrixMode(GL_MODELVIEW); }display函数里先画网格再画所有棋子。绘制顺序是棋盘底色、网格线、棋子这样棋子会压住网格线。glutPostRedisplay()每次棋盘变化后都要调用否则画面不会更新。4.3 鼠标回调中的坐标换算与落子流程鼠标回调拿到的是窗口像素坐标但x从左往右y从上往下和 OpenGL 的左下角原点不一致。这里必须先翻转yvoid mouse(int button, int state, int x, int y) { if (button ! GLUT_LEFT_BUTTON || state ! GLUT_DOWN) return; int glX x; int glY WINDOW_H - y; int col (glX - BOARD_OFFSET step / 2) / step; int row (glY - BOARD_OFFSET step / 2) / step; if (row 0 row Board::SIZE col 0 col Board::SIZE currentPlayer Board::BLACK) { if (gameBoard.isLegalMove(row, col, Board::BLACK)) { gameBoard gameBoard.makeMove(row, col, Board::BLACK); currentPlayer Board::WHITE; glutPostRedisplay(); if (gameBoard.hasNoLegalMoves(Board::WHITE)) { // 黑方获胜显示文字或弹窗这里省略 } } } }step / 2是做四舍五入的常用技巧。因为鼠标不可能精确点到格点中心所以把像素偏移加上半格再整除。4.4 接缝问题把 MCTS 放进 UI 循环的两种方式一个常见的认知是 AI 思考时界面必然卡死。其实常用的方案有两种同步阻塞和轮询异步。如果你的迭代次数只有 500 次直接在鼠标回调里调用mctsGetMove也能勉强接受因为棋盘小、耗时不到一秒。如果想要界面不卡可以用glutTimerFunc把 MCTS 的迭代拆成多次。每一帧只跑几十次迭代等累计次数够了再落子void aiTimer(int) { const int MAX_ITERATIONS 2000; const int ITERATIONS_PER_FRAME 50; static MCTSNode* root nullptr; static int remaining 0; static bool initialized false; if (!initialized) { // 递归创建根节点的逻辑需要另外实现这里只演示外部循环 initialized true; remaining MAX_ITERATIONS; } if (remaining 0) { for (int i 0; i ITERATIONS_PER_FRAME; i) { // 在这里执行一轮 MCTS 迭代访问全局 root 节点 // mctsIteration(root); } remaining - ITERATIONS_PER_FRAME; glutTimerFunc(10, aiTimer, 0); } else { // 从 root 中选最佳孩子落子并释放整个树 } }这种轮询方案比std::thread更稳定因为glutMainLoop本身是单线程的你不需要考虑锁和共享数据竞争。期末作业里如果不想引入线程轮询是最好的折中。5. 从编译到运行的常见问题排查避坑指南5.1 glut.h 找不到或链接报 unresolved external symbol现象编译时报fatal error C1083: Cannot open include file: GL/glut.h或者链接时一堆unresolved external symbol。原因glut 不是标准 OpenGL 的一部分默认 Visual Studio 也不会自动带上头文件和库。老式 SGI glut 在 64 位 Windows 上经常出问题需要换成 freeglut。解决把 freeglut 的 include 目录加进“附加包含目录”lib 目录加进“附加库目录”然后链接freeglut.lib opengl32.lib glu32.lib。如果运行时报找不到 DLL把 freeglut.dll 放到 exe 同目录下面。CMake 用户用我前面写的find_package即可这种方式能少踩很多坑。5.2 鼠标点击位置和棋子位置偏移现象明明点在这个空格附近棋子却落在了旁边一格甚至落在棋盘外。原因最常见的是没有把鼠标事件的y翻转成 OpenGL 坐标。窗口坐标和 OpenGL 坐标系的 y 轴方向相反。还有可能是gluOrtho2D的参数和窗口大小不一致。解决鼠标回调里先算y WINDOW_H - y再换成棋盘行号。网格绘制的step和鼠标处理的step必须来自同一个全局变量不要一个用62另一个用WINDOW / SIZE。窗口大小变化时reshape里要更新WINDOW_W/H否则棋盘被拉伸点击映射也会漂。5.3 AI 永远下同一个点或返回非法着法现象AI 每次思考后都走同一步或者走出的位置原本已经有棋子。原因问题往往出在 MCTS 根节点没有正确生成合法着法列表。比如untriedMoves在构造时调用getLegalMoves但此时棋盘状态还未同步导致列表为空。另一个原因是在回传时胜负值没有按视角翻转所有节点的胜率均匀化后谁访问次数多谁被选而某些无用分支占了多数访问。解决先在控制台程序里单独测试MCTSNode构造打印untriedMoves.size()。对于 9x9 空棋盘黑棋和getLegalMoves的数量都应该大于 50。然后调试回传逻辑可以在每次回传时打印路径长度和奖励值检查是否是 1、0、1、0 交替。5.4 程序运行几分钟后内存暴涨现象每走一步 AI 都要用几千个节点几回合之后内存占用持续上升。原因MCTS 每棵树有几百万次节点创建如果每次决策后不释放旧树内存会一直累积。new MCTSNode创建的子节点不会自动被删除。解决在拿到最佳落子后写一个递归释放函数一次性删除整棵树void deleteTree(MCTSNode* node) { for (MCTSNode* child : node-children) { deleteTree(child); } delete node; }在主函数里每轮 AI 决策结束后都要调用并且把指针置空。也可以把节点改成std::unique_ptr但递归释放的代码更好理解也更容易被改成手动内存池。5.5 AI 思考时间过长棋盘像卡死现象点击落子后窗口冻结几秒甚至几十秒。原因迭代次数太大或者simulate每次模拟都重新创建std::random_device随机数生成的开销非常大。还有一个隐藏原因getLegalMoves每次都要遍历所有空点并调用isLegalMove在模拟循环里这一步被反复执行如果棋盘已经接近中盘耗时已经很可观。解决随机数引擎改成全局static std::mt19937不要每次新建。迭代次数先设为 300 跑通再逐步调大。如果希望保持界面流畅用前面写的glutTimerFunc轮询方案让 AI 分帧思考。不要在mouse回调里直接跑 2000 次迭代那是死等。6. 让 MCTS 更聪明的几个小技巧从“能跑”走向“能赢”基础 MCTS 虽然能走棋但你会发现它经常走出一些没意义的棋比如把自己棋子的气一下子堵成 1 口。原因在于随机模拟没有偏向性很多模拟在中盘就崩坏了胜率统计被大量垃圾对局污染。要提升棋力最有效的方法是改模拟策略。第一个技巧是“气数加权随机”。在simulate中不要等概率随机选合法落子而是让落子后己方连通块气数越多的点被选中的概率越高。这样模拟出来的对局更像两个人类在正常下棋最终胜负也更贴近真实实力auto moves simBoard.getLegalMoves(player); if (moves.empty()) break; std::vectorint weights; int totalWeight 0; for (auto mv : moves) { Board after simBoard.makeMove(mv.first, mv.second, player); int lib after.countLiberties(mv.first, mv.second); int w lib * lib 1; weights.push_back(w); totalWeight w; } int rnd std::uniform_int_distribution(0, totalWeight - 1)(rng); int cumulative 0; pairint,int move moves[0]; for (size_t i 0; i moves.size(); i) { cumulative weights[i]; if (rnd cumulative) { move moves[i]; break; } } simBoard simBoard.makeMove(move.first, move.second, player);第二个技巧是最终选子时看“访问次数”而不是“胜率”。在 MCTS 迭代不足时某个子节点可能因为前几次模拟运气好而胜率是 1.0但实际风险很大。访问次数高的节点经过了更多验证作为最终着法更稳。第三个技巧是做个自对弈验证脚本。不要只靠肉眼观察直接让两个 AI 互相下 10 局黑白互换统计合法落子数量和胜负分布。这比任何单元测试都更能证明你的 MCTS 树、合法着法判断和终局逻辑是可靠的。我自己的习惯是先把棋盘逻辑写到控制台可以跑通再套上 MCTS最后才是 OpenGL。每次改动只动一个模块跑一轮自对弈确定没退化再继续。这套顺序也建议你照做它能帮你把“计算概论期末大作业基于C实现的不围棋游戏源码”这个题目拆成几块可以独立验证的小任务。希望帮到你。本文还有配套的精品资源点击获取