2020年10月22日 星期四

機率研究 (1) - 有限及無限個數機制與應用情景

在本文中,採用的研究是遊戲中所使用的常見中獎機率與分配研究。 在開始討論整體機率的設計之前,我想用「有限」、「無限」來區分設計方式。


在機率研究的系列中,應該會在幾個面向繼續探討: 機率分佈對機率調整的觀察、PDF,CDF 與偽隨機數產生器的實作、常見的隨機數產生器實作 (線性同餘、 BSD, MS...etc) 


無限個數的抽獎平衡

多數的人可能會認為,轉蛋機、抽獎的事件應該使用 Bernoulli(即 Binomial) 分佈描述,也有人說抽獎個數一多,就會呈現 Normal Distribution(常態分配) 的形狀,這個部份的問題,就是因為 Reward(獎品、獎勵分數) 可能不受發行數量限制,但又希望維持一定的公平性,所採用的設計方式。

P.S: 由於零星個案的隨機測試樣本不一定會靠近應有的數字,可能要測到 1 萬、10 萬才會較精準,因此,樣本若希望有較好的解釋能力,建議可以參考【樣本檢定】。 (針對主管報告時可能需要做事前準備)


常見寫法與應用


楓之谷轉蛋機機率探討

現呈的例子總是特別好舉例,我找到的是楓之谷 TMS 183 版本的 Java Code,由於架過楓之谷的私服,所以比較了解從哪邊開始 trace code,先找到一個 NPC List,找到轉蛋機的 NPC ID: 9100100 ,剛好在 server npc 目錄下也可以找到對應的 9100100.js 檔案,裡面用的轉蛋卷稱呼是 Gachapon Tickets ,總之回到正題,考慮以下寫法:

function action(mode, type, selection) {
    if (mode == 1) {
	status++;
    } else {
	status--;
    }
    if (status == 0) {
	if (cm.haveItem(5220000)) {
	    cm.sendYesNo("You have some #bGachapon Tickets#k there.\r\nWould you like to try your luck?");
	} else {
	    cm.sendOk("You don't have a single ticket with you. Please buy the ticket at the department store before coming back to me. Thank you.");
	    cm.safeDispose();
	}
    } else if (status == 1) {
	var item;
    
        // 1/300 的機率會中大獎
	if (Math.floor(Math.random() * 300) == 0) {
            // 獲得紫色冒險家披風一個 (曾經風光的東西)
	    item = cm.gainGachaponItem(1102042, 1); 
	
        } else {
    
            //考慮有 n 個數量的物品
	    var itemList = new Array(2040317, 3010013, 2000005, 2022113, 2043201, 2044001, 2041038, 2041039, 2041036, 2041037, 2041040, 2041041, 2041026, 2041027, 2044600, 2043301, 2040308, 2040309, 2040304, 2040305, 2040810, 2040811, 2040812, 2040813, 2040814, 2040815, 2040008, 2040009, 2040010, 2040011, 2040012, 2040013, 2040510, 2040511, 2040508, 2040509, 2040518, 2040519, 2040520, 2040521, 2044401, 2040900, 2040902, 2040908, 2040909, 2044301, 2040406, 2040407,1302026, 1061054, 1061054, 1452003, 145003, 1382037, 1302063, 1041067, 1372008, 1432006, 1332053, 1432016, 1302021, 1002393, 1051009, 1082148, 1102082, 143015, 1061043, 1452005, 1051016, 1442012, 1372017, 1332000, 1050026, 1041062);
        
            //隨機在 n 個數量為長度的機率事件中,挑選一個出來獲得
	    item = cm.gainGachaponItem(itemList[Math.floor(Math.random() * itemList.length)], 1);
	}

        //也許發生爆破性的結果
	if (item != -1) {
            //就還你一個藍色轉蛋劵 (物品代碼由 Reference [1] 得知)
	    cm.gainItem(5220000, -1);
	    cm.sendOk("You have obtained #b#t" + item + "##k.");
	} else {
	    cm.sendOk("Please check your item inventory and see if you have the ticket, or if the inventory is full.");
	}
	cm.safeDispose();
    }
}


這個寫法中,事實上我們有一個結論,就是 「中獎優先次序級」,顯然紫色冒險家披風是優先去抽獎的,但是機會只有 1/300 ,如果沒有抽到,就隨機給定,這也營造了大獎先抽的氛圍,就機率上的差別來看,我們可能會考慮紫色冒險家披風被連續抽中的機率,他的算法是獨立事件乘積,若我們想看連續被抽中兩次紫色冒險家披風的機率,那就是:


$$\frac{1}{300} \times \frac{1}{300} = \frac{1}{90000} \approx 0.00001$$


相較於連續兩次抽中其他物品的機率:


$$\frac{299}{300} \times \frac{299}{300} = \frac{89401}{90000} \approx 0.99$$


