# 進化論的アプローチによる 人狼ゲームにおけるエージェントの構築に関する調査

関井郁弥
横浜国立大学
sekii@forest.eis.ynu.ac.jp
}

阪本浩太郎
横浜国立大学
sakamoto@forest.eis.ynu.ac.jp
}

渋木英潔
国立情報学研究所
shib@nii.ac.jp
}

森辰則
横浜国立大学
mori@forest.eis.ynu.ac.jp

## 1 はじめに

近年，スマートスピーカーの普及によってコン ピュータとの対話が身近なものとなり，今後は情報検索や家電操作以外にも対話技術が応用されてい くことが予想される. 情報検索や家電操作などでは ユーザの指示に忠実に従うだけで問題ないが，例え ば，商品セールスなどに応用することを考えると， ユーザが当初目的としていなかった商品を売り込む といったユーザの意思決定に大きく影響を与える対話が求められることになる. 我々は，ユーザの意思決定に大きく影響を与える対話を翻意誘導対話と定義する。しかしながら，翻意誘導対話をどのように 実現するかに関する研究はほとんどない. 我々は,自分の目的を達成するために相手の意思決定に影響 を与えるという点で説得も欺瞒も翻意誘導対話の一種1) と考えている。そこで，ゲームにおける勝敗の ように目的が明確であり，かつ，その目的を対話に よって達成するものが，翻意誘導対話の対象として 適切であると考え，人狼ゲームを対象として研究に 取り組むこととした。

人狼ゲームとは，対話を通して「村人」の中に潜伏した「人狼」を見つけ出す対戦型の多人数ゲーム であり2)，近年，人狼知能プロジェクト3)など研究 テーマとしても注目されている. 人狼知能プロジェ クトでは，「人間と自然なコミュニケーションを取 りながら人狼をプレイするエージェント（AI）の構築」を究極の目標としており，エージェント同士の 対戦成績を一つの指標として人工知能の研究開発に 取り組んでいる.また，我々は，これまで人狼ゲーム プラットフォーム LiCOS[1] の開発や人狼エージェ ントの分析 [2]などに取り組んでいる。人狼ゲーム は意思決定の際に相手がどのような行動をとるか分 からない不完全情報ゲームであり，推論に誤謬がな くとも正解を導き出せるとは限らず，ゲーム中の行動が必ずしも論理的に説明できるわけではない。そ のため，エージェントの発話が翻意誘導できたかを 評価するためには，何度もゲームを繰り返して定量的に見積もる必要があり，模索段階で人間を相手に


ゲームを行うことは効率的でない。また，翻意誘導 された過程を調査する上でも，思考過程が透明であ るエージェントを対象とすることが望ましい，以上 の背景から，我々は人狼ゲームにおける翻意誘導の 対象となるエージェントの構築に取り組む. 将来的 に他のプレイヤの発言の理解や，自然言語を用いた 発話といった対話機能を含めた推理・発言の機能を 持つエージェントの構築を検討する。人間の思考過程を模した構築したエージェント相手への翻意誘導 を観察し，人間に対しても同様に翻意誘導ができる かの検証につながる情報を得ることを期待する。

翻意誘導の対象となるエージェントは，誘導され うる知性を備えつつ，エージェントごとにある程度 の多様性があることが望ましい，そのようなエー ジェントを構築する手段として，我々は進化論的ア プローチをとることとした. 人狼ゲームと同じ不完全情報ゲームである繰り返し囚人のジレンマにおい て進化論的アプローチにより最適戦略を求める研究は多くなされている $[3,4,5,6,7]$. しかしながら， ゲームの複雑さが異なるため，そのまま人狼ゲーム に応用できるか自明ではない。それゆえ，本稿で は，進化論的アプローチによるエージェント構築に 関する設計を行う。

## 2 エージェントの設計

