エイリアス法

ひとことで

「コモン 40%、レア 18%、レジェンド 5%」のような重み付きの抽選を、品物の数によらず一定の手間で行う方法です。前もって「どの列も高さ 1 で、色は多くても 2 つ」という表を作っておくと、抽選は「列をサイコロで 1 つ選び、0〜1 の乱数で下の色か上の色かを決める」だけになります。乱数 2 個と比較 1 回で済むので、同じ表から何百万回も抽選する場面で効果を発揮します。

ゲームでの使いどころ

• ドロップ・ガチャ：品物の多いドロップ表から、敵を倒すたびに抽選する。
• 大量の粒子の発生：メッシュの三角形を面積に比例して選び、表面から粒子を出す（大きな三角形ほど多く）。
• 手続き生成：波動関数崩壊でタイルの出現の重みに従って選ぶ、地形の上で植物の種類を重み付きで選ぶ。
• 多数の光源の選択：明るさに比例して光源を選ぶ（重要度サンプリング）とき、GPU でも分岐が少なく速い。

しくみ

$n$ 個の品物の確率を $p_i$ とします。

1. 平均を 1 にそろえる：各重みを $n$ 倍し、$h_i = n\,p_i$ とします。平均はちょうど 1 です。
2. 小と大に分ける：$h_i < 1$ の列を「小」、$h_i \ge 1$ の列を「大」のリストに入れます。
3. 大から切って小を埋める（ボーズの方法）：小の列 $s$ と大の列 $l$ を 1 つずつ取り出し、$s$ の空き $1 - h_s$ を $l$ から切り取って $s$ の上に継ぎ足します。$s$ の列の表は「下が $s$ で割合 $h_s$、上が $l$」で確定します（$\text{prob}_s = h_s$、$\text{alias}_s = l$）。$l$ の高さは $1 - h_s$ だけ減るので、1 を下回れば小へ、そうでなければ大へ戻します。
4. どちらかのリストが空になるまでくり返し、残りの列は $\text{prob} = 1$ とします。

各ステップで 1 列が確定するので、表は $O(n)$ で作れます。抽選は

です。どの列も面積 1 で、品物 $k$ の色の面積の合計は $n\,p_k$ なので、ちょうど確率 $p_k$ で選ばれます。

実装のポイント

• 乱数 1 個で済ませる：$n u$ の整数部分で列を、小数部分で高さを決めれば、乱数は 1 個で足ります（精度が十分な場合）。
• 重みが変わるなら：表の作り直しは $O(n)$ です。重みが毎回変わる抽選や、数回しか抽選しない場合は、累積和の二分探索（$O(\log n)$）の方が手軽です。
• 誤差の扱い：浮動小数点の誤差で、最後に「小」に 1 よりわずかに小さい値が残ることがあります。残った列はすべて $\text{prob} = 1$ にします。

つまずきやすい点

• 表示される確率と実際の確率：ガチャなどでは、表示した確率と実際の抽選が一致していることが求められます。表を作ったら、大量に抽選して割合を確かめるテストを用意します。
• 品物の追加で表が変わる：品物を 1 つ足しただけで、ほかの列の組み合わせも変わります。表をデータとして保存して使い回す場合は、重みを変えたら必ず作り直します。
• 天井や確率の変動：抽選回数に応じて確率を変える仕組み（天井）では、重みが毎回変わるので、エイリアス法の利点が薄れます。

デモで試すこと

1. 最初に、重みを平均 1 にそろえた棒が並び、大きい列（コモン）から切り取った部分が、小さい列の上へ移っていきます。左上の説明で、各手順で何が確定したかを確かめてください。
2. 表が完成すると、どの列も点線（高さ 1）にそろい、色は多くても 2 つになります。
3. 抽選では、白い枠で列が選ばれ、白い点の高さで下の色か上の色かが決まります。右下のグラフで、出た割合（赤）が元の重み（点線）に近づくことを確かめてください。
4. 「1 秒の抽選回数」を上げると、すぐに重みどおりの割合になります。「ドロップの重み」を変えると、表の作り方がどう変わるかも観察できます。