C++博弈树与α-β剪枝：五子棋AI四层搜索的实战解析

简介：这份源码实现基于C++的AI五子棋人机对战，核心算法采用博弈树并结合α-β剪枝优化，当前AI棋力可推算四层局面。源码面向具备基础C++知识的开发者，也适合对棋类AI算法感兴趣的读者，作为课程设计或二次开发的参考样本。压缩包共含47个文件，以CPP/H源文件、Visual Studio解决方案及工程文件为主，另附编译生成的exe与调试记录，整体大小约2.64MB，目录结构清晰，便于直接打开或修改。目前已有79人浏览学习。通过阅读并运行代码，可深入理解博弈树构建、局面评估、α-β剪枝策略的工程实现，也能在此基础上调整搜索深度、优化评估函数，从而提升AI棋力，是一份动手实践经典搜索算法的实用素材。

1. 做个人机对战五子棋不难，难在 AI 怎么看出四步后的输赢

拿到这份基于 C++ 博弈树并使用 α-β 剪枝改进的 AI 五子棋源码时，我第一反应不是打开代码，而是先想了一件事：15×15 的棋盘，四层推演要遍历的落子组合有几亿种，这个 AI 凭什么在普通电脑上几十毫秒就能落子？答案就在博弈树和 α-β 剪枝的组合里——它把搜索从盲目穷举变成有方向的选择，人机对战才真正跑得起来。这套源码适合两类人：一是想学 C++ 算法落地的学生，二是自己写五子棋但电脑对手智商总不在线的开发者。它给你一套能编译、能对战、能改参数的项目，把搜索框架、评估函数和交互逻辑完整串起来。下面我从原理拆到实战，把参数和坑都交代明白。

2. 博弈树与 α-β 剪枝：五子棋 AI 为什么不靠暴力穷举

2.1 博弈树是五子棋 AI 的骨架：节点、层数与局面评估

先理解博弈树。从空棋盘开始，AI 落一个子，这是在生成第一层节点；对手回应，生成第二层；双方交替，直到某一层达到我们设定的搜索深度。这份源码里默认搜索深度是四层，四层意味着 AI 模拟“自己下一子、对手下一子、自己再下一子、对手再下一子”，然后在这四个回合后的局面里寻找最优位置。很多刚接触的人会觉得四层太少，实际上四层配合剪枝和排序已经能击败大多数随手下的玩家，因为每一层都把对方最可能的应对考虑进去了。

每个节点都对应一个棋盘局面，而每个局面都需要一个数值告诉搜索程序“这个位置对 AI 到底有多好”。这个数值来自评估函数（Evaluate），是整个搜索的下半身。五子棋的评估函数不能只看已经连成五子，因为搜索四层时大概率还没形成五连，必须把活三、活四、冲四、活二这些棋型折算成分数，AI 才能在局面还早的时候看出哪条路更有潜力。源码里这部分的实现思路是：对横向、纵向和两个斜向分别扫描，凡是遇到连续同色棋子就累计棋型长度，遇到空位或对手棋子则中断，每段棋型根据长度和两端是否被堵打分，最后把所有方向求和。

这里要区分一个关键概念：博弈树和普通搜索树不一样。普通搜索树只需要找到自己最好的下一步，博弈树则要考虑对手下一步也会做出最优选择。也就是说，AI 决定下某个位置，不能只看这一步能长多少分，还要预判对手会怎么回击，然后站在对手的角度选他最狠的一手，再回到自己的视角选应对方案。这个“你一步，我一步，双方都取最优”的过程，决定了评估四层局面时不能简单地取最大值，而是要在奇数层取 Max，偶数层取 Min。

为了让这套逻辑可操作，我一般会把评估函数单独抽出来做单元测试。具体做法是：在源码里加一个测试入口，手动摆出几个定式局面，比如黑棋单活三、白棋冲四、双方各有一个活二，然后打印评估分数，确认分数大小关系符合预期。这一步能帮你快速定位是搜索算法写错了，还是评估函数本身打分不合常理。如果你发现某个局面分数异常高，先检查棋型扫描的方向数组是否正确，尤其斜向扫描是最容易漏段的。

