漫談尾牙抽獎程式的公正性

上週看到以程序員生活為題材的漫畫作者西喬的創作:「年会上的程序员们……」,改編自一個「CTO覺得抽獎程式有點問題,程式作者被迫在旺年會場接受上千人Code Review」的奇妙真實故事,令人不禁莞爾。

很巧地,看到漫畫的前一天剛好才參加完資訊部門尾牙,而永遠的重頭戲-摸彩,自然是跑程式抽獎。(每天寫程式的人做不出電腦抽獎,傳出去像話嗎?)隨著抽獎號碼一一抽出,眾人希望落空,台下沒中獎的程式設計師們開始鼓噪議論:「XX號為什麼出現這麼多次?」「靠!程式絕對有鬼」「Open the source, Luke!」「程式沒做Code Review,肯定有Bug」… 話是這麼說,但大家心知肚明,程式被動手腳或真出錯的機率甚微,都是或然率使然,純粹是拿Coding哏瞎起閧,沒中獎也尋開心唄。

不過,我很無聊地思考,抽獎程式是否可以做到讓程式設計師無法挑剔呢?仔細分析:在大家眼裡,傳統的抽籤、摸彩球還是較有公信力,即使沒做到樂透開獎等級:公證律師監督,準備多組彩球、抽獎機隨機採用,大家還是習慣眼見為憑,寧可相信人手在箱子裡攪和後抽出的號碼,而不是程式不知依據什麼冒出的結果。

針對這點疑慮,我覺得唯一的解決辦法是「讓程式碼公開,演算結果能被反覆驗證」。抽獎程式的核心在於亂數產生器,依前述要求,讓亂數元件抓執行時間當亂數種子的做法是不可行的,每次執行的結果永遠不同,那你如何證明當天當時按鈕就該跑出這個結果?所以,抽獎程式要經得起考驗一定要能反覆驗證,故「以其他具公信力方式決定亂數種子,再依據其產生亂數決定抽獎結果」是較理想做法。至於亂數種子怎麼決定?就抽籤、摸彩球囉… XD

看到這裡,可能會有人想翻桌了,繞了一圈又要抽籤,為什麼不從頭到尾抽籤就好?依我的看法,如果可行,用抽籤、摸彩球取代程式更不易起爭議,因為它原理簡單,不需要專業背景就能懂,如果有人對開獎結果不服氣,就把箱子倒出來,找出他的籤條打他臉,爭議立解。而程式演算法較難理解,把電腦拆開也沒法當場驗票,被人抹黑也只能往肚吞,實在悲情。但抽籤並非萬能,很多情況只有電腦抽獎才能勝任,例如:十萬名員工的抽獎得做十萬枝籤(又不是十萬枝箭可以開草船出去借),包準工作人員忙上好幾天;要當場抽出三百名普獎,從上烏魚子海蜇皮拼盤就要開始抽,抽到水果西米露登場都沒還抽完。抽籤公平,電腦選號有效率,那就「用抽籤結果衍生一組任意數量的隨機結果」,魚與熊掌兼得。

最後,把焦點拉回「如何選一個公平且夠隨機的亂數種子」。不同語言、平台的亂數元件規格不同,以C#為例,Random型別支援亂數種子,參數型別為Int32,故最多產生20億種不同結果,可滿足絕大多數的應用。(註:JavaScript內建的Math.random()不支援亂數種子,但有現成程式庫救援,可比照辦理)

20億種變化夠大,但勞煩長官一連抽十個數字,過程偏長且會冷場。我有個好點子,不妨摻雜一些「大家公認無法人為操控又會隨機跳動的數字」,例如:前期樂透開獎號碼、氣象預報氣溫、當天收盤的道瓊工業/那斯達克/台股指數、日圓/美元/歐元匯率… 做成一堆數字牌(注意:亂數種子取用規則要事前公佈),讓長官從中抽出幾個再洗牌重排順序,就可以得到夠多位數的亂數種子。如果嫌麻煩,買三副撲克牌只留1-9給長官抽出10張再洗牌排序比較簡單(如果長官不介意演一下賭神的話)。總之,方法很多,有辦法湊出沒人質疑的數字即可,數字位數愈多隨機性愈高但愈費工且可能會冷場或讓長官不悅不爽加碼(這個很嚴重),請大會自行拿捏。

還有一種有效率的替代做法,亂數種子不用數字,改取一段文字再用MD5或SHA1雜湊轉成數字,文字到處可得(報紙標題、人名、翻字典),中文字元數目眾多,常用的就有數千個,短短幾個字經過雜湊演算就能產生足夠的變化性。缺點是由字元產生雜湊數字的概念較不直覺,抽獎對象要有相關背景才易理解,需考慮參與者的接受度。

有了亂數種子,就能得到可重複驗算的一連串隨機數字,抽獎候選清單多半儲存於陣列,最直覺的寫法是取 0 到 Array.Length-1的亂數挑選中獎者,將其自陣列移出再用同樣邏輯抽下一個。我個人則偏好另一種做法,為陣列的每一個元素產生一個亂數,再依此亂數由小到大排序,演算法較簡單,一口氣取出數百上千名抽獎者都不是問題。

