【真相】技术宅的力量——现阶段五行石合成最优方案研究

2014-01-31 13:47| 查看: 253

【国际惯例】区服：电六N in 1ID：穿山乙职业：神僧(不是正太)
【contact info】……
伸手党直接看红字和黑体（结论在table3和table4，还有红字和黑体部分）如果你对本话题感兴趣，请下载并阅读1楼附件中的paper(共11页)

【body】著名哲学家，佛学家，人类学家、逻辑学家，处女座形象代言人沙迦（シャカ/Syaka）曾经说过：“真相，是深不可测，却又非常美好的东西。遗憾的是，千百年以来，人类想要触摸真相却是非常困难的……”今天，我就为大家揭开五行石合成系统的神秘真相，与大家分享这一周以来我的发现和研究。
目前，比较流行的6级五行石的合成方法是用快速合成（系统自带）合成3级，再将3级合成4级，最后由4级转化为6级。这或许是一种比较好的方法，但是，这究竟是不是最省钱或者最省精力的方法呢？因为这个问题牵扯概率，我们不是狄阁老，没有判断推断果断的天赋。为了解决这个问题，我们必须通过计算才能找到答案。
首先，每合成一个石头都有消耗，我们的目的是用最少的消耗合成出一个6级石头。那么，如何来定义“消耗”呢？一般来讲，消耗(Consumption)分为金钱消耗和体力(stamina)消耗（是精力还是体力我也搞不清楚，就是右边那个槽）。由于金钱和体力同样具有价值，因此我们可以定义一个权重W，总消耗就等于总消耗=W*金钱消耗+(1-W)*体力消耗 (1)当W=0，我们可以找出消耗体力最少的方法；当W=1，我们可以找出消耗金最少的方法；如果综合考虑金币和体力消耗，就要找出最优的W。
其次，也是很重要很容易被忽视的一个问题，就是成功率(hit rate)。计算消耗时，成功率必须考虑在内。比如说，某一次合成显示消耗10金，消耗10点体力，成功率是50%，那么这个操作实际消耗就是20金+10点体力。因为从统计上来讲，只有一半的几率成功，另一半浪费掉了（我们暂且不考虑副产品）。所以，实际消耗是一个统计平均值(statistical average):（不知道什么是统计平均值的小喷油，请至【FAQ1】。不知道什么是概率的小盆友，请至【FAQ2】。）实际消耗=显示消耗/成功率 (2)由于成功率的限制，和合成方法变的不是那么容易直接被看出来，而是需要通过计算才能得出。比如说，一个很简单的问题，如下图：如何合成2级石头最省钱？一般情况下，很多玩家凭直觉会选择第一种。但是实际上，假设1级五行石的单价是70银，那么第一种的金钱消耗是(70*4+12)/0.9436=3金9银45铜，第二种金钱消耗是(70*3+9)/0.7777=2金81银60铜。从统计上讲，明显第二种更省钱。因此，我所做的工作就是将所有可行的方法产生的消耗都计算一遍，从中挑出消耗最少的，当然这个工作要借助编程来完成。

经计算，不考虑主石头（被合成的石头，放在上面槽里的那个）的放法，仅仅子石头从1级到5级就有20349种放法，因此逐个采样记录成功率和加工费是不可能的。所以，我对加工费和成功率做了一下研究，找到了这两个量变化的规律。
【加工费分析】
很多基三player往往不考虑加工费，觉得加工费就几金，可以忽略。实际上，每合成一个6级石头需要N次合成，每一次的加工费叠加起来足可以跟石头的价值相比拟，不可以忽略。不难发现，每添加一个同等级的石头，加工费的增长是线性的。（不知道什么是线性的小盆友，请至【FAQ3】。）一开始我曾经认为，不管主石头放的是几级，只要各个等级的子石头的数量确定了，加工费就是个定值。但不难发现，线性公式里面的常数项，也就是截距(intercept)，是跟随主石头等级变化的。根据我的研究，加工费用公式表示为（单位：金，下同）加工费=5.6225*[5级石头的个数]+1.1596*[4级石头的个数]+0.4107*[3级石头的个数]+0.111*[2级石头的个数]+0.03*[1级石头的个数]+C (3)where C=5.6225 if 主石头是5级； C=1.1596 if 主石头是4级； C=0.4107 if 主石头是3级； C=0.111 if 主石头是2级；
C=0.03 if 主石头是1级。显然，这个常数项C等于与主石头等级相同的子石头的个数的系数（斜率）。这个函数牵扯6个变量，是个6维平面，无法画图给大家看，不过，当子石头只有1级和2级的时候，主石头为2级或3级的加工费分布是一个3维的，如下图所示（左图为2级主石头，右图为3级主石头。因为是线性关系，所以是平面。因为主石头等级影响截距，所以两个平面高度不同）。

