这一页讲的是对抗搜索的两种方法：Minimax 和 MCTS。

这一页讲的是对抗搜索（Adversarial Search），重点介绍了两种算法：Minimax 和 MCTS（Monte Carlo Tree Search）。对抗搜索是人工智能中用于解决博弈问题的重要技术，尤其在棋类游戏或其他竞争性环境中。Minimax 是一种基于递归的算法，用于在完全信息博弈中寻找最优策略，通过评估每个可能的行动来最大化自己的得分，同时最小化对手的得分。MCTS 则是一种基于统计的搜索方法，通过模拟大量随机样本路径来估计行动的价值，适用于信息不完全或搜索空间较大的问题。这两种方法在游戏 AI 和决策系统中具有广泛应用，理解它们的原理和适用场景对学习 AI 基础非常重要。

这一页讲的是学习目标，包括游戏问题的特点、对抗性游戏树和搜索算法的应用。

这一页讲的是学习目标，主要围绕对抗性搜索和游戏树展开。首先，要求描述不同类型游戏问题的特点，这可以帮助理解游戏问题的结构和复杂性。其次，学习如何构建对抗性游戏树（adversarial game tree），这种树用于模拟两个玩家的决策过程。接着，重点介绍如何应用极小极大算法（minimax algorithm）来寻找游戏树中的最佳下一步，这是一种常见的对抗性搜索方法。第四个目标是识别在资源有限条件下进行对抗性搜索的策略，这对于实际应用中的效率优化非常重要。最后，学习蒙特卡洛树搜索（Monte Carlo Tree Search）的原理，这是一种基于随机模拟的搜索算法，适用于复杂的决策问题。例如，在棋类游戏中，蒙特卡洛树搜索可以通过大量模拟来评估每一步的潜在价值，从而找到最优解。

这一页讲的是免责声明 (Disclaimer)，说明幻灯片内容的来源。

这一页讲的是免责声明 (Disclaimer)，主要强调幻灯片的内容来源于几位学者的工作。具体来说，这些幻灯片改编自 Pieter Abbeel 和 Dan Klein 的 UC Berkeley CS188 课程，以及 Mike Barley 和 Pat Riddle 的工作（来自奥克兰大学 UoA）。此外，幻灯片中的插图也来源于 Pieter Abbeel 和 Dan Klein 的 UC Berkeley CS188 课程。这一页的目的是明确知识产权归属，确保引用的内容具有权威性和可信度。

这一页讲的是游戏的类型与其特征轴，定义游戏为多代理环境，并介绍算法如何制定应对计划。

这一页讲的是游戏的类型与其特征轴。首先，游戏被定义为一种任务环境，其中至少有一个以上的代理（agent）。接着，幻灯片列出了游戏分类的几个关键轴（axes）：是否是确定性（deterministic）或随机性（stochastic）？信息是否完全可观察（perfect information）？参与者是一个、两个还是多个玩家？游戏是轮流进行（turn-taking）还是同时进行（simultaneous）？是否为零和游戏（zero sum）？这些特征对游戏的复杂性和策略设计有直接影响。最后，幻灯片强调了需要算法来计算应对计划（contingent plan），即一种策略或政策，可以针对每一种可能的情况推荐行动。这种计划在复杂的游戏环境中尤为重要，例如在多玩家同时参与的随机性游戏中，通过制定有效的策略可以提高胜率。例如，扑克牌游戏中玩家需要根据对手的行为和牌面信息制定动态的策略，这就需要一个强大的应对计划来指导决策。

这一页讲的是确定性游戏的形式化定义，包括状态、玩家、动作和关键函数。重点是玩家的解决方案是一种策略 (policy)。

这一页讲的是确定性游戏 (Deterministic Games) 的形式化定义。首先，游戏的状态 (States) 是 S，初始状态为 s₀。玩家集合是 P={1...N}，通常轮流行动。动作 (Actions) 是 A，可能依赖于玩家或当前状态。状态和动作通过转移函数 (Transition Function) S×A → S 来更新。终止测试 (Terminal Test) 是一个函数 S → {t, f}，用于判断游戏是否结束。终止效用 (Terminal Utilities) 是一个函数 S×P → R，表示玩家在某状态下的收益。最后，玩家的解决方案定义为一种策略 (policy)，即从状态 S 映射到动作 A 的函数。通过这些定义，可以清晰地描述游戏的规则和目标。例如，在棋类游戏中，状态可以表示棋盘布局，动作是玩家的移动，转移函数决定棋盘的更新方式，终止测试判断是否结束，而终止效用则评估胜负结果。这些概念为设计和分析确定性游戏提供了理论基础。

这一页讲的是零和博弈 (Zero-Sum Games) 和一般博弈 (General Games)。零和博弈中双方效用相反，一方获利另一方损失；一般博弈中双方效用独立，可能存在合作或竞争。

这一页讲的是博弈论中的两种类型：零和博弈 (Zero-Sum Games) 和一般博弈 (General Games)。零和博弈的特点是参与者的效用 (utility) 完全相反，属于纯竞争关系。例如，蓝色机器人试图最大化自己的收益，而红色机器人则试图最小化蓝色机器人的收益。这种博弈中，一方的胜利意味着另一方的失败。相对而言，一般博弈的参与者效用是独立的，不必完全对立，可能存在合作、竞争或无关的情况。例如右侧的图中，两个机器人可能同时获取资源，但也可能发生冲突或形成联盟。这种博弈更复杂，允许多样化的互动形式，如合作、联盟转变或竞争。理解这两种博弈类型对于设计人工智能策略至关重要，因为它们决定了如何优化决策以及应对不同的环境和对手。