也就是說,這種優先次序級的做法,在機率很小的時候,不見得會受到很大的連抽影響。 (注意,這是在機率很小的時候)


因此,我們也可以有以下的例子 (Java):

public static void main(String[] args) {
    //獎品優先等級式機率
    System.out.println(Math.floor(Math.random() * 3));
    if(Math.floor(Math.random() * 300) == 0){
        System.out.println("楓葉紫色戰劍");
    }else if (Math.floor(Math.random() * 300) == 0){
       System.out.println("黃金楓葉劍");
    }else{
        System.out.println("隨機丟垃圾給你");
    }
}

其實不只有轉蛋機會這麼做,事實上去追回 maplestory 大多有關中獎的 code 都是這麼做的,可以看看 Reference [2]。


以平等的角度看,這個 code 表現出來是沒有先後次序疑慮的 (Java):

public static void main(String[] args) {
    int item = (int)Math.floor(Math.random() * 4);
    switch (item) {
        case 0:
            System.out.println("進化單手武器魔力卷軸50%");
            break;
        case 1:
            System.out.println("混沌卷軸60%");
            break;
        case 2:
            System.out.println("純白的卷軸 50%");                
            break;
        case 3:
            System.out.println("傳說潛在能力卷軸30%");                
            break;
        default:
            throw new AssertionError();
    }
}

對所有的品項而言,中獎機率都是 1/4。


對每個品項做機率分配,除了上方對每個物品做 random == ? ,也可以從分區塊的觀點來看 (Java):

public static void main(String[] args) {
        int chance = (int)Math.floor(Math.random() * 10);
        switch (chance) {
            //分配機率為 1/2      (50%)
            case 0:
            case 1:
            case 2:
            case 3:            
            case 4:
                System.out.println("進化單手武器魔力卷軸50%");
                break;
                       
            //分配機率為 3/10     (30%)
            case 5:
            case 6:     
            case 7:        
                System.out.println("混沌卷軸60%");
                break;
                            
            //分配機率為 2/10     (20%)
            case 8:   
            case 9:
                System.out.println("純白的卷軸 50%");                
                break;
                                
            default:
                throw new AssertionError();
        }
}

對 chance 而言, 0~4 是一個區塊, 5~7 也是一個區塊, 8-9 也是一個區塊,數字落在這之中,就會中獎,這也是一種機率分配的方式。


零散區塊與連續區塊合併,對中獎機率的看法,就必須從機率值本身說起,連續抽到兩次是同區塊的機率,與連續兩次抽到同獎勵,但是是零散區塊與連續區塊的機率是不同的,也就表示在零散區塊與連續區塊,該物品中獎的機率並不是單純的母數加總,這樣的分配我還沒想到要怎樣看待這個機率分佈。


簡化剛才的詭異寫法,這會是使用此方法時不錯的寫法 (Java):

public static void main(String[] args) {
        int chance = (int)Math.floor(Math.random() * 10);
        if(0 <= chance && chance <= 4){
            System.out.println("進化單手武器魔力卷軸50%");
        }else if(5 <= chance && chance <= 7){
            System.out.println("混沌卷軸60%");
        }else{
            System.out.println("純白的卷軸 50%");
        }
}



有限個數的抽獎平衡


有限個數抽獎,這已經表是對整個尚未被觀察的打亂獎品集合來說機率會是完全固定的,在實作上的簡易說明就是: shuffle( reward_array ) 。

每次抽獎時,就會使用 reward_array.pop() 或 shift() 去取值,也就是從集合中撈出一個獎勵,但此時就必須考慮取球問題,當每次取出一個元素時,你同時也改變了整個集合的機率,因此,你可能需要設計一個機制,讓有限個數的獎勵集合補上新的值,亦或是時間到之後,重設所有機率。

這是最簡單的做法,另外我也在考慮獎勵集合的內部機率,在有限個數下,我想得到兩種加一種延伸的設計方法:

  1.  完全固定獎勵及數量,並存在【無任何中獎】的事件,那麼可以設計為: 每個獎品都有自己的機率值 (randInt(1,300) == 0) 以及如果無任何中獎,就跳出無中獎
  2. 打亂固定的陣列排序
    1.  延伸做法: 通過混亂程度來決定一個獎品的機率 (尚無法確定是否可以做到)


常見寫法與應用


拿一個例子來探討,考慮以下程式碼,從混淆陣列中來看,在陣列中每一個值得機率都是一樣的 (Java):

