博弈树 · aiwiki.page

博弈树是一种带根的分支结构，用来表示一场博弈所有可能的展开方式。节点表示局面或博弈历史，边表示可采取的行动，终端节点则给出结果及其收益。在博弈论中，这一结构是策略互动的扩展式表示的基础；在人工智能中，它为通过考察可能的回应及未来后果来选择行动的算法提供支持。博弈树表示的是各种可能性，本身既不是策略，也不是搜索算法。(artint.info)

结构与解释

形式上，博弈树是一种有根的有向图，其中除根节点外，每个节点都恰有一个父节点。因此，从根节点到任意节点都只有一条路径。根节点表示初始情境，或分析开始时的当前情境。内部节点标明下一步行动的玩家，其出边则表示该玩家可采取的行动。从根节点到终端节点的一条路径描述了一个完整的博弈过程。(live.ocw.mit.edu)

每个终端结果都为每位玩家赋予一个数值效用。这些收益表达玩家对不同结果的偏好，不一定是金钱收益。随机抽取等偶然事件可以用由“自然”控制的节点表示，并在其出边上赋予一个概率分布。因此，博弈树既能描述确定性博弈，也能描述含有随机因素的博弈，以及涉及两位以上玩家的互动。(artint.info)

严格来说，节点可以用博弈历史来标识，即从根节点出发、到达该节点的行动序列。两段不同的历史可能产生表面上相同的局面，但由于到达路径不同，它们仍是不同的节点。完整的博弈树包含规则允许的所有后续发展，而搜索过程通常只构建其中的一部分。因此，这种局部搜索树的叶节点可能只是尚未结束的局面，而不是真正的终端结果。(ocw.mit.edu)

极小化极大算法与逆向评估

对于具有完全信息的确定性双人零和博弈，标准评估方法是极小化极大算法。其中一位玩家通常记作 MAX，其目标是最大化从自身角度衡量的收益；对手记作 MIN，其目标则是将该收益最小化。算法通过递归将终端收益向上传递：在 MAX 节点取子节点值中的最大值，在 MIN 节点取最小值。(inst.eecs.berkeley.edu)

用 $C(s)$ 表示节点 $s$ 的子节点集合，则递推关系为

V(s)= \begin{cases} U(s), & s\text{ 为终端节点},\\ \max_{t\in C(s)}V(t), & s\text{ 属于 MAX},\\ \min_{t\in C(s)}V(t), & s\text{ 属于 MIN}. \end{cases}

这里， $U(s)$ 是终端收益。对于完整的有限博弈树，这一方法能够确定 MAX 在对手采取最优应对时仍能保证获得的收益，以及实现该收益的行动。(inst.eecs.berkeley.edu)

例如，假设 MAX 要在两个分支之间作出选择。在第一个分支中，MIN 可以选择收益为 3 或 5 的终端结果；在第二个分支中，MIN 可以选择收益为 2 或 9 的终端结果。因此，两个分支的值分别为 3 和 2，MAX 会选择第一个分支。这说明，可达结果中的最高收益 9 并不一定对应最佳行动。

计算成本与选择性搜索

实际应用中的主要困难在于博弈树的规模。如果每个节点大约有 $b$ 个子节点，搜索深度为 $d$ ，那么穷尽式极小化极大搜索的时间复杂度为 $O(b^d)$ 。因此，分支因子和深度使计算量呈指数增长。深度优先的实现方式不必保存整棵树，但穷尽式评估仍可能难以实际执行。(inst.eecs.berkeley.edu)

Alpha–Beta剪枝可以跳过不会改变极小化极大结果的分支。它维护 MAX 和 MIN 已可获得的值的界限；当这些界限足以确定某个分支与最终结果无关时，就停止探索该分支。它保留根节点的极小化极大值，不过在多个同样好的行动之间，最终选择可能有所不同。其效果取决于行动的搜索顺序：理想的顺序可将搜索成本降至约 $O(b^{d/2})$ ，而最坏情况下仍为 $O(b^d)$ 。(inst.eecs.berkeley.edu)

另一种方法是限制搜索深度，并用启发式评估函数评估尚未结束的局面。这些估计值取代了精确的终端收益，使决策同时取决于评估质量和搜索深度。所得选择对于经过评估的截断树是最优的，但对于完整博弈未必最优。(inst.eecs.berkeley.edu)

随机因素与隐藏信息

在机会节点，评估采用期望值，而不是最大值或最小值：

V(s)=\sum_{t\in C(s)}p(t\mid s)V(t).

期望极大算法将最大化决策与这种概率评估相结合。它可以表示随机事件，也可以表示行动遵循特定概率模型的对手。随机对抗博弈则可以在同一棵树中同时包含 MAX、MIN 和机会节点。与极小化极大算法的最坏情况假设不同，概率评估依赖于所赋概率的准确性。(inst.eecs.berkeley.edu)

隐藏信息需要额外的结构。在扩展式博弈中，信息集将行动玩家无法区分的决策节点归为一组。策略必须为这些节点规定相容的行为，而不能利用玩家并不掌握的信息。完全信息对应于每个信息集只包含一个节点的情况。因此，普通的逐节点极小化极大算法不能直接求解任意不完全信息博弈。(ocw.mit.edu)

基于模拟与学习的搜索

蒙特卡洛树搜索通过反复模拟来评估各种可能性，同时有选择地扩展一棵局部树。其常规循环包括选择、扩展、模拟，以及沿已访问节点反向传播结果。搜索资源的分配需要兼顾探索与利用的权衡：既考察尚未充分测试的行动，也再次考察已有估计较为有利的行动。(inst.eecs.berkeley.edu)

树搜索还可以结合学习得到的策略和局面价值。在最初的 AlphaGo 系统中，人工神经网络提供落子概率和局面评估，并与蒙特卡洛树搜索结合，用于围棋。其策略网络和价值网络通过监督学习与强化学习进行训练。这些学习得到的组件引导探索和评估，无须枚举完整的博弈树。(storage.googleapis.com)

参考来源

Artificial Intelligence—10.2.2 Extensive Form of a Gameartint.info
Game Theory, Lecture Notesocw.mit.edu
Game Theory, Lecture 2: Equilibrium Refinementslive.ocw.mit.edu
2 Minimaxinst.eecs.berkeley.edu
6 Summaryinst.eecs.berkeley.edu
CS 188 Spring 2025, Lecture 7inst.eecs.berkeley.edu
3 Expectimaxinst.eecs.berkeley.edu
5 Monte Carlo Tree Searchinst.eecs.berkeley.edu
Mastering the game of Go with deep neural networks and tree searchstorage.googleapis.com