はじめに
先進サービス開発事業部の山岡です。
重み付き乱択アルゴリズムとは結果に偏りのある抽選の事で、身近な例でいえばソシャゲのガチャでしょうか。ガチャはアイテムの抽選結果に偏りがあり、一般にそのアイテムの有用性が高いほど入手確率が低く設定されています。
こういった処理をプログラムで実装する機会があったので記録を残したいと思います（ガチャの実装ではありませんが）。
基本的な考え方
まずはGoとは関係無くどのようなロジックでこの抽選機能を実装するか考えましょう。
例えば金貨、銀貨、銅貨という3種類のアイテムがあったとします。出現確率が均等（1/3）である場合、単純に疑似乱数で発生させた値から3の剰余を取ればOKです。しかし今回の場合アイテムの希少性を反映し金貨5％、銀貨20％、銅貨75％という偏りを付けたいとします。
これは100回抽選した場合に金貨5枚、銀貨20枚、銅貨75枚になることが期待されますので、これをプログラムで実装するには乱数から100の剰余を取りどの結果に合致するかを判定すればよいことになります。
100回の抽選結果を100個の配列で表現すると金貨はarray[0]-[4]、銀貨はarray[5]-[24]、銅貨はarray[25]-[99]と表現できます。
仮に剰余が7だった場合（＝銀貨が当選した）を表したのが下記図です。またこの時に判定の基準になる値を「境界値」として青線で表現しています。この境界値を基準として順番にチェックしていけば取得した剰余がどこに該当するか（＝何が当選したか）を判定することができます。
Goのコード解説
weighted-randomize.go
package main import ( "fmt" "math/rand" "sort" "time" ) // itemWeights アイテム毎の重み一覧 var itemWeights = []int{ 5, // 金貨 5% 25, // 銀貨 25% 70, // 銅貨 70% } func main() { sort.Ints(itemWeights) // 重みの昇順でチェックしていくので重み一覧をソートする // 抽選結果チェックの基準となる境界値を生成 boundaries := make([]int, len(itemWeights)+1) for i := 1; i < len(itemWeights)+1; i++ { boundaries[i] = boundaries[i-1] + itemWeights[i-1] } boundaries = boundaries[1:len(boundaries)] // 頭の0値は不要なので破棄 // 1000000回抽選を行う rand.Seed(time.Now().UnixNano()) result := make([]int, len(itemWeights)) n := 1000000 for i := 0; i < n; i++ { draw := rand.Intn(boundaries[len(boundaries)-1]) + 1 for i, boundary := range boundaries { if draw <= boundary { result[i]++ break } } } fmt.Printf("境界値: %v\n", boundaries) fmt.Println("重み 想定 結果") fmt.Println("-----------------------------") for i := 0; i < len(itemWeights); i++ { fmt.Printf("%4d %f %f\n", itemWeights[i], float64(itemWeights[i])/float64(boundaries[len(boundaries)-1]), float64(result[i])/float64(n), ) } }
概ねコメントに書いてありますが細かい補足をこの記事でします。
まず抽選結果チェックの基準となる境界値の算出ですが、これは昇順ソートされていることを前提として「1つ前の境界値＋重み」で計算することができる（但し一番最初は0とする）のでそのようにfor文を組みます。また頭の0値は判定に不要なので削除します。
次に抽選ですが乱数のシードを初期化するのは当然として、抽選結果に+1する必要があります。これはGoの rand.Intn(n int) は0～引数に指定された値-1を生成するためで、前出の図の通り境界値は5と25なので+1して抽選結果を1～100にする必要があります。
今回の場合境界値の範囲がある程度広いためそれほど大きな誤差にはなりませんが、1:2のような狭い範囲の重みで抽選を行うと異常な結果になってしまいます（実際にやってみたコードが こちら 。31行目のコメントを外すと正しい結果になります）。
Go Playgroundの結果は以下のようになり、良い具合に重みがついた抽選ができていることがわかるかと思います（補足：Go Playgroundは時刻が固定なので常に同じ結果）。
境界値: [5 30 100] 重み 想定 結果 ----------------------------- 5 0.050000 0.049810 25 0.250000 0.250057 70 0.700000 0.700133
