基于信息的Alpha-Beta搜索与杀人司机游戏

# 基于信息的Alpha - Beta搜索与杀人司机游戏 ## 1. 动机 在许多系统中，局部最优（“贪婪”）的控制决策不一定是全局最优的控制决策。为了得出最优或近似最优的控制策略，某种“前瞻”机制是必要的。基于树的搜索技术在一些复杂离散系统的前瞻方面已被证明很强大，但难以应用于连续或混合系统。原因之一是需要对控制动作进行先验离散化，而找到一个好的离散化方案往往并不容易。 ### 1.1 局部最优与全局最优的差异 许多最优控制技术试图通过性能指标梯度的最陡上升或下降来优化性能指标。虽然这些“贪婪”控制动作在局部是最优的，但在有限或无限时间范围内不一定是最优的。 - **离散系统示例**：以国际象棋为例，如果性能指标基于物质优势，采用贪婪策略的玩家可能会因对手巧妙的弃子策略而失败。有远见的玩家会超越眼前的收益，考虑其后续影响。 - **连续系统示例**：在一个追逃游戏中，一个稍快的追捕者追逐逃避者。贪婪的逃避者会直接朝着与追捕者相反的方向逃跑以保持最大距离，而有远见的逃避者会先冲向追捕者然后转向侧面，使自己处于追捕者后方，暂时增加接近度，但最终能显著减少接近度。 - **混合系统示例**：可以想象一个具有环境约束（如危险空域、地形特征等）的追逃游戏。 ### 1.2 树搜索技术的应用与局限 在状态空间较小且有限（或连续、混合状态空间可近似为此类）的情况下，可以应用动态规划来计算全局最优控制策略，但这种情况在实践中很少见。随着状态空间维度的增加，所需的内存或离散化的粒度会呈指数级增长，使得这些方法不可行。 然而，当满足以下条件时，可以从树搜索技术中受益： 1. 可以为系统导出近似的连续或混合仿真模型。 2. 使用该模型进行有限的前瞻可以提高性能。 3. 对动作空间（即可能的控制输入向量空间）的采样足以做出良好的决策。 标准搜索方法的一个缺点是假设动作（即控制输入）被预先离散化为有限的动作集。找到一个好的控制输入离散化方案通常不是一件容易的事，而且在搜索前确定离散化方案后，无法利用搜索过程中获得的信息来形成更好的离散化。 ## 2. Alpha - Beta搜索 ### 2.1 人工智能搜索算法的本质 人工智能（AI）搜索算法本质上是一种优化形式。与其他优化形式的主要区别在于，搜索算法是对动作序列（即控制向量序列）的效用（即性能指标）进行优化。与多阶段问题的最优控制公式不同，AI搜索不假设阶段数是有限的，但由于计算的必要性，搜索通常倾向于较短的动作序列。任何能从检查短序列控制决策的影响中受益的过程都可以从这种优化形式中受益。 ### 2.2 经典AI游戏树搜索问题的定义 经典AI游戏树搜索问题的定义涉及离散系统动力学，由三个组件组成： 1. 初始状态（包括系统状态和当前玩家）。 2. 后继函数（从状态到可能的未来状态集的映射）。 3. 效用函数（从状态到处于该状态的价值的映射）。 也可以将后继函数拆分为两部分： - 操作符函数（从状态到合法动作集的映射）。 - 从状态和动作到结果状态的映射。这种形式通常更容易通过定义可能的动作来间接定义可能的状态。 ### 2.3 经典AI游戏树搜索算法的工作方式 从包含初始状态的未搜索状态集开始，迭代地选择并移除一个未搜索状态，评估其效用，生成可能的未来状态，并将这些状态添加到未搜索状态集中。在任何时候，搜索算法都会搜索搜索树的一部分，并可以通过将效用传播到树上修改对动作的估值。由于状态可以在树中重复，树中某个位置的特定状态称为节点。不同的算法在选择下一个未搜索状态的方式上会有所不同，并且由于大多数搜索树无法被彻底搜索，不同的算法也有不同的停止条件。 ### 2.4 Alpha - Beta剪枝优化 虽然极小极大算法可用于评估游戏搜索树，但对于零和游戏，通过一种称为Alpha - Beta剪枝的技术可以使这个过程显著更高效。在搜索过程中，如果可以通过零和约束证明理性玩法永远不会导致某个节点，则可以“剪枝”（即停止）从该节点的搜索。 在零和游戏中，每个节点有一个单一的效用值，一个玩家（MAX）试图最大化这个效用，另一个玩家（MIN）试图最小化它。在每个搜索节点，跟踪两个值α和β。从根节点到一个节点的路径上，α是MAX的最佳得分，β是MIN的最佳得分。在根节点，α为 -∞，β为∞。 #### 计算MAX - Value(s, α, β)的步骤： 1. 如果状态s是终端状态或触发搜索的终止条件，则返回s的效用。 2. 对于状态s中MAX的每个合法动作a： - 设状态s′是动作a在状态s中的结果。 - 将α设置为α和MIN - Value(s′, α, β)中的较大值。 - 如果α大于或等于β，则“剪枝”搜索并返回β。 3. 返回α。 #### 计算MIN - Value(s, α, β)的步骤