简介一份基于C和Qt实现的五子棋博弈游戏项目集合极大极小搜索与α-β剪枝算法并附有设计报告。项目源码逻辑清晰包含评估函数、走法生成、搜索线程等模块适合人工智能、计算机、自动化等专业学生用于课程设计或毕业设计也可作为博弈算法与Qt界面开发的学习参考。压缩包共145个文件大小约7.26MB涵盖cpp/h源代码、ui/qml界面文件、png/jpg图标资源、exe可执行程序、docx设计报告以及pro/vcxproj工程文件能完整还原项目构建与运行环境。目前已有65人学习下载适合快速掌握极大极小搜索与剪枝在五子棋工程中的落地方式。资源提供可运行程序与完整设计文档既可直接演示对战效果也便于在此基础上扩展更强AI策略或重构交互界面用作课程设计、毕业设计及人工智能算法实践的高性价比素材。1. 五子棋AI不靠棋谱靠搜索C和Qt这个组合为什么值得做很多学完C和Qt的开发者想做个「有意思但不复杂」的小项目会想到贪吃蛇或者俄罗斯方块但这两个做完就完了没什么可深挖的。五子棋博弈游戏就不一样它看起来只是个C小游戏真正动手才发现核心不是界面而是让AI会下棋的极大极小搜索和剪枝算法。这个标题里的项目方案是用Qt把15x15棋盘画出来、用C实现搜索算法、再配一份设计报告把思路讲清楚一整套下来数据结构、递归、STL、界面事件、算法分析全练到了。适合已经能写C类和STL容器、想完整跑通一个「带AI对手」项目的人。反直觉的地方在于AI不需要背任何棋谱也不需要一堆if-else规则只靠「把未来几步算清楚每次选对自己最有利的」这一招就能在棋盘上和你打得有来有回。2. 棋盘与界面先行用C和Qt搭出可落子的五子棋框架AI再聪明也得先有一块能落子的棋盘。这一章先把「棋盘的C数据表示」和「Qt绘图与鼠标交互」两条腿搭起来。很多人在这个项目上翻车不是因为搜索算法写不出来而是棋盘数据结构一开始就没设计好后面评估函数和剪枝越写越拧巴。2.1 棋盘数据结构选型二维数组为什么比位棋盘更适合五子棋常见做法是用15x15的二维数组表示棋盘每个格子取值0、1、2分别表示空、黑子、白子。网上也有用位棋盘方案的人把整盘棋压成几个uint64_t用位运算判断落子方向。位棋盘在国际象棋里很流行但五子棋棋盘只有225个格子评估函数需要频繁扫描横向、纵向、两条斜线方向的连续棋型二维数组直接索引比位运算直观得多调试时一眼就能看出坐标落在哪里。对初学者来说选二维数组不是妥协是性价比最高的选择。C实现上我一般会用std::vectorstd::vector 而不是原生二维数组。原生数组做类成员时要么写死15这个常量要么用指针手动new和delete拷贝和赋值还要自己处理深拷贝一不留神就是指针悬空。std::vector自带拷贝语义初始化也方便。Player用enum class而不是int是为了让代码自解释避免把0、1、2传错// Board.h 五子棋核心棋盘表示 #pragma once #include vector enum class Player : int { None 0, White 1, Black 2 }; struct Move { int row; int col; Move(int r, int c) : row(r), col(c) {} }; class Board { public: explicit Board() { m_board.assign(15, std::vectorPlayer(15, Player::None)); } Player stoneAt(int row, int col) const { return m_board[row][col]; } void setStone(const Move m, Player p) { m_board[m.row][m.col] p; } bool inBoard(int row, int col) const { return row 0 row 15 col 0 col 15; } private: std::vectorstd::vectorPlayer m_board; };这段代码的核心是让Board只负责「棋盘长什么样」不关心规则和AI。setStone是纯写入stoneAt是纯读取inBoard做边界检查。设计成这样之后后面写胜负判定、评估函数、搜索算法时都只用这三个接口不用反复接触内部存储结构。注意Player枚举指定了底层类型int这样以后想序列化棋盘或做Zobrist哈希时可以直接取整数值。这里有一个容易忽略的C细节如果你在Player里定义了None0那么vector初始化后默认就是None不用再写循环清零。class Board的构造函数里assign一次就够了。我见过有人在构造函数里用双重for循环逐个格子设值代码量翻倍还容易漏掉边界其实assign一行就能解决。2.2 Qt界面绘制与落子交互QPainter画棋盘、mousePressEvent换算格子棋盘数据模型有了接下来要让玩家能看到棋盘、能点鼠标落子。Qt做这种棋类界面最常见方案是写一个继承自QWidget的BoardWidget重写paintEvent画网格和棋子重写mousePressEvent把鼠标坐标换算成棋盘行列号。QGraphicsView那套对五子棋来说偏重QWidget加QPainter足够代码也更好懂。绘制时我会设置两个关键参数格子边长cell和棋盘边距margin。cell决定棋盘在窗口里的缩放margin保证最外圈棋子和窗口边缘之间有一定留白。下面的代码是paintEvent的核心画线用的是drawLine画棋子用的是带渐变的drawEllipse渐变能让棋子看起来有立体感而不是一个扁平圆点// BoardWidget.cpp 棋盘绘制与鼠标交互 #include QPainter #include QMouseEvent void BoardWidget::paintEvent(QPaintEvent*) { QPainter painter(this); painter.setRenderHint(QPainter::Antialiasing, true); const int margin 24; // 棋盘外边缘留白 const int cell 36; // 每个格子的像素宽度 // 画15x15网格线 for (int i 0; i 15; i) { painter.drawLine(margin i * cell, margin, margin i * cell, margin 14 * cell); painter.drawLine(margin, margin i * cell, margin 14 * cell, margin i * cell); } // 画棋子 for (int r 0; r 15; r) for (int c 0; c 15; c) if (m_board-stoneAt(r, c) ! Player::None) drawStone(painter, r, c); } void BoardWidget::drawStone(QPainter painter, int row, int col) { const int margin 24, cell 36; QPointF center(margin col * cell, margin row * cell); QRadialGradient grad(center, cell / 2.0); bool isWhite (m_board-stoneAt(row, col) Player::White); grad.setColorAt(0.0, isWhite ? QColor(240, 240, 240) : QColor(60, 60, 60)); grad.setColorAt(1.0, isWhite ? QColor(200, 200, 200) : QColor(10, 10, 10)); painter.setBrush(grad); painter.setPen(Qt::NoPen); painter.drawEllipse(center, cell * 0.42, cell * 0.42); }网格线用drawLine画15条横线和15条竖线棋子的半径取cell * 0.42而不是0.5是为了让相邻棋子之间留一条细缝棋盘看起来更透气。QRadialGradient的center颜色比边缘亮黑白棋子都能有「鼓起来」的视觉效果。鼠标落子部分要注意坐标换算的取整问题。如果鼠标点在两个格子中线上用int强转会直接截断小数导致棋子往左上偏一格。正确做法是用qRound做四舍五入同时必须先减margin再除以cell否则靠近边缘时会算错void BoardWidget::mousePressEvent(QMouseEvent* e) { const int margin 24, cell 36; int col qRound((e-position().x() - margin) / cell); int row qRound((e-position().y() - margin) / cell); if (!m_board-inBoard(row, col)) return; if (m_board-stoneAt(row, col) ! Player::None) return; emit humanPlaced(Move(row, col)); // 交由上层逻辑决定谁落子 }注意这里用的是e-position().x()这是Qt6的写法。如果你在Qt5上跑老代码要改成e-pos().x()。很多人把这个项目从Qt5工程搬到Qt6时编译报错就错在这一行。鼠标事件只负责「用户点了哪个格子」这一个信息具体是玩家落子还是AI落子由MainWindow里的信号槽连接决定。把界面事件和业务逻辑拆开后面接AI时不用再改这个类。到这里双人模式已经能跑了点击棋盘界面上出现棋子。下一步把AI接进来之前先要把搜索算法想清楚因为评估函数的写法直接决定AI的下棋风格。3. 极大极小搜索落地评估函数、搜索树与胜负判定五子棋AI的核心思想不复杂Alpha落子后Beta会选对他自己最有利的应对Alpha要做的是在这一步的「候选落子集合」里找到那个「无论Beta怎么应对最终局面都对我最有利」的位置。用递归一层层往下推就叫极大极小搜索。3.1 评估函数为什么说五子棋AI的「棋感」是一堆权重极大极小搜索需要在一个局面给出「这个局面到底谁占优」的分数这个打分函数叫评估函数。五子棋不像象棋可以用子力价值直接加减因为每个棋子的价值取决于它跟旁边棋子的配合程度。常见做法是对每个棋型单独打分一手棋同时形成活三和冲四的潜力极大而两个孤子方向相悖几乎等于零分。评估函数的核心流程是以某个空位为圆心向横、竖、主对角线、副对角线四个方向各扫描一段统计连子数和两端是否被堵把棋型映射成分数。棋型和分数的对应关系是一个「参数表」调起来更像炼丹不同人写的权重差别很大棋型分数说明五连1000000已经赢棋分数给到天花板活四100000两端都开放对手怎么堵都堵不住冲四50000一端被堵只能单向堵威胁稍小活三10000两端开放的三连下一步可变活四眠三1000一端被堵被强制堵一手活二500有发展潜力但离赢棋还远实现时有一条关键约束对手的棋型也要计分最后返回值用「我方总分数减对手总分数」。如果只算自己的棋型不防守AI会眼睁睁看着对手五连。下面的代码是一个简化版的方向扫描实际项目里还会处理跳子等变体但骨架是稳定的// Evaluator.cpp 评估某个落子位置的四方向棋型分数 #include vector #include Board.h int evaluatorScore( const std::vectorPlayer line, Player me, Player opp) { int meCount 0; int oppCount 0; bool openA (line.front() Player::None); // 线段左端是否开放 bool openB (line.back() Player::None); // 线段右端是否开放 for (Player p : line) { if (p me) meCount; else if (p opp) oppCount; } if (oppCount 0) return 0; // 中间夹着对方子不算有效棋型 if (meCount 5) return 1000000; // 五连 if (meCount 4 openA openB) return 100000; if (meCount 4) return 50000; // 一端被堵则为冲四 if (meCount 3 openA openB) return 10000; if (meCount 3) return 1000; // 眠三 if (meCount 2 openA openB) return 500; return 0; }这段代码的输入line是一条长度为7的切片中间位置是正要评估的空位两侧向两个方向各外扩3格。openA和openB判断这条线段两侧是不是空位如果遇到对手棋子或者棋盘边界就认为被堵住。注意「夹着对方子」的直接返回0因为这个棋型不可能通过继续落子变成五连打分只会干扰搜索顺序。参数说明meCount 5的分数要设成1000000级别的「绝对优势」保证搜索到必赢局时不会因为其他分支的微小利益而改选活三和眠三的差距是10倍因为活三下一步就能变活四而眠三基本被压死。不同权重会让AI产生不同风格活三权重越高AI越激进冲四权重越高AI越喜欢做杀棋前的铺垫。这是这个项目里最值得反复调的「玄学区域」每人调出来的手感都不一样。3.2 极大极小递归从叶节点回溯把胜负算到4步之后评估函数只是给局面打分真正决定落子的是搜索树。整个搜索树从当前棋盘状态出发AI在奇数层轮到AI走选分数最大的孩子对手在偶数层选分数最小的孩子。递归到叶子节点到达设定搜索深度时用评估函数给终局局面打分。打分逐层回溯根节点取得的分就是当前所有候选落子中「对未来最有利」的一手。五子棋搜索树比想象中大棋盘225个空位如果每个节点都试一遍4层搜索的节点数是225的四次方等于25亿这在一秒内跑不完。所以只能裁剪候选点只有距离已有棋子最近的空位才值得搜索离所有棋子两格以外的点走下对当前局势几乎无影响。常见做法是只保留「已有棋子周围两格内」的空位候选点数量从225降到二三十个。// SearchEngine.cpp 极大极小搜索骨架 #include algorithm #include vector #include Board.h int minimax( Board board, int depth, Player cur, Player aiPlayer, Player humanPlayer) { // 如果上一步已经分出胜负直接返回胜负分不再继续展开 int winScore board.checkWinLast(); if (winScore ! 0) return winScore; if (depth 0) return evaluateBoard(board, aiPlayer, humanPlayer); std::vectorMove moves generateCandidateMoves(board); // 已有棋子周围两格 if (cur aiPlayer) { int best -100000000; for (const Move m : moves) { board.setStone(m, cur); int score minimax(board, depth - 1, humanPlayer, aiPlayer, humanPlayer); board.setStone(m, Player::None); // 悔棋恢复局面 best std::max(best, score); } return best; } else { int best 100000000; for (const Move m : moves) { board.setStone(m, cur); int score minimax(board, depth - 1, aiPlayer, aiPlayer, humanPlayer); board.setStone(m, Player::None); best std::min(best, score); } return best; } }关键点有两个。第一递归之前必须落子递归回来必须悔棋setStone(Player::None)就是把格子恢复为空。如果忘掉悔棋搜索完一个分支后棋盘是脏的后面的评估全错而且这种错很难用调试器抓出来属于典型的「逻辑黑匣子」。第二评估在depth 0的叶子节点做而checkWinLast要在叶子节点之前就拦下来也就是说「已经赢了的局面」优先于「深度没够的局面」。有些实现把胜负判断放在depth0里一起算结果AI明明已经冲四成功却因为深度没到而继续展开不存在的大局白白浪费计算。搜索深度设成4时候选点约30个单次搜索会在千万级节点徘徊。如果你的机器跑不动先把候选点半径从2格减到1格或者把深度减到3。不要一开始就追求打败自己先跑通再提速。到这里无剪枝的极大极小搜索已经能把AI跑起来了。但你很快会发现一个现实问题深度4一步可能要算几秒深度6基本等不出结果。下一章的剪枝算法就是解决这个问题的关键。4. Alpha-Beta剪枝把搜索深度从4层推到6层关键在两个参数的更新极大极小搜索有一个致命问题搜索树每深一层节点数呈指数级爆炸。4层时候选点30个训练一次就要算81万个节点到6层就是7亿个节点单线程根本等不了。Alpha-Beta剪枝做了一件很反直觉的事在保证最终结果不变的前提下主动砍掉那些「不会影响根节点决策」的分支。4.1 剪枝原理alpha下界、beta上界砍掉不可能影响结果的分支搜索过程中维护两个参数alpha记录「AI当前已知的最好分数」的下界beta记录「对手当前已知的最好分数」的上界。在极大节点AI回合只更新alpha在极小节点对手回合只更新beta。剪枝条件是如果在极小节点发现某个分支的分数小于等于当前alpha说明对手已经能把这个局面压到AI不想要的程度那AI在上层一定不会选这个分支后面兄弟节点不用再搜反过来在极大节点如果发现分数大于等于当前betaAI已经有了对手无法接受的走法后续分支也直接剪掉。没有剪枝时搜索树的每一层都是全量的候选点相乘有剪枝后很多子树被整棵跳过。同一个深度下剪枝有效的节点数通常只有无剪枝的十分之一到二十分之一。剪枝的核心是「尽早找到一个尽量好的alpha值」因为alpha越高能剪掉的重复分支越多这也引出下一节的排序技巧。4.2 实现与两个关键参数节点排序、初始搜索窗口下面是带着Alpha-Beta的递归框架。和3.2的极大极小相比只多了alpha、beta两个参数和两处剪枝判断但运行时间天差地别// SearchEngine.cpp Alpha-Beta剪枝版 int alphabeta( Board board, int depth, int alpha, int beta, Player cur, Player aiPlayer, Player humanPlayer) { int winScore board.checkWinLast(); if (winScore ! 0) return winScore; if (depth 0) return evaluateBoard(board, aiPlayer, humanPlayer); std::vectorMove moves generateCandidateMoves(board); // 关键参数一按评估分数从高到低排序剪枝效率立刻上来 sortMovesByScore(moves, board, cur, aiPlayer, humanPlayer); if (cur aiPlayer) { int best -100000000; for (const Move m : moves) { board.setStone(m, cur); int score alphabeta(board, depth - 1, alpha, beta, humanPlayer, aiPlayer, humanPlayer); board.setStone(m, Player::None); best std::max(best, score); if (best alpha) alpha best; if (alpha beta) break; // beta截断对手不会让AI更好 } return best; } else { int best 100000000; for (const Move m : moves) { board.setStone(m, cur); int score alphabeta(board, depth - 1, alpha, beta, aiPlayer, aiPlayer, humanPlayer); board.setStone(m, Player::None); best std::min(best, score); if (best beta) beta best; if (beta alpha) break; // alpha截断AI不会选这条线 } return best; } }和3.2的代码对比改动是四处递归传参多传alpha和beta极大节点每次得到更好分数时更新alpha极小节点更新beta以及两处提前break。alpha和beta的合作可以这么理解alpha是AI能接受的最低分beta是对手能接受的最高分两人之间一旦没有谈判空间后面所有的分支都是废话。两个参数决定剪枝效果。第一个是节点排序sortMovesByScore在递归前用评估函数对候选点做一次快速排序先搜「看起来最有可能让AI占优」的分支。排序质量高的时候剪枝率能到90%以上不排序的话alpha永远停留在很低的初始值剪枝几乎不生效那一层该搜还是搜。第二个是初始搜索窗口整个搜索树只有一个根节点调用的alpha初始值设为负无穷、beta设为正无穷表示「AI任何下限都能接受对手任何上限都可能出现」。如果在某些局面你想让AI更倾向某种风格可以收窄初始窗口比如从(-2000000, 2000000)开始等于手动排除一些极端分数代价是有可能剪错分支。对五子棋来说开成负无穷到正无穷最安全。参数上我比较常用的起步组合是depth4候选点半径2排序用评估函数分。这个组合在普通笔记本上一步大约几十到几百毫秒体感是「稍微等一下但能接受」。如果排序写得好可以尝试depth6这时一步大约一两秒棋力和depth4比有肉眼可见的差距。超过6层不建议硬加五子棋的搜索层数涨到8以上就算有剪枝普通桌面机也会卡进十几秒不如去优化评估函数或棋谱开局库。剪枝是搜索算法的「后悔药」同样的结果用更少的时间算完。代价是比无剪枝版多写几行参数传递以及必须保证排序函数本身不能太慢否则sort一次的开销就把剪枝省下的时间吃回去了。这一块的收益是实打实的同样的搜索深度剪枝版速度翻几倍是常态。5. 避坑指南五子棋AI最常见的5个翻车现场与排查方法这个项目写起来最容易出问题的不是「算法不会写」而是几个隐蔽但很常见的坑。我按踩坑概率从高到低列一下每条都按现象、原因、解决来写方便你对号入座。5.1 AI一步想十几秒候选点没裁剪把225个空格全搜了现象点击棋盘后AI光标转圈超过十秒甚至像死机一样没有响应。原因generateCandidateMoves把整个15x15棋盘遍历了一遍把所有空位都当成候选点。4层深度时225的三次方已经是千万级四次方就是数十亿单线程算到天荒地老。解决候选点只保留已有棋子周围两格以内的空位。实现方法是先遍历棋盘收集所有非空格子再把这些格子半径2范围内的空位加入候选集合去重。这一步做完候选点数量从225降到20到40个搜索时间立刻下降一个数量级。如果还慢把半径改成1格试试会更快但AI棋力略微下降。5.2 AI总是「送子」评估函数只算了自己或者max/min取反现象AI明明占优却突然走一步废棋放着对手的四连不管过两手被人五连带走了。原因最常见的是评估函数只算AI棋型不算对手棋型。极大极小搜索的分数是「AI有利为正」但叶子节点的分值只用了AI的颜色去evaluate对手的冲四活三在分数里没有体现AI自然看不到危险。另一种情况更隐蔽AI回合用了std::max对手回合也用了std::max整个搜索就变成了「AI和自己的最佳走法对局」每一步都在自嗨。解决评估函数返回值必须是totalScore aiScore - humanScore两边都算。极大极小版本里AI层用max、对手层用min写完后用一组简单局面做单测比如「棋盘上对手已有四连AI的下一步应该堵在四连的一头」跑一遍看返回值对不对。5.3 Qt编译不过moc文件或Qt与编译器版本不匹配现象Qt Creator里编译报错报错信息形如 -1: error: dependent ............\qt\5.15.2\msvc2019_64\include\qtwidget does not exist。原因Qt版本和编译器不匹配。这个报错里的路径是Qt 5.15.2的MSVC 2019 64位头文件路径编译器如果选的不是MSVC 2019 x64或者Qt的kit没配置对include路径就会指向一个根本不存在的位置。解决先在Qt Creator的「构建套件Kit」设置里确认编译器是MSVC 2019 64位Qt版本选5.15.2。然后清理项目删除build目录重新qmake并构建。如果你从网上下载的项目源码自带了一套.pro.user文件里面记录的路径是别人机器上的一定要删掉或重配不然Qt Creator会用旧配置找头文件。5.4 点击棋盘棋子「落歪」坐标换算没做四舍五入或漏掉了margin现象鼠标点在格子边线上棋子画到两条线的中间看起来很难受。原因坐标换算式子里用了int强制转换而非qRound或者忘了先减margin。比如x 100margin 24cell 36如果不减margin直接除得到2正确值是(100-24)/362.11四舍五入也应为2但如果点在x100偏右的位置实际离第2格更近不加margin就会偏到第1格。解决统一用qRound((pos.x() - margin) / cell)并且在鼠标事件和绘制事件里复用同一组margin和cell常量。把这两个值定义成BoardWidget的成员变量不要在paintEvent和mousePressEvent里各写一份不然改一个忘另一个落点和绘制就错位了。5.5 界面在「AI思考中」卡死搜索跑在了Qt主线程现象AI计算期间整个窗口无法响应拖拽和点击转圈图标是死的。原因搜索是CPU密集型操作运行在GUI线程里会阻塞Qt的事件循环所有界面事件都在排队等它结束。解决用QtConcurrent::run把搜索丢到后台线程搜完之后通过信号把最优落子传回主线程在主线程里负责落子和重绘。注意不要在子线程里直接调board.setStone再触发界面update这样会跨线程操作QWidget轻则警告重则崩溃。定义SearchEngine类它内部持有棋盘副本搜索完成后发射moveFound(Move)信号BoardWidget收到信号后再落到界面上。整体来说这个项目一半的调试时间会花在数据和界面协同上剩下才是算法本身。把界面事件和搜索线程彻底拆开后面加任何功能都好办。6. 把AI调到能打赢你迭代加深、状态缓存与对局验证AI能跑起来只是第一步我建议照三条路线继续打磨这三条都是工程里真正常用的技巧不是花架子。第一是迭代加深。固定深度搜索有个天然缺陷你不知道当前机器能在1秒内搜到第几层。做法是先搜depth2记录结果再搜depth3记录再搜depth4直到发现这一层耗时超过设定预算比如1秒直接拿上一轮的结果落子。这样任何时候都有可用的走法属于给程序留「后悔药」。实现上只需要在最外层加一个循环让alphabeta的depth从2往上递增每次搜索前清空上一次的结果缓存即可。第二是开局库和状态缓存。前几步的搜索树巨大但局面相似很多人会想缓存。第一次搜完的棋盘状态存入std::unordered_map键用盘面的Zobrist哈希值是评估分数。五子棋棋盘状态变化频率高缓存命中率没有象棋高但对「同一局面反复出现」的场景比如双方互相试探某个定式很有效。注意不同搜索深度下的得分不能混用缓存表要按depth分层否则低深度的粗估值会污染高深度的精确结果。第三是自动对弈验证。我每次改完评估函数权重都会让新旧两个版本AI自己下100盘统计胜率和每步平均耗时。还可以写几个手工构造的棋局比如「AI冲四活三已经成型验证它下一步是直接赢还是会去堵」这类断言比看胜率更能快速发现权重调坏的地方。调权重时不要一次改多个棋型分一次只改一个参数跑完对局再看胜负否则出了问题你不知道是哪个权重改的。我做这个项目时吃过一次教训为了让AI「更凶」连续把活三权重从10000改到15000又改到20000结果胜率反而下降因为AI开始过度追求自己的活三忽略了对手的冲四。后来把所有权重复位每次只动一个棋型再跑对局才摸清每个权重的影响范围。这大概是整个五子棋项目里最磨人但也最像工程实践的阶段算法理论是骨架参数调优才是让它真正变强的血肉。希望这个方向能帮到你。从棋盘数据到极大极小搜索再到剪枝每一步都是可验证的跑通之后你拿着它去参加笔试面试、去继续加机器学习决策都有一条清晰的路。本文还有配套的精品资源点击获取