数学検証

[人狼確率論]m人の人狼のときの人狼が勝つ確率

ユキ
ユキ
どうも,ユキです。

今回は人狼が\(m\)人いる場合の、人狼チームが勝つ確率の求め方について解説をします。

なお予め,占い師,霊能者,騎士,ハンターなどの特殊な役職についておらず,全員ニート村人であるとして計算をしています。

\(n\)人村,\(m\)人狼のときの確率漸化式

結論からいうと,\(n\)人村,\(m\)人狼のときの人狼チームが勝つ確率を\(a_n\)としたとき,確率漸化式は次式で表されます。

 

$$a_{n,m}=\frac{n-1}{n+m-1}a_{n-2,m}+\frac{m}{n+m-1}a_{n-2,m-1}\tag{1}$$

 

ただし,\(a_{n\leq 2m,m}=1\) \(a_{n,0}=0\)

 

いきなり,確率漸化式を出されたので,戸惑うのも無理はありません。

本当にこの確率漸化式で,人狼が勝つ確率を求められるのだろうか?という人もいるかと思います。

ですので,実際に計算値を見せましょう。

データの出力・式の計算 練習問題皆さんこんばんにちは、ユウです。 今回の記事は、C言語のデータの出力と式の計算の練習問題となります。 データの出力と式の計算...

 

実際に計算

1人狼2人狼3人狼
6人村0.6250.9291.000
7人村0.4570.8000.963
9人村0.4060.7310.919
12人村0.4510.7560.918

 

一応念のために行っておきますが,9人村のときより,12人村のときの方が人狼が勝つ確率が高いですけれども,計算間違いしたわけではありません。なるべくしてそうなっただけです。

参考程度に前の記事です->

 

[人狼確率論]偶数村の方が人狼に有利であることを証明してみた 村の人口が偶数人の方が,人狼が勝つ確率は高い? ここでは人狼が1人の場合について考えています。前回の記事を読...

 

\(n\)人村,\(m\)人狼のときも,偶数人のときの方が人狼チームにとって有利に働くことがわかりますね。

ちなみに,\(m=1\)とすると,確率漸化式は

$$a_{n}=\frac{n-1}{n}a_{n-2}$$

 

\(a_{n \leq 2}=1\)

 

より,

 

\(n\)が奇数のときは,

 

\(a_{n}=\frac{(n-1)!!}{n!!}\)

 

\(n\)が偶数のときは,

 

\(a_{n}=2\frac{(n-1)!!}{n!!}\)

 

となり,前の記事で求めた,\(n\)人村,1人狼のときの人狼が勝つ確率と見事に一致します。

式の導き方

手順1:人狼ゲームは\(n\)人,\(m\)人から始めます。このとき,人狼チームが勝つ確率を\(a_{n,m}\)とします

 

昼のターンの確率について:

必ず1人は処刑される(\(n-1\)人となる)が,村人が処刑される(\(m\)のまま)場合と,人狼が1人処刑される(\(m-1\)となる)場合の2パターンが考えられます

ですので,人狼が勝つ確率をそれぞれ,\(a_{n-1,m}\)\(a_{n-1,m-1}\)とおきます

 

\(a_{n,m}\)から,\(a_{n-1,m}\)に移る確率を\(\alpha\)\(a_{n,m}\)から,\(a_{n-1,m-1}\)に移る確率は\(1-\alpha\)と書けるので,\(a_{n,m}\)は,

\(a_{n,m}=\alpha a_{n-1,m}+(1-\alpha)a_{n-1,m-1}\)

と書けます。

 

夜のターンの確率について:

夜のターンには人狼ではない人が必ず1人は捕食されるので,

\(a_{n-1,m}=a_{n-2,m}\)\(a_{n-1,m-1}=a_{n-2,m-1}\)

が成立します。先程の式に代入すれば,

\(a_{n,m}=\alpha a_{n-2,m}+(1-\alpha)a_{n-2,m-1}\)

