我是邪少
我什么都不会

利用状态转移矩阵和VBA求游戏中各种事件达成次数的期望

在工作中计算经济数值的时候,经常会遇到需要计算各种事件完成期望的工作(比如计算集齐一套特定的卡牌搭配需要抽多少次……)。本文就介绍一种比较快捷的计算方法。
一般来说,计算期望有以下几种方法:
依据期望的定义式,套用某些概型公式,数学推导计算期望。
这种方法需要解题灵感,有了灵感五分钟就解出来,没思路的话就要卡很久。工作中不是很推荐这种方法,因为工作需要稳定的产出。
用vba写程序模拟事件过程,跑很多次模拟期望次数。
这种稳定是达到了,但就是很麻烦,而且有的事件自己用vba写出来的难度几乎相当于重构了一遍项目对应模块的代码。
写出该事件的状态转移矩阵,再用VBA处理求出具体期望。
以下介绍这种方法。
什么是状态转移矩阵 就是一个矩阵,里面的元素都是非负的,且各行元素之和为1.
举个例子:
某个装备有+0,+1,+2三种状态。
+0强化至+1,成功率50%,失败后等级不变。
+1强化至+2,成功率40%,失败后等级下降至+0。
求由+0强化至+2的次数的期望值。

则该事件的一步状态转移矩阵可以写为:
该事件的一步状态转移矩阵
第一列第一行的0.5代表,强化一次从状态+0变为状态+2的概率为0.5,
同理,第i列第j行的元素即代表强化一次从状态i变为状态j的概率。
一步状态概率矩阵我们可以依照给定的情况很方便的写出来。
什么是K步状态转移矩阵 k步状态转移矩阵即为一步状态转移矩阵的K次方
矩阵的乘法规则自己百度。

举个例子:
该事件的则该事件的二步状态转移矩阵可以经计算得到:
该事件的二步状态转移矩阵
第i列第j行的元素即代表强化二次从状态i变为状态j的概率。
可以看到,强化二次从状态+0变为状态+2的概率为0.2

同理我们可以获得强化K次从状态+0变为状态+2的概率。
由期望定义式可知:
[公式]
Xk=KPk=[K步状态转移矩阵中的Pij]-[K-1步状态转移矩阵中的Pij]然后累加即可。
之所以Pk=[K步状态转移矩阵中的Pij]-[K-1步状态转移矩阵中的Pij],是因为[K步状态转移矩阵中的Pij]包含了[K-1步状态转移矩阵中的Pij],减去后才是仅经过K次强化后强化至+2的次数。(其实就是一个概率分布函数) Pij的值最终会收敛于1
用VBA计算上述过程,代码如下(我写的程序比较糙,属于能跑起来的那种):
Sub Matrix()
Dim i, j, k, a(1 To 10000, 1 To 10, 1 To 10), b(1 To 10000, 1 To 10, 1 To 10), p(1 To 1000), e(1 To 1000)

For i = 1 To 3              '一步转移矩阵写入
 For j = 1 To 3
    a(1, i, j) = Cells(i + 3, j + 2)
 Next j
Next i

p(1) = 0

For k = 2 To 1000            'K步转移矩阵计算
 For i = 1 To 3
  For j = 1 To 3

a(k, i, j) = a(1, i, 1) * a(k - 1, 1, j) + a(1, i, 2) * a(k - 1, 2, j) + a(1, i, 3) * a(k - 1, 3, j)

  Next j
 Next i
 p(k) = a(k, 1, 3)            'Pk=[K步状态转移矩阵中的Pij]
Next k

e(1) = 0

For k = 2 To 1000
 e(k) = e(k - 1) + k * (p(k) - p(k - 1))     '累加求和求得最终期望值
Next k

MsgBox e(1000)

End Sub
输出结果为:
即E(x)=7.5我们用另一种方法验算一下。
设装备从等级k-1强化到等级k的期望是E(k),每次强化成功概率是p1,不变概率是p2,掉级概率是p3。 现在分析从k-1级强化到k级的过程的几种情况 情况一:一次成功,由于成功的概率是p1,强化到k级花费的次数是1,这种情况下需要次数的期望是1 * p1 = p1。 情况二:不变,等级不变又回到从k-1级强化到k级的过程,不变概率是p2,强化到k级花费的次数是1 + E(k)(1代表强化等级不变消耗的次数,E(k)是从k-1级到k级的期望),这种情况下需要次数的期望是(1 + E(k)) * p2。 情况三:掉1级,掉1级变成需要从k-2级强化到k-1级,再从k-1级强化到k级,掉级概率是p3,强化到k级花费的次数是1 + E(k – 1) + E(k)(1代表强化掉级,E(k – 1)是从k-2级到k-1级的期望,E(k)是从k-1级到k级的期望),这种情况下需要次数的期望是(1 + E(k – 1) + E(k)) * p3。 综合上述三种情况, 装备从等级k-1强化到等级k的期望E(k) = p1 + (1 + E(k)) * p2 + (1 + E(k – 1) + E(k)) * p3。 再加上初始条件E(0) = 0,就可以求出E(1)、E(2)….E(n),把E(1)、E(2)….E(n)加起来就是从0级到n级的期望了。
求得E(1)=2,E(2)=5.5则E(x)=7.5致。
因为游戏中的过程状态都是离散的,所以这个方法基本可以处理所有的求期望相关的问题,只需要把一步状态转移矩阵写出来就行。
于是我们就可以处理各种骚问题了,比如打boss会有50%随机掉ABC中的任意一个装备,已知在已持有A的时候B的掉率会下降5%,但持有B的时候C的掉率上升5%,balabalabalabala,问集齐一套ABC期望打多少次boss。 这种问题用概型解或者用写程序跑都是及其痛苦的。但是我们可以快速的列出一步状态转移矩阵,用vba快速解出答案: 这种情况下,会有以下状态:都没、只有A、只有B、只有C、只有AB、只有AC、只有BC、都有,其一步状态转移矩阵是一个7*7的矩阵,你们可以试着写一下,然后用本文的算法算一下,很快就能求出从状态【都没】到状态【都有】的次数期望。

我发现了一种更简单的办法

mathematica中有内置的离散马科夫过程函数,可以进行快捷的计算: 第一步:列出一步状态转移矩阵 第二步:在Mathematica中读取一步状态转移矩阵
xlsxPath= "C:\Users\Administrator\Desktop\一步状态转移矩阵.xlsx";

m =Import[xlsxPath, "Data"][[1]][[2 ;; 4, 2 ;; 4]]
第二行从指定excel读取数据,2;;4表示2~4行,2;;4表示2~4列(这是直接读取xlsx文件的写法,若使用mathematica link for excel加载宏,可以使用Excel[“A1:C1”]这种更好理解的语法)
第三步:定义一个马尔科夫过程: markovProcess = DiscreteMarkovProcess[1,m]; · DiscreteMarkovProcess(Mathematica内置的离散马科夫过程函数),接收2个参数:初始状态和状态转移矩阵 · 赋值这个离散马科夫过程到变量markovProcess Mean[FirstPassageTimeDistribution[markovProcess,10]] Mean用于计算分布的期望值
markovProcess = DiscreteMarkovProcess[1,m];
Mean[FirstPassageTimeDistribution[markovProcess,3]]
输出结果为7.5
赞(3)
未经允许不得转载:微梦 - 邪少个人博客 » 利用状态转移矩阵和VBA求游戏中各种事件达成次数的期望