背景
程よく人狼の役職を決めるwebアプリを作ってみた、という話。
ここをクリック！ –> [人狼役職割り当てアプリ]
7名～12名位で盛り上がる人狼というカードゲームが流行っている。人狼２名(または3名)をカードでランダムに決めてゲームは始まる。残りは村人になる。
村人は人狼が誰かを推理して処刑すれば勝ち、人狼は村人のふりをしながら夜な夜な村人を殺し、村人の人数を人狼と同数まで減らせば勝ちという、心理戦ゲーム。例えば、Board Game to Life さんのサイトでルールを見てみて。
すごく面白くて僕もはまっているんだけど、役の決め方にちょっと不満がある。大抵、同じメンバーで何度も繰り返して遊ぶんだけど、1回は人狼をやりたいし、村人にも、占い師やボディーガードなどの役職があって、色々やってみたい。
でも、毎回完全にランダムで役職を決めるので、そうもいかない。1度も人狼に当たらなかったということもしょっちゅうある。ランダムって結構かたよるんだよね。
1度も人狼に当たらない人が出る確率というのをちゃんと計算してみよう。単純な場合として、プレイヤーは4人でその中から人狼を１人ランダムで決めるとする。そして、これを４ゲーム繰り返すとしよう。
直感的に考えれば、人狼になる確率は1/4 なので、4ゲームやれば平均で1人1回は人狼が当たるはずなんだけど。。1回のゲームで4人の中から1人の人狼を割り当てるパターンは4通りなので、4回のゲームでの割り当ての場合の数Aは、
[math]
A = 4\times 4 \times 4 \times 4
[/math]
4人全員に人狼が割り当てられる場合の数Bは、
[math]
B = 4\times 3 \times 2 \times 1
[/math]
4人全員に人狼が割り当てられる確率[math]P_{all}[/math]は、
[math]
\begin{eqnarray}
P_{all} &=& \frac{b}{a} \\
&=& \frac{4\times 3 \times 2 \times 1}{4\times 4 \times 4 \times 4}
\end{eqnarray}
[/math]
よって、1度も人狼に当たらない人が出る確率[math]P_{none}[/math] は、
[math]
\begin{eqnarray}
P_{none} &=& 1- P_{all} \\
&=& 1- \frac{4\times 3 \times 2 \times 1}{4\times 4 \times 4 \times 4} \\
&\simeq & 0.906
\end{eqnarray}
[/math]
となる。なんと、10回に9回も、誰かは一度も人狼をやれないということになるのだ！
ではゲーム数を6回に増やしたらどうか。さすがに6回ほどゲームをすれば、みんな1回は当たるだろうと思いきや、
[math]
\begin{eqnarray}
P_{none} &=& 1 – \frac{{}_6 C_4 \times 4! \times 4^2}{4^6} \\
&\simeq & 0.297
\end{eqnarray}
[/math]
となり、約30%の確率で1度も人狼しなかったという人が現れる。
望まれるアルゴリズムの仕様
どうやったらみんなが人狼できるように割り当てられるだろう。すぐに思いつくアルゴリズムは、参加者の中で人狼をやった回数が最も少ない人に人狼を割り当てるという方法だ。該当者が何人かいたらその中でランダムに決めればいい。
しかしこれだと明らかな問題がある。例えば3回ゲームをして、人狼をやっていない人が１人の場合、次のゲームでその人が人狼になることが分かってしまう。これじぁ、ゲームにならない。
つまり、完全に決定論的な要素があってはだめで、ランダムな要素は入れつつ、いいあんばいで、やっていない役になる確率を上げるということが必要なのだ。
例えば、過去の3回のゲーム（履歴）が、
1000 （1回目、参加者1が人狼）
0100 （2回目、参加者2が人狼）
1000 （1回目、参加者1が人狼）
だったとしたら、4回目では1000の確率がいちばん小さく、次に0100、そして、0010、0001は確率が一番高い高いようにしたい、ということだ。
ペナルティー（エネルギー）の定義
そこで、「候補のパターンが、これまでの履歴と何個重なっているか」をペナルティーとして定義しよう。
例えば、さっきの履歴
1000
0100
1000
に対して候補1000 (パターン番号0としよう)のペナルティーE(i)は以下のように計算する。
候補の1番目の1は、履歴の1列目に2個ある
候補の2番目は0で、履歴の2列目に2個ある
候補の3番目は0で、履歴の3列目に3個ある
候補の4番目は0で、履歴の3列目に3個ある
合計 2+2+3+3=10
よって0番目のパターン1000 のペナルティEは、
[math]
E(0)=10
[/math]
とする。この方法ですべての候補パターンの計算をすると、以下のようになる。
[math]
0100 に対して、E(1)=8
[/math]
[math]
0010 に対して、E(2)=6
[/math]
[math]
0001 に対して、E(3)=6
[/math]
これをエネルギーだと考えて、低いエネルギー状態ほど確率的にとりやすいというボルツマン分布をで表現しよう。まず、規格化されていない確率（足して1にならない）[math]q(i)[/math]を定義する。
[math]
q(i) =\exp (-\beta E(i)) \tag{1.1}
[/math]
ここで、[math]β[/math]は逆温度と呼ばれるパラメーターで、値が大きければ大きいほど、エネルギー(つまり、ペナルティー)の高い状態をとる確率が小さくなる。
そして、[math]q(i)[/math]のすべての和[math]Z[/math]を定義する。
[math]
Z= \sum_{i=0}^3 q(i) \tag{1.2}
[/math]
[math]q(i)[/math]を[math]Z[/math]で割れば、規格化された確率分布[math]p(i)[/math]が求まる。
[math]
p(i)=q(i) / Z \tag{1.3}
[/math]
[math]β=1[/math]として具体的に計算すると、
[math]
p(0)=0.027 \\
p(1)=0.1081 \\
p(2)=0.4324 \\
p(3)=0.4324
[/math]
となる。想定通り、[math]p(0)[/math]が一番小さく、[math]p(2)[/math]と[math]p(3)[/math]が一番大きい確率となった。[math]p(i)[/math]をベクトル[math]{\bf p}[/math]であらわすと、
[math]
{\bf p}=[0.027, 0.1081, 0.4324, 0.4324]
[/math]
だ。
規格化された確率分布ができれば、0から1の一様分布を使って、パターンをサンプリングすることができる。
アルゴリズムの拡張
さて、この方法なら、役職が増えてもその人が過去に何回その役職をやったかを数えるだけでペナルティーは計算できるので、拡張しやすい。
例えば実際にやるような人数と役職だと、11人で人狼3人、占い師1人、騎士1人、霊媒師1人、村人5人、などとなるが、それぞれの役職を、1, 2, 3, 4, 0 で表すとして、履歴
11123400000
11234000001
に対する、
12340000011
のペナルティーは、2+0+0+0+0+1+2+2+2+0+1 = 10 と計算できる。
アルゴリズムの問題点
でも、この方法、ひとつ問題がある。人数や役職が増えると、とりうるパターンの数がどんどん増えてしまう。さっきの、11123400000のとりうるパターンを計算してみると、
[math]
{}_{11} C_3 \times 8 \times 7 \times 6 = 55400
[/math]
と、55400通りもある。これは、[math]Z[/math]を計算するとき、この分だけ[math]q(i)[/math]を計算して、和を求めないといけないということだ。人狼は15人くらいでもやることはあるので、そうなるとこの方法はもっときつくなる。
[math]Z[/math]の計算をせずに、直接[math]q(i)[/math]からパターンをサンプリングできるといいのだが。。そこで、メトロポリスヘイスティングス法の出番となる。
(つづく）