Games -- Expectimax, Monte Carlo Tree Search
这一讲涉及到的是一个更复杂、也更贴近现实的博弈世界。 核心的转变是：从处理确定性的、纯粹策略对抗的博弈，转向包含随机性或机会元素 (chance) 的博弈。
在之前的Minimax博弈中，只有两个玩家：MAX和MIN。MAX的每一个行动，MIN都会用最优的策略来回应。然而，在许多现实世界的博弈中，例如扑克或双陆棋，结果不仅仅取决于你和对手的选择，还取决于机会——比如你摸到什么牌，或者掷出什么样的骰子。
为了在这种不确定的环境中做出理性决策，我们不能再简单地假设最坏情况的发生，而是需要计算期望的结果。
Expectimax
Expectimax 是 Minimax 算法的一个直接扩展，专门用于处理包含机会节点的博弈。
在博弈树中，除了原有的MAX节点（我方决策）和MIN节点（对手决策），我们引入了机会节点。
机会节点代表了环境中的随机事件（如掷骰子）。从机会节点出发的每条边代表一个可能发生的随机结果，并且每条边都关联一个概率。
例如, 在一个掷骰子的游戏中，机会节点会有6个子节点，分别对应掷出1到6点，每个子节点的概率都是1/6。
在Expectimax 的计算规则中, MAX 节和MIN 节点都与 MINIMAX一致, 选择效用最大/最小的节点, 核心区别在于机会节点：机会节点的值不是取最大或最小值，而是计算其所有子节点效用的期望值 (Expected Value)，即加权平均值。
- 公式：Value(ChanceNode) = Σ(P(outcomeᵢ) * Value(childᵢ))
另外值得注意的是, 在Expectimax中，评估函数的绝对数值变得至关重要.
以往在Minimax中，评估函数的相对顺序占据主导。只要 EVAL(A) > EVAL(B)，我们就会选择A。
但在Expectimax中，因为我们要计算加权平均值，所以一个评估值为100和一个评估值为10，在计算期望时会产生截然不同的结果。一个微小的可能性乘以一个巨大的回报（或损失），可能会完全改变最终的期望效用。
Expectimax 同样需要遍历博弈树，其时间复杂度与Minimax类似，为 O(bm)（其中 b 现在也包括了机会节点的分支）。对于分支因子巨大（如围棋）或深度很深的博弈，它仍然是不可行的
蒙特卡洛树搜索 (Monte Carlo Tree Search - MCTS)
传统的博弈算法，如 Minimax 和 Alpha-Beta 剪枝，试图通过深度搜索和逻辑推理来找到最佳行动。它们就像一个深思熟虑的棋手，试图穷尽所有可能性来评估一个局面的好坏。然而，当博弈变得极其复杂时（例如，围棋的分支因子高达361），这种“深度思考”在计算上是不可行的。
蒙特卡洛树搜索 (MCTS) 采用了一种截然不同的、更接近人类直觉的策略。它放弃了对博弈树的完整遍历，转而通过进行大量、快速、随机的模拟对局 (playouts) 来评估一个局面的潜力。
想象一下，你正在下一个你不太懂的棋。为了决定下一步怎么走，你不在脑海里进行复杂的逻辑推演，而是采用一种更简单的方法：对于每个可能的下一步，你都和朋友快速地、随机地把这盘棋下完，下个几百盘。最后，你发现从某个特定的第一步出发，你赢的次数最多。于是，你就决定走这一步。
这就是 MCTS 的精髓：用统计上的成功概率来代替静态的、手工设计的评估函数。
MCTS 的四个核心步骤
MCTS 算法通过一个不断重复的循环来逐步构建一棵不对称的、聚焦于有希望区域的搜索树。每一次循环都包含以下四个步骤：
- 选择 (Selection): 在已经构建的搜索树中，找到一个最有潜力的、值得进一步探索的“叶”节点。
从根节点（当前真实的游戏局面）开始，算法会根据一个选择策略，一层一层地向下走。这个策略必须巧妙地平衡两个目标：
利用 (Exploitation)：倾向于选择那些过去表现很好（胜率高）的节点。
探索 (Exploration)：也要给那些探索次数较少的节点一些机会，因为它们可能潜力巨大，只是我们还没发现。
常用策略：UCT (Upper Confidence bounds applied to Trees) 是一种非常流行的选择策略，它通过一个公式来计算每个节点的“紧迫性”，完美地平衡了利用和探索。
- 扩展 (Expansion): 当“选择”步骤到达一个叶节点时，我们需要扩展这棵树的边界。
- 算法会为这个叶节点创建一个或多个新的子节点，代表从该局面出发可以采取的、之前从未探索过的行动。
- 模拟 (Simulation / Playout): 快速地对新扩展的节点进行一次“价值评估”。
- 从新扩展的某个子节点开始，算法会进行一次完全随机（或者基于一个非常简单的策略）的快速对局，直到游戏分出胜负。这个过程不需要动脑筋，只需要速度快。
- 模拟（Simulation） 阶段完全脱离了已有的博弈树。它从一个新节点（树的叶子）出发，进入一个“想象中的”对局。它不需要再访问树中的任何其他节点，也不需要构建新的树节点。它只是在一个临时的游戏状态副本上，一路“走到底”。
- 反向传播 (Backpropagation): 将模拟的结果反馈给搜索树，更新我们的“知识库”。
- 模拟的结果（赢或输）会沿着“选择”阶段的路径，从下至上地传回根节点。路径上的每一个节点都会更新它们的统计数据，例如赢的次数 (wins)和总模拟次数 (visits)
这个“选择 -> 扩展 -> 模拟 -> 反向传播”的循环会进行成千上万次。当分配的时间用尽时, 此时经过大量的迭代后，根节点的每个子节点都积累了大量的统计数据。最终，算法会选择那个被访问次数最多且胜率也较高的子节点所对应的行动。
UCT (Upper Confidence bounds applied to Trees) - 应用于树的上置信界
UCT 并不是一个全新的算法，而是将 UCB (Upper Confidence Bound) 公式具体应用到蒙特卡洛树搜索 (MCTS) 的”选择 (Selection)“阶段的策略。为了更好地理解UCT，我们先介绍其理论基础——UCB算法。
UCB 算法基础
UCB (Upper Confidence Bound) 是一种通用的决策算法，专门用于解决多臂老虎机问题 (Multi-Armed Bandit Problem)。这个问题正是”探索与利用”困境的经典模型。
想象一下，你走进一家赌场，面前有多台老虎机（Slot Machine）, 这些老虎机看起来一模一样，但每台老虎机吐出奖励的概率（或者说奖励的期望值）是不同的，而且这个概率对你来说是未知的。 你的目标是在有限的尝试次数内，最大化你获得的总奖励。
而UCB 为每一个可选项（比如，每一台老虎机，或者 MCTS 中的每一步棋）计算一个综合分数：
UCB 分数 = 当前平均回报 + 探索奖励
1. 当前平均回报 (Exploitation Term)
- 含义：该选项到目前为止的平均表现
- 在MCTS中：节点的当前胜率 (赢的次数 / 总访问次数)
- 作用：值越高，说明该选项在过去的试验中表现越好，越有理由”利用”它
2. 探索奖励 (Exploration Term)
- 含义：鼓励尝试那些被选择次数较少的选项的奖励项
- 特点：奖励大小与该选项被访问的次数成反比
- 作用：访问次数越少，不确定性越大，探索其潜在价值的收益越高
3. 决策机制
算法选择UCB分数最高的选项，自动在”已被证明是好的”和”可能是更好的未知选项”之间做出权衡。
UCT 在 MCTS 中的应用
在 MCTS 的选择步骤中，当算法从一个非叶节点（父节点P）向下选择子节点时，它将P的所有子节点视为一个”多臂老虎机问题”。算法为每个子节点C计算UCT值，并选择值最高的子节点继续探索。
UCT 公式详解
公式组成部分：
利用项：
探索项：
公式工作原理：
探索阶段：当子节点C的访问次数N很小时，分母N很小，导致探索项的值很大，该节点更有可能被选中（鼓励探索）
利用阶段：随着子节点被访问次数N的增加，探索项逐渐减小，节点选择更多地取决于其胜率
（鼓励利用） 平衡机制：探索常数c控制探索与利用的平衡程度，较大的c值倾向于更多探索，较小的c值倾向于更多利用