C++五子棋AI实战：极大极小值与AlphaBeta剪枝详解

简介压缩包内是完整的C五子棋游戏项目以极大极小值算法配合AlphaBeta剪枝实现AI落子决策并配有前后端完整实现属于经导师指导后高分通过的课设/毕设项目。项目面向计算机相关专业学生可作为课程设计、期末大作业或毕业设计选题也适合想研究传统博弈树搜索与剪枝优化的开发者深入学习。压缩包共66个文件其中16个h头文件与14个cpp源文件覆盖游戏控制、棋盘逻辑、AI决策、服务器及视图层另有2个HTML、2个CSS、2个JS构成前端界面8个JSON记录配置数据6个PNG与4个GIF用于展示运行效果4个Markdown文档提供项目说明整体大小仅1.35MB。目前已有359人浏览学习。源码按功能模块分层游戏主程序、AI组件、棋盘、服务器和视图相互独立配合CMake构建文件与项目文档能快速搭建运行环境也便于围绕AI算法和局部模块进行二次开发与调试。1. 为什么五子棋AI还在用极大极小值AlphaBeta剪枝五子棋AI没必要一上来就上深度学习。用C手写一个基于极大极小值Minimax与AlphaBeta剪枝的传统搜索算法在15×15棋盘上跑到46层搜索已经足够压制多数业余玩家而且代码量比想象中少。很多C五子棋小游戏从一开始就走这个方案是因为五子棋每回合可落子位置有限评估函数写得太平也能靠额外一层搜索拉开差距。真正决定棋力上限的是评估表、走法排序和剪枝顺序这三样而不是框架复杂度。下面把搜索层拆开专注讲“极大极小值AlphaBeta剪枝”在C里怎么从公式变成能编译、能对弈的源码。2. 从博弈树到剪枝传统五子棋AI算法的两个核心组件2.1 极小极大值递推先假设对手总是最坏应对五子棋对局的本质是交替落子。站在当前回合这方的角度看自己落子后是对手落子对手总是会选择让自己收益最小的那一步再之后又轮到己方选择收益最大的分支。这个“一轮取最大、下一轮取最小”的交替递推就是极小极大值算法。搜索树里每一层对应一次落子树的深度就是向后看几步棋。int minimax(int depth, int player) { if (depth 0) return evaluate(player); // 叶子节点用静态评估函数打分 if (player AI) { int best -INF; for (auto [r, c] : gen_moves()) { board[r][c] player; best max(best, minimax(depth - 1, OPP)); board[r][c] EMPTY; } return best; } else { int best INF; for (auto [r, c] : gen_moves()) { board[r][c] player; best min(best, minimax(depth - 1, AI)); board[r][c] EMPTY; } return best; } }这段代码把“己方最大化、对手最小化”直接写成了两个分支。depth是剩余搜索层数player表示当前节点轮到谁落子evaluate返回当前局面对AI视角的估值正值表示AI优势负值表示对手优势。gen_moves生成所有合法空位这里先用全盘扫描后面会改成只在最近落子附近生成候选点。这个朴素版本的问题非常明显每一层都要展开全部空位15×15棋盘第4层就有接近几万个叶子节点评估函数稍有复杂度就会超时。极小极大值本身保证的是“在有限深度内找到理论最优解”但实际对局里时间预算根本不允许全展开所以必须有剪枝配合。2.2 AlphaBeta剪枝把“不用看的棋”砍掉AlphaBeta剪枝是在极小极大值框架上维护两个窗口值alpha表示AI方已知最好的分数下界beta表示对手方已知最差的分数上界。搜索每个分支时如果某个节点传回的值已经让这个窗口变得无效就立刻停止看剩余分支。核心判断是当beta alpha时当前节点剩下的分支无论怎么评估都不会被上层采纳。int alphabeta(int depth, int alpha, int beta, int player) { if (depth 0) return evaluate(player); for (auto [r, c] : gen_moves()) { board[r][c] player; int val -alphabeta(depth - 1, -beta, -alpha, OPP); board[r][c] EMPTY; if (val beta) return beta; // 对手不会再让步直接剪掉剩余分支 if (val alpha) alpha val; } return alpha; }这里用了一个常用的Negamax改写每个节点都对子节点返回值取负交替过程自然由符号完成省掉max/min两套分支同时窗口也要翻转。alpha从-INF开始beta从INF开始每层更新后窗口逐渐收紧。换成最直观的表述AI侧在抬升自己的最低收益对手侧在压低AI的最高收益两者相遇时后面的搜索没有意义了。剪枝效果取决于着法顺序。先搜到强手alpha抬升快后续大量弱手被剪掉如果先搜到弱手alpha长时间抬不上去剪枝就少。这就是为什么所有工程实现都特别看重走法排序。按理想顺序排序时AlphaBeta剪枝能让搜索量从O(W^D)降到约O(W^(D/2))也就是说同样的时间可以多看一倍深度。2.3 剪枝后的搜索深度对棋力的影响搜索深度不剪枝叶子节点数宽度20AlphaBeta剪枝理想叶子节点数2400约 394160,000约 799664,000,000约 15,999从这张表能看出AlphaBeta剪枝带来的不是“稍微快一点”而是数量级上的差距。第6层全展开需要看6400万个叶子带剪枝只需要约1.6万个节点评估函数按微秒算也能在一秒内完成。传统五子棋AI算法在本地机器上跑到6到8层完全是常规操作这也是它至今仍是多数五子棋源码首选方案的原因。有一点要特别说明剪枝不改变搜索结果只跳过那些“即使展开也改变不了上层决策”的分支。剪枝是否安全取决于alpha、beta窗口值传递是否正确常见错误是把return beta写成return alpha或者Negamax里忘记把窗口取负翻转。后面排查“AI突然变傻”时优先检查这两个位置。3. 用C实现五子棋评估与搜索源码怎么拆3.1 棋盘点位表示与候选着法生成实现五子棋源码时第一步是把棋盘建模做干净。常见做法是开一个比可见棋盘大两圈的二维数组避免后续四个方向扫描去处理边界溢出。AI侧用1表示对手侧用2表示空位用0。方向向量按横向、纵向、主对角线、副对角线四组排好扫描五连时直接复用。const int BOARD_SIZE 15; vectorvectorint board(BOARD_SIZE 2, vectorint(BOARD_SIZE 2, 0)); int dr[4] {0, 1, 1, -1}; int dc[4] {1, 0, 1, 1};候选着法生成不扫全盘。每回合只需检查最近一手上一步棋半径2范围内的空点因为真正会直接影响胜负的棋都离已有棋子不远。全盘扫描会引入大量“离战场太远”的落点即使剪枝能砍掉一部分排序带来的开销依然不值得。vectorpairint, int gen_moves(int last_r, int last_c) { vectorpairint, int moves; for (int r max(1, last_r - 2); r min(BOARD_SIZE, last_r 2); r) { for (int c max(1, last_c - 2); c min(BOARD_SIZE, last_c 2); c) { if (board[r][c] 0) moves.push_back({r, c}); } } return moves; }last_r、last_c是最新一手棋的坐标max、min用来夹紧边界。半径2覆盖了所有能形成活三、活四、冲四的局部区域这个参数不建议再扩大扩大到3后候选点数量翻倍剪枝压力的增速远大于棋力收益。开局前几步没有最近落子时可以固定返回棋盘中心附近的九个点。3.2 棋型评估函数得分表与方向扫描评估函数是传统五子棋AI算法的灵魂。搜索只负责“往后看几步”每一层的静态评估必须真正反映局部好坏。最实用的做法是按连续棋子数和两端开放状态打分比如活三、冲四、活四这些基础棋型。常见分值分配可以用一张表维护。连子情况两端状态分值五连任意1,000,000活四两端全空100,000冲四一端空10,000活三两端全空5,000眠三一端空1,000活二两端全空500扫描时以每个非空棋子为起点向四个方向单向延伸只统计“当前棋子在一条连子起始端”的情况避免同一条五连被重复计算。统计出连续同色棋子数后再看线段两端是空、边界还是异色棋查表加分。int evaluate(int ai_color) { int score 0; for (int r 1; r BOARD_SIZE; r) { for (int c 1; c BOARD_SIZE; c) { if (board[r][c] 0) continue; for (int d 0; d 4; d) { int pr r - dr[d], pc c - dc[d]; if (board[pr][pc] board[r][c]) continue; // 只统计连子起点 int cnt 1; int nr r dr[d], nc c dc[d]; while (board[nr][nc] board[r][c]) { cnt; nr dr[d]; nc dc[d]; } int open 0; if (board[nr][nc] 0) open; int br r - dr[d], bc c - dc[d]; if (board[br][bc] 0) open; int cur shape_score(cnt, open); score (board[r][c] ai_color) ? cur : -cur; } } } return score; }shape_score(cnt, open)按上一张表返回棋型分数。board[pr][pc] board[r][c]这个判断保证同一条连子只从起点算一次。返回值是对AI视角的分差AI方的棋型加上正值对手的棋型减去负值。这里有一个容易被忽略的细节对手的冲四、活三也必须完整计入否则搜索会低估对手威胁表现为防守端永远慢半拍。3.3 带AlphaBeta剪枝的极大极小值搜索函数把评估函数和候选着法生成接入搜索。工程实现里一般用Negamax写法并额外传一层“根节点”参数用来记录最佳落点。每次落子前先模拟放棋递归返回后撤销这个“试放再悔棋”的过程注意不要搞错坐标。int alphabeta(int depth, int alpha, int beta, int player, int last_r, int last_c) { if (depth 0) return evaluate(AI_COLOR); auto moves gen_moves(last_r, last_c); if (moves.empty()) return evaluate(AI_COLOR); // 简单启发式排序优先搜靠近棋盘中心的点剪枝效率更高 sort(moves.begin(), moves.end(), [](auto a, auto b) { auto dist_a abs(a.first - 8) abs(a.second - 8); auto dist_b abs(b.first - 8) abs(b.second - 8); return dist_a dist_b; }); int best -INF; for (auto [r, c] : moves) { board[r][c] player; int val -alphabeta(depth - 1, -beta, -alpha, OPP, r, c); board[r][c] 0; if (val best) best val; if (val alpha) alpha val; if (alpha beta) break; // 剪枝 } return best; }player是当前节点落子方AI固定是1对手固定是2。last_r、last_c传入刚落下的那手棋供下一层gen_moves就近生成候选点。排序先按到棋盘中心的曼哈顿距离排开局和中盘都够用如果想让排序更准可以在排序前先对每个候选点跑一次快速评估按评估值降序排。alpha beta触发剪枝后直接break这里和理论部分描述的beta alpha是完全一致的判断。需要留意的是递归里-alphabeta的写法把窗口翻转了意味着上层传下来的alpha、beta也必须跟着取负初学者最容易在这里写成alphabeta(depth - 1, alpha, beta, OPP)结果就是剪枝失效搜索变慢且行为诡异。3.4 迭代加深几层搜索由时间预算决定固定深度搜索有两个问题一是不知道自己这步会不会超时二是搜完一层后很难利用上一层的结果。迭代加深从第1层开始逐层加深搜索每搜完一层记录最佳着法并检查时间超时后直接返回上一层结果。Move iterative_search(int time_limit_ms) { auto start chrono::steady_clock::now(); Move best_move {7, 7}; for (int depth 1; depth MAX_DEPTH; depth) { int alpha -INF, beta INF; auto moves gen_moves(last_r, last_c); for (auto [r, c] : moves) { board[r][c] AI_COLOR; int val -alphabeta(depth - 1, -beta, -alpha, OPP, r, c); board[r][c] 0; if (val alpha) { alpha val; best_move {r, c}; } } auto elapsed chrono::duration_castchrono::milliseconds( chrono::steady_clock::now() - start).count(); if (elapsed time_limit_ms) break; } return best_move; }MAX_DEPTH建议设8到10实际能跑到几层由time_limit_ms决定。迭代加深的真正收益是每次加深后的最佳着法可以用于下一层的着法排序把上一层找到的强手放到候选列表最前面剪枝效率会显著提升。时间控制在实时棋类里尤其重要哪怕只多出一层搜索也要保证不卡顿。7, 7这种默认值只在棋盘全空或完全没搜到任何候选时兜底使用。4. C五子棋的前端与后端通信协议与编译参数4.1 前后端职责拆分与两套可选前端标题里写“含前端后端”对应到源码结构上后端是C的搜索与局面管理前端负责交互展示。最简单的形态是后端核心库加一个控制台前端Windows环境下也可以接一个原生窗口前端或者用SDL做简单图形界面。控制台前端对调试最友好因为落子坐标、搜索深度、耗时都能直接打印出来比对。前后端拆分的核心原则是后端不知道鼠标和窗口坐标系只接收“某方在某个坐标落子”指令返回“AI在哪个坐标落子”。这样后端可以独立测试前端也可以随时换成其他语言或框架。很多C五子棋源码出错不在搜索本身而是把界面坐标和棋盘索引混在一起导致横竖方向颠倒。4.2 回合制文本协议一次落子的完整往返推荐用JSON行协议方便未来前端换成网页版也不用改后端。每行一个JSON对象后端程序从标准输入读取指令解析后执行搜索向标准输出回写结果。方向内容示例前端到后端玩家落子坐标{type:move,x:7,y:7}后端到前端AI落子坐标与搜索信息{type:move,x:11,y:8,score:85,depth:6,time_ms:1142}前端到后端重新开局{type:reset}后端到前端胜负结果{type:win,winner:AI}x、y是0到14的棋盘索引和后端数组的下标一一对应。返回的score是根节点的评估值depth是实际搜到的层数time_ms是耗时。调试时把这三项打到日志里能直观看到每一层搜索的质量和耗时。协议解析用C标准库实现即可不需要引入第三方JSON库五子棋这种简单结构手写解析最可控。4.3 编译运行与限时参数搜索性能完全依赖优化选项Debug模式跑出的结果没有参考价值。g -O2 -stdc17 main.cpp -o gomoku_ai ./gomoku_ai --depth6 --timeout3-O2对递归搜索的循环展开和函数内联提升明显实测通常比默认优化快一倍以上。--depth指定最大搜索深度--timeout指定单步耗时上限。发布给用户时建议固定为--timeout2既保证手感也让棋力随机器性能自然浮动。如果源码里同时使用了多线程需要额外加-pthread后面讲置换表时也会用到。5. 实战用置换表和手顺优化把剪枝效率再提一档5.1 Zobrist哈希与置换表缓存同一局面在搜索树里会通过不同路径到达尤其是有大量对称分支时。置换表用Zobrist哈希把“棋盘局面”映射成64位键记录该局面在某深度的搜索结果。搜索进入节点前先查表评估过就直接返回分数能显著减少重复计算。uint64_t zobrist[BOARD_SIZE 2][BOARD_SIZE 2][3]; void init_zobrist() { mt19937_64 rng(2024); for (int r 1; r BOARD_SIZE; r) for (int c 1; c BOARD_SIZE; c) for (int p 1; p 2; p) zobrist[r][c][p] rng(); } uint64_t hash_board() { uint64_t h 0; for (int r 1; r BOARD_SIZE; r) for (int c 1; c BOARD_SIZE; c) if (board[r][c] ! 0) h ^ zobrist[r][c][board[r][c]]; return h; }init_zobrist为每个坐标、每个颜色随机生成一个64位数落子和悔棋时只需要异或对应的键不需要每次重新扫描全盘。查表只在同一深度或更深缓存时有效深度不足的记录不能直接拿来用否则会让AI错误相信一个更浅的评估。置换表本身不改变棋力上限但它能把重复搜索砍掉一半以上实机棋力提升非常明显。5.2 验证棋力一行配置的随机对局测试修改--depth参数分别设为4、5、6让AI和固定深度为4的旧版本对弈50局记录胜率。胜率有明显跳升说明评估函数和剪枝逻辑正确若深度增加后胜率反而下降优先怀疑置换表深度校验出错或剪枝窗口写错。每局把落子列表导出成文本用二分法定位第一步导致局势崩盘的落点。5.3 手顺微调候选点排序和窗口边界候选点排序不要只按离中心距离可以给每个候选点套一个快速分数模拟落子后跑一次简化评估分数高的分支先搜。搜索窗口建议用[alpha, beta]作为迭代加深的上层传参根节点用(-INF, INF)内层不要随意缩窄窗口窗口一旦设置错误会直接导致漏算最优解。最后检查一遍gen_moves里半径2内是否有空位可生成如果没有就返回中心点这个兜底逻辑能避免空列表让搜索直接返回垃圾值。本文还有配套的精品资源点击获取