「狗蛋和二五仔」题解

问题分析

这是一个复杂的两人零和随机博弈问题。小E和老师轮流行动，目标是将对方体力降至0或以下。游戏中有多种操作，且包含随机元素（打牌时的随机伤害）。

关键规则总结

状态要素：

• 双方体力值：$E$（小E），$S$（老师）
• 双方场上牌数及体力值：最多各4张，每张牌体力1或2
• 双方手牌数：0-3张
• 当前回合玩家
• 本回合已进行技能+打牌次数（不超过$O$）
• 每张牌是否已攻击过（本回合）

回合流程：

1. 回合开始时：抽一张牌（如果手牌<3）
2. 进行若干操作（至少一次）
3. 结束回合

操作类型：

1. 技能：自己体力-2，抽一张牌（手牌<3时）
2. 攻击：
   • 用自己的未攻击牌与对方场上牌同归于尽
   • 或用自己的未攻击牌打对方玩家-3体力
3. 打牌：
   • 先进行3次随机伤害：随机选择场上任一牌或任一玩家，概率均等
   • 然后从手牌放一张2体力牌到自己场上（场上<4时），该牌本回合已攻击
4. 结束回合：必须至少进行一次其他操作后才能结束

限制：每回合技能+打牌操作总数 ≤ $O$（$3 \leq O \leq 5$）

问题性质

1. 状态空间分析

由于$E,S \leq 20$，场上最多4张牌，每张牌体力1或2，手牌0-3，操作计数0-$O$，以及当前玩家和攻击标记。

状态数量估计：

• 体力值：21×21=441种
• 老师场上牌：考虑最多4张牌，每张体力1或2，且顺序可能重要？实际上牌是无区分的，只需记录每种体力的数量。设老师有$c_1$张1体力牌，$c_2$张2体力牌，$c_1+c_2 \leq 4$，有$(4+1)×(4+1)=25$种可能（包括0-4张1体力，剩余给2体力）
• 小E场上牌：同理25种
• 手牌：4×4=16种（老师0-3，小E0-3）
• 当前玩家：2种
• 操作计数：$O+1$种（0到$O$）
• 攻击标记：每张牌是否已攻击。场上最多8张牌，但实际需要标记的只有当前玩家场上的牌（因为只有自己的牌能攻击）。最多4张，$2^4=16$种

总状态数上界：$441 × 25 × 25 × 16 × 2 × (O+1) × 16 ≈ 441×25×25×16×2×6×16 ≈ 8.5×10^7$

实际上很多状态不可达，且可以进一步压缩。

2. 博弈类型

这是一个完全信息随机博弈：

• 双方知道所有状态信息
• 包含随机元素（打牌时的随机伤害）
• 双方都采取最优策略最大化自己获胜概率

算法框架

1. 状态表示

我们需要高效表示游戏状态。由于$O \leq 5$较小，可以使用记忆化搜索（DFS）。

定义状态为：

• 当前玩家：turn（0=小E，1=老师）
• 小E体力：e_hp
• 老师体力：s_hp
• 老师场上牌：可用位表示，但更简单用两个计数c1, c2（1体力和2体力数量）
• 小E场上牌：p1, p2
• 老师手牌：s_hand
• 小E手牌：e_hand
• 本回合已用操作次数：used（技能+打牌）
• 攻击标记：当前玩家场上牌的已攻击状态（位掩码）

2. 状态转移

对于当前状态，当前玩家可以选择：

1. 技能：如果used < O且自己体力>2
2. 攻击：如果有未攻击的牌
   • 与对方场上牌同归于尽
   • 直接攻击对方玩家
3. 打牌：如果used < O，场上牌<4，手牌>0
4. 结束回合：如果本回合已进行至少一次操作

特殊规则：

• 抽牌：回合开始自动抽牌；技能操作也抽牌
• 死亡检查：任何操作后立即检查，如果有玩家体力≤0，游戏结束
• 牌死亡：牌体力降为0时立即移除

3. 随机处理

打牌操作包含3次随机伤害。每次随机选择：

• 场上$k$张牌（双方合计） + 2个玩家 = $k+2$个目标
• 每个目标被选中的概率 $\frac{1}{k+2}$

由于随机性，我们需要计算期望胜率。

4. 动态规划/记忆化搜索

设dp(state)表示从当前状态state开始，在当前玩家采取最优策略下，小E的获胜概率。

对于确定性的操作（技能、攻击、结束回合）：

