从零开始理解博弈搜索：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 Search，MCTS）。
和极小化极大算法不同，MCTS不靠评估函数打分，而是靠大量随机模拟——让两个“随机玩家”从某个局面开始乱下一通，看谁赢的次数多。模拟的次数越多，统计结果就越可靠。
MCTS的核心优势是不需要人工设计评估函数，特别适合围棋这种评估函数极难设计的游戏。AlphaGo打败人类围棋冠军，背后就是MCTS加深度学习的组合。
不过MCTS和极小化极大是两种不同的思路，各有各的适用场景，不存在谁完全替代谁。
总结
把这篇文章的核心串起来就是这样：
博弈树是把整盘棋画成一棵可能性大树。评估函数是给每个半成品局面打分。极小化极大算法是在这棵树上做决策——MAX层取最大、MIN层取最小。Alpha-Beta剪枝砍掉不影响结果的树枝来提速。负极大值算法是让代码更简洁的实现方式。深度限制和迭代加深是现实世界中的妥协方案。而蒙特卡洛树搜索则提供了另一条完全不同的路。
所有这些概念拼在一起，就是AI下棋的决策密码——也是人工智能在博弈领域最经典的思想遗产。
