这个章节主要讨论了竞争环境中的搜索算法。

极小化极大搜索

这种搜索算法是与或搜索的一种推广，在与或搜索的基础上增加了剪枝。极小化极大值是建立在零和博弈的基础上，一方获益，另一方必然损益。

某一状态的极小化极大值是指：假设从该状态到博弈结束两个参与者都以最优策略行动，到达的终止状态对于 MAX 的效用值。

MAX 倾向于移动到极小化极大值最大状态，MIN 倾向与移动到极小化极大值最小状态。MAX 表示获益方，它的目标是尽可能取得最大利益。MIN 表示损失方，它的目标 是尽可能减少利益损失。

极小化极大搜索是对博弈树进行深度优先搜索。

算法优化策略

alpha-beta 剪枝技术。此技术得名于 Max-Value(state, alpha, beta)中的两个额外参数。他们分别是路径上任何位置的倒推值的下界和上界。

alpha-beta 剪枝技术实际是基于博弈双方的收益特性对算法进行的优化。虽然剪枝技术可以减少搜索的状态空间，但是搜索的顺序会影响减枝的效果。 所以引入了启发式评价函数。

启发式评价函数解决了剪枝效果的问题，但剪枝是剪去后面的状态空间，当前向有多个可选择状态，也需要一种优化算法，在这样的思想基础上 出现了前向剪枝。前向剪枝将剪掉哪些看上去很糟糕但也可能实际很好的移动。前向减枝是以出错风险增大的代价节省了计算时间。

蒙特卡罗搜索

此算法从当前状态开始做N次模拟，并记录从当前局面开始哪一种可能移动胜率最高。模拟结果会反向传播，更新每个节点的胜负积分。之后使用得分最多的状态

function Monte-Caro-Tree-Search(state) returns 一个动作
    tree = Node(state)
    while Is-Time-Remaining() do
        leaf = select(tree)
        child = expand(leaf)
        result = Simulate(child)
        Back-Propagate(result, child)
    return Actions(state)中指向模拟次数最多的节点的移动

包含随机因素的博弈

博弈树除了 Max 和 Min 节点外，还必须包括机会节点。此算法需要引入计算获胜概率的评价函数。

本章研究多智能体环境中的博弈搜索，核心概念：

博弈树与极小化极大算法

双方轮流行动：MAX（己方）追求最大收益，MIN（对手）追求最小收益。

递归求解：MAX节点取子节点最大值，MIN节点取子节点最小值。

Alpha-Beta剪枝

维护两个参数：α（MAX当前最好下界），β（MIN当前最好上界）。

当α ≥ β 时剪枝，无需探索剩余分支。

剪枝效率严重依赖移动顺序（先搜好走的）。

评估函数与深度截断

因状态空间巨大，无法搜索到终局，需用评估函数启发式估计非终局状态的价值。

评估函数应与获胜概率正相关。

地平线效应：深度截断可能错过关键事件（如即将发生的吃子），通过静止搜索（quiescence search）缓解。

蒙特卡洛树搜索（MCTS）

核心步骤：选择（如UCB）、扩展、模拟（随机走子）、反向传播。

适用于分支因子极大、难以写评估函数的博弈（如围棋、非完美信息博弈）。

部分可观测博弈（简要提及）

信息集、随机博弈、决策质量受限于观测信息。