占い確定狩人生存ゲームでの村勝率の解析計算-1-

何も知らない僕の, たったひとつの冴えたやりかた-全てはダイスの女神様のお気に召すまま- - 12A猫で学んだこと-Memoir-

で, 指示役がいてもいなくても, AグレーBWなら, 狼を吊ることができる可能性を B/Aにすることができることが分かりました. この結果を使うと, ゲームの勝率解析が進みます.

"駆け引き"の発生する場面では, 均衡解を考えなければならないので難しいのですが, その駆け引きの要素を除外すると, 漸化式によって勝率の解析解を求めることができます. 
一番単純な例は以下でしょうか. 

n人生存, m匹狼生存, s人村人確定の場合の村勝率 - 12A猫で学んだこと-Memoir-

の例以外にもいくつか試してみたいと思います.
占い生存, 

<ゲームのルール>
占い1の真が確定している。 初日, 占い以外の生存人数はn人, 狼はその中でm匹. 狩人1人の生存が確定している. (狂人 - 霊能などはいない.)
 

占い師は, 毎晩, 占っていない人間から1人ランダムに占う. 狩人 - 占い - 村人を占う確率は同じ確率. 昼間は, 占い師が●を出したプレイヤーを吊る. それがいない時は, ○を出されていない狼候補からランダムに1人を吊る.
"ただし狩人はCOできない. また, 狩人は占いしか護衛できない."
狼は夜に2つの戦略を選ぶ. 占い師を噛むか, ○を出されている人間を噛むかの2択.
占い師を噛むことができる確率は, (最後に平和が出たときからの狩人候補の死亡数)/(最後に平和が出たときの狩人候補)の数とする. ○を出されている人間は, 確実に噛むことができる.

このケースでの, 村陣営の勝率を求めましょう. 

簡単の為に, まずは狼数が1の場合から考えましょう.
f(n,m,s)を 占い非生存の時に, 朝の地点で生存人数n, 残り狼数がm, 村確定人数sの時の村勝率とします.
g(n, m, s, h, H)を次の条件を満たすときの村勝率とします.
占い生存の時に, 朝にn人生存している.最後に平和が出た(= 占い師の生存が確定している)時の狩人候補者の人数がH人, H人から狩人候補がh人死んでいる.
朝の地点(占い師が結果をはる前の地点)でn人のうち, 村人確定はs人.
n人のうち, 狼の生存数はm. 

w(n, m, s, h, H)を次の条件を満たす時の村勝率とします. 
占い生存の時に, 夜にn人生存している. 最後に平和がでた(= 占い師の生存が確定している)時の狩人候補者の人数がH人, H人から狩人候補がh人死んでいる. 狼の生存数はm, 
s人が村人確定. 

<朝の段階での村人の行動> 

占いが狼を見つける確率

占いは村に○だし, その後に狼が釣れる確率

占いは村に○出し, その後に村人(狩人候補)が釣れる確率

以上を用いて, 

と記述できる. 
ただし, 

<狼の戦略について>

w(n, m, s, h, H)について考える.

狼は以下の戦略のうち, 村勝率が低い方を採用する. 

<占い噛みチャレンジ> 

* 占いが噛める場合, 村勝率 f(n,m,s) 

* 平和がでた場合, 村勝率g(n, m, s, 0, n-m). 

平和が出る確率は, h/H.

<○噛みで勝機を伺う> 村勝率 g(n-1, m, s-1, h+1, H) 

以上をまとめると, 

終端条件に気をつけて, これを再帰的に求めていけば, 村勝率を計算することができる. 

計算するプログラムをpythonで作成しました.   numpyが実行には必要です. 

占い確定狩人生存ゲームでの村勝率の解析計算-1-(ソースコード) - 12A猫で学んだこと-Memoir-

ミスがあったらごめんね. 再帰 + メモ化で単純に作っています.多項式時間で計算可能とはいえ, 大体nの五乗のオーダーなので, 数が大きくなると結構空間計算量も時間計算量も必要になりますね. 

この解析解の前提の, "狩人がCOできない"というルールは 

狼有利に働いています.  

g(4,1,0,0,3)の値にそれが出ています. 
狩人がCOできる"という前提では, これは確定村勝ちのゲームです. 
しかし, プログラムの結果では, 0.916667と算出されています. 
これは, 狩人がCOできないというルール上, 
占い師が村人に○を出し, 1/3で狩人が釣れて, 狼の占いチャレンジが成功し, 
最終日2択という道筋があるからです. 
狼勝率の確率は, 村人に○が出る確率 2/4 * 狩人が釣れる確率1/3 * (占いチャレンジ) * (最終日2択)1/2
この計算結果は, 1/12です. 狩人がCOできないことによって, 狼有利の結果となっています. 

幾つかの場合の計算結果を記載します. 
g(20, 4, 0, 0, 20 -4)村勝率0.389

g(16, 3, 0, 0, 16 - 3)村勝率0.555

g(10, 2, 0, 0, 10 -2)村勝率0.717

みたいな感じですね. 少人数村の方が, 狼視点厳しくなっていく感じでしょうか. 

『狩人がCOできる前提ではどうなの？ 』と考えると, 

『狩人がCOするかどうか？』という行動と『狼が狩人生存と予想するか？』ということに駆け引きが発生する i.e. (均衡解を考えなければならなくなる)ので, 厳密性を持った証明は難しくなります.  狩人COが無い時に, 狼が占いを噛める可能性を (最後に平和が出たときからの狩人候補の死亡数)/(最後に平和が出たときの狩人候補)の数になるという仮定をおいてしまえば, その問題は解決できるので, 気が向いたら, このケースだけは試してみようかなーと思っています. 今回の場合とどれだけ違うのかは少し気になります. 

『こんなこと計算して何になるの？』と言われたら全くおっしゃる通りで, 現在の人狼での勝率を高めたいと思っている人にはほとんど役に立たない情報です.
ただ...実際の村で, 占いを噛むタイミングをいつにするか? という戦略を決める為の１つの指針を狼陣営に与える結果にはなっていると思います. 

個人的には, そんな実際のことよりも, 神々のプレイヤー達が人狼を継続続けた場合, 
どの程度の確率になるかを予測する方に価値をおいています. 
そして, 貴方が『人狼の勝率を高めること』を目標にしている人の場合、
算出された結果以上の勝率を出すことは, 貴方の努力だけでは不可能です.