likes
comments
collection
share

【算法】神奇宝贝打BOSS简化模型初步研究:概率dp和期望dp

作者站长头像
站长
· 阅读数 5

引言

今天心血来潮,想起了一道之前没有解决的算法题,但我已经近一年没碰过算法了

基础问题

相信大家都玩过神奇宝贝和类似游戏,本文我们一起考虑神奇宝贝和类似游戏对战的一系列简化模型,并研究其中的概率论问题。如果你之前没有学过概率dp和期望dp,那么本文可以教你一点概率dp和期望dp的套路,并提升一点点写小模拟的能力。

  1. 我方和BOSS轮流释放技能,技能可以造成伤害、给自身和队友(如果允许多打多)回血、增加属性等。
  2. 属性包括攻击、防御、特攻、特防、血量、速度等。释放技能先后顺序由速度决定;技能伤害由威力、我方攻击、对手防御、技能系别、对手系别(水、火、草……)等因素决定,并且会乘一个随机系数增加可玩性。
  3. 技能有使用次数限制,名为PP值,还可以吃药补PP值。
  4. ……

一道算法题,要考虑上述所有因素就太复杂了,我们先提炼一个精简的模型,来编写一道简单的概率论题目。基础问题如下: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 > 0my_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] = 0
  • dp[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_limitk == 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
评论
请登录