エージェントの思考過程を明示的に表現するた めには，エージェントがそれぞれ対戦相手の他エー ジェントの役職をどのように推理しているかという 認識を表現する必要がある. エージェントの多層的 な認識 (例:「エージェント Cは『エージェント Aが エージェント B の役職を村人だと思っている』と認識している」など）という思考を可視化して表現す るために，エージェントがそれぞれ自身の思考を行 う思考空間（メンタルスペース）と，参加している 各プレイヤに対応しメンタルスペース内に存在する 仮想上のエージェント（メンタルエージェント）を 所有しているモデルを導入する。

エージェントの動作は，他のプレイヤからの発言 を受けてエージェントがゲーム状況を把握するため のメンタルスペースの更新と，ゲームを進行させる ためメンタルスペースに対応した発話や投票を行う といった行動の 2 つからなる。

図 1 メンタルスペースの構造

## 2.1 メンタルスペースの構造

図 1 にメンタルスペースの構造を示す。メンタル エージェント内には，そのエージェントが各エー ジェントの役職をどのように認識しているかとい うキャラクタと役職を対応させた表（対応表）を持 つ. 対応表は，プレイヤと役職の表があり，対応は プレイヤがそれぞれの役職である確率 $[0,1]$ として 表される。 エージェントのメンタルスペース内のメ ンタルエージェント 1 人につき， 15 人のプレイヤご とに 6つの役職それぞれの確率の対応表を所有して いることで，「エージェント C は『エージェント A がエージェント B の役職を人狼だと思っている』と 認識している」などという複雑な認識を扱うことが できる.

また，エージェントはたとえ同じ内容の発言で あっても発言者が異なる場合に，その発言の信用具合が変化することが考えられる. エージェント毎の 信用具合の差を表すために，それぞれのメンタル エージェントには各プレイヤの発言をどれほど信用 するかという指標となる信頼度を所有させる．信頼度は各エージェントの発言を信用している度合い $[0,1]$ として表される. 信頼度が高いプレイヤからの 発言は対応表に大きな影響を与え，反対に低いプレ イヤからの発言は対応表に影響しにくくなる. 信頼度も対応表と同様に，メンタルスペース内のメンタ ルエージェント 1 人につき， 15 人のプレイヤ全員へ の信頼度を所有させる。

誰に投票するか，人狼のプレイヤが誰に襲撃する か, 占い師や狩人のプレイヤの能力の使用先を誰に するか，などのゲーム内での意思決定を含む行動を 説明可能にするために，メンタルエージェントには これらの各種意思決定の際に用いる投票意思, 占い 意思，護衛意思，襲撃意思という意思値を所有させ る. 意思値は，あるプレイヤに対して投票，人狼の 襲撃，占い師の占い，狩人の護衛といった行動をし ようという意思の強さ表した値で，基本的に意思値 が最も高いプレイヤに対して投票・襲撃といった各種行動を試みる。各種意思値はメンタルエージェン
トごとに 1 つずつ所有しており，対応表や信頼度の 数值によって変動するほか，CO（カミングアウト：自らの役職を宣言する）などの発言内容にも応じて 変化させる。

対応表，信頼度，各種意思値といった値は，「占い 師 CO をがされたとき，発言者が占い師かもしれな いと考える」「発言内容に矛盾が生じたとき，その発言者が人狼であると疑う」などといった，理性的な プレイヤが人狼ゲームをプレイする際に用いるルー ルに従って変化する。これらを変化させる際に，そ れぞれのルールの持つ影響力の指標として，各エー ジェントにパラメータを持たせる。，パラメータはそ れぞれ村人陣営の役職のときに強く発現するパラ メータ，人狼陣営のときに強く発現するパラメー タ，陣営にかかわらず発現するパラメータの 3 種類 が存在する。表 1 にエージェントの持つパラメータ の一部を記載する。実際のエージェントの構築では このようなパラメータを多数使用するが，ここでは 一部のみ抜粋する。このパラメータの組み合わせに より，エージェントの個性となる推理方法や発言な どの行動が変化する. 本研究では，このパラメータ を遺伝的アルゴリズムにおける学習対象の遺伝子と し，この数値を最適化することによって理性的に推理を行い，行動するエージェントの構成を試みる。

## 2.2 意思決定

エージェントは発言を要求されるたびに，

1. 役職が占い師，霊能者でそのゲーム中にまだ COしていなければ $\mathrm{CO}$ 発言

2. 占い師, 霊能者のときは能力の使用結果を公表

3. 一番投票してほしいエージェント（投票意思が 最も高いプレイヤ）へ投票するように希望する 発言

4. 今自分が誰を人狼だと思っているかなどの役職考察発言

の優先度で発言を行う。このアルゴリズムは第 2 回人狼知能大会のチーム饂飩の発話アルゴリズム [8] を参考にした。

また，エージェントは投票を要求されるたびに，
表 1 エージェントの構築に用いるパラメータ例

 &  & {$[0,1]$} & 土通 \\

表 2 試合ごとに加算される得点

生存している自分以外のプレイヤの中で最も投票意思が高いプレイヤへの投票を行う. 人狼のエージェ ントは. 襲撃先の投票が要求されるたびに，エー ジェントは生存している人狼でないプレイヤの中で 最も襲撃意思の高いプレイヤへ投票を行う.

## 3 エージェント構築の環境

翻意誘導される上で知性を持ったエージェントで ありながら，異なる個性をもったエージェントが多数得られることを期待し，並列分散型遺伝的アルゴ リズム [9](並列分散 GA) によってエージェントを構築する。エージェントの個体が持つパラメータの集 まりを遺伝子としており，人狼ゲームをプレイする 上で最適な遺伝子パラメータの組み合わせを学習す ることを目的とする。

個体の遺伝子に多様性を持たせるために村を $N_{\text {village }}$ 個用意する.また. 勝敗に運要素が絡むた め，信頼できる勝率を得るためにそれぞれの村で $N_{\text {game }}$ 回ずつ対戦を行う.

適者生存を示すスコアは村人陣営としてのスコア と人狼陣営としてのスコアの 2 種類を用意し，役職 が村人陣営（村人, 占い師, 霊能者, 狩人) で参加し た対戦での結果を村人陣営としてのスコア，人狼陣営（人狼，狂人）の役職で参加した対戦での結果を 人狼陣営のスコアとして計算することで，村人とし て優秀な個体，人狼として優秀な個体を判別する。村人陣営，人狼陣営はそれぞれ試合ごとに表 2 の点数を加算する. ここで，得点 $P_{V 1}$ と $P_{V 2}, P_{W 1}$ と $P_{W 2}$ については, 各プレイヤは自身の陣営の勝利を 何より優先させるべきという考えから， $P_{V 1}>P_{V 2}$, $P_{W 1}>P_{W 2}$ となることが想定される. 今回の実験 では, $P_{V 1}=10, P_{V 2}=1, P_{W 1}=10, P_{W 2}=5$ とした.各陣営としてのスコアは, その陣営として参加し たゲームあたりの平均得点となる。(一度も役職を 引かなかった陣営のスコアは 0)

