通用游戏博弈中的提升反向搜索策略

### 通用游戏博弈中的提升反向搜索策略 在通用游戏博弈（General Game Playing，GGP）领域，传统的蒙特卡罗树搜索（Monte Carlo Tree Search，MCTS）方法在评估游戏状态时存在一定的局限性。为了提高评估的准确性，本文提出了一种将 MCTS 与提升反向搜索（Lifted Backward Search）相结合的方法。 #### 1. 反向搜索在游戏博弈中的应用背景 在单智能体规划领域，曾有学者实现了一种启发式反向搜索算法 HSPr，但该算法会产生许多无法到达的“虚假状态”，因此效果并不理想。不过，后续有研究通过将前向搜索的一些常用技术扩展到反向搜索，改进了 HSPr 算法，创建了新的回归规划器 FDr。然而，提升反向搜索在具有对抗性智能体的领域中尚未得到应用。 #### 2. 基于反向搜索的玩家策略 传统的通用游戏博弈方法通常采用蒙特卡罗树搜索。该方法通过从游戏状态 w 开始进行随机移动模拟，直到到达终端状态，然后评估玩家在该终端状态的效用值，这个过程称为“滚动”（rollout）。多次重复滚动并取平均值，以估计状态 w 的真实效用值。但由于滚动是随机的，需要进行大量的滚动操作才能得到准确结果。 为了提高准确性，本文提出将 MCTS 与提升反向搜索相结合的策略。具体步骤如下： 1. **反向搜索阶段**：在应用 MCTS 之前，玩家先进行一段时间（例如 10 秒）的反向搜索。假设游戏是两个玩家 A 和 B 的轮流游戏，反向搜索会生成两个公式序列 α0, α1, α2 ... 和 β0, β1, β2 ...，并存储在内存中，供 MCTS 的滚动操作使用。 - α0 表示玩家 A 的获胜状态集合。 - α1 表示玩家 A 有一步行动可以导致获胜状态的所有状态集合。 - 一般来说，如果一个状态满足 αi，则意味着玩家 A 有策略保证下一个状态满足 αi - 1。 - βi 的含义与 αi 相反，β0 表示对手 B 的获胜状态，若一个状态满足 βi，则对手 B 可以强制下一个状态满足 βi - 1。 2. **MCTS 阶段**：反向搜索完成后，玩家应用 MCTS。在滚动过程中，对于每个探索到的游戏状态，算法会判断该状态是否满足任何 αi 或 βi。如果满足，则滚动可以提前终止，并返回相应的值：若满足 αi，则返回 100；若满足 βi，则返回 0。 这种方法不仅可以提前终止滚动，还能得到更准确的结果。例如，在某个状态 w 下，玩家 A 有 20 种可能的行动，只有一种行动能导致获胜状态（得 100 分），其他行动都导致平局（得 50 分）。传统的随机滚动只有 1/20 的概率选择到正确的获胜行动，而采用本文算法，滚动会检测到 w 满足 α1，从而始终返回正确的效用值 100。 此外，本文的反向搜索使用非接地公式，一个公式可以描述许多不同的状态。虽然生成这些公式可能需要大量时间，并且在最坏情况下公式大小可能会随 n 呈指数增长，但由于公式中包含变量，在许多情况下它们仍然相对紧凑。α0 和 β0 不一定代表终端获胜状态，也可以代表其他重要的游戏属性。例如在国际象棋中，α0 可以表示玩家 A 刚刚吃掉对手皇后的状态，此时滚动函数找到满足任何 αi 的状态时，将返回一个启发式值。 #### 3. 形式化定义 ##### 3.1 游戏的状态转换模型 游戏 G 被定义为一个元组 ⟨P, A, W, w1, T, L, u, U⟩，各部分含义如下： | 符号 | 含义 | | ---- | ---- | | P | 玩家集合，P = {A, B} | | A | 行动集合 | | W | 非空状态集合 | | w1 | 初始状态 | | T | 终端状态集合 | | L | 合法性函数，描述每个非终端状态下哪些行动是合法的 | | u | 更新函数，将每个状态和行动映射到一个新状态 | | U | 效用函数，为每个终端状态和玩家分配一个效用值 | 玩家 A 和 B 各有自己的行动集合 AA 和 AB，且 A = AA ∪ AB，AA ∩ AB = ∅。游戏由离散回合组成，玩家交替从各自的行动集合中选择行动，根据更新函数生成状态序列。在每个回合中，只有一个玩家可以选择行动，该玩家称为该回合的活跃玩家。 ##### 3.2 语法 本文使用一种自定义语言 L，它是一阶逻辑的一个片段。语言 L 从 GDL 借用基本组件，以便将 GDL 描述的游戏轻松转换为 L。L 包含特定于游戏 G 的有限常量、函数符号和关系符号，以及有限变量和逻辑连接词（¬, ∨, ∧, → 和 ∃）。L 继承了 GDL 中的一些与游戏无关的关系符号，如 distinct、true、does、legal、goal、terminal 和 next。 L 中的公式可以是复杂公式（通过 ¬, ∨, ∧ 或 ∃ 组合原子得到）或规则，规则形式为 p1 ∧ p2 ∧ ... pn → q，其中 pi 是正或负文字，q 是正文字。q 称为规则的头，pi 称为子目标，子目标的合取称为规则的体。规则的体可以为空（此时规则称为事实），子目标和头可以包含变量，变量用问号表示，如?x。 此外，语言 L 还有一些限制： - distinct、true 和 does 不能出现在任何规则的头中。 - legal、goal、terminal 和 next 不能出现在规则的体中。 同时，定义了一些特殊的概念： - 行动常量和行动函数：行动函数只能包含行动常量或在行动常量范围内取值的变量，包含行动函数的项称为行动项。 - 行动命题：形式为 does(t) 的接地原子。 - 依赖图：一组规则 R 的依赖图是一个有向图，每个出现在规则中的关系符号 p 对应一个顶点 vp，若有规则中 p 出现在体中且 q 出现在头中，则存在从 vp 到 vq 的边。若依赖图无环，则规则集 R 是无环的。 - 基本命题：形式为 true(t) 的命题，所有基本命题的有限集记为 B。 - 展开公式：只包含关系符号 distinct、true 和 does 的公式称为展开公式，否则称为未展开公式。 - 状态相关公式：若原子 ϕ 的关系符号 p 在依赖图中经过 vp 的所有路径都不经过对应关系符号 does 的顶点，则 ϕ 是状态相关的；若公式 φ 的所有原子都是状态相关的，则 φ 是状态相关公式，否则为非状态相关公式。 以下是这些概念的 mermaid 流程图： ```mermaid graph LR A[公式] --> B{是否为展开公式} B -- 是 --> C[展开公式] B -- 否 --> D[未展开公式] A --> E{是否为状态相关公式} E -- 是 --> F[状态相关公式] E -- 否 --> G[非状态相关公式] ``` ##### 3.3 语义 给定游戏 G 和语言 L，定义了一个估值函数 V：W → 2B，它将游戏的每个世界状态映射到不同的基本命题集合。当游戏处于状态 w 时，V(w) 中的命题被认为是真的，其他基本命题为假。同时，定义了一个双射映射 μ，将每个行动 a ∈ A 映射到一个接地行动项 ta。 满足关系的定义如下： - V, R ⊨(w,a) true(t) 当且仅当 true(t) ∈ V(w) - V, R ⊨(w,a) does(μ(b)) 当且仅当 a = b 且 a ∈ L(w) - V, R ⊨(w,a) distinct(t, s) 当且仅当 t ≠ s 对于非接地公式 φ，V, R ⊨(w,a) ∃φ 成立当且仅当存在一个替换 θ 使得 φ[θ] 是接地的且 V, R ⊨(w,a) φ[θ] 成立。对于规则集 R 中的原子 q，其前提定义为能与 q 统一的规则体，所有前提的析取称为 q 的完全前提，记为 Pr(q)。对于接地的未展开原子 q，V, R ⊨(w,a) q 当且仅当 V, R ⊨(w,a) ∃Pr(q)。对于接地公式 φ，其满足关系由命题逻辑连接词的标准解释以及上述定义递归确定。 游戏描述 G 是一个元组 ⟨L, V, μ, R⟩，其中 R 是有限且无环的，并且满足以下条件： - V, R ⊨(w,a) terminal 当且仅当 w ∈ T - V, R ⊨(w,a) legal(μ(a)) 当且仅当 a ∈ L(w) - V, R ⊨(w,a) next(t) 当且仅当 V ⊨ u(w,a) true(t) - V, R ⊨(w,a) goal(p, x) 当且仅当 U(w, p) = x #### 4. 反向搜索算法 玩家 A 的目标是使游戏达到同时满足 terminal 和 goal(A, 100) 的状态。为了提前确定是否能在未来状态中强制这些命题为真，本文应用一种算法来确定一系列展开的状态相关公式 α0, α1, α2 ...，直到时间耗尽。若状态 w 满足 αi，则玩家 A 可以在 i 轮内强制获胜。由于假设获胜者总是最后行动的玩家，若游戏处于满足 αi 的状态且 i 为奇数，则玩家 A 是活跃玩家；若 i 为偶数，则玩家 B 是活跃玩家。 为了解释这些公式的计算方法，定义了两个运算符：C 运算符和 N 运算符。这里先介绍 C 运算符。 ##### 4.1 C 运算符 C 运算符的作用是将任何公式重写为等价的展开公式，因为 N 运算符只能对展开公式进行操作。C 运算符的定义如下： - 对于任何项 t, s：C(true(t)) = true(t)，C(distinct(t, s)) = distinct(t, s)。 - 对于任何行动项 a：C(does(a)) = does(a) ∧ legal(a)。 - 对于任何未展开原子 q：C(q) = ∃Pr(q)。 - 对于任何非原子公式 φ，通过将 φ 中的每个原子 p 替换为 C(p) 得到 C(φ)。 例如，若 φ = q(t) ∧ does(a)，且规则集中只有 p1(?x) → q(?x) 和 p2(?y) → q(?y) 两条规则的头能与 q(t) 统一，则 C(φ) = (p1(t) ∨ p2(t)) ∧ does(a) ∧ legal(a)。 使用 C2(φ) 表示 C(C(φ))，Cn(φ) 表示 C(Cn - 1(φ))。由于规则集 R 是有限且无环的，对于任何公式 φ，存在某个 n 使得 Cn(φ) = Cn - 1(φ)，即序列 C1(φ), C2(φ) ... 总是收敛的，因此可以定义 C∞(φ) 为该序列的极限。 综上所述，本文提出的将 MCTS 与提升反向搜索相结合的方法，通过反向搜索生成的公式来提前终止 MCTS 的滚动操作，提高了游戏状态评估的准确性。同时，通过形式化定义游戏的状态转换模型、语言语法和语义，以及引入 C 运算符等，为算法的实现提供了理论基础。后续将继续介绍 N 运算符以及反向搜索算法的具体实现细节。 ### 通用游戏博弈中的提升反向搜索策略 #### 5. 反向搜索之 N 运算符 在了解了 C 运算符后，接下来介绍 N 运算符。N 运算符主要用于在反向搜索中，根据当前的展开状态相关公式生成下一轮的公式。 ##### 5.1 N 运算符的定义 N 运算符的输入是一个展开的状态相关公式 $\alpha$，输出是一个新的展开状态相关公式，该公式表示在当前状态下，经过一轮操作后能够达到满足 $\alpha$ 的状态集合。 具体定义如下： - 当 $\alpha$ 是 $true(t)$ 形式时： - 若当前活跃玩家是 A，$N(true(t)) = \bigvee_{a \in A_A} \exists \theta (next(t)[\theta] \wedge does(\mu(a))[\theta] \wedge legal(\mu(a))[\theta])$。这里的 $\theta$ 是一个替换，使得公式接地。其含义是对于玩家 A 的每个合法行动 $a$，存在一种替换使得在执行该行动后，下一个状态满足 $true(t)$。 - 若当前活跃玩家是 B，$N(true(t)) = \bigwedge_{a \in A_B} \exists \theta (next(t)[\theta] \vee \neg does(\mu(a))[\theta] \vee \neg legal(\mu(a))[\theta])$。即对于对手 B 的每个行动，要么执行该行动后下一个状态满足 $true(t)$，要么该行动不合法或者不被执行。 - 对于 $distinct(t, s)$ 形式的公式，$N(distinct(t, s))$ 的计算方式类似，根据活跃玩家的不同，分别考虑玩家的行动对 $distinct(t, s)$ 关系的影响。 - 对于 $does(a)$ 形式的公式，同样根据活跃玩家的不同进行相应的计算，以确保生成的公式能够准确反映经过一轮操作后满足 $does(a)$ 的状态。 以下是 N 运算符计算的流程图： ```mermaid graph LR A[输入展开状态相关公式 α] --> B{当前活跃玩家是谁?} B -- A --> C[按玩家 A 规则计算 N(α)] B -- B --> D[按玩家 B 规则计算 N(α)] C --> E[输出新的展开状态相关公式] D --> E ``` ##### 5.2 反向搜索公式的生成过程 利用 C 运算符和 N 运算符，反向搜索公式 $\alpha_0, \alpha_1, \alpha_2 \cdots$ 的生成过程如下： 1. 初始化 $\alpha_0$：$\alpha_0 = terminal \wedge goal(A, 100)$。这表示游戏的获胜状态。 2. 利用 C 运算符将 $\alpha_0$ 转换为等价的展开公式：$\alpha_0 = C(\alpha_0)$。 3. 迭代生成后续公式： - 对于 $i = 1, 2, \cdots$，计算 $\alpha_i = N(\alpha_{i - 1})$。 - 再将 $\alpha_i$ 通过 C 运算符转换为展开公式：$\alpha_i = C(\alpha_i)$。 这个过程会一直进行，直到时间耗尽。 以下是生成过程的列表说明： 1. 确定初始公式 $\alpha_0$ 为获胜状态。 2. 对 $\alpha_0$ 应用 C 运算符，得到展开的 $\alpha_0$。 3. 进入迭代循环： - 计算下一轮公式 $\alpha_i$ 为 $N(\alpha_{i - 1})$。 - 对 $\alpha_i$ 应用 C 运算符，更新为展开公式。 - 检查时间是否耗尽，若未耗尽则继续迭代。 #### 6. 算法的优势与应用场景 ##### 6.1 算法优势 - **提高评估准确性**：通过提前生成一系列公式 $\alpha_i$ 和 $\beta_i$，在 MCTS 的滚动过程中，能够快速判断当前状态是否具有获胜或失败的潜力，从而提前终止滚动，减少不必要的计算，提高对游戏状态评估的准确性。例如在前面提到的状态 w 中，能够准确识别出获胜行动，避免随机滚动的不确定性。 - **使用非接地公式**：反向搜索使用非接地公式，一个公式可以描述多个不同的状态，使得算法在处理复杂游戏时具有更好的泛化能力。虽然生成公式可能耗时，但在很多情况下，由于公式包含变量，其大小相对紧凑，不会过度占用计算资源。 ##### 6.2 应用场景 - **双人轮流游戏**：该算法适用于像国际象棋、跳棋、井字棋等双人轮流游戏，这些游戏通常有明确的胜负规则，且满足获胜者总是最后行动的玩家这一假设。 - **离散回合制游戏**：对于在离散回合中进行的游戏，算法可以通过确定每一轮的行动和状态转换，有效地提前规划获胜策略。 以下是算法优势和应用场景的表格总结： | 方面 | 详情 | | ---- | ---- | | 算法优势 | 提高评估准确性、使用非接地公式 | | 应用场景 | 双人轮流游戏、离散回合制游戏 | #### 7. 总结与展望 本文提出的将 MCTS 与提升反向搜索相结合的方法，为通用游戏博弈提供了一种有效的解决方案。通过反向搜索生成的展开状态相关公式，能够在 MCTS 中提前判断游戏状态的胜负潜力，提高了游戏状态评估的准确性。同时，形式化定义的游戏模型、语言语法和语义，以及 C 运算符和 N 运算符的引入，为算法的实现和计算提供了坚实的理论基础。 未来的研究可以考虑以下几个方向： 1. **放宽无环假设**：目前算法假设游戏描述的规则集是无环的，未来可以研究如何放宽这一假设，使算法能够应用于更广泛的游戏场景。 2. **优化公式生成**：进一步优化 C 运算符和 N 运算符的计算效率，减少公式生成的时间开销，提高算法的实时性。 3. **拓展应用领域**：尝试将该算法应用于更多类型的游戏，如多人游戏、连续动作游戏等，探索其在不同游戏环境中的适用性和有效性。 综上所述，该算法在通用游戏博弈领域具有重要的研究价值和应用前景，通过不断的优化和拓展，有望在更多的游戏场景中发挥作用。