2.2 α-β 剪枝为什么能把四层搜索压到毫秒级

如果源码里不剪枝，四层搜索的节点数是多少？粗算一下：开局附近能落子位置约 225 个，每层减一个，四层约 225×224×223×222，算出来接近 25 亿。如果每步都评估，普通机器根本扛不住。α-β 剪枝做的事，是在搜索过程中维护两个值：α 表示 AI 已经找到的最优下界，β 表示对手能接受的最优上界。当某个子节点返回的分数突破了这个区间，就说明这个分支后面的结果不可能比当前已知方案更好，可以直接砍掉，不用再往下递归。

这份源码的搜索主函数是递归写的，典型结构是先判断是否到达四层或终局，然后生成候选落子，对每个落子递归调用 AlphaBeta，返回后把分数传给父节点。剪枝的核心判断放在递归返回之后：当当前节点的分数已经让父节点不需要再探测其余子节点时，立刻 return。这里容易写错的是 α 和 β 的更新时机，我的经验是严格按“返回上一层才更新”来做，避免在递归内部把 α、β 当全局变量乱改。

下面给你一段我复现时用的最小 AlphaBeta 框架，和源码里 Search 的骨架基本一致，你可以对着源码改：

int AlphaBeta(int depth, int alpha, int beta, bool isAI) { if (depth == 0 || IsGameOver()) { return Evaluate(board); } vector<Move> moves = GenerateMoves(); SortMovesByScore(moves); // 按评估分数降序，提升剪枝效果 if (isAI) { int best = NEG_INF; // AI 希望分数尽量大 for (auto& m : moves) { MakeMove(board, m); best = max(best, AlphaBeta(depth - 1, alpha, beta, false)); UnmakeMove(board, m); alpha = max(alpha, best); // 更新下界 if (alpha >= beta) break; // 剪枝，不用再搜后面的候选 } return best; } else { int best = POS_INF; // 对手希望分数尽量小 for (auto& m : moves) { MakeMove(board, m); best = min(best, AlphaBeta(depth - 1, alpha, beta, true)); UnmakeMove(board, m); beta = min(beta, best); // 更新上界 if (alpha >= beta) break; } return best; } }

这里需要说明的是：isAI 参数控制 Max 和 Min 的切换，depth 每递归一层减一，alpha/beta 初始传入 NEG_INF 和 POS_INF，表示还没有任何已知信息。剪枝触发的条件是 alpha >= beta，意思是 AI 已经找不到比对手允许的更好结果，这个分支继续搜索只会浪费时间。SortMovesByScore 这一行看着不起眼，却直接影响剪枝率——排序越好，第一个搜索的分支越接近最优解，后面要砍掉的分支就越多。

实际操作里，我拿到源码后会先在 debug 模式下统计搜索节点数：在 AlphaBeta 函数入口加一个计数器，分别记录有剪枝和无剪枝的调用次数。四层搜索在不同位置剪枝率差距很大，一般能减少 70% 到 90% 的节点。如果发现剪枝几乎不生效，优先检查候选落子的排序；如果每次都从最差的分支开始，剪枝就形同虚设。所以不要跳过排序直接把剪枝加上去，两者是配套的。

2.3 评估函数的设计：不是只看连子数，要看活三冲四

我拆这份源码时最大的体会是：评估函数比搜索算法更容易翻车。搜索算法只要按照博弈树规则递归、剪枝，结果一般不会太离谱；但评估函数一旦打分不均衡，AI 会出现明显的“近视”——比如只盯着连子长度，四连但两端被堵的局面会给很高分，AI 就会往死路里钻；又比如把活二和冲四都记成 10 分，AI 就会在中盘阶段放弃能直接获胜的冲四，去补一个还没影的活二。

源码里评估函数使用棋型表的方式来避免这个问题：扫描到一个棋型后，按棋型类型查表得到分值。我在调试时习惯在这个函数里加一个开关，把每个棋型的中文名和得分打印出来，走一步打印一步，很快就能看出 AI 在哪个棋型上判断失误。下面这张表是我调过的最稳的一组参考值，你可以把它当作压测的起点，再按自己的手感微调：

五子棋的棋型优先级基本遵循：连五 > 活四 > 冲四 > 活三 > 眠三 > 活二 > 眠二。活四给 10000、冲四给 5000，中间至少要相差一个量级，否则 AI 会为了一个假机会丢掉真实杀棋。如果读者要自己改这份源码的评估函数，记得同时改搜索深度附近的终局判断：当棋盘出现连五时直接返回极大值，而不是交给棋型表去算，否则最大分会被表里的活四分数干扰。

把评估函数和搜索函数分开后，还能顺手做一步优化：只扫描落子点周围一定范围内的空位来生成候选落子。这份源码的做法是以最后一个落子为中心，选择半径 2 以内的所有空位作为下一层候选，这样可以避免搜索从远方完全无关的位置重新开始。这个优化单独写个 Move Generator 就能实现，不影响搜索主逻辑。到这里，博弈树、剪枝、评估函数三者闭环，AI 已经能下出像样的棋，但距离一套完整可对战的项目还差交互层和胜负判定。

3. 源码拆解：人机对战的完整流程与关键函数

3.1 数据结构与棋盘表示：从二维数组到落子判断

先看棋盘。源码里棋盘就是 int board[15][15] 这类二维数组，黑子为 1、白子为 -1、空为 0。也有的写法是分别用 1 和 2，区别不大，关键是全项目统一。我习惯用 1 和 -1，因为求对手颜色只需取相反数，做评估函数时也方便。二维数组本身很直接，横向扫描、纵向扫描和斜向扫描都容易写，真正的坑在于坐标边界。15×15 的数组下标从 0 到 14，方向数组如果写成 i + 4、j + 4 而没有边界判断，斜向扫描必然越界，轻则读到脏数据，重则直接崩溃。

落子合法性很简单：判断 board[i][j] 是否为 0。但如果把棋盘声明成类成员，每次递归都要注意 MakeMove 和 UnmakeMove 的配对。我在源码里检查过，MakeMove 会把原值保存到 Move 对象里，UnmakeMove 再从 Move 对象恢复，这样搜索完一轮棋盘能回到原始状态。如果你自己改动源码，不要在递归里手动改 board 而忘记恢复，那样后面所有评估都是错的。

方向数组是扫描的基础，源码里通常写成静态二维数组，大小是 8×2，对应上、下、左、右、左上、右上、左下、右下八个方向。下面这个片段很典型：

const int DIR[8][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, // 上下左右 {-1, -1}, {-1, 1}, {1, -1}, {1, 1} // 两条斜线 }; bool InBoard(int x, int y) { return x >= 0 && x < 15 && y >= 0 && y < 15; }

InBoard 配合 DIR 使用，每走一步都先判断边界，可以省掉一大堆分支错乱。判断五连时，先从当前落子点沿一个方向数，再沿反方向数，两个方向的连续棋子数加起来要算上当前这次落子。也就是 count = cnt1 + cnt2 + 1。这个“加回当前落子”的小细节很多人写漏，结果就是四连看起来是五连，或者五连因为边界问题不成立。

3.2 AI 搜索主流程：先根节点、生成走法、迭代加深

接下来是人机对战的核心流程。源码里 AI 落子不是直接在鼠标点击回调里调 search，而是先在一个工作线程里跑搜索，避免界面因为计算量太大而卡死。棋手点击棋盘后，程序会记录落子、判断胜负，然后进入 AI 的 GetBestMove 函数。GetBestMove 做的事是：清空上次搜索的缓存，调用 RootSearch，拿到最佳落子坐标，再把这个坐标封装成一个 Move 对象返回给界面。

RootSearch 和递归函数 AlphaBeta 的分工要留意：RootSearch 负责在根节点遍历所有候选落子，并在每个子节点上调用带 α-β 的递归搜索，同时维护一个 bestMove 变量。如果不做这个拆分，直接在 AlphaBeta 里返回分数，你就拿不到最终应该落在哪个位置。源码里这种一层封装的做法是 C++ 博弈程序的常见套路，值得保留。我把核心逻辑简化成下面这段，去掉界面代码后结构更清楚：

Move GetBestMove(int board[15][15], int aiColor) { vector<Move> candidates; GenerateMoves(candidates, lastMove, board); // 只生成落子点周围2格内的候选 SortMovesByScore(candidates, board, aiColor); // 按静态评估降序，先搜好分支 int bestScore = NEG_INF; Move bestMove = candidates[0]; for (auto& m : candidates) { MakeMove(board, m, aiColor); int score = AlphaBeta(MAX_DEPTH - 1, NEG_INF, POS_INF, false); UnmakeMove(board, m); if (score > bestScore) { bestScore = score; bestMove = m; } } return bestMove; }

这段代码的关键在于 MAX_DEPTH 是四层，AlphaBeta 第一个参数是 MAX_DEPTH - 1，因为在 GetBestMove 里的这步落子已经算作第一层，递归里只需要再推三层。candidates 的顺序直接决定剪枝上限，SortMovesByScore 内部用的还是评估函数，所以评估函数越准确，剪枝效率越高。如果你把深度改成六层，建议不要只用固定深度，而是引入迭代加深。

生成走法这块，源码用了“周围有子的空位”思路，以前面提到的 Move Generator 在落子点半径 2 范围内生成候选，再把候选按评估分数排序。这样做有两个作用：第一把每层搜索的分支因子从大约 200 降到 30 到 60 个；第二让 α-β 剪枝从第一轮就开始发力。排序函数 SortMovesByScore 的位置在搜索之前，源码里如果找不到剪枝率明显提升，多半是排序里用了静态评估但评估函数本身有 bug。

为了能够在规定时间内落子，进阶的做法是迭代加深：先搜索两层，算完后再搜索三层，直到搜索时间超过预设阈值就停止，并用最后一层的结果落子。这份源码固定四层，如果你把深度改到五层，建议改成迭代加深结构，否则遇到复杂局面对手等待观感很差。迭代加深不会白搜：前面浅层搜索拿到的最佳路线，可以作为深层搜索的初始 alpha 窗口，缩小搜索范围。

3.3 人机交互与胜负判定：落子、悔棋、重开

人机对战的交互流程相对简单：鼠标点击窗口，程序把像素坐标换算成棋盘行列索引，然后执行落子。这里有一个比较隐蔽的坑：坐标换算时如果棋盘格子宽度取整和偏移量处理不对，点击会落在格线和棋子边缘，玩家以为自己点了某个位置，程序识别成相邻位置。源码里的实现一般是用鼠标坐标减去棋盘左上角偏移量，再除以格子边长取整。我在复现时会打印换算前后坐标检查，确认点击目标与落子结果一致。

胜负判定在每次落子后执行。源码用 IsGameOver 函数检查以当前落子点为中心，四个方向（横、竖、两个斜）连续同色棋子数是否达到五。这里不用全盘扫描，只从最后一次落子出发，效率很高。判定时需要小心方向数组的对称性：横方向要同时向左、向右数，累加后判断是否 >=5，而不是只数一边。这个细节出 bug 时，会出现“五连胜棋不算赢但六子连算赢”的怪现象。

悔棋功能在源码里通常用栈实现：每次落子把位置和颜色压栈，悔棋时弹出栈顶并把棋盘复位。如果程序自己做 AI，还需要处理“玩家悔棋后 AI 要不要跟着悔一步”的策略。一般做法是 AI 记录自己上一次落子，玩家悔棋时把 AI 的上一步也撤销，恢复成玩家行动前的状态。源码里如果没有做这一步，你会发现玩家悔棋后变成 AI 先手，局面会错乱，这一点我经常当成检查重点。

到这里，你已经把棋盘、搜索、交互三个模块在脑子里串了起来。如果直接编译运行，大概率会先碰到环境问题，而不是算法问题，所以下一章全是实际操作里最容易翻车的地方。

4. 编译与运行避坑：Visual C++ 运行时、vscode 环境与剪枝参数翻车记录

4.1 我碰到的编译报错：链接错误、字符集问题

第一条链接错误。现象：拿源码用 Visual Studio 打开解决方案，直接生成报 LNK2019，提示无法解析外部符号 WinMainCRTStartup。原因：工程类型选错，代码入口是 WinMain，控制台应用的入口是 main，导致链接器找不到入口点。解决：在项目属性 → 链接器 → 系统 → 子系统里选“窗口”，并在入口点写 wWinMainCRTStartup；或者直接新建 Windows 桌面项目，把 .cpp 文件整体迁入。

第二条中文乱码。现象：源码里的中文提示在窗口里显示成乱码，编译阶段报 C2001 常量中有换行符。原因：源文件保存编码与编译器代码页不一致，中文字符串标签被错误解析。解决：把源文件转为 UTF-8 with BOM，或给编译器加 /utf-8 参数。这里顺带提一句：如果你用 vscode 里的 c/c++ 扩展编译，默认会用系统编码，同样建议把文件转成 UTF-8 with BOM，并且在 tasks.json 里指定 -finput-charset=UTF-8 -fexec-charset=UTF-8（g++ 写法）。别小看这个，我见过有人因为乱码浪费一下午。

还需要注意 Windows SDK 版本的差异。现象：工程打开后提示 MSB8036，找不到指定的 Windows SDK 版本。原因：源码工程文件里指定的 SDK 版本和你本机安装的不一致，常见于你用的是新环境。解决：在项目属性 → 常规 → Windows SDK 版本里选成当前已安装的版本，或者右键解决方案重新指定，一般不需要改代码就能编过。这条不是算法问题，但会影响你能不能很快看到 AI 跑起来。

4.2 α-β 剪枝参数翻车记录

记录三是 AI 走棋慢。现象：同样的四层深度，正常配置一两百毫秒能落子，我这台机器要两秒多，界面明显卡顿。原因：GenerateMoves 生成候选时没有限制在落子点周围，把棋盘所有空白位置都当候选，分支因子两百多，剪枝再强也救不回来。解决：改成以最后一手落子为中心、半径 2 以内的空位生成候选；每一层递归都用这个规则，节点数直接降一个数量级。这里有个参数要注意：半径 2 是经验值，改成半径 3 会扩大搜索面，但时间会涨不少，如果只是想保持四层流畅，别轻易加大。

记录四是剪枝不生效。现象：我在 AlphaBeta 入口加了计数器，分别统计总调用次数，结果发现开不开剪枝调用次数几乎一样，剪枝没起到作用。原因：候选落子没有排序，搜索总是从最差的分支开始，alpha 值提升得很慢，导致后面的分支几乎都要完整搜完。解决：在 GetBestMove 生成候选后调用 SortMovesByScore，按评估函数粗分降序。排序不需要特别精准，只要把活三冲四这类明显更优的位置放前面，剪枝率马上会上来。如果用调试工具打印每个分支的评估分数，可以直观看到排序前后的搜索次数差距。

除了这两个，还有一类翻车在评估函数本身。现象：AI 会主动下到对手活三旁边，帮对手成活四。原因：评估函数里活三、冲四的分数梯度不够，搜索时 AI 认为对手下一步威胁不大。解决：对照前面那张棋型分值表，确保活四、冲四和活三之间差一个量级。这个坑严格说不是 α-β 参数，但它表现在搜索结果上，排查时很容易误以为是剪枝写错了，所以我把它跟参数问题放在一起，调试时先查评估表再查剪枝。

4.3 运行环境踩坑：VCRUNTIME140.dll 缺失与 vscode 配置

运行库相关的坑最多。现象：把编译好的 exe 复制到另一台电脑，双击报“由于找不到 VCRUNTIME140.dll，无法继续执行代码”。原因：目标电脑没有安装 Microsoft Visual C++ 2015-2022 Redistributable 运行库。解决：安装对应架构的 vc_redist.x64.exe 或 vc_redist.x86.exe，两个架构都装也不冲突。如果你只是在自己电脑上跑，开发环境已经带运行库，不一定能发现这个问题，发布给别人才会中招。我发布前的习惯是找一台干净的虚拟机或者旧电脑测一遍。

vscode 配置则容易栽在链接参数上。现象：在 vscode 里用 g++ 编译源码，报一堆无法解析的外部符号，CreateWindowExW、RegisterClassW 这些 W 结尾 API 全部找不到。原因：源码是 MSVC 风格的 Windows 窗口程序，g++ 默认没有链接 user32、gdi32，也没有告诉链接器这是窗口子系统。解决：在 tasks.json 的编译命令里加 -mwindows -luser32 -lgdi32，如果源码还用到其他 Win32 API 就逐个补库。要注意的是，MinGW-w64 和 MSVC 的 ABI 不完全兼容，特别是涉及资源文件 .rc 的时候，尽量用 Visual Studio 编译这份源码；vscode 方案适合改算法逻辑或者做快速验证。

还有一种情况是运行时报错而不是编译报错。现象：程序启动后窗口一片黑，或者落子时偶尔闪退，控制台也看不到任何提示。原因：GUI 子系统程序不绑定控制台，printf 输出不会显示，真正的错误信息被吞掉了。解决：在代码里加日志文件输出，把关键搜索参数、落子坐标、胜负判断都写到 log 文件；我用的是 fprintf 写文本文件，每次落子前 flush 一次，定位问题比在窗口里猜快得多。这条主要是验证习惯，和算法正确性一样重要。

5. 进阶：把四层搜索提升到五层、六层的三个可行改法

前面几章已经把四层搜索跑通了。如果你觉得 AI 还是不够强，最直接的思路是增加搜索深度，但深度从四加到五，节点数会成倍涨，不能只改 MAX_DEPTH。这里分享三个我试过有效的改法。

第一个改法是给候选走法做启发式排序。排序不只是按当前评估分数排，还可以给“最近刚赢过棋的位置”额外加分，也就是历史启发。源码里的 SortMovesByScore 是静态排序，每次搜索前都算一遍。加上历史表后，搜索过程中命中过的杀棋位置会记录次数，后续局面排序时优先选择历史命中率高的位置。这个改动对 α-β 剪枝率提升非常明显，五层搜索的时间能压回和原来四层相近。

第二个改法是加置换表（Transposition Table）。五子棋棋型对称性带来大量重复局面，同一局面从不同落子顺序进入，搜索结果是一样的。用 Zobrist Hash 给局面生成一个 uint64_t 的 key，保存到哈希表里，下次搜到相同局面且表内深度足够时，直接返回缓存分数。这一步能把节点数再降掉三到五成。代码骨架大概是：

int AlphaBetaMemo(int depth, int alpha, int beta, bool isAI) { uint64_t key = ZobristHash(board, isAI); auto it = transTable.find(key); if (it != transTable.end() && it->second.depth >= depth) { return it->second.score; } int best = AlphaBeta(depth, alpha, beta, isAI); // 原有递归逻辑 transTable[key] = {depth, best}; // 保存结果 return best; }

这段代码说明两个参数：depth 缓存的是已搜索深度，只有当表里存的结果比当前需要的深度更深或相等时才能复用，否则不能直接用；key 在每次落子和悔棋时增量更新，比每次重新异或全部棋子快得多。注意因为 α-β 搜索的分数可能依赖窗口（alpha、beta），严格做法是存上界和下界，分别判断能不能截断。如果嫌麻烦，保守一点只在完全搜索的深度上复用，也能有不少收益。

第三个改法是引入迭代加深。固定深度四层改成一到六层循环搜索：搜完一层，如果时间还在阈值内，继续搜下一层；超时就停止，用最近一次完整的结果落子。迭代加深还能顺便给置换表填充更多缓存，让最终那层搜索跑得更快。从那以后，我每次调搜索深度都会强制走一遍节点数统计和局面基准测试，先确认剪枝率和时间都正常，再放手去加新功能。这些改法不一定要全部上，但至少把启发式排序做了，五层搜索才能谈得上顺畅。希望帮到你。

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