炉石传说中的期望

# <center> 炉石传说中的期望 </center>

同步发表在939499625的qq空间

### 前言：

作为一门功能性极强的学科，信息学科的竞赛知识经常可以用于解决生活中的一些实际问题。今天，我们就来看一看信息学竞赛在炉石传说中的应用。

在这篇文章中，你将看到如何利用信息学以及概率期望知识分析炉石传说的天梯上分难度。在这之前，我们先了解一些前置知识。

### 零、概率与期望：

概率相信大家并不陌生，表示一个事件发生的可能性。那么期望是什么呢？简单来说，期望是所有情况下收益的平均值。比如扔一个骰子，有1~6这6个面，一共有6种情况——6个面都可能朝上。于是我们用所有情况的点数和除以情况数得到期望为3.5 。类似概率的，它表示只要你扔的足够多，你扔出所有情况点数的平均值会无限接近3.5 。今天我们就是要研究假设每一场胜率为$p$ ，炉石传说从各个分段上到传说的期望对战场数，这个数值表示从一个分段打上传说**一般情况下**要打多少场。

### 一、实现原理(可以跳过)：

我们现在编程实现输入距离传说的星数，每一场获胜的概率，输出期望场次。

我们需要注意以下几点：

1、炉石传说在6~25级3场连胜及更多将会获得连胜奖励。

2、炉石传说在21~25级分段不会掉分。

3、新版炉石传说每一级都是5星，共125星，并且在5级、10级、15级处都不能掉分。

概率和期望可以考虑动态规划。

我们设$dp[i][j]$ 表示当前差$i$颗星星到传说，已经有$j$连胜($j>2$时都是等价的)。

然后我们不同的分段分别按该分段规则转移。

除此之外，我们还要定义3个状态，分别表示5、10、15级的0星状态。

因为此时不能掉分，但是星数和将要升级的6、11、16级一致。

但是我们发现这个动态规划是环形的，不能直接做。

考虑高斯消元，$O(n^3)$求解所有$dp$值，矩阵大小$n$约为400。

那么可以在1s内求解答案，建议预处理好转移数组，不容易写昏。

code:
```
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 505;
double mat[maxn][maxn];
int n, dp[maxn][3], tot;
int gap[3];
double win, lose, ans[maxn];

void plusC(int u, double C) {
	mat[u][tot] -= C;
}

void trans(int u, double k, int v) {
	mat[u][v] += k;//plusC(u, k);
}

void Gauss(int n) {
	int pos;
	double mx = 0, K;
	for(register int i = 0; i <= n; ++i) {
		pos = -1, mx = 0;
		for(register int j = i; j <= n; ++j) 
			if(abs(mat[j][i]) > mx) pos = j, mx = abs(mat[j][i]);
		if(!~pos) continue;
		swap(mat[i], mat[pos]);
		for(register int j = 0; j <=n; ++j) {
			if(j == i) continue;
			K = mat[j][i] / mat[i][i];
			for(register int k = 0; k <= n + 1; ++k) {
				mat[j][k] -= mat[i][k] * K;
			}
		}
	}
	for(register int i = 0; i <= n; ++i)
		ans[i] = mat[i][n + 1] / mat[i][i];
	return ;
}

int main() {
	scanf("%d%lf", &n, &win);
	lose = 1 - win;
	for(register int i = 0; i <= 126; ++i)
		for(register int j = 0; j <= 2; ++j) {
			dp[i][j] = tot++;
		}
	gap[0] = tot++, gap[1] = tot++, gap[2] = tot++;
	for(register int i = 0; i < tot; ++i)
		mat[i][i] = -1;
	for(register int i = 1; i <= 24; ++i) {
		for(register int j = 0; j <= 2; ++j) {
			plusC(dp[i][j], 1);
			trans(dp[i][j], win, dp[i - 1][min(j + 1, 2)]);
			trans(dp[i][j], lose, dp[i + 1][0]);
		}
	}
	for(register int j = 0; j <= 2; ++j) {
		plusC(dp[25][j], 1);
		trans(dp[25][j], win, dp[24][min(j + 1, 2)]);
		trans(dp[25][j], lose, gap[0]);
	}
	for(register int i = 26; i <= 100; ++i) {
		if(i == 100 || i % 25 != 0)
			for(register int j = 0; j <= 2; ++j) {
				plusC(dp[i][j], 1);
				if(j == 2) trans(dp[i][j], win, dp[i - 2][2]);
				else trans(dp[i][j], win, dp[i - 1][j + 1]);
				trans(dp[i][j], lose, dp[i + 1][0]);
			}
		else {
			for(register int j = 0; j <= 2; ++j) {
				plusC(dp[i][j], 1);
				if(j == 2) trans(dp[i][j], win, dp[i - 2][2]);
				else trans(dp[i][j], win, dp[i - 1][j + 1]);
				trans(dp[i][j], lose, gap[i / 25 - 1]);
			}
		}
	}
	for(register int i = 101; i <= 126; ++i) {
		for(register int j = 0; j <= 2; ++j) {
			plusC(dp[i][j], 1);
			if(j == 2) trans(dp[i][j], win, dp[i - 2][2]);
			else trans(dp[i][j], win, dp[i - 1][j + 1]);
			trans(dp[i][j], lose, dp[i][0]);
		}
	}
	trans(gap[0], lose, gap[0]);
	trans(gap[0], win, dp[25][1]);
	plusC(gap[0], 1);
	trans(gap[1], lose, gap[1]);
	trans(gap[1], win, dp[50][1]);
	plusC(gap[1], 1);
	trans(gap[2], lose, gap[2]);
	trans(gap[2], win, dp[75][1]);
	plusC(gap[2], 1);
	Gauss(tot - 1);
	printf("%.2lf", ans[dp[n][0]]);
	return 0;
}
```

### 二、研究成果：

根据计算，卡组胜率的影响因素远远大过分段的影响。

假设玩家使用主流卡组，能保持$65\%$的高胜率。

从5级1星、10级1星、15级1星、20级1星以及25级上传说的期望对战场次分别约为：

81.24，125.4，168.29，209.90，237.67 。

但是假如玩家的卡组胜率为$50\%$，那么对战场次分别约为：

700.00，862.87，1023.83，1184.79，1223.61 。

1224场炉石一个月打完，意味着……一天要打40场炉石 ……

综上所述，虽然说胜率低也有机会肝上传说，

但是花一些时间提高水平或卡组质量从而提高自己的胜率，要比硬肝明智很多。

最后，如果你胜率为$40\%$也是有希望上传说的，大概只需要……呃……打577381场就能上传说了……

Rockdu's Blog

导航

最近发表

大佬们的友链