这一页讲的是游戏问题和谜题问题的区别。游戏问题涉及不可预测的对手和时间限制，而谜题问题没有对手，环境可预测，目标是通过系统搜索找到最优解。

这一页讲的是游戏问题 (Games) 和谜题问题 (Puzzle problems) 的区别。游戏问题的特点是需要应对不可预测的对手，因此需要为每种可能的对手反应制定策略。同时，游戏问题通常有时间限制，导致无法找到精确的最优解，只能近似解决。而谜题问题则没有对手，环境是可预测的，问题的目标通常是通过系统化搜索找到最优解。比如，在国际象棋中，玩家需要预测对手的下一步并制定策略，这属于游戏问题；而解决数独则是一个谜题问题，因为没有对手，环境完全由规则定义，目标是找到唯一的正确解。理解这两类问题的差异有助于选择合适的算法和策略来解决不同类型的问题。

这一页讲的是对抗搜索（Adversarial Search），用于解决竞争环境中的决策问题。重点是模拟双方策略并预测对手行为。

这一页讲的是对抗搜索（Adversarial Search），它是人工智能中用于处理竞争性环境的一种搜索方法。对抗搜索通常应用于棋类游戏、博弈问题等需要考虑对手策略的场景。页面中的图像表现了两个机器人之间的竞争关系，其中蓝色机器人在思考红色机器人的策略，而红色机器人也在反过来预测蓝色机器人的行为。这种互动体现了对抗搜索的核心思想：每个参与者都试图最大化自己的收益，同时最小化对手的优势。对抗搜索的基本方法包括 Minimax 算法，它通过递归地评估每个可能的行动结果，找到最优决策。此外，Alpha-Beta 剪枝进一步优化了搜索效率，通过剪枝不必要的分支减少计算量。对抗搜索的重要性在于它能够帮助智能体在复杂的竞争环境中做出合理决策，例如在国际象棋或围棋中预测对手的下一步行动。

这一页讲的是 Single-Agent Trees (单智能体树) 的结构与搜索路径。重点包括树的分层结构、节点间的决策过程，以及最终目标值的计算。

这一页讲的是 Single-Agent Trees (单智能体树)，用于描述单一智能体在搜索问题中的决策过程。图中展示了一棵树结构，顶部为根节点，代表初始状态。每个节点分支表示智能体在不同选择下的状态转移。树的底部是叶节点，标注了具体的数值，例如 2、0、2、6 等，这些数值通常代表目标函数的值或评估分数。智能体通过树的层次结构逐步探索，最终选择路径以达到最大化或最优化目标值。图中显示了一个典型的搜索过程，其中智能体会比较不同分支的结果，例如选择 8 作为最终的最佳路径值。这种树结构在人工智能搜索算法中非常重要，例如用于实现深度优先搜索 (DFS) 或广度优先搜索 (BFS)，帮助智能体高效地找到最优解。

这一页讲的是状态的价值 (Value of a State)。主要内容包括状态价值的定义、终止状态和非终止状态的计算方式，以及树状图示例。

这一页讲的是状态的价值 (Value of a State)，即从某个状态出发能够达到的最佳结果或效用 (utility)。幻灯片中定义了两种状态：终止状态 (Terminal States) 和非终止状态 (Non-Terminal States)。终止状态的价值是已知的，直接给出，例如图中底部的三角形标注了具体数值（如 2、0、6 等）。非终止状态的价值通过递归计算，公式为 V(s) = max V(s')，其中 s' 是当前状态的后继状态 (successors)。树状图展示了一个状态空间的结构：从根节点开始，每个非终止状态的价值由其子节点的最大值决定。例如，右侧非终止状态的子节点中有一个终止状态值为 8，因此该非终止状态的价值为 8。这种计算方法在强化学习和搜索问题中非常重要，可以帮助我们找到最优路径或策略。

这一页讲的是状态价值函数(Value of a State)在单智能体搜索树中的定义。核心公式是：某个状态 s 的价值 V(s) 等于所有后继状态 s' 中 V(s') 的最大值，即 V(s) 等于对所有 successors(s) 里的 s' 取 max V(s')；而终止状态的 V 直接由游戏规则给出。这个定义奠定了整个 minimax 框架的基础。直觉上，「最优价值」就是「如果我从这个状态出发走最聪明的一步，最终能拿到的最好结果」。以图中例子理解：叶节点已知具体数值（如 8、2、0、6 等），父节点取子节点中的最大值向上传播，最终根节点得到的就是整局游戏的最优可达得分。考试常考：能手算一棵给定叶值树的每个节点价值；以及理解 V(s) 是定义在「当前决策者总是做最优选择」这一前提下的——单智能体时只有 max 层，引入对手之后就变成 minimax 的交替 max/min。易错点：很多同学会把「终止状态的 V 是已知的」和「非终止状态需要递归计算」混淆，导致递归基准情况写错。记住：只有叶节点才直接用游戏结果定义值，其他节点全靠递归。

这一页讲的是对抗性游戏树 (Adversarial Game Trees)，主要展示了游戏树结构、评分值以及决策过程的层级关系。

