蒙特卡洛搜索树解中国象棋残局：120关“乌江自刎”实战与优化

简介：这份资源是基于蒙特卡洛搜索树（MCTS）实现中国象棋残局解法的C++源码工程，面向计算机、人工智能及相关专业的在校学生、教师与企业开发者，可用于毕业设计、课程设计、大作业或项目立项演示，帮助理解MCTS在博弈搜索中的落子决策与残局求解思路。压缩包共14个文件，约4.16MB，包含3个cpp源文件、2个h头文件、1个sln解决方案与1个vcxproj工程文件，另有README说明文档和6张jpg效果图，工程结构完整，可直接用Visual Studio打开编译运行。资源以120关“乌江自刎”残局为案例，代码经过功能验证，运行稳定，读者可据此掌握搜索树扩展、模拟与回溯等核心流程，并在此基础上进行二次开发或拓展关卡。目前已有145人学习下载，适合作为入门进阶与实战参考。

1. 蒙特卡洛搜索树解中国象棋残局：120关“乌江自刎”到底难在哪

中国象棋残局“乌江自刎”是很多棋类算法爱好者绕不开的一道坎。它不像开局那样有海量棋谱可查，也不像中局那样靠评估函数就能蒙混过关——残局子力少、分支窄，但每一步都可能是生死手，传统 alpha-beta 剪枝一旦评估函数写得粗糙，就会在“看似均势实则必败”的局面里反复翻车。蒙特卡洛搜索树（MCTS）换了个思路：不靠精确评估，靠大量随机模拟统计胜率，配合 UCB 公式平衡探索与利用，天然适合这种“算不清但可以试”的场景。这套 C++ 源码把 MCTS 落到 120 关残局上，核心要解决三件事：走法生成要快、模拟要够随机、搜索要能收敛。适合已经会 C++ 基础语法、想拿一个完整项目练手搜索算法的开发者，也适合想理解 MCTS 从论文公式到可运行代码之间那段“血泪经验”的棋类爱好者。

2. MCTS 为什么能啃下残局：从 UCB 公式到象棋走法生成

2.1 残局搜索的痛点与 MCTS 的选型理由

中国象棋残局和开局最大的区别在于：开局有谱可循，中局有势可判，残局往往只剩几个子，但胜负判定极其尖锐。比如“乌江自刎”这类排局，红方可能只有车马炮，黑方只剩将和士象，表面看红方大优，实际上黑方有一步隐蔽的困毙或反杀。传统 alpha-beta 搜索依赖评估函数给叶子节点打分，残局里子力价值表基本失效——一个过河兵的价值可能超过一个未出动的车。评估函数写不准，搜索越深错得越离谱。

MCTS 的选型理由就在这里：它不需要静态评估函数，而是通过随机走子到终局，用胜负结果反向更新节点胜率。四个阶段——选择、扩展、模拟、回溯——构成一次完整迭代。选择阶段用 UCB1 公式：

UCB1 = (w_i / n_i) + c * sqrt(ln(N) / n_i)

其中w_i是节点 i 的累计胜场，n_i是访问次数，N是父节点总访问次数，c是探索常数。第一项利用已知好棋，第二项鼓励访问少的节点。残局分支因子小，单次模拟很快，几万次迭代就能把关键分支的胜率差异拉开。

但 MCTS 在象棋上有个天然缺陷：随机模拟的走法质量太差，纯随机走子到终局，胜率信号噪声极大。常见做法是给模拟阶段加轻量级启发：优先吃子、优先将军、避免送子。这套源码里模拟策略不是纯随机，而是带权重的走法选择，权重表需要根据残局特点调。

2.2 棋盘表示与走法生成：用数组还是位棋盘

C++ 实现象棋引擎，第一个决策是棋盘数据结构。常见三种：