public static void main(String[] args) {
        //獎勵陣列
        int array[] = new int[]{ 2040317, 3010013, 2000005, 2022113, 2043201, 2044001, 2041038, 2041039, 2041036, 2041037, 2041040, 2041041, 2041026, 2041027, 2044600, 2043301, 2040308, 2040309, 2040304, 2040305, 2040810, 2040811, 2040812, 2040813, 2040814, 2040815, 2040008, 2040009, 2040010, 2040011, 2040012, 2040013, 2040510, 2040511, 2040508, 2040509, 2040518, 2040519, 2040520, 2040521, 2044401, 2040900, 2040902, 2040908, 2040909, 2044301, 2040406, 2040407,1302026, 1061054, 1061054, 1452003, 145003, 1382037, 1302063, 1041067, 1372008, 1432006, 1332053, 1432016, 1302021, 1002393, 1051009, 1082148, 1102082, 143015, 1061043, 1452005, 1051016, 1442012, 1372017, 1332000, 1050026, 1041062 };
        //建立該獎勵陣列長度的 List
        List<Integer> solution = new ArrayList<>(array.length);
        //把獎勵陣列值丟到 List
        for (int i : array)
        {
            solution.add(i);
        }
        //做洗牌
        Collections.shuffle(solution);
        //顯示洗牌值 [2000005, 2040009, 365201, 10610....
        System.out.println(solution);
        //取得迭代器
        Iterator<Integer> it = solution.iterator();
        //直接拿混亂洗牌中第一個值 2000005
        System.out.println(it.next());
        //從牌組中拿掉該值
        it.remove(); 
        //取得下一個排組值 2040009
        System.out.println(it.next());
        //從牌組中拿掉該值
        it.remove();
        //顯示目前得牌組值 [365201, 10610....
        System.out.println(solution);
}



機率概念 PoC


硬幣只有一正一反,相當於公平的硬幣來說,一正一反的機率會是 5:5 開,要怎樣才能更好的理解這回事?


從 Python 部分的實作,可以得到答案:

sum([ (1 if random.randint(1,2) == 1 else 0) for i in range(1000) ])/1000

這段的意思是, random 1, 2 相當於正反面,如果是正面 1 就給 1 放到陣列,如果是反面就把 0 放到正面,然後重複做 1000 次,把整個陣列加總,你得到的是所有正面值的加總,把它除與 1000 次得到平均。

我跑的其中一次結果是 0.528 ,跑越多次可以越逼近 5:5 開。


Bernoulli / Binomial Distribution 看法與觀點


換個寫法,因為只有中跟沒中兩個結論,在統計學中我們要使用的分佈是 Bernoulli Distribution(就是 Binomial Distribution),這部份如果你不知道怎樣看,可以看到 Wiki 上的 Bernoulli Distri/Binomial Distri 頁面上,旁邊的支撐集 (Support),告訴你 $$ k=\{0,1\}\, $$

也就是二元機率。


對於一個硬幣朝上的機率是 0.2 (這只是假設,實際上這是與你的真實情境所設計的機率有關,不是寫 0.2 就表是硬幣朝上機率是 0.2,我們說硬幣朝上是 0.5 是因為硬幣只有 2 個結果,對於每個結果來說是獨立事件,因此每個面的機率是 1/2 = 0.5 )

# 證明 20% 機率 
test = sum(np.random.binomial(1, 0.2, 100000) == 1) / 100000
print(test)

這裡跑了更多次,我跑出來其中一次結果是 0.20132。


一次丟五個硬幣, 每個硬幣朝上的機率是 0.5, 重複 10 次試驗,以下為【每一次試驗】硬幣朝上的【個數】:

test = np.random.binomial(5, 0.5, 10)
print(test)

我跑出的其中一次結果是 [1 4 2 1 1 4 3 2 5 2]


一次拋 2 個硬幣,每枚硬幣拋到正反兩面的概率都是0.5,那麽兩個硬幣都是正面的概率是多少?

test = sum(np.random.binomial(2, 0.5, 100000) == 1) / 100000
print(test)


至於分佈圖的看法,是根據你所設定的參數去決定機率質量函數 (PMF) 長怎樣,這是整個概觀的函數統計圖形:


n=7
p=.6
k=np.arange(0,n+1)  #k 比 n 多一個 (0 ~ n+1 個)
binomial = stats.binom.pmf(k,n,p)

plt.plot(k,binomial,'o-')
plt.title('Binomial: (TIMES)n=%i , (COIN FRONT)p=%.2f' % (n,p), fontsize=15)
plt.xlabel('Number of Successes')
plt.ylabel('Probability of Successes')
plt.show()





但是量化的數據,如果說跑無限次會靠近 Normal Distribution (中央極限定理),我是覺得應用在有限獎品的情況下,使用此假設並不合理,要是你的 Random Generator 雷你一次,你的獎品發完就等著吃自己。  所以,關於 Random Generator 要怎樣產數字,才會讓我們安心,我們會接著在下幾篇文章後做文獻探討。


Reference:

[1] http://aicltw.blogspot.com/2016/10/blog-post_6.html

[2] https://github.com/reanox/MapleStory-v113-Server-Eimulator/search?q=Math.random%28%29

沒有留言:

張貼留言

© Mac Taylor, 歡迎自由轉貼。
Background Email Pattern by Toby Elliott
Since 2014