题目分析

我们有一个 $R \times C$ 的棋盘，每个格子是 J（贾斯汀）或 D（唐纳德）的棋子。 规则：

贾斯汀先手；

每回合，当前玩家选择自己的一个棋子，移动到相邻的格子（上下左右），并吃掉该格子的棋子（可以是己方或对方）；

不能移动就输；

玩家不是完全理性的，而是有一个失误因子 $A$：

如果当前可走步数 $\le A$，则考虑所有走法；

如果可走步数 $> A$，则只选择 $A$ 种走法（选择最优的 $A$ 种，即能最大化自己获胜概率的 $A$ 种）；

然后从这些走法中随机等概率选择一种执行。

给定 $J$（贾斯汀的失误因子）和 $D$（唐纳德的失误因子），求贾斯汀获胜的概率。

思路解析

1. 状态表示 棋盘最多 $13$ 格，每个格子可能是：

空（用 0 表示）

J 的棋子（用 1 表示）

D 的棋子（用 2 表示）

我们可以用一个长度为 $R \times C$ 的三进制数来表示整个棋盘状态。 或者更简单地，用一个长度 $R \times C$ 的字符串（或整数数组）表示，配合记忆化。

2. 基本博弈框架 这是一个轮流移动的博弈，可以用递归函数 win(state, turn, J, D) 表示：

state 是当前棋盘状态

turn = 0 表示贾斯汀走，turn = 1 表示唐纳德走

返回当前玩家在最优选择下的获胜概率

边界情况：

如果当前玩家没有合法移动，则当前玩家输（返回 0.0 如果当前是贾斯汀，返回 1.0 如果当前是唐纳德？这里要小心：win 我们定义为贾斯汀获胜的概率，所以如果贾斯汀不能走，概率=0；如果唐纳德不能走，概率=1）。

3. 考虑失误因子 假设当前玩家是贾斯汀（turn=0）：

找出所有合法移动（枚举自己的每个棋子，检查四个方向，如果目标格有棋子（J或D）就可以吃）；

对每个移动，得到新状态，递归计算 win(new_state, 1-turn, J, D)（即贾斯汀在新状态下的获胜概率）；

如果可走步数 m <= J，则贾斯汀会全部考虑，获胜概率 = 这些概率的平均值；

如果 m > J，则贾斯汀会选其中 J 个最优的（即获胜概率最大的 J 个），然后平均。

“最优”是指最大化自己的获胜概率，因此要按 win(new_state, ...) 从大到小排序，取前 J 个，然后取平均。

唐纳德同理，但他的目标是最小化贾斯汀的获胜概率，所以他会选择使 win(new_state, ...) 最小的 D 个走法（因为他是对手）。

算法步骤

将棋盘状态编码成一个字符串或整数（方便哈希记忆化）；

记忆化搜索：

如果状态已计算过，直接返回；

否则，找出当前玩家所有合法移动；

对每个移动，计算新状态，递归得到贾斯汀获胜概率；

根据失误因子和当前玩家，选择最优的子集，计算平均概率；

返回结果。

复杂度

状态数最多 $3^{13} \approx 1.6 \times 10^6$，但实际很多状态不可达。 每个状态最多 $4 \times 13 = 52$ 种移动，排序取前 $A$ 个，可接受。