ストリームアルゴリズムを用いて確率抽選を行う

ゲームにおけるアイテムのドロップなどにありがちな、

• Aというアイテムは50%で出現する
• Bは30％で出現する
• Cは20％で出現する

という確率に従ってA,B,Cを抽選するという処理を考えます。
様々な実装方法がありますが、ここではストリームアルゴリズム的な実装方法について記載します。

ストリームアルゴリズムとは

ストリームアルゴリズムとは、forループを用いて逐次的な処理で実現するアルゴリズムを指します。

例えば、配列から最大値を求める時に

const arr = [3, 1, 4, 2]
let max = arr[0]
for(let i = 1; i < arr.length; i++){
  if(arr[i] > max) max = arr[i]
}
console.log(max) // 4

のような実装をしますが、これがストリームアルゴリズムです。

ストリームアルゴリズムによる抽選方法

では本題の抽選についてですが、次のように実装します。

const arr = [50, 30, 20] // 生起確率（%）
let index = 0
let sum = 0
for(let i = 0; i < arr.length; i++){
  sum += arr[i]
  if(sum * Math.random() < arr[i]){
    index = i
  }
}

これを前述したABCの例で説明すると、

1. まずAが選ばれてる状態から開始
2. Aが50%、Bが30%なので、30/80=37.5% の確率でBを選択状態にする
3. Cは20％なので、20/100=20％の確率でCを選択状態にする

と言う流れになります。

試しに以下のようなコードでサンプリングしてみると、

function P() {
  const arr = [50, 30, 20]
  let index = 0
  let sum = 0
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i]
    if (sum * Math.random() < arr[i]) {
      index = i
    }
  }
  return index
}
 
const result = [0, 0, 0]
for (let i = 0; i < 10000; i++) {
  result[P()]++;
}
console.log(result)

[4962, 3006, 2032] という期待通りの出力を得ることができました。

ストリームアルゴリズムは、メモリを節約することができる特徴があり、色々な場所で使えると思います。