となるので,昼のターンのみを考えることができます。

 

2019年版|Web制作フリーランスに薦める案件サイト3選今回は、Web制作のフリーランスが案件を受注する際のオススメサイトを紹介しています。特に初心者の方の場合は案件が上手く取れない、どのようにすれば良いの?といった風に悩んでいる方もいるかもしれません。ですので、そのような方のためにアドバイスなどを踏まえて紹介しています。...

 

\(n-m\)人の村人が処刑される確率\(\alpha\)

では,人狼が味方に投票しない場合\(n-m\)人の村人が処刑される確率\(\alpha\)を求めましょう。

 

もしかしたら,

「第1項の村人が処刑される確率は,\(\frac{n-m}{n}\)で,第2項の人狼が処刑される確率は\(\frac{m}{n}\)なのでは?」

とお考えになられる方がいらっしゃるのではないでしょうか。

 

その方法で式を導出しても良いですが,今回の人狼を求める公式は,人狼たちはお互いが人狼であることを知っているため,味方には投票しないだろうという仮定に基づいて計算して参ります

 

(1)プレイヤーが5人で2人狼のとき

図を見ながら計算しましょう

 

○は投票する可能性がある人,×は投票する可能性がない人

人狼1人狼2村人1村人2村人3
人狼1の投票先××
人狼2の投票先××
村人1の投票先×
村人2の投票先×
村人3の投票先×

 

ここで,1人の村人がつられる確率を\(x\)とし,1人の人狼がつられる確率を\(y\)とすると,

\((5-1):(5-2)=x:y\)

の比が成立するので,\(y\)は,\(x\)を使って表すと,

\(y=\frac{5-2}{5-1}x\)

と書けます。

また,昼のターンに必ず1人の人が処刑されるので,

 

\((5-2)x+2y=1\)

 

が成立します。

 

\((5-2)x+2\frac{5-2}{5-1}x=1\)   \(∵y=\frac{5-2}{5-1}x\)

 

\(x=\frac{1}{(5-2)(1+\frac{2}{5-1}})\)

 

\(x=\frac{5-1}{(5-2)(5+2-1)}\)

 

よって,\(5-2\)人の村人がつられる確率\(\alpha\)は,

 

\(\alpha=(5-2)x=\frac{5-1}{5+2-1}\)

 

\(\alpha\)の導出

(2)プレイヤーが9人で3人狼のとき

図を見ながら計算しましょう

○は投票する可能性がある人,×は投票する可能性がない人

人狼1人狼2人狼3村人1村人2村人3村人4村人5村人6
人狼1の投票先×××
人狼2の投票先×××
人狼3の投票先×××
村人1の投票先×
村人2の投票先×
村人3の投票先×
村人4の投票先×
村人5の投票先×
村人6の投票先×

 

ここで,1人の村人がつられる確率を\(x\)とし,1人の人狼がつられる確率を\(y\)とすると,

 

\((9-1):(9-3)=x:y\)

の比が成立するので,\(y\)は,\(x\)を使って表すと,

\(y=\frac{9-3}{9-1}x\)

と書けます。

また,昼のターンに必ず1人の人が処刑されるので,

 

\((9-3)x+3y=1\)

 

が成立します。

 

\((9-3)x+3\frac{9-3}{9-1}x=1\)   \(∵y=\frac{9-3}{9-1}x\)

 

\(x=\frac{1}{(9-3)(1+\frac{3}{9-1})}\)

 

\(x=\frac{9-1}{(9-3)(9+3-1)}\)

 

よって,\(9-3\)人の村人がつられる確率\(\alpha\)は,

 

\((9-3)x=\frac{9-1}{9+3-1}\)

 

 

(3)\(n\)人村で,\(m\)人狼のとき,村人が勝つ確率

 

いよいよ本題です。

 

○は投票する可能性がある人,×は投票する可能性がない人

