简介这是一份基于C与Qt框架开发的五子棋博弈游戏完整源码核心采用极大极小搜索配合剪枝算法实现AI对战适合计算机、人工智能、自动化等相关专业的学生、教师及开发者用于课程设计、毕业设计或算法学习。资源包共145个文件约7.26MB涵盖cpp与h源码、ui与qml界面文件、png与jpg素材、exe可执行程序及docx设计报告等结构完整便于直接运行与二次开发。项目代码经过测试功能完善可正常运行并附有设计文档方便理解算法思路与整体架构。目前已有65人学习下载。读者可从中掌握博弈树搜索、剪枝优化、Qt界面开发与多线程处理等关键技能也可在此基础上修改扩展实现其他棋类或功能适合作为课设、毕设或项目立项的参考范例。1. 从一份五子棋压缩包说起极大极小搜索和剪枝到底能跑多快很多人第一次看到「C和Qt开发的五子棋博弈游戏-极大极小搜索剪枝算法」这类标题第一反应是五子棋规则简单棋盘 15×15写个判断输赢的函数不就行了真动手才发现让电脑「会下棋」和让电脑「下得快」完全是两码事。纯暴力枚举在五子棋上的分支因子大约是 200 级别搜索 4 层就是 200 的 4 次方普通笔记本直接卡死。极大极小搜索Minimax负责把「我走一步、对手走一步」的对抗逻辑建模成博弈树Alpha-Beta 剪枝负责把明显不需要展开的分支砍掉两者配合才能把搜索深度从 3 层推到 6 层甚至更深。这套方案适合两类人一类是想通过一个完整项目把 C 递归、Qt 界面、算法优化串起来的学生或转行者另一类是想给已有棋类程序加 AI 但不知道从哪下手的开发者。下面按「先跑通、再调参、最后避坑」的顺序拆开讲。2. 极大极小搜索在五子棋里怎么落地从估值函数到递归框架2.1 为什么五子棋的估值函数比搜索深度更关键极大极小搜索的核心思想不复杂假设对手永远走最优解我在每一层选择让自己得分最高的走法对手选择让我得分最低的走法。但五子棋没有像象棋那样的子力价值表棋盘上每个点的价值完全取决于周围棋型。常见做法是给不同棋型打分活四两端开放的四连给 100000 分冲四给 10000 分活三给 1000 分眠三给 100 分活二给 100 分眠二给 10 分。这个分值表不是拍脑袋来的它决定了 AI 是「看见活四就堵」还是「自己先做活四」。我一般会把估值函数写成对每个空点周围 8 个方向做模式匹配而不是全盘扫描。全盘扫描 225 个点、每个点查 4 个方向、每个方向看 9 个格子一次估值就是 8100 次操作搜索 6 层根本扛不住。局部估值只检查落子点周围 2 格范围内的棋型变化能把单次估值压到 200 次操作以内。// 五子棋棋型分值表按连子数和开放端数区分 const int SCORE_FIVE 1000000; // 五连 const int SCORE_LIVE_FOUR 100000; // 活四 const int SCORE_RUSH_FOUR 10000; // 冲四 const int SCORE_LIVE_THREE 1000; // 活三 const int SCORE_SLEEP_THREE 100; // 眠三 const int SCORE_LIVE_TWO 100; // 活二 const int SCORE_SLEEP_TWO 10; // 眠二 // 评估一个落子点对某一方的价值 int evaluatePoint(const Board board, int x, int y, int role) { int totalScore 0; // 四个方向横、竖、左斜、右斜 const int dx[4] {1, 0, 1, 1}; const int dy[4] {0, 1, 1, -1}; for (int dir 0; dir 4; dir) { int count 1; // 当前点本身算一个 int openEnds 0; // 两端开放数 // 正方向延伸 for (int step 1; step 4; step) { int nx x dx[dir] * step; int ny y dy[dir] * step; if (!board.inRange(nx, ny)) break; if (board.get(nx, ny) role) count; else if (board.get(nx, ny) EMPTY) { openEnds; break; } else break; } // 负方向延伸 for (int step 1; step 4; step) { int nx x - dx[dir] * step; int ny y - dy[dir] * step; if (!board.inRange(nx, ny)) break; if (board.get(nx, ny) role) count; else if (board.get(nx, ny) EMPTY) { openEnds; break; } else break; } // 根据连子数和开放端数查表给分 totalScore lookupScore(count, openEnds); } return totalScore; }这段代码的关键参数是count和openEnds。count统计的是包含当前落子点在内、某一方向上连续同色棋子的数量openEnds统计的是这条连线两端还有几个空位。同样是三连两端都空活三和只有一端空眠三的价值差 10 倍。lookupScore是一个二维查表函数行是count1 到 5列是openEnds0 到 2返回对应的分值。注意count 5直接返回SCORE_FIVE这是胜负手不需要再考虑开放端。2.2 递归框架Negamax 写法比标准 Minimax 少一半代码标准 Minimax 要分「最大化层」和「最小化层」写两套逻辑容易写错。实际项目中我更推荐 Negamax 变体每一层都取当前走棋方的视角分数取负值传给上一层。这样递归函数只有一个代码量减半剪枝逻辑也更清晰。// Negamax Alpha-Beta 剪枝 // depth: 剩余搜索深度alpha/beta: 剪枝窗口 int negamax(Board board, int depth, int alpha, int beta, int role) { // 终局判断如果上一步已经形成五连直接返回极值 if (board.hasFive(role)) return SCORE_FIVE depth; // 越早赢分越高 if (depth 0) return evaluateBoard(board, role); int bestScore -INF; // 生成候选走法只考虑已有棋子周围 2 格内的空点 std::vectorMove moves generateMoves(board, role); // 按估值排序好的走法先搜剪枝效率更高 std::sort(moves.begin(), moves.end(), [](const Move a, const Move b) { return evaluatePoint(board, a.x, a.y, role) evaluatePoint(board, b.x, b.y, role); }); for (const Move mv : moves) { board.place(mv.x, mv.y, role); // 递归时交换角色分数取负 int score -negamax(board, depth - 1, -beta, -alpha, 3 - role); board.undo(mv.x, mv.y); if (score bestScore) bestScore score; if (score alpha) alpha score; if (alpha beta) break; // Beta 剪枝对手不会让我走到这里 } return bestScore; }这段递归里有三个参数需要重点理解。depth是剩余搜索层数每递归一次减一减到 0 就调用估值函数返回当前局面分。alpha是当前走棋方已经能找到的最好分数下界beta是对手能接受的最差分数上界。当alpha beta时说明这个分支对手不可能允许出现直接break掉。role参数用 1 和 2 表示黑白双方递归时用3 - role切换。generateMoves的候选点生成策略直接影响性能。如果每层都遍历全部 225 个空点搜索 6 层就是 225 的 6 次方剪枝也救不回来。常见做法是只考虑已有棋子周围 2 格内的空点并且按估值从高到低排序。排序这一步看起来多花了时间但能让剪枝提前发生整体搜索节点数往往能减少 50% 以上。3. Alpha-Beta 剪枝的工程实现窗口、排序和置换表3.1 剪枝窗口怎么设全窗口、零窗口和迭代加深Alpha-Beta 剪枝的效率极度依赖初始窗口[alpha, beta]的设置。全窗口搜索从[-INF, INF]开始第一层每个走法都要完整搜索剪枝效果最差。零窗口搜索也叫空窗口搜索把alpha和beta设成相邻值比如[score, score1]只判断「这个走法比当前最好走法好还是差」不关心具体好多少。零窗口搜索速度快但返回的分数不精确通常配合迭代加深使用。迭代加深的思路是先搜 2 层拿到一个大概的最好走法再用这个走法作为首选走法去搜 4 层再搜 6 层。每一层搜索时上一层的搜索结果用来排序候选走法让好的走法排在前面剪枝效率逐层提升。实际项目中我一般会设置一个时间上限比如 3 秒在时间用完之前不断加深搜索深度返回最后一次完整搜索的结果。// 迭代加深主循环 Move findBestMove(Board board, int role, int timeLimitMs) { auto startTime std::chrono::steady_clock::now(); Move bestMove generateMoves(board, role)[0]; // 兜底走法 int bestScore -INF; for (int depth 2; depth MAX_DEPTH; depth 2) { auto elapsed std::chrono::duration_caststd::chrono::milliseconds( std::chrono::steady_clock::now() - startTime).count(); if (elapsed timeLimitMs) break; // 超时退出 int alpha -INF, beta INF; Move currentBest; int currentScore -INF; std::vectorMove moves generateMoves(board, role); // 把上一轮的最好走法排到最前面 std::sort(moves.begin(), moves.end(), [](const Move a, const Move b) { if (a bestMove) return true; if (b bestMove) return false; return evaluatePoint(board, a.x, a.y, role) evaluatePoint(board, b.x, b.y, role); }); for (const Move mv : moves) { board.place(mv.x, mv.y, role); int score -negamax(board, depth - 1, -beta, -alpha, 3 - role); board.undo(mv.x, mv.y); if (score currentScore) { currentScore score; currentBest mv; } if (score alpha) alpha score; } bestMove currentBest; bestScore currentScore; // 如果已经找到必胜/必败不用再加深 if (bestScore SCORE_FIVE - 100 || bestScore -SCORE_FIVE 100) break; } return bestMove; }这段代码里MAX_DEPTH一般设 8 到 10但实际能搜到多深取决于时间限制和剪枝效率。timeLimitMs设 3000 表示 3 秒这是人机对弈时比较舒服的等待时间。如果设 1000 以下AI 会下得很快但棋力明显下降设 5000 以上人会等得不耐烦。depth 2而不是depth是因为五子棋搜索深度增加一层节点数大约翻 10 倍奇数层和偶数层的估值偏差不大跳着搜更划算。3.2 置换表用哈希缓存已经搜过的局面同一个局面可能通过不同的走法顺序到达比如「先下 A 再下 B」和「先下 B 再下 A」最终棋盘一样。如果不做缓存这两种路径会被重复搜索。置换表Transposition Table用 Zobrist 哈希把局面映射成一个 64 位整数搜索前先查表如果命中就直接返回缓存分数。// Zobrist 哈希每个位置每个角色对应一个随机数 uint64_t zobristTable[15][15][3]; // [x][y][role] void initZobrist() { std::mt19937_64 rng(12345); // 固定种子保证每次运行哈希一致 for (int x 0; x 15; x) for (int y 0; y 15; y) for (int r 0; r 3; r) zobristTable[x][y][r] rng(); } // 置换表条目 struct TTEntry { uint64_t hash; // 局面哈希 int depth; // 搜索深度 int score; // 分数 int flag; // 0精确值1下界2上界 Move bestMove; // 最好走法用于排序 }; std::unordered_mapuint64_t, TTEntry transTable; // 在 negamax 开头查表 int negamaxWithTT(Board board, int depth, int alpha, int beta, int role) { uint64_t hash board.getHash(); auto it transTable.find(hash); if (it ! transTable.end() it-second.depth depth) { if (it-second.flag 0) return it-second.score; if (it-second.flag 1 it-second.score beta) return it-second.score; if (it-second.flag 2 it-second.score alpha) return it-second.score; } // ... 正常搜索逻辑 ... // 搜索结束后写入置换表 TTEntry entry; entry.hash hash; entry.depth depth; entry.score bestScore; entry.flag (bestScore alpha) ? 2 : (bestScore beta) ? 1 : 0; entry.bestMove bestMove; transTable[hash] entry; return bestScore; }置换表的关键参数是depth和flag。只有缓存深度大于等于当前搜索深度时才能直接使用否则缓存分数不可靠。flag标记这个分数是精确值、下界还是上界如果缓存分数是下界且大于等于beta说明之前搜索已经证明这个局面至少有这么好可以直接返回如果是上界且小于等于alpha说明这个局面最多就这么好也可以直接返回。bestMove字段用来在候选走法排序时把历史最好走法排到前面进一步提升剪枝效率。注意置换表会占用内存unordered_map在节点数超过百万后插入和查找开销明显。实际项目中可以用固定大小的数组加取模索引或者用std::vector预分配空间。4. Qt 界面和 C 引擎怎么对接信号槽、线程和刷新节奏4.1 用 QThread 把搜索放到后台避免界面卡死Qt 的主线程负责界面刷新和事件循环如果在主线程里直接调用findBestMove搜索 3 秒界面就卡 3 秒鼠标点击、窗口拖动全部无响应。常见做法是把搜索逻辑放到QThread子类或者QObject加moveToThread里搜索完成后通过信号把走法传回主线程。// AI 搜索线程类 class AIWorker : public QObject { Q_OBJECT public slots: void search(Board board, int role, int timeLimit) { Move best findBestMove(board, role, timeLimit); emit searchFinished(best.x, best.y); } signals: void searchFinished(int x, int y); }; // 主窗口中的调用 void MainWindow::onAITurn() { QThread* thread new QThread; AIWorker* worker new AIWorker; worker-moveToThread(thread); connect(thread, QThread::started, []() { worker-search(currentBoard, aiRole, 3000); }); connect(worker, AIWorker::searchFinished, this, MainWindow::onAIMoveReady); connect(worker, AIWorker::searchFinished, thread, QThread::quit); connect(thread, QThread::finished, worker, QObject::deleteLater); connect(thread, QThread::finished, thread, QObject::deleteLater); thread-start(); } void MainWindow::onAIMoveReady(int x, int y) { currentBoard.place(x, y, aiRole); update(); // 触发 paintEvent 重绘棋盘 // 判断胜负切换回合 }这段代码里moveToThread把worker对象移到子线程search槽函数在子线程执行。searchFinished信号默认是队列连接会自动切回主线程执行onAIMoveReady。注意Board对象在传参时用了值传递避免子线程和主线程同时读写同一块内存。如果棋盘数据量大可以用QSharedPointer或者加锁但五子棋棋盘只有 225 个格子值传递的开销可以忽略。4.2 棋盘绘制QPainter 画格子和棋子别用 QLabel 拼Qt 画五子棋棋盘有两种常见做法一种是用QGridLayout塞 225 个QLabel每个QLabel显示一个棋子图片另一种是重写paintEvent用QPainter直接画线画圆。前者代码直观但性能差225 个控件每次刷新都要重新布局后者代码稍多但刷新流畅而且容易做落子动画和最后一手标记。void BoardWidget::paintEvent(QPaintEvent* event) { QPainter painter(this); painter.setRenderHint(QPainter::Antialiasing, true); int cellSize qMin(width(), height()) / 16; // 15 格棋盘留边距 int offset cellSize; // 画网格线 painter.setPen(QPen(Qt::black, 1)); for (int i 0; i 15; i) { int pos offset i * cellSize; painter.drawLine(offset, pos, offset 14 * cellSize, pos); painter.drawLine(pos, offset, pos, offset 14 * cellSize); } // 画棋子 for (int x 0; x 15; x) { for (int y 0; y 15; y) { int role board.get(x, y); if (role EMPTY) continue; int cx offset x * cellSize; int cy offset y * cellSize; int radius cellSize * 0.4; QRadialGradient gradient(cx - radius/3, cy - radius/3, radius); if (role BLACK) { gradient.setColorAt(0, Qt::darkGray); gradient.setColorAt(1, Qt::black); } else { gradient.setColorAt(0, Qt::white); gradient.setColorAt(1, Qt::gray); } painter.setBrush(gradient); painter.drawEllipse(QPoint(cx, cy), radius, radius); } } // 标记最后一手 if (lastMove.x 0) { int cx offset lastMove.x * cellSize; int cy offset lastMove.y * cellSize; painter.setPen(QPen(Qt::red, 2)); painter.setBrush(Qt::NoBrush); painter.drawEllipse(QPoint(cx, cy), cellSize * 0.15, cellSize * 0.15); } }cellSize根据窗口大小动态计算保证棋盘始终居中且不超出窗口。QRadialGradient给棋子加一点立体感比纯色圆看起来舒服。最后一手用红色小圆标记方便玩家看清 AI 刚下在哪里。鼠标点击事件里把像素坐标转成棋盘坐标公式是(mouseX - offset cellSize/2) / cellSize加cellSize/2是为了让点击落在格子中心附近也能正确映射。5. 避坑与排查搜索慢、界面卡、剪枝失效的 5 个血泪教训5.1 搜索深度加到 6 层就卡死CPU 占用 100% 但不出结果现象把MAX_DEPTH从 4 改成 6程序运行后界面无响应任务管理器显示 CPU 满载等 10 秒也没走出一步。原因候选走法生成没有限制范围每层都在遍历全部空点。15×15 棋盘在开局阶段有 200 多个空点搜索 6 层的节点数大约是 200 的 6 次方剪枝根本来不及生效。解决generateMoves只返回已有棋子周围 2 格内的空点并且按估值排序。开局阶段候选点从 200 降到 20 左右搜索 6 层的节点数直接降两个数量级。另外加上迭代加深和时间限制超时就用上一层的搜索结果。5.2 Alpha-Beta 剪枝后结果和全搜索不一致现象关掉剪枝跑一遍AI 走 A 点打开剪枝跑一遍AI 走 B 点两个点的估值分数还不一样。原因剪枝窗口传递时写错了符号。Negamax 递归里alpha和beta要取负并交换写成-negamax(board, depth-1, alpha, beta, 3-role)就错了正确写法是-negamax(board, depth-1, -beta, -alpha, 3-role)。解决检查递归调用里的参数顺序-beta传给alpha位置-alpha传给beta位置。这个错误很隐蔽因为剪枝后分数偏差不大但走法选择会变。5.3 Qt 界面在 AI 搜索时点击无响应窗口拖动卡顿现象AI 思考的 3 秒内鼠标点击棋盘没反应拖动窗口会留下残影。原因搜索逻辑跑在主线程阻塞了 Qt 的事件循环。QApplication::processEvents()虽然能临时刷新界面但会引入重入问题不推荐。解决用QThread把搜索放到子线程通过信号槽把结果传回主线程。注意Board对象要值传递或者深拷贝避免多线程读写冲突。5.4 置换表命中率低搜索速度没提升现象加了置换表之后搜索节点数没减少反而因为哈希计算和查表多花了时间。原因Zobrist 哈希初始化时用了rand()而不是固定种子每次运行哈希值不同置换表里的缓存全部失效。另外置换表没有设置大小上限unordered_map在节点数多了之后冲突严重。解决Zobrist 哈希用固定种子初始化保证同一局面每次哈希值一致。置换表用固定大小的数组加取模索引或者定期清空。缓存条目要检查depth只有缓存深度大于等于当前深度才能用。5.5 估值函数把活三和冲四搞反AI 该堵不堵现象对手形成活三AI 不去堵反而去下自己的棋两步之后被对手做成活四。原因估值函数里活三和冲四的分值设反了或者openEnds统计逻辑有 bug把两端封闭的冲四算成了活四。解决打印估值函数的中间结果手动摆几个典型棋型验证。活三的分值应该低于冲四因为冲四下一步就能成五活三还需要两步。openEnds统计时注意边界情况棋盘边缘的棋子只有一端能延伸。6. 把搜索深度推到 8 层历史启发和杀手走法的实战调参搜索深度从 6 层到 8 层节点数大约翻 100 倍光靠 Alpha-Beta 剪枝不够需要加启发式排序。历史启发History Heuristic记录每个走法在之前搜索中触发剪枝的次数次数越多说明这个走法越可能引起剪枝排序时优先搜索。杀手走法Killer Move记录同一层里最近触发剪枝的走法在兄弟节点搜索时优先尝试。// 历史启发表history[role][x][y] 记录该走法触发剪枝的次数 int historyTable[3][15][15] {0}; // 杀手走法每层记录 2 个最近触发剪枝的走法 Move killerMoves[MAX_DEPTH][2]; // 在 negamax 里更新历史表和杀手走法 if (alpha beta) { // 触发剪枝增加历史分数 historyTable[role][mv.x][mv.y] depth * depth; // 更新杀手走法 if (killerMoves[depth][0] ! mv) { killerMoves[depth][1] killerMoves[depth][0]; killerMoves[depth][0] mv; } break; } // 候选走法排序时综合估值、历史分数和杀手走法 std::sort(moves.begin(), moves.end(), [](const Move a, const Move b) { // 杀手走法优先级最高 if (a killerMoves[depth][0]) return true; if (b killerMoves[depth][0]) return false; if (a killerMoves[depth][1]) return true; if (b killerMoves[depth][1]) return false; // 其次比较历史分数 int histA historyTable[role][a.x][a.y]; int histB historyTable[role][b.x][b.y]; if (histA ! histB) return histA histB; // 最后比较静态估值 return evaluatePoint(board, a.x, a.y, role) evaluatePoint(board, b.x, b.y, role); });历史分数用depth * depth累加深度越大权重越高因为深层剪枝说明这个走法在更关键的局面下有用。杀手走法每层只存 2 个避免排序时开销过大。实际测试中加上历史启发和杀手走法后搜索 8 层的节点数比纯估值排序减少约 60%3 秒内能稳定搜到 8 层。还有一个容易被忽略的调参点是估值函数的权重。开局阶段棋盘空旷活三和活二的分值应该适当降低避免 AI 过早定型中局阶段棋子密集冲四和活四的分值要拉高让 AI 优先处理威胁。我一般会准备两套分值表根据棋盘上棋子数量切换棋子少于 10 个用开局表多于 10 个用中局表。这个改动不大但棋力提升很明显。最后说一个我踩过的坑置换表里的bestMove字段在缓存命中时也要用来排序否则置换表只加速了分数返回没有加速剪枝。另外置换表在迭代加深的每一层之间不要清空上一层的缓存对下一层仍然有效清空反而浪费。希望帮到你。本文还有配套的精品资源点击获取