【算法】神奇宝贝打BOSS简化模型初步研究：概率dp和期望dp
站长
· 阅读数 7
引言
今天心血来潮，想起了一道之前没有解决的算法题，但我已经近一年没碰过算法了。
基础问题
相信大家都玩过神奇宝贝和类似游戏，本文我们一起考虑神奇宝贝和类似游戏对战的一系列简化模型，并研究其中的概率论问题。如果你之前没有学过概率dp和期望dp，那么本文可以教你一点概率dp和期望dp的套路，并提升一点点写小模拟的能力。
- 我方和BOSS轮流释放技能，技能可以造成伤害、给自身和队友（如果允许多打多）回血、增加属性等。
- 属性包括攻击、防御、特攻、特防、血量、速度等。释放技能先后顺序由速度决定；技能伤害由威力、我方攻击、对手防御、技能系别、对手系别（水、火、草……）等因素决定，并且会乘一个随机系数增加可玩性。
- 技能有使用次数限制，名为PP值，还可以吃药补PP值。
- ……
一道算法题，要考虑上述所有因素就太复杂了，我们先提炼一个精简的模型，来编写一道简单的概率论题目。基础问题如下：BOSS有x滴血，我一局打BOSS掉y滴血，BOSS有p的概率回z滴血，有1-p的概率攻击我。我平均需要几局能打败BOSS？假设：（1）我血量无限。（2）血量不能超过血量上限。（3）我先手，且打赢BOSS那局应该算1局而非0.5局。（3）y <= x。
全期望公式、全概率公式和期望dp、概率dp
全概率公式：P(B) = sum(P(A[i]) * P(B | A[i]))
全期望公式：E(B) = sum(P(A[i]) * E(B | A[i]))
这两个公式思想是一致的，就是将问题划分为若干个互斥事件，并分别求条件概率和条件期望。在算法竞赛中，条件概率和条件期望往往可以用dp来描述，dp的含义一般为“从初始状态到终态”的期望步数or概率。而dp的各个维度既能将问题划分为若干互斥事件，也是对当前局面的一种描述。
有时我们写出的状态转移方程存在循环依赖，此时可以尝试消除循环依赖，比如：设中间变量。但如果做不到，我们往往需要将其建模为方程组才能求解，不过大多数情况下期望dp和概率dp的方程组都是线性方程组。
通过其他算法题，理解了上述套路后，本文你就不需要再看了，因为本文涉及的技巧都太过显然了，只剩下了实现上的难度。如果没有理解，可以以本文为例帮助理解上述套路。
本文52pojie：www.52pojie.cn/thread-1766…
本文CSDN：blog.csdn.net/hans7748829…
基础问题：期望dp做法
设dp[i]为BOSS从i滴血的初始局面到被打败平均需要几局。由全期望公式：
dp[0] = 0
dp[1~y] = 1
dp[y+1] = 1 + p*dp[min(z+1,x)] + (1-p)*dp[1]
dp[y+2] = 1 + p*dp[min(z+2,x)] + (1-p)*dp[2]
# 即
dp[i] = 1 + p*dp[min(i-y+z,x)] + (1-p)*dp[i-y]
这个dp有依赖关系，线性时间复杂度的做法似乎不好想，那就用线性方程组解吧！我选择用numpy来解线性方程组，如果import失败，需要pip install numpy进行安装。具体见代码。
基础问题：brute force，或者说是蒙特卡洛模拟
蒙特卡洛模拟的做法主要是用于对拍。因为我手头没有数据，所以我认为对拍程序和算法输出结果差异较小，即为两者实现均正确。在brute force做法中，为了实现方便，我用了一个小技巧：把退出条件设为cur_blood > y，退出后只需要1局或0局即可击败BOSS。
也可以将我放技能和BOSS放技能的动作拆解开来。这个写法在“扩展2”及以后所有扩展问题中都是必需的。
基础问题：代码
brute force函数名base_bf。
import random
import numpy as np
def base_dp(x: int, y: int, z: int, p: float):
b = np.array([[1 if i else 0] for i in range(x + 1)])
a = [[0] * (x + 1) for _ in range(x + 1)]
for i in range(x + 1):
a[i][i] = 1
for i in range(y + 1, x + 1):
a[i][min(i - y + z, x)] -= p
a[i][i - y] += p - 1
a = np.array(a)
ans = np.linalg.solve(a, b)
return ans[x][0]
def base_bf(x: int, y: int, z: int, p: float, trys=1000000):
def bf(x: int, y: int, z: int, p: float):
ret = 0
cur_blood = x
while cur_blood > y:
ret += 1
rv = random.random()
if rv < p:
cur_blood = min(cur_blood - y + z, x)
else:
cur_blood -= y
# 剩1～y滴血时，1局可打败
return ret + (1 if cur_blood > 0 else 0)
tot = 0
for _ in range(trys):
tot += bf(x, y, z, p)
return tot / trys
print(base_dp(4, 1, 2, 0.25)) # 6.037037037037038
print(base_bf(4, 1, 2, 0.25))
print(base_dp(80, 14, 22, 0.2)) # 8.216744626007252
print(base_bf(80, 14, 22, 0.2))
扩展1：考虑我方血量
BOSS有x1滴血，我有x2滴血，BOSS一局打我掉y1滴血，我一局打BOSS掉y2滴血，BOSS有p的概率回z滴血，有1-p的概率攻击我。赢定义为：BOSS血量小于等于0且我方血量大于0。我赢的概率是多少？假设：（1）血量不能超过血量上限。（2）我先手。（3）y2 <= x1, y1 <= x2。
PS：本来还想问：我在胜利的情况下的期望局数。但想来原理是差不多的，就先不写了。
扩展1：2维的概率dp
可以用(BOSS血量, 我的血量)来描述一个局面。设dp[i][j]为当前局面BOSS有i滴血，我有j滴血，到“赢”的各个状态，即局面(0, j > 0)的概率之和。由全概率公式：
dp[0~x1][0] = 0
dp[0][1~x2] = 1
# 值得注意的是，这里抽出了我方再攻击一次就胜利（必胜）的局面，这是针对“扩展1”的特殊性的做法，可以简化代码实现，但后续不能再使用这个技巧。
dp[1~y2][1~x2] = 1
dp[i][j] = p*dp[min(i-y2+z,x1)][j] + (1-p)*dp[i-y2][j-y1], i = y2+1~x1, j = 1~x2
这里需要越界判断，如果j <= y1，则dp[i-y2][j-y1]应改为取0。
依旧是用矩阵实现，这里的实现难度会比上面大一些。我使用的技巧是，将上面给出的dp公式进行编号，dp[0~x1][0] = 0为第0～x1号公式，依此类推，于是可以维护一个expression_count变量。有expression_count后，我们正常枚举BOSS血量和自己的血量，并初始化矩阵即可。另外，可以引入一个pos函数，来指出某个局面对应的矩阵中的位置，以减小编码难度：
# boss, me
def pos(i, j):
if i < 0 or i > x1 or j < 0 or j > x2:
raise Exception("越界！")
return i * (x2 + 1) + j
扩展1：brute force
仍然是一道小模拟，但难度更大了。借鉴上一题的想法，我把退出条件仅设定为BOSS必败，并在循环中识别我失败的场景。
也可以将我放技能和BOSS放技能的动作拆解开来。这个写法在后续所有的扩展问题中都是必须的。
扩展1：代码
brute force函数名i_may_lose_bf。在测试数据中发现了一些规律。
import random
import numpy as np
# boss血量，我血量，boss攻击，我攻击，boss回血技能回血量，boss发动回血技能概率
def i_may_lose_dp(x1: int, x2: int, y1: int, y2: int, z: int, p: float):
mat_size = (x1 + 1) * (x2 + 1)
# boss, me
def pos(i, j):
if i < 0 or i > x1 or j < 0 or j > x2:
raise Exception("越界！")
return i * (x2 + 1) + j
b = [[0] for _ in range(mat_size)]
for i in range(x1 + 1, x1 + 1 + x2 + y2 * x2):
b[i][0] = 1
b = np.array(b)
a = [[0] * mat_size for _ in range(mat_size)]
expression_count = 0
for i in range(x1 + 1):
a[expression_count][pos(i, 0)] = 1
expression_count += 1
for i in range(1, x2 + 1):
a[expression_count][pos(0, i)] = 1
expression_count += 1
for i in range(1, y2 + 1):
for j in range(1, x2 + 1):
a[expression_count][pos(i, j)] = 1
expression_count += 1
assert expression_count == x1 + 1 + x2 + y2 * x2
for i in range(y2 + 1, x1 + 1):
for j in range(1, x2 + 1):
a[expression_count][pos(i, j)] = 1
a[expression_count][pos(min(i - y2 + z, x1), j)] -= p
if j > y1:
a[expression_count][pos(i - y2, j - y1)] += p - 1
expression_count += 1
assert expression_count == mat_size
a = np.array(a)
ans = np.linalg.solve(a, b)
return ans[mat_size - 1][0]
def i_may_lose_bf(
x1: int,
x2: int,
y1: int,
y2: int,
z: int,
p: float,
trys=1000000
):
def bf(x1: int, x2: int, y1: int, y2: int, z: int, p: float):
ret = 0
boss_blood, my_blood = x1, x2
while boss_blood > y2:
ret += 1
rv = random.random()
if rv < p:
boss_blood = min(boss_blood - y2 + z, x1)
else:
boss_blood -= y2
my_blood -= y1
if my_blood <= 0:
return -1, False
# boss剩1～y2滴血时，1局后我必胜
return ret + (1 if boss_blood > 0 else 0), True
tot, win_count = 0, 0
for _ in range(trys):
step, is_win = bf(x1, x2, y1, y2, z, p)
if is_win:
tot += step
win_count += 1
return tot / win_count if win_count else -114514, win_count / trys
cases = [
# (4, 5, 1, 1, 2, 0.25), # 0.80859375
# (4, 6, 1, 1, 2, 0.3), # 0.8673489999999998
# (17, 18, 3, 4, 5, 0.2), # 0.9998172160000002
# (17, 17, 3, 3, 5, 0.25), # 0.31640625
# (26, 27, 5, 5, 9, 0.3), # 0.5282199999999998
(26, 17, 2, 3, 2, 0.3), # 1
(26, 17, 2, 3, 3, 0.3), # 1
(26, 17, 2, 3, 4, 0.3), # 0.2552983299999999
(26, 17, 2, 3, 5, 0.3), # 0.08235429999999996
(26, 17, 2, 3, 6, 0.3), # 0.08235429999999996
# (24, 24, 5, 5, 5, 0.3), # 1
# (24, 24, 5, 5, 6, 0.3), # 0.6516999999999998
# (24, 24, 5, 5, 7, 0.3), # 0.3429999999999999
# (24, 24, 5, 5, 9, 0.3), # 0.3429999999999999
# (24, 24, 5, 5, 10, 0.3), # 0.3429999999999999
# (24, 24, 5, 5, 25, 0.3), # 0.3429999999999999
# (23, 22, 4, 4, 4, 0.3), # 1
# (23, 22, 4, 4, 5, 0.3), # 0.5282199999999998
# (23, 22, 4, 4, 6, 0.3), # 0.24009999999999992
# (23, 22, 4, 4, 7, 0.3), # 0.24009999999999992
# (23, 22, 4, 4, 20, 0.3), # 0.24009999999999992
# (23, 20, 4, 4, 0, 0.3), # 0.8319300000000001
# (23, 20, 4, 4, 1, 0.3), # 0.8319300000000001
# (23, 20, 4, 4, 2, 0.3), # 0.579825
# (23, 20, 4, 4, 3, 0.3), # 0.3529305
# (23, 20, 4, 4, 4, 0.3), # 0
# (23, 15, 4, 4, 0, 0.25), # 0.3671875
# (23, 15, 4, 4, 1, 0.25), # 0.16943359375
# (23, 15, 4, 4, 2, 0.25), # 0.070556640625
# (23, 15, 4, 4, 3, 0.25), # 0.003505706787109375
# (23, 15, 4, 4, 4, 0.25), # 0
]
for c in cases:
ans1 = i_may_lose_dp(*c)
ans2 = i_may_lose_bf(*c)
print(ans1 - ans2[1], ans1, ans2)
扩展2：双方都能攻击或回血
这个问题有对称性了。做法和扩展1差不多，也比扩展3简单，但时间关系我先搁置了，由大家补全代码～
扩展3：我方能使用加攻击技能且有次数限制，对方能无限次使用回血技能
BOSS和我分别有boss_blood, my_blood滴血，BOSS和我的攻击、防御分别为boss_attack, my_attack, boss_defense, my_defense，BOSS回血量为boss_add_blood，回血技能使用概率为boss_add_blood_probability，我使用加攻击技能的概率为my_add_attack_probability，我使用加攻击技能的次数上限为my_add_attack_limit。我打BOSS的血量为my_power = max((k + 1) * my_attack - boss_defense, 0)，k表示我当前的攻击等级，在这个问题中简化为使用加攻击技能的次数，取值0~my_add_attack_limit。BOSS打我的血量为boss_power = max(boss_attack - my_defense, 0)。赢定义为：BOSS血量小于等于0且我方血量大于0。我赢的概率是多少？假设：（1）双方血量不能超过血量上限。（2）我先手，且打赢BOSS那局应该算1局而非0.5局。（3）boss_power > 0且my_biggest_power = (my_add_attack_limit + 1) * my_attack - boss_defense大于0，这条限制保证战斗能结束。
扩展3：3维dp
做法和“扩展1”类似，我们需要引入一个新的维度，表示初始状态下我已经使用的加攻击技能的次数。更具体地说，dp定义扩展为：dp[i][j][k]表示boss初始血量为i，我初始血量为j，我初始状态已经使用的加攻击次数为k的局面下我赢的概率，这里“赢”依旧是指到达一系列局面的概率之和。答案为dp[boss_blood][my_blood][0]。
边界条件：
dp[0~boss_blood][0][0~my_add_attack_limit] = 0dp[0][1~my_blood][0~my_add_attack_limit] = 1
值得注意的是，扩展1将一种必胜局面抽出，作为边界条件，以简化代码实现。但我们在此只给出了真正的边界条件，不再专门取出所有的1局后必胜条件，因为如果问题继续扩展，那么人工枚举所有的必胜条件几乎是不可能的。
状态转移方程：dp[i][j][k] = (1-my_add_attack_probability*boss_add_blood_probability*dp[min(i-my_power+boss_add_blood,boss_blood)][j][k] + (1-my_add_attack_probability)*(1-boss_add_blood_probability)*dp[i-my_power][j-boss_power][k] + my_add_attack_probability*boss_add_blood_probability*dp[i][min(j+boss_add_blood,boss_blood)][k+1] + my_add_attack_probability*(1-boss_add_blood_probability)*dp[i][j-boss_power][k+1]，其想法就是简单枚举所有的技能使用情况。这个状态转移方程只是一种直观描述，实际上，我打BOSS和BOSS打我的情况都要注意判定血量，血量需要取到非正数时，dp值应改为取常量1或0。dp值取常量1表示b[expression_count]要进行相应增加，dp值取常量0表示对a的操作跳过。另外，还需要判断我使用加攻击技能的次数是否已经达到上限，如果达到了使用加攻击技能次数上限，那么攻击的概率应该是1。在代码实现中，为了简单，我把k < my_add_attack_limit和k == my_add_attack_limit的情况拆为2个循环。放在一个循环中，并定义一个变量my_actual_add_attack_probability = my_add_attack_probability if k < my_add_attack_limit else 0的实现方式应该也是可行的。
TODO：找一个和dp状态数相同数量级的做法，如果找不到，也可以退而求其次，找一个稀疏矩阵的算法。
相关代码如下：
def i_can_add_attack_dp(
boss_blood: int,
my_blood: int,
boss_attack: int,
my_attack: int,
boss_defense: int,
my_defense: int,
boss_add_blood: int,
boss_add_blood_probability: float,
my_add_attack_probability: float,
my_add_attack_limit: int
):
mat_size = (boss_blood + 1) * (my_blood + 1) * (my_add_attack_limit + 1)
# boss_blood, my_blood, my_add_attack_num
def pos(i: int, j: int, k: int):
if i < 0 or i > boss_blood or j < 0 or j > my_blood or k < 0 or k > my_add_attack_limit:
raise Exception("越界！(%s, %s, %s)" % (i, j, k))
return i * (my_blood + 1) * (my_add_attack_limit + 1) + \
j * (my_add_attack_limit + 1) + k
a = [[0] * mat_size for _ in range(mat_size)]
b = [[0] for _ in range(mat_size)]
expression_count = 0
for i in range(boss_blood + 1):
for k in range(my_add_attack_limit + 1):
a[expression_count][pos(i, 0, k)] = 1
expression_count += 1
for j in range(1, my_blood + 1):
for k in range(my_add_attack_limit + 1):
a[expression_count][pos(0, j, k)] = 1
b[expression_count][0] = 1
expression_count += 1
for i in range(1, boss_blood + 1):
for j in range(1, my_blood + 1):
for k in range(my_add_attack_limit):
my_power = max((k + 1) * my_attack - boss_defense, 0)
boss_power = max(boss_attack - my_defense, 0)
a[expression_count][pos(i, j, k)] = 1
# 我攻击，BOSS加血
if my_power >= i:
b[expression_count][0] += (
1 - my_add_attack_probability) * boss_add_blood_probability
else:
a[expression_count][pos(min(i - my_power + boss_add_blood, boss_blood), j, k)] -= (
1 - my_add_attack_probability) * boss_add_blood_probability
# 我攻击，BOSS攻击
if my_power >= i:
b[expression_count][0] += (1 - my_add_attack_probability) * \
(1 - boss_add_blood_probability)
elif boss_power < j:
a[expression_count][pos(i - my_power, j - boss_power, k)] -= (
1 - my_add_attack_probability) * (1 - boss_add_blood_probability)
# 我加攻击，BOSS加血
a[expression_count][pos(min(i + boss_add_blood, boss_blood), j, k + 1)
] -= my_add_attack_probability * boss_add_blood_probability
# 我加攻击，BOSS攻击
if boss_power < j:
a[expression_count][pos(
i, j - boss_power, k + 1)] -= my_add_attack_probability * (1 - boss_add_blood_probability)
expression_count += 1
for i in range(1, boss_blood + 1):
for j in range(1, my_blood + 1):
my_power = max((my_add_attack_limit + 1) *
my_attack - boss_defense, 0)
boss_power = max(boss_attack - my_defense, 0)
a[expression_count][pos(i, j, my_add_attack_limit)] = 1
# 我攻击，BOSS加血
if my_power >= i:
b[expression_count][0] += boss_add_blood_probability
else:
a[expression_count][pos(min(i - my_power + boss_add_blood, boss_blood),
j, my_add_attack_limit)] -= boss_add_blood_probability
# 我攻击，BOSS攻击
if my_power >= i:
b[expression_count][0] += 1 - boss_add_blood_probability
elif boss_power < j:
a[expression_count][pos(
i - my_power, j - boss_power, my_add_attack_limit)] -= 1 - boss_add_blood_probability
expression_count += 1
assert expression_count == mat_size
a = np.array(a)
b = np.array(b)
ans = np.linalg.solve(a, b)
return ans[pos(boss_blood, my_blood, 0)][0]
扩展3：brute force
需要维护的状态多了一个：我当前的攻击等级my_cur_attack_level。值得注意的是，我们必须拆解我方和BOSS释放技能的动作。
我们引入了my_actual_add_attack_probability变量my_actual_add_attack_probability = my_add_attack_probability if my_cur_attack_level < my_add_attack_limit else 0，这样后续代码就只需要人工枚举双方释放技能的所有可能情况，简化了代码实现。
相关代码如下（PS：这段代码应该可以用面向对象来规范一下，但我懒得做了……）：
def i_can_add_attack_bf(
boss_blood: int,
my_blood: int,
boss_attack: int,
my_attack: int,
boss_defense: int,
my_defense: int,
boss_add_blood: int,
boss_add_blood_probability: float,
my_add_attack_probability: float,
my_add_attack_limit: int,
trys=1000000
):
assert boss_attack > my_defense # 暂不支持BOSS打不动我的情况
assert 0 <= boss_add_blood_probability and boss_add_blood_probability <= 1
assert 0 <= my_add_attack_probability and my_add_attack_probability < 1
def bf(
boss_blood: int,
my_blood: int,
boss_attack: int,
my_attack: int,
boss_defense: int,
my_defense: int,
boss_add_blood: int,
boss_add_blood_probability: float,
my_add_attack_probability: float,
my_add_attack_limit: int
):
ret = 0
boss_cur_blood, my_cur_blood, my_cur_attack_level = boss_blood, my_blood, 0
while True:
ret += 1
pivot_boss_skill = random.random()
pivot_my_skill = random.random()
# 引入 my_actual_add_attack_probability
# ，这样后续代码就可以简化为双方释放情况的人工枚举，即若干个if块
my_actual_add_attack_probability = my_add_attack_probability if my_cur_attack_level < my_add_attack_limit else 0
boss_skill_is_attack = pivot_boss_skill >= boss_add_blood_probability
boss_skill_is_add_blood = pivot_boss_skill < boss_add_blood_probability
my_skill_is_attack = pivot_my_skill >= my_actual_add_attack_probability
my_skill_is_add_attack = pivot_my_skill < my_actual_add_attack_probability
if my_skill_is_attack and boss_skill_is_add_blood:
my_power = max((my_cur_attack_level + 1) *
my_attack - boss_defense, 0)
if my_power >= boss_cur_blood:
return ret, True
boss_cur_blood = min(
boss_cur_blood - my_power + boss_add_blood,
boss_blood
)
if my_skill_is_attack and boss_skill_is_attack:
my_power = max((my_cur_attack_level + 1) *
my_attack - boss_defense, 0)
if my_power >= boss_cur_blood:
return ret, True
boss_cur_blood -= my_power
boss_power = max(boss_attack - my_defense, 0)
if boss_power >= my_cur_blood:
return -1, False
my_cur_blood -= boss_power
if my_skill_is_add_attack and boss_skill_is_add_blood:
my_cur_attack_level += 1
boss_cur_blood = min(
boss_cur_blood + boss_add_blood,
boss_blood
)
if my_skill_is_add_attack and boss_skill_is_attack:
my_cur_attack_level += 1
boss_power = max(boss_attack - my_defense, 0)
if boss_power >= my_cur_blood:
return -1, False
my_cur_blood -= boss_power
tot, win_count = 0, 0
for _ in range(trys):
step, is_win = bf(boss_blood,
my_blood,
boss_attack,
my_attack,
boss_defense,
my_defense,
boss_add_blood,
boss_add_blood_probability,
my_add_attack_probability,
my_add_attack_limit)
if is_win:
tot += step
win_count += 1
return tot / win_count if win_count else -114514, win_count / trys
扩展3：自动生成测试用例
人工测试用例，由“扩展1”的测试用例（因为“扩展1”是“扩展3”的子问题）和一些随便写的测试用例组成。为了方便测试代码正确性，我们写一段引入自动生成测试用例的代码。这段代码的主体是一个无限循环，取随机数直到满足我的条件：（1）战斗能够较快结束。（2）矩阵的大小不能太大。
另外，为什么失败条件设得比较宽松delta >= 0.001呢？因为我发现蒙特卡洛模拟，只做1e6次的情况下得到的胜利次数差异可以达到1000，且限于计算资源，模拟次数不能设太大。再说一个小tips，如果发现差值总是正数或总是负数，并且概率差值有时能达到0.01，这说明你的代码有一些细微的错误。
def gen_cases(case_count=3):
cases = []
for _ in range(case_count):
while True:
boss_blood = random.randint(1, 20)
my_blood = random.randint(1, 20)
boss_attack = random.randint(1, 10)
my_attack = random.randint(1, 10)
boss_defense = random.randint(1, 10)
my_defense = random.randint(1, 10)
boss_add_blood = random.randint(1, 15)
boss_add_blood_probability = random.random() / 1.2
my_add_attack_probability = random.random() / 1.2
my_add_attack_limit = random.randint(0, 3)
my_biggest_power = (my_add_attack_limit + 1) * \
my_attack - boss_defense
boss_power = max(boss_attack - my_defense, 0)
mat_size = (boss_blood + 1) * (my_blood + 1) * \
(my_add_attack_limit + 1)
if my_biggest_power > 0 and boss_blood / \
my_biggest_power < 5 and boss_power > 0 and my_blood / boss_power < 5 and mat_size <= 1000:
cases.append((
boss_blood,
my_blood,
boss_attack,
my_attack,
boss_defense,
my_defense,
boss_add_blood,
boss_add_blood_probability,
my_add_attack_probability,
my_add_attack_limit
))
break
return cases
def run_auto_cases(case_count=3):
cases = gen_cases(case_count)
for c in cases:
ans1 = i_can_add_attack_dp(*c)
ans2 = i_can_add_attack_bf(*c)
delta = abs(ans1 - ans2[1])
if delta >= 0.001:
print('[run_auto_cases] 代码在这个用例下可能有问题qwq', c)
else:
print('[run_auto_cases]', c)
print(ans1 - ans2[1], ans1, ans2[1])
run_auto_cases()
扩展3：完整代码
import random
import numpy as np
# boss_blood my_blood boss_attack my_attack boss_defense my_defense boss_add_blood
# boss_add_blood_probability my_add_attack_probability my_add_attack_limit
# boss血量，我血量，boss攻击力，我攻击力，boss防御力，我防御力，boss回血技能回血量，boss发动回血技能概率，我使用加攻击技能概率，我加攻击次数限制
# dp[i][j][k] boss初始血量 我初始血量 我初始状态已经使用的加攻击次数，答案 = dp[boss_blood][my_blood][0]
# dp[0~boss_blood][0][0~my_add_attack_limit] = 0
# dp[0][1~my_blood][0~my_add_attack_limit] = 1
# dp[i][j][k] = (1-my_add_attack_probability)*boss_add_blood_probability*dp[min(i-my_power+boss_add_blood,boss_blood)][j][k] +
# (1-my_add_attack_probability)*(1-boss_add_blood_probability)*dp[i-my_power][j-boss_power][k] +
# my_add_attack_probability*boss_add_blood_probability*dp[i][min(j+boss_add_blood,boss_blood)][k+1] +
# my_add_attack_probability*(1-boss_add_blood_probability)*dp[i][j-boss_power][k+1]
# my_power = max((k + 1) * my_attack - boss_defense, 0)
# boss_power = max(boss_attack - my_defense, 0)
# 我打BOSS和BOSS打我的情况都要注意判定血量，血量需要取到非正数时，dp值应改为取常量1或0，dp值取常量1表示b[expression_count]要进行相应增加，dp值取常量0表示对a的操作跳过
def i_can_add_attack_dp(
boss_blood: int,
my_blood: int,
boss_attack: int,
my_attack: int,
boss_defense: int,
my_defense: int,
boss_add_blood: int,
boss_add_blood_probability: float,
my_add_attack_probability: float,
my_add_attack_limit: int
):
mat_size = (boss_blood + 1) * (my_blood + 1) * (my_add_attack_limit + 1)
# boss_blood, my_blood, my_add_attack_num
def pos(i: int, j: int, k: int):
if i < 0 or i > boss_blood or j < 0 or j > my_blood or k < 0 or k > my_add_attack_limit:
raise Exception("越界！(%s, %s, %s)" % (i, j, k))
return i * (my_blood + 1) * (my_add_attack_limit + 1) + \
j * (my_add_attack_limit + 1) + k
a = [[0] * mat_size for _ in range(mat_size)]
b = [[0] for _ in range(mat_size)]
expression_count = 0
for i in range(boss_blood + 1):
for k in range(my_add_attack_limit + 1):
a[expression_count][pos(i, 0, k)] = 1
expression_count += 1
for j in range(1, my_blood + 1):
for k in range(my_add_attack_limit + 1):
a[expression_count][pos(0, j, k)] = 1
b[expression_count][0] = 1
expression_count += 1
for i in range(1, boss_blood + 1):
for j in range(1, my_blood + 1):
for k in range(my_add_attack_limit):
my_power = max((k + 1) * my_attack - boss_defense, 0)
boss_power = max(boss_attack - my_defense, 0)
a[expression_count][pos(i, j, k)] = 1
# 我攻击，BOSS加血
if my_power >= i:
b[expression_count][0] += (
1 - my_add_attack_probability) * boss_add_blood_probability
else:
a[expression_count][pos(min(i - my_power + boss_add_blood, boss_blood), j, k)] -= (
1 - my_add_attack_probability) * boss_add_blood_probability
# 我攻击，BOSS攻击
if my_power >= i:
b[expression_count][0] += (1 - my_add_attack_probability) * \
(1 - boss_add_blood_probability)
elif boss_power < j:
a[expression_count][pos(i - my_power, j - boss_power, k)] -= (
1 - my_add_attack_probability) * (1 - boss_add_blood_probability)
# 我加攻击，BOSS加血
a[expression_count][pos(min(i + boss_add_blood, boss_blood), j, k + 1)
] -= my_add_attack_probability * boss_add_blood_probability
# 我加攻击，BOSS攻击
if boss_power < j:
a[expression_count][pos(
i, j - boss_power, k + 1)] -= my_add_attack_probability * (1 - boss_add_blood_probability)
expression_count += 1
for i in range(1, boss_blood + 1):
for j in range(1, my_blood + 1):
my_power = max((my_add_attack_limit + 1) *
my_attack - boss_defense, 0)
boss_power = max(boss_attack - my_defense, 0)
a[expression_count][pos(i, j, my_add_attack_limit)] = 1
# 我攻击，BOSS加血
if my_power >= i:
b[expression_count][0] += boss_add_blood_probability
else:
a[expression_count][pos(min(i - my_power + boss_add_blood, boss_blood),
j, my_add_attack_limit)] -= boss_add_blood_probability
# 我攻击，BOSS攻击
if my_power >= i:
b[expression_count][0] += 1 - boss_add_blood_probability
elif boss_power < j:
a[expression_count][pos(
i - my_power, j - boss_power, my_add_attack_limit)] -= 1 - boss_add_blood_probability
expression_count += 1
assert expression_count == mat_size
a = np.array(a)
b = np.array(b)
ans = np.linalg.solve(a, b)
return ans[pos(boss_blood, my_blood, 0)][0]
def i_can_add_attack_bf(
boss_blood: int,
my_blood: int,
boss_attack: int,
my_attack: int,
boss_defense: int,
my_defense: int,
boss_add_blood: int,
boss_add_blood_probability: float,
my_add_attack_probability: float,
my_add_attack_limit: int,
trys=1000000
):
assert boss_attack > my_defense # 暂不支持BOSS打不动我的情况
assert 0 <= boss_add_blood_probability and boss_add_blood_probability <= 1
assert 0 <= my_add_attack_probability and my_add_attack_probability < 1
def bf(
boss_blood: int,
my_blood: int,
boss_attack: int,
my_attack: int,
boss_defense: int,
my_defense: int,
boss_add_blood: int,
boss_add_blood_probability: float,
my_add_attack_probability: float,
my_add_attack_limit: int
):
ret = 0
boss_cur_blood, my_cur_blood, my_cur_attack_level = boss_blood, my_blood, 0
while True:
ret += 1
pivot_boss_skill = random.random()
pivot_my_skill = random.random()
# 引入 my_actual_add_attack_probability
# ，这样后续代码就可以简化为双方释放情况的人工枚举，即若干个if块
my_actual_add_attack_probability = my_add_attack_probability if my_cur_attack_level < my_add_attack_limit else 0
boss_skill_is_attack = pivot_boss_skill >= boss_add_blood_probability
boss_skill_is_add_blood = pivot_boss_skill < boss_add_blood_probability
my_skill_is_attack = pivot_my_skill >= my_actual_add_attack_probability
my_skill_is_add_attack = pivot_my_skill < my_actual_add_attack_probability
if my_skill_is_attack and boss_skill_is_add_blood:
my_power = max((my_cur_attack_level + 1) *
my_attack - boss_defense, 0)
if my_power >= boss_cur_blood:
return ret, True
boss_cur_blood = min(
boss_cur_blood - my_power + boss_add_blood,
boss_blood
)
if my_skill_is_attack and boss_skill_is_attack:
my_power = max((my_cur_attack_level + 1) *
my_attack - boss_defense, 0)
if my_power >= boss_cur_blood:
return ret, True
boss_cur_blood -= my_power
boss_power = max(boss_attack - my_defense, 0)
if boss_power >= my_cur_blood:
return -1, False
my_cur_blood -= boss_power
if my_skill_is_add_attack and boss_skill_is_add_blood:
my_cur_attack_level += 1
boss_cur_blood = min(
boss_cur_blood + boss_add_blood,
boss_blood
)
if my_skill_is_add_attack and boss_skill_is_attack:
my_cur_attack_level += 1
boss_power = max(boss_attack - my_defense, 0)
if boss_power >= my_cur_blood:
return -1, False
my_cur_blood -= boss_power
tot, win_count = 0, 0
for _ in range(trys):
step, is_win = bf(boss_blood,
my_blood,
boss_attack,
my_attack,
boss_defense,
my_defense,
boss_add_blood,
boss_add_blood_probability,
my_add_attack_probability,
my_add_attack_limit)
if is_win:
tot += step
win_count += 1
return tot / win_count if win_count else -114514, win_count / trys
def gen_cases(case_count=3):
cases = []
for _ in range(case_count):
while True:
boss_blood = random.randint(1, 20)
my_blood = random.randint(1, 20)
boss_attack = random.randint(1, 10)
my_attack = random.randint(1, 10)
boss_defense = random.randint(1, 10)
my_defense = random.randint(1, 10)
boss_add_blood = random.randint(1, 15)
boss_add_blood_probability = random.random() / 1.2
my_add_attack_probability = random.random() / 1.2
my_add_attack_limit = random.randint(0, 3)
my_biggest_power = (my_add_attack_limit + 1) * \
my_attack - boss_defense
boss_power = max(boss_attack - my_defense, 0)
mat_size = (boss_blood + 1) * (my_blood + 1) * \
(my_add_attack_limit + 1)
if my_biggest_power > 0 and boss_blood / \
my_biggest_power < 5 and boss_power > 0 and my_blood / boss_power < 5 and mat_size <= 1000:
cases.append((
boss_blood,
my_blood,
boss_attack,
my_attack,
boss_defense,
my_defense,
boss_add_blood,
boss_add_blood_probability,
my_add_attack_probability,
my_add_attack_limit
))
break
return cases
def run_auto_cases(case_count=3):
cases = gen_cases(case_count)
for c in cases:
ans1 = i_can_add_attack_dp(*c)
ans2 = i_can_add_attack_bf(*c)
delta = abs(ans1 - ans2[1])
if delta >= 0.001:
print('[run_auto_cases] 代码在这个用例下可能有问题qwq', c)
else:
print('[run_auto_cases]', c)
print(ans1 - ans2[1], ans1, ans2[1])
# 扩展1的case
no_add_attack_cases = [
# (4, 5, 1, 1, 0, 0, 2, 0.25, 0, 0), # 0.80859375
# (4, 6, 1, 1, 0, 0, 2, 0.3, 0, 0), # 0.8673489999999998
# (17, 18, 3, 4, 0, 0, 5, 0.2, 0, 0), # 0.9998172160000002
# (17, 17, 3, 3, 0, 0, 5, 0.25, 0, 0), # 0.31640625
# (26, 27, 5, 5, 0, 0, 9, 0.3, 0, 0), # 0.5282199999999998
# (26, 17, 2, 3, 0, 0, 2, 0.3, 0, 0), # 1
# (26, 17, 2, 3, 0, 0, 3, 0.3, 0, 0), # 1
# (26, 17, 2, 3, 0, 0, 4, 0.3, 0, 0), # 0.2552983299999999
# (26, 17, 2, 3, 0, 0, 5, 0.3, 0, 0), # 0.08235429999999996
# (26, 17, 2, 3, 0, 0, 6, 0.3, 0, 0), # 0.08235429999999996
# (24, 24, 5, 5, 0, 0, 5, 0.3, 0, 0), # 1
# (24, 24, 5, 5, 0, 0, 6, 0.3, 0, 0), # 0.6516999999999998
# (24, 24, 5, 5, 0, 0, 7, 0.3, 0, 0), # 0.3429999999999999
# (24, 24, 5, 5, 0, 0, 9, 0.3, 0, 0), # 0.3429999999999999
# (24, 24, 5, 5, 0, 0, 10, 0.3, 0, 0), # 0.3429999999999999
# (24, 24, 5, 5, 0, 0, 25, 0.3, 0, 0), # 0.3429999999999999
# (23, 22, 4, 4, 0, 0, 4, 0.3, 0, 0), # 1
# (23, 22, 4, 4, 0, 0, 5, 0.3, 0, 0), # 0.5282199999999998
# (23, 22, 4, 4, 0, 0, 6, 0.3, 0, 0), # 0.24009999999999992
# (23, 22, 4, 4, 0, 0, 7, 0.3, 0, 0), # 0.24009999999999992
# (23, 22, 4, 4, 0, 0, 20, 0.3, 0, 0), # 0.24009999999999992
# (23, 20, 4, 4, 0, 0, 0, 0.3, 0, 0), # 0.8319300000000001
# (23, 20, 4, 4, 0, 0, 1, 0.3, 0, 0), # 0.8319300000000001
# (23, 20, 4, 4, 0, 0, 2, 0.3, 0, 0), # 0.579825
# (23, 20, 4, 4, 0, 0, 3, 0.3, 0, 0), # 0.3529305
# (23, 20, 4, 4, 0, 0, 4, 0.3, 0, 0), # 0
# (23, 15, 4, 4, 0, 0, 0, 0.25, 0, 0), # 0.3671875
# (23, 15, 4, 4, 0, 0, 1, 0.25, 0, 0), # 0.16943359375
# (23, 15, 4, 4, 0, 0, 2, 0.25, 0, 0), # 0.070556640625
# (23, 15, 4, 4, 0, 0, 3, 0.25, 0, 0), # 0.003505706787109375
# (23, 15, 4, 4, 0, 0, 4, 0.25, 0, 0), # 0
]
cases = [
*no_add_attack_cases,
# (4, 5, 1, 1, 0, 0, 2, 0.25, 0.25, 3), # 0.9160377010889875
# (4, 6, 1, 1, 0, 0, 2, 0.3, 0.25, 3), # 0.9741987084147316
# (17, 18, 3, 4, 0, 0, 5, 0.2, 0.25, 3), # 0.9820515464729096
# (17, 17, 3, 3, 0, 0, 5, 0.25, 0.25, 3), # 0.8115670869690697
# (26, 27, 5, 5, 0, 0, 9, 0.3, 0.25, 3), # 0.873849609228737
# (26, 17, 2, 3, 0, 0, 2, 0.3, 0.2, 3), # 0.9905333909547174
# (26, 17, 2, 3, 0, 0, 3, 0.3, 0.2, 3), # 0.9777544970640041
# (26, 17, 2, 3, 0, 0, 4, 0.3, 0.2, 3), # 0.9147414027044304
# (26, 17, 2, 3, 0, 0, 5, 0.3, 0.2, 3), # 0.8731776837795042
# (26, 17, 2, 3, 0, 0, 6, 0.3, 0.2, 3), # 0.8492809049470756
# (24, 24, 5, 5, 0, 0, 5, 0.3, 0.25, 3), # 0.9183074507949731
# (24, 24, 5, 5, 0, 0, 6, 0.3, 0.25, 3), # 0.8585987923823502
# (24, 24, 5, 5, 0, 0, 7, 0.3, 0.25, 3), # 0.7740757521611915
# (24, 24, 5, 5, 0, 0, 9, 0.3, 0.25, 3), # 0.7433988933602607
# (24, 24, 5, 5, 0, 0, 10, 0.3, 0.25, 3), # 0.7409449791377299
# (24, 24, 5, 5, 0, 0, 25, 0.3, 0.25, 3), # 0.6575242627019245
# (23, 22, 4, 4, 0, 0, 4, 0.3, 0.2, 3), # 0.9443943496217228
# (23, 22, 4, 4, 0, 0, 5, 0.3, 0.2, 3), # 0.8574007848491916
# (23, 22, 4, 4, 0, 0, 6, 0.3, 0.2, 3), # 0.7658891690144051
# (23, 22, 4, 4, 0, 0, 7, 0.3, 0.2, 3), # 0.7475453781164894
# (23, 22, 4, 4, 0, 0, 20, 0.3, 0.2, 3), # 0.6679427026235988
# (23, 20, 4, 4, 0, 0, 0, 0.3, 0.25, 3), # 0.8686731676567078
# (23, 20, 4, 4, 0, 0, 1, 0.3, 0.25, 3), # 0.8562376017170137
# (23, 20, 4, 4, 0, 0, 2, 0.3, 0.25, 3), # 0.771857783579355
# (23, 20, 4, 4, 0, 0, 3, 0.3, 0.25, 3), # 0.7163414966132311
# (23, 20, 4, 4, 0, 0, 4, 0.3, 0.25, 3), # 0.6691316566228978
# (23, 15, 4, 4, 0, 0, 0, 0.25, 0.2, 3), # 0.5077913500000001
# (23, 15, 4, 4, 0, 0, 1, 0.25, 0.2, 3), # 0.4285612324000001
# (23, 15, 4, 4, 0, 0, 2, 0.25, 0.2, 3), # 0.35735150696320006
# (23, 15, 4, 4, 0, 0, 3, 0.25, 0.2, 3), # 0.3222425538737369
# (23, 15, 4, 4, 0, 0, 4, 0.25, 0.2, 3), # 0.30972575195312513
# (12, 9, 6, 4, 10, 4, 11, 0.642597, 0.077409, 3), # 0.05168324414398858
# (18, 11, 10, 7, 5, 5, 3, 0.319059, 0.506039, 3), # 0.45683775982637675
# (2, 7, 8, 3, 7, 6, 8, 0.152426, 0.575946, 2), # 0.7198123697734008
# (6, 4, 6, 10, 7, 3, 7, 0.029775, 0.589464, 2), # 0.4342016554147815
# (3, 16, 10, 5, 10, 2, 7, 0.570169, 0.287427, 2), # 0.2696812367978718
# (1, 16, 9, 2, 5, 4, 5, 0.533026, 0.123434, 3), # 0.23279906085426308
# (5, 13, 9, 8, 9, 1, 11, 0.341245, 0.322049, 3), # 0.411064579885941
# (12, 7, 6, 9, 1, 2, 10, 0.587649, 0.30710, 1), # 0.9389672281289208
]
for c in cases:
ans1 = i_can_add_attack_dp(*c)
ans2 = i_can_add_attack_bf(*c)
print(ans1 - ans2[1], ans1, ans2)
delta = abs(ans1 - ans2[1])
if delta >= 0.001:
print('[manual_cases] 代码在这个用例下可能有问题qwq', c)
run_auto_cases()
转载自:https://juejin.cn/post/7215967109184372792