Visual C++实现苏拉卡塔人机博弈：alpha-beta剪枝与状态空间搜索

简介surakarta.rar是一份基于Visual C实现的Surakarta棋类人机博弈小项目面向对游戏AI、alpha-beta搜索算法以及C工程组织感兴趣的初学者。压缩包共8个文件包含3个cpp源码、3个头文件和2个exe可执行程序整体仅296KB轻量易读。主要代码模块分工明确value.cpp/h提供棋局估值函数search.cpp/h实现带剪枝的alpha-beta搜索main.cpp负责程序流程而Surakarta.exe和Project2.exe可直接运行体验人机对战。已有209人学习/下载。通过这个小项目可以直观理解博弈树搜索的剪枝策略与评估函数的设计思路同时也能参考Visual Studio下.h/.cpp文件的组织方式适合作为游戏AI和C实践入门的学习素材。1. 苏拉卡塔不是五子棋Visual C 人机博弈与状态空间搜索这份 rar 包名字里带“搜索引擎”但拆开看它其实是一套用 Visual C 写成的苏拉卡塔Surakarta人机对战程序。苏拉卡塔是 6×6 棋盘、靠四角环形轨道吃子的印尼传统棋规则比象棋简单搜索分支数却不低正好拿来做 alpha-beta 剪枝的练手对象。包里两个 exe 可以直接跑起来体验棋感更值钱的是 main.cpp、search.cpp、value.cpp 这一组源码入口、算法、估值函数分得清清楚楚。想学博弈搜索、想搞懂 Visual C 工程怎么拆文件的人照着编译一遍、改一个估值权重、调一档搜索深度比纯看书直观得多。下面从工程结构、算法配合、编译排错到扩展验证逐层拆开讲。2. 工程结构拆解main.cpp、define.h 与 search/value 的职责边界拿到压缩包先别急着双击 exe把文件摆开看一遍再动手。包里源文件是一个很典型的控制台项目组织define.h 放公共定义main.cpp 是入口和回合循环search.h/search.cpp 管搜索算法value.h/value.cpp 管估值函数另有两个 exe——Surakarta.exe 和 Project2.exe。后者很可能是同一次作业在不同阶段生成的构建产物名字保留了当时的工程命名不影响我们读代码。2.1 define.h棋盘尺寸、棋子常量与模块间的“协议层”小项目最容易翻车的地方不是算法而是每个文件各写一套常量最后连棋盘尺寸都对不上。define.h 的存在就是为了消灭这种情况棋盘多大、黑棋白棋用什么数字表示、无穷大怎么取、Move 结构长什么样全部集中在这一处。// define.h —— 公共定义避免魔法数字散落在各文件 #ifndef DEFINE_H #define DEFINE_H #define BOARD_SIZE 6 // 苏拉卡塔棋盘 6×6 #define EMPTY 0 #define BLACK 1 #define WHITE 2 #define INF 1000000 // 搜索用的“足够大”值注意别溢出 int struct Move { int fromRow, fromCol; // 起始格 int toRow, toCol; // 目标格 }; struct BoardState { int grid[BOARD_SIZE][BOARD_SIZE]; // 0空1黑2白 int pieceCount[3]; // pieceCount[BLACK]/pieceCount[WHITE] }; bool IsInside(int row, int col); bool IsRingCell(int row, int col); // 是否处于角上环形轨道的入口/出口 #endifpieceCount这个数组看着不起眼调试时非常好用下棋下到一半想知道黑白各剩几子直接读 count不用整个棋盘扫一遍。INF取 1000000 是因为估值函数返回的量级一般只有几千乘以 2 也不会超过 int 范围但如果你的估值函数里加了很重的中盘系数记得回来检查这个值。IsRingCell是苏拉卡塔特有的判定只有落在角区轨道点上的棋子才可能走“绕圈吃子”这一步判断直接影响移动生成和估值。很多移植版本在这个函数上写错导致 AI 永远不吃子。2.2 main.cpp回合循环怎么把玩家输入和 AI 搜索串起来main.cpp 是整局棋的“导演”它不关心 alpha-beta 内部怎么剪枝只负责一件事按回合交替让玩家落子、让 AI 落子直到终局。// main.cpp 的骨架 #include define.h #include search.h BoardState g_state; // 全局状态search 里只读避免边算边改 int main(int argc, char* argv[]) { InitBoard(g_state); int turn BLACK; while (!IsGameOver(g_state)) { DisplayBoard(g_state); if (turn HUMAN) { int fr, fc, tr, tc; scanf_s(%d %d %d %d, fr, fc, tr, tc); Move m { fr, fc, tr, tc }; if (!IsLegalMove(g_state, m, turn)) { printf(非法走法请重新输入\n); continue; } ApplyMove(g_state, m, turn); } else { SearchResult result GetBestMove(g_state, SEARCH_DEPTH, turn); printf(AI 走: (%d,%d) - (%d,%d)\n, result.move.fromRow, result.move.fromCol, result.move.toRow, result.move.toCol); ApplyMove(g_state, result.move, turn); } turn 3 - turn; // BLACK(1) 和 WHITE(2) 互换 } PrintWinner(g_state); return 0; }这里的关键设计是GetBestMove(g_state, SEARCH_DEPTH, turn)只接收三个参数状态、深度、当前方。搜索要的“我是谁”从turn取估值要的“站在谁的角度”也从turn取。你不需要给 search 模块单独传一个“AI 身份”因为调用方知道当前轮到谁。turn 3 - turn是个小技巧1 和 2 互为 3 的补数这种写法比turn BLACK ? WHITE : BLACK更短但在代码可读性上一般你完全可以写成 if-else。看代码时如果发现 AI 连续走两步先回来检查这里是不是写成了turn turn。2.3 search.h/search.cppalpha-beta 对外暴露的接口极其收敛search 模块对外只暴露一个函数GetBestMove。这不是偷懒而是刻意的边界控制——main.cpp 不需要知道你是用 alpha-beta 还是蒙特卡洛它只需要一个“给我一步棋”的答案。// search.h #ifndef SEARCH_H #define SEARCH_H #include define.h struct SearchResult { Move move; // 搜索得到的最佳着法 int score; // 这个着法对应的估值调试时很有用 }; SearchResult GetBestMove(BoardState state, int depth, int side); #endifSEARCH_DEPTH没有写在 search.h 里而是放在 main.cpp 顶部或 define.h 里这个细节值得留意。把搜索深度放在调用方而不是算法内部意味着你可以在不改算法代码的情况下单独写一个测试程序循环测试 depth1 到 depth6 的棋力变化。如果 depth 写死在 search.cpp 内部每次测试都要重新编译。2.4 value.cpp/value.h估值函数决定 AI 的“棋品”value 模块是整个项目里最像“玄学”的部分。search 决定 AI 看得多远value 决定 AI 看到了之后认不认得哪边好。一个只数棋子的估值函数会让 AI 变成莽夫可能为了吃一个子连丢三个空格。下面是最常见的基础写法// value.cpp —— 估值函数实现 #include value.h #include define.h int EvaluateBoard(const BoardState state, int mySide) { int score 0; for (int r 0; r BOARD_SIZE; r) { for (int c 0; c BOARD_SIZE; c) { int piece state.grid[r][c]; if (piece mySide) { score 10; if (IsRingCell(r, c)) score 3; // 轨道点位置加分 } else if (piece 3 - mySide) { score - 10; if (IsRingCell(r, c)) score - 3; } } } return score; // 正数表示 mySide 占优 }这个函数的语义是一个子基本值 10 分站在环形轨道入口的棋子额外值 3 分。因为苏拉卡塔的吃子必须通过角上环形轨道占据轨道点相当于控制了“出海口”给一点位置奖励是合理的。注意评估必须是对称的——己方加分、对方就减同样的分否则 AI 会出现“双方都认为自己优势”的错乱局面。拿到代码后你第一个可以动手的实验就是改这两个数字把 10 改成 5把 3 改成 8AI 会更倾向于占位而不是换子。你会发现同样的搜索深度棋风完全不同这就是估值函数对行为的直接影响。3. 估值函数与 alpha-beta 的配合剪枝效率决定 AI 的棋力上限第二章四个文件各自是什么已经清楚了这一章把它们拼起来看。search.cpp 做的是纵向搜索value.cpp 做的是横向评判两者不是各干各的而是每一层递归都要交换一次数据。理解这个交换过程比背十个算法模板都管用。3.1 搜索循环alpha、beta、depth 三个参数各自在干什么alpha-beta 搜索的入口是GetBestMove真正的递归在内部函数里。以负极大值Negamax写法为例代码比朴素的极大极小值写法短一半提别适合这种小项目。// search.cpp —— Negamax 形式的 alpha-beta 搜索 static int AlphaBeta(BoardState state, int depth, int alpha, int beta, int side) { if (depth 0 || state.pieceCount[BLACK] 0 || state.pieceCount[WHITE] 0) { return EvaluateBoard(state, side); } Move moves[MAX_MOVES]; int moveCnt GenerateMoves(state, side, moves); int best -INF; for (int i 0; i moveCnt; i) { ApplyMove(state, moves[i], side); int val -AlphaBeta(state, depth - 1, -beta, -alpha, 3 - side); UndoMove(state, moves[i], side); if (val best) best val; if (val alpha) alpha val; if (alpha beta) break; // 剪枝这条路已经不可能被上层选了 } return best; } SearchResult GetBestMove(BoardState state, int depth, int side) { SearchResult res; res.score -INF; Move moves[MAX_MOVES]; int moveCnt GenerateMoves(state, side, moves); for (int i 0; i moveCnt; i) { ApplyMove(state, moves[i], side); int val -AlphaBeta(state, depth - 1, -INF, INF, 3 - side); UndoMove(state, moves[i], side); if (val res.score) { res.score val; res.move moves[i]; } } return res; }alpha的含义是“我方目前已经能保证拿到的最小收益”beta是“对方会允许你拿到的最大收益”。如果某一层发现alpha beta说明对方在上一层已经有一个更优选择当前分支无论怎么走都会被放弃于是 break 掉这就是剪枝。depth每下降一层减 1减到 0 就停止向下展开直接调估值函数。这段代码里唯一要小心的点是-AlphaBeta(state, depth-1, -beta, -alpha, 3-side)。负极大值的标准写法要求把 alpha 和 beta 取反后交换位置传下去因为下一层的“己方”是上一层的“对方”。如果你把参数原样传下去剪枝会直接失效搜索会退化成一个没有剪枝的极大极小深度一加就慢得没法看。3.2 移动顺序同一套剪枝先走哪步差别是一个数量级alpha-beta 剪枝的效率极度依赖着法顺序。理想情况下每一步都先尝试最好的着法剪枝概率最大最坏情况下等于没剪枝。刷排序的启发式规则可以很简单——吃子着法排在普通着法前面。// 将吃子着法移动到列表前部 for (int i 1; i moveCnt; i) { Move key moves[i]; int j i - 1; while (j 0 IsCaptureMove(moves[j]) 0 IsCaptureMove(key) 1) { moves[j 1] moves[j]; j--; } moves[j 1] key; }这段代码不动搜索结果只改变遍历顺序。但它能显著减少EvaluateBoard的调用次数。你可以做一个简单实验在EvaluateBoard第一行加一个计数器分别跑排序前和排序后的搜索观察同样的深度下估值函数被调了多少次。通常先走吃子着法能削减 30% 以上的搜索节点深度越高差距越明显。为什么吃子优先在这里特别有效苏拉卡塔的吃子着法往往直接改变棋盘局势一个能吃掉对方子的分支其估值大概率比普通走法高。把这种大概率“好”的分支先搜一遍alpha 值会被快速推高后面的分支很容易触发alpha beta剪枝。3.3 估值函数的对称性为什么左右不均会让 AI 变成“双面人”value.cpp 里有一句话被很多人忽略评估必须站在mySide的角度返回。也就是说同一个棋盘站在黑方看是 30站在白方看就应该是 -30。如果估值函数不对称会出现什么后果假设你的函数里不小心多写了一句“如果黑棋在轨道点就加 5 分”那么 AI 作为黑棋时激进占点作为白棋时完全不占点走法风格撕裂而且搜索深度越深这种撕裂被放大得越明显。自查方法很简单写一个测试函数构造十组局面分别以 BLACK 和 WHITE 调用EvaluateBoard两边结果加起来应当等于 0。不等于 0 说明函数里有身份偏好找到对应的加分项删掉。3.4 深度与耗时depth2 可能不到 1 毫秒depth8 可能要一分钟苏拉卡塔每回合可选着法大约在 20 到 60 之间后期棋子减少了会降下来alpha-beta 的理想情况下搜索节点数是 2 的 depth 次方量级实际会再多一些。depth4 通常在毫秒级depth6 能感觉到明显卡顿depth8 如果移动顺序不好会让人以为是死机。调深度时观察两个值一是单回合平均响应时间二是估值函数调用次数。如果 depth 加到 6 后响应时间突然从 2 秒跳到了 30 秒大概率是移动排序没有生效先去检查 3.2 节的排序代码。真正把剪枝写对的项目响应时间随深度增长应该是平缓的而不是爆炸式增长。4. 避坑指南编译、运行、AI 异常三类问题一次说清看代码是一回事把代码跑起来又是另一回事。这一章把最常见的坑按“现象 → 原因 → 解决”列清楚对照排查就行。我自己第一次编译这个包时也在这几个问题上卡了小半天。4.1 现象编译报 C3861说 AlphaBetaSearch 找不到标识符原因main.cpp 调用了GetBestMove但文件顶部没有#include search.h编译器不知道这个函数的声明。另一个常见原因是 search.cpp 里写了AlphaBeta递归函数但 search.h 里只声明了GetBestMovemain 里直接调用了AlphaBeta。解决先确认 main.cpp 的 include 区有没有#include search.h。再确认你调用的到底是哪个函数名——对外接口只有GetBestMove内部递归函数不要从 main 直接调。检查 include 写在.cpp文件顶部而不是.h文件里因为头文件只负责接口声明。4.2 现象双击 exe 弹“缺少 xxx.dll”或者黑窗口一闪而过原因exe 依赖的 Visual C 运行库在当前机器上缺失。旧版 VC 编译出来的程序在没装 Redistributable 的机器上经常出现这种情况还有一种是 exe 本身被 Windows 当成 GUI 程序main 返回之前控制台就关了。解决先装对应版本的 Microsoft Visual C Redistributablex86 和 x64 都装上最稳妥。然后打开 cmd手动执行 execd /d D:\surakarta Surakarta.exe echo %errorlevel%用命令行跑的好处是exe 里的printf输出不会因为窗口关闭而消失你也能看到它是不是返回了非零错误码。如果两个 exe 有其中一个能跑起来另一个闪退通常不是代码逻辑问题而是构建配置差异优先用能跑的那个做体验。4.3 现象AI 总是做很蠢的棋比如主动把棋子送到对方轨道口原因搜索深度太低或者估值函数里没有正确考虑“下一步可能被吃”的因素。depth1 时 AI 只看眼前一步它不知道自己送上门会立刻被吃掉。另一个原因是估值函数只算了子力差没有算位置威胁轨道口的子虽然加了 3 分但你们可能把“轨道点”判定写反了把安全位置当成危险位置。解决把 depth 从 1 逐步往上调同时观察走法变化。如果 depth3 仍然蠢就把IsRingCell对应的打印打开看 AI 眼里哪些格子算轨道点。用命令行版本跑一局每一步打印出SearchResult.score看看 AI 给出的分数和实际局面是否一致——分数高却走臭棋问题在移动生成分数低还硬走问题在估值函数的方向。4.4 现象搜索深度加到 8 后直接栈溢出原因AlphaBeta 函数是递归调用每层递归都会把局部变量压入调用栈。如果BoardState通过值传递而不是引用传递每层都会拷贝一份 6×6 数组栈帧体积陡增。depth8 时递归层数其实不算高但每层的栈帧太大就会撞上栈上限。解决把AlphaBeta和EvaluateBoard的参数改成BoardState引用确保全局只有一份棋盘状态在 apply/undo 之间反复修改。ApplyMove里如果频繁分配Move数组也建议换成固定大小的数组。改完后同一台机器上搜索深度能多 push 2 到 3 层。4.5 现象改了估值参数AI 却“没反应”原因改完 value.cpp 后没有重新编译或者编译了但运行的是 old exe。很多项目里 exe 文件名和源代码名不一致改完代码直接双击旧的 Surakarta.exe自然看不到变化。解决在 Visual Studio 里重新生成解决方案确认输出目录里 exe 的时间戳是刚刚更新的。写代码时养成习惯先把 exe 关掉再编译否则 VS 会提示文件被占用。验证 AI 有变化的最快方式是编译后用命令行跑一次在命令行打印一轮的估值分数和改代码前的分数对比数字变了就说明新代码生效了。5. 验证与扩展玩法AI 互博、可观测性改造与 alpha-beta 的迁移走到这一步代码能编译、AI 能下棋、简单参数会改了接下来可以玩点更有价值的让 AI 和自己对弈把搜索过程变成可见数据再把这种状态空间搜索的思路迁移到其他场景。5.1 AI 互博同一份代码两个深度对战改完估值函数或搜索深度之后怎么判断棋力真的变强了跟真人下容易受主观影响跟以前的版本下才是硬指标。常见做法是写一个main_autoplay分支不用人工输入让 BLACK 和 WHITE 都用GetBestMove走棋// 自动对弈循环入口加一个 -autoplay 参数 if (argc 1 strcmp(argv[1], -autoplay) 0) { int depthBlack atoi(argv[2]); // 例如 4 int depthWhite atoi(argv[3]); // 例如 2 while (!IsGameOver(g_state)) { SearchResult r GetBestMove(g_state, (turn BLACK) ? depthBlack : depthWhite, turn); ApplyMove(g_state, r.move, turn); turn 3 - turn; } printf(Winner: %d\n, winner); }记录对局结果时别只记胜负把步数也记下来。一个有趣的现象是深度高的 AI 不一定赢更快但通常会赢在残局阶段而不是开局抢攻。如果 depth6 的一方总是输给 depth3 的优先怀疑估值函数是不是有方向性错误而不是继续加搜索深度。5.2 给搜索加“可观测性”统计节点数而不是猜AI 是黑匣子的时候出了问题只能靠猜。一个很轻量的改造是加一个全局计数器每次进入AlphaBeta函数就nodeCount搜索结束后打印出来。这个数字能直接告诉你剪枝到底有没有生效。改代码前 depth5 搜索了 12 万个节点改完移动排序后同一个局面只搜了 3 万个这就是实实在在的优化成果。把nodeCount初始化的代码放在GetBestMove开头这样每次落子都自动归零。5.3 从苏拉卡塔到其他问题alpha-beta 本质是状态空间搜索包里这个 search.cpp 大概是整个压缩包价值最高的文件因为 alpha-beta 不只用在棋类上——路径规划、资源调度、有限回合决策只要满足“状态可枚举、行动可逆、有终局判据”这三个条件都可以套同一套模板。我后来做其他项目时就把这套结构里的ApplyMove/UndoMove换成状态转移函数把EvaluateBoard换成代价估算直接改成了一台小型决策搜索引擎。网格搜索的游戏 AI就是搜索引擎在棋盘状态空间里干活。从那以后我每次拿到这种博弈项目都强制自己先跑一遍命令行对局、再改代码把节点数和估值分数打印出来留底。做一次两次觉得是走形式攒了三个版本的日志后会发现任何参数改动到底带来收益还是负优化全部有数可查。希望这份苏拉卡塔代码包也能成为你理解 alpha-beta 和状态空间搜索的第一块垫脚石。本文还有配套的精品资源点击获取