绪论

目前关于抽卡概率的计算大多使用概率论的方法进行计算，该方法对于较复杂抽卡机制完全无能为力，例如异环的棋盘以及终末地的双保底机制。对于这些复杂机制往往使用蒙特卡洛方法进行模拟。但是该算法往往具有误差，并且模拟次数较多时不能保证算法效率。注意到抽卡过程为典型的离散随机过程，可以通过迭代精确计算每一步的概率分布。本文提出了一种基于转移矩阵的方法计算抽卡概率，在效率和精度上都有较大优势。

基础知识

离散时间马尔科夫链（简化版本

马尔科夫链的核心是无记忆性。在马尔科夫链中，系统从一个状态转移到下一个状态，只取决于当前的状态，而与它之前是怎么走到这一步的完全无关。

马尔科夫链通常由三个要素组成：

1. 状态（States）： 系统可能处于的情况（比如：晴天、雨天）。

2. 状态空间（State Space）： 所有可能状态的集合。

3. 转移概率（Transition Probability）： 从一个状态跳到另一个状态的概率。通常会画成一个“状态转移图”或者写成一个“转移矩阵”。

假设给状态空间S = {}，若一粒子位于，则下一步跳到的概率为，且无关乎该粒子之前的状态。由为矩阵元构成的矩阵成为转移矩阵。注意转移矩阵的每一行和必须为1。

我们假设在第m步时粒子位于的概率为，把称为粒子在第m步时的分布。那么可以推导出在t步后粒子的分布为。

我们可以注意到大部分二游的抽卡也是一种随机过程，每一步出金的概率往往只取决于已经垫的抽数，故可以用马尔科夫链计算抽卡的概率：

实现原理

卡池状态

我们先考虑一个简单的抽卡模型：该卡池每抽抽到目标结果的概率为p，若抽取2次之后仍未获得目标则在下一抽必定获得。此时的状态空间可以表示为S = {0,1,2}。表示经过n次抽卡后，在上一次出金后又进行了i次抽取。此时可以很容易的写出转移矩阵

假设抽卡从第0抽（表示从上一次保底后没有抽过）开始，则初始分布为。于是我们可以得到投入n抽后的分布为，表示n抽之后距离上一次出金抽了i次的概率。

这个方法可以很高效的计算n抽之后卡池状态的分布，但是这个方法并不能记录已获得的抽数，为此，我们需要做以下调整。

抽数统计——拓展状态空间

在我们的模型中，抽卡的结果会被表示为状态空间S上的一个状态，显然S = {0,1,2}仅能表示卡池的保底状态。为了统计出金的次数，最简单的方式就是将状态空间变为S = N {0,1,2} ，此时表示n抽之后已垫i抽，且出金次数为a，我们将其成为“状态—结果空间”，简称结果空间。此时的转移矩阵将会变成

在这种情况下，状态空间将会具有无穷个状态，在实际计算中无法处理无穷维的转移矩阵。为此，我们有两种方式来解决这个问题

1.由于n次抽卡至多只能抽出n个目标，故可以将状态空间压缩到S = {0..n} {0,1,2}（以后将以{a..b}表示从a到b的整数构成的集合，含两边），将转移矩阵超出n*n的部分砍掉，就可以无伤实现这个算法。但是对于较大的n，每抽都出金的概率几乎可以忽略不记，随着出金次数的增加其概率将会很快被淹没到浮点运算的误差中。但是我们的代价则是大幅提高转移矩阵阶数，使得运算时间成倍增加。

2.对于n次抽卡，我们可以预先设定一个阈值m，认为总的出金数不会超过m。例如进行100次抽卡，完全可以假定出金数不会超过10个，此时状态空间会变为S = {0..m} {0,1,2} 。对于转移矩阵，我们仅保留其前3(m+1)*3(m+1)的部分，并且做如下修订：

其物理含义为：若以及出现m金后再次抽卡出金，我们仍只认为总共出了m次金。该修订可以保证所有状态的概率总和保持为1。

卡池状态空间与状态—结果空间的关系

对于一般的情况，假设卡池状态空间S = {0..n}，P表示其上转移矩阵，且S中第一个状态表示出金，那么我们通过以下方式构建结果空间：

结果空间的状态为，对于S上的转移矩阵P，我们将原始转移矩阵除第一列以外的部分全部变成0，得到的矩阵记作，记作，原转移矩阵可以表示为，而修改后的矩阵可以表示为：

注：状态按顺序排列为

给定结果求抽数分布的情况

通过上文我们可以使用轻松求解给定初始状态抽卡n次后可能出现的结果分布，但是还有一类问题需要讨论达到目标状态所需抽数的分布。对此我们可以引入吸收壁的存在。假设我们需要求获得m金所需抽数的概率分布。定义状态空间S = {0..(m-1)} {0,1,2} + {1..3m}，前一部分来着上一部分的状态空间，后一部分则是吸收壁。

对于的状态，我们沿用之前的转移矩阵

对于，我们引入含时的转移矩阵

含义为：若以出金m-1次，若第t次抽卡时出金，则跳转到状态t上

对于，这部分为吸收壁，其上状态总是保持不动，即。

由于抽卡大保底的限制，概率分布总会在3m步以内完全转移到上。计算，为初始分布（一般为，其他为0）此时在i抽刚好达成目标的几率就是。

对于一般状态空间S = {0..n} 以及其上转移矩阵P，结果空间为

我们同样给出该结果转移矩阵一般表示：