这套 120 关残局源码我建议用一维数组起步。残局子力少，走法生成不是瓶颈，一维数组的index = row * 9 + col映射足够快，而且代码可读性好，方便后面加调试输出。走法生成的核心是遍历己方所有棋子，对每个棋子按规则生成合法走法，再过滤掉走后被将军的情况。

// 一维数组棋盘，红方在上，黑方在下 const int BOARD_SIZE = 90; int board[BOARD_SIZE]; // 0=空, 正数=红方, 负数=黑方 // 判断坐标是否在棋盘内 inline bool inBoard(int row, int col) { return row >= 0 && row < 10 && col >= 0 && col < 9; } // 生成红方某个车的所有走法 void genRookMoves(int row, int col, std::vector<Move>& moves) { // 四个方向：上下左右 int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; for (auto& d : dirs) { int r = row + d[0], c = col + d[1]; while (inBoard(r, c)) { int target = board[r * 9 + c]; if (target == 0) { moves.push_back({row, col, r, c}); // 空位可走 } else { if (target * board[row * 9 + col] < 0) // 敌子 moves.push_back({row, col, r, c}); break; // 遇到任何子都停 } r += d[0]; c += d[1]; } } }

逻辑说明：board用正负区分红黑，target * board[...] < 0判断敌我。车走法沿四个方向延伸，遇到空位继续，遇到敌子可吃但停止，遇到己方子直接停止。参数上，row和col是棋子当前位置，moves是输出向量。残局里车是主力，这段代码的正确性直接决定搜索质量。

注意：将帅不能照面，走法生成后必须加一步“帅将同列且中间无子”的过滤，否则模拟阶段会出现非法局面，胜率统计全乱。

2.3 MCTS 主循环的 C++ 实现骨架

MCTS 主循环不复杂，难在内存管理和节点选择效率。每个节点存：棋盘状态、父节点指针、子节点列表、访问次数、累计胜场、待扩展走法列表。

