五子棋AI核心算法：C++实现α-β剪枝与评估函数实战

简介这是一个基于C开发的AI五子棋游戏工程核心利用α-β剪枝算法高效搜索博弈树面向算法学习者、游戏AI开发者和课程设计/毕业设计学生。代码针对五子棋局面做了三点实用优化仅检索落子点周围2×2格内的棋子位置大幅压缩搜索分支一旦出现必胜或必败局面则立即返回估值避免无谓递归并在多个评分相近的位置中随机择一落子让AI不因固定套路而被轻易击败。资源压缩包共5个文件包含1份C源码、1份PDF设计报告、README说明文档、开源许可证及gitattributes配置整体大小约803KB源码结构清晰核心算法集中在单个cpp文件中报告则对博弈树建模、估值函数与剪枝流程进行了说明适合直接阅读和二次开发。当前已有506人学习下载对学习极大极小值算法、α-β剪枝及设计五子棋AI的同学有不错的参考价值。通过源码可对比不同剪枝力度和随机机制对最终棋力的影响便于进一步调优。1. 五子棋AI没那么玄α-β剪枝是你自己就能写出来的核心很多人听到“AI五子棋”第一反应是上深度学习、上神经网络结果折腾一圈连环境都跑不顺。实际上对于五子棋这种规则明确、局面可完全观测的双人零和游戏最可靠的做法是 C 实现的 α-β 剪枝搜索它不需要训练数据不需要显卡甚至不需要第三方库一台普通开发机就能跑出能赢过大部分业余玩家的棋力。这套方案的性价比极高也是我见过的最适合用来理解博弈树搜索的入门项目。这篇文章要解决的是四个具体问题AI 怎么“看懂”棋盘、搜索树怎么建、α-β 剪枝到底剪掉了什么、以及为什么你的 AI 会突然超时或走出昏招。我会直接给出可编译的 C 代码和参数建议中间穿插我实际调优时踩过的坑。适合刚学完 C 语法、想做一个有说服力的课程设计或面试项目的读者也适合已经写过简单人机对战、但发现 AI 棋力上不去的开发者对照查漏。2. 评估函数先行AI“看懂”棋局才谈得上搜索搜索算法本身不产生智能它只是在庞大的博弈树里找一条“看起来最好”的路径。真正让 AI 具备棋感的是评估函数——这是一个把棋盘状态映射成一个分数的函数分数越高代表当前局面对某一方越有利。评估函数设计的质量直接决定了 α-β 剪枝搜索的上限搜索只是把这个上限尽量逼近而已。2.1 棋型识别从“连子数”到“活眠”判断五子棋的攻防核心是棋型而不是简单的连子计数。所谓的棋型就是在一条直线横、竖、两条对角线上某方棋子形成 的连续或不连续但可通过一格补成的形状。最常见的分类是连五、活四、冲四、活三、眠三、活二、眠二。我一开始写过一版只统计“最多连了几颗子”的评估函数结果 AI 极其迟钝它不知道活三比眠三危险得多也不知道冲四虽然只有四颗子但对手必须马上挡否则下一手就成五。后来我把棋型判断拆成了两个维度连子长度和两端是否开放。一个形状如果两端都是空位称为“活”如果一端被对手或边界堵住称为“眠”如果一端空一端堵就是“冲”。真正的工程难点在于处理跳子形状比如 XOOOX 中间的断点可以被一枚己方棋子补上这种形状虽然当前连子数只有三段但威胁性接近于活四。常见做法是对每个空位做“假设落下己方棋子后以该点为中心检查四个方向的最大延伸长度”从而把跳子威胁也纳入评估。这种方法虽然会多几次扫描但实现简单、不易漏判非常适合作为第一版评估函数的核心逻辑。2.2 启发式评分表分数不是拍脑袋定的确定棋型分类后下一步就是给每类棋型定分数。我见过不少初学者把活三设为 10、活四设为 100、五连设为 1000这种线性比例在实际对局中非常不稳定因为 AI 会把“两步活三”和“一步活四”等价看待而实际上活四的威胁远大于两个活三之和。常见的做法是采用指数级或数量级差距的评分表。我推荐下面这组经过大量对局验证的基准值棋型我方得分说明连五10000000绝对赢棋必须最大活四1000000对方无法同时堵两端冲四100000对方必须应一手活三10000下一步可能变活四眠三1000威胁有限但需要关注活二100潜力点眠二10几乎无即时威胁这组评分为什么能打关键在于相邻级别之间差一个数量级这样在搜索过程中AI 会宁可放弃两三个活三的机会也优先去阻止对方的活四或冲四。在 minimax 回溯时这个数量级的差距还能起到天然的剪枝效果一旦某条分支发现对方有冲四其他分值低于 100000 的候选走法基本可以直接忽略。2.3 评估函数代码先写一个能打赢“只会堵”的版本下面给出一个简洁但有效的评估函数实现核心思路是遍历棋盘上的每一个位置分别以该位置为基准扫描四个方向统计棋型并累计分数。为了控制篇幅这里只展示单方向的棋型统计逻辑#include vector #include algorithm const int BOARD_SIZE 15; const int EMPTY 0; const int BLACK 1; // 我方 const int WHITE 2; // 对方 // 棋型分数表 const long long SCORE_FIVE 10000000LL; const long long SCORE_LIVE_FOUR 1000000LL; const long long SCORE_RUSH_FOUR 100000LL; const long long SCORE_LIVE_THREE 10000LL; const long long SCORE_SLEEP_THREE 1000LL; const long long SCORE_LIVE_TWO 100LL; const long long SCORE_SLEEP_TWO 10LL; // 方向向量横、竖、撇对角线、捺对角线 const int DIRS[4][2] {{0, 1}, {1, 0}, {1, 1}, {1, -1}}; // 扫描以 (row, col) 为起点、方向 dir 的一整条线统计棋型 long long evaluateLine(const std::vectorstd::vectorint board, int row, int col, int dirIndex, int player) { int count 1; // 当前连子数 int openEnds 0; // 开放端数量两端为空位 int dr DIRS[dirIndex][0]; int dc DIRS[dirIndex][1]; // 正方向扫描 for (int step 1; step 5; step) { int nr row dr * step; int nc col dc * step; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) break; if (board[nr][nc] player) { count; } else { if (board[nr][nc] EMPTY) openEnds; break; } } // 反方向扫描 for (int step 1; step 5; step) { int nr row - dr * step; int nc col - dc * step; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) break; if (board[nr][nc] player) { count; } else { if (board[nr][nc] EMPTY) openEnds; break; } } // 根据连子数和开放端数映射分数 if (count 5) return SCORE_FIVE; if (count 4) { if (openEnds 2) return SCORE_LIVE_FOUR; if (openEnds 1) return SCORE_RUSH_FOUR; } if (count 3) { if (openEnds 2) return SCORE_LIVE_THREE; if (openEnds 1) return SCORE_SLEEP_THREE; } if (count 2) { if (openEnds 2) return SCORE_LIVE_TWO; if (openEnds 1) return SCORE_SLEEP_TWO; } return 0; }这段代码的逻辑是从棋盘上的每个棋子出发沿四个方向分别向两端延伸统计连续同色棋子数以及两端的开放情况然后通过查表映射成分数。注意这里 count 的初始值是 1因为起点本身就是一枚己方棋子如果起点是空位需要先假设落子再调用该函数这样才能评估“下一步落在这里能形成什么棋型”。评估整个棋盘时需要分别从黑白双方视角计算分数然后做差totalScore myScore - oppScore * factor。factor 是防御权重我一般设 1.1 到 1.2让 AI 略微偏重防守。这个偏置在实战中很关键因为五子棋先手优势明显AI 如果想要后手不败防守必须略强于进攻。提示评估函数里的 openEnds 计数有一个常见疏漏——两端都是空位但其中一个方向是边界外这种情况 openEnds 最多只能算 1。上面的代码已经通过坐标边界判断处理了这一点但如果你的棋盘尺寸可变记得把边界判断改成nr 0 || nr size而不是写死 15。3. 从 minimax 到 α-β 剪枝把博弈树变小有了评估函数理论上就能做“穷举搜索”模拟双方轮流落子直到某个深度然后用评估函数给叶子节点打分。但五子棋每步平均有几十个合法落点搜索深度到 4 层就可能有上百万个节点纯 minimax 的耗时完全不可接受。α-β 剪枝正是在不改变搜索结果的前提下把不需要探索的分支直接砍掉。3.1 剪枝边界是怎么来的理解 α-β 剪枝先要理解 minimax 的“我方取 max、对方取 min”规则。假设我们已经搜完了一个分支确定当前节点的分数至少是 α继续搜索另一个分支时发现这个分支里对方可以选择一条路径让分数降到 β且 β 已经小于 α那么这个分支后续无论怎么发展都不可能再用更大的分数来影响父节点可以立即停止。上面这句话看着绕实际操作就是一个递归函数里维护两个参数alpha和beta。α 是当前“我方能保证的最低分”β 是当前“对方最多会让我方拿到的分”。每次递归向下传一旦在某层发现alpha beta就剪枝返回。这个机制完全不会漏掉最优解只是把确定无用的节点剔除。我在第一次实现时犯过一个典型的错误把 α、β 的更新写在了递归调用的返回值之后导致剪枝条件判断时用的还是父节点传入的旧值。正确的逻辑是在递归返回后立刻更新当前层的边界值而且 α 和 β 的更新要区分当前层是谁在走棋我方层更新 α对方层更新 β。这个区分如果不做AI 的走棋会表现得很怪时而激进时而过早放弃。3.2 候选走法生成先过滤掉明显的坏棋剪枝的效率高度依赖走法的搜索顺序。如果每次都是把最差的走法放在最前面α-β 剪枝几乎退化成纯 minimax。所以实战中一定要在进入搜索之前先对候选落子点做一次启发式排序。常见的做法是维护一个“候选点集合”只考虑与已有棋子曼哈顿距离不超过 2 的空位然后按“该点放置我方棋子的评估增加值 放置对方棋子的评估增加值”之和排序。这个和值体现的是该点对我方和对方的综合价值既能进攻又能防守的点应该优先搜索。下面给出候选点生成与排序的代码#include queue #include vector struct Move { int row; int col; long long score; // 排序用分数高的优先 bool operator(const Move other) const { return score other.score; } }; // 生成候选走法并按启发式分数排序 std::vectorMove generateMoves(const std::vectorstd::vectorint board, const std::vectorstd::vectorint scoreMap) { std::vectorMove moves; std::vectorstd::vectorbool visited(BOARD_SIZE, std::vectorbool(BOARD_SIZE, false)); for (int r 0; r BOARD_SIZE; r) { for (int c 0; c BOARD_SIZE; c) { if (board[r][c] EMPTY) continue; // 只考虑距离已有棋子不超过 2 的空位 for (int dr -2; dr 2; dr) { for (int dc -2; dc 2; dc) { int nr r dr; int nc c dc; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE) continue; if (board[nr][nc] ! EMPTY) continue; if (visited[nr][nc]) continue; visited[nr][nc] true; moves.push_back({nr, nc, scoreMap[nr][nc]}); } } } } // 按分数从大到小排序保证搜索时优先走“最像好棋”的点 std::sort(moves.begin(), moves.end(), [](const Move a, const Move b) { return a.score b.score; }); if (moves.empty()) { moves.push_back({BOARD_SIZE / 2, BOARD_SIZE / 2, 0}); } return moves; }这里scoreMap可以预先计算对每个空位分别计算“我方的评估增加值”和“对方的评估增加值”再加权求和。这个预计算在每轮搜索前做一次即可因为棋盘状态在玩家落子和 AI 落子之间只变化一步可以增量更新但从工程上讲全量重算 225 个点的代价并不高用O(n^2)的代价换取排序准确性完全值得。3.3 α-β 搜索的核心递归一个函数讲清楚下面是 α-β 剪枝搜索的核心实现。我采用负极大值negamax写法它和标准 minimax 等价但代码更简洁——每一层都从当前走棋方视角返回分数父节点取负值即可#include climits // 负极大值 α-β 剪枝 // depth: 搜索深度 // alpha, beta: 剪枝边界 // player: 当前层走棋方1黑2白 long long negamax(std::vectorstd::vectorint board, int depth, long long alpha, long long beta, int player) { // 判断胜负如果有一方已经连五不再深入搜索 int winner checkWin(board); if (winner ! EMPTY) { return (winner player) ? SCORE_FIVE : -SCORE_FIVE; } if (depth 0) { // 叶子节点从当前走棋方视角返回评估值 long long myScore evaluateBoard(board, player); long long oppScore evaluateBoard(board, opponent(player)); return myScore - oppScore; } auto moves generateMoves(board, scoreMap); long long best -LLONG_MAX; for (const auto move : moves) { // 尝试落子 board[move.row][move.col] player; long long val -negamax(board, depth - 1, -beta, -alpha, opponent(player)); board[move.row][move.col] EMPTY; // 恢复棋盘 if (val best) best val; if (best alpha) alpha best; if (alpha beta) break; // β 剪枝 } return best; }这段代码有两点需要仔细理解。第一递归调用时传入的是-beta, -alpha同时返回值取负这是因为切换了走棋方视角后上一层的“我方最大值”变成了下一层的“对方最大值”取负是对称转换的标准写法。第二剪枝条件是alpha beta一旦触发说明当前分支已经不可能影响上层决策可以直接 break 跳出循环。checkWin函数每次从根节点调用时全局判断一次即可不需要在每个递归节点都全盘扫描。常见的优化做法是只在“刚刚落子的那个点”检查五连因为一盘五子棋的胜负只可能由最后一手产生。调用入口也很简单根节点调用negamax(board, depth, -LLONG_MAX, LLONG_MAX, aiPlayer)返回值最大的那个Move就是 AI 的最终选择。注意根节点需要把返回分数和对应走法一起记录而不是像递归内部那样只记录分数。4. 搜索深度与候选优化让 AI 在 1 秒内做出决策代码能跑通和能实战是两回事。我在做完第一版后直接把搜索深度设成 6结果一步棋算了快 10 秒玩家早就等得不耐烦了。这里的核心矛盾是深度越深棋力越强但时间成本指数增长。工程上必须从搜索深度、候选数量、迭代加深三个方向同时想办法。4.1 深度预算4 层起步6 层封顶对 15 路棋盘来说搜索深度 2 的 AI 只会看眼前一步几乎不会防守深度 4 能正确应对活三和冲四但对深层次的陷阱看得不够远深度 6 基本能碾压业余玩家但耗时会显著上升。我的建议是常规对局用深度 4配合每步 200ms 的时间预算如果玩家水平较高或需要展示效果可以切到深度 6但必须配合走法排序和剪枝优化。剪枝效率的上限取决于走法排序质量这点的优先级高于一切参数调整。如果generateMoves返回的走法顺序接近最优即好的走法排在前面α-β 剪枝能砍掉 60% 到 80% 的节点如果顺序接近随机剪枝率会掉到 20% 以下。血泪经验是先优化排序再考虑加深度顺序不能反。4.2 迭代加深时间不够就“降级”迭代加深的思想很简单先搜深度 1如果时间充足再搜深度 2再搜深度 3直到超过时间预算直接使用上一次完整搜索的结果作为最终走法。这个策略的核心优势在于无论什么时候被中断都有一个“次优但可用”的结果不会出现超时崩溃。实现迭代加深只需要在外面套一层循环#include chrono Move iterativeDeepening(std::vectorstd::vectorint board, int maxDepth, int timeLimitMs, int aiPlayer) { auto start std::chrono::steady_clock::now(); Move bestMove; std::vectorstd::vectorint scoreMap computeScoreMap(board, aiPlayer); for (int depth 1; depth maxDepth; depth) { // 每层搜索前更新 scoreMap棋盘可能没变但稳妥起见重算一次 long long alpha -LLONG_MAX; long long beta LLONG_MAX; auto moves generateMoves(board, scoreMap); Move localBest; long long localScore -LLONG_MAX; for (const auto move : moves) { board[move.row][move.col] aiPlayer; long long val -negamax(board, depth - 1, -beta, -alpha, opponent(aiPlayer)); board[move.row][move.col] EMPTY; if (val localScore) { localScore val; localBest move; } if (localScore alpha) alpha localScore; // 每搜完 10 个节点检查一次时间 if (std::chrono::duration_caststd::chrono::milliseconds( std::chrono::steady_clock::now() - start).count() timeLimitMs) { return bestMove; // 时间不够返回上一次完整深度的结果 } } bestMove localBest; } return bestMove; }这段代码里最关键的是循环末尾的bestMove localBest只有完整搜索完一个深度才会更新bestMove。这样即使下一层深度超时返回的也是已完成搜索中最好的走法不会拿半截结果充数。时间检查放在每 10 个节点一次是为了避免频繁调用steady_clock带来的开销。如果你发现耗时抖动很大可以改成每 50 个节点检查一次也能接受。4.3 窗口与置换表剪枝的进阶参数α-β 剪枝的初始窗口一般设[-∞, ∞]。如果提前知道评估函数的可能范围比如五子棋限死在[-SCORE_FIVE, SCORE_FIVE]可以把初始窗口压窄比如[-SCORE_FIVE, SCORE_FIVE]。窗口越窄剪枝越激进但有风险如果最优解的真实分数落在窗口之外搜索结果会出错。常见做法是用窄窗口搜第一遍如果发现返回分数落在边界上等于 alpha 或 beta再用宽窗口重搜一遍。置换表是另一个性价比极高的优化它的核心是缓存搜索过的棋盘状态。由于五子棋对弈路径非常多同一盘面完全可能在搜索过程中以不同顺序重新到达。用std::unordered_map以棋盘的 Zobrist 哈希为键保存“该盘面的分数与深度”下次遇到直接查表。我实现置换表后发现深度 6 搜索的耗时下降了约 40%非常值得做。不过要注意置换表条目必须记录搜索深度深度大于当前要求的条目才能复用否则可能用到低精度的旧结果反而把棋力拉低。5. 避坑AI 五子棋的 5 个真实翻车点与排查方法写完第一版 AI 后我的预期是它能轻松赢我结果对弈几局发现它要么超时、要么昏招频出。这些问题极具普遍性我按实际发生频率整理成下面的清单每条从现象到原因到解决可以直接对照排查。5.1 搜索超时深度翻倍耗时指数爆炸现象AI 在前几步很快但中盘开始每步耗时超过 10 秒甚至直接卡死。原因中盘候选点数量最多每层分支因子变大如果走法排序质量差剪枝率骤降节点数会接近纯 minimax 的规模。此外如果你用的是递归里每次重新算了 ScoreMap也会放大耗时。解决先确认走法排序是否按综合价值降序再确认时间检查逻辑是否放在每层搜索内而不是根节点。我最终把固定深度搜索换成了迭代加深加时间预算超时问题才彻底解决。你的目标应该是“深度尽最大但时间不超过 N 毫秒”而不是“这几步必须搜到深度 6”。5.2 评估函数正负号错乱AI 主动送对方赢现象AI 明明检测到对方有活三却不下棋去堵反而走了一步无关紧要的棋。原因在 negamax 中返回的分数始终是“当前走棋方视角”父层通过取负来切换视角。假如你在叶子节点直接返回了固定视角的评估值比如总是返回黑方视角的分数那么轮到白方走棋时负极大值逻辑就会认为“对白方越好”的分数是“对黑方越差”导致 AI 在自己走棋时主动选择让黑方对方优势的走法。解决在叶子节点用myScore - oppScore其中myScore是当前player的视角。不确定时可以写一个断言让 AI 自己和自己对弈看它是否会主动堵自己的活三。如果不会那评估函数和搜索的衔接一定有方向性问题。这个坑极其隐蔽C 里没有运行时保护我花了一个下午才定位到。5.3 活三漏判block 了中间却没堵两端现象对方走了一个“跳活三”比如 X.X.X 中间隔一格AI 却跑到无关位置以为没有威胁。原因前面给出的evaluateLine只统计了“连续同色棋子”遇到跳子形状会直接断裂导致 count 远小于实际威胁长度。解决在评估函数里增加“跳过一格的补全检测”。常见做法是扫描线时允许一次空位跳变如果碰到空位记录下位置继续扫下一格如果下一格仍是己方棋子且空位可以补上就把棋型修正为活三甚至活四。实现上可以在 count 统计之后追加一个“isBreakable”检查决定棋型等级是否升级。5.4 同一分数随机震荡AI 越走越犹豫现象同一局面下AI 的表情是“随便挑了一个”有时候这一步堵左边下一步又堵右边看起来十分不稳定。原因排序时如果多个候选点分数相近std::sort的稳定性不保证加上没有打散机制AI 就会在并列分数里随机选择。另一个原因是 ScoreMap 里没有叠加微小噪声或优先下靠近中心的点。解决给启发式分数加一个与距离中心相关的微小权重比如score (BOARD_SIZE / 2 - abs(row - BOARD_SIZE / 2)) * 0.01。这样同分数下 AI 会偏向中心也能让行为可复现。测试时可固定srand种子否则很难判断是评估函数问题还是随机选择问题。5.5 自己先手必胜后手被碾压防守权重失衡现象AI 执黑先手时几乎必胜执白后手时却显得被动挨打完全不像同一个棋力。原因评估函数直接使用分数差值时双方机会被等权对待。但五子棋先手优势巨大白方如果不在防守上倾注更多资源很容易被黑方的一波攻势带走。解决在evaluateBoard返回最终差值时把对方分数乘以一个大于 1 的防守系数。我一般设置白方视角的防守系数为 1.15黑方为 1.05。这个偏斜会让 AI 在后手时更频繁地选择防守点虽然没有根本上扭转先手优势但能显著延长对抗回合数让对局更有可看性。提示防守系数的值不宜超过 1.3否则 AI 会走向另一个极端——只守不攻明明自己有活四机会也不把握错失胜机。调参时建议用一个自动对弈脚本循环测试不要靠手感判断。5.6 崩溃与越界边界坐标的隐性坑现象程序偶尔在搜索到第几十个节点时崩溃表现为vector subscript out of range或段错误。原因方向扫描时row dr * step可能超出[0, 14]范围虽然大部分代码里都有边界判断但generateMoves的双层循环里如果漏了空位判断会往已占用的格子落子后续评估时 player 值和预期不符导致棋型统计出现异常值。解决在做任何数组下标访问前先写一个通用的isValid(row, col)函数里面统一判断边界与棋盘大小。然后在所有扫描循环里用它替代手写的边界条件。另外C 的operator[]越界默认未定义行为建议在 Debug 模式下用std::vector::at()做一次全面检查确认无误后再换回operator[]保性能。6. 进阶技巧走法排序、Zobrist 哈希与自对弈验证基础版 AI 能玩了但距离“有棋感”还有一段路。这一节给你三个可落地的进阶方向按性价比从高到低排列。第一个方向是完善走法排序。我之前用的是简单的“进攻分 防守分”排序后来改成把“是否形成活三或冲四”作为排序的第一关键字效果立刻提升了一个档次。具体做法就是在generateMoves里如果某个空位落下后能形成活三或冲四把这个走法的分数直接提高一个数量级。理由很简单五子棋中威胁对方比一般位置的价值高得多优先搜索这类点可以显著加速剪枝。第二个方向是 Zobrist 哈希配合置换表。我给每个格子分配两个 64 位随机数黑子和白子各一个棋盘状态用一个 64 位整数表示落子和悔棋时通过异或更新哈希值。配合前面提到的置换表可以缓存已经搜索过的盘面评估结果大幅提速。Zobrist 哈希的独特优势是增量更新极快——一步落子只需要两次异或运算而且几乎不会冲突对五子棋这种棋盘状态有限的游戏非常可靠。第三个方向是自对弈验证。我在调试阶段写了一个简单的自动对弈脚本让 AI 执黑和执白各下 20 局统计先手胜率、平均回合数和每步耗时。胜率高于 80% 说明评估函数的攻防偏斜可能过大胜率低于 50% 说明搜索深度或走法排序还有问题。这个验证方法不需要外部工具只要在main函数里循环调用iterativeDeepening即可。我自己的经验是把逻辑错乱的评估函数调回来以后自对弈从“一步就结束”变成了“平均 30 回合分出胜负”这才是棋力正常的信号。最后说说我现在的习惯每当要调整评估函数参数或搜索深度时先跑一次自对弈作为回归测试确认修改没有引入新的昏招再挪到玩家对战里去验证体验。希望大家也能保留这个“先自动验证、再手动体验”的工作流它帮我省下了大量调试时间。希望帮到你。本文还有配套的精品资源点击获取