其中Q(t)为n*n(m+1)阶矩阵，其第t列等于的第一列，其余全0。严谨起见，给出的排序

实际应用

不歪池

以鸣朝的武器池为例，其规则为前64抽0.8%出金，以后每抽概率上涨6%且不会歪。定义状态空间为S = 0..79，转移矩阵为：

展开后的矩阵长这个样子：

歪保底池

对于会歪的角色池，我们令 = {0,1} {0..79} 表示其状态空间，其中{0,1}表示是上一个金是否歪，0..79记录已经垫的抽数。转移矩阵为

注意到状态空间是一个80*2的矩阵，这是为了让大家更好的理解每个状态的含义。在算法中计算的时候，我们需要把状态空间拉直，同之前集合直积后的顺序。其对应的转移矩阵表示为160阶的方阵

以下为示例代码（给定抽数求结果）

mod1 = input("输入数字：1.武器池，2.角色池");
num = input("输入投入抽数:");
num2 = input("输入垫池子数:");
if ~exist('num2','var')
    num2 = 0;
end
n = 80;
P1 = [[0.008 * ones(1,64),0.008 + 0.06*(1:15),1].',zeros(80,79)];
P2 = [zeros(79,1),diag([0.992*ones(1,64),0.992 - 0.06*(1:15)]);zeros(1,80)];      %创建转移矩阵
if mod1 == 2
    P2 = [P2,P1/2;zeros(80),P2];
    P1 = [[P1/2;P1],zeros(160,80)];
    n = 160;
end

m = ceil(num/30)+1;
P_tilde = spalloc(n*(m+1),n*(m+1),3*n*m);
for i = 0:m
    P_tilde(i*n + (1:n),i*n + (1:n)) = P2;
end
for i = 1:m
    P_tilde((i-1)*n + (1:n),i*n + (1:n)) = P1;
end
P_tilde(m*n + (1:n),m*n + (1:n)) = P_tilde(m*n + (1:n),m*n + (1:n)) + P1;       %结果空间的转移矩阵

mu = zeros(1,n*(m+1));
mu(num2+1) = 1;
for i = 1:num               %计算分布
    mu = mu * P_tilde;
end
expectation = 0;
for i = 0:m             %对获得抽数进行统计
    p = sum(mu(i*n+(1:n)));
    expectation = expectation + i * p;
    if p > 0
        disp(['抽到',num2str(i),'个目标的概率为',num2str(p)]);
    end
end
disp(['期望获得个数',num2str(expectation)]);
disp(['精度丢失',num2str(1-sum(mu))]);

示例代码（给定结果求抽数）

% mod1 = input("输入数字：1.武器池，2.角色池");
% num = input("输入所需金数:");
% num2 = input("输入垫池子数:");
mod1 = 2;
num = 3;
if ~exist('num2','var')
    num2 = 0;
end
n = 80;
P1 = [[0.008 * ones(1,64),0.008 + 0.06*(1:15),1].',zeros(80,79)];
P2 = [zeros(79,1),diag([0.992*ones(1,64),0.992 - 0.06*(1:15)]);zeros(1,80)];      %创建转移矩阵
if mod1 == 2
    P2 = [P2,P1/2;zeros(80),P2];
    P1 = [[P1/2;P1],zeros(160,80)];
    n = 160;
end

m = num;
P_tilde = spalloc(n*m,n*m,3*n*m);               %结果空间的转移矩阵
for i = 0:(m-1)
    P_tilde(i*n + (1:n),i*n + (1:n)) = P2;
end
for i = 1:(m-1)
    P_tilde((i-1)*n + (1:n),i*n + (1:n)) = P1;
end   

mu = zeros(1,2*n*m);
mu(num2+1) = 1;
Q0 = sparse(P1(:,1));
for t = 1:n*m               %计算分布
    Q = [sparse(n*(m-1),n*m);[sparse(n,t-1),Q0,sparse(n,n*m-t)]];
    mu = mu * [P_tilde,Q;sparse(n*m,n*m),sparse(1:n*m,1:n*m,ones(1,n*m))];
end
p = mu(n*m + (1:n*m));
S = zeros(1,n*m);
S(1) = p(1);
expectation = p(1);
for i = 2:n*m
    S(i) = S(i-1) + p(i);  %累进概率
    expectation = expectation + p(i)*i;
end

figure;
yyaxis left;
plot(1:n*m,S);
ylabel('累进概率');
yyaxis right;
plot(1:n*m,p(1:n*m));
ylabel('单抽概率');
disp(['期望抽数',num2str(expectation)]);
disp(['精度丢失',num2str(1-sum(p))]);

总结

这篇文章的主要目的是介绍这种算法的原理和实现过程。对于米池这种机制简单的池子，用概率论的方法可以简单而高效的实现计算（卷积，启动！）。但是对于概率论方法无法计算的池子，例如异环的神秘棋盘，或者终末的的双保底机制。这种算法仍然可以使用，而且相比蒙特卡洛算法具有全面优势。

我在网上看测评的时候总是看到各种用蒙特卡洛算法模拟抽卡概率的攻略，目前并没有见到使用转移矩阵进行精确计算的讨论，所以我希望这种算法可以被看到。最近刚写完毕业论文，心血来潮就写了这一篇，也算是练习论文写作能力。上面的内容大家应该能看懂吧（嘘

如果看的人多的话应该会有第二篇，讨论更复杂的抽卡机制。

转载和引用请标明出处