简介基于C与α-β剪枝算法实现的AI五子棋游戏项目面向需要完成棋类AI课程设计、毕业设计或想深入理解博弈树搜索与剪枝优化的C开发者。压缩包共5个文件包含C源码、PDF实验报告、README说明与许可证文件整体仅803KB报告可辅助梳理算法流程结构紧凑便于按需查看、对照学习和二次开发。代码利用α-β剪枝对博弈树进行裁剪只搜索落子点周围2×2范围内存在棋子的候选位置显著减少无效节点遇到必胜或必败局面会直接返回估值不再继续深搜。AI还会在估值相近的落点中随机选择避免玩家用固定套路反复获胜提升对局灵活性与趣味性。已有507人学习下载既适合作为课程设计的完整参考也适合用来理解剪枝优化、棋局评估与AI落子策略的落地实现。1. 从贪心到α-β剪枝一个C五子棋AI的搜索空间压缩实战先说一个反直觉的结论同样的局面普通极小极大搜索下到第4层就开始卡顿而加上α-β剪枝和候选点筛选之后同一台机器能稳定推到第6到第8层落子响应还保持在秒级以内。这个差距不是因为机器变快了而是因为大部分搜索分支根本不需要看。这套基于C实现的α-β剪枝五子棋AI代码包就是围绕这个核心思路做的用博弈树剪枝压缩搜索空间用邻域限缩减少候选点用随机化打破固定应对套路。源码、报告、README都在包里适合两类人一是做课程设计或毕业设计想拿一个能跑、能讲清楚原理的C小游戏项目二是对博弈树算法有兴趣想看看α-β剪枝在真实棋盘上到底怎么落地的开发者。2. 博弈树与α-β剪枝的原理为什么普通极小极大撑不到第6层2.1 五子棋博弈树的节点规模到底有多恐怖五子棋棋盘是15×15理论上每个空位都可以落子。第1手有225个候选第2手224个第3手223个按这个速度往下走深度为d的博弈树节点数大约是候选点数的d次方。假设用邻域筛选后每层保留50个候选点搜索4层就要访问50的4次方即625万个节点如果不做任何裁剪下一层的子节点会立刻把这个数字推到几亿级别。这个数量级对C来说也不是不能跑但问题是五子棋AI需要在玩家落子后实时响应不是离线算一次。普通极小极大搜索在每一层都要完整评估所有子节点然后逐层返回最大值或最小值它的计算量是固定的不管局面是优是劣都必须全部算完。这意味着当深度增加到6层、8层时算法的耗时是指数级上升的很快就会出现玩家落子后要等几十秒甚至几分钟的局面。所以单纯用极小极大搜索做五子棋AI在工程上是不现实的。α-β剪枝解决的就是这个问题它不改变搜索的结果但能把很多必然不会被选中的分支直接砍掉。剪枝率足够高时同样的深度下计算量可以降一个数量级这才是AI能实时落子的关键。2.2 α-β剪枝剪掉的是哪些不用看的分支α-β剪枝的核心思路可以这样理解极大层AI回合维护一个α值代表AI当前已经找到的最低保障分数极小层玩家回合维护一个β值代表玩家当前能给AI造成的最大威胁。当搜索到某一个极小层节点发现玩家的回应对手能让分数压到α以下那AI无论如何都不会选择这个分支因为已经有更好的选择摆在前面了。此时直接return不再往下展开这就是β剪枝。反过来极大层节点发现某个走法能把分数抬到β以上玩家那一侧也不会让这个局面发生于是触发α剪枝。从代码实现上看剪枝条件只有一句话if (alpha beta) break;。但这句话能不能生效严重依赖于搜索顺序。如果先搜索的走法恰好是较优的走法α和β会快速收敛剪枝频繁触发如果先搜索的是很差的走法α和β长时间停留在初始值附近剪枝就很难发生退化成普通极小极大搜索。常见做法是在进入α-β递归之前先对候选点做一次简单排序用评估函数粗算每个候选点的分数把分高的走法排在前面。这样虽然每次多花一点排序时间但剪枝率会明显提升。这个项目里并没有强制要求排序因为候选点本身被限制在2×2邻域范围内数量不大排序的收益容易被搜索本身的耗时掩盖。我个人的习惯是当单层候选点超过30个时排序是划算的少于20个时直接按获取顺序进入递归问题也不大剪枝率会有波动但整体可控。2.3 评估函数把棋形量化成可比较的分数α-β剪枝本身不产生棋力它只是加速搜索。真正决定AI强弱的是评估函数。评估函数负责回答一个问题当前这个局面站在AI角度值多少分。五子棋的评估通常围绕棋形展开就是看棋盘上有多少活二、眠三、活三、冲四、活四之类的特征。常见做法是扫描所有方向上连续的同色棋子数量按长度和开放程度打分。下面是一份常用的棋形分数表数值的量级划分比具体数值更重要棋形典型分数说明五连100000搜索中通常由胜负判定直接截获活四50000两头都开放的四个连子无法被堵死冲四5000只有一头开放的四个连子活三3000再走一步能变成活四的三连眠三500只有一头开放的三连活二200有发展潜力的两连单子10孤立棋子基本只有占地价值这份分数表只是一个起点。真正在实战中你会发现AI的防守能力取决于对手棋形在评估里占了多大权重。如果评估函数只统计AI自己的连子分数、不扣除玩家棋形的威胁那AI就会变成只顾进攻、死活不堵对手活三的愣头青。所以合格的五子棋评估函数一定是攻防对称的AI得分减去玩家得分的差值才是局面评估值。3. 三个关键的工程取舍候选点、搜索深度与随机化落子3.1 候选点筛选只搜落子点周围2×2邻域15×15棋盘上一共有225个位置如果每一层都对所有空位做评估和递归搜索树会迅速膨胀到不可收拾。但这个项目的核心优化思路很直接远离已有棋子的空位在几步之内不会对局面产生实质影响根本不需要参与搜索。所以候选点只从落子点周围2×2格范围内存在棋子的位置里生成。这个radius 2的默认值是有讲究的。棋盘上最强的攻击棋形比如活三、冲四最远影响的棋子距离是间隔两个交叉点的跳二或跳三。半径取2能覆盖到大部分有实际意义的着法包括跳活二的第三子延伸、冲四的堵截位置。我做过简单实验把radius从2调到3候选点数量大约膨胀1.5到2倍搜索时间跟着翻倍但棋力提升非常有限。std::vectorPos get_candidate_moves(const Board board, int radius 2) { bool mark[BOARD_SIZE][BOARD_SIZE] {false}; std::vectorPos candidates; for (int r 0; r BOARD_SIZE; r) { for (int c 0; c BOARD_SIZE; c) { if (board.grid[r][c] EMPTY) continue; for (int dr -radius; dr radius; dr) { for (int dc -radius; dc radius; dc) { int nr r dr, nc c dc; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) continue; if (board.grid[nr][nc] EMPTY !mark[nr][nc]) { mark[nr][nc] true; candidates.push_back({nr, nc}); } } } } } return candidates; }这段代码的逻辑是遍历棋盘上所有非空棋子以每个棋子为中心把周围2×2范围内的空格记录下来。mark数组用来去重防止同一个位置被多个相邻棋子重复加入候选。这里有两个容易被忽略的边界第一当棋盘还是空的、没有任何棋子时候选集合为空AI会无处可下。第二白棋和黑棋是轮流落子的候选点应该同时覆盖双方棋子的邻域不能只搜AI自己棋子的周围否则AI会看不见对手的进攻。3.2 搜索深度怎么定从4层起步的迭代加深深度决定了AI能看多远深度4的AI能看到自己走一步、对手应一步、自己再走一步的完整变化深度6则能看到三步半。但深度每加1博弈树的节点数大约乘以候选点数所以深度不是一个可以随意上调的参数。常见的做法是迭代加深先算深度2拿一个基准结果再算深度4再算深度6每层之间如果超时就停止用上一层的搜索结果兜底。这个项目的源码里没有强制做复杂的超时控制主要靠固定深度加剪枝来控制时间。根据我的实测经验在候选点被限制到2×2邻域、评估函数不做全盘重复扫描的前提下各深度在Release模式下的表现大致如下搜索深度单层候选点数大致耗时适用场景220~40 10ms初学者验证流程430~50100ms左右日常对弈起步值640~601~3秒棋力明显增强响应可接受86010秒以上不建议用于交互式对弈参数调优时要注意深度6和深度4的棋力差距非常明显但前提是评估函数本身没写歪。如果评估函数只统计连子数量、不看开放度深度再高也只会走出看似合理实则漏洞百出的棋。3.3 随机化落子让AI不再一套路吃遍天普通AI有一个很致命的问题对同一局面永远给出同一个回应。玩家只要赢了一次记住那套走法复盘重来就能用完全相同的方式再次获胜。这个项目的解决方案是在AI选择落子位置时把估值接近的几个位置放进候选池从中随机挑一个。把逻辑说清楚α-β搜索返回的是最佳估值但最佳不是一个点而是一组点——所有估值等于最优值的走法都值得考虑。与其固定选第一个不如把它们都收集起来最后用随机数决定。int bestVal -INF; std::vectorPos bestList; for (const Pos m : moves) { board.place(m, COMPUTER); int val alphabeta(board, depth - 1, -INF, INF, false); board.undo(m); if (val bestVal) { bestVal val; bestList.clear(); bestList.push_back(m); } else if (val bestVal) { bestList.push_back(m); } } Pos finalMove bestList[rand() % bestList.size()];这里有一个关键参数val bestVal的相等判定在浮点评估下几乎不会触发因为评估分数通常是整数累加所以实际上收集到的仍然是有多个等价最优解的情况。如果你把评估函数改成浮点打分最好把换成区间判定比如abs(val - bestVal) 10否则随机化就名存实亡了。随机化的幅度也要控制。我一般会给随机池设一个上限比如只从估值差距不超过50分的走法里挑选避免AI在明显劣等的走法里随机游走。换句话说随机是给看起来差不多的最优解加扰动不是让AI乱下。4. 核心代码拆解从棋盘类到α-β搜索主循环4.1 棋盘数据结构二维数组与STL的选择棋盘的表示方式直接影响到后面所有函数的写法。这个项目里的棋盘是固定15×15最自然的表示就是int grid[15][15]。用std::vectorstd::vectorint当然也可以但固定尺寸二维数组在Cache友好性和写代码的直观性上都更好尤其适合课程设计这种需要反复讲解代码的场景。我习惯把棋盘相关的操作封装成一个Board类至少包含落子、撤销、胜负判断、评估四个方法。落子后要记录最后落子的位置这样胜负判断只需要检查最后落子点附近的棋形而不需要每次全盘扫描。撤销落子则是α-β递归回溯时的必要操作用grid[r][c] EMPTY即可不需要额外记录历史状态。constexpr int BOARD_SIZE 15; constexpr int EMPTY 0; constexpr int PLAYER 1; constexpr int COMPUTER 2; struct Pos { int r, c; }; class Board { public: int grid[BOARD_SIZE][BOARD_SIZE]; int last_r -1, last_c -1; bool game_over false; Board() { memset(grid, 0, sizeof(grid)); } void place(int r, int c, int player) { grid[r][c] player; last_r r; last_c c; } void undo(int r, int c) { grid[r][c] EMPTY; } };place和undo是搜索递归的两个对称操作。搜索过程实际上是不断尝试落子、评估、撤销的过程grid始终反映当前搜索路径上的局面。这里有个细节undo之后last_r不会自动恢复但由于胜负判断只关注刚刚落下的那一手而递归过程中每一层的last_r都由那一层的place重新设置所以不会出错。4.2 α-β搜索主函数初始值、返回值与剪枝判定核心搜索函数是递归的参数包括当前局面、剩余深度、α值、β值、当前轮次。下面是我按这个项目思路重写的标准版本注意必胜负局面的提前返回const int MAX_SCORE 100000; int alphabeta(Board board, int depth, int alpha, int beta, bool maximizing) { int winner check_win(board); if (winner COMPUTER) return MAX_SCORE; if (winner PLAYER) return -MAX_SCORE; if (depth 0) return evaluate(board); auto moves get_candidate_moves(board); if (moves.empty()) moves.push_back({BOARD_SIZE / 2, BOARD_SIZE / 2}); if (maximizing) { for (const Pos m : moves) { board.place(m.r, m.c, COMPUTER); int val alphabeta(board, depth - 1, alpha, beta, false); board.undo(m.r, m.c); if (val alpha) alpha val; if (alpha beta) break; } return alpha; } else { for (const Pos m : moves) { board.place(m.r, m.c, PLAYER); int val alphabeta(board, depth - 1, alpha, beta, true); board.undo(m.r, m.c); if (val beta) beta val; if (alpha beta) break; } return beta; } }先看返回值当发现玩家已经五连直接返回-MAX_SCORE等于告诉上层这个分支已经彻底死了继续搜索是浪费时间。这正是项目说明里避免对必胜/负局面搜索的落点。MAX_SCORE取得足够大保证它优先于任何评估分数。再看剪枝条件最大化分支里只在val alpha时更新α一旦α≥β就停最小化分支对称处理。这里如果alpha和beta的初始值设反了剪枝条件会永远不成立代码会退化成普通极小极大速度立刻降下来。这个函数在实战中用到的频率非常高栈深度等于搜索深度。深度6的时候递归调用次数可能上千万每一步的place、undo、check_win都要快所以那些全盘扫描的写法在8层深度下就是灾难。4.3 胜负判定与评估函数只查最后落子的优化胜负判定如果每次递归都对整个棋盘做四方向扫描代价太高。正确做法是只检查最后落子的位置从最后落子点出发沿水平、垂直、两条对角线各向两端延伸统计连续同色棋子数任意方向累计达到5即判胜。int check_win(const Board board) { int r board.last_r, c board.last_c; int p board.grid[r][c]; if (p EMPTY) return EMPTY; static const int dr[4] {0, 1, 1, 1}; static const int dc[4] {1, 0, 1, -1}; for (int d 0; d 4; d) { int cnt 1; for (int step 1; step 5; step) { int nr r dr[d] * step, nc c dc[d] * step; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) break; if (board.grid[nr][nc] ! p) break; cnt; } for (int step 1; step 5; step) { int nr r - dr[d] * step, nc c - dc[d] * step; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) break; if (board.grid[nr][nc] ! p) break; cnt; } if (cnt 5) return p; } return EMPTY; }这个函数每轮只检查一个点最坏情况下每个方向累计检查8个格子32次循环非常轻量。我在实际写代码时会把cnt的初始值设为1因为最后落子点本身已经是同色棋子了。双方向累加时要注意正方向和反方向的循环索引很容易把边界判断写错导致数组越界或漏判。评估函数的写法空间很大。我见过最简的版本就是按每个位置四个方向上连子数的平方来累加差分AI的连子数贡献正分玩家的连子数贡献负分。缺点是它没有区分活三和眠三碰到两头都被堵死的死棋也会给出高估分。完整的做法是先判断两端是否开放再给棋形分类。对于这个项目来说评估函数即使做成简化版也够用因为深度6的搜索会通过局面推演修正很多静态评估的错误。4.4 主流程人机交替、计时与AI调用主程序的逻辑并不复杂初始化棋盘玩家和AI交替落子AI每一次落子前启动计时器搜索结束后打印耗时和落子坐标。这里有一个容易被忽略的细节AI的搜索深度应该根据当前候选点数量动态调整。开局时棋子少、候选点少可以放心搜到6层中盘候选点多了强行维持6层会导致长考。常见做法是给搜索加一个时间上限到点就返回当前已完成深度的结果。int main() { Board board; srand(static_castunsigned(time(nullptr))); bool ai_first false; while (!board.game_over) { board.show(); if (board.last_r -1) { // 空棋盘AI先手固定走天元附近 board.place(7, 7, ai_first ? COMPUTER : PLAYER); continue; } if (board.turn COMPUTER) { auto start std::chrono::steady_clock::now(); Pos p ai_move(board, 6); board.place(p.r, p.c, COMPUTER); auto ms std::chrono::duration_caststd::chrono::milliseconds( std::chrono::steady_clock::now() - start).count(); std::cout AI耗时 ms ms 落子: ( p.r , p.c )\n; } else { int r, c; std::cin r c; board.place(r, c, PLAYER); } board.game_over (check_win(board) ! EMPTY); } return 0; }ai_move内部调用alphabeta把返回的最优位置交给主流程。计时输出对调参特别有价值你改了评估函数或者depth之后看这两行数字就知道改动是让AI变快了还是变慢了。在VSCode里配好C/C环境之后直接F5跑起来就能看到完整的对弈过程调试窗口里还能打断点看α、β值的变化轨迹。5. 避坑指南五子棋AI调试中的五个典型翻车点5.1 空棋盘时AI无处可下现象AI先手落子时直接崩溃或者调用get_candidate_moves返回空集合moves为空后取不到合法落子点。原因候选点生成函数只围绕已有棋子展开空棋盘上一个棋子都没有自然生成不了任何候选点。很多人在测试时没有先手让AI落子后面所有的搜索都建立在这个假设上直到换边才暴露。解决在alphabeta和ai_move入口处加空棋盘判断。空棋盘时直接返回天元位置即Pos{7, 7}。我写的是在搜索函数里兜底if (moves.empty()) moves.push_back({BOARD_SIZE / 2, BOARD_SIZE / 2});这样不管什么路径进来都不会因为空候选崩溃。5.2 评估函数只算进攻不算防守现象AI棋力看起来很强连子摆得很多但对手下出活三甚至冲四时AI熟视无睹不去堵截最终被一波带走。原因评估函数只统计了AI自己的棋形分数玩家棋子的威胁没有进入评估值。α-β搜索的最优只对评估函数负责如果评估函数看不见对手的活三搜索自然不会去防守。解决评估函数改成攻防对称AI分数减去玩家分数。并且对玩家活三、冲四这类即将成杀的棋形要给特别高的负分权重。血泪经验是评估函数里防守权重略高于进攻权重AI下棋的稳感会明显提升。5.3 α和β初始值设反剪枝形同虚设现象加了α-β剪枝之后搜索速度没有明显变化和普通极小极大耗时差不多甚至更慢。原因极大层初始α设成了INF、极小层β设成了-INF导致alpha beta永远不可能成立剪枝条件从未触发过。另一个可能原因是递归内部的调用层数搞反了极大层调用了极大层。解决初始化固定为int alpha -INF; int beta INF;。在递归入口加一行调试日志输出当前层的alpha和beta看它们是否在快速收敛。如果十几次搜索后α和β仍然保持初始值基本可以断定剪枝条件或者递归方向写错了。5.4 深度提一档响应时间暴涨几倍现象搜索深度从4调到6之后AI单步思考时间从几百毫秒涨到十几秒完全无法对弈。原因深度每加1博弈树规模大约乘以平均候选点数。如果候选点没有裁剪到位、评估函数每次全盘扫描时间膨胀就是灾难性的。还有一个隐蔽因素是编译模式Debug模式下递归开销巨大同样的深度耗时可能是Release的10倍以上。解决先确认候选点限制在2×2邻域胜负判定只看最后落子点。然后用迭代加深代替固定深度先搜2层再搜4层给整体调用一个时间上限超时就用上一层的计算结果。编译时使用Release模式并开启O2优化C的递归函数在这两个模式下的性能差距非常离谱。5.5 随机化之后bug难复现现象加了随机化落子之后AI有时候下得很好有时候明显抽风。想复现某一步异常时重开一局又走出了不同的棋没法稳定观察。原因随机种子没有做开关控制每次运行都不一样。调试时你看到的是一个黑匣子同样的局面AI可能给出完全不同的反应。解决把随机化做成可配置项。加一个config.h定义const bool RANDOMIZE true;和const int RANDOM_SEED 42;。调试时把RANDOMIZE关掉或固定种子复现问题调完再打开。我一般在main里只写if (RANDOMIZE) srand(time(nullptr)); else srand(RANDOM_SEED);这一行就够。6. 验证AI强度先手后手回归测试与调试日志技巧判断一个五子棋AI改动到底是变强了还是变弱了最直接的做法不是跟它下几局靠感觉判断而是跑一轮先手后手各20局的回归对弈。把AI放在先手位置固定种子连下20局记录胜负再换到后手位置再连下20局。改动之后对比这两组数据胜率提升才是真提升单局赢棋很可能是运气。我用这个方案踩过不少坑。有一次只改了评估函数里活三的权重跟AI下了三局觉得变强了结果回归测试一跑后手胜率掉了15个百分点——原因是权重调太高后AI过度追求活三忽略了冲四的直接杀着。从那以后我每次改完评估函数都会强制走一遍先手后手各20局的回归再决定要不要保留这次改动。这个习惯替我挡住了很多次看着变强实际变弱的翻车。另一个很实用的技巧是给搜索过程加日志开关。在alphabeta的入口做一个debug变量控制打印当前深度、候选点数量、剪枝触发次数、返回值。这样你能看到AI在某一层究竟剪掉了多少分支也能定位这一步AI为什么下在这里的推理过程。搜索的α-β值收敛轨迹其实比最终落子信息更有参考价值。这个项目的代码和报告都在压缩包里README里已经写清了文件路径和编译方式解压后按说明跑起来建议先把我说的这几个避坑点过一遍再动手调参。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/12 20:33:15 · 阅读 1.2k C++五子棋AI实战：α-β剪枝与博弈树搜索优化
简介基于C与α-β剪枝算法实现的AI五子棋游戏项目面向需要完成棋类AI课程设计、毕业设计或想深入理解博弈树搜索与剪枝优化的C开发者。压缩包共5个文件包含C源码、PDF实验报告、README说明与许可证文件整体仅803KB报告可辅助梳理算法流程结构紧凑便于按需查看、对照学习和二次开发。代码利用α-β剪枝对博弈树进行裁剪只搜索落子点周围2×2范围内存在棋子的候选位置显著减少无效节点遇到必胜或必败局面会直接返回估值不再继续深搜。AI还会在估值相近的落点中随机选择避免玩家用固定套路反复获胜提升对局灵活性与趣味性。已有507人学习下载既适合作为课程设计的完整参考也适合用来理解剪枝优化、棋局评估与AI落子策略的落地实现。1. 从贪心到α-β剪枝一个C五子棋AI的搜索空间压缩实战先说一个反直觉的结论同样的局面普通极小极大搜索下到第4层就开始卡顿而加上α-β剪枝和候选点筛选之后同一台机器能稳定推到第6到第8层落子响应还保持在秒级以内。这个差距不是因为机器变快了而是因为大部分搜索分支根本不需要看。这套基于C实现的α-β剪枝五子棋AI代码包就是围绕这个核心思路做的用博弈树剪枝压缩搜索空间用邻域限缩减少候选点用随机化打破固定应对套路。源码、报告、README都在包里适合两类人一是做课程设计或毕业设计想拿一个能跑、能讲清楚原理的C小游戏项目二是对博弈树算法有兴趣想看看α-β剪枝在真实棋盘上到底怎么落地的开发者。2. 博弈树与α-β剪枝的原理为什么普通极小极大撑不到第6层2.1 五子棋博弈树的节点规模到底有多恐怖五子棋棋盘是15×15理论上每个空位都可以落子。第1手有225个候选第2手224个第3手223个按这个速度往下走深度为d的博弈树节点数大约是候选点数的d次方。假设用邻域筛选后每层保留50个候选点搜索4层就要访问50的4次方即625万个节点如果不做任何裁剪下一层的子节点会立刻把这个数字推到几亿级别。这个数量级对C来说也不是不能跑但问题是五子棋AI需要在玩家落子后实时响应不是离线算一次。普通极小极大搜索在每一层都要完整评估所有子节点然后逐层返回最大值或最小值它的计算量是固定的不管局面是优是劣都必须全部算完。这意味着当深度增加到6层、8层时算法的耗时是指数级上升的很快就会出现玩家落子后要等几十秒甚至几分钟的局面。所以单纯用极小极大搜索做五子棋AI在工程上是不现实的。α-β剪枝解决的就是这个问题它不改变搜索的结果但能把很多必然不会被选中的分支直接砍掉。剪枝率足够高时同样的深度下计算量可以降一个数量级这才是AI能实时落子的关键。2.2 α-β剪枝剪掉的是哪些不用看的分支α-β剪枝的核心思路可以这样理解极大层AI回合维护一个α值代表AI当前已经找到的最低保障分数极小层玩家回合维护一个β值代表玩家当前能给AI造成的最大威胁。当搜索到某一个极小层节点发现玩家的回应对手能让分数压到α以下那AI无论如何都不会选择这个分支因为已经有更好的选择摆在前面了。此时直接return不再往下展开这就是β剪枝。反过来极大层节点发现某个走法能把分数抬到β以上玩家那一侧也不会让这个局面发生于是触发α剪枝。从代码实现上看剪枝条件只有一句话if (alpha beta) break;。但这句话能不能生效严重依赖于搜索顺序。如果先搜索的走法恰好是较优的走法α和β会快速收敛剪枝频繁触发如果先搜索的是很差的走法α和β长时间停留在初始值附近剪枝就很难发生退化成普通极小极大搜索。常见做法是在进入α-β递归之前先对候选点做一次简单排序用评估函数粗算每个候选点的分数把分高的走法排在前面。这样虽然每次多花一点排序时间但剪枝率会明显提升。这个项目里并没有强制要求排序因为候选点本身被限制在2×2邻域范围内数量不大排序的收益容易被搜索本身的耗时掩盖。我个人的习惯是当单层候选点超过30个时排序是划算的少于20个时直接按获取顺序进入递归问题也不大剪枝率会有波动但整体可控。2.3 评估函数把棋形量化成可比较的分数α-β剪枝本身不产生棋力它只是加速搜索。真正决定AI强弱的是评估函数。评估函数负责回答一个问题当前这个局面站在AI角度值多少分。五子棋的评估通常围绕棋形展开就是看棋盘上有多少活二、眠三、活三、冲四、活四之类的特征。常见做法是扫描所有方向上连续的同色棋子数量按长度和开放程度打分。下面是一份常用的棋形分数表数值的量级划分比具体数值更重要棋形典型分数说明五连100000搜索中通常由胜负判定直接截获活四50000两头都开放的四个连子无法被堵死冲四5000只有一头开放的四个连子活三3000再走一步能变成活四的三连眠三500只有一头开放的三连活二200有发展潜力的两连单子10孤立棋子基本只有占地价值这份分数表只是一个起点。真正在实战中你会发现AI的防守能力取决于对手棋形在评估里占了多大权重。如果评估函数只统计AI自己的连子分数、不扣除玩家棋形的威胁那AI就会变成只顾进攻、死活不堵对手活三的愣头青。所以合格的五子棋评估函数一定是攻防对称的AI得分减去玩家得分的差值才是局面评估值。3. 三个关键的工程取舍候选点、搜索深度与随机化落子3.1 候选点筛选只搜落子点周围2×2邻域15×15棋盘上一共有225个位置如果每一层都对所有空位做评估和递归搜索树会迅速膨胀到不可收拾。但这个项目的核心优化思路很直接远离已有棋子的空位在几步之内不会对局面产生实质影响根本不需要参与搜索。所以候选点只从落子点周围2×2格范围内存在棋子的位置里生成。这个radius 2的默认值是有讲究的。棋盘上最强的攻击棋形比如活三、冲四最远影响的棋子距离是间隔两个交叉点的跳二或跳三。半径取2能覆盖到大部分有实际意义的着法包括跳活二的第三子延伸、冲四的堵截位置。我做过简单实验把radius从2调到3候选点数量大约膨胀1.5到2倍搜索时间跟着翻倍但棋力提升非常有限。std::vectorPos get_candidate_moves(const Board board, int radius 2) { bool mark[BOARD_SIZE][BOARD_SIZE] {false}; std::vectorPos candidates; for (int r 0; r BOARD_SIZE; r) { for (int c 0; c BOARD_SIZE; c) { if (board.grid[r][c] EMPTY) continue; for (int dr -radius; dr radius; dr) { for (int dc -radius; dc radius; dc) { int nr r dr, nc c dc; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) continue; if (board.grid[nr][nc] EMPTY !mark[nr][nc]) { mark[nr][nc] true; candidates.push_back({nr, nc}); } } } } } return candidates; }这段代码的逻辑是遍历棋盘上所有非空棋子以每个棋子为中心把周围2×2范围内的空格记录下来。mark数组用来去重防止同一个位置被多个相邻棋子重复加入候选。这里有两个容易被忽略的边界第一当棋盘还是空的、没有任何棋子时候选集合为空AI会无处可下。第二白棋和黑棋是轮流落子的候选点应该同时覆盖双方棋子的邻域不能只搜AI自己棋子的周围否则AI会看不见对手的进攻。3.2 搜索深度怎么定从4层起步的迭代加深深度决定了AI能看多远深度4的AI能看到自己走一步、对手应一步、自己再走一步的完整变化深度6则能看到三步半。但深度每加1博弈树的节点数大约乘以候选点数所以深度不是一个可以随意上调的参数。常见的做法是迭代加深先算深度2拿一个基准结果再算深度4再算深度6每层之间如果超时就停止用上一层的搜索结果兜底。这个项目的源码里没有强制做复杂的超时控制主要靠固定深度加剪枝来控制时间。根据我的实测经验在候选点被限制到2×2邻域、评估函数不做全盘重复扫描的前提下各深度在Release模式下的表现大致如下搜索深度单层候选点数大致耗时适用场景220~40 10ms初学者验证流程430~50100ms左右日常对弈起步值640~601~3秒棋力明显增强响应可接受86010秒以上不建议用于交互式对弈参数调优时要注意深度6和深度4的棋力差距非常明显但前提是评估函数本身没写歪。如果评估函数只统计连子数量、不看开放度深度再高也只会走出看似合理实则漏洞百出的棋。3.3 随机化落子让AI不再一套路吃遍天普通AI有一个很致命的问题对同一局面永远给出同一个回应。玩家只要赢了一次记住那套走法复盘重来就能用完全相同的方式再次获胜。这个项目的解决方案是在AI选择落子位置时把估值接近的几个位置放进候选池从中随机挑一个。把逻辑说清楚α-β搜索返回的是最佳估值但最佳不是一个点而是一组点——所有估值等于最优值的走法都值得考虑。与其固定选第一个不如把它们都收集起来最后用随机数决定。int bestVal -INF; std::vectorPos bestList; for (const Pos m : moves) { board.place(m, COMPUTER); int val alphabeta(board, depth - 1, -INF, INF, false); board.undo(m); if (val bestVal) { bestVal val; bestList.clear(); bestList.push_back(m); } else if (val bestVal) { bestList.push_back(m); } } Pos finalMove bestList[rand() % bestList.size()];这里有一个关键参数val bestVal的相等判定在浮点评估下几乎不会触发因为评估分数通常是整数累加所以实际上收集到的仍然是有多个等价最优解的情况。如果你把评估函数改成浮点打分最好把换成区间判定比如abs(val - bestVal) 10否则随机化就名存实亡了。随机化的幅度也要控制。我一般会给随机池设一个上限比如只从估值差距不超过50分的走法里挑选避免AI在明显劣等的走法里随机游走。换句话说随机是给看起来差不多的最优解加扰动不是让AI乱下。4. 核心代码拆解从棋盘类到α-β搜索主循环4.1 棋盘数据结构二维数组与STL的选择棋盘的表示方式直接影响到后面所有函数的写法。这个项目里的棋盘是固定15×15最自然的表示就是int grid[15][15]。用std::vectorstd::vectorint当然也可以但固定尺寸二维数组在Cache友好性和写代码的直观性上都更好尤其适合课程设计这种需要反复讲解代码的场景。我习惯把棋盘相关的操作封装成一个Board类至少包含落子、撤销、胜负判断、评估四个方法。落子后要记录最后落子的位置这样胜负判断只需要检查最后落子点附近的棋形而不需要每次全盘扫描。撤销落子则是α-β递归回溯时的必要操作用grid[r][c] EMPTY即可不需要额外记录历史状态。constexpr int BOARD_SIZE 15; constexpr int EMPTY 0; constexpr int PLAYER 1; constexpr int COMPUTER 2; struct Pos { int r, c; }; class Board { public: int grid[BOARD_SIZE][BOARD_SIZE]; int last_r -1, last_c -1; bool game_over false; Board() { memset(grid, 0, sizeof(grid)); } void place(int r, int c, int player) { grid[r][c] player; last_r r; last_c c; } void undo(int r, int c) { grid[r][c] EMPTY; } };place和undo是搜索递归的两个对称操作。搜索过程实际上是不断尝试落子、评估、撤销的过程grid始终反映当前搜索路径上的局面。这里有个细节undo之后last_r不会自动恢复但由于胜负判断只关注刚刚落下的那一手而递归过程中每一层的last_r都由那一层的place重新设置所以不会出错。4.2 α-β搜索主函数初始值、返回值与剪枝判定核心搜索函数是递归的参数包括当前局面、剩余深度、α值、β值、当前轮次。下面是我按这个项目思路重写的标准版本注意必胜负局面的提前返回const int MAX_SCORE 100000; int alphabeta(Board board, int depth, int alpha, int beta, bool maximizing) { int winner check_win(board); if (winner COMPUTER) return MAX_SCORE; if (winner PLAYER) return -MAX_SCORE; if (depth 0) return evaluate(board); auto moves get_candidate_moves(board); if (moves.empty()) moves.push_back({BOARD_SIZE / 2, BOARD_SIZE / 2}); if (maximizing) { for (const Pos m : moves) { board.place(m.r, m.c, COMPUTER); int val alphabeta(board, depth - 1, alpha, beta, false); board.undo(m.r, m.c); if (val alpha) alpha val; if (alpha beta) break; } return alpha; } else { for (const Pos m : moves) { board.place(m.r, m.c, PLAYER); int val alphabeta(board, depth - 1, alpha, beta, true); board.undo(m.r, m.c); if (val beta) beta val; if (alpha beta) break; } return beta; } }先看返回值当发现玩家已经五连直接返回-MAX_SCORE等于告诉上层这个分支已经彻底死了继续搜索是浪费时间。这正是项目说明里避免对必胜/负局面搜索的落点。MAX_SCORE取得足够大保证它优先于任何评估分数。再看剪枝条件最大化分支里只在val alpha时更新α一旦α≥β就停最小化分支对称处理。这里如果alpha和beta的初始值设反了剪枝条件会永远不成立代码会退化成普通极小极大速度立刻降下来。这个函数在实战中用到的频率非常高栈深度等于搜索深度。深度6的时候递归调用次数可能上千万每一步的place、undo、check_win都要快所以那些全盘扫描的写法在8层深度下就是灾难。4.3 胜负判定与评估函数只查最后落子的优化胜负判定如果每次递归都对整个棋盘做四方向扫描代价太高。正确做法是只检查最后落子的位置从最后落子点出发沿水平、垂直、两条对角线各向两端延伸统计连续同色棋子数任意方向累计达到5即判胜。int check_win(const Board board) { int r board.last_r, c board.last_c; int p board.grid[r][c]; if (p EMPTY) return EMPTY; static const int dr[4] {0, 1, 1, 1}; static const int dc[4] {1, 0, 1, -1}; for (int d 0; d 4; d) { int cnt 1; for (int step 1; step 5; step) { int nr r dr[d] * step, nc c dc[d] * step; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) break; if (board.grid[nr][nc] ! p) break; cnt; } for (int step 1; step 5; step) { int nr r - dr[d] * step, nc c - dc[d] * step; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) break; if (board.grid[nr][nc] ! p) break; cnt; } if (cnt 5) return p; } return EMPTY; }这个函数每轮只检查一个点最坏情况下每个方向累计检查8个格子32次循环非常轻量。我在实际写代码时会把cnt的初始值设为1因为最后落子点本身已经是同色棋子了。双方向累加时要注意正方向和反方向的循环索引很容易把边界判断写错导致数组越界或漏判。评估函数的写法空间很大。我见过最简的版本就是按每个位置四个方向上连子数的平方来累加差分AI的连子数贡献正分玩家的连子数贡献负分。缺点是它没有区分活三和眠三碰到两头都被堵死的死棋也会给出高估分。完整的做法是先判断两端是否开放再给棋形分类。对于这个项目来说评估函数即使做成简化版也够用因为深度6的搜索会通过局面推演修正很多静态评估的错误。4.4 主流程人机交替、计时与AI调用主程序的逻辑并不复杂初始化棋盘玩家和AI交替落子AI每一次落子前启动计时器搜索结束后打印耗时和落子坐标。这里有一个容易被忽略的细节AI的搜索深度应该根据当前候选点数量动态调整。开局时棋子少、候选点少可以放心搜到6层中盘候选点多了强行维持6层会导致长考。常见做法是给搜索加一个时间上限到点就返回当前已完成深度的结果。int main() { Board board; srand(static_castunsigned(time(nullptr))); bool ai_first false; while (!board.game_over) { board.show(); if (board.last_r -1) { // 空棋盘AI先手固定走天元附近 board.place(7, 7, ai_first ? COMPUTER : PLAYER); continue; } if (board.turn COMPUTER) { auto start std::chrono::steady_clock::now(); Pos p ai_move(board, 6); board.place(p.r, p.c, COMPUTER); auto ms std::chrono::duration_caststd::chrono::milliseconds( std::chrono::steady_clock::now() - start).count(); std::cout AI耗时 ms ms 落子: ( p.r , p.c )\n; } else { int r, c; std::cin r c; board.place(r, c, PLAYER); } board.game_over (check_win(board) ! EMPTY); } return 0; }ai_move内部调用alphabeta把返回的最优位置交给主流程。计时输出对调参特别有价值你改了评估函数或者depth之后看这两行数字就知道改动是让AI变快了还是变慢了。在VSCode里配好C/C环境之后直接F5跑起来就能看到完整的对弈过程调试窗口里还能打断点看α、β值的变化轨迹。5. 避坑指南五子棋AI调试中的五个典型翻车点5.1 空棋盘时AI无处可下现象AI先手落子时直接崩溃或者调用get_candidate_moves返回空集合moves为空后取不到合法落子点。原因候选点生成函数只围绕已有棋子展开空棋盘上一个棋子都没有自然生成不了任何候选点。很多人在测试时没有先手让AI落子后面所有的搜索都建立在这个假设上直到换边才暴露。解决在alphabeta和ai_move入口处加空棋盘判断。空棋盘时直接返回天元位置即Pos{7, 7}。我写的是在搜索函数里兜底if (moves.empty()) moves.push_back({BOARD_SIZE / 2, BOARD_SIZE / 2});这样不管什么路径进来都不会因为空候选崩溃。5.2 评估函数只算进攻不算防守现象AI棋力看起来很强连子摆得很多但对手下出活三甚至冲四时AI熟视无睹不去堵截最终被一波带走。原因评估函数只统计了AI自己的棋形分数玩家棋子的威胁没有进入评估值。α-β搜索的最优只对评估函数负责如果评估函数看不见对手的活三搜索自然不会去防守。解决评估函数改成攻防对称AI分数减去玩家分数。并且对玩家活三、冲四这类即将成杀的棋形要给特别高的负分权重。血泪经验是评估函数里防守权重略高于进攻权重AI下棋的稳感会明显提升。5.3 α和β初始值设反剪枝形同虚设现象加了α-β剪枝之后搜索速度没有明显变化和普通极小极大耗时差不多甚至更慢。原因极大层初始α设成了INF、极小层β设成了-INF导致alpha beta永远不可能成立剪枝条件从未触发过。另一个可能原因是递归内部的调用层数搞反了极大层调用了极大层。解决初始化固定为int alpha -INF; int beta INF;。在递归入口加一行调试日志输出当前层的alpha和beta看它们是否在快速收敛。如果十几次搜索后α和β仍然保持初始值基本可以断定剪枝条件或者递归方向写错了。5.4 深度提一档响应时间暴涨几倍现象搜索深度从4调到6之后AI单步思考时间从几百毫秒涨到十几秒完全无法对弈。原因深度每加1博弈树规模大约乘以平均候选点数。如果候选点没有裁剪到位、评估函数每次全盘扫描时间膨胀就是灾难性的。还有一个隐蔽因素是编译模式Debug模式下递归开销巨大同样的深度耗时可能是Release的10倍以上。解决先确认候选点限制在2×2邻域胜负判定只看最后落子点。然后用迭代加深代替固定深度先搜2层再搜4层给整体调用一个时间上限超时就用上一层的计算结果。编译时使用Release模式并开启O2优化C的递归函数在这两个模式下的性能差距非常离谱。5.5 随机化之后bug难复现现象加了随机化落子之后AI有时候下得很好有时候明显抽风。想复现某一步异常时重开一局又走出了不同的棋没法稳定观察。原因随机种子没有做开关控制每次运行都不一样。调试时你看到的是一个黑匣子同样的局面AI可能给出完全不同的反应。解决把随机化做成可配置项。加一个config.h定义const bool RANDOMIZE true;和const int RANDOM_SEED 42;。调试时把RANDOMIZE关掉或固定种子复现问题调完再打开。我一般在main里只写if (RANDOMIZE) srand(time(nullptr)); else srand(RANDOM_SEED);这一行就够。6. 验证AI强度先手后手回归测试与调试日志技巧判断一个五子棋AI改动到底是变强了还是变弱了最直接的做法不是跟它下几局靠感觉判断而是跑一轮先手后手各20局的回归对弈。把AI放在先手位置固定种子连下20局记录胜负再换到后手位置再连下20局。改动之后对比这两组数据胜率提升才是真提升单局赢棋很可能是运气。我用这个方案踩过不少坑。有一次只改了评估函数里活三的权重跟AI下了三局觉得变强了结果回归测试一跑后手胜率掉了15个百分点——原因是权重调太高后AI过度追求活三忽略了冲四的直接杀着。从那以后我每次改完评估函数都会强制走一遍先手后手各20局的回归再决定要不要保留这次改动。这个习惯替我挡住了很多次看着变强实际变弱的翻车。另一个很实用的技巧是给搜索过程加日志开关。在alphabeta的入口做一个debug变量控制打印当前深度、候选点数量、剪枝触发次数、返回值。这样你能看到AI在某一层究竟剪掉了多少分支也能定位这一步AI为什么下在这里的推理过程。搜索的α-β值收敛轨迹其实比最终落子信息更有参考价值。这个项目的代码和报告都在压缩包里README里已经写清了文件路径和编译方式解压后按说明跑起来建议先把我说的这几个避坑点过一遍再动手调参。希望帮到你。本文还有配套的精品资源点击获取