日本ソフトウェア科学会第 34 回大会 (2017 年度) 講演論文集

進化シミュレーションを用いた３人人狼の分析
大澤 博隆

汪 博豪

佐藤 健

本研究では、不完全情報ゲームであり、正体隠匿型ゲームに分類されるコミュニケーションゲーム人狼を用い、人狼ゲームの最小系である 3 人人狼を考え、どのような戦略がありうるか検討した。検討のため、ゲームのモデル化を行った後、このゲームの発展について、進化シミュレーションの手法を用いて検討した。シミュレーション結果より、
人狼ゲームにおいてプレイヤーが嘘をつく状況が一時的に支配的になるものの、安定解が存在しないことを確かめたは多人数ゲームだが、前項の条件から、2 人ではゲー1 はじめにムが成立しないため、最少人数は 3 人となる。

様々なゲーム課題がプログラムによって解かれつつ本研究では人狼ゲームの最小系である 3 人人狼をあり、人間より強いプログラムが登場しつつある。完

考え、どのような戦略がありうるか検討する。本研究

全情報ゲームの中で最も難しい課題と言われていたでは、以前の研究成果である３人人狼における発話の囲碁に関しても、実質的に人間より強いプログラムがモデル [6] を元にして、進化シミュレーションの手法できつつある [3]。また、不完全情報ゲームの中でメを使い、どのように３人人狼の系が発展しうるか検討ジャーな問題であるポーカーについても、投資に制限した。のある条件では理論解が導き出されている [2]。
こうした動きの中、次に解くべき課題として注目さ2 ３人人狼の定義れているのが、不完全情報ゲームであり、かつ相手の2. 1 人狼ゲームとは何か利得条件が隠されている中で最適手を探る人狼ゲーム

人狼ゲームはスパイ発見ゲームの一種である。各である [8]。人狼ゲームは、プレイヤー同士の情報が隠プレイヤーは村人陣営と人狼陣営に分かれてプレイされている不完全情報ゲームであり、その中でも相手を行う。村人陣営はすべての人狼を追放することを目が協調するプレイヤーか、敵対するプレイヤーかがわ指し、人狼陣営は村人陣営のプレイヤーを襲撃するからない、という正体隠匿系のゲームに属している。

ことで数を減らしていく。最終的に以下の勝利条件をまた、コミュニケーションが全て自然言語で行われて満たした陣営が勝利となる。人狼ゲームにおける村おり、正体や戦略含めた多彩なやりとりがプレイヤー人陣営、人狼陣営にはいくつかの特殊能力をもつ役間で行われるのが特徴である。人狼ゲームの理論的分職が存在する。この中で、最も基本となる役職は、夜析 [1] [5] [7] や、オンライン人狼ゲームの勝敗データをのフェーズに誰が人狼であるかを見分ける占い師で元にした統計的分析 [4] が行われている。人狼ゲーム

ある。

Analysis of Three Player’s Werewolf Game with Evolutionary Computation
Hirotaka Osawa, Bohao Wang, 筑波大学, University ofTsukuba.
Ken Satoh, 国立情報学研究所, National Institute ofInformatics.

人狼ゲームは昼と夜のフェーズが交互に進むゲームである。昼のフェーズでは対話と追放対象の多数決投票による決定、夜のフェーズでは狼の襲撃先の決定や、占い師の占い先の決定が行われる。人狼が居なくなった場合に村人陣営が勝利となり、人狼の数が人間と同数以上になった場合に、人狼陣営が勝利する。

投票先が占い師で、かつ村人の投票が占い師とならない限り、人狼勝利とはならない。これ以外の場合、

2. 2 ３人人狼ゲーム投票結果は引き分けとなる。

上記人狼ゲームを最も単純化したルールが、3 人人狼ゲームである。人狼ゲームはその性質上、2 人では3 3 人人狼の定式化遊べない。人狼ゲームにおけるプレイヤー中かならず

3. 1 ゲーム状態の定義