1 世代分の対戦が終わると，遺伝・交叉により，次世代の個体を生成する．今回の実験では，エリート 保存戦略 [10] によって 4 個体，交叉によって 11 個体を生成する。まず，人狼としてのスコアの 1 位， 2 位と村人としてのスコア 1 位，2 位の個体を選出 する. 村人としての 1 位，2 位と人狼としての 1 位, 2 位の個体計 4 個体をそのまま残し，人狼陣営 1 位表 3 遺伝子の交叉方法

図 2 同一エージェント同士の対戦の試合数と勝率

の個体 (w1)，人狼陣営 2 位の個体 (w2), 村人陣営 1 位の個体 (v1)，村人陣営 2 位の個体 (v2) の遺伝子を それぞれに対して表 3 のように，村人としてのスコ アの高かった個体から村人側の遺伝子を，人狼とし てのスコアが高かった個体から人狼側の遺伝子を遺伝させる形で 11 個体を新しく生成する。共通して 発現する遺伝子の v2 or w2 の部分は， v2 か w2 のど ちらかをランダムに遺伝させる。

この遺伝・交叉システムを用いて世代を重ね，学習の局所解への早期収束を防ぐため， $N_{g}$ eneration 世代ごとに一度，遺伝・交叉の後に他の村への個体 の移住を行った。個体の移住では，それぞれの村に ついて村のエージェントのうちランダムに 7 個体を 移住個体として選び，すべての村の移住個体を集め て，ランダムに各村に 7 体ずつ配りなおすという動作を行い，ほかの村のエージェントを交えて次世代 の対戦を行うことで個体の多様性の維持を図る。