struct Node { int board[90]; Node* parent; std::vector<Node*> children; std::vector<Move> untriedMoves; int visits = 0; double wins = 0.0; int playerJustMoved; // 刚走完的是哪方 }; Node* select(Node* node) { while (!node->untriedMoves.empty() == false && !node->children.empty()) { node = bestUCTChild(node); } return node; } Node* expand(Node* node) { if (node->untriedMoves.empty()) return node; Move m = node->untriedMoves.back(); node->untriedMoves.pop_back(); Node* child = new Node(); memcpy(child->board, node->board, sizeof(child->board)); applyMove(child->board, m); child->parent = node; child->playerJustMoved = -node->playerJustMoved; generateMoves(child->board, child->playerJustMoved, child->untriedMoves); node->children.push_back(child); return child; }

逻辑说明：select沿 UCB 最大的子节点一路向下，直到遇到还有未扩展走法的节点。expand取一个未试走法，生成新节点，并预生成该节点的所有走法。playerJustMoved用来判断模拟结束时谁赢了。参数上，untriedMoves在节点创建时一次性生成，避免重复计算。

模拟阶段用带权重的随机走子，权重规则：吃子 +3，将军 +2，走子到对方九宫附近 +1，其余 +0.1。回溯阶段从扩展节点一路更新到根，visits++，如果模拟结果是“刚走完的一方赢了”，则wins += 1。

3. 把 120 关残局跑起来：从加载 FEN 到输出最佳走法

3.1 残局关卡的数据格式与解析

120 关残局如果每关都硬编码棋盘数组，代码会臃肿到没法维护。常见做法是用 FEN 字符串描述局面。中国象棋 FEN 和国象类似：rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w，其中小写黑方、大写红方，数字表示连续空位数，最后的w表示轮到红方走。

解析函数要处理三件事：按/分行、按字符填棋盘、识别走子方。

bool loadFEN(const std::string& fen, int board[90], int& sideToMove) { memset(board, 0, sizeof(int) * 90); int row = 0, col = 0; size_t i = 0; while (i < fen.size() && fen[i] != ' ') { char c = fen[i]; if (c == '/') { row++; col = 0; } else if (isdigit(c)) { col += c - '0'; } else { int piece = charToPiece(c); // 自定义映射 board[row * 9 + col] = piece; col++; } i++; } // 跳过空格，读走子方 while (i < fen.size() && fen[i] == ' ') i++; sideToMove = (i < fen.size() && fen[i] == 'w') ? 1 : -1; return true; }

逻辑说明：charToPiece把K映射为红帅（比如 1），k映射为黑将（-1），车马炮士象兵依次给不同数值。sideToMove为 1 表示红走，-1 表示黑走。参数上，FEN 字符串必须合法，否则col可能越界，实际项目里要加边界检查。

注意：中国象棋 FEN 没有统一标准，有的用w/b，有的用r/b，加载前先确认关卡文件的格式，否则走子方判断反了，MCTS 搜出来的全是对方的棋。

3.2 单关搜索的完整调用流程

一关残局的求解流程：加载 FEN → 构建根节点 → 循环迭代 MCTS → 输出访问次数最多的走法。迭代次数根据残局复杂度设，简单残局 5000 次就收敛，复杂排局可能要 50000 次以上。

Move solveOnePuzzle(const std::string& fen, int iterations) { int board[90], side; loadFEN(fen, board, side); Node* root = new Node(); memcpy(root->board, board, sizeof(board)); root->playerJustMoved = -side; // 轮到 side 走，所以刚走完的是 -side generateMoves(root->board, side, root->untriedMoves); for (int i = 0; i < iterations; i++) { Node* node = select(root); if (!node->untriedMoves.empty()) node = expand(node); double result = simulate(node->board, node->playerJustMoved); backpropagate(node, result); } // 选访问次数最多的子节点对应走法 Node* best = nullptr; int maxVisits = -1; for (Node* child : root->children) { if (child->visits > maxVisits) { maxVisits = child->visits; best = child; } } return extractMove(root, best); }

逻辑说明：simulate从当前局面随机走子到终局，返回 1 表示playerJustMoved赢，0 表示输或和。backpropagate沿父链更新visits和wins。最后选访问次数最多的子节点，而不是胜率最高的——访问次数多说明 MCTS 把最多计算资源投在了这个分支，统计置信度更高。参数上，iterations是唯一需要按关卡调的，建议先跑 10000 次看结果，不收敛再加。

3.3 批量跑 120 关的脚本与结果校验

单关调通后，批量跑 120 关需要把每关 FEN 存成一行，用循环读取。结果校验不能只看“有没有解”，还要看解是否合法、是否在限定步数内。

// puzzles.txt 每行一个 FEN std::ifstream fin("puzzles.txt"); std::string fen; int puzzleId = 1; while (std::getline(fin, fen)) { if (fen.empty()) continue; Move best = solveOnePuzzle(fen, 20000); std::cout << "Puzzle " << puzzleId << ": " << moveToString(best) << std::endl; puzzleId++; }

逻辑说明：moveToString把走法转成“炮二平五”这类中文记谱或坐标记谱。批量跑的时候建议加超时，单关超过 30 秒就跳过并记录，避免某一关因为分支爆炸卡死整个流程。参数上，20000是迭代次数，120 关全跑完大概几分钟到十几分钟，取决于机器性能。

注意：批量跑之前先确认所有 FEN 的走子方正确。我踩过的坑是有一关 FEN 末尾漏了w，解析默认黑走，结果 MCTS 帮黑方找了一步绝杀，输出看起来“有解”，实际是帮对手解的。

4. 避坑与排查：MCTS 解残局最容易翻车的 5 个地方

4.1 模拟阶段死循环，程序卡死不出结果

现象：跑某一关时 CPU 占满但迟迟不输出，调试发现simulate函数里走子循环停不下来。原因：残局里双方都没有进攻子力时，随机走子可能反复走帅和将，永远到不了终局。解决：模拟阶段加步数上限，比如 200 步还没分胜负就判和，返回 0.5。同时检测重复局面，同一局面出现三次直接判和。

4.2 UCB 探索常数 c 设错，好棋被埋没

现象：明明有一招绝杀，MCTS 却选了另一步平淡的棋。原因：c值太大，探索项压过利用项，算法一直在试新走法，没深挖已知好棋。解决：残局分支少，c设 0.5 到 1.0 之间，先用 0.7 跑，看最佳走法的访问次数占比，低于 30% 就调小c。

4.3 走法生成漏掉“将帅照面”过滤

现象：模拟出来的局面里帅和将直接对面，按规则这是非法局面，但程序照常继续。原因：走法生成只检查了棋子自身规则，没加全局合法性过滤。解决：在generateMoves最后加一步：对每个走法，模拟走子后检查帅将是否同列且中间无子，有则剔除。

4.4 内存泄漏，跑几十关后程序崩溃

现象：批量跑前几关正常，跑到三四十关时内存占用飙升，最后bad_alloc。原因：每次expand都new Node，但搜索结束后没有释放整棵树。解决：每关求解完调用deleteTree(root)递归释放，或者用内存池预分配节点，避免频繁new/delete。

4.5 胜率统计方向搞反，输出最差走法

现象：MCTS 输出的走法看起来是送子，但访问次数最高。原因：backpropagate里更新wins时，判断的是“当前节点玩家是否赢了”，但playerJustMoved在回溯过程中没有正确翻转。解决：回溯时从模拟结果出发，每上一层翻转一次胜负归属，确保每个节点的wins都是“该节点刚走完的那方赢的次数”。

5. 让 MCTS 更准：用置换表去重和渐进式加宽收尾

MCTS 在残局里最大的浪费是重复搜索相同局面。象棋走法顺序不同但到达同一局面很常见，比如先平炮再跳马和先跳马再平炮。加一张置换表（transposition table），用 Zobrist 哈希把局面映射到节点指针，搜索前先查表，命中就直接复用访问次数和胜场。

// Zobrist 哈希：每个棋子在每个位置一个随机数 uint64_t zobrist[15][90]; uint64_t computeHash(int board[90]) { uint64_t h = 0; for (int i = 0; i < 90; i++) { if (board[i] != 0) h ^= zobrist[board[i] + 7][i]; } return h; } std::unordered_map<uint64_t, Node*> transTable; Node* getOrCreateNode(int board[90], Node* parent) { uint64_t h = computeHash(board); auto it = transTable.find(h); if (it != transTable.end()) return it->second; Node* node = new Node(); memcpy(node->board, board, sizeof(node->board)); node->parent = parent; transTable[h] = node; return node; }

逻辑说明：zobrist[15][90]覆盖所有棋子类型和位置，board[i] + 7把 -7 到 7 的棋子值映射到 0 到 14。computeHash用异或累加，走子时只需异或旧位置和新位置，不用全盘重算。参数上，置换表用unordered_map实现简单，但哈希冲突概率随节点数上升，大规模搜索建议换成固定大小的数组表加替换策略。

渐进式加宽是另一个实用技巧：初始只扩展访问次数最多的几个走法，随着迭代增加逐步放开冷门走法。残局里很多走法一看就是废棋，全量扩展浪费算力。具体做法是给每个节点的untriedMoves按启发式排序，前 5 个先扩展，访问次数超过阈值后再扩展后面的。

我自己的习惯是：先用纯 MCTS 跑通 120 关，记录每关的迭代次数和耗时，然后加置换表看能省多少，最后调渐进式加宽的阈值。不要一上来就堆优化，否则出问题时分不清是算法错还是优化错。这套源码的价值不在代码多长，而在它把 MCTS 从公式到能跑通残局的每一步都摊开了，你照着改参数、加调试输出，就能理解搜索算法在棋类问题上的真实边界。希望帮到你。

本文还有配套的精品资源，点击获取