这一页讲的是对抗性游戏树 (Adversarial Game Trees)，它是一种用于决策分析的树状结构，特别适合描述两方对抗的场景，比如游戏中的玩家与对手。幻灯片中展示了一个典型的游戏树，顶部是初始状态，接着分为两层：第一层是玩家的决策节点，第二层是对手的决策节点。每个节点都有可能的行动分支，最终到达叶子节点，叶子节点标注了对应的评分值 (如 -20, -8, +4 等)。这些评分值代表了玩家在该路径下的收益或损失。通过树的结构，可以看到玩家和对手的行为是交替进行的，玩家试图最大化自己的收益，而对手试图最小化玩家的收益。这种树通常用于实现 Minimax 算法，通过逐层回溯评分值，帮助玩家选择最优策略。例如，玩家会选择一个路径，使得对手的最坏行为对自己影响最小。图中 Pac-Man 和幽灵的图像直观地表达了对抗性场景，帮助理解游戏树的应用。

这一页讲的是井字棋(Tic-Tac-Toe)的游戏树结构及其终端状态的效用值。主要展示了 MAX 和 MIN 玩家在不同层级的决策过程，以及终端状态的评分规则。

这一页讲的是井字棋(Tic-Tac-Toe)的游戏树结构，重点分析 MAX 玩家(X)和 MIN 玩家(O)在游戏中的决策过程。图中展示了一个完整的游戏树，从初始状态开始，经过每一层的玩家轮流决策，逐步展开所有可能的棋盘状态。每一层由不同玩家控制，MAX 玩家试图最大化效用值，而 MIN 玩家试图最小化效用值。树的底部是终端状态(Terminal)，即游戏结束时的棋盘状态。紫色区域列出了几种终端状态及其对应的效用值(Utility)：+1 表示 MAX 赢，-1 表示 MIN 赢，0 表示平局。这种评分规则帮助算法评估每个状态的优劣，从而选择最佳策略。通过这种树结构，可以直观理解井字棋的所有可能路径及其结果。举个例子，若某状态下 MAX 玩家能确保胜利，则该路径会被优先选择。

这一页讲的是 Minimax 算法的值计算过程。重点包括 MAX 节点由 Agent 控制，MIN 节点由 Opponent 控制，以及终端状态值已知。

这一页讲的是 Minimax 算法的值计算过程，用于决策树中寻找最优策略。MAX 节点由 Agent 控制，计算公式为 V(s) = max V(s')，即选择后继状态中值最大的路径；MIN 节点由 Opponent 控制，计算公式为 V(s) = min V(s')，即选择后继状态中值最小的路径。幻灯片中的树结构展示了这一过程：终端状态的值已知（如 -5、-10 和 +8），通过向上回溯，MAX 节点选择最大值（如 -8），MIN 节点选择最小值（如 -10）。最终得出根节点的值为 -8。这种算法在博弈论中非常重要，可以帮助智能体在面对对手时做出最优决策。例如在棋类游戏中，Minimax 算法可以预测对手的行为并制定最佳策略。

这一页讲的是 Minimax 算法中 MAX 节点与 MIN 节点的交替结构及对应的价值定义，是整个对抗搜索的核心机制。规则只有两条：MAX 节点（我方决策）取所有子节点值的最大值；MIN 节点（对手决策）取所有子节点值的最小值；终止节点直接返回已知效用值。从图中可以看到一棵 3 层树，叶节点有 +8、-10、-5、-8 等数值；MIN 层会取最小（如 -8 = min(-5, -8)），MAX 层再取最大（如 -8 = max(-8, -10, -8)）。直觉是：我方总是挑对自己最有利的走法，对手则总是挑对我方最不利的走法，双方都被假设为「理性最优」。这里的关键假设是「对手是完全理性的(rational adversary)」——minimax 给出的是在最坏情况下你能保证得到的最优结果，即「最优最坏情况保证」。考试常见题型：给定完整博弈树，手动计算每个节点的 minimax 值，然后指出根节点应选哪一步。易错点：层的方向搞反——哪一层是 MAX 哪一层是 MIN 需要结合题目判断是谁先手；另外别忘了 MIN 节点取最小，很多人在算大题时因为习惯性取 max 而出错。

这一页讲的是对抗搜索(Adversarial Search)中的极小极大算法(Minimax)。主要内容包括零和游戏的特点、极小极大搜索的原理，以及递归计算极小极大值的过程。

这一页讲的是对抗搜索(Adversarial Search)中的极小极大算法(Minimax)。首先，零和游戏(Zero-sum games)是确定性的游戏，例如井字棋(Tic-tac-toe)、国际象棋(Chess)和跳棋(Checkers)，其中一个玩家试图最大化结果，而另一个玩家试图最小化结果。极小极大搜索(Minimax search)基于状态空间搜索树(State-space search tree)，玩家轮流进行操作。每个节点的极小极大值(Minimax value)表示在面对理性对手时能够实现的最佳效用。幻灯片右侧的图展示了极小极大值的递归计算过程：从终端节点(例如值为8、2、5、6的节点)开始，逐层向上计算。最底层的值是游戏的终端值(Terminal values)，中间层的“min”节点选择子节点中的最小值，而顶层的“max”节点选择子节点中的最大值。最终结果是根节点的极小极大值，代表最佳决策。这个算法在AI中用于解决棋类游戏等对抗性问题。

