1. 从课程设计到能跑的人机对弈这个项目的真实门槛在哪五子棋人机对战这个题目几乎每一届学数据结构与算法课程的同学都会碰到。表面上看规则简单——横竖斜连成五个就赢棋盘就15×15好像随便写写就能交差。但我带过几届课程设计的经验告诉我真正能拿得出手的作品和勉强能跑的作业之间差距比想象中大得多。大部分人卡住的地方根本不是怎么判断五子连珠而是机器怎么下得像个人。这个项目的核心价值在于它把数据结构与算法课程里最枯燥的几个知识点——数组与稀疏矩阵、递归与回溯、启发式搜索、排序与优先队列、哈希去重——全部串进了一个看得见摸得着的场景里。你写出来的不是一段打印星号的代码而是一个真的能跟你对弈、偶尔还能赢你的对手。适合谁来参考如果你正在做课程设计或者想找一个能把算法知识落地的小项目练手这个方向非常合适。它不需要图形界面也能跑控制台版本照样能把算法核心讲清楚如果你想加界面后面接一个简单的绘图库也不难。我见过太多同学一上来就想着我要写个AI结果写出来的东西要么是随机落子要么是只会堵你最后一步的近视眼。问题出在他们跳过了最关键的思考机器评估一个棋局到底在评估什么这个问题的答案决定了你后面所有代码的组织方式。接下来我会把这个项目从数据结构选型到搜索算法落地再到实际调试中踩过的坑一层层拆开讲。2. 棋盘的数据结构选型为什么我不推荐一上来就用二维数组2.1 二维数组的直觉陷阱绝大多数人拿到题目的第一反应是开一个int board[15][15]0表示空1表示黑2表示白。这个选择本身没错简单直接访问是O(1)。但问题在于当你后面要做棋型识别、要做搜索树的节点复制时一个15×15的二维数组每次复制就是225个整数的开销。搜索树稍微深一点比如搜到第4层、第5层节点数量指数级增长内存和复制时间会迅速成为瓶颈。我在第一次做这个项目时就吃了这个亏。当时用二维数组做搜索深度设到4程序思考一步要等七八秒答辩的时候演示特别尴尬。后来我把棋盘换成了更紧凑的表示速度直接上来了。2.2 用一维数组加坐标映射一个更实用的做法是用一维数组int board[225]落子位置(r, c)映射到下标r * 15 c。这样做的好处是复制整个棋盘只需要一次内存拷贝比二维数组的逐行复制快很多。而且在做棋型扫描时一维数组配合方向偏移量比如水平方向偏移1垂直方向偏移15主对角线偏移16副对角线偏移14写起来反而更统一。// 方向偏移量定义配合一维数组使用 const int DIR[4] {1, 15, 16, 14}; // 水平、垂直、主对角、副对角这里有个细节要注意副对角线的偏移是14而不是-14因为我们统一按从左到右、从上到下扫描副对角线方向从右上往左下走时下标是减14但如果我们固定从每个点的左上方向右下方向扫描用14配合边界判断也能覆盖。这个偏移量的正负和扫描起点是很多人写棋型判断时最容易搞混的地方我后面会专门讲。2.3 稀疏表示只在有棋子的地方花心思15×15的棋盘一局棋下完通常也就几十个棋子绝大多数格子是空的。如果你的算法需要对所有已落子位置做遍历用稀疏表示会更省。可以用一个数组记录所有已落子的坐标再配一个哈希表或者简单的二维布尔数组做快速查重。这样遍历时只走有棋子的点而不是傻乎乎地扫225个格子。不过我要提醒一句稀疏表示在棋型识别时反而可能变麻烦因为判断五连需要看连续的空格和棋子。所以我的建议是——棋盘状态用一维数组存遍历候选落子点时用稀疏列表。两者结合既保证了棋型判断的方便又避免了无谓的全盘扫描。这个取舍是我踩过坑之后才想明白的一开始我非要用纯稀疏结构结果写棋型判断写了一堆边界特判代码又臭又长。3. 棋型识别机器看懂棋局的唯一途径3.1 五子棋里到底有哪些棋型机器要会下棋首先得能识别出当前局面里有哪些形状。五子棋的棋型按威胁程度从高到低大致有这么几类棋型名称形态描述威胁等级连五连续五个同色直接获胜活四四个连子两端都空必胜冲四四个连子一端被堵强制对手应对活三三个连子两端都空可发展为活四眠三三个连子一端被堵威胁较低活二两个连子两端都空布局阶段有价值识别这些棋型的本质就是沿着四个方向对每个已落子的点向两边延伸统计连续同色棋子的数量和两端是否被封堵。听起来简单但实际写起来边界处理和跳子情况比如中间隔一个空格的活三会让代码复杂度陡增。3.2 沿四个方向扫描的实现思路我的做法是对棋盘上每一个已落子的点分别沿水平、垂直、主对角、副对角四个方向向正负两个方向延伸记录连续同色棋子数和端点状态。核心函数大概长这样// 评估某个点在某个方向上的棋型 // 返回一个编码值表示连续长度和两端封堵情况 int evalDirection(int pos, int dir, int color) { int count 1; // 当前点本身算一个 int block 0; // 被封堵的端数 // 正向延伸 int p pos dir; while (inBoard(p) board[p] color) { count; p dir; } if (!inBoard(p) || board[p] ! EMPTY) block; // 负向延伸 p pos - dir; while (inBoard(p) board[p] color) { count; p - dir; } if (!inBoard(p) || board[p] ! EMPTY) block; return encode(count, block); }这段代码看着简单但inBoard的边界判断必须非常小心。一维数组下水平方向从第14列往右走会绕到下一行所以不能只判断下标是否在0到224之间还要判断列号是否越界。我当初就是这里没处理好导致水平方向的棋型判断在边界处出现莫名其妙的误判调了整整一个晚上。3.3 跳子棋型的处理真正让棋型识别变复杂的是跳子情况。比如黑 空 黑 黑 黑这种中间隔了一个空位但它依然是有威胁的。处理方式是在扫描时允许跳过最多一个空位继续统计后面的同色棋子。但跳子会让连续长度的定义变得模糊我的经验是把跳子单独作为一种棋型来识别不要硬塞进连续棋型的统计里。具体做法是在扫描时如果遇到一个空位记录下这个空位的位置然后继续往后看如果后面还有同色棋子就标记为跳子棋型并根据跳子后的连续长度单独给分。这个处理方式的好处是逻辑清晰坏处是代码量会增加。但对于课程设计来说能把跳子处理好已经能超过大部分同学的作品了。我见过很多作业版本完全忽略跳子结果机器经常漏掉对手的跳三威胁被一步带走。4. 评估函数让机器知道现在谁占优4.1 评估函数的本质是打分搜索算法需要一个标准来判断某个局面是好是坏这个标准就是评估函数。对于五子棋评估函数的基本思路是扫描整个棋盘统计我方和对方的各种棋型数量然后按棋型价值加权求和得到当前局面对我方的分数。棋型价值的设定直接决定了机器的性格。如果活四给10000分活三给1000分活二给100分那机器会非常激进地追求进攻。如果反过来把对方的活三扣分扣得很重机器就会变得保守优先堵你的棋。我一般会设两组权重一组用于评估自己的进攻价值一组用于评估对手的威胁价值最后用myScore - opponentScore * defenseFactor作为综合评分。defenseFactor通常设成1.2到1.5之间让机器稍微偏向防守一点这样不容易被对手的连续进攻打崩。4.2 全盘扫描的性能问题评估函数最直接的写法是每次需要评分时遍历棋盘上所有已落子的点对每个点做四个方向的棋型识别。这个开销在搜索树里会被放大很多倍。假设搜索深度是4每层有20个候选点那就有大约20^4 160000个叶子节点每个叶子节点都要做一次全盘评估每次评估要扫几十个点、每个点扫四个方向——这个计算量在普通电脑上跑起来会非常慢。优化的方向有两个。第一个是增量评估不每次重新算全盘而是只计算新落子带来的分数变化。落一个子只影响它周围四个方向上一定范围内的棋型其他区域的分数不变。这样每次评估只需要算局部速度能提升一个数量级。第二个是缓存棋型识别结果对于同一个点同一个方向如果棋盘没变识别结果就不变可以用哈希表缓存起来。不过增量评估的实现难度比全盘扫描高不少课程设计里如果时间紧可以先做全盘扫描保证正确性再考虑优化。4.3 一个容易忽略的细节评估的对称性评估函数必须保证对称性——如果我把棋盘黑白互换评估分数的正负应该反过来。这个性质听起来理所当然但实际写代码时很容易破坏它。比如你在统计棋型时如果对黑棋和白棋用了不同的代码路径就可能出现黑棋活三算1000分白棋活三算800分这种不对称。这种bug非常隐蔽因为机器自己跟自己下的时候看不出来只有当你手动构造对称局面去测试时才会暴露。我的建议是写一个专门的对称性测试函数随机生成一些局面把黑白互换后分别评估检查分数是否互为相反数。这个测试花不了多少时间但能帮你排除掉一大类隐蔽bug。5. 搜索算法从极小化极大到Alpha-Beta剪枝5.1 极小化极大搜索的基本框架五子棋是典型的零和博弈一方得分就是另一方失分。极小化极大Minimax搜索的思路是假设双方都走最优棋我来推演未来若干步找到让我在最坏情况下收益最大的那步棋。在代码里这表现为一个递归函数轮到我了我尝试所有候选落子对每个落子递归调用轮到对手的函数对手会选让我的分数最低的那步我则从这些最低分里选最高的那个。int minimax(int depth, int isMax, int alpha, int beta) { if (depth 0 || gameOver()) return evaluate(); if (isMax) { int best -INF; for (each candidate move) { makeMove(move); best max(best, minimax(depth-1, 0, alpha, beta)); undoMove(move); alpha max(alpha, best); if (beta alpha) break; // Alpha-Beta剪枝 } return best; } else { int best INF; for (each candidate move) { makeMove(move); best min(best, minimax(depth-1, 1, alpha, beta)); undoMove(move); beta min(beta, best); if (beta alpha) break; } return best; } }这段框架是标准写法但直接套用到五子棋上会有两个问题候选落子太多以及搜索深度不够。5.2 候选落子生成不是每个空位都值得考虑15×15的棋盘有225个空位如果每层都遍历所有空位搜索树会爆炸。实际上五子棋里有意义的落子点几乎都在已有棋子的附近。我的做法是只考虑距离已有棋子两格以内的空位。这个范围能覆盖所有有战术价值的点同时把候选数量从200多降到20到40个左右。更进一步可以对候选点做排序把评估分数高的点排在前面。Alpha-Beta剪枝的效果高度依赖搜索顺序——如果好的走法先被搜到剪枝就能更早发生效率提升非常明显。我实测下来加了候选排序之后同样深度下搜索时间能减少一半以上。5.3 Alpha-Beta剪枝到底剪掉了什么Alpha-Beta剪枝的原理用一个生活化的类比你在比较几个方案已经知道方案A至少能得80分现在评估方案B时发现它的某个分支最多只能得70分那方案B剩下的分支就不用看了因为它不可能超过A。这就是剪枝。在代码里alpha记录的是当前能保证拿到的最高分beta记录的是对手能保证拿到的最低分。当beta alpha时说明这个分支的结果对双方都没有吸引力可以安全地跳过。这个剪枝不会改变最终结果只是省去了无用的计算。但要注意Alpha-Beta剪枝对搜索顺序非常敏感。如果候选点排序很差剪枝几乎不起作用搜索时间跟不剪枝差不多。所以候选排序不是可选项而是让剪枝生效的必要前提。5.4 迭代加深时间可控的搜索策略固定深度的搜索有个问题你不知道搜到第几层会超时。迭代加深的思路是先搜深度1再搜深度2再搜深度3……每搜完一层如果时间还够就继续加深。这样即使时间到了你至少有一个完整的浅层搜索结果可用。对于课程设计我建议把搜索深度设在4到6层之间配合迭代加深和Alpha-Beta剪枝在普通电脑上思考一步大概在1到3秒体验比较流畅。如果追求更强可以加到8层但需要更激进的剪枝和更好的候选排序。6. 实战调试那些文档里不会写的坑6.1 机器自杀评估函数符号搞反我调试时遇到过一个经典bug机器明明有一步能直接连五获胜却偏偏去堵对手一个无关紧要的活二。排查了半天发现是评估函数里对手威胁的扣分系数设得太大导致机器觉得堵这个活二比自己连五得分更高。这个问题的根源是评估函数没有对立即获胜做特殊处理。修复方法很简单在搜索之前先检查自己有没有一步获胜的机会有就直接下再检查对手有没有一步获胜的机会有就堵。这个必胜/必堵的预处理能避免大量低级失误。6.2 边界处的棋型误判前面提到过一维数组下水平方向的边界判断容易出错。我当时的bug是在第14列往右扫描时下标1会跳到下一行第0列代码误以为那里有棋子导致棋型识别错误。修复方式是在扫描时同时检查列号变化或者干脆用二维坐标做棋型识别只在棋盘存储时用一维数组。这个坑我踩了两次第二次是因为换了方向偏移量之后忘了同步修改边界判断。6.3 搜索深度增加后程序卡死有一次我把搜索深度从4调到6程序直接卡住不动了。原因是候选点没有做数量限制深度每增加一层节点数乘以候选数6层下来节点数到了几百万加上每个节点都要做评估时间直接爆炸。解决办法是限制每层的候选点数量比如每层只取评估分数最高的前10到15个点。这样虽然可能漏掉一些冷门好棋但保证了搜索能在合理时间内完成。对于课程设计这个取舍完全可接受。6.4 先手优势的处理五子棋先手优势很大如果机器执黑它应该主动进攻如果执白则要更注重防守。我的做法是在评估函数里根据执子颜色调整进攻和防守的权重。执黑时进攻权重高一些执白时防守权重高一些。这个调整不需要很精确但能让机器的表现更符合预期。7. 从能跑到好用几个提升体验的细节7.1 开局库的简单实现完全靠搜索下棋机器在开局阶段可能会走出一些奇怪的棋。一个简单的改进是准备一个小型开局库记录前几步的常见应对。比如机器执黑第一步下天元对手下附近机器按预设走法应对。开局库不需要很大覆盖前3到4步就够了但能让机器的开局看起来专业很多。7.2 禁手规则的取舍标准五子棋有禁手规则黑棋不能走双三、双四、长连但课程设计里实现禁手判断会让代码复杂度大幅上升。我的建议是如果题目没有明确要求可以不实现禁手在说明文档里注明本实现采用无禁手规则即可。如果确实需要禁手判断可以复用棋型识别的代码在落子后检查是否形成禁手棋型。7.3 思考时间的控制机器思考时间太长会让对弈体验很差。除了限制搜索深度还可以加一个时间检查在搜索过程中定期检查已经用掉的时间如果超过预设上限比如2秒就立即返回当前找到的最好结果。这个机制配合迭代加深使用效果最好——浅层结果总是完整的深层搜索随时可以中断。7.4 胜负判断的即时性每落一子后只需要检查这个子所在的四个方向上是否形成五连不需要全盘扫描。这个优化虽然简单但能明显减少每步的延迟。实现时注意只检查经过新落子的那几条线其他方向的棋型不可能因为这一步而改变。8. 我在这个项目里最想分享的几条经验做这个项目最大的体会是算法课上的知识只有真正落地到一个具体场景里你才会理解它为什么长那样。极小化极大搜索在课本上就是几行伪代码但当你真的用它来下棋才会明白候选排序为什么重要、评估函数的精度如何影响搜索效果、剪枝条件写错会导致什么后果。另外一条经验是关于调试的。五子棋AI的bug往往不会让程序崩溃而是让机器变傻——走出莫名其妙的棋。这类bug最难查因为没有一个明确的报错信息。我的方法是构造特定局面做单元测试比如摆一个机器有活四的局面看它能不能识别并获胜摆一个对手有冲四的局面看它会不会去堵。把这些测试用例固定下来每次改完代码跑一遍能快速发现回归问题。最后说一个关于性能的实用技巧如果你的程序在搜索时很慢先别急着优化算法用性能分析工具看看时间到底花在哪里。我一度以为是搜索本身慢后来发现80%的时间花在评估函数的全盘扫描上。把评估改成增量计算之后速度直接翻了几倍。先测量再优化这个原则在任何性能问题上都适用。
