C++五子棋AI实战：博弈树与α-β剪枝四层搜索

简介基于C与博弈树实现的AI五子棋人机对战源码包面向希望学习棋类AI算法、特别是博弈树搜索与α-β剪枝优化的开发者。AI通过构建博弈树评估棋局状态并利用α-β剪枝动态剪去无望分支减少搜索节点目前可推算四层局面适合作为课程设计、算法实验或人机对战入门项目的参考。压缩包共47个文件大小2.64MB包含完整的Visual Studio工程C头文件与源文件实现棋盘逻辑、AI核心和哈希表.sln与.vcxproj工程文件便于直接加载编译另附编译生成的exe及pdb、obj等调试与中间产物既可体验对战效果也能跟踪调试。项目结构清晰核心代码集中在少量cpp/h文件中易于阅读和扩展如调整搜索深度或评估函数。发布以来已有79人学习下载对于想深入理解博弈树与α-β剪枝实现细节的读者是一份可直接运行的实用源码。1. 四层推算的人机对战五子棋用C把博弈树和α-β剪枝落到实处先说一个反直觉的结论一个让普通玩家觉得“难缠”的五子棋AI不需要深度学习也不需要把棋盘上所有空位全量搜索到底。用C实现一个传统的博弈树配上α-β剪枝把搜索深度稳定推到四层就足以在中端笔记本上做到单步百毫秒级应答棋力明显超过随手落子的新人。这里“四层”指的是AI下完一手之后把“对手应一手、我再应一手、对手再应一手”的变化都推算一遍再从当前可选落点里挑后续局面最好的一步。标题里这个源码.zip要解决的核心问题正好落在博弈树、α-β剪枝和局面评估这三件事上界面反而是次要的。这篇笔记会把这套方案的选型理由、可运行的C代码和踩坑点全部展开适合想自己搞一个离线五子棋AI的人也适合面试前需要手写搜索算法的同学。2. 博弈树搜索空间有多大α-β剪枝为何能把四层推算压进100毫秒2.1 五子棋博弈树长什么样分支因子、深度与候选落子博弈树这个概念不能只在图论里看落在五子棋棋盘上它就是一棵递归展开的“可能局面树”。15×15的棋盘第一手有225个空位第二手224个第三手223个……如果真把所有空位都列成节点那到第四层的节点数就是225×224×223×222约2.5亿个节点。这个数字对任何个人电脑都不现实所以第一步不是优化搜索而是先把树的规模压下来。工程上常见的做法是“候选落子过滤”只搜索距离已有棋子两格以内的空位。一盘正常对弈中棋盘上通常只有几十颗棋子按这个规则过滤后每个节点的候选落点往往只有15到30个。这样四层深度对应的节点数就从2.5亿掉到15^4约5万这个量级C跑一遍只需要几毫秒到几十毫秒。这个过滤不是玄学道理很直白离所有棋子都超过两格的位置在当前这个局面下几乎不可能产生“成五”“活四”这类关键棋型先手落子和后续变化都接不上剪掉它不会改变搜索结论只会让搜索快一个数量级。另一个必须控制的参数是根节点的搜索范围。空棋盘开局时所有位置都离棋子无限远过滤规则会失效所以开局前几手我会直接给AI一个固定书库先占天元对手占星位附近再按对称位置响应。实现这个只需要在根节点做特殊判断不参与递归。搜索深度四层在博弈树上具体展开是这样的第一层AI落子第二层对手落子第三层AI再落子第四层对手再落子然后在第四层结束时调用评估函数打分。也就是说AI能看到自己当前这手之后完整的一来一回这是对付“对手会不会堵我活三”这种问题的最低配置深度。深度只有两层的话AI看不到对手的后续威胁深度到六层以上节点数又指数爆炸四层正好是性能和棋力都稳的位置。2.2 α-β剪枝的上下界α、β两个值怎么让搜索量减少一个数量级α-β剪枝的原理可以压缩成一句话如果当前节点已经找到一个足够好的走法那兄弟节点里那些一眼看过去更差的走法就不必再算了。标准博弈树搜索里AI方用α记录“我能保底拿到的最好分数”对手方用β记录“对手能接受的最高分数”。当α大于等于β时说明当前分支无论如何都不可能被双方同时接受继续往下搜只是浪费时间直接返回即可。具体到四层树上看剪枝发生在两个方向。AI层取最大值搜索某个子节点时子节点会返回一个分数如果这个分数比已经算出来的α还大就更新α继续检查α是否大于或等于β若是则立即终止当前节点的循环不再看其余候选点。对手层取最小值是对称操作算出的分数比当前β还小就更新β一旦β小于或等于α就终止循环。这个机制生效的前提是“节点搜索顺序足够好”。剪枝最理想的情况是每一层第一个搜索的候选点恰好就是这个节点的最优解那么后面所有兄弟节点都能被剪掉搜索量会降到原来开根号的量级。顺序乱的话剪枝效率很差甚至接近没剪。所以有经验的工程实现里会在进入递归前先对候选落点按一个粗评分排序把“最可能的好棋”放到前面。这个排序本身不参与最终决策只影响剪枝速度代价很低但收益极大。节点数量下降到什么程度拿四层深度、每层约20个候选点来说不剪枝的理论节点数是20^4约16万带上α-β剪枝和排序后实际递归调用经常只能跑到1万次左右再配合每个节点几十条指令的评分计算单步搜索在普通机器上跑到0.1秒以内是常态。这也是标题里“112毫秒”这类指标来得出的原因——它并不是机器性能秀而是博弈树的自然算术结果。2.3 四层深度的人机对战效果为什么不是越深越好五子棋不像围棋那样深不可测它的威胁是短促而局部的。一条线上的连子从活二到活三到冲四到成五往往只需要两三手完成。四层深度恰好能覆盖“我形成活三对手堵一边我变冲四对手再堵”这种完整攻防链。比这个深度更浅AI看不到对手的反击比这个更深棋力提升其实很平缓但搜索时间成倍增加用户体验会快速变差。深度四层还有一个容易被忽略的优势它让AI的落子风格偏向“稳健防守”。因为搜索看到了对手两轮以内的所有应对所以那些起手很激进、但后续会被对手连续反击的开局会被评分压低AI自动会选有后续手段的稳妥着法。实测下来这类AI跟业余棋手对战胜率主要来自不犯低级失误而不是某条绝杀妙手。对普通玩家来说这种风格正好——输了会觉得是自己没算到赢了会很有成就感适合做产品而不是做强到劝退的对手。需要提醒的是深度是博弈树搜索的全局参数但实际棋力还跟评估函数的偏向强相关。后面代码部分我会把评估函数的细节讲清楚。如果你改的评分里把“防守权重”调得过高四层AI可能会变得异常消极这不是搜索的锅是分数的锅。3. C实现α-β剪枝的落子搜索评估函数与递归代码逐行拆解3.1 棋盘数据结构的选择二维数组冲零就好别急着上zobrist五子棋的棋盘只有15×15一个棋子就是一个整数存进二维数组是最直接的做法。棋盘类里只需要三个成员一个当前局面的二维数组、一个记录当前轮到哪方下的标记、一个记录已经走了多少手的计数器。初始化时全部清空用0表示空位1表示黑棋2表示白棋。为什么不建议一开始就引入zobrist哈希这类高级结构因为四层搜索的节点数只有万级每秒不过几千次递归调用一次memcpy拷贝数组的开销完全扛得住。置换表确实能加速重复局面但它引入的哈希计算和维护成本对新手不友好等基础版本跑通之后再加不迟。这一点很重要先把搜索主链路跑明白再想优化否则你调试时根本分不清是搜索逻辑错了还是哈希更新错了。#include array #include vector constexpr int BOARD_SIZE 15; constexpr int EMPTY 0; constexpr int BLACK 1; constexpr int WHITE 2; using Board std::arraystd::arrayint, BOARD_SIZE, BOARD_SIZE; struct Move { int x -1; int y -1; }; class GomokuBoard { public: Board board{}; int currentSide BLACK; void reset() { for (auto row : board) { row.fill(EMPTY); } currentSide BLACK; } bool isInside(int x, int y) const { return x 0 x BOARD_SIZE y 0 y BOARD_SIZE; } bool move(int x, int y, int side) { if (!isInside(x, y) || board[x][y] ! EMPTY) { return false; } board[x][y] side; currentSide (side BLACK) ? WHITE : BLACK; return true; } };棋盘类本身很简单move函数做落子并切换回合。EMPTY、BLACK、WHITE三个常量贯穿整个搜索过程递归里判断“这个位置该谁下”时直接用currentSide对应的值。搜索算法的输入输出都围绕这个类展开界面层不管你是用控制台还是MFC调用它拿到的都是一个落子坐标。提前把坐标合法性判断放在move里而不是搜索里可以省掉一层一层传参数的麻烦。3.2 评估函数怎么给棋型打分连子、活二活三眠三的分数设置评估函数是整个AI最像“玄学”的部分也是棋力差异最大的来源。α-β剪枝只负责在给定评分的游戏中找到最优路径但“局面好坏”这个信号完全由评估函数给出。四层搜索的叶子节点会按评估函数的结果回溯分数设置错了剪枝再正确也白搭。常见实现思路是把每个方向上的连子都拆出来按长度和两端是否开放打分。我一般用这样一组基准值成五直接给100万分活四给1万分冲四给8000分活三给1000分眠三给500分活二给100分眠二给50分单个棋子给10分。这里的“活”指两端都被空位夹住“眠”指至少一端被堵死或出了棋盘。注意评分时必须同时扫描黑棋和白棋因为AI不但要看到自己的进攻机会还要看到对手的潜在威胁否则它不会去防守。int shapeScore(int len, bool openStart, bool openEnd) { if (len 5) return 1000000; bool bothOpen openStart openEnd; bool oneOpen openStart ! openEnd; if (bothOpen) { switch (len) { case 4: return 10000; case 3: return 1000; case 2: return 100; case 1: return 10; default: return 0; } } else if (oneOpen) { switch (len) { case 4: return 8000; case 3: return 500; case 2: return 50; case 1: return 5; default: return 0; } } return 0; }这个shapeScore只描述一种棋型的价值真正遍历全场要用四个方向扫描。为了避免同一条线段被重复统计我在外层循环里只统计“线段起点”——也就是反方向没有同色棋子的那个端点开始延伸。这样一条五颗连子只被计数一次不会因为从中间扫描而把一条五连数成两段评分逻辑也更清晰。int evaluateBoard(const GomokuBoard gb, int mySide) { const int dx[4] {0, 1, 1, 1}; const int dy[4] {1, 0, 1, -1}; int score 0; for (int x 0; x BOARD_SIZE; x) { for (int y 0; y BOARD_SIZE; y) { int cur gb.board[x][y]; if (cur EMPTY) continue; for (int d 0; d 4; d) { int px x - dx[d]; int py y - dy[d]; if (gb.isInside(px, py) gb.board[px][py] cur) { continue; } int len 0; int cx x; int cy y; while (gb.isInside(cx, cy) gb.board[cx][cy] cur) { len; cx dx[d]; cy dy[d]; } bool openStart gb.isInside(px, py) gb.board[px][py] EMPTY; bool openEnd gb.isInside(cx, cy) gb.board[cx][cy] EMPTY; int base shapeScore(len, openStart, openEnd); if (base 0) continue; score (cur mySide) ? base : -base; } } } return score; }evaluateBoard对每个棋子的四个方向做延伸先跳过那些不是线段起点的位置再用循环数出连续同色棋子的长度最后根据两端开放情况取分数。对手的棋型全部按负分处理AI的按正分处理最终得分越高表示对AI越有利。这里“正负号怎么分配”是后面会踩到的大坑先记住一个原则评估函数永远站在AI侧看局面AI的活三加1000对手的活三减1000绝不能两边都加正分。3.3 核心递归α-β剪枝函数的最小可运行实现alphaBetaSearch是最短也是最核心的递归。每一层只做三件事判断深度是否到零、获取候选落点、对每个候选点落子并递归搜索。真正的剪枝发生在递归返回后用返回值更新α或β并判断是否该提前终止循环。constexpr int NEG_INF -2000000; constexpr int POS_INF 2000000; std::vectorMove generateCandidates(const GomokuBoard gb) { std::vectorMove result; if (gb.totalMoves 0) { result.push_back({7, 7}); return result; } for (int x 0; x BOARD_SIZE; x) { for (int y 0; y BOARD_SIZE; y) { if (gb.board[x][y] ! EMPTY) continue; bool near false; for (int i -2; i 2; i) { for (int j -2; j 2; j) { int nx x i; int ny y j; if (gb.isInside(nx, ny) gb.board[nx][ny] ! EMPTY) { near true; break; } } if (near) break; } if (near) { result.push_back({x, y}); } } } return result; }generateCandidates在空棋盘时强制落天元其他时候只返回棋盘点周围两格以内的空位。返回值是不动vector棋盘状态由调用方在递归里自行恢复这样多线程并行搜索时每个线程拥有自己的临时棋盘副本不会互相污染。totalMoves成员需要在move里递增用来判断是否空棋盘开局。int alphaBetaSearch(GomokuBoard gb, int depth, int alpha, int beta, bool isAI) { if (gb.hasWin()) { return isAI ? NEG_INF depth : POS_INF - depth; } if (depth 0) { return evaluateBoard(gb, AI_SIDE); } std::vectorMove moves generateCandidates(gb); if (moves.empty()) { return evaluateBoard(gb, AI_SIDE); } if (isAI) { int bestVal NEG_INF; for (const Move m : moves) { gb.board[m.x][m.y] AI_SIDE; int val alphaBetaSearch(gb, depth - 1, alpha, beta, false); gb.board[m.x][m.y] EMPTY; if (val bestVal) { bestVal val; } if (bestVal alpha) { alpha bestVal; } if (alpha beta) { break; } } return bestVal; } else { int bestVal POS_INF; for (const Move m : moves) { gb.board[m.x][m.y] HUMAN_SIDE; int val alphaBetaSearch(gb, depth 1 - 1, alpha, beta, true); gb.board[m.x][m.y] EMPTY; if (val bestVal) { bestVal val; } if (bestVal beta) { beta bestVal; } if (alpha beta) { break; } } return bestVal; } }搜索到的终局会优先判断是否有人赢棋hasWin可以在每次落子后只检查最后一颗棋子周围四个方向来快速实现。注意胜局返回的分数加了深度修正在赢棋时优先选更快赢的路径输棋时优先选更晚输的路径这是博弈树搜索里防止AI“赢棋磨蹭”的关键细节。alpha和beta的初始值直接给正负两百万即可因为单局评分绝对值不会超过这个范围。递归的每一层只做一次val和bestVal的更新然后立刻推进alpha或beta剪枝判断用alpha beta。这里有个常见的写法问题有人会把剪枝判断写成if (val beta)这在某些实现里也能工作但和标准α-β写法不一致在带置换表的版本里会导致边界混乱后面会专门讲。3.4 顶层调用与界面对接AI落子坐标怎么返回递归函数只返回分数真正要做决策的顶层需要返回一个坐标。findBestMove干的事情是拿每个候选点试落一颗AI棋子然后用三层的alphaBetaSearch算这个局面下的最优后续分数把所有候选点的分数比一遍取最高分的那个点作为最终落子。Move findBestMove(GomokuBoard gb) { std::vectorMove moves generateCandidates(gb); int bestScore NEG_INF; Move bestMove moves.empty() ? Move{7, 7} : moves[0]; for (const Move m : moves) { gb.board[m.x][m.y] AI_SIDE; int score alphaBetaSearch(gb, 3, NEG_INF, POS_INF, false); gb.board[m.x][m.y] EMPTY; if (score bestScore) { bestScore score; bestMove m; } } return bestMove; }这段代码把“四层”这个参数的分布讲得很清楚顶层本身就消耗了一层所以这里调用alphaBetaSearch时depth传的是3递归内部再加一层就是完整四层。如果你想要更深的搜索改顶层参数和递归参数时要注意depth预算概念顶层搜索不是“另开一层”它是第一层。顶层调用完成之后AI的落子坐标就以Move结构体返回界面只需要把这个坐标画到棋盘上。这套搜索核心不依赖任何图形库控制台打印、Qt窗口、MFC对话框都能直接套用。4. 避坑α-β剪枝最容易翻车的四个细节4.1 评估函数正负号写反AI变成送棋大师现象搜索能跑落子也很快但AI总是在帮对手做活三自己该进攻的位置视而不见。根源在于评估函数里把对手的棋型也加了正分。比如对手活三你给1000AI的活三也给1000那搜索找到的局面里AI会觉得“双方都有活三很好”它当然落子就随意了。解决评估函数严格站在AI视角打分对手棋型一律取负。最简单的检查办法是在一个空棋盘上黑白各放几颗棋子手工计算一遍预期分数再跑evaluateBoard对比。如果对手一边的分数是正数就是符号问题。4.2 剪枝条件写错导致搜索深度莫名掉一层现象同一条局面换一个depth参数后AI棋力反而变弱了或者落子风格忽然变得激进。常见原因是在min层里把剪枝条件写成了if (val beta)而在max层又用了if (val alpha)两边不对称会导致某些分支被过早剪掉四层搜索退化成三层半的视野。解决max层里用alpha beta终止min层里同样用alpha beta终止不要用val去跟边界比较。改完之后可以用一个最简单的验证设计一个“两步必赢”的局面四层搜索应当在第一步就找到制胜点。如果找不到八成是剪枝把制胜路径截断了。4.3 候选落子点过多四层搜索超过1秒的排查路径现象中盘局面搜索时间突然飙到两三秒。原因多半是generateCandidates的半径参数开太大或者干脆实现成“所有空位都入候选”。半径2以内是经验值如果这颗子周围全是棋子候选点很快就会增长到棋盘一半空位搜索量就爆炸了。解决先输出当前局面的候选点数看看超过30个就要警惕。如果确实需要兼顾边角大飞守可以把半径改成从“附近半径2以内的棋子”扩展到“附近半径2以内的空位”而不是所有空位。另外还可以给候选点总数加一个硬上限超过60个时按粗评分排序后只取前60个保证最坏情况也能在几百毫秒内返回。4.4 棋力时好时坏启发式排序没做α-β等于白剪现象AI有时能连续进攻有时突然下一手远离战场的废棋。如果棋力不稳定先检查generateCandidates返回的候选顺序是不是固定的从上到下扫描。若顺序固定α-β剪枝的排序优势完全发挥不出来因为运气不好时先搜到的全是烂棋后面的好棋没机会做alpha更新也就没机会剪枝。解决在generateCandidates返回前先对候选点做一次快速评分按从高到低排序。不需要精确评估只需要能看得出哪些点是“明显有棋”的那些。我一般在候选点生成阶段只检查这个点周围八个方向里有没有能形成活三以上潜在棋型的趋势给一个粗糙分直接插入排序。这一步不加到总耗时里却能显著提高剪枝效率。5. 让四层AI更聪明置换表、候选点排序和一条可验证的棋力路线5.1 给四层搜索加一个置换表重复局面的后悔药基础版本跑通后棋力提升最明显且代码改动最小的一步是加置换表。置换表的核心思想是同一个棋盘局面可以从不同落子顺序到达比如A点先下再下B点跟B点先下再下A点最终棋盘状态完全一样但搜索树会重复计算两次。用哈希表缓存已搜索局面的分数和深度再次遇到相同局面时直接取缓存结果。实现时用zobrist哈希给每种棋子、每个坐标分配一个64位随机数每次落子和撤销时对棋盘哈希值做异或更新。哈希表项里要保存搜索深度、类型精确值/下界/上界和分数。取缓存时只有深度满足条件时才能直接用。这个优化能把中盘搜索的重复计算量再砍掉一半但对四层搜索来说收益已经很明显了。struct TTEntry { uint64_t hash 0; int depth -1; int score 0; int flag 0; // 0精确 1下界 2上界 }; std::unordered_mapuint64_t, TTEntry transTable; int probeTT(uint64_t hash, int depth, int alpha, int beta) { auto it transTable.find(hash); if (it transTable.end()) return NEG_INF; const TTEntry e it-second; if (e.depth depth) return NEG_INF; if (e.flag 0) return e.score; if (e.flag 1 e.score beta) return e.score; if (e.flag 2 e.score alpha) return e.score; return NEG_INF; }注意置换表必须在棋局重启时清空同时哈希表的键值要包含当前轮到谁。同一盘面轮到白方和轮到黑方是完全不同的搜索方向混用会直接导致棋力崩溃。这个坑我踩过血泪记忆。5.2 三种可以落地的棋力验证方法验证AI棋力不能靠自我感觉至少要做三个层面的测试。第一层是“必杀测试”在棋盘上摆几个两步必杀的局面AI必须在第一步就找到连杀点。这一步检验搜索完整性和评估函数是否偏科。第二层是“防守测试”让AI面对一个对手已形成活三的局面看它能不能优先堵住威胁而不是自己去进攻。如果它跑去自己冲四说明防守权重低调整评估函数里的对称负分比例。第三层是和真人长期对战这是最有效的整体验证。还有一个实用技巧把深度四层和深度三层的AI都挂到一个命令行程序里中间隔一场让两个AI互下10盘统计深度四层的胜率。如果四层只比三层高5个百分点说明评估函数区分度不够加多少层都没意义。我自己的经验是评估函数的权重大约占整体棋力七成搜索深度占两成剪枝优化只占一成。这套代码从头拆下来牛角尖都在评估函数和边界恢复上。最让我吃亏的一次是撤销棋子时忘了把totalMoves减回去导致后手方永远以为自己在空棋盘开局AI前五步全把棋下在天元。这种问题不会让程序报错只会让棋力表现得像个智力障碍排查起来极其折磨。后来我把所有会修改棋盘状态的函数集中到类方法里并且每次修改必须成对出现这个问题才绝迹。希望这篇笔记能帮你少走几段弯路四层AI的代码量不大但每一行都值得自己亲手敲一遍。本文还有配套的精品资源点击获取