这一页讲的是 Minimax 算法的正式定义和核心属性，包括时间复杂度、空间复杂度、完备性和最优性。算法本质就是对博弈树做深度优先搜索（DFS），在 MAX 层取最大值、在 MIN 层取最小值，直至叶节点。时间复杂度是 O(b 的 m 次方)，其中 b 是分支因子，m 是树的最大深度；空间复杂度是 O(b 乘以 m)，因为 DFS 只需要记录当前路径。完备性：若博弈树有限，算法必然终止，结果是完备的。最优性：若对手也是最优的，minimax 给出的策略是最优的。但这一页最精彩的部分是现实数字：国际象棋中 b 约等于 35，m 约等于 100，因此节点数约等于 35 的 100 次方，大概是 10 的 154 次方，而宇宙中原子总数也只有 10 的 78 到 82 次方之间。这说明精确 minimax 在实际中完全不可行，必须引入剪枝或评估函数。考试常考：计算给定 b 和 m 下 minimax 的时间复杂度，以及为什么需要 alpha-beta 剪枝。易错点：空间复杂度——很多人误写成 O(b 的 m 次方)，但因为是 DFS，同一时刻只需保存从根到当前节点的路径，所以空间是线性的 O(bm)，不是指数级的。

这一页讲的是 Minimax 算法的示例，展示如何在决策树中选择最优策略。关键点包括最大化和最小化节点的计算过程。

这一页讲的是 Minimax 算法的示例，用一个决策树来说明算法的工作原理。图中展示了一个三层的树结构，底层节点是具体的数值（如 3, 12, 8 等），中间层和顶层节点分别表示最小化和最大化的决策。首先，底层的数值被传递到中间层的最小化节点，最小化节点会选择其子节点中的最小值，例如左侧的 '3' 是从 {3, 12, 8} 中选出的最小值。然后，最小化节点的值被传递到顶层的最大化节点，最大化节点会选择其子节点中的最大值，例如顶层的 '3' 是从 {3, 2, 2} 中选出的最大值。这一过程体现了 Minimax 算法的核心思想：在对手试图最小化收益的情况下，选择能够最大化自己收益的策略。这种算法广泛应用于博弈问题，例如棋类游戏中，帮助玩家预测最佳行动。

这一页讲的是 Alpha-Beta 剪枝（Alpha-Beta Pruning）策略，以及在时间有限时使用深度截断加评估函数（Evaluation Function）的有界前瞻（Bounded Lookahead）方案，是对抗搜索中最重要的实用技术。Alpha-Beta 的核心思路：在搜索过程中维护两个参数，alpha 是当前路径上 MAX 节点迄今见到的最优（最大）下界，beta 是当前路径上 MIN 节点迄今见到的最优（最小）上界。一旦某个 MIN 节点的当前最小值已经小于等于其祖先 MAX 节点的 alpha，就说明这条分支无论继续搜索结果如何，外层 MAX 节点都不会选它——直接剪掉（beta cutoff 同理）。节点生成顺序非常关键：如果好棋先被搜索到，剪枝效果最好，时间复杂度可从 O(b 的 m 次方) 降至 O(b 的 m/2 次方)，相当于分支因子从 b 降为根号 b，即「搜索深度翻倍」。有界前瞻部分：把搜索截断到某个预设深度，叶节点不再是游戏终止状态，而是用一个评估函数（Evaluation Function）估计当前棋面的价值——可以是特征的线性加权，也可以是神经网络。代价是失去「对最优对手最优」的保证，但深度越深、评估函数越好，实际效果通常越好。考试考点：能描述 alpha 和 beta 各自的含义；能手动模拟剪枝过程判断哪些节点会被剪掉；理解节点顺序对剪枝效率的影响。易错点：分不清 alpha cutoff（在 MIN 节点剪枝）和 beta cutoff（在 MAX 节点剪枝），以及搞混「剪枝不影响根节点最终选择」这个核心性质。

这一页讲的是 Minimax 算法的性质，包括效率、完整性和最优性，并通过国际象棋的例子说明其计算复杂性。

这一页讲的是 Minimax 算法的性质。首先，Minimax 的效率类似于穷举深度优先搜索 (DFS)，时间复杂度为 O(b^m)，空间复杂度为 O(bm)，其中 b 是每个节点的分支数，m 是树的最大深度。其次，Minimax 在树是有限的情况下是完整的 (Complete)，并且在面对最优对手时能够提供最优解 (Optimal)。幻灯片还通过国际象棋的例子说明了计算复杂性：在象棋中，b 约为 35，m 约为 100，因此状态空间大小为 35^100，大约是 10^154，比宇宙中原子的数量（10^78 到 10^82）还要多。这表明精确求解在实际中完全不可行。这些性质强调了 Minimax 算法的理论优势和实际计算的局限性。

这一页讲的是有限资源下的策略，重点是游戏树剪枝（Game tree pruning）。主要介绍了 Alpha-Beta 剪枝的原理，以及生成顺序对剪枝效果的影响。

这一页讲的是有限资源下的策略，具体是游戏树剪枝（Game tree pruning）。Alpha-Beta 剪枝是一种优化搜索算法的方法，它通过剪掉那些不可能比当前最佳选择更优的分支，减少计算量。在右侧的图中，展示了一个游戏树，红色三角形表示 MAX 节点，紫色方块表示叶节点的效用值（utility value）。Alpha 值表示当前路径上 MAX 节点的最佳选择，例如图中 α=3，表示当前路径的最佳效用值为 3。剪刀图示说明了某些分支被剪掉，因为它们的效用值显然不会超过 α=3。此外，幻灯片强调了生成顺序的重要性：如果好的选择先被生成，剪枝效果会更显著。例如，右侧的分支在 α=3 的情况下，后续的效用值如 14 不会被考虑，因为它已被剪枝。这种方法在减少搜索空间的同时保持了结果的准确性，是人工智能搜索算法中的重要优化策略。

