抽包的數學

(註:本文的研究在一年多前就完成了。原本想推廣到3種卡的情況,不過由於太繁瑣而遲遲沒有開動。於是在這裏也發一下。這個研究是Enp戰隊的清水選手和本人一起做的。)
前段時間我們群裏有人問起某個包抽到了某張卡,要不要重置這樣的問題。群裏的清水研究了一下這個問題,用程序給出了在各種情況下一個包有兩種需要的獨有卡(大包UR或小包UR及SR),抽到某種卡,是否應該重置的解答。後來我對連續的情況也進行了推導,給出一個連續情形的公式。
問題的定義
一個總數爲n的卡包,玩家希望從中抽出兩種獨有卡,A卡和B卡分別需要x和y張。抽了k包抽到了A卡,問此時是否應該重置(按最後成型的期望鑽石消耗來算)?
(雖然每包是3張,但SR以上每次最多一張,也就是不會出現一包同時有兩張想要的卡的情況。)
Python程序
# dl.py
def dld(n, x, y):
    if x * y == 0:
        return [(x + y) * (n + 1) / 2., 0., 0.]
    else:
        s = 0
        fx = dld(n, x - 1, y)[0]
        fy = dld(n, x, y - 1)[0]
        fxy = dld(n, x - 1, y - 1)[0]
        stopx = 2 * fxy - 2 * fx + n + 1
        stopy = 2 * fxy - 2 * fy + n + 1
        for m in range(1, n):
            ex = fx if m <= stopx else fxy + (n + 1 - m) / 2.
            ey = fy if m <= stopy else fxy + (n + 1 - m) / 2.
            s += (ex + ey + 2 * m) * (n - m) / (n * n - n)
        return [s, stopx, stopy]
def dlc(x, y):
    if x * y == 0:
        return [(x + y) / 2., 0., 0.]
    else:
        fx = dlc(x - 1, y)[0]
        fy = dlc(x, y - 1)[0]
        fxy = dlc(x - 1, y - 1)[0]
        return [-2 * (fx ** 3 + fy ** 3) / 3. + 2 * (fx ** 2 + fy ** 2) * fxy - 2 * (fx + fy) * fxy ** 2 + (fx + fy) / 2. + 4 * fxy ** 3 / 3. + 1 / 3., 2 * fxy - 2 * fx + 1., 2 * fxy - 2 * fy + 1.] # last two are stopx and stopy

程序裏首先用到了“卡包裏有一種需要卡需要抽幾包”的期望,在剩餘n包時,平均抽(n+1)/2包能抽出來。第一個dld程序是離散的情況,看當前重置與否哪個期望cost最低,再遞歸累計求和。第二個dlc程序是連續的情況,最後的式子是我積分化簡後的結果。原本以爲化簡後觀察前幾個結果能猜出通項公式,再用歸納法證明。但是繁瑣程度超出我的想像。

示例
(刪除太長的小數部分)
>>> import dl
>>> dl.dld(100, 1, 1)
[67.33, 0.0, 0.0]
>>> dl.dld(100, 1, 2)
[109.123, 0.0, 67.33]
>>> dl.dld(100, 2, 2)
[133.31, 17.42, 17.42]
輸入是n, x, y。輸出的第一個數字是抽滿的期望值、在多少包之前抽到A卡應該重置、在多少包之前抽到B卡應該重置。
上面的運算是對總共有100包卡的情況。結果解讀:
如果A卡和B卡都各需要1張,那任何時候抽到任一張都不需要重置(程序輸出的意思是“0包前抽到可以重置”)。抽滿的期望是67.33包,也就是(1+100)*2/3。
如果A卡需要1張,B卡需要2張,任何時候抽到A卡仍然不需要重置。在第67包或之前抽到B卡的話應該重置,67包之後抽到B卡不需要重置。抽滿的期望是109.12包。
如果A卡和B卡都各需要2張,在第17包或之前抽到任一張就重置,然後退化成分別需要1、2張的情況。抽滿的期望是133.31包,比(1, 1)的2倍略小。這是因爲(2, 2)有更多的提前重置機會。
連續情況示例:
>>> import dl
>>> dl.dlc(1, 1)
[0.6667, 0.0, 0.0]
>>> dl.dlc(1, 2)
[1.0802, 0.0, 0.6667]
>>> dl.dlc(2, 2)
[1.3193, 0.1728, 0.1728]
用連續的結果去近似離散的情況,誤差量級是1/n。
現有的100、80、200、180包的情況的總結表格
100
1
2
3
1
(67.33, 0.00, 0.00)
(109.12, 0.00, 67.33)
(155.53, 0.00, 84.75)
2
 
(133.31, 17.42, 17.42)
(170.68, 8.18, 52.63)
3
 
 
(197.60, 26.26, 26.26)
80
1
2
3
1
(54.00, 0.00, 0.00)
(87.52, 0.00, 54.0)
(124.74, 0.00, 67.96)
2
 