在这个图的后方有一个明显的断层，这是由于受到子石头个数的限制（constrains）。最多只能放16个子石头。
【概率分析】成功率与加工费不一样，它不是取决于每一个等级子石头的数量，而是取决于与主石头等级相同的子石头的数量和比主石头等级低一级和两级的子石头的数量。主要注意的是，如果主石头是5级，概率分布情况稍有不同，我们分开讨论。另外，当所有的石头摆好以后，会有两个概率出现：升一级的成功率和升两级的成功率，我们也分开讨论。

先来看让主石头升一级的概率。当主石头不是5级时（5级主石头稍后讨论），大家会发现，当放的同一等级的石头越来越多，成功率就越接近1，但是超过一定的数量，成功率就会下降，这时候主石头升两级的成功率就会上升。我将这个变化趋势称为上升概率(ascendingprobability)和下降概率(descending probability)。经过实验计算，当主石头不为5级时，上升概率为

上升概率=0.3889*[与主石头等级相同的子石头的个数]+0.1089*[比主石头低一级的子石头的个数]+0.0304*[比主石头低两级的子石头的个数] (4)
比主石头低三级的子石头对合成不起任何作用。同样的方法，当主石头不为5级时，下降概率为
下降概率=-0.1089*[与主石头等级相同的子石头的个数]-0.0304*[比主石头低一级的子石头的个数]-0.0085*[比主石头低两级的子石头的个数]+1.2696 (5)
很明显，上升概率的系数和下降概率的系数错位相等。
再来看当主石头是5级石头的情况。这种情况下，没有下降概率，因为石头不能合成7级，不需要补偿升两级的概率。这时候，放2级石头对概率有影响，影响规律是
主石头是5级石头时的概率=0.3889*[与主石头等级相同(Lv.5)的子石头的个数]+0.1089*[比主石头低一级(Lv.4)的子石头的个数]+0.0304*[比主石头低两级(Lv.3)的子石头的个数]+0.0085*[比主石头低三级(Lv.2)的子石头的个数] (6)
再看主石头升两级的概率。这个概率只有上升阶段，而且是线性，与升一级的下降概率分布对称，并且与比主石头等级高一级的子石头数量有关：升两级的概率=0.3889*[比主石头高一级的子石头的个数]+0.1089*[与主石头等级相同的子石头的个数]+0.0304*[比主石头低一级的子石头的个数]+0.0085*[比主石头低两级的子石头的个数]-0.2704 (7)

说的比较复杂，上个图就明白了

这个图是当主石头是2级的时候，升一级的概率。横轴代表2级子石头的个数，4个图分别放了0,1,2,3个1级子石头。可以看出来，每个三角形的形状完全一样，就是每两个之间有一个位移，而且是等量平移，这就说明在1级石头数量这个轴上也是线性。但是有一点不要忘记，不管概率怎么分布，概率的值必须大于等于0且小于等于1，如果上面的公式分布超出了这个范围，要把概率归为0或者1，如下图，在升两级的概率分布中，红色和紫色超出这个范围的部分被设置为1和0。

（未完待续）游客，如果您要查看本帖隐藏内容请回复

【循环计算(ergodic process)】
我的思路是遍历所有的合成方法，找到一种最简单的。反正是计算机跑程序，不用担心运算量大。但是，我还是筛掉了一些不可能的方法，比如说主石头等级很高的时候，放一个1级的子石头没有任何作用，还浪费成本，这种情况我筛掉了。具体的作法是把每个等级的石头的个数保存成向量，一共5个元素，代表1级到5级的个数
每一种可能性=[Lv.1的个数, Lv.2的个数, Lv.3的个数, Lv.4的个数, Lv.5的个数,]=[a,b,c,d,e] (8)
其中a+b+c+d+e不能超过16，而且非零元素的长度不能超过4，e.g.[2,4,3,1,1]这种trial就会被删掉，因为放了一个5级石头，再放2个1级石头完全没有意义。筛选后，子石头一共有8720种放法。