1 人は人狼であるため、2 人で始めた場合、どちらにプレイヤーが 3 人いたとき、3 人人狼における役職とっても人狼の位置が自明となる。かつ、人狼が過半の組み合わせは 6 通り存在する。しかしながら、ある数を占めた時点で人狼陣営勝利となるため、ゲーム村側陣営から見た時の役職の可能性は、右手に狼がいが開始しない。よって、もっとも少人数のゲームは 3るか、左手に狼がいるかの 2 通りであり、これは人狼人で行われることになる。

陣営から見ても一緒である。つまり、どのプレイヤー

3 人人狼の場合、処刑が一回行われるとゲームが終も自分の役職は決定しているため、各プレイヤーの信了するため、上記で説明した夜のフェーズが存在しな念中に存在する役職の可能世界は、2 通りということい。投票が同数になった場合、人狼ゲームは再投票やになる。本研究では、村人側から数えて時計回りに村ランダム投票などの仕組みを用いて投票先を決定し、人、占い師、人狼となる場合を D0、村人、人狼、占村人陣営か人狼陣営の勝利を決定する。しかしながい師となる場合を D1 と呼ぶ。

ら、本研究では簡易化のため、全員が同数投票（3 人

なお、占い師はゲーム開始前に、自分の村が D0 も人狼では各自１票ずつ投票）された場合、引き分けとしくは D1 のどちらのセットで開始されているかを伝して扱う。

えられる。したがって、占い師の可能世界は 1 通りし

3 人人狼で最もシンプルな形式は、村人 2 人と人狼かない1 人による組み合わせである。ただしこの場合、事前に情報が手に入らないため、村人側が会話によって人

3. 2 会話のない状況の定義

狼の場所の情報を得ることができず、そのことが全員会話のある状況を前提とする前に、会話のない状況に共有されている。よって、情報交換や、その情報交を考える。会話のない状況での人狼ゲームでは、村人換をかき乱すような偽装の利点がなく、本研究で扱いはどちらが狼であるか、という情報を持たない。従ったいような知的課題として適さない。て、 村人はどちらも選択することができ、追放先はそのため本研究では、村人の一人を占い師とし、占占い師もしくは狼側となる。また、人狼は情報を得るい師に事前にどちらが狼であるかの情報を与えてゲーことができないため、占い師と村人の判定ができなムを開始するゲームを 3 人人狼と定義する。本研究い。従って、こちらも選択肢は削減できず、両方に投で仮定する３人人狼ゲームでは、村人および占い師票する場合がありえる。以上より、状態の場合分けのが村人陣営となり、人狼が人狼陣営となる。占い師は結果は表 1 のとおりとなる。

村人陣営であり、かつ、誰が人狼であるかをゲーム開
表1始前に知っている。そのため、いかなる状況であっても、占い師の追放先は人狼であることが最適手となる。従って、本研究で問題となるのは村人、人狼の投票先であり、それがどのように変化するかである。村
人側は人狼に投票を２票集めればよいため、村人の選択が人狼投票になる場合に村人側はかならず勝利する。人狼側は自分以外の誰かに２票集めれば勝利する。自分自身に投票できる人間はいないため、人狼の会話のない状況の分類

村人投票先

人狼投票先

結果

人狼

占い師

村側勝利

人狼

村人

村側勝利

占い師

占い師

狼側勝利

占い師

村人

引き分け

3. 3 会話のある状況の定義を目指すのが最善手となる。人狼プレイヤーに関し

人狼ゲームにおける最も難しい要素が、会話の定義ては、村側陣営を追放するのが最善手となる。この場である。人狼ゲームではプレイヤーの現在の状態だけ合、村人、占い師の両方に投票する手段がありえるでなく、未来や過去の進行についても記述が可能であが、占い師が必ず人狼に投票する条件である場合、人る。したがって例えば、「これ以降２人のプレイヤー狼が村人に投票した時点で、村人の投票先が人狼でが 今日の晩飯は牛丼である といった場合に私は左あれば人狼の負け、村人の投票先が占い師であれば引側のプレイヤーに投票する」といった、今後の行動をき分けとなり、勝利する可能性がなくなる。したがっ含めた記述が可能である。原理的には、自然言語で可て、勝利を目指す人狼の最善手は、自分の信念の中で能な表現は全て可能であり、自由度を制約して考える占い師と目される人物へ投票し、村人と投票を合わのは難しい。

