从零开始理解博弈搜索AI下棋的决策密码当你和AI下棋时它到底在“想”什么一、先搞清楚三个前提什么样的游戏能用这套方法在讲具体算法之前得先弄清楚一个前提——极小化极大算法不是万能的它只适用于一类特定的游戏。这类游戏需要同时满足三个条件第一零和博弈。简单说就是“你死我活”——你赢就是我输我赢就是你输没有双赢的可能。象棋、围棋、五子棋都是这样但合作类游戏就不行。第二完全信息。棋盘上所有信息双方都看得一清二楚没有暗牌、没有隐藏的手牌。斗地主就不行因为你看不到对手的牌。第三轮流行动、无随机因素。你走一步我走一步不靠掷骰子决定。满足这三个条件的游戏才能用博弈树和极小化极大算法来建模。这被称为二人零和完全信息博弈。二、博弈树把整盘棋画成一棵“可能性大树”现在假设你正在下井字棋。轮到你走了棋盘上还剩三个空位。如果你脑子足够大可以把从现在开始到最后结束的所有可能情况全部列出来你走A、对手走B、你再走C……每一种可能性都像树枝一样分叉出去最后长成一棵巨大的树。这棵“可能性大树”就叫博弈树Game Tree。树的根节点就是当前的棋盘状态。树枝边每走一步棋就是从一个节点到另一个节点。树的每一层交替代表你和对手的回合。叶子节点终局分出胜负或平局的时刻。下棋的过程本质上就是在这棵博弈树上从根走到某个叶子的过程。你和对手轮流做选择每一步都决定接下来走哪根树枝。三、评估函数给每个局面打个分博弈树有了但光有树不行——电脑得知道哪个局面好、哪个局面差。对于已经分出胜负的叶子节点打分很简单你赢了就是正分输了就是负分平局就是零。但问题来了象棋、围棋的博弈树大到宇宙都装不下电脑不可能算到终局。怎么办只算到一定深度就停下来然后给这个“半成品”局面打个分。这个打分的工具就叫评估函数Evaluation Function也叫启发式评估函数Heuristic Evaluation Function。评估函数本质上是一套经验法则——它根据棋子的数量、位置、控制区域等信息快速估算一个局面对谁更有利。比如最简单的象棋评估函数可以数双方棋子的数量再给每个棋子车、马、炮乘以不同的权重。评估函数越准AI的棋力就越强。但它永远不可能完美——如果真有完美的评估函数直接用它就能判断所有局面根本不需要搜索了。四、极小化极大算法核心决策逻辑有了博弈树和评估函数接下来就是核心问题怎么在树上做选择这就轮到极小化极大算法Minimax Algorithm出场了。它也叫极大极小值算法是博弈树搜索最基础的方法。算法的名字已经剧透了全部秘密——“极小”和“极大”。假设你是MAX玩家最大化方你的目标是让局面分数越大越好。你的对手是MIN玩家最小化方他的目标是让局面分数越小越好。那么当你站在博弈树的某一层时如果是你的回合MAX层你会从所有可选走法中选择分数最大的那个。如果是对手的回合MIN层对手会从所有可选走法中选择分数最小的那个对你最不利的。算法从叶子节点开始自底向上逐层计算MIN层取最小值MAX层取最大值一直算到根节点。根节点算出来的分数就是在双方都采取最优策略的情况下你能获得的最好结果。这个算法的核心假设是对手和你一样聪明每一步都会走最优的棋。这是一种悲观策略——不指望对手犯错只求在对手最完美的情况下自己也能拿到最好的结果。算法通常用深度优先搜索DFS来实现递归地遍历博弈树。如果树的深度是m每个节点有b个合法走法时间复杂度是O(b^m)——指数级增长这也是它最大的问题。五、Alpha-Beta剪枝砍掉没用的树枝极小化极大算法有个致命缺点太慢了。象棋每一步平均有几十种走法算10步就是几十亿个节点电脑根本扛不住。但仔细一想所有节点都需要算吗答案是不需要。Alpha-Beta剪枝就是用来砍掉那些不影响最终决策的树枝的。它的原理很朴素假如你已经在某个分支上找到了一个分数为10的走法现在正在看另一个分支。结果刚看了一步就发现这个分支最好也只能得5分——那你还继续往下看吗不用了因为就算这个分支后面的情况再好也不可能超过10分。算法维护两个值AlphaαMAX玩家目前能找到的最好分数下界。BetaβMIN玩家目前能接受的最差分数上界。当某个节点的分数已经不可能影响最终决策时就直接“剪掉”这个分支不再往下搜。Alpha-Beta剪枝不会改变最终结果——它和完整的极小化极大算法得出的结论一模一样。它只是跳过了那些没必要看的节点。在理想情况下走法顺序排得特别好能把搜索量从O(bm)减少到大约O(b(m/2))相当于同样的时间内可以多搜一倍的深度。六、负极大值算法让代码更简洁除了Alpha-Beta剪枝极小化极大算法还有一个常见的变体叫负极大值算法Negamax。原来的极小化极大算法需要写两个函数一个处理MAX层取最大值一个处理MIN层取最小值。负极大值算法的巧妙之处在于它把“取最小值”转换成了“取负数的最大值”。数学上很简单min(a, b) -max(-a, -b)。也就是说在MIN层我不需要专门取最小值只需要把所有分数取反然后统一取最大值就行了。这样一来整个算法只需要一个递归函数代码更加简洁优雅。负极大值算法本质上和极小化极大算法完全等价只是实现方式不同。七、深度限制与迭代加深现实世界的妥协理论上极小化极大算法可以一直搜到终局。但现实中象棋、围棋的博弈树实在太大了根本搜不完。所以实际应用中AI通常会设置一个搜索深度——比如只往前看6步或10步。搜到指定深度后就不再往下搜而是用评估函数给当前局面打分。这就是深度受限搜索Depth-Limited Search。但深度设多少合适呢设小了棋力不够设大了又太慢。迭代加深Iterative Deepening是一种聪明的折中方案先搜1层、再搜2层、再搜3层……直到时间用完为止。这样既能在时间紧张时快速给出一个“还行”的走法又能在时间充裕时搜得更深。八、蒙特卡洛树搜索另一条路最后简单提一下蒙特卡洛树搜索Monte Carlo Tree SearchMCTS。和极小化极大算法不同MCTS不靠评估函数打分而是靠大量随机模拟——让两个“随机玩家”从某个局面开始乱下一通看谁赢的次数多。模拟的次数越多统计结果就越可靠。MCTS的核心优势是不需要人工设计评估函数特别适合围棋这种评估函数极难设计的游戏。AlphaGo打败人类围棋冠军背后就是MCTS加深度学习的组合。不过MCTS和极小化极大是两种不同的思路各有各的适用场景不存在谁完全替代谁。总结把这篇文章的核心串起来就是这样博弈树是把整盘棋画成一棵可能性大树。评估函数是给每个半成品局面打分。极小化极大算法是在这棵树上做决策——MAX层取最大、MIN层取最小。Alpha-Beta剪枝砍掉不影响结果的树枝来提速。负极大值算法是让代码更简洁的实现方式。深度限制和迭代加深是现实世界中的妥协方案。而蒙特卡洛树搜索则提供了另一条完全不同的路。所有这些概念拼在一起就是AI下棋的决策密码——也是人工智能在博弈领域最经典的思想遗产。