LV. 4
GP 109

【攻略】抽包的數學(未完成)(更新提前重置與否的比較)

樓主 Z.Blade danstone
GP34 BP-
前段時間我們群裏有人問起某個包抽到了某張卡,要不要重置這樣的問題。群裏的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包能抽出來。第一個程序是離散的情況,看當前重置與否哪個期望cost最低,再遞歸累計求和。第二個程序是連續的情況,最後的式子是我積分化簡後的結果。原本以爲化簡後觀察前幾個結果能猜出通項公式,再用歸納法證明。但是繁瑣程度超出我的想像。

示例

>>> import dl
>>> dl.dld(100, 1, 1)
[67.33333333333336, 0.0, 0.0]
>>> dl.dld(100, 1, 2)
[109.12333333333335, 0.0, 67.33333333333329]
>>> dl.dld(100, 2, 2)
[133.3097232323233, 17.420000000000016, 17.420000000000016]

輸入是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.6666666666666667, 0.0, 0.0]
>>> dl.dlc(1, 2)
[1.080246913580247, 0.0, 0.6666666666666665]
>>> dl.dlc(2, 2)
[1.3192571392371564, 0.17283950617283939, 0.17283950617283939]

用連續的結果去近似離散的情況,誤差量級是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)

第一個數字是採用提前重置策略的期望,第二個是不採用時的期望。顯然當需求偏差大時,提前重置的作用更明顯。需求總量也會讓提前重置用到的機會稍多一些。

34
-
未登入的勇者,要加入 2 樓的討論嗎?
板務人員:

524 筆精華,今天 更新
一個月內新增 10
歡迎加入共同維護。


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】