せ、追放を狙うことである。

しかしながら、会話をいくつかの種類に分類することは可能である。本研究では、会話を以下の種類に分類した

1. ゲームに関係のない発話「今夜の晩飯は牛丼である」

2. ゲームに関係があるが、ルールに沿わない会話「この村に人狼はいない」

3. 現状の記述

3. 5 初期プレイヤーの手順
占い師にとって、他のプレイヤーの会話から新しく得られる情報はない。一方で、村人、人狼プレイヤーにとって、他のプレイヤーの会話から、ある程度合理的な手が導き出せる。我々は以前の研究より、全てのプレイヤーが引き分けではなく勝利を目指す場合に、合理的な手があることを求めている [6]。これより、村「私は占い師であり、プレイヤー X を占った結人、人狼の双方が会話を受けた時の手を表 2, 表 3 に果、人狼であった」

示す。

4. 進行の記述
表2「私はプレイヤー X に投票する」

5. 過去の自分の状態に関する記述「私はプレイヤー X に投票した」
本研究では、上記のうち 3 の記述のみを扱う。本研
究で扱う会話形式は、以下の 3 通りである。

1. 「私は村人である」

P1’s talk
P1
P2P0
VS
VW
S
W
VVS
VW
SW
VV
S
V
W
SW
V

村人の初期手

P2’s talk
P2
P0
P1VV
V
S
V
W
S
V
W
S
V
W
S
W
V
S
W
V
S
W
V

P0’s next
P1
P2

DP01011V
V
V
VW
S
W
W

S
W
S
S

0V

S

W

0V

S

W

2. 「私は占い師であり、左のプレイヤーが人狼であった」
表3

3. 「私は占い師であり、右のプレイヤーが人狼であった」
発言 2 は状態が D0 に属することを示しており、発言 3 は状態が D1 に属することを示している。

3. 4 各プレイヤーの投票先

P1’s talk
P1
P2
P0
V
S
V
W
S
W
V
V
S
V
W
S
W
V
V
S
V
W
S
W
V

狼の初期手

P2’s talk
P2P0
P1
V
V
S
W
S
S
S
S
S
S

V
V
V
W
WWWWW
VVV

P0’s next
P1
P2

DP01W

SV1WSV0W

VS0WVS

各プレイヤーは自身の持つ可能世界に従って投票行動を行う。占い師は事実を知っているため、投票行動・投票先は常に人狼とするのが最も最適な手とな4 シミュレーションの手続きる。また、村側陣営である村人の投票も、自分の信念各プレイヤーが合理的な手から出発し、どのように中で人狼であるプレイヤーに投票し、追放すること発展するかを、進化シミュレーションを用いて求めた。

手続きを図 1 に示す。各プレイヤーはまず、自身の内割合で展開するものの、占い師が徐々に嘘をつくよう部状態からはツン現内容を決定する (genecode1)。入になる。それに伴い村人側の勝率が上がるが、ある点力となる内部状態は 2 種類であり、発言は 4 種類であから勝率が減少し、50%へ近づいていく。100 サンプ

る。次に、各プレイヤーは他のプレイヤーの 2 つの発ルのどの条件でも、100 世代までの序盤に同じような言から、自身の内部状態を更新する (genecode2)。他推移を行うことを確認した。

プレイヤーの各発言は 4 通りであるため、genecode2の入力は 16 種類、更新する内部状態は 2 種類となる。

5. 1 考察
結果より、当初予想していたのと異なる結果がもたらされた。以下にその要件を述べる。
占い師が嘘をつくようになった理由として、占い師であることの宣言で村人にとっては情報が十分に伝わり、占い結果を述べることで、狼側からかえって正体がわかりやすくなってしまう、という圧力が会ったことが考えられる。本来は占い師が正直に結果を述べるのが合理的であると判断し、シミュレーションを開始した。しかしどのシミュレーション条件であっても、

図1

進化シミュレーションのプロセス

占い師の結果はおよそ半数以上が嘘を含む形に進化した。

村人、占い師、人狼の各エージェントを 10 体用意

