第 4 章 超伝導 34
5.2 しりトらす
5.2.1 「しりとり→グラフ→数理」？？？
この記事では、私たち自然言語処理班が作成した「しり トらす」ゲームの仕組みを紹介することで、皆さんに「し りとりをグラフに表して数理的に解く」ことの面白さをお 伝えしたいと思います。
とはいえいきなり「しりとりをグラフに表して数理的に 解く」なんて言われても、頭に「？」が浮かぶだけで全くイ メージがわかないでしょう。ですので、最終的に皆さんの
「？」が「！」に変わるのを目標に、一歩一歩お話を進めて いくことにします。そして、言葉（自然言語）を使った遊 びを数学的な問題として扱うことができ、さらにはそれが ゲーム理論という深い数学的な理論にも通じているという
ことに数理の凄さを感じていただくことが、私たちの最終目標です。それでは、早速本題に入りましょう。
5.2.2 「しりとりの面白さは 2 つある
࡞ࡆ
⇐
࡞࠶࠻ Ⅎⅇ
࡞ࡊ
ࡆ࡞ ᮻ ࠕࡅ࡞
ࡔ࡞
ᤐ ࠨ࡞
ࠞࠛ࡞ ࠕࠗ࠼࡞
ࡊ࡞ ࠪ࡞
ࡄ࠭࡞
ࠧ࡞
ᤤ ᄛ 㢬
ཬ᳝ ࠹ࡉ࡞
̖GVE
̖GVE
ޟࠆޠߢᆎ߹ࠆ
ޟࠆޠߢ⚳ࠊࠆ
しりとりと言えば誰しも一度はやったことがある遊びでしょう。話す 環境さえあればどこでも気軽にできる上、特有の面白さがあります。例 えば、おかしな単語を言って皆で笑ったり、「こんなのがあったのか！」
と驚くような単語が出てきたり。また、同じ文字で終わる単語を連発し て相手を困らせるのが好きな人もいるでしょう。例えば「る」で終わる単 語は多いのに「る」で始まる単語は少ないので、「る」で終わる単語を連発 されると、相手はなかなか単語を思いつけなくて困ってしまうんですね。
このように見ると、しりとりの面白さは大きく分けて、⃝1おかしい単 語や意表を突いた単語が出てくることの面白さ、⃝2相手が単語を思いつ きにくいように攻めていくことの面白さ、の2つがあると言えるのでは ないでしょうか。
5.2.3 コンピュータ相手でも面白いしりとりゲームを考えよう
そこで私たちは、このしりとりをコンピュータとすることはできないか？と考えました。実はコン ピュータと単にしりとりをするプログラムなら簡単に作れます。コンピュータに辞書データを入れ、特定 の開始文字の単語を検索して1つ選んで表示するようにプログラムしてやればいいのです。でも、これだ と面白くないのです。コンピュータはただ機械的に単語を表示するだけですし、単語がなかなか思いつ けずに悩んでしまうということもありません。つまり、しりとりの面白さの⃝1と⃝2がそのまま欠けてし まっているんですね。⃝1をコンピューター上で実現することは難しい*4ので、私たちは逆に⃝2を追求し て、コンピュータ相手だからこそ面白くなる新たなルールのしりとりを作ってしまおう、と考えました。
そうして生まれたのがしりとりゲーム「しりトらす」です。
5.2.4 「しりトらす」は、いわば「詰めしりとり」
「しりトらす」はコンピュータの能力が生かせるようにしりとりを改造した頭脳的パズルゲームです。
具体的な「しりトらす」のルールは以下の通りです。
• 使うことのできる単語を限定し、全て公開。
• 通常のしりとりと同様、一度使った単語は使えなくなる。
• 相手が単語を言えなくなるようにしたら勝ち。
ߒ㧦ߒޔߒ߅ࠅޔຠ‛
ࠅ㧦࠶࠻ޔࠅߔ ߣ㧦໊ㄆሶޔ࠻ࡑ࠻࠰ࠬ
ࠄ㧦ࠬ࠻ࠬࡄ࠻
ߔ㧦ࠬࠤ࠻࠙࠳ޔๆᲖޔ᳓᥏ޔߔߘ㊁ޔ㈶ߩ‛
߁㧦ㆇᴡޔ࠙ࠖࡦࠢ
߇㧦ᄖ㘩
ߊ㧦ⓨ⣻ޔ㤥⍾♧
ߩ㧦ࡁ࠶ࠢࠕ࠙࠻ޔᱷࠅ㚅ޔߩߞߵࠄ߷߁ 単語が全て公開されているので、あらかじめ使え 㗴
る単語を見て作戦を立てられること、そして必ず最 後にどちらかが負けることが特徴です。また、あと でわかりますが、使える単語セットに応じて、先手 か後手のどちらかに必勝法が存在します。これは しりとりの面白さのうち⃝2だけを抽出したような ゲーム、言うなれば「詰めしりとり」です*5。
例えば、右の問題を考えてみましょう。
勝つにはどうしたらいいでしょうか。しかしこれでは単語が多すぎて、作戦を立てづらいですね。まし てや必勝法など見つかりそうにありません。もっとわかりやすく情報を整理する方法は無いでしょうか。
*4http://www2.nict.go.jp/x/x161/member/murata/technique/siritori/siritori.htmlなど、これを目指したものもあり ます。
*5 なんだ、使える単語が決められているしりとりなんてつまらないじゃないか、と思う方もいるかもしれません。全くその通 りなのですが、あくまで「しりトらす」はしりとりの⃝2の面白さを追求して生まれた新たなパズルゲームなんだ、という意識 で眺めてみてください。そしてこの先を読んでいただければ、少しはその面白さがわかるのではないかと思います。
50 第5章 自然言語
5.2.5 しりとりをグラフに！
ߒ
ߒࠅߣࠅࠅ
ࠅࠎߏߏ
そこでグラフの登場です。ただし、グラフと言っても実験でよ く見る折れ線グラフとかではなくて、点とそれを結ぶ辺から成る、
数学的なグラフです。例えば「しりとり→りんご→ゴリラ」の場
合、右のように表すことができます。これがグラフです。先の問題もグラフで表してみましょう。
ߒ ࠅ
ߣ
ߩ
ߔ ߁
߇
ߊ
ࠄ
ᄖ㘩 ᱷࠅ㚅
᳓᥏ ๆᲖ
ࠬࠤ࠻࠙࠳
ࡁ࠶ࠢࠕ࠙࠻
໊ㄆሶ ࠅߔ
࠶࠻
࠻ࡑ࠻࠰ࠬ
ࠬ࠻ࠬࡄ࠻
ߒ߅ࠅ
ຠ‛
ߒ
㈶ߩ‛ߔߘ㊁
ߩߞߵࠄ߷߁
ㆇᴡ
࠙ࠖࡦࠢ
㤥⍾♧
ⓨ⣻
ߒ ࠅ
ߣ
ߩ
ߔ ߁
߇
ߊ
ࠄ
5VCTV
この図を見て勝つ方法を考えていくと、実は単語それ自体は重要ではなく、むしろ文字を表す「点」と文 字同士を結ぶ単語を表す「辺」の本数が重要であることがわかると思います。つまりしりとりは、点から 点へと移動していくパズルゲームと見ることができるのです。この場合、移動する度に通った道を削除し ていって、先に移動できなくなってしまった方が負けとなります。
さて、グラフは数学的に定義された対象です。*6よって、しりとりゲームは数学の力を使って解くことが できるのです！このように数学を使って現実にある現象を読み解くことを、「数理的に解く」と言います。
それでは早速「数理的に」問題を解いていきましょう。これによって、問題が先手必勝なのか後手必勝 なのかがわかり、さらには必勝法もわかることになります！*7
5.2.6 グラフを簡略化するテクニック
まず数学にはこのゲームのグラフを簡略化する定理が4つあり、そのうち重要な2つをテクニックとし て紹介すると次のようになります*8
1. 互いに逆向きの辺の相殺
2. 一方通行の辺がある場合の問題の分割
1.について）もし有利になるからと選んでも、その場合相手にすぐに戻されてしまいます。逆に相手が有 利になるために選んできたら、こちらが戻せばいいだけです。つまり、使っても使わなくても状況は変わ
*6グラフの数学的定義が知りたい方は、「グラフ理論」の教科書を読んでみて下さい。
*7 ※簡単になる様子をより強調して伝えるため、この問題は「しりトらす」の中でも最高難易度の問題となっています。パズル が好きでない方は、とりあえずひと通り図を眺めていって、しりとりのグラフが簡単になっていく様子を見てみてください。
*8他のテクニックは「しりトらす」ゲームを実際にプレイしてもらえれば知ることができます。当日以外でも、5月祭が終了後 に公開する予定です。詳細は、2007年五月祭研究展示〜あなたのハテナをビックリに〜http://mayfes.hobby-site.com/
の自然言語ページをご覧になってください。
߁ ߇
ߊ
ߎߩ ߟߩㄝࠍ㒰
߁ ߇
ߊ
ᓟᚻᔅൎ㧔ޟ߇ޠ߇ࠬ࠲࠻ߩ႐ว㧕
వᚻᔅൎ㧔ޟ߁ޠ߇ࠬ࠲࠻ߩ႐ว㧕 ᔅൎᴺត⚝ߢߪ
ะ߆ว߁ㄝࠍ㒰
2.について）一方通行の場所があるとき左下の図のように問題を分けて考えられるという意味です。そし て左下の図を見ると、勝つには「の」への辺と、「う」への辺を使ってはならない（相手が必勝となってし まう）ので、結局お互い負けないようにすると、右下の図の範囲しか動かないことがわかります。
ߒ ࠅ
ߣ ߔ
ࠄ ߒ
ࠅ
ߣ
ߩ
ߔ ߁
߇
ߊ
ࠄ ᓟᚻᔅൎ߳ߩ⍫ශࠍ߁ߣൎߡࠆ㧍 㧔⥄ಽ߇ᓟᚻߦߥࠇࠆߚ㧕
ᓟᚻᔅൎ
వᚻᔅൎ ߎߩ⍫ශࠍ
߁ߣൎߜ
ߎߩ⍫ශࠍ
߁ߣ⽶ߌ ߎߩ
⍫ශ ࠍ
߁ ߣ⽶
ߌ
ߎߎߪߐߞ߈⸃ߚ ᧄߩ⍫ශߪ৻ᣇㅢⴕ
ߎߎߢ㗴ࠍಽഀ
5VCTV 5VCTV
5.2.7 必勝法の探索 - バックトラック法
ߔψࠄψߣ
ߒ ࠅψߣ ߔψࠄ
ߒψࠅψߣ
ߣ
ߒ
ߒψࠅψߔψࠄψߣψߔψࠄ ࠅψߔψࠄψߣψߔψࠄ ߔψࠄψߣψߒ ߒψࠅψߔψࠄ
ࠅψߔψࠄ ࠅ
వ
వ
వ వ
వ
వ వ వ
వ వ
వ వ వ
వ వ
వ
వ వ
వ ᓟ ᓟ
ᓟ
ᓟ ᓟ ᓟ
ᓟ ᓟ
ᓟ ᓟ ᓟ
ᓟ
さあ、数理の力で問題がここまで簡単にな りました。あとは地道に場合分けをして考 えていくことになりますが、ここでバックト ラック法という手法を使います。これはコン ピュータでゲームを解くときによく使われる 探索アルゴリズムです。
「行き止まりの一つ前の点から先手必勝と 後手必勝が交互に続く」「後手必勝が一つでも 選択できる分岐点は先手必勝」の2点に注意 して全てのルートについて調べると、右の図 のようになります。
しかし、実際はスタート直後の分岐が一つでも後手必勝に繋がっていたらその問題は先手必勝となるた め、右の図で言うと、最初の上の分岐を調べた時点で探索は終了できます。このように、バックトラック 法は単純に全探索する方法よりも効率が良いと言えます。
以上のことから、先手はまず「りす」を選べばよいことがわかります！
「りす」を選んだ後は常にこちらが必勝の点に移動していけば絶対に勝て
ます。
52 第5章 自然言語
5.2.8 「しりとり→グラフ→数理」！！！
さて、これで問題が先手必勝であることと、その必勝法もわかりました。これが数理の力です。そして この数理はコンピュータに実装することができるため、コンピュータも必勝法を計算できることになりま す。そのため、問題が先手必勝か後手必勝かを正しく判断し、その後必勝法に従って単語を選んでいった ときのみコンピュータに勝てるということになります。これが詰めしりとりである「しりトらす」ゲーム の仕組みです。
ところで、しりトらすが数理的に解けて必勝法も存在することには数学的な理由があります。それはし りトらすがゲーム理論（数学の一分野）で言う「完全情報確定的有限二人ゼロ和ゲーム」（＝ゲームの状 況が全て1手ごとに公開されていて、いつか必ず勝負がつく、二人のうち片方が勝ってもう片方が負ける ゲーム）であったためです。
また、しりトらすの先手・後手必勝判定は、PSPACE完全（＝チューリングマシンによって多項式領 域で解ける問題のうち、最も「難しい」問題）であることも知られています。詳しい説明は省きますが、
PSPACE完全な問題は別のPSPACE完全な問題に効率的に書き換えられます。例えばオセロや五目並べ
などの必勝判定がPSPACE完全ですが、これらの問題を解く効率的な方法を見つければ、同じ方法を応 用してしりトらすの必勝判定問題を解くこともできるのです。逆にしりトらすの必勝判定問題を解く効率 的な方法を見つければ、オセロや五目並べなどの必勝判定問題も解けるので、しりトらすの必勝判定問題 とこれらの問題は「同じ」問題だと考えてしまいます。*9
PSPACE完全な問題はまだまだたくさんあります。また、PSPACE完全な問題に書き換えることがで
きる問題は他にもいくつかの種類があることが知られています。つまり私達は、しりトらすを考えると同 時に、たくさんの問題についても考えていたことになるのです。
このように現象を数理的に扱うことで、しりとりに限らない様々な現象が同じ枠組みに収められ、統一 的な視点から議論できるようになります。これこそ私たちが伝えたい、数理の本質です。
以上でしりとりゲーム「しりトらす」のお話はおしまいです。しりとりという言葉遊びがこのように数 理という豊かな土壌で扱うことができることに少しでも感動していただければ、私たちにってこれ以上な い幸せです。