任务背景

游戏中的武器有如下属性：

  • min_dmg，最小伤害值
  • max_dmg，最大伤害值
  • timecost，每次攻击消耗的时间（越少攻击速度越快）

为了理解不同属性武器的实战效果，我们需要引入TTK（Time To Kill）这个概念，给定怪物的当前生命值 hp，函数ttk()返回使用武器击倒敌人所需时间的期望。

1
def ttk(min_dmg: int,. max_dmg: int, hp: int, timecost: float): ...

可选方法

朴素的公式

高效但有时很不精确的方法，未考虑伤害溢出以及伤害随机性。

1
2
3
def ttk_wrong(min_dmg: int, max_dmg: int, hp: int, timecost: float = 1.0):
    avg_dmg = (min_dmg + max_dmg) / 2.0
    return hp / avg_dmg * timecost

动态规划

理论上是精确的，但复杂度偏高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def ttk_analytical(min_dmg: int, max_dmg: int, hp: int, timecost: float = 1.0):
    E = [0.0] * (hp + 1)
    dmg_range = list(range(min_dmg, max_dmg + 1))
    N = len(dmg_range)

    for h in range(1, hp + 1):
        expected_hits = 1.0
        sum_next = 0.0
        for dmg in dmg_range:
            next_hp = max(0, h - dmg)
            sum_next += E[next_hp]
        expected_hits += sum_next / N
        E[h] = expected_hits
    return E[hp] * timecost

蒙特卡洛

模拟次数较大时趋近于准确值，用来验证上述算法的实际偏差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def ttk_montecarlo(min_dmg: int, max_dmg: int, hp: int, timecost: float = 1.0):
    import random
    rand = random.Random(42)
    total_hits = 0.0
    trials = 200000

    for _ in range(trials):
        current_hp = hp
        hits = 0
        while current_hp > 0:
            dmg = rand.randint(min_dmg, max_dmg)
            current_hp -= dmg
            hits += 1
        total_hits += hits

    return total_hits / trials * timecost

三种方法对比

1
2
3
4
5
6
7
8
min_dmg = 3
max_dmg = 8
timecost = 1.0
hp = 10

print("TTK (Wrong):", ttk_wrong(min_dmg, max_dmg, hp, timecost))
print("TTK (Analytical):", ttk_analytical(min_dmg, max_dmg, hp, timecost))
print("TTK (Monte Carlo):", ttk_montecarlo(min_dmg, max_dmg, hp, timecost))

输出：

  • TTK (Wrong): 1.8181818181818181
  • TTK (Analytical): 2.2824074074074074
  • TTK (Monte Carlo): 2.28284