• 新状态s'
• dp(state) = 1 - dp(s')（如果是对方回合）或直接计算

对于随机操作（打牌）：

• 需要枚举所有可能的随机结果
• 计算每个结果的概率和对应的胜率
• 加权平均得到期望胜率

最优策略：当前玩家选择使自己胜率最大化的操作（老师会使小E胜率最小化）。

因此递推公式：

• 如果当前是小E的回合：dp(state) = max_{操作} (期望胜率)
• 如果当前是老师的回合：dp(state) = min_{操作} (期望胜率)

5. 状态简化

由于状态空间较大，需要压缩：

1. 牌的对称性：同体力值的牌是无区别的，只需记录数量
2. 攻击标记：只需标记当前玩家场上的牌（因为只有自己的牌能攻击）
3. 操作计数重置：结束回合后，操作计数重置为0，攻击标记清除
4. 回合开始抽牌：可以预处理在状态进入时处理

6. 记忆化实现

使用哈希表存储状态->胜率的映射。

关键优化：

1. 状态哈希：将状态编码为64位整数
2. 剪枝：如果找到必胜或必败状态，可以提前返回
3. 对称状态：交换双方角色，胜率互补

7. 随机伤害的枚举

打牌操作需要进行3次随机伤害，每次从$k+2$个目标中选择。

可能的随机结果很多：$(k+2)^3$种。$k \leq 8$，最多$10^3 = 1000$种，可接受。

但需要高效枚举，因为每个状态都需要计算。

详细算法步骤

步骤1：状态编码

将状态编码为紧凑形式：

state = (turn, e_hp, s_hp, c1, c2, p1, p2, s_hand, e_hand, used, attack_mask)

其中：

• turn: 1位
• e_hp, s_hp: 各5位（0-20，实际0-30但输入≤20）
• c1, c2, p1, p2: 各3位（0-4）
• s_hand, e_hand: 各2位（0-3）
• used: 3位（0-5）
• attack_mask: 4位（场上最多4张牌）

总位数：1+5+5+3+3+3+3+2+2+3+4 = 34位，适合32位或64位整数。

步骤2：记忆化搜索框架

def dfs(state):
    if state in memo: return memo[state]
    
    # 检查游戏是否结束
    if e_hp <= 0: return 0.0  # 小E输
    if s_hp <= 0: return 1.0  # 小E赢
    
    # 当前玩家
    if turn == 0:  # 小E回合
        best = 0.0
        for 每个合法操作:
            计算操作后的期望胜率prob
            best = max(best, prob)
        memo[state] = best
        return best
    else:  # 老师回合
        best = 1.0
        for 每个合法操作:
            计算操作后的期望胜率prob
            best = min(best, prob)
        memo[state] = best
        return best

步骤3：操作实现

3.1 技能操作

条件：used < O，自己体力>2 效果：

• 自己体力-2
• 如果手牌<3，手牌+1
• used+1
• 攻击标记不变

3.2 攻击操作

条件：有未攻击的牌（根据attack_mask）

两种攻击方式：

1. 同归于尽：选择自己一张未攻击牌，选择对方一张牌
   • 双方牌都移除
   • 自己的牌标记为已攻击
2. 攻击玩家：选择自己一张未攻击牌
   • 对方玩家体力-3
   • 自己的牌标记为已攻击

3.3 打牌操作

条件：used < O，场上牌<4，手牌>0

过程：

1. 进行3次随机伤害
2. 手牌-1，场上+1张2体力牌（标记为已攻击）
3. used+1

随机伤害的递归计算： 对于每次伤害，有$k+2$种可能结果（$k$=场上牌数）。 需要递归计算所有可能序列的概率和胜率。

由于3次伤害，可以编写一个辅助函数：

def simulate_damage(state, remaining_damage):
    if remaining_damage == 0:
        return dfs(打牌完成后的状态)
    
    total_prob = 0.0
    k = 场上牌总数
    targets = k + 2  # 包括两个玩家
    
    for 每个目标:
        if 目标是牌:
            新状态 = state, 该牌体力-1
            if 牌体力变0: 移除该牌
        elif 目标是玩家:
            新状态 = state, 玩家体力-1
        
        prob = 1.0 / targets
        total_prob += prob * simulate_damage(新状态, remaining_damage-1)
    
    return total_prob

3.4 结束回合操作

条件：本回合已进行至少一次操作 效果：

• 切换玩家
• used=0
• 清除攻击标记
• 新回合开始：新玩家抽一张牌（如果手牌<3）

步骤4：优化技巧

1. α-β剪枝：由于是零和博弈，可以使用α-β剪枝优化搜索
2. 状态对称性：如果交换双方角色，胜率互补。可以存储规范化状态（如总是从小E视角）
3. 预计算随机结果：对于给定的场上配置，可以预计算打牌操作的平均效果
4. 迭代加深：由于状态空间大，可以限制搜索深度

复杂度分析

最坏情况复杂度

• 状态数：约$10^7$量级
• 每个状态的操作数：有限（技能1种，攻击最多几种，打牌1种，结束1种）
• 打牌操作需要计算随机结果：最多$(8+2)^3=1000$种分支

总计算量可能很大，但：

1. 很多状态不可达
2. 可以使用剪枝和记忆化
3. $O$较小（3-5），限制操作数
4. 体力值较小（≤20）

实现注意事项

1. 浮点数精度

需要高精度浮点数（double）存储概率，误差要求$10^{-6}$。

2. 死亡处理

任何操作后立即检查死亡：

• 玩家体力≤0：游戏结束
• 牌体力≤0：立即移除

3. 抽牌逻辑

• 回合开始自动抽牌
• 技能操作也抽牌
• 手牌上限为3

4. 边界条件

• 不能进行0次操作就结束回合
• 技能和打牌总数限制

总结

本题是一个复杂的随机博弈问题，需要通过记忆化搜索求解。关键点包括：

1. 状态表示：紧凑编码所有游戏信息
2. 随机处理：计算打牌操作的期望胜率
3. 最优策略：小E最大化胜率，老师最小化小E胜率
4. 记忆化优化：使用哈希表避免重复计算

虽然状态空间较大，但由于游戏规则限制和$O$值较小，实际可达状态有限，记忆化搜索是可行的。

算法框架：

1. 解析输入状态
2. 从该状态开始记忆化搜索
3. 对于每个状态，枚举所有合法操作
4. 计算每个操作的期望胜率
5. 根据当前玩家选择最大或最小值
6. 输出小E的获胜概率