また，個体の移住とは別の手段での多様性の維持手段として，これらの遺伝・交叉・個体の移住が終了した後で，特定の変異率による突然変異を行う。今回の実験では，新しい世代の全個体に対してそれ ぞれ変異率 0.01 で遺伝子のうち 1 箇所をランダム
表 4 各世代交叉終了時に最も数の多かった遺伝子の個体

に初期化する突然変異を行った。

## 4 遺伝的アルゴリズムの設定値

今回の実験における各種設定值について，一部 の設定値について妥当な値を調査するため実験を 行った.

## 4.1 ゲームルール

それぞれの村は 15 人人狼を行い，役職の内訳は 占い師 1 ，霊能者 1 ，狩人 1 ，狂人 1 ，人狼 3 ，村人 8 人ずつの 15 人からなる. 他，詳細なルールは人狼 BBS の $\mathrm{G}^{2}$ 国 $^{4}$ における 16 人村（初日の犠牲者が いないため実質同じルールとして働く）を参考に した.

## 4.21 世代あたりの対戦数について

自己対戦において 1 世代の対戦数に必要な対戦数を調査するため，同一エージェント同士の対戦を 行った. 同一エージェント同士の対戦では，まった く同じパラメータの組み合わせをもつエージェント 同士による対戦を無限回に繰り返すことで理論上 エージェントの勝率の分散はどの村でも 0 に収束す るという考えのもと，同一エージェント同士の対戦 100 回を 10 セット行い，勝率の分散値の変化を調査 した.

図 2 は，まったく同じ遺伝子の組み合わせをもつ エージェント同士による対戦を 100 回 10 セットを 行ったときの，試合数に対するエージェントの勝率 の分散である. 対戦数が 10 対戦付近ではまだ村ご との分散が大きく，結果がばらけてしまっている が，30 対戦から 50 対戦で分散が小さくなり，その あと分散は小さくなり続けているものの概ね横ばい


図 3 第 4 世代終了時に最も数の多かった遺伝子の各世代 での個体数変化

の値をとっている.この結果より，エージェント同士の勝率がある程度収束し，個体ごとに優秀な個体 とそうでない個体を判別するのに対戦数は最低限 30 対戦から 50 対戦は必要となることが考えられる。 そこで，本研究では 1 世代あたりの対戦数 $N_{\text {game }}$ を 50 対戦として設定し実験を行った。

## 4.3 並列分散 GA の移住までの世代数

並列分散型遺伝的アルゴリズムによる，移住まで に必要とされる世代数について最適な世代数を調べ るための調査を行った。表 4 は, 1 世代あたりの対戦数を 50 としたとき 12 の村について，各世代後の交叉終了時に最も数が多かった遺伝子の個体名と個体数を示したものである。遺伝子の個体名について は，上 1 桁はその個体がどの世代で初めて生成され たものであるかを示しており，下 3 桁はその世代で 何番目に生成された個体であるかを示している。

