Unity棋类AI搜索算法实战：从Minimax到Job System优化

做棋类AI搜索算法永远是躲不开的核心话题。最近有好几个读者私信问我在Unity里实现棋类对战AI的思路从五子棋到象棋再到自创的小棋种都有。我梳理了一下干脆把Unity环境下棋类游戏智能搜索算法的完整实践写出来从最朴素的Minimax到α-β剪枝、迭代加深、走法排序再到Unity特有的Job System优化一条链路讲清楚。这篇文章适合刚入门棋类AI、被搜索效率卡住、或者想在回合制游戏里加入可调难度AI的开发者文中所有代码都是C#可以直接在Unity工程里跑通。1. 棋类AI搜索算法的起点为什么Minimax是绕不开的基础1.1 棋类博弈的本质信息完备的零和对抗棋类游戏和动作游戏、卡牌游戏最大的区别在于——对局双方看到的信息完全一致每个回合的状态转换是确定的不存在随机性。意思是在这类游戏里AI不需要处理不确定信息它需要的只是一个能在当前局面下枚举所有合法走法的规则引擎以及一个用来评价这个局面到底谁占优的评估函数。有了这两个东西理论上可以枚举所有可能走法选一条对自己最有利的路径。大学的时候我参加校内AI对抗赛当时指导我的某导师说过一句让我印象很深的话棋类搜索不是找一步好棋而是让对方找不到好棋。Minimax算法就是把这句话数学化的产物。1.2 Minimax的核心逻辑与初始实现Minimax的思路不复杂。假设当前是己方回合我们把所有合法走法都试走一遍得到下一层局面再站在对方视角假设对方也会选择对自己最有利、对我们最不利的走法这样交替递归下去。到了预设深度比如4层就停止搜索用评估函数给局面打分。分数越高代表对己方越有利。向上回溯时己方节点取子节点最大值对方节点取子节点最小值。用伪代码可以写得更清楚float Minimax(GameState state, int depth, bool isMaximizingPlayer) { if (depth 0 || state.IsGameOver()) return Evaluate(state); if (isMaximizingPlayer) { float maxEval float.NegativeInfinity; foreach (var move in state.GetLegalMoves()) { state.ApplyMove(move); float eval Minimax(state, depth - 1, false); state.UndoMove(move); maxEval Mathf.Max(maxEval, eval); } return maxEval; } else { float minEval float.PositiveInfinity; foreach (var move in state.GetLegalMoves()) { state.ApplyMove(move); float eval Minimax(state, depth - 1, true); state.UndoMove(move); minEval Mathf.Min(minEval, eval); } return minEval; } }层数每加深一层工作量成指数增长。以国际象棋为例平均分支因子大约35搜索4层需要评估35^4约150万个节点深度加到6层就是18亿个节点。纯粹用Minimax在Unity里跑2层能实时响应3层就开始卡顿4层直接吃满主线程。这也是为什么Minimax只适合做入门demo或者棋类规则极简比如井字棋的游戏。1.3 负极大值形式让代码少一半Minimax用交替取最大最小的方式写逻辑清晰但代码里每个节点都要判断当前是谁的回合有点冗余。在实战项目里我更推荐用Negamax负极大值形式。它利用了一个性质对任意局面己方的最优收益等于对方的最优收益的相反数。这样递归函数只需要一直做取最大值操作配合评估函数时注意分数始终以当前走棋方为正即可。float Negamax(GameState state, int depth) { if (depth 0 || state.IsGameOver()) return Evaluate(state); float maxEval float.NegativeInfinity; foreach (var move in state.GetLegalMoves()) { state.ApplyMove(move); float eval -Negamax(state, depth - 1); state.UndoMove(move); maxEval Mathf.Max(maxEval, eval); } return maxEval; }这里有一个必须注意的细节评估函数的分数必须始终站在当前走棋方的角度当前走棋方优势为正劣势为负。这样递归中取负号才成立。很多人第一次写Negamax结果评估函数仍然站在固定一方角度去打分导致整个搜索树逻辑错乱搜索出来的最优走法完全没法看。这个问题我至少见过三个人踩过。在真正进入剪枝优化之前我建议先把Negamax的递归结构、走法生成、局面回滚这套基本功做扎实。不要急着上α-β剪枝因为剪枝是建立在基础搜索能正确返回结果之上的。如果搜索本身就是错的剪枝只会更快地返回错误答案。2. 剪枝与走法排序让搜索树从能跑变成能打2.1 α-β剪枝的直觉理解与实现α-β剪枝不改变搜索结果它只是把肯定不会被选择的分支提前砍掉。还是拿一个具体场景来模拟。假设当前节点是己方取最大我们已经搜完了一个分支得到分数3。这时候进入下一个分支第一个子节点返回2那么后面的走法还有必要看吗没有必要了因为对方在这个节点上会取最小的2给我们而2已经小于3了己方永远不可能在这个分支获得比3更优的结果。于是整个分支都可以放弃。实现上我们给递归函数传两个参数α表示当前路径上己方已知的下界β表示对方已知的上界。当某个节点的返回值超过β时直接剪断。伪代码如下float AlphaBeta(GameState state, int depth, float alpha, float beta) { if (depth 0 || state.IsGameOver()) return Evaluate(state); float maxEval float.NegativeInfinity; foreach (var move in state.GetLegalMoves()) { state.ApplyMove(move); float eval -AlphaBeta(state, depth - 1, -beta, -alpha); state.UndoMove(move); maxEval Mathf.Max(maxEval, eval); alpha Mathf.Max(alpha, eval); if (alpha beta) break; // beta剪枝 } return maxEval; }注意这里负号的取法递归调用时把α、β取反并互换位置这是Negamax形式和α-β剪枝结合的常见写法数学上等价于普通的Minimax版本但代码更简洁。我在某跨平台系统项目里用这套写法把原来的搜索深度从4层提到了7层耗时基本不变。2.2 剪枝效率的关键走法排序决定一切很多人以为α-β剪枝的优化幅度是固定的其实不是。剪枝效率强烈依赖于走法的搜索顺序如果每次第一个搜索的都是最好的走法那么后续走法几乎全都能被剪掉节点数可以逼近理论最优值大约是原始搜索树大小的平方根量级。反过来如果你每次先搜最差的走法剪枝几乎不发生性能退化回普通Minimax。所以走法排序是α-β剪枝真正拉开差距的地方。常用的排序策略分几个层次。第一层是静态启发。在生成走法后先给每个走法算一个粗糙的优先级然后按优先级排序。比如在国际象棋里吃子走法优先而且吃的子价值越高、吃的子越便宜优先级越高。这个可以用MVV-LVA最有价值受害者-最便宜攻击者策略实现。第二层是杀手走法。在搜索过程中记录每个深度上导致剪枝最多的那个走法后续搜索到同一深度时优先尝试这些杀手走法。第三层是历史启发。走法在搜索中被成功证明为最优的次数越多排序越靠前。这三层排序可以叠加使用。我个人的经验是走法排序做到杀手走法静态启发这个级别剪枝效率已经非常可观历史表可以做但收益相对小除非你追求顶尖搜索强度。2.3 空着剪枝与边界情况进阶但不要迷信除了α-β剪枝棋类搜索里还有一个常见技巧——空着剪枝Null Move Pruning。思路是当前局面假设己方不走棋相当于让子让对方连续走两步如果这种情况下对方仍然占不到便宜那说明当前局面已经足够好可以提前剪掉。这个技巧在国际象棋引擎里非常有效但在棋类规则比较复杂、存在不可让子状态比如将军时不允许空着的游戏中需要格外小心。Unity里做棋类AI我建议先把α-β剪枝跑稳再考虑空着剪枝。空着剪枝用不好会出现明显的漏招游戏体验反而下降。还需要提一个边界剪枝的前提是评估函数足够稳定。如果评估函数忽高忽低、噪声很大剪枝会误判大量分支导致搜索结果的可靠性下降。所以我会在调完评估函数之后再回头优化搜索效率这个顺序别搞反了。3. 评估函数设计搜索算法真正的胜负手3.1 评估函数到底在评估什么搜索算法本身不产生棋力棋力全部藏在评估函数里。搜索只是把评估函数延伸到了更深层但最终决定每一步好坏的是每一个叶子节点的分数。初学者最容易犯的错误是花大量时间研究搜索算法评估函数随便写个子力差结果AI下棋像个莽夫只知道吃子完全没有位置概念。评估函数的设计要围绕这个棋的制胜因素是什么来展开。国际象棋的评估至少包含子力价值、兵型结构、王的安全、空间优势、机动性等。五子棋则要评估各方向上的连子潜力、活三、冲四、眠三等。象棋要评估子力位置、车马炮的机动性、士象完整性、将帅安全性等。在设计前一定要坐下来把棋类的胜负规则和常见战术完整梳理一遍否则评估函数很容易漏掉关键因素。3.2 从简化版评估到结构化评估的演进我用一个简化例子说明评估函数怎么写。假设做一个类似国际跳棋的小棋种棋子有普通子和王可后退目标是把对方棋子吃光或让对手无棋可走。那么一个合理的评估函数大致长这样float Evaluate(GameState state) { if (state.IsGameOver()) return state.CurrentWinnerIsWhite() ? 10000 : -10000; float eval 0; foreach (var piece in state.GetAllPieces()) { float sign (piece.Side Side.White) ? 1f : -1f; eval sign * piece.BaseValue; eval sign * EvaluatePiecePosition(piece); eval sign * EvaluatePieceMobility(piece); } return eval; }其中BaseValue是子力基础价值EvaluatePiecePosition是位置价值表EvaluatePieceMobility是机动性可选走的步数。归一化很重要所有子力、位置、机动性的量纲要统一否则会出现某个因素权重过大、其他因素形同虚设的问题。我的做法是先用一局游戏手动下几十步观察AI是否出现明显的局部短视行为再调整权重。3.3 我的评估函数调试流程评估函数最让人头疼的是权重调参。分享一个我常用的调试流程。第一步跑AI对AI的自我对局打开终端日志每步打印搜索深度、评估值、走法、最佳分数。先看有没有明显的无效循环——比如AI反复在两个走法之间来回。第二步固定开局让AI和不同权重组合的自己下记录胜负和平均步数。这一步能发现权重失衡问题比如只追子力、不管位置的AI往往会因为贪吃子而丢掉局面优势。第三步针对边界场景写单元测试。例如设计一个两步杀的局面要求AI必须走出制胜着法设计一个必败防守局面要求AI必须走出唯一的防守着法。如果评估函数目标不清晰这两类测试会暴露很多问题。我见过某开发者在做五子棋AI时因为评估函数里活三和冲四的分数设置不合理导致AI经常下出自杀式堵塞自己的棋形。后来他把活三分数调成冲四分数的一半以下AI一下子就开窍了。评估函数的权重不是玄学是拿大量对局数据逐步调出来的。3.4 叶子节点评估的稳定性问题搜索深度不同同一个局面可能得到完全相反的结论。这是因为叶子节点评估值本身有噪声浅层搜索更容易受噪声影响。解决办法是给评估函数加一个深度惩罚越深的节点评估值乘以一个接近1但小于1的系数比如0.99^depth让浅层的更自信的评估压过深层的模糊评估。这个小技巧不是所有引擎都这么做但我在自己的项目里实测它确实能减少浅层搜索的抽风现象。4. 迭代加深与时间控制Unity实战里的搜索调度4.1 为什么不用固定深度而用迭代加深很多人做棋类AI时直接把深度定成4或者6AI每步都在这个深度搜索。这个做法非常简单但不适合实际游戏体验。原因有两个。第一不同局面的复杂度差异很大残局可能分支因子很小开局可能分支因子很大固定深度会造成有时候思考太久、有时候秒回。第二我们希望在时间允许的情况下能用尽量的深度时间不允许时拿上一个深度的结果兜底。迭代加深的做法是先搜深度1再搜深度2再搜深度3直到时间用完返回最后一次完整搜索的最佳走法。虽然看起来重复搜索浪费了时间但走法排序带来的剪枝效率提升使得下次搜索不必从零开始代价远小于收益。我实测过做了排序的迭代加深深度6的总耗时往往只比直接搜深度6多15%左右但时间控制能力是天壤之别。4.2 Unity里的搜索调度协程、异步与轮询Unity的主线程是帧驱动的。如果在Update()里同步执行搜索搜索时长超过一帧16ms画面就会卡顿超过几百毫秒直接掉帧到个位数。最简单的方案是协程。但协程有个问题每步执行完yield return null后搜索状态需要完全保存和恢复递归函数的栈帧不好暂停。所以真正的协程化搜索通常是把栈显式管理成迭代版本。这一点工作量大、容易出错但做成了非常优雅。我推荐另一种做法把搜索放到后台线程通过结果队列传回主线程。搜索逻辑本身不访问任何Unity对象因为GameObject相关API不能跨线程只操作我们自己定义的数据结构——棋盘数组、走法列表、评估结果。这样在StartCoroutine里每6毫秒查看一下线程状态有结果就直接应用走法没有就继续等。用户体验上就是AI思考了一会儿完全不卡主线程。下面是一个线程版迭代加深的骨架public class SearchAgent { private Thread searchThread; private volatile bool terminateRequested; private object resultLock new object(); private Move bestMove; private bool hasResult; public void BeginSearch(GameState state, int maxDepth, float timeLimitMs) { terminateRequested false; hasResult false; searchThread new Thread(() { var stopwatch Stopwatch.StartNew(); Move currentBest default; for (int depth 1; depth maxDepth; depth) { currentBest SearchRoot(state, depth); lock (resultLock) { bestMove currentBest; hasResult true; } if (stopwatch.ElapsedMilliseconds timeLimitMs) break; } }); searchThread.Start(); } public bool TryGetBestMove(out Move move) { lock (resultLock) { if (hasResult) { move bestMove; return true; } } move default; return false; } }核心逻辑在SearchRoot它调用带α-β剪枝的AlphaBeta返回最佳走法。搜索过程中不碰Unity API所以线程安全。有一点要注意volatile bool和lock不是高性能的但它们保证了主线程和搜索线程之间的数据一致性对回合制棋类来说完全够用。别为了极致性能去用无锁队列收益很低容易踩死锁坑。4.3 时间分配策略开局、中局、残局各不同搜索时间不能从头到尾一个值。开局阶段局面变化大前几步可以参考常见开局库直接返回固定走法省下时间给中局。中局搜索深度可以更深但要注意时间预算残局分支因子小可以适当延长搜索时间把深度推高。一个简单的经验公式是timeForMove baseTime * (0.5f 1.2f * (branchFactor / 35f))baseTime是你给AI设定的平均思考时间branchFactor是当前根节点的合法走法数量。这个公式的意思是走法多的局面多给点时间走法少的局面少给点时间。当然这只是起点值接下来还要考虑当前深度搜索到底用了多少时间来做动态调整。我在某个跳棋模拟项目里用这个策略AI平均思考时间从每步1.2秒降到了0.7秒棋力反而还略有提升因为它把省下的时间都集中在中后期的关键局面上了。4.4 中止搜索时的安全处理迭代加深最怕用户在搜索过程中点击了UI上的重新开始或者退出对局。搜索线程还在跑但棋盘已经被重置了线程继续访问无效的棋盘数组就会崩溃。我的建议是引入搜索代际概念每次发起搜索时给一个自增的代际号回调应用结果前检查代际号是否一致不一致则丢弃结果。UI交互全部通过主线程的发布订阅处理搜索线程不直接修改任何游戏对象状态。5. 从单线程到Job SystemUnity环境下的搜索性能优化5.1 搜索是天然的并行候选吗很多人以为把搜索算法加上Parallel.For就能多倍加速实际上没有那么简单。搜索树的分支天然是不均衡的某个分支可能是10层深度的剧烈搜索另一个分支可能1层就被剪枝。如果只是简单地把根节点的走法分给多个线程速度快的那根线程干完就闲着慢的那根拖着整个进度。所以并行搜索需要工作窃取work stealing或者更复杂的任务分割。Unity的Job System Burst编译器提供了一个相对可控的机制。5.2 把评估函数改成Burst兼容Unity的Job System要求job结构体是unmanaged struct里面不能有托管引用类型类、字符串、委托等。所以如果我们之前用了class Piece就要改成用NativeArrayint和整数编码表示棋子。举个例子我用一个长度为64的NativeArrayint表示棋盘棋子编码为0表示空1表示白兵2表示白王-1表示黑兵-2表示黑王。评估函数就变成纯NativeArray读操作完全Burst兼容。[BurstCompile] struct EvaluateJob : IJob { [ReadOnly] public NativeArrayint Board; public float Result; public void Execute() { float score 0; for (int i 0; i Board.Length; i) { int piece Board[i]; if (piece 0) continue; float sign piece 0 ? 1f : -1f; int type Mathf.Abs(piece); score sign * PieceValue(type); score sign * PositionBonus(type, i); } Result score; } }这是最简单的一层把评估函数并行化。实际上更常用的优化是并行搜索根节点走法。在Burst里做递归AlphaBeta会稍微麻烦因为Burst编译器对递归的支持有限但并非不可用实践中我更多是保留C#版本的搜索函数只把评估、走法生成这些热点函数写进Burst job里。这样做的好处是不用改搜索逻辑用job计算批量局面评估同时把NativeArray的分配和回收放到job里管理。5.3 一个可行的根结点并行方案假设根节点有4个候选走法每个走法递归深度6。我们可以开4个job并行搜索每个job返回自己的最佳评估值主线程最终取最大。为了让剪枝在并行时依然有效我通常先跑一个浅层预搜索深度2得到走法排序结果然后给每个job分配一组走法且使用共享的alpha/beta上界。这样并行搜索的节点总量会比串行搜索多一点点但墙钟时间能压到串行的40%左右。这个方案在Unity 2021以上版本配合Burst跑效果非常明显。5.4 小心线程竞争置换表的并发访问如果要做置换表转置表并行访问要格外小心。置换表本质是一个哈希表多个线程同时读写会产生竞争。最简单的方式是每线程一张表搜索时只访问自己线程的表结果用于排序启发时可以共享但同一深度结果缓存不能跨线程误用。用NativeParallelHashMap可以做全局并发但要注意Add和TryAdd在并发下的语义。我个人建议新手先不做并行置换表先跑通并行搜索再评估置换表的收益。6. 棋类AI落地中的调试手段与常见坑6.1 搜索日志与结点计数调试棋类AI最基础也是最重要的一步是让搜索过程可观测。我通常在SearchRoot和AlphaBeta里插入结点计数器和深度信息每隔一段时间打印一行日志格式如下[depth4][nodes123456][alpha0.32][bestMovee2e4][time231ms]这些日志能帮你快速定位两类问题搜索是否进入死循环评估值是否稳定收敛如果结点数暴涨到几百万但时间只有几十毫秒说明剪枝失效了如果评估值在不同深度之间来回横跳说明评估函数有问题。日志别打太多每搜索完一层打一次就行否则输出反而干扰判断。6.2 常见坑一评估函数的正负号不统一这件事再怎么强调都不为过。Negamax的评估函数必须始终站在当前走棋方视角而很多人在写评估函数时潜意识里会固定站在白方或己方视角。我排查过某开发者的项目他的AI白方玩得还行黑方就表现得完全像随机走子最后发现弱智的是评估函数黑方局面分数没有取反导致黑方在搜索时看似在取最大实则在最小化自己的利益。修一行代码棋力从200 ELO直接飙到1300 ELO。6.3 常见坑二走法生成不完整导致的隐形盲区走法生成是搜索正确性的基石。如果合法走法生成函数漏掉了某个规则比如王车易位、吃过路兵、别马脚AI就会出现明明看着没有更好走法但就是输了的诡异局面。排查时最有效的办法是写一个穷举验证脚本给定一个局面把你的走法生成结果和人工验证的走法列表逐项对比。每个棋类规则都单独做测试用例尤其是棋子移动边界、越界、被将军时不合法等场景。这个测试能挡住至少一半的AI突然变笨问题。6.4 常见坑三UI与搜索线程的数据竞争Unity主线程和后台搜索线程之间共享的数据只要有一处没加锁或没正确处理就会出现不可复现的崩溃。我的原则是搜索线程只写两个变量——是否有结果和最佳走法主线程通过锁读取。除此之外搜索线程不允许访问GameObject、Transform、MonoBehaviour的任何字段。棋盘数据在发起搜索时直接拷贝一份到搜索线程搜索结束后主线程再根据最佳走法去修改GameObject位置。严格遵守这个边界才能避免Unity里的各种莫名其妙闪退。6.5 从棋力测试到调参闭环最后一个实用的建议是搭建一套自动对局测试脚本。写一个GameController脚本让AI的两个不同参数配置互下100盘统计胜率。这样每次调整权重后可以立刻通过数字看到变化而不是凭感觉。我更推荐先固定搜索深度只调评估函数权重跑出基线胜率然后再逐步提高搜索深度观察胜率提升曲线是否合理。某图像处理Demo项目里我就是用这套方法把评估函数的30多个权重逐一调校完成的每一步都有数据支撑完全不靠玄学。我在实际项目里一直把搜索和评估分成两个独立模块来维护。搜索模块只负责讲如何从局面A找到最佳走法评估模块只负责回答这个局面到底谁好。两者用统一的Evaluate(state)接口对接想换搜索算法就换搜索想调评估权重就调评估互不干扰。从最早的井字棋、五子棋到后来的国际跳棋变种这套结构让我在多款棋类项目里都快速落地了AI。最后再分享一个小技巧给AI的搜索加一个随机性开关。如果每次都用绝对最优走法AI很容易被对手预测当AI优势很大时让它以一定概率选择第二或第三优的走法对局体验会丰富很多。这只需要在根节点返回最佳走法时偶尔选次佳走法即可不会实质影响棋力但能让玩家觉得对面的AI像个活人。这个技巧实测很管用推荐一试。