C++五子棋AI对战实现：从数据结构到博弈树搜索

1. 整体设计与开发思路1.1 从零开始做一个能跑起来的五子棋程序C五子棋人机对战这个项目几乎是每个学过C的人都绕不开的练手关卡。它不像学生管理系统那样只有增删改查的枯燥操作也不像计算器那样逻辑过于单薄它天然包含了棋盘数据结构设计、输入输出交互、规则判断、状态管理以及最吸引人的AI博弈逻辑。哪怕只是做一个最基础的控制台版本你也能把一个学期学到的语法知识点真正串起来。我先说结论这个项目最适合三类人。第一类是C语法刚学完、正处于“啥都会一点但写不出完整项目”阶段的初学者第二类是想用图形库或Qt做游戏但还没准备好、先在控制台里练逻辑的准游戏开发者第三类是单纯想搞懂五子棋AI是怎么思考的算法爱好者。无论你属于哪一类从控制台版开始做都是投入产出比最高的选择。我做的这个版本没有用任何第三方库全程标准C一个cpp文件搞定核心逻辑编译环境用VS或g都行。棋盘大小、胜利条件、AI搜索深度这些参数全部做成宏定义或可配置变量方便后续扩展。1.2 为什么选控制台版而不是Qt或EasyX很多人的第一个疑问是五子棋这种游戏不做图形界面还能玩吗答案是不仅能玩而且对学习更有利。道理很简单图形界面解决的是“怎么把棋盘画出来”的问题而五子棋的核心价值在于“怎么判断输赢”和“怎么让AI下棋”。如果你一上来就用EasyX画棋盘、用鼠标事件接收落子你会发现代码里80%的内容都在处理绘图刷新事件回调真正跟五子棋规则相关的逻辑反而被挤到角落。而且图形库的安装配置本身就劝退了一批人——搜一下“error: microsoft visual c 14.0 or greater is required”有多少人踩坑就知道了。控制台方案的优势有三个零依赖、开箱即用、逻辑透明。棋盘用二维数组表示玩家用坐标输入落子AI通过算法计算落子位置整个过程所有决策都发生在你写的代码里配合cout输出棋盘的ASCII画法每一步都有完整的视觉反馈。用十乘十或十五乘十五的网格字符画输出终端里的显示效果相当清晰配合 system(cls) 做清屏重绘玩起来的流畅感是够的。等你把控制台版里的AI逻辑打磨到能下赢普通人了再考虑用Qt或EasyX给它套上一层好看的皮那个成本非常低。这就好比你先学会了做菜再研究摆盘而不是先研究摆盘却不会做菜。1.3 项目功能拆解和模块划分这个项目我把它拆成四大模块棋盘与状态管理、落子规则与胜负判定、人机交互界面、AI决策引擎。每个模块各司其职模块之间通过明确的数据接口通信这个思路本身就是工程化开发的基本功。棋盘与状态管理负责维护一个二维数组记录每个交叉点的状态空、黑子、白子同时提供棋盘初始化、副本复制、位置合法性查询这些底层操作。落子规则与胜负判定负责处理“这个位置能不能下”和“下了之后有没有人赢了”两个核心问题。人机交互界面负责打印棋盘、接收玩家输入、显示游戏结果、处理异常输入。AI决策引擎则是整个项目最值钱的部分它根据当前棋盘状态通过评估函数和搜索算法选择一个最优落子点。这四个模块之间没有循环依赖——UI调用棋盘模块做展示调用游戏规则模块做校验AI模块只读棋盘状态并返回坐标。这个清晰的单向依赖关系让我后面调bug的时候省了大量时间也建议你在动手写代码前先把这个结构画出来。// 简单的模块划分示意 // ChessBoard: 棋盘数据 基本操作 // GameRules: 落子合法性 五连判断 // AIEngine: 评估函数 搜索决策 // GameUI: 输出棋盘 输入交互 主循环2. 棋盘表示与核心数据结构设计2.1 二维数组存储棋盘状态五子棋棋盘本质上就是一个网格最自然的数据结构就是二维数组。标准五子棋是十五路15×15也有下十九路的但十五路最经典我最终选择了15×15。我定义棋盘的存储方式是一个int类型的二维数组0表示空位1表示黑子玩家2表示白子AI。有人喜欢用枚举我承认枚举可读性更好但int在处理AI评分计算时更直接而且没有任何性能浪费项目规模小int完全够用。const int BOARD_SIZE 15; int board[BOARD_SIZE][BOARD_SIZE]; // 0空 1黑(玩家) 2白(AI) void initBoard() { for (int i 0; i BOARD_SIZE; i) { for (int j 0; j BOARD_SIZE; j) { board[i][j] 0; } } }这里有一个细节值得留意15×15的棋盘数组索引范围是0到14。很多人在写循环的时候会惯性写成i 15然后就会发现某次下棋时数组越界程序莫名其妙崩溃。我建议你在所有涉及棋盘边界的循环里统一写成i BOARD_SIZE同时把BOARD_SIZE定义成const常量不要到处用魔法数字。2.2 坐标体系与玩家输入的映射棋盘输出到控制台后玩家怎么告诉程序他想下在哪最直接的方式是输入两个数字分别代表行和列。但这里有个隐藏的设计决策坐标是从0开始还是从1开始。如果你让玩家输入0到14的坐标程序不用做任何转换直接拿索引访问数组非常方便。但实际体验后你会发现普通人习惯从1开始数格子你打印的棋盘上标号如果也是从1开始玩家输入就更自然。因此我采用了“显示坐标为1到15内部索引为0到14”的方案玩家输入后统一减一。int row, col; cin row col; row--; // 转换为0基索引 col--; if (isValidMove(row, col)) { board[row][col] PLAYER; } else { cout 非法落子请重新输入 endl; }棋盘的可视化用行列标号配合符号输出。我用表示空位、●表示黑子、○表示白子但控制台环境下中文字符和特殊符号的对齐有时会出问题所以实际项目里我改用了、X、O三个ASCII字符对齐稳定、跨平台无乱码。如果你用的是Windows新终端或VS Code的集成终端●和○能正常显示那视觉效果会更棒这个取决于你的运行环境自己实测一下就行。2.3 落子合法性与边界检查落子合法性判断是这个项目最简单的函数之一但它处在所有功能的底层一旦出错整个游戏都会崩溃。逻辑只有两条坐标是否在棋盘范围内以及该位置是否已经被占用。bool isValidMove(int row, int col) { if (row 0 || row BOARD_SIZE || col 0 || col BOARD_SIZE) { return false; } return board[row][col] 0; }这个函数本身没有技术含量但它被玩家输入处理、AI决策、悔棋功能反复调用我把它做成一个独立函数而不是内联判断就是为了避免在多个地方都写一遍边界条件。以后如果你要扩展禁手规则三三禁、四四禁、长连禁也只改这一个文件不会到处失控。3. 胜负判定算法实战3.1 每次落子后检测五连五子棋的胜负判定就是检查落子位置周围有没有形成五个同色棋子的连线。很多初版实现会写一个checkWin()函数遍历整个棋盘每下一步棋就把全盘扫描一遍。这样做虽然不会错但完全没有必要——你只需要检查新落下的那颗棋子周围的四个方向就够了因为新棋局的变化只可能由最后一颗子引起。方向有四个横向、纵向、主对角线左上到右下、副对角线右上到左下。每个方向上的五连判定逻辑是从这个落子点出发向某个方向的正向数同色棋子个数再向反向数同色棋子个数加在一起如果大于等于5就说明赢了。bool checkWin(int row, int col) { int directions[4][2] {{1, 0}, {0, 1}, {1, 1}, {1, -1}}; int player board[row][col]; for (int k 0; k 4; k) { int count 1; // 正向延伸 for (int i 1; ; i) { int nr row directions[k][0] * i; int nc col directions[k][1] * i; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE || board[nr][nc] ! player) break; count; } // 反向延伸 for (int i 1; ; i) { int nr row - directions[k][0] * i; int nc col - directions[k][1] * i; if (nr 0 || nr BOARD_SIZE || nc 0 || nc BOARD_SIZE || board[nr][nc] ! player) break; count; } if (count 5) return true; } return false; }3.2 搜索方向向量与循环边界上面代码里directions[4][2]这个二维数组是方向向量的经典用法用{1,0}表示横向、{0,1}表示纵向、{1,1}和{1,-1}分别表示两条对角线。这样做的好处是循环代码不需要写四遍你只需要遍历四个向量就可以覆盖所有检查方向。边界条件是最容易写错的地方。在正向延伸的循环里我用了for (int i 1; ; i)这种无边界条件的写法然后在循环体内部用if检查新坐标是否越界越界就break。这种方式的优点是不需要事先计算延伸步数代码短而且不会漏掉边界情况。有人会把边界检查写成nr BOARD_SIZE || nc BOARD_SIZE之后就break但容易漏掉nr 0 || nc 0的反向边界检查。这个问题在调bug时非常隐蔽——你在棋盘中央落子时发现不了问题但只要在左上角或右下角落子程序就可能访问到负索引读到了数组前面的垃圾数据。我自己当初做这个项目时就因为这个原因出现过AI在棋盘边缘判断出“诡异胜利”的情况排查了半天才发现是反向延伸没做下界判断。3.3 平局判定与其他结局分支平局的情况是棋盘满了但没人连成五子。判定方式很简单每一次落子有效后检查棋盘是否全满。bool isDraw() { for (int i 0; i BOARD_SIZE; i) { for (int j 0; j BOARD_SIZE; j) { if (board[i][j] 0) return false; } } return true; }注意判断顺序落子后先判断是否赢再判断是否平局。如果棋盘满了同时刚好有人赢了应该优先判胜。这与大多数五子棋规则一致先达成五连的人获胜不存在“满盘和五连同时发生”的模糊地带。4. 核心功能五子棋AI算法设计与实现4.1 最简单的AI基于评分函数的贪心AI算法是这个项目的灵魂也是刷掉一大批人的地方。我从简到复杂给你完整讲一遍设计路径你先能跑起来再追求强大。第一版AI用贪心策略遍历所有空位对每个空位分别评估“如果我下在这我的得分”和“如果对手下在这对手的得分”两者相加作为这个位置的最终评分取最高分的那个位置下棋。int evaluatePoint(int row, int col, int player) { // 模拟在(row, col)落子后向四个方向统计棋子数量 // 返回一个评分 } pairint,int aiMove() { int bestScore -1; int bestRow -1, bestCol -1; for (int i 0; i BOARD_SIZE; i) { for (int j 0; j BOARD_SIZE; j) { if (board[i][j] ! 0) continue; int attackScore evaluatePoint(i, j, AI_PLAYER); int defendScore evaluatePoint(i, j, HUMAN_PLAYER); int totalScore attackScore defendScore; if (totalScore bestScore) { bestScore totalScore; bestRow i; bestCol j; } } } return {bestRow, bestCol}; }“攻防结合”是贪心AI的核心思想只考虑进攻提升自己的连线潜力或者只考虑防守压制对手的连线潜力都会导致AI出现严重偏科。attackScore defendScore的公式虽然简陋但它让AI同时兼顾了两头。我见过不少初学者只写了进攻分结果就是AI永远在自嗨不去堵对手的活三被玩家轻松下赢。4.2 棋型评估表的设计评估函数是评分式AI的地基。它做的事情是假设某个玩家在某位置落子后沿四个方向看它形成了什么棋型然后根据棋型的威胁重量级给分。我把棋型分成五个等级五连已获胜、活四两端都开放的四连下一步必赢、冲四一端被堵的四连但能逼对手防守、活三两端开放的三连下一步可变成活四、眠三一端被堵的三连以及活二、眠二等。评分表长这样int patternScore(int count, int openEnds) { if (count 5) return 1000000; // 五连 if (count 4) { if (openEnds 2) return 100000; // 活四必赢 if (openEnds 1) return 10000; // 冲四 } if (count 3) { if (openEnds 2) return 8000; // 活三 if (openEnds 1) return 1000; // 眠三 } if (count 2) { if (openEnds 2) return 500; if (openEnds 1) return 100; } if (count 1) return 10; return 0; }这里的openEnds表示两端是否开放向某个方向延伸时如果紧挨着棋型的两端是空格就是开放端如果越界或被对方棋子堵住就是封闭端。五连和活四的分数拉开一个数量级是为了让AI优先赢棋而不是贪图棋型美观。不建议用简单的“连续棋子数乘以固定权重”来做评估比如count*100这种。因为五子棋的棋型价值不是线性的活三的威胁远超两个活二的和不用梯度式的分数表AI会出现“过度防守消极棋型、放走关键进攻点”的智力低下表现。4.3 方向聚合计算评估分值evaluatePoint的完整实现需要沿四个方向分别统计连子数量和开放端数然后查表累加。每个方向的统计流程是从落子点出发向正方向数连续同色棋子向反方向数连续同色棋子再检查两端的后续格子状态。int evaluatePoint(int row, int col, int player) { int totalScore 0; int directions[4][2] {{1, 0}, {0, 1}, {1, 1}, {1, -1}}; for (int k 0; k 4; k) { int count 1; int openEnds 0; // 正方向统计 int r row directions[k][0], c col directions[k][1]; while (inBoard(r, c) board[r][c] player) { count; r directions[k][0]; c directions[k][1]; } if (!inBoard(r, c)) { // 越界视为封闭 } else if (board[r][c] 0) { openEnds; } // 反方向统计 r row - directions[k][0]; c col - directions[k][1]; while (inBoard(r, c) board[r][c] player) { count; r - directions[k][0]; c - directions[k][1]; } if (!inBoard(r, c)) { // 越界视为封闭 } else if (board[r][c] 0) { openEnds; } totalScore patternScore(count, openEnds); } return totalScore; }这里有一个重要细节统计openEnds时你只检查连续棋子的两端外面的第一个格子是不是空的不能继续往外延伸否则会把活二和活三混淆。比如一个三连两端各有一个空格它就是活三不需要管空格外面是什么。这个逻辑理解透了评估函数的问题就解决了一半。4.4 进阶极小化极大搜索与α-β剪枝如果对评分式AI的表现不满意想让AI变得“像人一样思考几步棋”就需要引入搜索算法。五子棋的博弈树本质是一个零和游戏我下一步你下一步双方轮流决策。极小化极大算法的思路是设AI为MAX方追求高评分玩家为MIN方追求低评分AI在模拟落子时选择分数最高的分支同时预测玩家在下一步会选择分数最低的分支来应对。int minimax(int depth, int alpha, int beta, bool isMaximizing) { if (depth 0) return evaluateBoard(); if (isMaximizing) { int best -INF; for (auto move : generateMoves()) { board[move.row][move.col] AI; int score minimax(depth - 1, alpha, beta, false); board[move.row][move.col] 0; best max(best, score); alpha max(alpha, best); if (beta alpha) break; // β剪枝 } return best; } else { int best INF; for (auto move : generateMoves()) { board[move.row][move.col] HUMAN; int score minimax(depth - 1, alpha, beta, true); board[move.row][move.col] 0; best min(best, score); beta min(beta, best); if (beta alpha) break; // α剪枝 } return best; } }α-β剪枝能让搜索树减少约一半到四分之三的节点。如果没有剪枝深度为4的搜索在最坏情况下要评估15×15×14×13≈4万多个节点算起来非常吃力加了剪枝后配合合理的走法排序先评估启发式分数高的位置同样的深度只需评估几千个节点速度质的飞跃。4.5 搜索深度与性能的实际平衡体验过搜索算法后你会发现深度是性能的最大瓶颈。控制台版五子棋AI深度设为4已经能让一般玩家感觉到“有点聪明”了再往上到6单步思考时间就会明显卡顿尤其是在后期棋盘上可落子点变多的时候。我实际测试的数据是这样的CPU为普通英特尔i5Debug模式搜索深度可用落子点约50个用时2秒回0.1s3明显可感知约0.3-0.8s4停顿但可接受约2-5s6长时间卡顿10-30s所以性能优化的关键是缩小候选点集合而不是无脑提高搜索深度。业内常用的办法叫“启发式裁剪”只搜索当前棋盘上已有棋子周围两格内的空位远处的空位在当前阶段几乎不可能是最优落子点。这样可以把每层的候选点从200直接压缩到20-30个同深度下搜索速度能提升十倍不止。5. 完整实现流程与交互设计5.1 游戏主循环架构游戏主循环是连接人机交互和AI的核心骨架我采用典型的“轮次驱动”模型先玩家落子判断是否结束再AI落子判断是否结束如此循环直到终局。为了保证人机公平同时约定玩家执黑先行AI执白后行。int main() { initBoard(); bool isPlayerTurn true; while (true) { system(cls); // 清屏重绘 printBoard(); if (isPlayerTurn) { int row, col; cout 轮到你了输入行和列1-15; cin row col; row--; col--; if (!isValidMove(row, col)) { cout 位置无效请重新输入 endl; system(pause); continue; } board[row][col] HUMAN; if (checkWin(row, col)) { printBoard(); cout 恭喜你赢了 endl; break; } } else { cout AI思考中... endl; auto aiMove getAIMove(); board[aiMove.first][aiMove.second] AI; if (checkWin(aiMove.first, aiMove.second)) { printBoard(); cout AI获胜再来一局 endl; break; } } if (isDraw()) { printBoard(); cout 平局 endl; break; } isPlayerTurn !isPlayerTurn; } return 0; }这个循环看起来简单但“继续/重新开始”的处理是个容易忽略的细节。上面代码里的break会让程序直接退出玩家想再来就得重启程序体验很差。更好的做法是把整个循环包在一个while(true)大循环里结束对局后问一句“是否继续”根据输入重置棋盘再开一局。这个小改动会让项目的完整度上一个台阶。5.2 棋盘打印与清屏刷新控制台界面的体验好坏很大程度取决于你怎么处理刷新。一开始我用的是“每次落子后就不断cout输出新棋盘”不做清屏结果就是终端里旧棋盘一遍遍往上滚新棋盘在底部玩久了根本找不到当前状态在哪。后来改成system(cls)加printBoard()的组合每轮开始前清一次屏、再打印一次棋盘界面就清爽了。system(cls)是Windows专属命令在Linux/macOS下需要换成system(clear)。我用了一个预处理指令做跨平台适配#ifdef _WIN32 #define CLEAR_SCREEN() system(cls) #else #define CLEAR_SCREEN() system(clear) #endif这样在Windows和Linux上都能编译运行。如果你在VS Code的终端里跑Windows下默认就是cmdcls没问题如果你用的是PowerShell它也兼容cls。5.3 异常输入的处理方式关于玩家输入我踩过一个大坑用户输入了非数字字符比如输了个abc然后cin row读入失败输入流进入错误状态之后的每一次cin都会直接跳过程序立刻陷入死循环。这几乎是控制台版小游戏最容易翻车的地方。解决方案是每次读取后检查cin的状态如果失败就用cin.clear()恢复输入流并用cin.ignore(...)清掉缓冲区里的垃圾字符。int row, col; while (!(cin row col)) { cin.clear(); cin.ignore(1024, \n); cout 请重新输入有效的整数坐标; } cin.ignore(1024, \n); // 清掉多余字符这段代码我强烈建议所有C控制台游戏都加上。别觉得丑没有它你的程序在别人手上一输入字母就直接卡死。这种问题在真实的用户测试中暴露得极快如果你体验过关这是个加分项。5.4 代码组织从单文件到多文件我一开始把所有代码都堆在一个main.cpp里整个文件300多行能跑但很臃肿。调试的时候找一个函数得翻半天滚动条。后来做了一次代码重构拆成了chess_board.h/cpp、game_ai.h/cpp、main.cpp每个文件的职责清晰了编译命令也变成了多文件编译。# 多文件编译示例 g main.cpp chess_board.cpp game_ai.cpp -o gomoku.exe如果你用VS Code需要先配置好tasks.json里的编译参数把新加的cpp文件加进去。多文件编译对初学C的人来说是一个不小的门槛但它同时是通往工程化的必经之路你可以等单文件版本跑通之后再做这一步不要一开始就给自己增加配置负担。6. 调试经验与常见问题排查6.1 编译错误排查从环境配置到语法细节这个项目的编译错误大多集中在几个经典位置。第一种是编译器版本不兼容导致的报错比如error: max is not a member of std这可能是因为你没有包含algorithm头文件。处理方式很简单把用到的所有STL头文件都写上别嫌多。第二种是Windows平台下特有的 “error: microsoft visual c 14.0 or greater is required”这个报错和你的代码无关而是Python包或Node插件在安装依赖时找不到合适的MSVC编译器导致的。如果你在配置VSCode的C环境时遇到它最干净的解决办法是安装Visual Studio的“使用C的桌面开发”工作负载或者单独安装“C生成工具”。第三类坑是编码问题。Windows中文系统下控制台默认编码是GBK如果cpp文件是UTF-8编码cout中文字符串可能显示乱码。解决办法有两个一是源文件保存时选GBK编码二是在代码最顶部加system(chcp 65001 nul);把控制台切换成UTF-8。我推荐后者因为它对不同编辑器更友好只是要注意加了这个后每次运行都有一点延迟。6.2 逻辑BugAI不堵棋、乱下棋的调试流程AI出现不堵棋、乱下棋的“智障行为”是调试中最常见的问题。我的排查顺序是先打印每个候选位置的评分看评分是否合理再检查评估函数里openEnds的计算是否准确尤其是有边界棋子时最后确认AI的攻防分数权重是否失衡。举个例子我曾经发现AI在对手已经形成活三时不去堵中间的空位反而去边角发展自己的棋型。打印了评分后我才发现我的进攻分权重是防守分的2倍活三的威胁分被压得过低。调整权重后AI才表现出“知道先防守”的理性行为。一般来说AI不合理的决策根源不是算法本身而是评估函数的数值设计没调好。建议你多打印、多模拟、多对比这是调试博弈类AI的黄金法则。6.3 性能优化落子慢的三大原因如果AI落子非常慢超过十秒通常是三个原因之一评估函数本身效率太低每评估一个点都要遍历全盘搜索树的候选点集没有裁剪每个空位都进入了搜索分支std::vector或其他动态内存分配在搜索热点里频繁调用。针对第一个原因评估一个点的分数时不需要遍历全盘只需检查以该点为中心的4个方向、每方向10个格子的局部区域。针对第二个原因用“启发式裁剪”只搜索已有棋子邻域内的空位或只取评分Top N的空位进入搜索。针对第三个原因优先把递归搜索里频繁调用的临时变量放到栈上避免在递归内部构造vector。我用这些优化后深度4的搜索时间从最初的十几秒降到了3秒以内对控制台版游戏已经非常可用了。6.4 常见问题速查表问题现象可能原因解决方案棋盘上的数字/符号错位中文字符宽度不一致统一使用ASCII字符显示棋盘输入字母后程序卡死cin进入错误状态使用cin.clear() cin.ignore()恢复AI从不堵对手的活三防守分权重过低检查evaluatePoint中AI与对手分权重比例程序在坐标15时崩溃数组越界检查所有循环边界统一用BOARD_SIZE常量编译提示找不到头文件环境变量或包含路径错误检查VS Code的c_cpp_properties.json配置中文输出乱码控制台编码与源文件编码不一致使用system(chcp 65001)或调整源文件编码7. 扩展思路与进阶方向控制台版稳定跑通后扩展方向非常多。最直接的一步是换成Qt或EasyX做图形界面棋盘用绘制方式输出落子用鼠标点击交互体验会比控制台好一个数量级。同时你在控制台版本里写的棋盘逻辑、AI评估代码可以完全复用只需要把UI层替换掉。AI方面可以引入机器学习思路比如用蒙特卡洛树搜索代替传统的极小化极大搜索或者用神经网络训练一个走子策略。这个门槛较高但如果对AI感兴趣五子棋是个很好的起点比围棋简单得多又比井字棋复杂得多卡在难度曲线的甜点位置。还可以加入更多对局功能比如双人本地对战、悔棋、保存复盘、难度选择不同AI深度对应不同难度、计时器。我当时加了一个“AI执黑先手”的模式靠先手优势AI难度更高用同一个AI逻辑就做出了两种难度体验性价比极高。如果你打算把这个项目写进简历建议补充性能对比数据、评估分数可视化、以及你自己对算法的改进点。C项目不能只会“写出能跑的代码”要能说清楚为什么这样设计、瓶颈在哪、怎么优化这些思考过程在面试里比代码本身更值钱。最后分享一个个人体会五子棋这个小项目我从最初200行的粗糙版本一路迭代到带搜索算法、跨平台、多文件的完整版本每一步都踩过不同的坑。但正是因为踩过这些坑我才真正理解了什么叫做“用C解决问题”而不是“背语法”。如果你的代码能顺畅跑起来、能下赢你身边的朋友这个项目的学习目标就已经达成了大半至于AI能不能打赢职业选手那是另一段旅程的事。