下面再来看主石头路径。循环从合成2级石头开始，逐步升高目标石头的等级。这里顺带一提，很显然，要合成一个N级的石头，主石头升级的路径是一个Fibonacci数列(Fibonacci sequence)（不知道这是什么玩意的小盆友，请至【FAQ4】）。说的屌丝一点，就是合成一个2级石头，只有1条路径（Lv.1-Lv.2）；合成一个3级石头，有2条路径（Lv.1-Lv.2-Lv.3或者Lv.1-Lv.3）；合成一个4级石头，有3条路径（Lv.1-Lv.2-Lv.4或者Lv.1-Lv.3- Lv.4或者Lv.1-Lv.2-Lv.3-Lv.4）……以此类推，合成某个等级的石头的路径数就等于合成比他小一级和小两级的路径数量之和：
0,1,2,3,5,8，… (9)
回忆一下Fibonacci数列的递推公式和通项公式：
F(n) = F(n − 1) + F(n − 2)

（不想手敲公式了，贴图）
我们要合成6级时候，把n=6带进去，得到8个路径：（其实就6个数，一个个数也行，但是显得比较低端。我这样做也是为了提供一个模型，以后可以合成更高级的石头的时候就可以直接带公式。）

这8条路径用层级关系表示为

不管哪条路径，都是由图中标注的9步操作完成的。从底层开始，分别计算每一级石头的消耗。我们区现在的1级五行石65银一个，结果如下：
最省钱的方法：

最省体力的方法：（最省体力就说明不在乎花多少钱。理论上60体力就可以合出一块6级石头，但是要花1W多金，实际中只要不是脑残不会有人这样做的）

其实，很多玩家在犹豫，到底是直接卖体力还是合了石头卖石头呢？卖石头比卖体力能多赚多少？为了解决这个问题，我们需要找到一个权重W,使得收益（profit）最大。其中，收益可以表示为
收益=（6级石头的市场价-合成消耗的金）*（3520/单个6级的体力消耗）（10）
因此，这个问题就变成
Max{（市场价-成本）/单个6级的体力消耗}s.t. constrains [和谐] mentioned before

目前笔者所在区服6级石头的市场价差不多是800J，以一级五行石的单价为65银为例，最优的权重W等于0.4840-0.4900.(W的取值是一个闭区间，在这个区间内的W带来的收益是相等的。这个很好理解，因为数值虽然是连续的，但是合成路径是离散的。)在这种情况下，最优合成路径是

第一栏代表想要合成的石头的等级，第二栏代表主石头的等级，3-7栏代表各个级别子石头的数量，cost那一栏是金消耗，stamina是体力消耗。

做个简单的说明，实际上收益是一个6级石头市场价和1级石头单价的函数，当这两个自变量变化的时候，权重W是不一样的。下图是在6级石头卖800J的情况下，最优权重区间的中值（median）和1级石头的单价的变化规律：

如果考虑6级五行石的售价，那收益就是个3维的

换句话说，五行石到底怎么合成最划算，取决于6级石头的市场价和1级石头的单价。如果用帮贡去买1级石头，75银一个，最优合成路径是不同的，我算了一下，75银的一级石头合成6级，如果6级能卖800J一个的话，最优合成方法是

另外上一个与这个结论无关的图，某个6级的最终消耗取决于1级五行石的市场价和一管体力的市场价，他们之间的关系如下图

这个图能看懂的就看看，看不懂的就算了，不多做解释了，不影响上面的结论。

我把我上面说的这一堆写成了一篇10页的paper，如果你想详细了解，或者有不明白的地方，欢迎下载1楼附件中的论文。
【FutureStudy】1. 非常重要的一点，五行石合成的成功率跟石头的属性有关！！！主石头的属性必须和所有子石头都相同，才是较划算的，才遵循我上面所说的规律。我不懂五行相生相克，懂的人科普一下吧。比如说，放2个2级火石头当子石头，再放一个1级火石头，成功率是77.77%，但是放一个1级水石头，就变成了74.07%。至于不同属性的石头如何影响最优方案，虽然没有必要研究，但是如果谁有兴趣，可以当个没有funding的project做做。2. 在上面的计算中，我没有考虑合成时候产生的副产品。比如说，我想把4级合成6级，但是不小心出来个5级，理论上严格的讲，要把这个5级的价值考虑进去，但是那样比较复杂，而且目前比较流行的方案也没考虑这个问题，所以我就没考虑。不过如果哪位学术帝有时间考虑一下这个问题，会把这个方案做的更加完善。
3. 上面计算的加工费和概率分布维数太高，我本来是希望能找到各个维度的系数之间的规律，但是由于只有5个系数，太少了，不好做拟合（不知道什么是拟合的小盆友，请至【FAQ5】）。就比如说加工费那5个系数，5.6225,1.5196，0.4107,0.1110,0.0300，这几个数到底是一种什么样的增长规律？单凭这5个数，他们之间可以是指数关系，高斯关系，4阶多项式关系，甚至是rational关系（不知道这种关系中文叫什么，贴个公式吧）