这一页讲的是有限资源情况下的搜索策略，包括游戏树剪枝和有限展望两种方法。

这一页讲的是有限资源情况下的搜索策略，主要包括两种方法：游戏树剪枝（Game tree pruning）和有限展望（Bounded lookahead）。游戏树剪枝中最常用的是 Alpha-Beta 剪枝，它通过剪除那些会导致较低效用值的分支，从而减少计算量，保留当前最优选项。图中展示了一个简单的 Alpha-Beta 剪枝过程，其中最大节点和最小节点交替选择最优值。有限展望策略则是通过设定搜索深度限制（depth limit）或视野范围（horizon），仅搜索到预定的深度。对于非终端状态，使用评估函数（evaluation function）来估计效用值，该函数可以是简单的线性组合，也可以是更复杂的非线性模型（如神经网络）。然而，这种方法无法保证绝对最优的游戏表现。深入的搜索通常能带来更好的结果，而更高质量的评估函数则可以在较浅的搜索深度下实现更好的表现。这两种策略在资源有限的情况下非常重要，能够显著提高搜索效率并优化决策。

这一页讲的是 Monte-Carlo Tree Search (MCTS)。它是一种用于决策和搜索的算法，特别适合在巨大搜索空间中找到最佳策略。

这一页讲的是 Monte-Carlo Tree Search (MCTS)，它是一种基于概率和模拟的搜索算法，常用于解决复杂的决策问题，例如棋类游戏或机器人规划。MCTS 的核心思想是通过模拟未来可能的行动路径，逐步扩展搜索树，并根据模拟结果优化决策。Monte-Carlo 方法利用随机抽样来估算某些状态的价值，而树搜索则通过逐步扩展节点来探索最优路径。这种方法的优势在于它可以在不需要完全搜索整个空间的情况下，找到近似最优解。幻灯片中的图片可能是为了形象化“Monte-Carlo”这一术语，暗示其与概率和随机性相关。一个简单的例子是围棋中，MCTS 可通过模拟不同的落子路径，评估每一步的胜率，从而选择最优策略。

这一页讲的是 Monte-Carlo Tree Search (MCTS) 的核心思想，包括选择性搜索和通过模拟进行评估。

这一页讲的是 Monte-Carlo Tree Search (MCTS)，它结合了两个重要的概念：选择性搜索 (Selective search) 和通过模拟进行评估 (Evaluation by rollouts)。选择性搜索的核心是探索树中的部分节点，这些节点能够帮助改进根节点的决策，而不受树深度的限制。这种方法避免了对整个搜索空间的全面探索，提升了效率。通过模拟进行评估的方式是从某个状态 s 开始，使用简单且快速的 rollout 策略，进行多次游戏直到结束，并记录胜负情况。这种评估方法通过统计大量模拟结果来预测某个状态的可能结果，从而为决策提供依据。例如，在棋类游戏中，MCTS可以从当前棋盘状态出发，模拟多次对局来评估每一步的潜在价值。

这一页讲的是蒙特卡洛搜索中的 Rollouts 方法，强调通过模拟对局评估棋盘位置的价值。主要讨论了 Rollout 策略的重要性。

这一页讲的是蒙特卡洛搜索中的 Rollouts 方法。Rollouts 是一种模拟对局的方法，用于评估棋盘上某个位置的价值。具体来说，每次 Rollout 会重复进行，直到对局结束。在模拟过程中，按照一个固定且快速的 Rollout 策略（rollout policy）进行落子，并记录最终结果，例如胜负情况。通过多次模拟，可以计算胜率（fraction of wins），而这个胜率通常与该位置的真实价值相关联。幻灯片还指出，拥有一个更好的 Rollout 策略可以显著提高模拟的效果。右侧的围棋棋盘图展示了一个特定的棋局位置（“Move 37”），其中紫色和黄色标记可能代表不同策略的模拟结果。通过这种方法，可以帮助人工智能更准确地评估棋盘位置的优劣。例如，如果一个位置的胜率较高，说明它可能是一个更优的选择。这种方法广泛应用于棋类游戏的 AI 中，如 AlphaGo。

这一页讲的是蒙特卡洛树搜索（MCTS）的基本版本，强调通过模拟选取最佳动作。

这一页讲的是蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）的Version 0版本。主要内容包括两个步骤：第一，从根节点的每个子节点进行 N 次模拟（rollouts），记录胜利的比例；第二，根据胜率选择能够带来最佳结果的动作。图中展示了一个简单的树结构，蓝色三角形代表根节点，红色三角形是子节点。每个子节点下方标注了模拟结果，例如左边子节点的胜率为57/100，中间为39/100，右边为65/100。通过比较这些胜率，可以看到右边子节点的胜率最高，因此在这个版本中会选择右边的动作。这种方法的直觉是通过大量模拟估计每个动作的潜在收益，从而指导决策。虽然简单，但这种方法可能忽略了探索的长期价值，需要进一步优化。

这一页讲的是 MCTS (Monte Carlo Tree Search) Version 0.9 的改进，通过将模拟分配给更有潜力的节点。

