简介：这份资源面向计算机、人工智能及相关专业的在校学生与开发者，提供一套基于蒙特卡洛搜索树（MCTS）求解中国象棋残局的C++完整源码，内含120关「乌江自刎」残局案例，可用于毕业设计、课程设计、大作业或算法入门进阶练习。压缩包共14个文件，约4.16MB，以cpp与h源码文件为核心，配合sln与vcxproj工程文件可直接在Visual Studio中打开编译，另附README说明文档与多张残局示意图，便于理解棋盘状态与搜索过程。目前已有145人学习关注。代码经过功能验证，运行稳定，读者可借此掌握MCTS的节点扩展、模拟与回溯机制，并观察其在象棋博弈中的落子决策效果，也可在此基础上替换评估函数、调整搜索深度或扩展更多残局关卡，作为二次开发与算法对比实验的起点。
1. 从「乌江自刎」说起：MCTS 解中国象棋残局到底在解什么
中国象棋残局里有一类局面特别折磨人：红方只剩车马炮加几个兵，黑方士象全但缺一匹马，理论上红方必胜，可你坐在棋盘前推演半小时也找不到那条唯一的杀路。120 关「乌江自刎」这类残局合集，本质就是把这种「人类算不清、但机器能穷举」的局面打包成题库。用蒙特卡洛搜索树（MCTS）去解它，不是让程序「下棋下得好」，而是让它在有限步数内找到一条从当前局面到将死的强制路径。
这件事适合谁做？一是想拿 C++ 练手搜索算法的学生，二是想给自己的象棋程序加一个残局求解模块的开发者，三是单纯想搞明白 MCTS 为什么在围棋上封神、在象棋残局里却要改一堆参数的人。它不需要你懂深度学习，但需要你理解「随机模拟 + 树形统计」这套逻辑在确定性完全信息博弈里的边界在哪。下面我从选型理由讲到能跑通的代码骨架，再讲我踩过的坑。
2. MCTS 解残局的核心机制：为什么不能直接套围棋那套
2.1 残局求解和普通对弈是两回事
普通象棋 AI 用 Alpha-Beta 剪枝加置换表，深度 8 到 12 层就能下得不错。但残局求解的目标不是「胜率最高的一步」，而是「存在一条强制将死路径」。这意味着搜索必须偏向「窄而深」，而不是「宽而浅」。MCTS 的四个阶段——选择、扩展、模拟、回传——在残局里要改两个地方：模拟阶段不能随机走到底，要用轻量启发式快速判定「这个分支有没有杀棋苗头」；回传阶段不能只回传胜负，要回传「距离将死的步数」作为奖励信号。
我一般会把残局求解的 MCTS 分成两种模式：一种是「证明模式」，只关心能不能找到杀棋，找到就停；另一种是「优化模式」，在所有杀棋路径里找最短的那条。120 关这种题库，通常要求输出最短杀法，所以奖励函数要设计成reward = 1 / (步数 + 1)，步数越短奖励越高。
2.2 节点结构怎么设计才不爆内存
C++ 里写 MCTS，节点结构是第一个要拍板的东西。残局搜索树的分支因子虽然比开局小，但深度可能到 20 到 30 层，节点数轻松上百万。我的做法是节点只存必要信息：局面哈希、访问次数、累计奖励、父节点指针、子节点索引列表。局面本身不存，用 Zobrist 哈希做键，需要时从哈希表反查。
struct MCTSNode { uint64_t zobristKey; // 局面哈希，用于置换表查重 int visitCount; // 访问次数 double totalReward; // 累计奖励 int parentIndex; // 父节点在池中的下标，-1 表示根 std::vector<int> children; // 子节点下标列表 int moveFrom, moveTo; // 到达该节点的走法 bool isTerminal; // 是否终局 };这里用std::vector<MCTSNode>做节点池，而不是每个节点new一个对象。原因是残局搜索频繁创建销毁节点，裸指针加new/delete会产生大量内存碎片，跑 120 关下来性能差距能到 3 倍以上。节点池预分配 200 万个节点，用下标代替指针，缓存友好性也更好。
参数上，visitCount和totalReward用int和double是权衡后的选择。visitCount不会超过百万级，int够用；totalReward要累加浮点奖励，double精度足够。如果你要做分布式搜索，这两个字段要改成原子类型，但单机残局求解没必要。
2.3 UCT 公式在残局里的参数调法
UCT 是 MCTS 的选择核心：UCB = reward/visit + C * sqrt(ln(parentVisit)/visit)。围棋里 C 取 1.414 左右，但残局里这个值要调小。原因是残局分支少，探索空间有限，C 太大反而会在劣着上浪费模拟次数。我实测下来 C 取 0.5 到 0.8 比较稳，具体看残局复杂度。
double uctValue(const MCTSNode& node, const MCTSNode& parent, double C) { if (node.visitCount == 0) return 1e9; // 未访问节点优先 double exploitation = node.totalReward / node.visitCount; double exploration = C * std::sqrt(std::log(parent.visitCount) / node.visitCount); return exploitation + exploration; }注意visitCount == 0时返回一个极大值，这是标准做法，保证每个子节点至少被访问一次。但残局里有个坑：如果某个子节点一访问就发现是将死，它的奖励会极高，后续 UCT 会一直偏向它，导致其他分支饿死。解决办法是在回传时对「已确认杀棋」的节点做标记，一旦找到最短杀棋路径就提前终止搜索。
3. 从零搭一个能跑 120 关的 C++ 求解器
3.1 棋盘表示和走法生成
中国象棋棋盘 9 列 10 行，我用int board[10][9]存棋子编码，红方正数、黑方负数，0 表示空。走法生成要处理车、马、炮、兵、士、象、将七种棋子的规则，其中马腿和象眼是新手最容易写错的地方。
// 马的八个方向，前两个是腿的偏移，后两个是目标偏移 const int horseMoves[8][4] = { {-1, 0, -2, -1}, {-1, 0, -2, 1}, {1, 0, 2, -1}, {1, 0, 2, 1}, {0, -1, -1, -2}, {0, -1, 1, -2}, {0, 1, -1, 2}, {0, 1, 1, 2} }; void generateHorseMoves(const int board[10][9], int r, int c, std::vector<Move>& moves) { int side = board[r][c] > 0 ? 1 : -1; for (auto& m : horseMoves) { int legR = r + m[0], legC = c + m[1]; int toR = r + m[2], toC = c + m[3]; if (toR < 0 || toR > 9 || toC < 0 || toC > 8) continue; if (board[legR][legC] != 0) continue; // 蹩马腿 if (board[toR][toC] * side > 0) continue; // 不能吃己方 moves.push_back({r, c, toR, toC}); } }这段代码里side用来判断目标格是不是己方棋子，board[toR][toC] * side > 0的意思是「目标格棋子和我同号」，同号就不能走。马腿判断是board[legR][legC] != 0，只要腿的位置有棋子就蹩住，不管对方还是己方。这个逻辑我见过有人写成只判对方棋子，结果己方棋子挡马腿的残局全解错。
走法生成完整版还要处理将帅照面、士象不能出九宫和过河等规则。将帅照面可以在生成走法后做一次合法性过滤，也可以在每个棋子生成时判断。我选后者，因为残局里将帅照面出现频率高，提前剪掉能省不少模拟次数。
3.2 MCTS 主循环的四个阶段
主循环就是反复执行选择、扩展、模拟、回传，直到达到时间限制或找到杀棋。残局求解我一般设两个终止条件：找到深度小于等于 N 的杀棋，或者搜索时间超过 5 秒。
Move solveByMCTS(const Board& root, int maxDepth, double timeLimit) { std::vector<MCTSNode> pool; pool.reserve(2000000); pool.push_back(createRoot(root)); auto startTime = std::chrono::steady_clock::now(); while (true) { auto elapsed = std::chrono::duration<double>( std::chrono::steady_clock::now() - startTime).count(); if (elapsed > timeLimit) break; int nodeIdx = selectAndExpand(pool, root); double reward = simulate(pool[nodeIdx], maxDepth); backpropagate(pool, nodeIdx, reward); if (foundMate(pool)) break; // 找到杀棋提前退出 } return bestMove(pool); }selectAndExpand从根节点往下走，遇到未完全扩展的节点就扩展一个新子节点并返回。simulate从该节点开始做随机模拟，但残局里纯随机模拟效率极低，我改成「带启发的浅层搜索」：模拟时优先走将军、吃子、靠近九宫的走法，深度限制在 10 到 15 步，如果模拟结束还没分出胜负就返回 0.5 的平局奖励。
backpropagate从当前节点一路回传到根，每个节点的visitCount加一，totalReward加上奖励值。注意奖励值要按步数衰减，否则 MCTS 会倾向于选择「走得远但最终能赢」的路径，而不是最短杀棋。
3.3 模拟阶段的启发式策略
纯随机模拟在象棋残局里基本不可用，因为随机走法大概率会走出循环或者被对方反杀。我的做法是给模拟加三层过滤：第一层，如果当前有将军走法，优先走将军；第二层，如果没有将军，优先走吃子走法，尤其是吃对方防守子力；第三层，如果都没有，走靠近对方将的走法。
Move pickSimulationMove(const Board& board, const std::vector<Move>& moves) { std::vector<Move> mateMoves, captureMoves, forwardMoves; for (auto& m : moves) { Board next = applyMove(board, m); if (isCheckmate(next)) return m; // 直接杀棋，立即返回 if (isCheck(next)) mateMoves.push_back(m); else if (board[m.toR][m.toC] != 0) captureMoves.push_back(m); else if (isForwardMove(board, m)) forwardMoves.push_back(m); } if (!mateMoves.empty()) return mateMoves[rand() % mateMoves.size()]; if (!captureMoves.empty()) return captureMoves[rand() % captureMoves.size()]; if (!forwardMoves.empty()) return forwardMoves[rand() % forwardMoves.size()]; return moves[rand() % moves.size()]; }这段代码里isCheckmate判断走完后对方是否被将死，isCheck判断是否将军。注意applyMove要返回新棋盘而不是原地修改，否则模拟会污染真实棋盘状态。这个坑我踩过：早期版本为了省内存原地修改棋盘，结果模拟结束后忘记撤销，导致搜索树里的局面全乱了。
4. 120 关批量求解的工程化处理
4.1 残局文件的解析和局面加载
120 关「乌江自刎」通常以文本文件存储，每关一个 FEN 串或者自定义格式。我见过的格式有「红方棋子坐标 + 黑方棋子坐标 + 轮到谁走」这种，解析时要处理坐标越界和棋子编码不合法的情况。
bool loadEndgame(const std::string& line, Board& board, int& sideToMove) { std::fill(&board[0][0], &board[0][0] + 90, 0); std::istringstream iss(line); std::string token; while (iss >> token) { if (token == "RED") { sideToMove = 1; continue; } if (token == "BLACK") { sideToMove = -1; continue; } // token 格式如 "R1a" 表示红车在 a 列 1 行 char piece = token[0]; int col = token[1] - 'a'; int row = token[2] - '1'; if (row < 0 || row > 9 || col < 0 || col > 8) return false; board[row][col] = encodePiece(piece, sideToMove); } return true; }encodePiece把字符映射成整数编码，红方正数黑方负数。这里要注意sideToMove的解析顺序：如果文件里先写棋子再写轮到谁走，sideToMove在解析棋子时还是默认值，会导致棋子颜色全错。我的做法是先扫一遍 token 列表找到 RED/BLACK 标记，再解析棋子。
4.2 多关并行和结果输出
120 关串行跑，每关 5 秒，总共 10 分钟。如果每关给 10 秒，就是 20 分钟。实际调试时这个时间太长，我一般用std::thread开 4 到 8 个线程并行跑，每个线程处理一关，结果写到独立的输出文件。
void solveAll(const std::vector<std::string>& endgames, int threadCount) { std::vector<std::thread> workers; std::atomic<int> nextIdx{0}; for (int t = 0; t < threadCount; ++t) { workers.emplace_back([&]() { while (true) { int idx = nextIdx.fetch_add(1); if (idx >= (int)endgames.size()) break; Board board; int side; if (!loadEndgame(endgames[idx], board, side)) { printf("Level %d: parse error\n", idx + 1); continue; } Move best = solveByMCTS(board, 30, 5.0); printf("Level %d: %c%d -> %c%d\n", idx + 1, best.fromC + 'a', best.fromR + 1, best.toC + 'a', best.toR + 1); } }); } for (auto& w : workers) w.join(); }nextIdx用原子变量做任务分发，每个线程抢一个关卡号。注意solveByMCTS内部不能有共享状态，否则多线程会互相干扰。我早期版本把置换表设成全局变量，多线程跑的时候哈希冲突频发，结果全错。后来改成每个线程独立的置换表，内存占用翻倍但结果稳定。
4.3 求解结果的验证方法
MCTS 找到的杀棋路径不一定最短，也不一定正确。验证方法有两种：一是用独立的 Alpha-Beta 搜索做交叉验证，二是人工抽查关键关卡。我一般先跑一遍 Alpha-Beta 深度 12 层，把结果作为基准，再用 MCTS 跑，对比两者输出的第一步是否一致。
bool verifyMate(const Board& board, const std::vector<Move>& path, int side) { Board cur = board; for (auto& m : path) { if (!isLegalMove(cur, m, side)) return false; cur = applyMove(cur, m); side = -side; if (isCheckmate(cur)) return side != 0; // 对方被将死 } return false; }verifyMate逐歩检查走法合法性，最后判断是否将死。如果 MCTS 输出的路径超过 20 步还没将死，大概率是模拟阶段的启发式出了问题，需要调低 UCT 的 C 值或者增加模拟深度。
5. 避坑与排查：残局求解里最容易翻车的五个地方
5.1 现象：搜索跑了一分钟还没结果，CPU 占用 100% 但内存不涨
原因通常是模拟阶段陷入了循环。象棋残局里双方来回走同一组走法很常见，纯随机模拟如果没有步数上限，会一直循环下去。解决方法是给模拟加硬性步数限制，比如 50 步内没分出胜负就返回平局奖励。另外可以在模拟路径上记录局面哈希，发现重复局面立即终止。
5.2 现象：MCTS 输出的第一步是「送子」，明显是劣着
原因是奖励函数设计有问题。如果奖励只看最终胜负，不看步数，MCTS 会认为「送子但 20 步后赢」和「不送子 5 步赢」是一样的。解决办法是把奖励改成1 / (步数 + 1)，步数越短奖励越高。另外 UCT 的 C 值太大也会导致探索过度，调小到 0.5 试试。
5.3 现象：多线程跑的时候结果不稳定，同一关两次跑出不同答案
原因是共享了置换表或者随机数生成器。rand()在多线程下不是线程安全的，要用std::mt19937每个线程独立种子。置换表如果全局共享，读写冲突会导致哈希表损坏。我的做法是每个线程一个独立的std::unordered_map做置换表，内存换稳定。
5.4 现象：某些关卡解析出来棋盘是空的，或者棋子颜色全反
原因是残局文件格式不统一。有的文件用「红方在上黑方在下」，有的反过来；有的用坐标a1到i10，有的用1-9和0-9。解决方法是解析前先打印原始行，人工确认格式，再写对应的解析逻辑。不要假设所有关卡格式一致。
5.5 现象：找到的杀棋路径超过 30 步，人类棋谱里明明有 10 步杀
原因是 MCTS 的模拟深度不够，或者启发式太弱，导致短杀路径被淹没在长路径里。解决办法是增加模拟深度到 20 步以上，同时在选择阶段对「将军」走法给额外奖励。另外可以先用 Alpha-Beta 做浅层搜索，把明显有杀棋的分支标记出来，MCTS 优先探索这些分支。
6. 进阶技巧：用置换表和迭代加深把求解速度再提一倍
置换表在 MCTS 里的用法和 Alpha-Beta 不同。Alpha-Beta 的置换表存的是「局面 + 深度 + 评分」，MCTS 的置换表存的是「局面哈希 → 节点下标」，用来在扩展阶段快速判断这个局面是否已经出现过。如果出现过，直接复用已有节点，不再新建。
int findOrCreateNode(std::vector<MCTSNode>& pool, std::unordered_map<uint64_t, int>& transTable, const Board& board, int parentIdx, Move move) { uint64_t key = zobristHash(board); auto it = transTable.find(key); if (it != transTable.end()) { return it->second; // 已有节点，直接复用 } int idx = pool.size(); pool.push_back(createNode(board, parentIdx, move)); transTable[key] = idx; return idx; }zobristHash用随机数表对每个棋子的每个位置做异或，走子时增量更新。注意置换表要限制大小，超过 500 万条时清空重建，否则内存会爆。我一般设 200 万条上限，跑 120 关够用。
迭代加深是另一个提速手段：先跑 1 秒搜索，如果找到杀棋就停；没找到就延长到 3 秒；再没找到延长到 5 秒。这样简单关卡几秒内出结果，复杂关卡才用满时间。实测下来 120 关总耗时从 10 分钟降到 4 分钟左右。
最后说个我自己的习惯：每次改完参数，先拿第 1 关和第 60 关做回归测试，这两关一个简单一个复杂，能快速判断改动是正向还是负向。别一上来就跑全部 120 关，浪费时间还看不出问题。希望帮到你。
本文还有配套的精品资源，点击获取