人狼1\(\cdots\)人狼\(m\)村人1\(\cdots\)村人\(\cdots\)
人狼1の投票先×\(\cdots\)×\(\cdots\)
\(\vdots\)\(\vdots\)\(\ddots\)\(\vdots\)\(\vdots\)\(\ddots\)\(\cdots\)
人狼\(m\)の投票先×\(\cdots\)×\(\cdots\)
村人1の投票先\(\cdots\)×\(\cdots\)
\(\vdots\)\(\vdots\)\(\ddots\)\(\vdots\)\(\ddots\)\(\cdots\)
村人\(n-m\)の投票先\(\cdots\)\(\cdots\)×

 

ここで,1人の村人がつられる確率を\(x\)とし,1人の人狼がつられる確率を\(y\)とすると,

 

 

\((n-1):(n-m)=x:y\)

 

の比が成立するので,\(y\)は,\(x\)を使って表すと,

 

\(y=\frac{n-m}{n-1}x\)

 

と書けます。

また,昼のターンに必ず1人の人が処刑されるので,

 

\((n-m)x+my=1\)

 

が成立します。

 

\((n-m)x+m\frac{n-m}{n-1}x=1\)   \(∵y=\frac{n-m}{n-1}x\)

 

\(x=\frac{1}{(n-m)(1+\frac{m}{n-1})}\)

 

\(x=\frac{n-1}{(n-m)(n+m-1)}\)

 

よって,\(n-m\)人の村人がつられる確率\(\alpha\)は,

 

\(\alpha=(n-m)x=\frac{n-1}{n+m-1}\)

 

ちなみに,\(m\)人の人狼が処刑される確率\(1-\alpha\)

 

\(1-\alpha=1-\frac{n-1}{n+m-1}=\frac{m}{n+m-1}\)

 

となります。

 

よって,\(\alpha\)を式(1)に代入すると,

 

\(a_{n,m}=\frac{n-1}{n+m-1} a_{n-2,m}+\frac{m}{n+m-1}a_{n-2,m-1}\)

健康になるための心理学![基礎理論編]心と身体は密接に関係していて、「健全に精神は健全な肉体に宿る」とも言われますよね。健康になるための心理学である応用心理学が一種、健康心理学についての記事です。今回は基礎理論ですので、具体的な方法はありませんが理解していく中でためになるので、ぜひ読んでもらえると深まると思います。...

人狼ゲームの勝利条件を数式化

最後に2つのルールを数式化すると,人狼を求める公式が完成します。

・人狼が0人になると,人狼は必ず敗北する

・人狼の数\(\geq\)村人の数になると,人狼は必ず勝利する

を数式化すると,

\(a_{n,0}=0\)

\(a_{n \leq 2m,m}=1\)

となります。

関連記事

 

[無料公開]人狼ゲーム計算ツール人狼ゲームで勝つ確率を計算する為のツールです。人狼が複数匹いる場合の人狼チームが勝つ確率や、騎士がいる場合の人狼チームが勝つ確率などを計算します。...

 

最後に

ついに,\(n\)人村,\(m\)人狼のとき,人狼の勝つ確率を求める公式を導出することが出来ました。

今後の展望としては,

1 特殊な役職をフルオープンしたときの人狼が勝つ確率

2 占い師がCOする最適タイミング

3 魔女の毒殺や蘇生による,確率の変動

4 騎士を追加したときの人狼の勝つ確率

5 ハンターの発砲

などを求めていこうと思います。

人狼は様々な役職があり、奥が深いですね。

ちなみに私は人狼側になると,喋りすぎたり震えたりするので苦手なんですよね。

人狼ゲームは勝っても負けても楽しいです。

ABOUT ME
ユキ
ユキ
数学担当です。お金大好き大学生やってます。 講義がないときは、だいたい図書館にいるので図書館の門番とも呼ばれています。(呼ばれてない) L・O・V・E ラブリー マネー!