与马尔可夫决策过程（不同，强化学习是一种**在线规划（Online Planning）**方法。在传统的MDP（离线规划）中，智能体**完全了解环境的转移函数和奖励函数**，并以此为基础预先计算出最优策略。...

Minimax算法的核心假设是对手总是做出最优选择，这使其在面对非最优或随机对手时显得过于悲观。例如，在棋牌或骰子游戏中，结果本身具有不确定性，Minimax的“最坏情况”分析不再适用。 **Expectimax搜索**是Minimax的泛化，专门用于处理这类不确定性。它在博弈树中引入了**机会节点（Chance Nodes）** 来取代Minimax中的最小化节点（Minimizer...

在传统搜索问题中，智能体可以使用搜索算法确定最佳计划并直接执行以达到目标。但在**对抗性环境**中，智能体面临一个或多个试图阻止其达成目标的对手。由于无法确定性地预知对手的策略和反应，传统搜索算法不再适用，我们需要新的算法类别来解决**对抗性搜索问题**，也就是**游戏**。 确定性零和游戏具有以下特点： - **确定性**：动作的结果是确定的，没有随机性 -...

与在确定的搜索问题中寻找一个通往目标状态的最优“计划”不同，解决一个马尔可夫决策过程意味着寻找一个**最优策略 (Optimal Policy)**。 策略 $\pi$ 是一个从状态 $s \in S$ 到动作 $a \in A$ 的映射，即 $\pi: S \to A$。它定义了一个“反射式”智能体：给定一个状态 $s$，智能体会立即选择动作 $a =...

马尔可夫决策过程（Markov Decision Processes, MDP）为智能体在不确定性环境中进行决策提供了一个数学模型。其核心思想是，智能体的下一个状态**只与当前状态和所选动作有关，而与之前的历史无关**。 一个MDP由以下几个关键部分定义： - **状态集合**：一个包含**所有可能状态**的集合 $S$。 -...

Minimax（极小化极大）是一种在**零和博弈**中做出决策的经典算法。其核心思想是，在一个回合制、信息完全的对抗游戏中，我方（MAX玩家）总是希望最大化自己的收益，而对手（MIN玩家）则总是希望最小化我方的收益。算法假定对手每一步都会做出最优选择。 一个状态的**值 (Value)** 指的是当前玩家从该状态出发所能获得的**最优结果**。 - **终止状态 (Terminal...

对于像围棋这样**分支因子**极大的应用，传统的Minimax及其变种算法因计算量过大而不再适用。**蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）** 为此类问题提供了强大的解决方案。 MCTS基于两个核心理念： 1. **通过模拟进行评估 (Evaluation by Rollouts)**：从一个状态 $s$...

策略迭代是一种用于在马尔可夫决策过程中寻找最优策略 $\pi^*$ 的算法。与值迭代相比，策略迭代通常能够更快地收敛，因为它**直接优化策略**，而策略的收敛速度往往比值的收敛速度快得多。 该算法的核心思想是：从一个任意的初始策略开始，通过一个迭代循环不断优化它，直到策略不再发生变化为止。每一次迭代都包含两个核心步骤：**策略评估**和**策略改进**。 | 特性 | 价值迭代...

价值迭代 (Value Iteration) 是一种经典的动态规划算法，用于在已知的马尔可夫决策过程中，计算所有状态的最优价值函数 $V^*(s)$。其核心思想是通过迭代的方式，不断更新每个状态的价值，直到价值收敛为止。 算法通过引入“时间限制”的概念，从一个有限的未来开始，**逐步扩展到无限的未来**，最终得到最优价值。 我们定义 $V_k(s)$ 为在状态 $s$ 出发，且**还剩下...

在约束满足问题中，**过滤（Filtering）** 是通过约束传播来缩小变量域的技术。过滤的核心思想是**在搜索过程中主动推理，提前发现和消除不可能的赋值**，从而显著减少搜索空间。 过滤不同于盲目的回溯搜索，它利用约束的结构信息进行**局部推理**，在赋值之前就排除明显不可行的选择，避免了大量无意义的搜索尝试。...