また、引き分けの条件があまり存在せず、村人陣営し、これを 1500 世代に渡って進化させた。各世代にと人間陣営が半数ずつ勝つ場合と、村人陣営が大きくおいて、エージェントはランダムで 1000 試合を行う。

勝つ場合に二分されることがわかった。会話のない条

試合後、勝敗の数、嘘をついた数、占い師として CO

件と異なり、進化的な条件下では、村人が半数勝ち、した数の集計を行う。村人プレイヤーは、村人でない1/4 で人狼が勝ち、1/4 で引き分ける、という条件がと宣言した時に嘘をついたと判断し、占い師プレイ安定解でない可能性が考えられる。

ヤーは村人として宣言した時および偽の占い結果を述べた時に嘘と判断する。発話の制約上、人狼プレイ

6 結論

ヤーは常に嘘をつくしかできないため、人狼プレイ

本研究では３人人狼ゲームのモデル化を行った後、ヤーの場合には占い師として発言した数を集計した。

このゲームの発展について、進化シミュレーションの各役について勝率を求め、最も勝率が低いエージェ手法を用いて検討した。検討結果より、人狼ゲームにントを消去し、次に、最も成績が高いエージェントおいてプレイヤーが嘘をつく状況が一時支配的になと、2 番めに成績が高いエージェント同士をかけ合わるものの、安定解が存在しないことを確かめた。

せ、新しいエージェントを作る交叉を行う。最後に、今後は、会話が繰り返される状況、再帰的に相手の10%の確率で、各コードの状態を変化させる突然変異状態を持つ状況を進化的シミュレーションにより検討を行う。本シミュレーションを 100 回行った。

し、再帰的な推論がどのようにゲームに貢献しているか、検討する予定である。

5 シミュレーション結果
シミュレーションの実行結果のうち 1 つを図 2 に示す。各プレイヤーの状態が収束せず、定常状態とそうでない状態を繰り返していることがわかる。
初期状態においては、会話のない人狼ゲームと同じ

謝辞 本研究は JSPS 科研費 26118006 および人工知能財団の助成を受けたものです。

図21500 世代における村、占、狼エージェントの勝率と嘘、CO の割合（背景の下部が村側の勝率、上部が狼側の勝率、間の区域が引き分けの率となる）

参 考 文 献[1] Braverman, M., Etesami, O., and Mossel, E.:
Mafia: A theoretical study of players and coalitions
in a partial information environment, The Annals ofApplied Probability, Vol. 18, No. 3(2008), pp. 825–846.
[2] Michael Bowling, Neil Burch, Michael Johanson,
and Oskari Tammelin: Heads-up limit hold ’ em
poker is solved, Science, Vol. 347, No. 6218(2015),
pp. 145–149.
[3] Silver, D., Huang, A., Maddison, C. J., Guez,A., Sifre, L., van den Driessche, G., Schrittwieser,J., Antonoglou, I., Panneershelvam, V., Lanctot,M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach,M., Kavukcuoglu, K., Graepel, T., and Hassabis,D.: Mastering the game of Go with deep neural networks and tree search, Nature, Vol. 529,No. 7587(2016), pp. 484–489.
[4] 稲葉通将, 鳥海不二夫, 高橋健一: 人狼ゲームデータの統計的分析, ゲームプログラミングワークショップ 2012
論文集, Vol. 2012, No. 6(2012), pp. 144–147.
[5] 西野順二: 自然な人狼の勝率, 研究報告ゲーム情報学（GI）, Vol. 2015, No. 18(2015), pp. 1–5.
[6] 大澤博隆, 佐藤健: ３者間人狼における戦略の検討, 人工知能学会全国大会, 2016, pp. 2F4–3.
[7] 畢暁恒, 田中哲朗: 対話のない人狼ゲームの戦略,ゲームプログラミングワークショップ 2015 論文集,Vol. 2015(2015), pp. 25–30.
[8] 片上大輔, 鳥海不二夫, 大澤博隆, 稲葉通将, 篠田孝祐, 松原仁: 人狼知能プロジェクト, 人工知能学会誌,
Vol. 30, No. 1(2015), pp. 65–73.