这一页讲的是 MCTS (Monte Carlo Tree Search) Version 0.9 的优化方法，其核心是通过分析节点的表现，将更多的模拟次数分配给更有潜力的节点。图中展示了一个树形结构，其中蓝色三角形表示根节点，红色三角形表示子节点。每个子节点下面有一个统计值，例如 '77/140' 表示该节点的成功次数为 77，总模拟次数为 140。通过比较不同节点的统计值，可以看出右侧节点 '90/150' 的成功率更高，因此会被分配更多的模拟次数，而中间节点 '0/10' 的表现较差，可能会被减少分配。这样的方法可以提高搜索效率，集中资源在更可能获得较好结果的路径上。这种机制在实际应用中可以显著提升搜索算法的性能，尤其是在复杂的决策问题中，例如游戏 AI 或路径规划。

这一页讲的是 MCTS Version 1.0 的节点分配策略，包括分配到更有潜力的节点和更不确定的节点。

这一页讲的是 MCTS Version 1.0（蒙特卡洛树搜索）的节点分配策略。主要讨论如何合理分配模拟次数（rollouts）。第一点是将更多的模拟分配到更有潜力的节点，这样可以集中资源探索可能的最佳路径。第二点是将更多的模拟分配到更不确定的节点，以减少决策中的不确定性。图中展示了一个树结构，顶部蓝色节点通过箭头连接到三个红色子节点，每个子节点下面都有一个紫色框，框内的数字表示该节点的模拟次数和总次数。例如，左侧节点的数字是 48/110，表示该节点已经进行了 48 次模拟，总计分配了 110 次。通过这些数字可以看出，模拟次数的分配是基于节点的潜力和不确定性。这样的策略可以提高搜索效率，找到更优的解决方案。

这一页讲的是 UCB (Upper Confidence Bound) 的启发式方法，重点介绍 UCB1 公式如何结合“有前途性”和“不确定性”，并讨论探索与利用的平衡。

这一页讲的是 UCB (Upper Confidence Bound) 的启发式方法，主要用于解决探索与利用 (Exploitation vs Exploration) 的问题。UCB1 公式的核心思想是结合节点的“有前途性”和“不确定性”。公式中，U(n) 表示节点 n 的总效用，例如节点的胜利次数；N(n) 表示从节点 n 出发的总模拟次数。公式的第一部分 U(n)/N(n) 反映了节点的平均效用，代表“有前途性”；第二部分 C × √(logN(PARENT(n))/N(n)) 则衡量了节点的不确定性，C 是一个调节参数，决定探索的力度。公式通过这两部分的加权组合，动态调整选择节点的优先级。探索与利用的平衡在许多领域都非常重要，例如蒙特卡洛树搜索 (MCTS) 中的决策优化。举例来说，如果某节点的效用高但模拟次数少，公式会倾向于进一步探索该节点，以验证其潜力。

这一页讲的是 UCB（Upper Confidence Bound）启发式公式，也是 MCTS 中「选择（Selection）」步骤的核心数学依据。UCB1 公式把每个节点的得分表示为两部分之和：第一项是 U(n) 除以 N(n)，也就是该节点的平均胜率（exploitation，利用已有信息）；第二项是 C 乘以根号下 log(N(parent)) 除以 N(n)（exploration，探索不确定节点）。其中 N(n) 是节点 n 被访问的次数，U(n) 是该节点累计赢局数，N(parent) 是父节点的总访问次数，C 是平衡探索与利用的超参数。直觉上，第一项高的节点说明「胜率高、值得继续押注」，第二项高的节点说明「访问次数少、很多未知」——两项之和最高的节点是下一轮应该展开的最优候选。这个「exploitation vs. exploration」的权衡是 MCTS 最核心的设计哲学，也是它比 minimax 更适合大空间（如围棋）的根本原因：不必全宽搜索，而是把计算资源集中在看起来最有潜力的分支上。考试常考：能描述 UCB1 公式两项各自的含义；理解为何 N(n) 很小时第二项大（鼓励探索）、N(n) 大时第一项主导（利用知识）。易错点：把 N(n) 和 U(n) 的分子分母搞混；另外要注意当 N(n) 为 0 时节点未被访问，通常规定优先选择，以避免除以零。

这一页讲的是 MCTS Version 2.0 中的 UCT 方法，重点是如何通过 UCB 算法递归选择路径到叶节点。

这一页讲的是 MCTS Version 2.0 中的 UCT (Upper Confidence Trees) 方法，它是一种基于蒙特卡洛树搜索的改进算法。主要内容是重复执行以下步骤直到时间耗尽：在当前搜索树中递归应用 UCB (Upper Confidence Bound) 算法，选择路径到达叶节点。右侧的图展示了一个搜索树的结构，其中每个节点包含两个数值，分别表示当前节点的访问次数和总奖励值。通过 UCB 算法，系统可以在探索未知路径和利用已知高奖励路径之间找到平衡，从而选择最优路径。比如，从根节点开始，算法会根据 UCB 公式选择访问奖励较高的分支（如 7/10），并逐步深入到叶节点（如 3/3）。这一过程确保了搜索效率和决策质量。这种方法在游戏 AI 和决策系统中非常重要，能够有效处理不确定性和复杂性。

