简介一套基于C博弈树与α-β剪枝实现的五子棋AI源码面向对棋类AI和博弈搜索算法感兴趣的开发者可直接进行人机对战当前AI能够推算四层局面适合作为算法学习与二次开发的起点。压缩包共47个文件大小约2.64MB核心内容包括cpp源码、h头文件及Visual Studio工程配置另附编译生成的exe与调试信息解压后即可用C环境编译运行。已有79人学习下载。源码清晰呈现了博弈树构建、局面评估与α-β剪枝的完整实现代码结构简洁、注释明确便于逐段拆解搜索流程。通过调整搜索深度或估值函数可直观对比剪枝前后搜索节点数量的变化深入理解启发式搜索的加速原理是实践经典博弈算法的实用范本。1. 博弈树与α-β剪枝这套五子棋源码到底在解决什么问题我拆这份源码之前先问了三个问题它是不是真能下出像样的棋四层推算在普通电脑上会不会卡到没法玩剪枝到底剪掉多少无用计算看完代码我可以直接说这套C五子棋AI走的是经典博弈树路线——把每一步落子当成一个搜索节点用极小极大搜索评估双方交替落子后四层的局面得分再用α-β剪枝把本来指数级的搜索树剪到普通PC能实时响应的规模。它解决的不是“怎么画棋盘”这种入门问题而是“AI怎么在有限算力里看得够远、选得够准”。适合正在做课程设计、研究棋类AI剪枝算法或者想把手头五子棋小项目从“人人对战”升级成“人机对战”的人。带人机对战源码最怕的是评估函数乱给分、搜索深度一上去就卡死这份代码的价值在于它把博弈树、评估函数、剪枝边界都串到了一套能跑的工程里拆开就能复现。2. 棋盘表示与胜负判定先把棋盘画对、判赢判对2.1 数据结构与落子动作怎么设计五子棋最直接的数据结构就是二维数组。15×15的棋盘用一个int board[15][15]就能表示0代表空位1代表黑方2代表白方。我见过有人一开始就用vector套pair、或者给每个格子建结构体结果下棋逻辑到处都要解引用代码越写越乱。这份源码的做法是回到最朴素的二维数组配合行列号操作读写直观、调试也好打日志。落子这个动作本身并不复杂真正容易翻车的是“落子前判断是否越界、是否已有子”。下面这段是常规做法也是我拆源码时先看的部分const int BOARD_SIZE 15; int board[BOARD_SIZE][BOARD_SIZE]; // 0空位, 1黑子, 2白子 bool placePiece(int row, int col, int player) { if (row 0 || row BOARD_SIZE || col 0 || col BOARD_SIZE) { return false; // 越界直接返回失败 } if (board[row][col] ! 0) { return false; // 已有棋子不能重复落子 } board[row][col] player; return true; } void undoPlace(int row, int col) { board[row][col] 0; // 搜索时需要回滚 }这里placePiece返回bool方便人机对战时直接用来校验鼠标点的坐标是否合法。undoPlace是为后面的博弈树搜索准备的AI在递归推演时要模拟落子后再撤销否则棋盘状态会被搜乱了。参数上row和col都从0开始棋盘左上角是(0,0)这和数组下标天然对齐不容易出“差一错误”。我一般会把黑方固定成玩家先手白方交给AI这样在评估函数里只需要区分当前落子方就能控制攻防方向。2.2 四方向判定胜负的实现五子棋的胜负判定是整套AI的地基——评估函数也好、搜索结束条件也好全都要依赖它。判定逻辑其实很固定只看最后落下的那一颗子以它为中心沿水平、垂直、两条对角线共四个方向每个方向朝两端数连续同色棋子的数量。只要任何一个方向累计大于等于5就是获胜。这里有个常见误区有人会每下一步棋就把整个棋盘扫描一遍判断场上所有位置是否成五。那样也不是不能跑但搜索到四层时每一步都要做一次全盘扫描白白浪费几十毫秒。源码里的做法是只查落子点代码长这样bool checkWin(int row, int col, int player) { int dirs[4][2] { {0, 1}, // 水平向右 {1, 0}, // 垂直向下 {1, 1}, // 主对角线 {1, -1} // 副对角线 }; for (int d 0; d 4; d) { int count 1; int dr dirs[d][0], dc dirs[d][1]; // 向正方向延伸 for (int i 1; i 5; i) { int nr row dr * i; int nc col dc * i; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) break; if (board[nr][nc] ! player) break; count; } // 向反方向延伸 for (int i 1; i 5; i) { int nr row - dr * i; int nc col - dc * i; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) break; if (board[nr][nc] ! player) break; count; } if (count 5) return true; } return false; }四个方向只需要四个基向量(0,1)、(1,0)、(1,1)、(1,-1)。因为两个相反方向共用一组向量正方向加负方向就能覆盖一条线的两端。每个方向的循环上限设成4是因为只要总数能达到5就算赢向两端各延伸4格已经足够覆盖全部可能。整套判定的时间复杂度是O(1)——固定方向、固定次数的循环。在α-β剪枝的递归里这个低成本判定会被反复调用必须做到不需要全盘扫描就能给出结论。3. 评估函数与棋型打分四层局面靠什么判断“哪一步好”3.1 棋型权重表与得分逻辑搜索深度能到四层说明每一层节点都要快速得到一个“这盘棋现在谁占优”的分数。这个分数的来源就是评估函数。评估函数不靠穷举未来它靠的是对当前棋盘上所有棋型的加权求和。常见的棋型权重表长这样棋型含义建议分值五连已凑齐五子100000活四四子两端都开放10000冲四四子只有一端开放6000活三三子两端开放能成四2000眠三三子一端被封400活二二子两端开放200眠二二子一端被封50为什么五连要设到10万这么高因为一旦出现五连博弈直接结束任何活四、冲四的分数和它相比都要绝对占优否则搜索会为了挡一个活四而漏掉已经成五的杀棋。活四和冲四的差距也很大——活四两头开放下一步无论如何都能成五几乎等同必胜冲四只有一端开放防守方堵住唯一缺口就化解了。评估棋盘时常见做法是分别统计黑方棋型总分和白方棋型总分最后返回两者之差。也就是说一个对黑方友好的局面得分是正数对白方友好则是负数。这样在博弈树里黑方走极大节点取最大分白方走极小节点取最小分语义一致。计算棋型分数时核心函数是对单条直线上的连子做模式识别。下面是一个精简但完整的打分思路struct LineInfo { int count; // 连续同色棋子数 bool openEnd; // 两端是否都开放两头都无对方棋子且无边界 }; int scoreLineForPlayer(int r, int c, int dr, int dc, int player) { // 沿方向延伸统计player的连子数量 int count 0; int i 1; // 向正方向数 while (true) { int nr r dr * i; int nc c dc * i; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) break; if (board[nr][nc] player) { count; } else break; i; } // 再向反方向数 i 1; while (true) { int nr r - dr * i; int nc c - dc * i; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) break; if (board[nr][nc] player) { count; } else break; i; } // 判断两端是否开放 bool openEnd false; // ... 分别检查两个端点的外侧只要有一个端点外侧为空就视为开放 if (count 5) return 100000; if (count 4 openEnd) return 10000; if (count 4 !openEnd) return 6000; if (count 3 openEnd) return 2000; if (count 3 !openEnd) return 400; if (count 2 openEnd) return 200; if (count 2 !openEnd) return 50; return 0; }注意这个函数的分值判断是“只按连子长度和开放与否”来打分是简化版。真正工程里还要考虑“跳活三”“斷二”这类中间有空格的情况但核心思路一致——把每一段连续子当成一个棋型单元查表给分两端状态决定是“活”还是“眠”。参数上openEnd的判断很重要两端都没有对方棋子、也没顶到棋盘边界才算开放。很多AI下棋犯傻问题就出在把一端被对方堵死的眠三也当成活三来给分导致该挡的位置判断错。3.2 让评估函数兼顾进攻和防守只用“自己棋型的得分”来评估会让AI只想着进攻对手明明快成五了它还在做自己的活三。真正能下赢人的评估函数必须同时算两边的棋型分。它的逻辑是当前局面得分 黑方棋型总分 - 白方棋型总分。AI如果是白方它搜索时找的是让这个差值最小的落子点也就是既要压低黑方分数又要抬高自己分数。防守的“隐形加分”体现在一个细节里当你扫到对方的活三时你落子去堵这个位置在你自己的棋型评估里通常只有很低的分数但在“差值”评估里由于降低了对方得分整手棋的价值反而很高。这就是为什么评估函数一定要双方都算不能只算当前方。我拆的这份源码在evaluateBoard()里就是这么写的int evaluateBoard() { int blackScore evaluateForPlayer(BLACK); int whiteScore evaluateForPlayer(WHITE); return blackScore - whiteScore; // 正数偏黑优负数偏白优 }evaluateForPlayer的实现就是遍历所有行、列、对角线对每条线上的每个位置调用scoreLineForPlayer把重复统计的棋型适当做去重或归一化最终汇总成单人总分。这个函数的单次执行耗时直接决定四层搜索能不能跑得动太贵的评估函数即使剪枝再好也会让单步思考时间突破20秒。所以源码里对这个函数能压则压——少用动态分配少用STL容器遍历保持在O(n²)级别并且常数很小。4. 极小极大与α-β剪枝把博弈树从指数级砍到可实时4.1 递归搜索的主干结构现在到了整份源码最核心的部分。没有剪枝的博弈树四层深度在15×15棋盘上根本不可能跑完——候选点动辄上百个一百的四次方是1亿次评估。α-β剪枝的价值就是把这个数量级压到几千次甚至几百次。搜索的主干是递归函数每层模拟一个玩家落子落子后调用评估函数打分再把分数往上传。先看主框架struct Point { int row, col; }; const int INF 1e9; int alphabeta(Point lastMove, int depth, int alpha, int beta, int currentPlayer) { // 模拟落子lastMove是上一层已经放好的子 if (checkWin(lastMove.row, lastMove.col, currentPlayer)) { // 上一步使得currentPlayer获胜 return currentPlayer BLACK ? 100000 depth : -100000 - depth; } if (depth 0) { return evaluateBoard(); // 到底层直接评个分 } std::vectorPoint candidates generateCandidates(); if (currentPlayer BLACK) { int maxEval -INF; for (Point p : candidates) { board[p.row][p.col] BLACK; int eval alphabeta(p, depth - 1, alpha, beta, WHITE); board[p.row][p.col] 0; // 恢复现场 maxEval std::max(maxEval, eval); alpha std::max(alpha, eval); if (beta alpha) break; // beta剪枝 } return maxEval; } else { int minEval INF; for (Point p : candidates) { board[p.row][p.col] WHITE; int eval alphabeta(p, depth - 1, alpha, beta, BLACK); board[p.row][p.col] 0; minEval std::min(minEval, eval); beta std::min(beta, eval); if (beta alpha) break; // alpha剪枝 } return minEval; } }这里有几个细节值得反复看。第一剪枝判断用的是beta alpha不是。用意味着当双方分数相等时直接剪掉不会影响正确性但能多砍一些节点。第二每次递归返回前都把棋盘置回0这个撤销动作一旦漏写整个搜索就会在错误棋盘上越陷越深。第三获胜返回值带了depth修饰越早获胜分越高这样AI在四层深度里会倾向于更快结束战斗而不是明明两步能赢却绕了五步。这个depth和-depth的技巧很多初版博弈树都没做结果就是AI完全不追求速度取胜。4.2 α-β剪枝的具体判定与边界条件单独看αβ参数也许不容易理解。用一个简单例子说明黑方是极大方白方是极小方。搜索过程中当前黑方已经找到一个分数为2000的分支那么alpha就被更新为2000。这时轮到黑方搜索另一个分支的白方节点白方一旦在这个节点里发现某个子节点的分数低于2000它就可以立刻返回——因为黑方上一层不可能选择一个比2000更差的结果。这就是alpha剪枝的直观含义。代码上要注意的边界条件是alpha和beta在递归过程中是以引用或者值传递的方式往下传的。上面代码用的是值传递意味着每一层都持有当前路径的alpha和beta快照剪枝判断只对本层有效。如果你改成全局变量务必小心子节点修改了alpha后影响兄弟节点判断很容易漏剪或错剪。源码里把alpha和beta作为函数参数传递、并且只在当前层更新这是正确且清晰的做法。另一个边界是深度归零时的处理。如果深度到0就返回evaluateBoard()这个评估分数应该对“谁先手”不敏感——它评价的是棋盘整体状态而不带“轮到谁”的先手优势。如果评估函数里包含了“当前轮次加分”那么搜索在偶数层和奇数层会得到不同的口径导致AI偏好某一方的奇怪行为。所以源码在设计评估函数时刻意规避了轮次信息只评价静态棋形。4.3 候选点排序启发式搜索让剪枝效率翻倍α-β剪枝的效果极大依赖搜索顺序——如果每次第一个候选点恰好是最优解剪枝率会非常高如果每次都先搜最差分支剪枝率就会相当难看。为了让“好的分支先被搜索”源码在递归前要对候选点排序。这个排序用的不是评估整盘棋而是一个轻量的启发式打分把候选点放上棋子算一下该点对当前玩家的棋型贡献再加上对对方棋型潜力的抵消作用排序后优先尝试分数高的点。int heuristicScore(const Point p, int player) { if (board[p.row][p.col] ! 0) return -INF; board[p.row][p.col] player; int gain evaluatePoint(p, player); // 我方落子后的棋型增益 board[p.row][p.col] 0; return gain; } void orderCandidates(std::vectorPoint cand, int player) { std::sort(cand.begin(), cand.end(), [](const Point a, const Point b) { return heuristicScore(a, player) heuristicScore(b, player); }); }这个evaluatePoint不需要全盘扫描只需要看落子点周围的四个方向上新增连子带来的分数增量。它比完整评估函数快一个数量级但已经能区分出“这个点是不是好点”。排序的代价是每次递归都要执行一次排序但换来的是更高频的剪枝整体收益远大于排序开销。源码里generateCandidates也做了限制只把已有棋子周围一圈的空位作为候选而不是整个棋盘的空格。这一步把候选数从上百分支压到二三十个分支是四层能跑实时的重要原因。5. 避坑与调参从评估函数到编译环境五个常见问题5.1 深度配置与性能的坑现象把搜索深度从4改成6AI单步思考时间从2秒暴涨到40秒。原因候选点数量没有限制时每层搜索节点数成指数增长单纯加深深度不会让剪枝率自动跟上。解决先确认候选点是“周围一圈”而不是全盘空点再用启发式排序把最优分支提前如果还不够快可以在搜索层加入时间上限到了时间阈值强制返回当前最佳分支。对这份源码来说四层在主流PC上能跑到1到3秒左右属于推荐配置。还有一类深度相关的问题正好相反搜索深度只设2层AI完全看不出对手的连续进攻意图经常做出挡住一个活二却放任对方连成冲四的蠢操作。原因深度不足时评估函数看到的是静态棋型活三的威胁要到更深层才会变成“成五得分”。解决至少设置到三层四层比较均衡如果硬件性能够五层以上配合置换表才有性价比。源码标题写“推算四层局面”意思就是默认depth4。5.2 评估函数与棋型的坑现象AI有机会活四却去冲三或者对手已经形成双活三它完全视而不见。原因评估函数给“活三”的分数和“冲三”区分不够导致搜索时觉得冲三的进攻潜力更大或者双方分数差计算时防守权重没有通过差值逻辑体现。解决严格对照上一章的权重表把五连、活四、冲四之间的差距拉大。记住一个原则评估函数的分数跨度要大于搜索深度的累计误差。四层搜索里一个冲四的误判会随着层数放大好几倍权重不可太接近。现象AI落子后明明没赢却返回了类似“必胜”的分数之后几手棋开始胡走。原因checkWin的判定条件不完整——可能只判了四个方向中的两个或者没有处理边界。解决用固定的五子棋题目比如黑方横四、白方竖四分别跑一次单测确认四种方向都能返回true。我日常调试时会专门写一个临时main函数把各种棋形摆上去直接调用checkWin。5.3 搜索回溯与工程环境的坑现象AI反复把一个位置当成空位落子棋盘上出现了叠子。原因递归里board[p.row][p.col] 0的恢复代码放在了获胜判断之前获胜返回时没有执行恢复导致棋盘状态污染。解决恢复现场和落子应当成对出现要么用RAII对象要么在每一个return之前手动复位。让恢复代码紧跟落子之后别分散在多个分支里。现象源码在Visual Studio里编译报C4996错误或者运行时scanf报安全警告。原因版本较老的C工程用了scanf、sprintf新编译器默认开启安全校验。解决项目属性里加_CRT_SECURE_NO_WARNINGS预处理宏或者换用std::cin、std::string输入。这也是为什么我拆这种老源码包时先会看一眼编译模式再开跑避免在环境问题上浪费半小时。6. 实战验证与扩展方向让AI从“能下”到“能赢”验证AI强度的最好方式不是跟人类下几局凭感觉而是让AI自己跟自己对弈统计固定时间内的胜率分布。我一般会写一个循环让黑方AI与白方AI各用同一份评估函数分别下100局记录胜负。如果黑方胜率明显高于白方说明评估函数对黑方存在系统偏好这通常是评估口径里某处把黑白权重搞不对称了。正常情况胜率应该接近50%——谁先手谁微优但不该出现压倒性优势。源码的扩展方向上第一优先级是加置换表。四层搜索里大量重复局面会在同一层多次出现用一个以棋盘哈希为key、以深度、评估值、最佳着法为value的缓存表可以让搜索速度提升一个数量级以上。第二个值得加的是时间控制不在递归里限制深度而是限制总耗时超过时间阈值就返回当前最佳着法。这样在低性能机器上AI会自动降层不至于思考超时。第三个方向是把当前的控制台棋盘换成图形界面——最简单的方式是接一个SDL窗口实用代码或者如果你不想引入图形库可以直接用Win32 API画棋盘加鼠标事件逻辑部分完全不用动。我自己的血泪教训是AI写完以后一定要强制跑一遍“AI执黑对阵AI执白”100局的自对弈验证再交付。有一版我以为把防守修好了结果实际一跑黑方老喜欢往边上落子原因是候选区域边界处理的缩略版让靠近边缘的棋型得分虚高。从那以后我每次手改评估函数的权重表都会先跑一轮自对弈回归后再合并到主分支。希望帮到你——这份五子棋AI源码的核心算法是标准的值不值得下载只看你愿不愿意把它当成一个解剖样本从棋盘表示一路剪枝到启发式排序全部吃透。本文还有配套的精品资源点击获取