探究明日方舟部分游戏机制的模拟实现

这是一篇发表于 2022年4月1日的博文，作者将其精简了无聊的 CRUD 部分，保留了对核心机制的探索部分，包括：明日方舟的公招词条组合优化，明日方舟的抽卡模拟实现，明日方舟的抽卡概率探索。

明日方舟的公招词条组合优化

模拟公招时，以提供五个词条为例，需要将五个词条的所有一词条、二词条、三词条组合都列出，并逐一在公招规则中进行查询，现在需要计算需要查询的词条组合

最简单的办法自然是暴力，获取$n$词条组合这个问题可等价于对一个集合

A = [tag_1, tag_2, tag_3, tag_4, tag_5]

进行$n-1$次笛卡尔积，将所有结果排序后去重，得到的结果即为所求结果

但是，这个方法效率奇差，不算排序和去重，光是笛卡尔积就需要计算5 + 5 \times 5 + 5 \times 5 \times 5 =155 次，而此问题的目标输出规模为C_5^1 + C_5^2 + C_5^3 = 25 ，显然过于离谱

然后自然而然想到了对集合$A$进行全排列，然后进行排序去重，不算排序和去重的话，递归进行全排列的运算次数为A_5^1 + A_5^2 + A_5^3 = 85 次，此时已经优化了很多了，但还是太离谱了

最后就想到了少有提起的全组合，全组合天然的优势是不用去重和排序，并且全组合的运算次数为2^5 = 32 次，已经和目标的输出规模很接近了，故采用全组合来实现此需求

对于全组合，我们只需要开辟一个 bool 数组，长度与集合A 的元素个数相同即可，按位对应，若元素数量不多，直接使用一个 int 类型的整数类型即可。其 true/false 即为集合A 对应元素是否出现在结果中，遍历完数组的每一个状态，全组合也就求完了。

这个优化的实现如下，以 golang 作为实现语言：

func combination(tags []string) (result [][]string) {
	length := len(tags)
	upperBound := 1<<length
	result = make([][]string, upperBound-1)

	for i := 1; i < upperBound; i++ {
		temp := ""
		for j := 0; j < length; j++ {
			if i>>j == 0 {
				break
			} else {
				if (i>>j)^1 == 1 {
					temp += tags[j] + ","
				}
			}
		}
		result[i-1] = strings.Split(strings.TrimRight(temp, ","), ",")
	}

	return result
}

明日方舟的抽卡模拟实现

由于完全随机较容易出现极端值，~~我们可以调一个正态的图形出来~~

尝试过调模型了，事实证明这个活适合专业人士去干，想用喜闻乐见的十倍开根号进行修正，结果调出了极其奇怪的图像🤦，有兴趣的同学可以自己去试试

简单测试了一下 rand 库的随机数函数的生成效率，生成1024 组，每组2^{20} 个随机数，所用时间为十二秒 (测试平台为 Apple M1)，对于抽卡而言性能我猜够了

gacha 的实现如下，精确度为小数点后六位，以 golang 作为实现语言：

func gacha(alreadyGacha, count, fourStar, fiveStar, sixStar, sixStarCorrection int) (result []int) {
	result = make([]int, count)
	correctionSixStar := sixStar
	
	for i, _ := range result {
		if alreadyGacha >= 50 {
			correctionSixStar += sixStarCorrection
		}

		prop := rand.Int() % 1000000
		alreadyGacha += 1
		if prop < fourStar {
			result[i] = 3
			continue
		}
		switch {
		case prop > correctionSixStar:
			result[i] = 6
			alreadyGacha = 0
			correctionSixStar = sixStar
		case prop > fiveStar:
			result[i] = 5
		default:
			result[i] = 4
		}
	}

	return result
}

明日方舟的抽卡概率探索

我们知道随机事件A 发生的概率为P，即抽卡出货的概率为2\%，那么A 的对立事件\overline{A} 即抽卡不出货的概率为1-2 %=98 %，则连续两次抽卡不出货的概率为P(\overline{A}) \times P(\overline{A}) = 98\% \times 98\%，以此类推，五十抽以内，前n 次抽卡都不出货的概率P(n) = (0.98)^{n}

但是当抽卡次数达到50 抽以上时，将会触发概率补正，即增加2\% 的额外概率，五十抽以后，再抽一发还不出货的概率为P(n) \times P(n)'，其中P(n) 为该抽前不出货的概率，P'(n) = 2\% + (n-50) \times 2\% ，n 为已经抽卡次数

那么连续抽n 次都不出货的概率P(n) 表达式如下：

P(n) = \begin{cases} 0.98^{n}, n \leq 50 \\\\ P(n-1) \times (0.98-0.02\times(50-n)), 50 < n \end{cases}

那么，连续抽n 次至少出一张六星的概率P'(n) = 1-P(n)，我们假定当至少出一张六星的概率大于99.9\% 时，下一抽必出货

顶着 float64 ~~溢出的边缘计算~~，得到结果：当抽卡74 次仍没出货时，下一抽的出货的概率至少为99.9\% ，好想去问候鹰角为什么我四五次到了70~77抽才出货

至于那个网上流传已久的期望34.5 抽是怎么来的，可以参考这里 [知乎 - 从明日方舟抽卡机制开始的些微探索]