★ FEATURED ARTICLE 做棋类游戏AI部分是最容易让新手怀疑人生的地方。棋盘渲染、落子交互、胜负判定都做得像模像样AI一上手却显得很呆——要么只顾眼前乱吃子要么半天卡住不落子有时候甚至走出一步自杀的棋。教程做到第8章我把智能搜索算法的深入实践放在这里就是为了系统性解决“AI怎么真正变聪明”这个核心问题。这篇博文不会只在概念层面打转我会直接把一套在Unity里验证过的棋类搜索算法设计方案拆开来讲核心是Minimax、Alpha-Beta剪枝配套估值函数、走法排序、迭代加深这些工程手段从原理讲到落地再聊那些常规文档里不会写的坑。主要目标读者是已经能用Unity做棋盘、写规则判定的开发者如果你正准备给某个棋类项目接入AI或者想搞懂搜索算法怎样真正跑起来而不是停留在课本公式上这篇内容应该正合需求。1. 内容整体设计与思路拆解1.1 棋类AI绕不开搜索算法的根本原因棋类游戏和动作游戏最大的区别在于动作游戏的核心是实时反馈玩家按一个键角色做一个反应而棋类游戏的核心是决策推演“我走这一步之后对手最可能的应对是什么我再怎么接”这本质上就是一个搜索问题。以五子棋为例15×15的棋盘上第一步有225种合法落点第二步对手有224种对应选择组合数量就已经超过5万。到第6层搜索空间大约是225×224×223×222×221×220数量级在10的14次方左右别说是Unity就是放在大型服务器上想完全展开也根本不现实。象棋、围棋、黑白棋全都面临同样的状态空间爆炸问题只是爆炸的猛烈程度不同。所以棋类AI的标准决策链长这样拿到当前棋盘状态枚举当前玩家的所有合法走法对每种走法模拟对手的最优应对在有限深度内对局面做出评估选出评估分数最高的走法返回这条链路里最关键的两个引擎就是搜索策略和估值函数。搜索策略负责“怎么找”估值函数负责“怎么判断找到的是好棋还是坏棋”。缺了任何一个AI都跑不起来。1.2 为什么选Minimax加Alpha-Beta作为主力方案棋类AI可以用的搜索算法不少我整理了一张对比表方便你看清楚选择边界算法基本思路适合场景实现成本最大劣势Minimax双方轮流最大化/最小化收益分支因子较小的棋类低节点数随深度指数爆炸Alpha-Beta剪枝在Minimax上剪掉无用子树有明确胜负目标的棋类中剪枝效果依赖走法排序MCTS蒙特卡洛树搜索随机模拟加统计胜率分支因子极大的棋类高需要大量模拟早期棋力偏弱深度学习策略网络加价值网络任意棋类极高需要数据、算力和训练框架我在第8章的实践里最终选择的是Minimax配Alpha-Beta剪枝加迭代加深和启发式走法排序。为什么这么选因为大部分棋类游戏的项目需求是“AI能在1秒到3秒内给出一个合理的走法难度可调”这个目标用Minimax加剪枝完全可以覆盖。以黑白棋奥赛罗为例它的分支因子通常在10到20之间配合Alpha-Beta剪枝和合理的走法排序搜索深度做到8层以上、单步响应在几百毫秒级别完全可行。MCTS也能做但黑白棋的随机模拟噪声会让中前期棋力显得不太稳定而这些副作用在Minimax体系里更容易控制和调试。1.3 架构分层把AI从Unity显示逻辑里抽出来我在某个棋类Demo里的做法是把AI逻辑拆成三层互相之间只通过接口打交道Core层BoardState、Move、规则判定纯C#数据与逻辑完全不引用Unity APISearch层估值函数、走法生成器、搜索器同样不依赖MonoBehaviourAdapter层AIController挂在场景物体上负责把Core层的输出转成Unity里的落子动画这个分层看着多了一道手续实际收益非常大。第一搜索计算很重如果直接写在MonoBehaviour里很容易和渲染逻辑挤在主线程上一搜就是几百毫秒画面直接卡住第二Core层和Search层做成纯C#类之后单元测试可以完全脱离Unity编辑器运行调试搜索逻辑的速度会快出好几倍第三之后如果你想把这套AI接到服务器端做联机对战只需要把Adapter层重写一下就行。2. 估值函数、Minimax 与 Alpha-Beta 核心机制解析2.1 估值函数AI怎么“看懂”棋局AI没有一个人类意义上的“棋感”它眼里只有一串数字。估值函数要做的事情就是把当前棋盘局面换算成一个分数让AI知道这盘棋自己处于优势还是劣势。最简单的估值是子力差比如黑白棋里黑子比白子多几个就返回正几少几个返回负几。但这个估值有个致命问题AI会为了中期棋子数量优势放弃像角、边这样的关键位置。因为角一旦占住几乎不会被翻过来而棋盘中间的棋子数量再多到最后也可能被一口气全部翻掉。所以实践中一定要用“位置权重加子力”的复合估值。黑白棋里我常用的配置是棋盘位置权重分数原因四个角500占住后几乎无法被翻转边位50相对稳定但不如角关键C位角的斜对角-30极易把角暴露给对手邻角位角旁边-20同样容易送角普通格子1基础子力分注意位置权重表不是抄来就能用的不同开局阶段、不同落子分布下同一位置的价值会变化。实操中我会在每盘棋结束后对权重做手动微调比如发现AI总是前期守角太激进就把C位的罚分调高一点。这个调参过程是调AI风格最快的手段比改搜索逻辑直观得多。2.2 Minimax搜索原理推导Minimax的思想简单到一句话假设双方都足够聪明那么在AI回合AI会选择让自己收益最大的走法在对手回合对手会选择让AI收益最小的走法。于是整个搜索过程就是不断交替地“求最大”和“求最小”。从博弈树的角度看AI执行一次搜索会展开一棵树根节点是当前局面子节点是AI能走的每个位置孙子节点是AI走了之后对手能走的每个位置如此往下推。树的每一层都代表一个玩家的回合。当搜索到达设定的深度边界时就调用估值函数给节点打分然后逐层往上回传。用生活类比来解释你和朋友轮流选择楼层你想挑最高层但朋友每次都想把你能选的楼层压到最低。你在自己回合从可选项里挑最高的朋友回合就从可选项里挑对你来说最低的。最后你选的是在对方刻意压低之后依然最高的那条路。伪代码长这样function MiniMax(state, depth, isMaximizingPlayer): if depth 0 or gameOver(state): return Evaluate(state) moves GenerateMoves(state) if isMaximizingPlayer: bestValue -infinity for move in moves: value MiniMax(Apply(state, move), depth - 1, false) bestValue max(bestValue, value) return bestValue else: bestValue infinity for move in moves: value MiniMax(Apply(state, move), depth - 1, true) bestValue min(bestValue, value) return bestValue这个递归结构是后面一切优化的地基。先把这个逻辑跑通再去做剪枝会顺利很多。2.3 Alpha-Beta剪枝把指数级搜索压到可接受范围Minimax本身不剪枝意味着搜索节点的数量会随着深度指数增长。Alpha-Beta剪枝的核心思路是在搜索过程中维护两个边界值alpha表示当前最大化玩家已经确保能得到的最低分数beta表示当前最小化玩家允许对方拿到的最高分数。一旦某个分支里alpha大于等于beta说明这条分支已经不可能被父节点选上直接裁掉。剪枝的直观理解是这样的你已经找到一条能赢30分的走法这时在另一条分支里对手有一个应对能让你的分数压到10分以下。既然这条分支不可能比已经找到的好那就不需要继续探下去省下的时间全部留给别的更有希望的分支。伪代码如下function AlphaBeta(state, depth, alpha, beta, isMaximizingPlayer): if depth 0 or gameOver(state): return Evaluate(state) moves GenerateMoves(state) if isMaximizingPlayer: bestValue -infinity for move in moves: value AlphaBeta(Apply(state, move), depth - 1, alpha, beta, false) bestValue max(bestValue, value) alpha max(alpha, bestValue) if beta alpha: break return bestValue else: bestValue infinity for move in moves: value AlphaBeta(Apply(state, move), depth - 1, alpha, beta, true) bestValue min(bestValue, value) beta min(beta, bestValue) if beta alpha: break return bestValue注意那个break剪枝就发生在这里。如果剪枝条件判断出错或者break放错位置搜索结果就会和纯Minimax不一致AI行为会变得诡异。剪枝率受走法顺序影响非常大。最理想情况下Alpha-Beta的节点数能从O(b^d)降到大约O(b^(d/2))也就是说同样的消耗可搜索深度能提升约一倍。但这是建立在每次都能先搜到好走法的前提下如果排序很烂剪枝基本没效果搜索退化成普通Minimax。3. 在 Unity 中的实操落地与性能优化3.1 代码组织别把搜索写进MonoBehaviour我在自己的项目里会给搜索器单独建一个纯C#类不挂任何Unity组件。这样有三个好处跑单元测试不需要打开编辑器逻辑清晰不会和生命周期方法搅在一起后续要把搜索挪到后台线程更加方便。核心类的结构大概是这样public class ChessAISearcher { private Evaluator evaluator; private MoveGenerator moveGenerator; public ChessAISearcher(Evaluator evaluator, MoveGenerator moveGenerator) { this.evaluator evaluator; this.moveGenerator moveGenerator; } public Move FindBestMove(BoardState state, int depth) { Move bestMove null; int bestValue int.MinValue; var moves moveGenerator.GenerateMoves(state); foreach (var move in moves) { state.ApplyMove(move); int value AlphaBeta(state, depth - 1, int.MinValue, int.MaxValue, false); state.UndoMove(move); if (value bestValue) { bestValue value; bestMove move; } } return bestMove; } }在AIController里MonoBehaviour只在收到“该AI走了”的事件时调用FindBestMove拿到结果后再把棋子动画交给显示层。搜索细节和渲染完全无关。3.2 用迭代加深替代固定深度固定深度搜索看似简单实际上体验很差。原因在于同一深度在不同局面下的耗时差异非常大。某个局面分支少深度6可能只需要100毫秒另一个局面分支多深度6可能要2秒。单位时间内卡顿不稳定玩家体验很糟糕。解决方法是迭代加深思路非常直白先以深度1搜索一遍拿到候选走法再看时间预算如果还剩时间用深度2重新搜时间不够时直接返回上一次深度已经算出来的走法public Move FindBestMoveWithTimeBudget(BoardState state, float timeBudgetSeconds) { Move bestMove null; var stopwatch System.Diagnostics.Stopwatch.StartNew(); int maxDepth 12; for (int depth 1; depth maxDepth; depth) { Move candidate SearchFixedDepth(state, depth); if (stopwatch.Elapsed.TotalSeconds timeBudgetSeconds) { break; } bestMove candidate; } return bestMove; }迭代加深看起来多搜了好几遍但因为每一层浅搜索开销都远小于深层总的额外消耗并不大。而且它天然解决了“超时”问题在真实游戏里比固定深度实用得多。3.3 怎么避免搜索卡住主线程Unity的MonoBehaviour生命周期调用全部发生在主线程。如果Update里直接跑几百万节点的递归搜索那么搜索期间整个游戏画面都会被冻住移动端甚至会直接触发“应用无响应”。实际项目中我常用三种方案配合协程把搜索循环拆开每处理几百个节点就yield return null把控制权交还给主线程渲染一帧后台线程在单独的Task里执行搜索逻辑等结果出来后再通过主线程调度切换回来Job System加Burst适合对性能要求极高的情况但学习成本高而且搜索逻辑要改成Unity支持的Job结构改动较大我建议优先用协程。改动最小代码结构也直观。等到搜索深度真的加到很深、一帧内处理不完时再考虑后台线程。注意后台线程方案有一个大坑搜索函数内部绝对不能直接调用任何Unity API包括GameObject.transform访问否则子线程访问主线程对象会直接抛异常。这就是前面强调要分层、让Search层不依赖Unity API的原因。3.4 走法排序让剪枝率成倍提升的隐藏开关剪枝生效的前提是“先搜到好的走法”。如果每次进入新节点第一个尝试的走法就是最差的那条Alpha-Beta几乎不会剪掉任何分支搜索退化成暴力枚举。所以我在搜索进入每层之前先通过一个快速评估函数给该层的所有走法打分然后按分数从高到低排序。这个排序用的评估要比完整估值函数轻量得多可以用位置表甚至单纯的行棋位置做粗略排序。还有两个进阶技巧置换表把搜索过的棋盘状态哈希值和结果存起来下一轮搜索遇到相同状态直接查表时间感知排序把上一轮迭代加深搜出来的最佳走法强制放在当前层最前面效果极好我实测过排序对性能的影响。同一个黑白棋局面固定深度6未排序节点数大约420万简单启发式排序后下降到72万耗时下降超过70%。这是整个优化过程中收益最直观的一步。3.5 一个完整的搜索调用链示例以一次AI走棋为例玩家落子后AIController更新BoardStateAIController调用FindBestMoveWithTimeBudget(state, 1.5f)Searcher启动迭代加深从深度1开始逐层递增每层先调用MoveGenerator生成走法再用轻量评估排序递归执行AlphaBeta搜索每层完成后检查时间时间不足则停止并返回上一层结果Searcher返回最佳Move给AIControllerAIController把Move转成场景中的落子表现实际项目里还要考虑一个问题搜索中途如果棋盘状态变化比如联机对战对方先落子当前搜索结果必须作废。所以AIController里每次启动搜索前要检查局面版本号避免把旧局面的结果应用到新局面上。4. 常见问题排查与避坑实录4.1 AI下棋下得很差甚至走出“自杀”式走法这大概是新手最容易遇到的问题了我自己刚写搜索的时候也撞过。排查要按顺序来检查估值函数符号。很多项目里是黑方优势-是白方优势但搜索的时候又要从黑方视角调用很容易在某个递归层写出反号检查走法生成器是否漏掉合法走法。比如黑白棋的翻转规则写错导致某些位置的合法落点没有生成检查状态回滚。递归里ApplyMove之后如果忘了UndoMove兄弟节点看到的棋盘就是脏的AI当然会乱走打印某几层搜索树的关键分支估值看你觉得的好棋在搜索树里是不是评到了高分最容易出问题的其实不是搜索逻辑本身而是走法生成和状态回滚。只要这两个地方有一个小bug搜索越深错得越离谱。4.2 深度增加但棋力没有提升有读者曾经问过我“为什么我把搜索深度从4加到6AI反倒更呆了”。这个问题出现的原因通常有两类。第一类估值函数太平面只算了子力差完全没有位置因素。这种估值驱动下的深度加深只会让AI更坚定地去执行短视的策略所以看起来越“聪明”越乱来。第二类水平线效应。搜索深度固定时有些坏棋的影响发生在深度边界之外搜索看不到那一步灾难就会误判为安全的走法。处理方式要么继续加深要么在估值函数中加入更深入的静态判断。我的体感是在深度不高的阶段估值函数的打磨远比深度提升重要。先让AI“看懂”简单局面再考虑让它“看远”顺序不要反。4.3 搜索卡成PPT节点数异常多这种问题十有八九是剪枝没生效。我在排查时会在搜索器里加一个计数器记录每一层实际展开的节点数然后对比剪枝前后数据。如果节点数接近暴力枚举数量重点查两件事beta alpha的剪枝条件有没有触发break写没写走法排序是否真的有效还是只是形式上排了个序实际最优走法经常排到后面如果节点数明显减少了但还是卡那问题多半在内存分配上。每展开一个节点就new Listint深度稍微加大内存垃圾就会多到让GC频繁卡顿。优化方式是把走法列表复用或者用ArrayPool。4.4 状态回滚问题大吐槽我必须要单独拎出来说。递归搜索里每个节点都要基于父节点状态做出修改搜索完再恢复到原状。最省事的写法是ApplyMove返回一个新状态对象但这样内存开销巨大。省内存的做法是修改原状态搜索完后逆操作恢复。黑白棋的状态回滚最容易错的就是翻转棋子。ApplyMove翻转了几个棋子UndoMove就得老老实实把那些棋子翻回来如果翻转列表没有保存完整或者恢复顺序错乱整个搜索树就废了。我在调试阶段用过一个笨办法每次搜索前复制棋盘快照搜索结束后直接整体恢复。虽然后来为了性能换成了增量回滚但早期这个笨办法帮我确认了搜索逻辑本身是正确的非常值得一用。4.5 单元测试是搜索算法的底气搜索算法复杂度高、隐蔽bug多手工测试很难覆盖全面。我习惯给Search层写一组固定局面测试比如“这个局面下深度4必须返回角位”这类断言。每次改估值函数或者调整剪枝逻辑后只要跑一遍测试就能快速确认基础行为没有跑偏。这一步看着不起眼实际能帮你省下大量调参时间。尤其是在后面要增加新算法比如MCTS的时候有了测试打底重构起来心里踏实得多。5. 从简单搜索到MCTS后续进阶方向5.1 MCTS蒙特卡洛树搜索的基本流程如果你做的棋类分支因子很大比如围棋或者将棋Minimax加剪枝会吃不住——搜索空间太大穷举式的展开根本来不及。这时就需要换到蒙特卡洛树搜索核心思想不再展开整棵博弈树而是通过大量随机对局模拟来估算每个落子的胜率。MCTS的过程分四步选择从根节点出发按照一定策略选出一个当前最有探索价值的子节点扩展如果选到头了一个还没完全展开的节点就给它加入一个新子节点模拟从新子节点开始随机下到终局或者一个预设深度回溯把模拟结果沿路径回传更新路径上所有节点的统计信息重复反复执行这几步访问次数最多的子节点就被认为是最优走法。这个思路在中文社区经常被概括为“推演多少次就信哪条路”。5.2 UCT公式怎么理解MCTS的选择阶段最常用的是UCT公式UCT V_i C × sqrt(ln(N) / n_i)其中V_i是这个子节点当前的平均胜率收益N是父节点总访问次数n_i是当前子节点的访问次数C是探索与利用的平衡系数。公式里的ln(N)随着父节点访问次数增长当一个节点好久没被选中时它的探索项会变大从而又有机会被访问。这个机制解决了一个核心问题既不能只盯着当前胜率最高的节点利用也不能一直随机瞎逛探索。UCT在两者之间取了平衡。C调大AI偏向探索调小AI偏向利用。不过要提醒一点如果你做的是黑白棋、五子棋这种分支因子不算夸张的棋类MCTS未必比Alpha-Beta体验更好。我见过一些项目把MCTS奉为万能药结果跑出来的棋力忽高忽低反而不如老老实实地把Minimax调好。5.3 在Unity项目里怎么平滑升级到MCTS从工程角度说MCTS和Minimax是两套完全不同的决策逻辑但上层接口可以保持一致。你可以让FindBestMove内部根据棋种配置选择用AlphaBeta还是MCTS这样AIController不需要改动。如果你没有写过MCTS最快的入门路线是先写一个纯随机模拟的朴素版跑通流程再逐步加UCT选择策略和模拟剪枝。不要一开始就写完整版因为MCTS的随机性导致调试比Minimax麻烦很多中间出了问题根本分不清是选择错了还是模拟错了。在Unity里的落地方式和Minimax类似同样建议放在协程或后台线程里。MCTS的模拟通常要跑上千次甚至上万次主线程等待必然卡顿。另外MCTS对随机数生成器的要求较高Unity默认的UnityEngine.Random不建议在多线程环境下直接使用换成自定义的种子随机数更稳。结尾一点个人心得回头看看这一章从设计到实现的过程我最深的体会是做棋类AI数学公式只是起点工程习惯才是真正制约棋力的地方。估值函数有没有打磨走法排序有没有做状态回滚严不严谨时间预算怎么控制这些东西比起一上来就堆搜索深度对最终体验的影响大得多。最后再分享一个小技巧调试AI的时候永远在搜索器里保留一个“详细日志”开关。打开后能看到每一层的搜索深度、节点数、剪枝率、选中的最佳走法及估值。很多看起来很玄学的“AI抽风”问题其实靠日志一击就能定位到原因。省下来的时间拿去调平棋盘和打磨体验比什么都值。
阅读完成 · 觉得有帮助？
