抽選の仕組みについて考えてみた
メリークリスマスイヴ！
世間はクリスマスだってのに働き者はいるもんだ
みなさまメリークリスマスイブ！！！
私は40年来のガンダムオタクなのでクリスマスと言えば「機動戦士ガンダム0080 ポケットの戦争」と「新機動戦記ガンダムW Endless Waltz」を思い浮かべてしまいます。
ポケットの中の戦争の主人公「アルフレッド・イズルハ」役の声優さんは今や超売れっ子ベテラン声優の浪川大輔さんです。当時12歳だったそうです。
今ではオンデマンドサービスで両作品観れるのでまだ未見で浪川大輔さんファンも機会があれば見てください！
本エントリーはコネヒトアドベントカレンダーの24日目のエントリーです。
背景
10年くらい前までソーシャルゲーム開発を行う会社にいたのでガチャの仕組みの実装も見る機会がありました。
ソシャゲをやらない人もガチャという単語を使うことがあるので割と一般的な言葉になっているのではないでしょうか？
ふと「抽選のロジックってどんなのがあるんだろう？」という疑問が湧いてきたので調べてみようと思いたちました。
AdventCalendar以前にブログ形式の投稿をするのが苦手なので、今回は完全に趣味丸出しで自分の気になったことをテーマにしました。
技術は楽しんで学ぶのが良いと思っています。
完全に趣味の話なので会社のAdvent Calendarのエントリーではあるけど個人のZennのページに載せることにしました。
抽選とは
ガチャガチャもくじ引きもそうですが、決められたグループの中から1つ取り出す抽選処理が発生します。
当たりくじを分かりやすい数にして図解すると以下の様なイメージです。
あたりの等級ごとに当たりの数が設定され、それらを一つの場所「くじ引きの箱」の中にまとめます。その中から1枚くじを引いて、引いたくじが何かで報酬が決まる仕組みです。
くじの箱の中はこのような状態でそれぞれの等級を表すくじが同じ箱の中にある状態です。
くじ引きの箱を配列に置き換え、抽選処理自体は乱数を使います。
PHPのコードに書き起こすとこんな感じです。
<?php
declare(strict_types=1);
$samples = [
'1等' => 1,
'2等' => 5,
'3等' => 20,
'はずれ' => 74,
];
$summation = array_sum($samples);
$lots = [];
foreach ($samples as $name => $count) {
echo sprintf("%s の確率: %4.3f%%\n", $name, ($count / $summation) * 100);
$lots = array_merge($lots, array_fill(0, $count, $name));
}
$random = random_int(0, count($lots) - 1);
echo ">> {$lots[$random]}\n";
1等 の確率: 1.000%
2等 の確率: 5.000%
3等 の確率: 20.000%
はずれ の確率: 74.000%
>> はずれ
パフォーマンスやメモリなどを意識せずシンプルな形で実装すると上記のコードになります。
このコードでは当たりのパターンを増やしたり、当たりの確率調整を行うと配列の要素数が増えてしまうため、メモリや処理速度に影響が出てきてしまいます。（たぶん
そこでググれば別のやり方が見つかるので、私のやり方と探して出て来た方法でどちらがパフォーマンスが良いか、気にする程でもないかどうかを見ていきたいと思います。
ちなみにググってみたところ「重み付き乱択アルゴリズム」というものだということがわかりました。
パターンごとの実装
色々手法はあるのですが、今回は自分のコードと累積和・二分木探索でパフォーマンスを試してみたいと思います。
累積和
<?php
declare(strict_types=1);
class CumulativeSummary {
private array $samples = [];
private array $cumulative = [];
private int $summation = 0;
public function __construct(array $samples) {
$this->samples = $samples;
$this->summation = array_sum($this->samples);
$cumulative = 0;
foreach ($this->samples as $name => $count) {
$cumulative += $count;
$this->cumulative[$name] = $cumulative;
echo sprintf("%s の確率: %4.3f%%\n", $name, ($count / $this->summation) * 100);
}
}
public function weightedRandomSelect(): string {
$random = random_int(0, $this->summation - 1);
foreach ($this->cumulative as $key => $max) {
if ($random < $max) {
return "{$key} (random: {$random})";
}
}
// フォールバック（通常到達しない）
return "エラー";
}
}
$samples = [
'1等' => 1,
'2等' => 5,
'3等' => 20,
'はずれ' => 74,
];
$cs = new CumulativeSummary($samples);
echo $cs->weightedRandomSelect() . PHP_EOL;
二分木探索
(※ChatGPTと相談しながら書きました)
<?php
declare(strict_types=1);
// ノードを表すクラス
class WeightedNode
{
public string $value;
public int $weight; // ノードの重み
public int $subtreeWeight; // 部分木の総重み
public ?WeightedNode $left;
public ?WeightedNode $right;
public function __construct(string $value, int $weight)
{
$this->value = $value;
$this->weight = $weight;
$this->subtreeWeight = $weight;
$this->left = null;
$this->right = null;
}
}
// 重み付け二分探索木クラス
class WeightedBinarySearchTree
{
private ?WeightedNode $root;
public function __construct()
{
$this->root = null;
}
// 値を挿入するメソッド
public function insert(string $value, int $weight): void
{
$this->root = $this->insertNode($this->root, $value, $weight);
}
private function insertNode(?WeightedNode $node, string $value, int $weight): WeightedNode
{
if ($node === null) {
return new WeightedNode($value, $weight);
}
if ($value < $node->value) {
$node->left = $this->insertNode($node->left, $value, $weight);
} elseif ($value > $node->value) {
$node->right = $this->insertNode($node->right, $value, $weight);
}
// 部分木の重みを更新
$node->subtreeWeight = $node->weight + $this->getSubtreeWeight($node->left) + $this->getSubtreeWeight($node->right);
return $node;
}
private function getSubtreeWeight(?WeightedNode $node): int
{
return $node ? $node->subtreeWeight : 0;
}
// 重みに基づいて乱択するメソッド
public function weightedRandomSelect(): ?string
{
if ($this->root === null) {
return null;
}
return $this->selectNode($this->root);
}
private function selectNode(WeightedNode $node): string
{
$leftWeight = $this->getSubtreeWeight($node->left);
$randomWeight = random_int(1, $node->subtreeWeight);
if ($randomWeight <= $leftWeight) {
// 左部分木にある
return $this->selectNode($node->left);
} elseif ($randomWeight <= $leftWeight + $node->weight) {
// 現在のノードを選択
return $node->value;
} else {
// 右部分木にある
return $this->selectNode($node->right);
}
}
}
$samples = [
'1等' => 1,
'2等' => 5,
'3等' => 20,
'はずれ' => 74,
];
$tree = new WeightedBinarySearchTree();
foreach($samples as $key => $value) {
$tree->insert($key, $value);
}
// 重みに基づいた乱択を10回試す
for ($i = 0; $i < 10; $i++) {
echo "Random Selection: " . $tree->weightedRandomSelect() . PHP_EOL;
}
期待した結果になるかどうか
以下の確率設定を元に100万回実行した際の抽選結果と、それを更に10回繰り返した実行時間の平均を出してみました。
| . | 確率 |
|---|---|
| 1等 | 1 % |
| 2等 | 5 % |
| 3等 | 20 % |
| はずれ | 74% |
| . | 配列を使った抽選 | 累積和 | 二分木探索 |
|---|---|---|---|
| 実行時間(ms) 平均 |
150.56943 | 198.17112 | 663.61962 |
| 1等 | 0.996 | 1 | 1.001 |
| 2等 | 5.003 | 5.008 | 4.997 |
| 3等 | 19.989 | 20.003 | 20.032 |
| はずれ | 74.013 | 73.99 | 73.969 |
確からしさ、という点ではどの手法でも問題なさそうです。
実行時間では差が出てしまいました。
コードを見ればループや条件分岐といった複雑性がシンプルに実行時間に影響が出てしまったようです。
結果パターンが5000種類の場合
結果の確からしさという点では差異がなさそうということなので、抽選の当選パターンを膨大な量にした場合にどうなるかを試してみます。
重みは1から順に5000までを配列に設定したものを利用します。
と、意気揚々に試そうとしたのですが私の最初提示したコードはメモリバッファオーバーフローになって計測不能になりました 🤮
計測できた累積和と二分木探索の結果はこちらです。
| . | 累積和(ms) | 二分木探索(ms) |
|---|---|---|
| 1回目 | 46270.556 | 3329.3309 |
| 2回目 | 45746.5689 | 3338.083 |
| 3回目 | 45670.4299 | 3415.107 |
| 4回目 | 46220.0491 | 3378.726 |
| 5回目 | 46515.6951 | 3348.9249 |
| 6回目 | 46776.7279 | 3373.0609 |
| 7回目 | 45862.1361 | 3352.4601 |
| 8回目 | 46160.2201 | 3326.112 |
| 9回目 | 45839.3762 | 3349.8931 |
| 10回目 | 45793.916 | 3329.143 |
| average | 46085.56753 | 3354.08409 |
先ほどとは逆に累積和にかなり時間がかかる反面、二分木探索の場合はそこまで大きく影響は出ませんでした。
極端な例ではありますが、普通に使うのであれば累積和で十分そうです。
Webサービスとして利用する場合二分木探索を利用するのはちょっと厳しそうです。
抽選の当選パターンを大量に用意するケースはあまりなさそうなので累積和がベターなのかな、という感想です。
今回試してみたコードはGitHub上にあげておいたので手元で試したり、もっと良い方法があるんじゃない？と試してみたい方はこちらを参考になさってください。
それでは良いクリスマスをお過ごしください〜〜。
Discussion