《飞镖王》是休闲小游戏大集合pk32里的小游戏之一,作者本意想模拟的是飞镖运动,但由于这项运动相比台球而言,较难复刻在PC/安卓等虚拟平台,实际效果可玩性在整套合集里也比较一般。下面是这个游戏的界面:
游戏要求在给定机会内将分数清零,并且要求目标数字必须都被射中。初级难度有24次机会,2个目标数字,中级难度18次机会,3个目标数字,高级难度只有12次机会,但要求射中多达4个目标数字。各个级别初始分数均为501。飞镖盘上共有从1~20的20个数字,每个数字都有单倍,双倍和三倍区,射中对应区域则分数可以乘2或者乘3。正中央有单倍红心区和双倍红心区,pk32复刻版单倍红心区为50分,双倍红心区为100分,相比普通飞镖运动翻倍了,这样对玩家更为友好,一般情况下尽量瞄准中心就可以尽快降低剩余分数。如果剩余分数小于射中的分数,那么剩余分数不变,但是如果射中的是目标数字,那也算有效。
这样显然高级难度一定有解,而且至少能剩余2次机会。一个平凡解是这样,前5次都射双倍红心区,分数就只剩下1,接下来4次射4个目标数字(这时分数不变),如果目标数字不包括1,那么再射1次数字1的单倍区,这样保证可以9~10次完成任务。
(资料图片)
UP的个人纪录是中级剩余9次机会,高级剩余2次机会。那么过关后剩余机会的理论上限应该是多少呢?本专栏就讨论这个问题。
这个问题看似可以贪心求解,实则不然。不难发现可以单次射中的分数不是连续的,如57和60之间,60和100之间没有其他的单次有效射中分数。另外目标数字是必须要射中的,但并不一定都射3倍区是最优的,这是因为分数需要恰好归零,不能成为负数。
实际上可以用背包型动态规划的方法求解,如果没有目标数字,就可以用dp[left]表示剩余分数left时清空分数需要射的最少次数。由于每个目标数字是否被射过是独立的,可以用位掩码的形式表示,即mask的第j位为1,表示tgt[j]已被射过,tgt为目标数字构成的数组。如掩码1110,表示4个目标数字里,只有最小的一个没被射过。因此最终状态定义为dp[left][mask]表示剩余分数left,各个目标数字的被射中情况为mask时,清空分数并射完目标数字所需要射的最少次数。以高级为例,边界条件为dp[0][0b1111]=0,dp[0][mask]=∞(mask为非全1的掩码)。我们想要求的实际就是dp[501][0]。
由于状态定义较为复杂,可以模拟游戏过程,用递归形式即记忆化搜索,来实现动态规划。Python语言可以使用functools的cache自动记忆化,其他语言使用二维数组来手动记忆化。由于每次可以射任意数字的单倍双倍三倍区,以及单倍和双倍红心区,共62个区域,因此每个当前状态最多对应62个新状态。但并不是所有操作都有效,使用记忆化搜索时,如果做无效操作,就会让程序陷入死循环,无法求解。有效操作需要满足下列条件之一:
1. 当前操作可以降低分数
2. 当前操作虽然不能降低分数,但可以改变掩码
当然,操作1也有可能改变掩码,因此需要在记忆化搜索前对每个数字对应的掩码先做预处理,模拟操作过程时,无论作何操作,下一个状态的掩码,都应该是当前状态掩码与当前射的数字的掩码做一个按位或操作。
这就是记忆化搜索部分的Python代码。
如何分析复杂度呢?设n为目标数字的数量,m为游戏盘面最大数字,C为需要清零总分,显然共有C*2^n个状态。每个状态的处理需要模拟所有可能的操作,对这个问题是3m+2个,即O(m)的,因此总时间复杂度就是O(C*2^n*m)。对于C=501,n<=4,m=20,总复杂度小于6个数量级,因此计算单次游戏的max是极为快速的。
如果想要计算所有可能的目标数字里的最不利情况呢?可以用LeetCode主站第77题的枚举组合的方法,枚举所有可能的目标数字组合,然后分别计算。事实上由于最多只有4个目标数字,完全可以暴力4个for循环,时间复杂度也不会提升。
上面的代码为枚举组合的方法,对于这个场景其实是不必需的。
作者给出计算结果:
对于初级而言,共有C(20,2)=190种组合,其中148种可以射7镖完成,剩余42种均可以射8镖完成,也就是过关剩余次数的max近80%的概率为17,其余情况为16。
对于中级而言,共有C(20,3)=1140种组合,其中946种可以射8镖完成,176种则需要射9镖,还有18种理论只需要7镖。也就是过关剩余次数的max,约5/6的情况为10,近1/6的情况为9,还有极低概率为11。
对于高级而言,共有从C(20,4)=4845种组合,其中3169种可以射8镖完成,1662种需要射9镖,理论上射7镖能完成的有13种组合,还有一个最特殊的组合:[2,3,4,5],这时候射10镖的平凡解就已经最优了,其实[2,3,4,5]没有更好的解法,多想一想还是不难证明的,但UP在运行这个代码前,一直认为至少要射10镖的目标数字组合未必存在。因此,高级难度过关剩余次数的max,近2/3的情况为4,超1/3的情况为3,极低概率为5,如果碰到了最非酋的组合,max只有2。
关键词: