基于C++与α-β剪枝算法实现会思考的五子棋AI

简介本资源是一套基于C实现的五子棋AI人机对战系统源码面向算法初学者、计算机专业学生及AI实践开发者聚焦博弈论基础算法在经典棋类中的落地应用。项目以博弈树为核心框架集成α-β剪枝优化策略显著提升搜索效率当前支持四层深度推演在保证响应速度的同时兼顾决策合理性适用于课程设计、算法实验与小型AI对弈开发参考。压缩包共47个文件含3个核心头文件.h、3个实现源文件.cpp、1个Visual Studio解决方案.sln及可执行程序.exe辅以调试符号.pdb、编译中间文件.obj/.tlog等工程必需组件整体体积2.64MB结构完整、开箱即编译运行。已有74人学习下载代码模块划分清晰——AI逻辑封装于AI.h/AI.cpp哈希表加速落子评估见Hash_Table.h/.cpp主界面与游戏流程由chess_test.cpp统一调度便于读者理解算法分层设计并开展剪枝策略调优或搜索深度扩展。1. 项目缘起从“能下”到“会思考”的AI五子棋几年前我写过一个简单的五子棋人机对战程序那时的AI逻辑简单粗暴遍历棋盘上所有空位计算每个位置对自己和对手的“威胁值”然后选一个分数最高的地方落子。这种基于“静态评估”的AI对付新手还行稍微有点经验的玩家很快就能找到它的套路——它只会看眼前一步的“局部最优”缺乏长远的“战略眼光”。玩家很容易通过设置一些两三步之后的“陷阱”来引诱AI上钩从而轻松获胜。这让我开始思考如何让AI真正“会思考”答案就是引入“博弈树”和“搜索”。五子棋的棋盘有15*15225个交叉点理论上每一步都有上百种可能的下法。如果AI要思考未来N步的局面那么需要评估的局面数量将是天文数字搜索空间随深度指数级增长。这就是所谓的“组合爆炸”问题。为了让AI在有限的时间内进行更深度的思考必须使用优化算法来“剪掉”那些明显不好的分支避免无谓的计算。α-β剪枝算法正是解决这个问题的经典钥匙。它能让AI在搜索时像一位经验丰富的棋手一样快速排除掉那些“一看就不行”的走法把宝贵的计算资源集中在最有希望的几个选择上。这个项目就是基于C实现一个运用了博弈树和α-β剪枝算法的五子棋AI。目前这个AI已经能够“向前看”四层局面即思考“我下-对方下-我下-对方下”这四步之后的各种可能并从中选择对自己最有利的走法。它不再是一个只会“见招拆招”的愣头青而是一个开始懂得“谋篇布局”的对手。接下来我将详细拆解这个AI的“大脑”是如何构建和工作的。2. 核心架构棋盘、评估与搜索的三角支撑一个五子棋AI的核心可以抽象为三个相互协作的模块棋盘表示与操作模块、局面评估函数模块和博弈树搜索模块。这三个模块构成了AI的“感官”、“直觉”和“逻辑推理”系统。2.1 棋盘的数据基石二维数组与位运算棋盘是AI感知世界的全部。在C中最直观的表示方法是一个15x15的二维数组。我们可以用简单的整数来表示状态比如0代表空位1代表黑棋AI2代表白棋玩家。这种表示法简单易懂但在进行大量棋盘状态复制和比较时搜索算法需要频繁生成和回溯局面效率会成为瓶颈。一个更高效的方案是使用位棋盘。我们可以用两个unsigned long long类型的变量假设棋盘小于8x8或者用多个unsigned int组成的数组来分别表示黑子和白子的位置。每一位bit对应棋盘上的一个交叉点1表示有子0表示无子。这样判断某条线上是否有连续五子、计算某个位置的“潜力”等操作都可以通过快速的位运算与、或、移位来完成速度远超遍历数组。不过位棋盘的实现和调试相对复杂对初学者不够友好。在本项目的初始版本中为了清晰展示算法逻辑我依然选择了二维数组作为棋盘模型。在实际的性能优化版本中可以逐步替换为位棋盘。棋盘模块还需要提供一些基础功能makeMove(x, y, player): 在坐标(x, y)处放置player的棋子。undoMove(x, y): 撤销上一步落子搜索回溯时必需。isWin(x, y, player): 判断在(x, y)落子后player是否获胜。这通常通过从落子点向四个方向横、竖、左斜、右斜延伸检查是否有连续五个同色棋子来实现。getValidMoves(): 获取当前所有可以落子的空位。一个重要的优化是启发式排序不要返回所有空位而是只返回有意义的空位。例如只考虑那些在已有棋子周围一定范围比如两格内的空位。一个孤零零在角落的空位在开局和中局阶段几乎不可能是好棋。预先对候选落子点按“潜在价值”排序能极大地提升α-β剪枝的效率。2.2 局面的价值判断评估函数的设计哲学评估函数是AI的“直觉”。给定一个棋盘状态它需要快速给出一个分数量化当前局面对AI的有利程度。这是整个AI“棋力”的灵魂所在也是最需要精心调校的部分。一个基础的评估函数会扫描整个棋盘为AI黑和玩家白分别计算“活四”、“冲四”、“活三”、“眠三”、“活二”等棋型的数量。不同的棋型具有不同的威胁等级对应不同的分数权重。例如活四两头无阻挡的四连子必杀棋型分数极高如10000分。冲四一头被堵的四连子下一步即可成五威胁极大分数也很高如1000分。活三两头无阻挡的三连子可以发展成活四是进攻的主要手段如500分。双活三、冲四活三等组合攻击分数应具有叠加效应甚至更高。评估函数的最终得分通常是AI的分数 - 玩家的分数。这样一个对AI有利的局面会得到正分对玩家有利的局面得到负分。注意评估函数的设计需要平衡“准确性”和“速度”。一个过于复杂的评估函数比如考虑所有形状、所有距离虽然判断更准但计算耗时太长会导致搜索深度变浅。一个过于简单的评估函数则无法准确反映局面优劣。我的经验是先实现一个中等复杂度的评估函数确保搜索算法能稳定运行然后再通过大量自我对弈或与人对弈来调整权重。例如你可能发现AI过于注重进攻而忽视防守这时就需要适当提高对手“活三”等威胁棋型的负权重。2.3 大脑的思考过程极小化极大算法与α-β剪枝这是AI的“逻辑推理”核心。它的基本思想是模拟双方都绝对理性、都采取最优策略的对弈过程。2.3.1 极小化极大算法假设AI执黑最大化玩家玩家执白最小化玩家。AI在思考时会构建一棵博弈树根节点是当前棋盘状态AI黑走棋。AI会考虑所有可能的落子点子节点。对于每一个子节点AI会想“如果我走这里对手白会怎么应对”于是AI为每个自己的落子点继续模拟玩家白的所有可能应对孙节点。如此递归下去直到达到预设的搜索深度或者某个节点已经决出胜负。在叶子节点终止搜索的节点调用评估函数得到一个分数。分数从叶子节点向上传递在AI黑的回合它总是选择能获得最大分数的分支因为AI希望自己赢。在玩家白的回合它总是选择让AI获得最小分数的分支因为玩家希望AI输即分数低。最终根节点选择那个能保证在最坏情况下对手最优应对依然得到最高分数的走法。这就是“在对手最聪明的反击下为我争取最好结果”的策略。2.3.2 α-β剪枝给思考装上“快进”键极小化极大算法需要遍历整棵树计算量巨大。α-β剪枝的核心思想是如果某个分支明显差于已知的另一个分支那么就没必要继续深入计算这个分支了。α阿尔法当前路径上AI最大化方至少能保证得到的最好分数。初始值为负无穷。β贝塔当前路径上玩家最小化方至多允许AI得到的分数。初始值为正无穷。在搜索过程中当在AI层Max层计算时如果发现某个子节点的返回值已经大于等于当前的β值那么玩家父节点的Min层绝对不会允许走到这个分支因为玩家会选择让AI分数更小的分支所以这个AI节点的其他兄弟节点就不用再搜索了剪枝。当在玩家层Min层计算时如果发现某个子节点的返回值已经小于等于当前的α值那么AI父节点的Max层绝对不会选择这个分支因为AI会选择分数更高的分支所以这个玩家节点的其他兄弟节点也不用再搜索了剪枝。一个生活化的比喻你在市场上买水果问第一家苹果5元一斤α5。问第二家时他一开始说“我的苹果分不同等级最差的6元...”。听到“6元”你立刻就知道他最差的都比我知道的最好的贵那最好的肯定更贵没必要再听他报完所有等级的价格了剪枝。α-β剪枝让AI避免了大量无效计算通常能将搜索效率提升数个数量级从而实现更深的搜索深度。3. 关键实现细节从理论到C代码理解了原理我们来看看在C中如何具体实现。项目的核心是一个AIPlayer类。3.1 搜索函数的递归实现这是算法的骨架一个典型的带α-β剪枝的Negamax框架实现Negamax是极小化极大算法的一种简化写法统一用分数的相反数在层间传递。// 假设棋盘类为 Board 评估函数为 evaluate(Board) 当前玩家颜色为 color (1:AI, -1:玩家) // 使用Negamax风格总是最大化当前玩家的分数 int AIPlayer::alphaBetaSearch(Board board, int depth, int alpha, int beta, int color) { // 终止条件达到深度限制或游戏结束 if (depth 0 || board.isGameOver()) { return color * evaluate(board); // 注意对当前玩家进行评估 } // 获取当前所有可行的走法并按启发式规则排序重要 vectorMove moves board.getOrderedMoves(); int bestValue -INFINITY; for (Move move : moves) { // 尝试走一步 board.makeMove(move.x, move.y, color); // 递归搜索对手走棋颜色取反深度减一 int value -alphaBetaSearch(board, depth - 1, -beta, -alpha, -color); // 撤销走子回溯 board.undoMove(move.x, move.y); // 更新最优值 if (value bestValue) { bestValue value; if (depth maxDepth) { // 记录根节点的最佳走法 bestMove move; } } // α-β剪枝核心逻辑 alpha max(alpha, value); if (alpha beta) { break; // 发生剪枝 } } return bestValue; }代码解析与踩坑点递归与回溯makeMove和undoMove必须成对出现。这是实现正确回溯的关键。我曾在早期版本忘记undoMove导致棋盘状态混乱搜索结果完全错误。分数传递Negamax写法中下一层的返回值要取负-alphaBetaSearch(...)再传回因为双方利益相反。同时传入的alpha和beta边界也要取负并交换-beta, -alpha。这是最容易出错的地方之一务必理解其对称性。启发式排序getOrderedMoves()函数至关重要。如果走法顺序是随机的α-β剪枝几乎无效。好的排序能让“看起来更好”的走法先被搜索从而更早地提升alpha值触发更多剪枝。我的排序规则是优先搜索靠近棋盘中心、靠近已有棋子的位置并且如果某一步能直接获胜成五或阻止对方获胜则将其排在首位。最佳走法记录注意if (depth maxDepth)这一行。我们只在递归的最顶层初始调用层记录最终选择的bestMove。在递归深处记录的走法不是AI最终要走的。3.2 评估函数的量化实现评估函数evaluate需要遍历棋盘。一个高效的做法不是每次全盘扫描而是增量更新每次落子只更新受该棋子影响的几条线上的棋型计数。但这实现起来较复杂。在初期我们可以采用全盘扫描虽然慢但正确性有保障。int AIPlayer::evaluate(Board board) { int aiScore 0; int humanScore 0; // 假设board提供了分析一条线的函数 // 这里简化表示遍历所有行、列、对角线分析其中的连子情况 for (每个需要检查的方向线) { LineInfo info board.analyzeLine(...); aiScore getScoreByPattern(info.blackPattern); humanScore getScoreByPattern(info.whitePattern); } // 一个重要的技巧加入位置权重 // 棋盘中央的位置通常比边角更有价值可以在基础分上乘一个位置权重系数 // aiScore * positionWeight[centrality]; return aiScore - humanScore; } int getScoreByPattern(Pattern p) { switch(p) { case FIVE: return 100000; // 成五直接返回极大值游戏结束 case LIVE_FOUR: return 10000; case DEAD_FOUR: // 冲四 case LIVE_THREE: return 5000; case SLEEP_THREE: // 眠三 case LIVE_TWO: return 500; // ... 其他棋型 default: return 0; } }评估函数调参心得分数尺度确保不同棋型之间的分数差距足够大。例如“活四”和“活三”的分数差如果太小AI可能无法意识到活四是立即的胜利威胁。攻防平衡初期我的AI进攻犀利但防守蠢笨。后来我发现原因在于评估函数中对“敌方活三”的负向惩罚不够。将humanScore中对应棋型的权重提高后AI的防守意识明显增强。终局处理当搜索深度到达叶子节点如果发现某一方已经赢了应该直接返回一个极大值或极小值比如±100000并立即停止对该分支的更深搜索这能节省大量计算。4. 性能优化与深度提升让AI思考得更远“推算四层”是一个起点但面对高手可能还不够。如何在不升级硬件的情况下让AI思考到五层、六层甚至更深4.1 迭代加深与时间控制不要一次性固定搜索4层。可以采用迭代加深策略先搜索1层得到最佳走法和分数。再搜索2层用第1层得到的最佳走法作为启发重新搜索。接着搜索3层、4层...设置一个时间限制比如每步5秒。在规定时间内能迭代到第几层就输出第几层的结果。这样做的好处是总能有一个可行结果哪怕时间仓促只搜了1层并且更深层的搜索可以利用浅层搜索的排序信息提高剪枝效率。在GUI中可以显示当前搜索深度让玩家感受到AI的“思考过程”。4.2 开局库与残局库开局库对于五子棋前几步有相当多的标准开局如花月、浦月等。我们可以预先存储这些开局及其公认的最佳应对。当AI发现当前局面存在于开局库中时直接使用库中的推荐走法无需搜索。这不仅能节省时间还能让AI走出职业的开局。残局库对于棋子已经非常密集的残局搜索深度需要极深才能算清。可以预先计算所有小规模棋盘例如最后20个空位以内的必胜、必败局面做成一个“残局数据库”。在搜索时如果遇到数据库中存在的情况直接查表返回结果这是质的飞跃。4.3 更高级的剪枝与搜索策略置换表这是一个“记忆化”技术。在搜索过程中不同的走子顺序可能到达相同的棋盘局面。置换表就是一个哈希表用来存储已经计算过的局面对应的最佳走法和分数估值。当再次遇到相同局面时直接查表避免重复计算。实现置换表需要解决哈希冲突和深度覆盖等问题是提升性能的大杀器。渴望搜索在α-β搜索中我们先用一个较小的窗口如[alpha, alphawindow]进行搜索如果返回的值在这个窗口内说明估值准确如果超出窗口即“渴望”失败再重新用正常窗口[alpha, beta]搜索。这有点像“先试探一下”很多时候能减少搜索量。多线程并行搜索现代CPU都是多核的。可以将根节点的不同子节点即AI的第一层候选走法分配给不同的线程同时进行搜索最后汇总结果。这能近乎线性地提升搜索速度。5. 项目构建、测试与对弈心得5.1 开发环境与项目结构我使用的是Visual Studio Code配合MSVC或MinGW编译器来开发这个C项目。项目结构清晰很重要FiveChessAI/ ├── src/ │ ├── main.cpp // 程序入口游戏主循环 │ ├── Board.cpp/.h // 棋盘类负责状态存储、落子、胜负判断 │ ├── AIPlayer.cpp/.h // AI核心类包含搜索和评估函数 │ ├── Evaluator.cpp/.h // 可独立出来的评估函数模块 │ └── GUI.cpp/.h // 图形界面如使用SDL2、Qt或简单的控制台图形 ├── include/ // 第三方库头文件 ├── lib/ // 第三方库文件 └── CMakeLists.txt // 跨平台构建配置使用CMake可以方便地在不同平台Windows/Linux/macOS上生成编译文件。对于初学者在VSCode中配置tasks.json和launch.json来实现一键编译调试也非常方便。5.2 如何测试与调试AI的棋力自我对弈让同一个AI执黑和白互相对下成千上万盘。统计胜率。调整评估函数权重后再对弈看胜率是否向预期方向变化。这是最基础的调参方法。与已知算法对战在网上寻找一些开源的、棋力已知的五子棋AI程序与自己的AI对战衡量水平。设立测试局面设计一些典型的杀棋、做棋、防守局面看AI能否走出正确的一步。例如一个“活三”局面看AI是选择进攻还是防守无关紧要的位置。输出调试信息在搜索时可以输出当前搜索的深度、主要考虑的走法及其估值、剪枝次数等。这有助于理解AI的“思考”过程发现评估函数的盲点。5.3 人机对战的体验与策略在与自己开发的这个4层AI对弈后我发现它已经具备基本战术意识能够识别并做出“活三”、“冲四”这样的基本攻击也能防守我的“活三”。它的弱点在于战略层面由于深度只有4层它对于需要超过4步才能形成的复杂攻击比如做一个“一子双杀”的陷阱缺乏预见性。我可以通过构造一些长线陷阱来击败它。先手优势明显在五子棋无禁手规则下先手黑方优势巨大。这个AI如果执黑进攻非常主动执白时如果前期防守出现疏漏很容易崩盘。要让AI更强除了前面提到的增加搜索深度和优化算法优化评估函数是提升棋力性价比最高的途径。例如加入对“势”的评估不仅计算现有棋型还要评估某个位置的发展潜力“这个点虽然现在没棋但未来可能形成多个好形”。这个项目从零开始构建一个会“思考”的棋类AI涵盖了博弈树、搜索优化、评估函数设计、算法到工程实现的全过程。它不仅仅是一个五子棋游戏更是一个理解经典人工智能搜索算法的绝佳范例。当你看到AI因为你写的几行代码而走出一手让你惊讶的“妙招”时那种成就感是无与伦比的。你可以继续挑战为它加入开局库、实现置换表甚至尝试用蒙特卡洛树搜索来改造它探索AI博弈的更多可能性。本文还有配套的精品资源点击获取