(106.93, 13.96, 13.96)
(136.90, 6.56, 42.18)
3
 
 
(158.50, 21.06, 21.06)
200
1
2
3
1
(140, 0.00, 0.00)
(217.15, 0.00, 134.00)
(309.51, 0.00, 168.70)
2
 
(339.58, 34.70, 34.70)
(339.58, 16.28, 104.83)
3
 
 
(393.09, 52.30, 52.30)
180
1
2
3
1
(120.67, 0.00, 0.00)
(195.54, 0.00, 120.67)
(278.71, 0.00, 151.91)
2
 
(238.85, 31.25, 31.25)
(305.80, 14.66, 94.39)
3
 
 
(353.99, 47.10, 47.10)
比如說180大包需要UR卡A卡2張,B卡3張,查表得(305.80, 14.66, 94.39)。意思是14包或之前抽到A卡可以重置,94包或之前抽到B卡可以重置。該輪重置後退化成需求數量更少的情形繼續查表,直到抽滿。抽滿的期望是305.80包。
當然,完全按照這個表去做的前提是一開始的需求就非常明確,包裏其它的卡都認爲毫無價值
有的卡雖然暫時想玩的卡組用不到,但可能以後有用或有通用的用途。又或者在“自己玩什麼卡組”這方面不強求,而會根據前幾包抽到的卡接受自己能玩什麼卡組。再說出新卡,舊卡進表也是不斷在發生的。考慮到這些情況,這個表就只是個大致的參考。
另外,對有嚴格預算(hard budget build)的情況來說,只要餘下的卡包裏還有需要的卡而提前重置,雖然可能降低期望,但一定會提高最壞情況的消耗
大包UR和SR都需要的情況就會比較複雜。我們也考慮過一個包裏有三種獨有卡想要的情況。這等於是在更大的一個空間裏分更多情況求和或積分。有一點思路但還沒有完整結果。
對不提前重置的情況的補充說明
下面這個網站有抽包模擬
我看了後,感覺這個模擬是不考慮提前重置的。而且沒有考慮到+1。比如說100包的小包抽一種一張的UR,期望是50.5包,而不是50包(1到100的平均)。
不提前重置的期望值其實比較好算,對任意獨有卡組合都可以。
例子:
100包的卡,需要獨有A卡3張、B卡3張、C卡2張、D卡1張、E卡1張。先換個角度去看所要的卡:

也就是三輪分別抽5、3、2張獨有卡。n包的卡裏抽出k張獨有卡的期望是抽(n+1)*k/(k+1)包。我一時寫不出嚴格推導,不過相當確定這個結論。只要想像成均匀切割就可以了。那抽滿的期望就是
101*(5/6 + 3/4 + 2/3) = 227.25
如果是大包SR並且需求是偶數2,那第一輪可以把這兩張SR當成兩張不同的獨有卡就可以了。如果大包SR的需求是奇數就會複雜一些。
大包UR和SR各需要一張,期望是在7/12的位置抽滿。先想像成那1張UR和2張SR均匀切割。有2/3的機會在平均1/2的位置剛好抽UR和SR,有1/3的機會在平均1/2的位置抽到兩張卡但都是SR,需要進一步抽到3/4才能抽到UR。因爲這個問題是線性的所以可以這樣去簡化計算。
提前重置與否的差距
是否採用提前重置策略,抽滿所要的期望值是不一樣的。當然採用提前重置會低一些。具體見下表。
100
1
2
3
1
(67.33, 67.33)
(109.12, 117.83)
(155.53, 168.33)
2
 
(133.31, 134.67)
(170.68, 185.17)
3
 
 
(197.60, 202.00)
第一個數字是採用提前重置策略的期望,第二個是不採用時的期望。顯然當需求偏差大時,提前重置的作用更明顯。需求總量也會讓提前重置用到的機會稍多一些。

人已赞赏
心得分享精选看点

沉稳,低调,厚积薄发——写在YGL捧杯RW联赛冠军后

2021-3-23 15:37:12

游戏难点精选看点

传1上王到底要打多少局?

2021-3-24 10:22:11

12 条回复 A文章作者 M管理员
  1. 姐骑兵团水姐

    请问决斗链接大学什么时候开学,还收学生吗?

  2. 拷贝猫菜叶

    学废了

  3. 雨月

    强大的Python,但我仍然喜欢Java

  4. 平凡上班族

    学习遇到难题:阿巴阿巴。
    打牌遇到难题:第八门,开![○・`Д´・ ○]

  5. 喝点牛奶

    我在游戏网站学数学。

  6. 胖虎嗷

    不瞒兄弟们,我没看懂,猎凯

  7. mengxinlxw

    打牌王必精通数学😭

  8. 拉的脆皮鸡

    中文网抽卡模拟器gkd😍

  9. ABG杰尼杰尼

    不愧是石头哥。

  10. 梦随乡兮

    数学太差的我直接裂开了😂

个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索