1.人工知能とゲーム：完全情報ゲームから不完全情報ゲームへ
人工知能は知能の再現を目指す分野である。
しかし、知能とは何か、という問いに答えるのは簡単ではない。頭がいい人間、といった場合には、知識があることを意味する場合もあるだろうし、発想力があることを意味する場合もあるだろう。ずる賢い、という意味もあるかもしれない。こうした「頭の良さ」を試すための課題として、人工知能分野ではゲーム課題が昔から用いられてきた。チェスや将棋、囲碁といったゲームは特に、人間の知能の高さを示す課題と考えられており、古くから人工知能による挑戦が行われてきた課題である。
特にチェスは、コンピュータが登場した当初から、いずれ人間よりも強いプレイヤーが登場するだろう課題と目されてきた。計算機科学の祖であるアラン・チューリングは、1951年に自身でチェスプログラムを作成している。ただし、このチェスプログラムを再現できるコンピュータが無かったため、彼は自分で手計算を行いながらチェスプログラムを「稼働」させた。
つまり不思議なことだが、チェスプログラムの人工知能の歴史は、チェスプログラムを動かすコンピュータよりも古いということである。ゲーム課題が、それだけ人々にとってわかりやすく、魅力的な課題であった一つの証左かもしれない。
コンピュータプログラムが賢くなるスピードは、研究者たちの予想よりは遅かったが、チェスプレイヤーたちの予想よりは早かった。また、チェスプログラムの発展は、戦後の米ソ冷戦に後押しされた側面もある。
1974年に初めて行われた国際チェスコンピュータ大会では、ソ連のプログラムであるKaissa1が米国MITで開発されたKotok-McCarthy2を破って優勝し、西側の研究者たちに衝撃を与えた。それまでコンピュータのチェス研究は、どちらかというとコンピュータを遊ばせる牧歌的なイメージで受け取られてきたが、この大会以降、特に米国社会および企業は、計算機技術の実証試験としてのチェスプログラムの研究に力を入れていく。
こうした開発の流れは1996年のチェスチャンピオンGarry Kasparov(ロシア)に対するチェスコンピュータDeepBlue(米国IBM)の勝利につながる。その1年後にはオセロチャンピオンの村上健(日本)がLogistello(米国NEC)に敗れ、20年後には将棋で佐藤天彦(日本)がPonanza(山本一成)3に敗れ、囲碁で柯潔(中国)がAlphaGo(米国Google/DeepMind)に敗れる(2017年)。
ただし、チェスやオセロ、将棋や囲碁といったゲームは、理論上完全情報ゲームと呼ばれる種類のゲームであり、実は本質的にはコンピュータのほうが強いことがすでにわかっていた。完全情報ゲームとは、相手と自分の手が常に公開されているゲームである。
このようなゲームの場合、相手に不利な手、自分に有利な手を選んでいけば、最適な「神の一手」が必ず存在する。こうした手法はミニマックス探索と呼ばれている。例えば無限に情報が書ける石版があり、そこに可能な相手の手、それに対する自分の手、を次々と書いていけば、いつかは相手に対する最適な手がわかってしまうのだ。神の視点からみれば、相手がどういう人間かは考えなくても、解けてしまうゲームであると言える。
その上で神ならぬ人間やコンピュータは、自身の持つ限りある情報資源の中で、いかに無駄な思考をしないで推論を突き詰めていくかを競う必要がある。こうしたゲーム研究で培われてきた盤面評価、アルファベータ法、モンテカルロ木探索や深層学習（「価値」と「ポリシー」の２段学習）などは、究極的には「いかに余計な場面を省いて思考を省略するか」を探索する方法であったと言える。得られたプログラミング手法は探索アルゴリズムなど、ゲーム研究に限らない応用をもたらしてきた。以上のような完全情報ゲームの研究は、知名度が高い中で最も難易度が高い「囲碁」における人工知能の勝利が得られた時点で、おおよそ研究対象としての注目は収まったと言える。
次に注目対象となったのは、不完全情報ゲームと呼ばれる研究領域だった。
不完全情報ゲームは、完全情報ゲームと違い、プレイヤーの手が公開されない種類のゲームである。有名なものではポーカーや麻雀などのゲームがこれに含まれる。相手の手が見えないゲームは、相手の手が見えているゲームよりさらに難しい。麻雀で、通ると思った捨て牌が通らない、ということを体験された方もいるかもしれないが、相手の手が見えないゆえに、いくら時間があったとしても、その場で最適な手を選ぶことが出来ない。これが、無限の時間があれば解ける完全情報ゲームとの大きな違いである。とはいえ理論上は、相手の持っている麻雀牌のすべてのパターンを網羅すれば、最適ではなくても合理的な解は導ける。しかし、この分岐は完全情報ゲームよりはるかに多くなり、確率的にしか決定できない。この点が、不完全情報ゲームが完全情報ゲームに比べて難しい点である。
不完全情報ゲームで最も研究が進んでいるのは、国際的な大会が存在するポーカーである。
ポーカーについては、まずリミテッドポーカーという「掛け金に上限が存在するポーカー」で理論的な解が得られた。そして、現実的な解として、2017年にポーカーのトッププレイヤーと人工知能Libratusを12万回対戦させ、人工知能側が金額で勝ち越したことを持って、ある程度人間を上回ったと見られている。ただし、ここには批判もある。著者は研究会で日本初のポーカーチャンピオンの木原直哉氏と会ったことがある。その際に彼は、ポーカーにおいて重要なスキルの一つが、いかに「弱そうなカモを見つけられるか」であり、相手の選べない総当り戦で試合を行ってコンピュータが人間に勝ったからといって、人間が人工知能に負けた、ということを必ずしも意味しないのではないか、と語ってくれた4。ゲームに勝つ、ということはどういうことなのかを、そもそも考えさせられる面がある。
コンピュータがゲームに挑戦するということは、単にコンピュータプログラムが人間に勝つ、ということだけではなく、コンピュータプログラムを通してゲームの本質に迫る、ということでもある。
実際に、将棋や囲碁、ポーカーと言ったジャンルは、こうしたコンピュータプログラムによる分析が、人間の力を底上げしている側面もある。例えば、羽生善治棋士以降の世代の棋士は、自身の対局をコンピュータで分析することを普通に行っている（これは現在、破竹の勢いで記録を残す若き棋士、藤井聡太氏も同様である）。人工知能を、うまくコーチ役として使っているわけである。ポーカーについても、その可能性が検討されている。またコンピュータプログラムが、新しい将棋や囲碁の定跡を見つけることも珍しくなくなってきた。
2.正体隠蔽系ゲーム研究から「人狼」ゲームへ
上記、不完全情報ゲームにはいくつかの種類があるが、その中で特に最近注目が集まっているのが、相手の意図がわからない状況で、相手の意図を読まないと勝てないタイプのゲームである。
この中で突出したゲームの一つに協力ゲームHanabiがあり、もう一つに協力と敵対環境が合わさったゲーム「人狼」がある。
Hanabiは複数人のプレイヤーが同じ色のカードを、小さい数字から順番にみんなで重ねていくゲームだが、自分自身のカードが見えない、という状況で協力をするゲームである。誰かから教えてもらえばカードは出せるが、教え方が極めて制限されているのが特徴である。上手いプレイヤーは、相手が教えた情報や捨てたカードから、相手が何を意図していたか、を考えて、少ない手がかりから「空気を読んで」自分のカードの情報を補って手を出す。Hanabiを学術研究として行ったのは著者が初だと思われるが、現在はDeepMind社やFacebook社が実際に人工知能のテスト課題として研究を行うゲームとなった。
そして、このHanabiよりさらに難しく、かつ面白い課題として研究が進められているのが、人狼ゲームとなる。人狼ゲームは、昼間は人間に化けているが夜になると狼の本性を表す「人狼」という化け物がいる村で、どのように人狼役を発見し、追放できるかを競う団体型のゲームである。10 人前後のプレイヤーが村人陣営と人狼陣営に分かれ、お互いの正体を隠しながら相手陣営をゲームから排除していく。プレイヤーはお互いの正体を探るべく会話を行い，会話の中からヒントを見つけ出して人狼を探し出すことになる。いわば、スパイ発見ゲームであると言える。このスパイ発見ゲームである人狼を、人工知能の新しい課題とすることが、人狼知能プロジェクトの目標である。
3.人狼ゲームとはなにか：内容とその歴史
人狼ゲームは推理と説得のゲームと呼ばれ、「コミュニケーション」以外の客観的情報、勝敗決定要因がほとんど存在しない、という性質がある。人狼で客観的と言える情報は、各人の発言内容自体と、日数、処刑者、襲撃者などであり、特に現在日本で標準化されているクローズドルールでは、人狼に登場する殆どの役職達は、自分自身の役職を「客観的に」証明する手段を持たない。
たとえば、あなたが人狼ゲームをプレイしている「村人（無能力者）」であり、あなたの友人がそのゲームを外から観察している（＝ゲーム上の発話のみを観測している）とする。この時、ゲームプレイ中に、あなたが村人、あるいは人間側であることをその友人に対し証明することは不可能である（これは、あなたがどの役職であっても同様である）。
もちろん、ゲーム中の「人狼」のプレイヤーにとってあなたが少なくとも「非人狼＝人間側」であることは自明であるし、もし村の中の占い師があなたを占ったとすると、その占い師はあなたが人間側であることを知ることができ、また占い師はあなたが人間であるという発話を行うことができる。しかしながら、村の外にいるあなたの友人から見た時、その「人狼」のプレイヤーが本当に人狼であるのか、あるいは「占い師」と宣言した人間が本当に占い師であるのかどうかはゲーム終了までわからない。
上記制約から、プレイヤーは自身の証明を自身の言語のみで行い、自身の決断を自身のみの判断で行う、という状況にさらされることになる。プレイヤーは誰かを盲信し、自分の選択をその人に委ねる、という手段が取れない中で、自身の行動を選択していく必要がある。
ここで、推論を行うとは、相手の情報について確からしい情報を選んでいくということであり、説得を行うとは、自分の発話により相手の想定している自分の像を変えていくということである。相手の思考や相手の中にある自分のイメージを変えていくことが求められる点で、人狼ゲームは不完全情報ゲーム、特に正体隠蔽型のゲームの中でも、最もシンプルであり、かつセキュリティから人工知能との協調課題まで、多方面への応用が期待されているゲームと言える。
人狼ゲームの由来については諸説あるが、1986年にソ連モスクワ州立大学の心理学の学生であったDimitry Davidoffが形式を整えた、という点についてはおおよその一致が見られる。当時は市民の中にいるマフィアを探す、というシンプルなゲームであり、このゲームは旧共産圏一帯に広がった。
このマフィアというゲームの政治色を取り去り、中世の村に人に化ける狼がやってきた、というアレンジを加えたのが米国のゲーム作家でありプログラマのAndrew Plotkin5である。この人狼のアイディアを元に、米国Looney Labsが2001年に”Are You a Werewolf? (汝は人狼なりや?)”というカードゲームを作り、ここで村人、人狼、占い師という初期のゲーム内の「役職」が決定された6。
人狼ゲームは米国経由で西側諸国に広がり、フランスでは” Les Loups-Garous de Thiercelieux (ティエルスーの人狼、という意味だが、米国版の「ミラーズホロウの人狼」という訳が有名)”7、翌年2002年にはイタリアで”Lupus in Tabula (タブラの人狼)”8が登場する。後者は特に、クローズドルールと呼ばれる、ある人物が処刑されたり追放されたりしても、そのカード情報が全体に公開されないルールを取っており、より推理のバリエーションが増えている。
人狼ゲームは2003年から2004年頃にかけて、おもにオンラインゲームとして登場しているが、このタブラの人狼ルールを元に、2004年に作られた人狼BBS9が日本では流行し、その後の日本での人狼文化の規範の一つとなった(残念ながら2020年1月末に、新規更新は停止している)。
人狼BBSの特徴はいくつかあった。まず人狼BBSは、カードゲーム型のルールを引き継いだCGI型の人狼と異なり、議論の昼と能力使用の夜の区別がない。狼は人間同士の議論と並行して、狼同士の秘密の会話を行い、リアルタイムで発話を修正することが可能である。またゲーム内の1日を24時間と置いており、これによって忙しい人でも参加しやすい設定となっている。この特徴が人狼ゲームにおける人口の増加をもたらした。
次に人狼BBSは、プレイヤーと別に、プレイヤーが操るキャラクターをロール・プレイする要素がある。人狼BBSでは村に登場するキャラクターがおおよそ固定されており、インタフェースとして老若男女織り交ぜた、共通のキャラクターセットが用意されている。これにより、各プレイヤーは自身のプレイスタイルや人狼、占い師などの役職のプレイ（ロールプレイ）だけでなく、キャラクターの役割を意識したプレイ（キャラクタープレイ）ができるようになった。人狼BBSと同様のBBS型人狼はネット上にて爆発的な普及を見せ、国外にも同様の人狼サイトが作成されている。
次に日本で人狼ゲームがブームとなったのは2012年以降である。
この頃にはスマートフォンが普及し、人狼ゲームにおけるゲームマスターをスマートフォンが代替するアプリが普及した。これによって学校を初めとした多くの場所で対面の人狼ゲームが気軽に行われるようになった。この第二次ブームを背景として、テレビ番組や演劇で人狼を扱うものや、小説や漫画、ビデオゲームで人狼を扱うものが増えていく。
株式会社人狼10（人狼カード販売、人狼ハウス運営）や有限会社ことり11（ドイツゲームスペース、人狼ルーム運営）のように、人狼を業務の一環とし、企業研修のために人狼を提供する会社も増えている。ブームの一翼を担った演劇型の人狼「人狼 ザ・ライブプレイングシアター」12は、人狼一次ブームのキャラクターロールプレイと、二次ブーム時の対面人狼の面白さを文化として継いでおり、彼らの採用する13人で行われる人狼ゲームは、対面人狼における一つの基準となっている。
4.人狼知能プロジェクトの取り組み
人狼知能プロジェクトでは、分野の違う研究者が集まって、この人狼ゲームに対する研究を行っている13。やり方としては、プロジェクトとして毎年大会を開き、そこに集まったプログラムの分析を行いながら、人狼ゲームを形作る要因を調べていく、というやり方をとっている。大会の種類としては、プレイヤー同士が決められたプロトコルで話すプロトコル部門と、人間と同じような自然言語で話す自然言語部門の2つに分かれている。
プロトコル部門は、自然言語処理にとって重要な課題と、推論にとって重要な課題を切り分けるために設計された。
人間どうしの人狼では自然言語による会話が行われるが、これらの自然言語をそのままエージェントが扱うのは開発者にとって負荷が大きい。また、人狼中の言語は極めて文脈に依存しやすく、既存の言語認識手法が使いづらいという問題もある。そこで，人狼ゲームを人間とエージェントの混在環境やエージェント間でプレイするために、他者のモデル推定と他者から見た自己のモデル推定について伝達できるような独自のプロトコルを設計した。
人狼プロトコルは，エージェントや役職を表す単語、意思表明や行動あるいは行動の結果を表す文、同意や異議、他者への要請などから構成され、それらを決められた順番で並べることによって発話を生成する。例えば、「私（Agent1）はAgent2 を人狼だと思う」という発言は、「推定」を表す“ESTIMATE” を使い、“Agent1 ESTIMATE Agent2 Werewolf” と表現する。
人狼知能大会プロトコル部門は、2015 年8 月に第1回人狼知能大会が、2016 年には人工知能学会30 周年記念として第2 回人狼知能大会が、国内最大級のゲームカンファレンスCEDECにおいて開催されるなど、2015 ～ 18年にかけて4 回の大会が行われている。2016～2017年にかけては、春のゲーム情報学研究会においてミニ大会も開かれた。さらに、2019 年には国際人工知能学会IJCAI 2019（International Joint Conference on Artificial Intelligence）の併設イベントであるANAC 2019（10th International Automated Negotiating Agents Competition）にて、初の国際大会The 1st International AI Wolf Contest として行われた。今年（2020年）は新型コロナウイルス感染症により大会の時期が遅れているが、2020年7月に第二回国際大会の予備戦が開催された。
おおよそ毎大会ごとに70 ～ 100 エージェントが登録されているが、実際にエラーなく起動するのは30～40エージェント程度である。無事起動したエージェントどうしで予選大会を行い、予選を勝ち抜いた15 エージェントで決勝大会を行う。
試合は予選、決勝ともに五人人狼と15 人人狼の双方が行われ、それぞれでの勝利数の合算によってエージェントの順位を決定し、決勝大会で最も勝率の高かったエージェントを優勝としている。開発言語としては、Java, Python, C# を公式にサポートしているが、それ以外の言語でもプラットフォームとTCP/IP 通信接続ができれば参加可能である。事実、Python やC# は参加者によってつくられたライブラリがその後公式として採用されるというプロセスを経ている。
プロトコル部門では、当初ルールベースのエージェントが多かったが、近年では機械学習を導入したエージェントが特にPython を利用して多数開発されている。機械学習の利用方法はエージェントによってさまざまであるが、役職推定などに一定の成果を上げているようである。しかしながら，機械学習を利用することで計算時間がかかるようになり、一試合が第1 回人狼知能大会では平均1 秒未満だったのに対し、現在は10 秒ほどかかるようになり、実行可能な試合数の減少をもたらしており、今後どのようにするかについて検討が必要となっている。
人狼知能大会プロトコル部門は英語をベースとした人狼プロトコルを利用しているため、国際化が容易であり、2019 年には人狼知能国際大会はコンペティションAutomated Negotiating Agents Competition（ANAC）の一部門として試合が開催された。ANAC は交渉エージェントに関するコンペティションであり、マカオで行われた国際人工知能大会IJCAI 2019 のセッションとして開催された。
The 1st International AI Wolf Contest では、海外エージェント7 チーム（イスラエル、フランス、トルコ、スペイン、シンガポール）を含む94 チームの登録があり、そのうち74 チームがエージェントの登録を行い，31 チームが予選に参加した。エージェント予選では各エージェントとも10 000 回以上の対戦を行い、上位の成績を収めた15 エージェントが決勝戦に進出している。29 チームが最後までエラーを起こさずに残った。29 チーム中12 チームがJava、15 チームがPython、2 チームがC# で書かれていた。残念ながら、最終的に決勝戦に残った海外から登録されたエージェントはいなかった。これは、これまで4 年間日本国内で人狼知能大会が行われていたため、日本国内の参加チームの開発経験が豊富だったことが要因であると考えられる。
ANAC では，IJCAI （2019）本会議中のコンペティションセッションに先立ち、8 月11 日にInternational Workshop on Agent based Complex Automated Negotiations （ACAN）が開催された。このセッションで我々は、人狼知能大会の趣旨について説明を行い，同時にプロトコル改良の意図を説明した。続いて、8 月15 日に行われたIJCAI 本会議中のANAC セッションにおいて、受賞者を含めた成績が発表された。優勝は東京大学の学生が開発したTakeda であった。ANAC セッションには30 名を超える参加者がおり、コンテストの模様はYouTube にて中継された。
自然言語処部門は、同じく毎年大会を行っている。
技術力が多く求められるため、プロトコル部門に比べると参加者は少ないが、年々レベルが上がっている。自然言語部門の特徴として、どれだけ人間に近い会話を行ったか評価する点がある。毎年、「発話が自然か」「文脈を踏まえているか」「発話内容に一貫性があるか」「ゲーム行動が対話と一致しているか」「発話表現が豊かか」という点について個々のプレイヤーの評価を行っている。こうしたプレイヤーたちは、推理小説風であったり、意図を説明したりと、それぞれ人を惹きつける個性的な話し方に挑戦している。ただし、現状ではエージェント間で十分に相互の意図を理解したやり取りをしているとは言いづらい状況であり、今後、改善が見込まれる点でもある。
5.おわりに：「心の理論」の解明に向けて
知能とはなにか、という問いに答えることは簡単ではない。
知能とは問題解決の手段であり、その発現系は多方面に渡る。ゲーム課題はこうした様々な知能を分析し、磨くための、人工知能に対する試金石であった。歴史的に、探索アルゴリズムや学習アルゴリズムの発展にゲーム研究は大きく寄与している。
では、人狼ゲームが試す「知能」とは何か。
人狼ゲームは人を騙すゲームだと考えられているが、実際には、騙される環境の中で、それでも人を信じ抜くとはどういうことか、が試されるゲームである。人狼の研究が目指す知能とは、人間が持つ知能のうち、社会的知能と呼ばれる種類の知能の分析である。これは、相手の意図を読み、相手と協力するための知能といえる。
人間にも同じような知能があり、相手の意図を読む知能は「心の理論」と呼ばれている。心の理論は、人間の持つ知能の中でも最も難しい種類の知能である。
しかし、こうした知能がなければ、人工知能が人のやりたいことを理解し、人と協力し、問題を解決するような世の中は訪れないであろう。また、人工知能が心の理論を理解するということは、人が人の心を理解するための手助けを、人工知能が行える、ということでもある。
チェスや囲碁やポーカーの人工知能の研究は、さまざまな社会状況に揉まれ、時にはゲームプレイヤーたちの厳しい視線にさらされてきた。しかし今ではゲームの分野を広げ、プレイヤーを育てる上でも、欠かせない存在となっている。
同様に人狼ゲームの研究は、人の意図を読み、人を説得するための仕組みの理解につながるだろう。そして、こうした仕組みを処理する人工知能は、ゲームの範囲を超えて、広く、人と協力できる人工知能システムを生み出す基盤研究になると、我々は考えている。
参考文献
[1] Noam Brown and Tuomas Sandholm. 2017. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science (80-. ). (December 2017). Retrieved from http://science.sciencemag.org/content/early/2017/12/15/science.aao1733.abstract
[2] Michael Buro and 石川大介. 2000. コンピュータリバーシの現状(完)最強の学習型オセロプログラムlogistello. Bit 32, 7 (2000), 46–50. Retrieved September 21, 2020 from http://ci.nii.ac.jp/naid/40000002958/ja/
[3] Murray Campbell, A. Joseph Hoane, and Feng Hsiung Hsu. 2002. Deep Blue. Artif. Intell. 134, 1–2 (January 2002), 57–83. DOI:https://doi.org/10.1016/S0004-3702(01)00129-1
[4] Dimma Davidoff. 1999. The Original Magia Rules. Retrieved from http://web.archive.org/web/19990302082118/http://members.theglobe.com/mafia_rules/
[5] Andrew Hodges. 2014. Alan Turing: The Enigma. DOI:https://doi.org/10.2307/j.ctvc77913
[6] Hirotaka Osawa. 2015. Solving Hanabi : Estimating Hands by Opponent’s Actions in Cooperative Game with Incomplete Information. AAAI Work. Comput. Poker Imperfect Inf. (2015), 37–43.
[7] Hirotaka Osawa, Takashi Otsuki, Claus de Castro Aranha, and Fujio Toriumi. 2019. Negotiation in Hidden Identity: Designing Protocol for Werewolf Game. In Twelfth International Workshop on Agent-based Complex Automated Negotiations, 1–4.
[8] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George Van Den Driessche, Thore Graepel, and Demis Hassabis. 2017. Mastering the game of Go without human knowledge. Nature 550, 7676 (2017). DOI:https://doi.org/10.1038/nature24270
[9] 大澤博隆. 2020. Hanabi コンペティション ─不完全情報下における相互協力─. 人工知能 35, 3 (2020), 385–389.
[10] 鳥海不二夫, 片上大輔, 大澤博隆, 稲葉通将, 篠田孝祐, and 狩野芳伸. 2016. 人狼知能：だます・見破る・説得する人工知能. 森北出版.
[11] 鳥海不二夫, 狩野芳伸, 大槻恭士, 大澤博隆, アランニャクラウス, 稲葉通将, and 片上大輔. 2020. 人狼知能大会 ─国際大会と自然言語大会を終えて─. 人工知能 35, 3 (2020), 344–350.