借用先前500萬人次抽獎的程式當範例,程式差不是長這様,其中的12345就是亂數種子,不同亂數種子取出的得獎者不同,且可反覆驗證:

    class Program
    {
        static void Main(string[] args)
        {
            string raw = @"1.Jeffrey
2.Darkthread
3.球證
4.旁證
5.主辦
6.協辦
7.全都是我的人";
            List<string> candidates = new List<string>(raw.Split('\n'));
            Random rnd = new Random(12345);
            Console.Write(candidates.OrderBy(o => rnd.Next()).First());
            Console.Read();
        }
    }

順手也寫了一個JavaScript版:Live Demo

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width">
  <title>尾牙抽獎範例</title>
</head>
<body>
    亂數種子=<input value="12345" /> <input type="button" value="抽獎" />
   <script src="https://cdnjs.cloudflare.com/ajax/libs/seedrandom/2.4.2/seedrandom.js"></script>
  <script src="https://ajax.aspnetcdn.com/ajax/jQuery/jquery-2.1.4.js"></script>
  <script>
    var candidates = 
        "1.Jeffrey,2.Darkthread,3.球證,4.旁證,5.主辦,6.協辦,7.全都是我的人".split(',');
    $(":button").click(function() {
      Math.seedrandom($(":text").val());
      var list = $.map(candidates, function(n) {
                     return { name: n, rand: Math.random() }
                 });
      list.sort(function(a, b) { return a.rand - b.rand; });
      alert("得獎的是:" + list[0].name);
    });
  </script> 
</body>
</html>

抽獎程式碼先公開,預先公告亂數種子取碼規則,只待當天填入亂數種子就能抽出任意數量的得獎者,抽獎結果可以反覆驗證,在我心中,這就稱得上是公平公正公開的抽獎程式囉~

歡迎推文分享:
Published 01 February 2016 07:43 AM 由 Jeffrey
Filed under:
Views: 14,796



意見

# 胡忠晞 said on 31 January, 2016 08:36 PM

一般的亂數函數很容易岀現重複

# tomexou said on 01 February, 2016 12:40 PM

我也贊同最後一段話,seed用一個公開規則來隨機抽取,這樣產生的亂數表可以反覆驗證,是最公平的,也最簡單。

# 旺旺勳 said on 01 February, 2016 02:08 PM

其實就算是夠亂也不一定適合,因為還是有可能較為集中

在某個範圍。

在一個範圍內要能夠平均的出現在各個區塊內

才是讓人信服的做法,話說每個部門都有人中獎才讓人會有期待。

最好最佳的解法是用 二階質數乘餘法

它不但有國內外的論文證實有效性,國外甚至有學者用數十種

統計方式證明它是最好的亂數產生做法。

# closer said on 02 February, 2016 03:15 AM

路過留言....

其實原本那份漫畫中有提到:該位程式員是呼叫 Random.org 的 API 取得亂數種子的。Random.org 是利用大氣噪音來產生「真」亂數。用這個當種子是不是比較好呢?

# Jeffrey said on 02 February, 2016 04:09 AM

to closer,要證明程式符合規格,沒有其他方法比用測試程式反覆驗證更具說服力。依我個人觀點,亂數亂不亂共不是重點,只要演算法及規則事先公告,依據遊戲規則,那個當下就該算出這個結果,才能封悠悠之口。

Random.org 隨機性無人能質疑,但當執行結果與網路頻寬、程式執行速度快慢有關,程式跑快1ms跟跑慢1ms,頭獎易主,如此網管人員跟程式作者無形中也具有得主的決定權(雖然無法控制是誰),爭議永存。這是我認為要指定亂數種子,交由非IT人員定生死的最重要理由。

# 路過 said on 16 March, 2016 10:53 PM

怎麼抽都是1得獎

# Fish said on 28 May, 2016 10:19 PM

www.sciencenews.org/.../new-technique-produces-real-randomness

# cathy said on 10 November, 2016 03:15 AM

請問電腦抽獎的方式,如果是一般網路上下載,會有自key入人名的方式抽獎,而不是跑號碼的嗎? 甚至說如果想要出現公司logo,是否現成的軟體都沒有,一定須要另外寫呢?

如果須要另外寫,有沒有推薦的軟體公司,費用大約是多少呢?

謝謝~

# 花花 said on 18 November, 2016 01:38 AM

to cathy

個人有幫公司寫一套抽獎系統,若有興趣可與我聯絡,email: eee198172@gmail.com

你的看法呢?

(必要的) 
(必要的) 
(選擇性的)
(必要的) 
(提醒: 因快取機制,您的留言幾分鐘後才會顯示在網站,請耐心稍候)

5 + 3 =

搜尋

Go

<February 2016>
SunMonTueWedThuFriSat
31123456
78910111213
14151617181920
21222324252627
282912345
6789101112
 
RSS
創用 CC 授權條款
【廣告】
twMVC

Tags 分類檢視
關於作者

一個醉心技術又酷愛分享的Coding魔人,十年的IT職場生涯,寫過系統、管過專案, 也帶過團隊,最後還是無怨無悔地選擇了技術鑽研這條路,近年來則以做一個"有為的中年人"自許。

文章典藏
其他功能

這個部落格


Syndication