这一页讲的是 MCTS 的完整版本 UCT（Upper Confidence Trees）算法的四个步骤及其终止条件，是 MCTS 考试中最常考的流程题。UCT 的循环直到时间耗尽为止，每次迭代包含三步。第一步 Selection（选择）：从根节点出发，递归应用 UCB 公式选择分值最高的子节点，一路向下直到达到叶节点 n。第二步 Expansion and Simulation（扩展+模拟）：若 n 不是终止节点，为 n 新增一个子节点 c，并从 c 出发用快速随机的 rollout 策略模拟对局直到终局，记录结果（胜或负）。第三步 Backpropagation（反向传播）：将模拟结果从 c 沿路径回传到根节点，更新路径上每个节点的 N(n) 和 U(n)。更新规则是不对称的：若 MAX 赢了，则路径上的 MAX 节点 U 加一，MIN 节点不加；反之亦然——这体现了对抗搜索中两方利益相反的本质。最终决策：时间到后，选择根节点中访问次数 N 最高的子节点对应的动作（注意：不是 UCB 分最高，而是 N 最高，因为 N 高意味着被充分验证过）。当 N 趋向无穷时，UCT 的行为逼近 minimax 的结果。考试常考：能写出或描述 UCT 四步流程；能解释 backprop 时 MAX/MIN 节点更新规则不同的原因。易错点：把最终决策误认为选 UCB 最高的孩子，正确答案是选 N 最高的孩子。

这一页讲的是 MCTS Version 2.0 的 UCT 方法，包括选择、扩展和模拟的过程。

这一页讲的是 MCTS Version 2.0 的 UCT（Upper Confidence Trees）方法。UCT 是一种基于蒙特卡洛树搜索的优化算法，结合了 UCB（Upper Confidence Bound）策略，用于选择路径。幻灯片的主要内容分为两个步骤：第一步是选择（selection），通过递归应用 UCB 策略，从当前搜索树中选择路径到叶节点；第二步是扩展和模拟（expansion & simulation），如果选中的节点不是终端节点，就为该节点添加一个新的子节点，并从该子节点运行模拟（rollout）。右侧的图展示了扩展和模拟的过程，树的节点记录了访问次数和成功次数，灰色节点表示已经扩展的部分，而白色节点表示尚未访问的部分。这种方法通过不断重复上述步骤，在有限时间内优化搜索树结构，最终找到最优解。举例来说，在游戏决策中，UCT 可以帮助智能体选择最优行动路径。

这一页讲的是 MCTS Version 2.0 中的 UCT (Upper Confidence Trees) 算法。重点包括递归应用 UCB 选择路径、节点扩展与模拟、以及胜率的回溯更新。

这一页讲的是 MCTS Version 2.0 中的 UCT (Upper Confidence Trees) 算法，它是一种基于蒙特卡洛树搜索的改进方法。主要流程包括三个步骤：第一，使用 UCB (Upper Confidence Bound) 算法递归选择路径，找到叶节点 n，这一步称为 selection；第二，如果 n 不是终止节点，则扩展一个新的子节点 c，并从 c 开始进行模拟，这一步是 expansion 和 simulation；第三，使用 backpropagation 从 c 回溯更新胜率到根节点。页面右侧的树状图展示了回溯更新的过程，节点中的数字表示胜率和访问次数，例如根节点显示 11/22，表示 22 次访问中有 11 次胜利。此外，页面还提到效用函数 U(n) 的更新规则：如果是 MAX 节点胜利，MAX 节点胜率增加，MIN 节点不变；如果是 MAX 节点失败，则 MIN 节点胜率增加，MAX 节点不变。这个算法通过平衡探索与利用，提高了搜索效率和决策质量。

这一页讲的是 MCTS Version 2.0 的 UCT算法。主要包括 UCT 的执行步骤：选择、扩展与模拟、回溯，以及如何选择最优动作。

这一页讲的是 MCTS Version 2.0 的 UCT (Upper Confidence Trees) 算法。UCT 是一种基于蒙特卡洛树搜索的优化方法，核心思想是通过 UCB (Upper Confidence Bound) 策略选择路径并不断更新节点信息。执行步骤包括：第一，选择 (selection)，从当前搜索树中递归应用 UCB 策略，找到一个叶节点 n；第二，扩展与模拟 (expansion & simulation)，如果 n 不是终止节点，则添加一个新子节点 c 并从 c 开始进行模拟；第三，回溯 (backpropagation)，将 c 的胜率信息更新回根节点。右侧的树图展示了回溯过程，节点的分数表示胜率与总模拟次数的比值。最后，UCT 会选择胜率最高的子节点作为最优动作。随着模拟次数 N 增加，UCT 会逐渐收敛到类似极小极大 (minimax) 算法的行为。这种方法对探索和利用之间的平衡非常重要，例如在博弈中选择下一步动作时，可以通过 UCT 更有效地评估策略。

这一页讲的是蒙特卡洛树搜索（MCTS）中的UCT算法步骤，包括选择、扩展、模拟和回溯。

这一页讲的是蒙特卡洛树搜索（MCTS）中的UCT（Upper Confidence Bound for Trees）算法的四个主要步骤：选择（Selection）、扩展（Expansion）、模拟（Simulation）和回溯（Backpropagation）。首先，选择阶段通过UCT公式选择当前树中最优的节点进行探索。接着，在扩展阶段，算法会为选中的节点添加新的子节点，扩展搜索空间。然后，在模拟阶段，算法从新节点开始进行随机模拟，评估可能的结果。最后，在回溯阶段，模拟结果会向上回传到根节点，更新各节点的统计数据（如胜率）。图中展示了这四个阶段的树结构变化，例如在回溯阶段，根节点的统计数据从11/21更新为11/22，反映了模拟结果对整体树的影响。这些步骤确保了算法可以在有限时间内有效探索搜索空间，并逐步优化决策。