表 4 の結果について, 第 4 世代終了時に最多個体数である個体はほとんどが第 3 世代終了時でも最多個体であり，第 3 世代終了時点で過半数を占めてい るものが多いため，第 3 世代終了時の時点で交叉に よって優秀な遺伝子はほとんど完成している可能性を考え，さらに第 4 世代終了時に個体数が最も多 かった個体の各世代終了時の個体数について調査し た. 図 3 は， 1 世代あたりの対戦数を 50 としたとき の第 4 世代目終了後の交叉終了時に最も数が多かっ た遺伝子の各世代での個体数の変化を示したもので ある.この結果より，第 3 世代から第 4 世代にかけ て，最多数個体の個体数は増えているものの，第 3 世代までの結果でどの個体がその後最多数となるか について大勢は決しているものと判断し, 本研究で は個体の移住までの世代数 $N_{\text {generation }} 3$ 世代ごと と設定した。

## 5 まとめ

本稿では，翻意誘導の対象となりえる人狼エー ジェントの構築のため，進化論的アプローチによる エージェント構築に関する設計と，方法の調査を 行った. 今後は発話の意味理解や自然言語による発話の生成を含め，実際にエージェントを構築しエー ジェントに対しての翻意誘導を実現する技術の調査 を行う予定である。

## 参考文献

[1]阪本浩太郎, 永山翔滋, 石下円香, 渋木英潔, 森辰則, and 神門典子. 人狼ゲームプラットフォーム licos を用いた 欺瞞対話コーパスのためのゲームログの収集. 言語処理学会第 25 回年次大会, 32019.

[2]Shoji Nagayama, Jotaro Abe, Kosuke Oya, Kotaro Sakamoto, Hideyuki Shibuki, Tatsunori Mori, and Noriko Kando. Strategies for an autonomous agent playing the "werewolf game" as a stealth werewolf. In Proceedings of the 1st International Workshop of AI Werewolf and Dialog System (AIWolfDial2019), pages 20-24, Tokyo, Japan, October 2019. Association for Computational Linguistics.

[3]Robert Axelrod. Genetic Algorithms and Simulated Annealing, chapter The Evolution of Strategies in the Iterated Prisoner's Dilemma, pages 32-41. Morgan Kaufman, Los Altos, CA, 1987.

[4]Richard Brunauer, Andreas Löcker, Helmut A. Mayer, Gerhard Mitterlechner, and Hannes Payer. Evolution of iterated prisoner' $\mathrm{s}$ dilemma strategies with different history lengths in static and cultural environments. In Yookun Cho, Roger L. Wainwright, Hisham Haddad, Sung Y. Shin, and Yong Wan Koo, editors, Proceedings of the 22nd Symposium on Applied Computing, pages 720-727. ACM, 2007.

[5]Mieko Tanaka-Yamawaki and Taku Murakami. Effect of Reputation on the Formation of Cooperative Network of Prisoners, pages 615-623. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.

[6]系井良太 and 田中美栄子. 進化型繰り返し囚人のジレ ンマにおける最適戦略の探究. Technical Report 3 , 鳥取大学大学院工学研究科エレクトロニクス専攻, 鳥取大学大学院工学研究科エレクトロニクス専攻, may 2012.

[7]鳥居 拓馬, 日高昇平, and 真隅 暁. 学習あり繰り返し囚人のジレンマにおける協調行動の発生. 人工知能学会全国大会論文集, JSAI2014:4H13-4H13, 2014

[8]狩野芳伸, 大槻恭士, 園田亜斗夢, 中田洋平, 箕輪峻, and 鳥海不二夫. 人狼知能で学ぶ $A I$ プログラミング: 欺䁐・推理・会話で不完全情報ゲームを戦う人工知能の 作り方. マイナビ出版, 2017.

[9]三木光範, 廣安知之, 畠中一幸, and 吉田純一. 並列分散遺伝的アルゴリズムの有効性. 日本計算工学会論文集, 2000:20000038-20000038, 2000.

[10]北野宏明. 遺伝的アルゴリズム. 人工知能学会誌, 7(1):26-37, 1992.
 関井郁弥 横浜国立大学 sekii@forest.eis.ynu.ac.jp }  阪本浩太郎 横浜国立大学 sakamoto@forest.eis.ynu.ac.jp }  渋木英潔 国立情報学研究所 shib@nii.ac.jp }  森辰則 横浜国立大学 mori@forest.eis.ynu.ac.jp  