简介面向毕业设计场景的智能人机博弈五子棋完整源码项目适合想研究贪心策略直接搜索算法与极大极小博弈树算法在游戏AI中落地实践的开发者。项目将贪心策略在开局和中盘快速占位的优势与极大极小博弈树对后续局势的深度推演相结合针对五子棋中的活三、冲四等棋型进行局面评估并借助预设的开局、中局、残局测试场景帮助读者对比不同算法的决策差异。压缩包共72个文件大小约58MB以Java源码和编译后的class文件为核心辅以图片、音频资源以及设计文档、类调用关系图等说明材料方便按目录检索和二次开发。目前已有285人学习下载可作为毕业设计参考、AI博弈算法入门或五子棋开发练习的完整素材提供从算法原理、代码实现到界面资源替换的清晰路径。1. 人机五子棋的决策困局为什么贪心搜索和博弈树要同时出现开局才十来手棋盘上棋子还没连成片AI如果只按当前局面的局部利益去落子很容易被对手的一手跳活三牵进被动防守反过来如果让AI把整个15路棋盘的所有空位全部放进搜索树深度一旦超过4层普通笔记本上的计算量就能压住帧率一步想三五秒都算不完。这是多数人第一次写五子棋AI都会撞上的墙也是这套源码里真正要解决的核心问题。这套毕业设计源码把贪心策略直接搜索算法和极大极小博弈树算法焊在一起用先用贪心快速扫出少数高潜力落点再对这几个点做有限深度的对抗搜索。贪心把视野收窄博弈树把眼光放远两者配合后AI才能在单步耗时可控的情况下想清楚后面几步。文章后面会结合src目录和gobang_test预设场景讲透实现细节、参数设置和调参顺序适合正在做机器博弈课程设计、毕业设计或者想把手写五子棋AI再调强一截的开发者参考。2. 决策骨架贪心直接搜索与极大极小搜索的融合实现2.1 贪心直接搜索从全盘扫描到候选点压缩五子棋棋盘上真正值得考虑的空位并不多绝大多数落子都会发生在已有棋子周围一到两格以内。离棋盘上所有棋子都超过两格的“真空点”要么是开局抢中心要么是后期彻底无关的废点。所以贪心阶段不建议从头到尾遍历全部225个空位去做评分而是先做一个“附近点收集器”扫描棋盘上已经落下的棋子把每个棋子周围半径两格以内的空点收集进std::vectorPosition candidates。这个步骤能把决策空间从两百多个点压缩到几十个点是后面一切搜索的性能前提。收集完候选点后按贪心评分排序目的是把真正的重点排进前N名。贪心评分不需要很精确但一定要快常见做法是对每个候选点在横、竖、两条斜线四个方向上统计连续同色棋子的数量再结合中心距离做轻微加权。下面这段代码就是贪心评分的最小实现只扫描四个方向计算量非常小。struct Position { int row, col; }; static const int dx[4] {1, 0, 1, -1}; static const int dy[4] {0, 1, 1, 1}; // 贪心评分只统计pos四个方向上的己方连续棋子和空位 int greedyScore(const Board bd, const Position pos, PieceType me) { if (bd.get(pos) ! PIECE_EMPTY) return -9999; int score 0; for (int dir 0; dir 4; dir) { int cnt 1; for (int step 1; step 5; step) { Position p{pos.row dx[dir] * step, pos.col dy[dir] * step}; if (bd.inBoard(p) bd.get(p) me) cnt; else break; } for (int step 1; step 5; step) { Position p{pos.row - dx[dir] * step, pos.col - dy[dir] * step}; if (bd.inBoard(p) bd.get(p) me) cnt; else break; } score cnt * cnt; // 连续子数做平方放大 } return score; }逻辑说明cnt是当前点在某方向上与己方棋子连成串的总长度cnt * cnt让更长连线的权重远高于短连线。比如连续三子得9分连续四子得16分差距被平方放大AI会对形成长连的落点更敏感。这里没有考虑端点的阻挡状态因为贪心阶段只求排序快真正的棋型评估留到博弈树的叶子节点去做。排序之后取前CANDIDATE_LIMIT个候选点参与后续搜索。这个值我一般设在10因为搜索宽度越大博弈树的分支因子就越大。太小可能漏掉最优手太大则深度上不去。实测在普通笔记本上候选点10个、搜索深度4层单步耗时能保持在0.3秒左右对局体验已经可以接受。2.2 负极大值搜索用一层函数代替双人递归极大极小博弈树的标准写法要区分maxPlayer和minPlayer两层递归代码重复度比较高。源码里实际用的是负极大值Negamax写法核心思想是当前节点返回的分数始终站在当前走子一方视角递归调用时对结果取负号这样就自动完成了视角切换。胜负判断放在递归入口处先看这一步是否导致局面结束再决定是否进入深度展开。// 博弈树搜索入口depth 表示还要往下看几层 int negamax(Board bd, int depth, int alpha, int beta, PieceType player) { Position winPos; PieceType winner bd.checkWinner(); if (winner player) return 100000 depth; // 早赢加分鼓励短胜 if (winner opponent(player)) return -100000 - depth; if (depth 0) return evaluate(bd, player); vectorPosition cands generateCandidates(bd, player); sortCandidatesByGreedy(bd, cands, player); // 复用贪心排序结果 if (cands.size() CANDIDATE_LIMIT) { cands.resize(CANDIDATE_LIMIT); } int best -INF; for (auto p : cands) { bd.move(p, player); int val -negamax(bd, depth - 1, -beta, -alpha, opponent(player)); bd.undo(p); if (val best) best val; if (val alpha) alpha val; if (alpha beta) break; // alpha-beta 剪枝 } return best; }参数说明alpha初始取负无穷beta取正无穷递归过程中通过-beta, -alpha翻转传递。100000 depth与-100000 - depth的写法有个细节同样是赢棋搜索路径越短得分越高这样AI会在多个必胜分支里选择最快赢棋的那一条避免无意义绕路。更关键的是递归开始时必须调用checkWinner()否则深度为0时可能把已经五连的盘面当叶子节点用评估函数去算一个已经结束的棋局导致胜负判断被掩盖。剪枝效率直接和cands的排序质量挂钩。如果每次都能把最有可能让对手难受的走法排在前面alpha-beta剪枝会剪掉大量无意义分支如果走法顺序杂乱搜索复杂度会退化成全展开。所以这里的sortCandidatesByGreedy不是简单的排列而是把贪心评分和历史搜索经验混合在一起下一章会具体展开棋型评估。2.3 融合流程先粗选后细想两个模块在src里的调度顺序很清晰。棋盘每轮轮到AI时先调用GreedySearch::findCandidateMoves()获取候选点集合随后把候选点交给MiniMaxTree::search()做搜索。搜索内部也不是每层都全盘遍历而是一路复用候选生成和贪心排序只是每层都会截断到指定宽度。这样设计让AI既不会在开局就漫无目的地往边角乱跑也不会在中盘对一个明显没棋的区域投入大量计算。参数名典型值作用CANDIDATE_LIMIT10每层递归最多展开的候选点数控制搜索宽度SEARCH_DEPTH4表示AI能向前预测的回合数增加1层耗时约3-5倍NEARBY_RADIUS2贪心搜索收集周边空点的半径范围过大会让候选点暴涨WIN_SCORE100000胜利基准分必须大于任意评估函数输出调参时不要只盯搜索深度。我一般先把NEARBY_RADIUS固定为2因为半径是1时AI对跳活三这类隔空棋形完全无感半径是3则候选点数量会从几十涨到一两百CANDIDATE_LIMIT的截断作用被削弱。接下来调CANDIDATE_LIMIT从8逐次加到12观察单步耗时稳定之后再尝试把SEARCH_DEPTH从4提到5。按这个顺序来AI棋力的提升是有梯度的不会出现一步卡死。另外要注意候选点为空的兜底情况。如果棋盘刚开局还没有任何棋子或某个区域被填满导致没有空点生成函数必须显式返回棋盘中心或周围随机点否则搜索会进入死循环。常见的做法是开局前两手直接走天元或者以离中心最近的空位作为兜底。3. 棋型评估与分值设计让AI看懂“活三”和“死四”3.1 棋型分类为什么不能只看连续子数如果评估函数只统计连续同色棋子的个数AI会分不清活形和眠形。同样是三子连在一起两边都没堵的活三下一步就能变成活四一端被堵死的眠三只要对手再堵住另一头就直接废掉。这两种棋型在实战里的价值差着一个量级评估函数必须把它们区分开。下面这套基础分值表在绝大多数五子棋AI里都适用源码里也是按这个思路落到evaluate.cpp里的。棋型方向占位分值五连已有5子1000000活四4子两端均空100000冲四4子一端被堵10000活三3子两端均空5000眠三3子一端被堵1000活二2子两端均空500眠二2子一端被堵100注意活四分值是十万而搜索树里的胜利分是百万级。这样设置是故意的搜索层如果已经能看到五连直接返回胜利分不再依赖评估函数评估函数只负责处理那些“胜负未定”的叶子节点。所以不需要把棋型分数抬到和胜负一样高保持大小比例关系就足够让AI在不同候选点里做选择。除了活三、冲四这些静态棋型实战里还需要处理跳子情况比如“空一格的两连”。这种棋型在扫描窗口时不能只判断连续棋子否则跳活三会被漏判。典型的做法是把五格窗口视为一个基本单元分析窗口内黑白子的排列组合用枚举方式直接映射到上表对应的棋型。3.2 评估函数实现四次方向扫描做一次“抹平重复”写评估函数最容易踩的坑是按四个方向分别扫描结果同一个活三被横竖两条方向各计数一次AI误以为形成了双活三实际并没有。为了避免重复计分需要把五个格子当成一个窗口按滑动窗口的方式逐点检查并且把连续棋子的连通块聚合起来统一算分。int evaluateForPlayer(const Board bd, PieceType me) { int score 0; static const int dirs[4][2] {{0,1},{1,0},{1,1},{1,-1}}; for (int r 0; r BOARD_SIZE; r) { for (int c 0; c BOARD_SIZE; c) { for (int d 0; d 4; d) { if (bd.windowInBoard(r, c, dirs[d])) { Pattern p analyzeWindow(bd, r, c, dirs[d]); if (p.owner me) score PATTERN_SCORE[p.kind]; else if (p.owner opponentOf(me)) score - PATTERN_SCORE[p.kind]; } } } } return score; }这段代码的核心是analyzeWindow它检查每个五格窗口里的棋子排列返回Pattern结构体。Pattern.kind就是上表里的棋型枚举PATTERN_SCORE是对应的分值。真正工程化的实现里会对棋盘上每个棋子生成一个连通块ID最终以块为单位统计棋型而不是以方向为单位累加。这样做能避免同一组棋子在相邻窗口里被重复识别。另外要特别注意对手棋型的扣分逻辑。很多初版AI只给自己加分给对手的棋子只做“挡路”处理这会让AI只想着进攻不堵对手双三形成“互相各下一条线”的局面。必须在评估函数里扣掉对方的威胁分数最简单的做法是对方棋型分乘以一个大于1的系数再减去让AI感知到不防守就可能被绝杀。实际对局里冲四的威胁通常比己方活三更急迫所以很多源码里会对对方冲四额外加权。3.3 用 gobang_test 预设场景校验评估顺序gobang_test是源码里一组预设局面文件覆盖开局、中局和残局每个文件里除了棋盘坐标还标注了当前轮次和期望走法。它不只是一个给玩家玩的题库更是评估函数的回归测试集。调试AI时我会写一个验证入口每次修改评估函数后把gobang_test里的局面逐个载入让AI算出最佳位置再和文件里标注的正解比对。# 常见验证方式把 gobang_test 当入参交给评测入口 ./gobang_game --testgobang_test --timeout5运行后终端会打印每个场景的搜索结果比如case_02: expect(7,7) got(7,7) PASS这样能快速看出哪些局面判断失败。对于失败案例打开设计文档里的“五子棋程序类调用关系图.doc”沿着搜索调用链检查是候选点没有包含正解还是评估函数把正解的分数压低了。这种验证方式比手动打开游戏一局一局试错高效得多改完棋型分值后只跑一遍测试集就能知道整体影响。这里有个容易被忽略的问题单纯跑通测试集只能说明评估函数没有倒退不能说明棋力变强。想判断棋力变化要把调整前后两版AI放进自对弈模式跑几十局统计胜率。这一步在生产里非常有价值但很多课程设计不会做只在测试集上比正确率是不够的。4. 源码编译、运行与调参从src跑通第一局人机对战4.1 源码结构先弄明白src里拆了哪些模块解压11444738175025182.zip后会看到src、gobang_test、README.md、设计文档.doc和五子棋程序类调用关系图.doc。src目录里一般按职责拆成几个子目录这套源码中比较典型的分层如下表所示。路径作用src/board棋盘映射、落子/悔棋、胜负检测src/search贪心候选生成、负极大值搜索、置换表src/evaluate棋型定义、窗口扫描、分值表gobang_test预设开局/中局/残局场景用于回归测试类的调用顺序是GameLoop::onPlayerMove()收到玩家落子后通知AIPlayer::think()think()先调GreedySearch::findCandidates()把结果传给MiniMaxTree::search()。这份调用关系在设计文档.doc里画得很清楚类数量不多核心逻辑围绕Board、GreedySearch、MiniMaxTree、Evaluator四个类展开。我建议先把README.md里的构建说明看一遍确认依赖项和编译方式再动代码。4.2 编译与运行命令源码如果没有提供现成的Makefile直接用g手动编译是常见的做法。需要确保src目录下所有.cpp文件都参与链接缺一个就会出现undefined reference错误。下面这条命令把main.cpp和src/*.cpp一起编译成gobang_game可执行文件。g -stdc14 -O2 main.cpp src/*.cpp -I src -o gobang_game ./gobang_game --modehuman-vs-ai运行参数说明--modehuman-vs-ai是标准的人机对战模式也可以改成--modeself-play让AI自己左右互搏用于测试不同参数配置下的胜率变化。-O2必须加搜索算法对性能极度敏感不开优化的话深度4层也可能卡到一秒以上。如果编译时遇到undefined reference to Board::makeMove大概率是src下有源文件没被链接进来把src/*.cpp展开成具体文件名列表重试即可。4.3 常见异常和边界处理人机对战调试中最常遇到三类问题。第一AI回传出非法坐标这通常是候选点生成时没有过滤掉已经被棋子占用的格子导致搜索阶段bd.move(p, player)覆盖了已有棋子。第二胜利检测滞后已经出现五连但AI还在继续搜索这种多半是checkWinner()只检查了落子位置周围的四个方向而副对角线方向越界。我的经验是把所有边界判断收敛到inBoard()函数里任何方向遍历前先问一次能避免大半越界问题。第三评估函数重复计分导致AI误判棋型。同一个活三如果因为方向扫描重复计算会被识别成双活三AI以为自己必胜实际走一步才发现根本连不成四。解决办法在前面说过按连通块ID聚合棋型不按方向计数。调参顺序也很重要。先在config.h里把CANDIDATE_LIMIT从8提升到12观察单步耗时如果稳定在1秒内再把SEARCH_DEPTH从4提升到5。不要一开始就盲目加深搜索层数搜索层数每增加1层计算量会膨胀数倍很多同学的电脑就是在这一步卡死的。5. 进阶技巧用走法排序和置换表把搜索深度再推一层5.1 走法排序把最大威胁放最前面剪枝效率最直接alpha-beta 剪枝的效率和走法顺序强相关。最理想的情况是每层搜索第一个走法就是最优解后续走法全被剪掉复杂度接近O(b^(d/2))比暴力搜索高很多。单纯靠greedyScore排序只能保证局部优先对重复出现的类似局面帮助不大。更有效的做法是引入历史启发表搜索过程中一旦某个落子在某层让alpha值提高就给这个位置累加一个奖励值后续节点排序时把奖励值加到贪心评分上。// 在负极大值搜索中对搜索路径上证明有效的落子更新历史表 for (auto pos : searchedMoves) { history[pos.row][pos.col] (1 depth); } sortCandidates(cands, player, history);这里的history表是一个15x15的整数数组1 depth给浅层搜索的落子更高权重理由是浅层节点被搜索频率高更新价值更有代表性。把历史启发表和贪心评分结合后走法顺序会越来越接近“最优优先”剪枝率明显上升原本只能稳定在深度4的引擎在相同耗时下能多跑半层搜索。5.2 置换表让重复局面不用第二次计算搜索过程中经常出现同一局面通过不同落子顺序到达的情况。比如先下(5,5)再下(6,6)和先下(6,6)再下(5,5)最终棋盘形态完全一样。用置换表缓存这些重复局面能直接跳过重复搜索。常见的实现是用Zobrist哈希给棋盘的每个格子生成随机数黑白状态各一个落子和悔棋时通过异或运算进出哈希值。struct TTEntry { int depth; int bound; // EXACT / LOWER / UPPER int score; }; std::unordered_mapuint64_t, TTEntry transTable;要注意存储的depth和搜索边界类型必须一起保存。如果缓存的是深度2的搜索结果却直接复用在深度5的搜索里会丢失后续层数的信息导致AI看漏杀棋。我一般对命中条目判断一下只有缓存深度不小于当前搜索需求时才允许直接取用否则丢弃。置换表内存不需要很大预留2MB就能显著提升4层以上搜索的命中率尤其是对同一局面反复做验证时很有帮助。把这两项技巧加上之后SEARCH_DEPTH从4提到5单步耗时通常只增加30%左右而不是翻倍很多在4层看不清的双三连招就能提前算到AI的对局水平会有肉眼可见的提升。本文还有配套的精品资源点击获取