这一页讲的是 UCT 树与 Minimax 树的对比。主要说明了 Minimax 树是全宽度树，UCT 树是非对称树，并随着 N 增长趋向 Minimax 树。

这一页讲的是 UCT 树（Upper Confidence Tree）与 Minimax 树的结构和特性对比。Minimax 树是一种全宽度树，它会在某个深度边界内展开所有可能的节点，适合用于完全搜索的环境。而 UCT 树是一种非对称树，它根据探索与利用的平衡逐步扩展节点，通常不会展开所有可能的路径，但随着模拟次数 N 的增加，UCT 树的结构会逐渐趋向于 Minimax 树。左图展示了 UCT 树的非对称结构，右图则是 Minimax 树的规则对称结构。通过这种对比可以看出，UCT 树更适合在资源有限的情况下进行决策，而 Minimax 树则适合在计算资源充足时进行全面搜索。举例来说，在棋类游戏中，UCT 树可以通过蒙特卡洛搜索快速找到合理的策略，而 Minimax 树则可以通过完全搜索找到最优解。

这一页讲的是 MCTS (Monte Carlo Tree Search) 的演示资源，包括博客、代码库和视频链接。

这一页讲的是 MCTS (Monte Carlo Tree Search) 的演示资源，提供了几个链接供学习和实践。首先，页面列出了一个博客链接(http://beej.us/blog/data/monte-carlo-method-game-ai/)，详细介绍了 MCTS 在游戏 AI 中的应用原理。接下来是三个 GitHub 代码库链接，分别展示了 MCTS 在不同游戏中的实现：Tetris、Pac-Man 和 Connect Four。这些代码库可以帮助学习者理解 MCTS 的具体实现方式及其在不同游戏中的效果。此外，页面还提供了两个 YouTube 视频链接，可能是关于 MCTS 的讲解或演示。这些资源结合了理论和实践，适合对 MCTS 感兴趣的学生进一步探索其应用场景和实现细节。

这一页讲的是 AlphaGo 的核心搜索方法 Monte Carlo Tree Search (MCTS)，以及它如何结合学习模型提升效率。重点包括策略网络和价值网络的功能。

这一页讲的是 AlphaGo 的搜索框架 Monte Carlo Tree Search (MCTS)，并通过结合学习模型来优化搜索过程。MCTS 是一种基于概率的搜索算法，用于探索可能的动作路径。AlphaGo 使用两种神经网络来增强 MCTS 的性能：策略网络 (Policy Network) 和价值网络 (Value Network)。策略网络负责推荐最有希望的动作，从而减少搜索的分支因子 b，集中搜索资源，提高效率。价值网络则预测某个位置的结果（胜率），并与模拟结果结合，以提高评估的准确性和稳定性。通过这种方式，MCTS 提供了搜索框架，而神经网络使搜索更高效且信息更充分。例如，在围棋中，策略网络可以快速找到可能的最佳下一步，而价值网络可以评估当前棋盘的胜负概率，从而帮助 AlphaGo 做出更有依据的决策。

这一页讲的是 AlphaGo 如何把 MCTS 和神经网络结合，构成当时 AI 里程碑式的突破。AlphaGo 的架构以 MCTS 为骨架，加入两个神经网络。策略网络（Policy Network）的作用是在 Selection/Expansion 步骤中缩小分支因子——对当前棋面预测出「哪几步最值得下」，只扩展高概率的走法，避免无效分支爆炸。价值网络（Value Network）的作用是在 Simulation 步骤中替代（或补充）随机 rollout——直接给出当前棋面的胜率估计，比随机 rollout 更准确且更快。两者的融合公式是：节点评估值等于 (1-lambda) 乘以价值网络输出 加上 lambda 乘以 rollout 胜率，lambda 是混合系数。这样既保留了 rollout 的无偏蒙特卡洛特性，又利用了神经网络的位置理解能力。关键思想总结：MCTS 提供搜索框架，神经网络让搜索更高效、更精准。对比纯 minimax：围棋分支因子约 250，深度数百步，minimax 完全不可行；MCTS 加策略网络把有效分支因子压缩到个位数级别，配合价值网络减少 rollout 深度，才使超人水平的围棋 AI 成为可能。考试常考：Policy Network 和 Value Network 各自解决什么问题（减小 b vs. 减小 m/提升评估精度）；以及 MCTS+NN 整体架构的高层次描述。易错点：混淆两个网络的分工，或误以为 AlphaGo 完全抛弃了 rollout（实际上 AlphaGo 用了混合评估，AlphaGo Zero 才完全用价值网络替代 rollout）。

这一页讲的是搜索算法的分类与应用，包括 Uninformed Search、Informed Search 和 Adversarial Search 的特点及用处。

这一页讲的是搜索算法的分类与应用。首先，Uninformed Search（无信息搜索）是一种盲目探索的方法，因为它没有使用任何额外信息来指导搜索，因此在处理大型问题时效率较低。其次，Informed Search（有信息搜索）则利用启发式（heuristics）来引导搜索，能够找到更优的解决路径。启发式方法通过提供额外信息帮助算法更快地接近目标。最后，Adversarial Search（对抗搜索）主要用于处理竞争环境，例如游戏领域。蒙特卡洛树搜索（MCTS）结合启发式方法（如 UCB1），可以在非常大的游戏空间中实现高效决策，例如 AlphaGo 的应用。页面还推荐了进一步学习的资源：《Artificial Intelligence: A Modern Approach (AIMA)》的第 3 到 5 章，提供了更深入的理论与实践内容。