JavaScriptで重みを付けてランダムに出現させる。(重み付き乱択)

2019/01/12/2019/10/06/

背景

JavaScriptにおいて、ある特定の要素群を重みを付けてランダムに出現させる方法（重み付き乱択）について記載します。
既に記載されている方も多いのですが、私の理解力不足でイメージしづらかったため、少しずつ順を追って説明していきます。

重み付き乱択について

ゲームなどで、アイテムによって出現確率を変えてドロップさせたい場合などに利用できます。
実際の利用ケースを想定して以下に実装方法を整理していきます。

例えば、以下の3つのアイテムがある場合を考えます。

金の剣
青銅の剣
木の棒

上記アイテムは、レア度が高い順に金の剣 > 青銅の剣 >> 木の棒であるとします。

まず、以下のようにアイテムごとに重みを設定します。

アイテム名	重み(個数)
金の剣	1
青銅の剣	2
木の棒	7

重みは出現のしやすさです。ここではわかりやすさのため、重み = 個数と考えます。
アイテムは全部で10個あります。金の剣はレア度が高いため、他の剣よりも数が少なく10個中1個しかありません。逆に、木の棒はレア度が低いため10個中7個あります。

コードで表すと以下です。（処理1）

const itemList = [
  { name: '金の剣' , stock: 1 },
  { name: '青銅の剣' , stock: 2 },
  { name: '木の棒', stock: 7 }
]

次に、重み（個数）の合計を求めます。（処理2）

const totalWeight = itemList.reduce((previous, current) => {
  return { weight: previous.weight + current.weight }
});

ここでは、アロー関数(※1)と配列のreduceメソッド(※2)を利用しています。
上記処理により、アイテム合計個数が 10個 であることがわかります。

現在の状況を棒グラフで図示すると以下のようになります。
このように位置関係（分布）で考えることが理解に繋がります。

f:id:stuffed_cabbage:20190112025702p:plain — 全体要素のグラフイメージ

次に、用意した全10個のアイテムから1個のアイテムを取得する場合を考えます。
以下のコードで表せます。（処理3）

let pickedItem = Math.random() * totalWeight;

Math.random()では、0.0～1.0未満の乱数が返ります。
また、totalWeightには、現在10.0が格納されています。

つまり、pickedItemには、0.0～10未満の値が格納されます。
取り出した値(pickedItem)が、どのアイテムに該当するかを下図で確認します。

f:id:stuffed_cabbage:20190112025801p:plain — 取得時イメージ

上図のような横に長いダーツボードがあるとイメージします。また、アイテム1個あたり 1.0の長さをとることします。
金の剣は1個あるので、0.0~1.0の幅でアイテム1個分のスペースをとります。続けて1.0を起点として、青銅の剣は1.0~3.0までの幅で、アイテム2個分のスペースをとります。同様に、木の棒は3.0~10.0までの幅で、アイテム7個分のスペースをとります。
ダーツボードにダーツを投げて、刺さった場所のアイテムが貰えるものとすると、ダーツを投げる行為が先程のランダム値の取得になります。

プログラムでは、ダーツの刺さった場所を確認する必要がありますので、以下のコードで確認します。（処理4）

const AppraiseItem = (pickedItem, itemList) => {
  let searchPosition = 0.0;
  for (const item of itemList) {
  searchPosition += item.weight
  if (pickedItem < searchPosition) { return item.name }
  }
}

取り出したアイテム(pickedItem)が、2.6だったと仮定します。

ダーツボードの左から順番に比較していきます。
はじめの探索位置(searchPosition)は、0.0から始まります。

1回目のfor文で、1個目の要素幅(金の剣)分探索します。
イメージとしては、下図になります。

f:id:stuffed_cabbage:20190112025655p:plain — 探索1回目

初期探索位置(0.0)から現在探索位置(1.0)までの範囲で、取り出したアイテム(pickedItem)がないか確認します。取り出したアイテム(pickedItem)の値は、2.6ですので、金の剣には該当しません。金の剣に該当しませんでしたので、次の要素(青銅の剣)に進みます。

2回目のfor文で、2個目の要素幅(青銅の剣)分探索します。
イメージとしては、下図になります。

f:id:stuffed_cabbage:20190112025651p:plain — 探索2回目

前回探索位置から(1.0)から現在探索位置(3.0)までの範囲で、取り出したアイテム(pickedItem)があるか確認します。
取り出したアイテム(pickedItem)の値は、2.6ですので、この範囲に存在することがわかります。つまり、取り出したアイテムが「青銅の剣」であることがわかりました。

総括

このように、重み付け乱択は、グラフ(軸)で考えると非常にわかりやすいです。
全部で10の範囲のうち、0.0~1.0は金の剣、1.0~3.0は青銅の剣と、全体の領域を、
それぞれの要素が、自身の重み分の領域を占有するイメージになります。当然、占有する幅が大きいほど、出現する確率は高くなります。
このアルゴリズムは、順番が前後しても出現確率は同様です。重み(幅)が変わらない限りは変化がありません。

完成コード

完成コードを以下に示します。
処理3と処理4は、GetItem関数にまとめています。

const itemList = [
  { name: '金の剣' , weight: 1 },
  { name: '青銅の剣' , weight: 2 },
  { name: '木の棒', weight: 7 }
]

const totalWeight = itemList.reduce((previous, current) => {
  return { weight: previous.weight + current.weight }
});

const GetItem = (itemList) => {
  const pickedItem = Math.random() * totalWeight.weight;
  let searchPosition = 0.0;
  for (const item of itemList) {
    searchPosition += item.weight
    if (pickedItem < searchPosition) { return item.name }
  }
}