いろいろなボードゲームの複雑性クラスとその直感的説明

いろいろなボードゲームの複雑性クラスは語られることはありますが、多くの場合直観的説明がなく、論文を読むしかない状況にありました。調べたことをまとめておきます。

チューリングマシンの機能

決定性チューリングマシン

普通のコンピュータのことだと思えばよいです。

非決定性チューリングマシン

決定性チューリングマシンに、『ひとり用のゲーム*1を遊んでいるとき、「ここはどっちに進むとクリアできるか?」という質問に答えてくれる機能』が追加されたものだと思えばよいです。これは何回でも使えます。 「なぜそうなのか?」という質問には答えてくれないので、本当にクリアできることを確かめるには自分でやってみるしかありません。

この機能は使わなくてもよいので、決定性チューリングマシンより強力です。

交代性チューリングマシン

決定性チューリングマシンに、『ふたり用のゲーム*2を遊んでいるとき、「この局面は必勝局面か?」という質問に答えてくれる機能』が追加されたものだと思えばよいです。 あるいは、『絶対間違わないプロ棋士次の一手を聞ける権利』と思っても同じです。これも何回でも使えます。 やはり「なぜそうなのか?」という質問には答えてくれないので、本当に必勝であることを確かめるのは難しいです。

この機能は、ひとり用のゲームを解くのにも使えるため、非決定性チューリングマシンより強力です。

複雑性クラス

多項式時間

P

決定性チューリングマシンを用いると多項式時間で解ける決定問題のクラスです。 ようするに、普通のコンピュータで多項式時間で解ける、Yes, Noを答える問題です。

NP

非決定性チューリングマシンを用いると多項式時間で解ける決定問題のクラスです。 "証拠"を見せられた時に多項式時間で納得できるものであるとも解釈されます。この"証拠"としては、"ここはどっちに進むとクリアできるか?"という質問への答えの列が挙げられます。

当然Pを含んでいますが、真に包含しているかは不明です(P≠NP予想)。

AP

交代性チューリングマシンを用いると多項式時間で解ける決定問題のクラスです。 交代性チューリングマシンは強すぎてなかなか直感的説明が難しいです。

当然NPを含んでいますが、真に包含しているかは不明です。

多項式空間

PSPACE

決定性チューリングマシン多項式量のメモリを与えると解けるけ決定問題のクラスです。 多項式時間では自明に多項式空間しか使用できない(時間計算量と空間計算量の関係)ため、P、NP、APを全て包含します。

実はAP=PSPACEであることがわかっています(並列計算原理)。P, NPを真に包含するかは不明です。

NPSPCAE

非決定性チューリングマシン多項式量のメモリを与えると解ける決定問題のクラスです。

実は、非決定性チューリングマシン多項式空間を使って解ける問題は、その二乗程度の空間を使ってよければ決定性チューリングマシンでも解けることが知られています(サヴィッチの定理)。 多項式を二乗しても多項式であるため、PSPACE=NPSPACEです*3

APSPACE

交代性チューリングマシン多項式量のメモリを与えると解ける決定問題のクラスです。 当然NPSPACEを含んでいますが、真に包含しているかは不明です。

指数時間

EXPTIME

決定性チューリングマシンを用いると指数時間で解ける決定問題のクラスです。 PSPACEやAPSPACEを含んでいます。なぜなら、多項式量のメモリで表される状態数は高々指数個しかないため、それを全探索するのには指数時間しかかからないからです(空間計算量と時間計算量の関係)。

実は、APSPACE=EXPTIMEであることがわかっています(並列計算原理)。 また、Pを真に包含することもわかっています(時間階層定理)。 NP, PSPACEを真に包含しているかは不明です。

NEXPTIME

非決定性チューリングマシンを用いると指数時間で解ける決定問題です。

当然EXPTIMEを含んでいますが、真に包含しているかは不明です。

AEXPTIME

交代性チューリングマシンを用いると指数時間で解ける決定問題です。

当然NEXPTIMEを含んでいますが、真に包含しているかは不明です。

指数空間

EXPSPACE

決定性チューリングマシンに指数量のメモリを与えると解ける決定問題です。

PSPACEの時の議論と全く同じ議論により、NEXPTIMEを包含すること(時間計算量と空間計算量の関係)、NEXPSPACEと同じであること(サヴィッチの定理)、AEXPTIMEと同じであること(並列計算原理)がわかっています。 また、PSPACEを真に包含することがわかっています(空間階層定理)。

いろいろなボードゲーム

スリザーリンク*4をはじめとする多くのペンシルパズル、充足可能性問題

その問題に解があるかを判定する問題はNP完全であることがわかっています。

  • 指数的な分岐があるため、多項式時間では解けなさそう
    • Pではなさそう
  • 答えを見れば「確かにこの問題の答えである」と多項式時間で納得できる(唯一解であるかはまた別の問題)
  • 非決定性チューリングマシンの機能に『ここに線を引くべきか?』などを聞きながら解いていくことができる
    • NPに含まれる

オセロ*5をはじめとする単調に終局に近づく二人零和完全情報ゲーム

ボードサイズを一般化し、(初期配置から到達できるとは限らない)特定の局面に必勝手順があるかを判定する問題はPSPACE完全であることがわかっています。 語彙の集合が与えられる"しりとり"(Generalized geography)も全く同様です。

  • 指数的な分岐があるため、多項式時間では解けなさそう
    • Pではなさそう
  • 最善手順のみ見せられても多項式時間では納得できない(他の手を打ったらどうなるの?となってしまう)
    • NPではなさそう
  • 多項式手数で終わるため、深さ優先探索をすれば多項式空間で解くことができる
    • PSPACEに含まれる
  • 多項式手数で終わるため、交代性チューリングマシンの機能を用いて、『絶対間違わないプロ棋士』同士を戦わせれば多項式時間で解くことができる
    • APに含まれる

倉庫番をはじめとする可逆なギミックがある一人用コンピュータゲーム

その問題に解があるかを判定する問題はPSPACE完全であることがわかっています。 マリオブラザーズ*6などもここに分類されます。

  • 指数的な分岐があるため、多項式時間では解けなさそう
    • Pではなさそう
  • 最短手順が指数的に長い問題もあるため、それを見せられても多項式時間では納得できなさそう
    • NPではなさそう
  • 盤面を覚えておくのは多項式空間でできるため、非決定性チューリングマシンの機能に『次の一手』を聞きながら手順を進めていけば多項式空間で解くことができる
    • NPSPACEに含まれる

ところで、ちょっと考えただけでは

  • 最短手順が指数的に長い問題もあるため、反復深化深さ優先探索を行ってもコールスタックのために指数的な空間が必要そう
    • PSPACEでなさそう……?

となってしまいそうですが、PSPACE=NPSPACEなので、これはおかしいです。実は、時間を犠牲にしてメモリ使用量を削るテクニック(これこそがサヴィッチの定理です)が存在し、それを使うとPSPACEに収まることがわかります。 反復深化深さ優先探索の時間計算量は、Cを適当な定数、Nを入力長として(たぶん)Ο(CN)ですが、メモリ使用量削減手法では最悪時Ο(CN2)になるはずです。

このテクニックは一人用ゲームにしか適用できない手法です。二人用ゲームの深さ優先探索に適用する場合、特定の手を打つと必勝手順に持ち込まれてしまうか、という情報をコールスタックに記録する必要がある点が異なります。一人用ゲームであれば、全探索したことさえわかればよいので、コールスタックを愚直に記録する必要はない、という発想によりメモリ使用量を削ることができます。

時間を犠牲にしてメモリ使用量を削るテクニック(サヴィッチの定理)の適用

具体的なテクニックは驚くほど簡単です。盤面は指数通り(例えば2T通り、ここでTはNの多項式)しかなく、これを枚挙することは多項式空間でできます。また、その盤面が解局面であるかは簡単に判定できます。そこで、あり得る解局面全てを枚挙することができるので、それらすべてについて、「初期盤面からその解局面に到達できるか(到達する手順が存在するか)?」という部分問題を解けば元問題が解けることになります。他の部分問題の解はその部分問題の解に影響を及ぼさず、どの部分問題まで解いたかは多項式空間(T bit)で覚えておくことができます。

ここで、「局面Aから局面Bにk手で到達できるか?」という問題を解くには、「局面Aから局面Cにk/2手で到達できる、かつ、局面Cから局面Bにk/2手で到達できる」かをあり得るすべての局面Cについて調べれば十分です。 これで問題サイズが半分になりました。以下再帰的に問題サイズを小さくしていけば、この再帰はlog k段で終了します。kが1である基底ケースは自明に解けます。

全く同じ局面は最短手順の中に出てこないはずなので、その手順の長さは盤面の通り数2Tで抑えられます。よって、「初期盤面からこの解局面に到達できるか?」という問題は「初期盤面からこの解局面に2T手以内で到達できるか?」という問題と同値になります。0から2T手までの各手数について、先の手法を使うと再帰の段数は高々T段になります。また、各再帰のコールスタックでは、局面Cとしてどこまで検索したかというやはり多項式に収まる情報(T bit)を持っておけば十分です。合わせてT2程度の空間計算量で解けることになります。

この手法はメモリ使用量は削減できますが、同じ仕事を非常に多数回行うため非常に非効率的であり、実用的な手法ではありません。

詰将棋*7、日本ルールの囲碁*8など

ボードサイズを一般化し、(初期配置から到達できるとは限らない、任意の位置に任意の駒を配置できる)特定の局面に必勝手順があるかを判定する問題はEXPTIME完全であることがわかっています。

  • 指数的な分岐があり、多項式時間では解けなさそう
    • Pではなさそう(実際、Pではないことが示されています)
  • 最善手順だけ見せられても多項式時間では納得できない(他の手を指したら/打ったらどうなるの?となってしまう)
    • NPではなさそう
  • 最善手順は指数的に長い可能性があるため、交代性チューリングマシンの機能を用いても多項式時間で解くことはできなさそう(『絶対間違わないプロ棋士』同士の対戦は指数時間かかる)
    • APではなさそう
  • 最善手順は指数的に長い可能性があるため、深さ優先探索を行うと指数的な空間が必要になる
    • PSPACEではなさそう
  • 局面を覚えておくのは多項式空間でできるため、交代性チューリングマシンの機能を用いて『絶対間違わないプロ棋士』同士を戦わせることにより多項式空間で解ける
    • APSPACEに含まれる
  • 局面の情報のみから必勝手順があるかが決まり、あり得る局面は指数個しかないので、メモ化深さ優先探索すれば指数時間かけて解ける
    • EXPTIMEに含まれる

補足

日本ルールの囲碁はアゲハマの数を覚えておく必要がありますが、指数的な長さの最善手順の対局では指数的な個数のアゲハマしか発生せず、それは多項式bitの情報量しか持ちません。

中国ルールの囲碁は、指数的に長い手順が必要なパターンがあることが示されておらず、EXPTIME完全かはわかっていないようです。それでも少なくともPSPACE困難であることはわかっています。コウの取り扱いに依存しない囲碁の部分問題として、「このシチョウ(珍瓏)はどちらが勝つか?」のような決定問題が考えられます。この問題はオセロ同様に単調に終局に向かう性質があり、実際PSPACE完全です。

将棋*9をはじめとする同一局面の再現を制限するルールのある二人零和有限確定完全情報ゲーム

ボードサイズを一般化し、(任意の位置に任意の駒を配置できる)特定の局面に必勝手順があるかを判定する問題はEXPSPACE完全であることがわかっています。 同一局面を再現する手を合法手としないルールは、スーパー劫ルールとも呼ばれます。将棋の千日手ルールは、すでに三回出現した局面を再現する手を合法手としないルールですが、似たようなものです。 いずれも相手の有用な着手を妨害する効果を持つ点が話をややこしくする原因です。

  • 指数的な分岐があり、多項式時間では解けなさそう
    • Pではなさそう(実際、Pではないことが示されています)
  • 最善手順だけ見せられても多項式時間では納得できない(他の手を指したら/打ったらどうなるの?となってしまう)
    • NPではなさそう(実際、NPではないことが示されています)
  • 最善手順は指数的に長い可能性があるため、交代性チューリングマシンの機能を用いても多項式時間で解くことはできなさそう(『絶対間違わないプロ棋士』同士の対戦は指数時間かかる)
    • APではなさそう(実際、APではないことが示されています)
  • 最善手順は指数的に長い可能性があるため、深さ優先探索を行うと指数的な空間が必要になる
    • PSPACEではなさそう(実際、PSPACEではないことが示されています)
  • どの局面が既に出現したかも含めたあり得るゲームの状態の数は指数個に収まらないので、深さ優先探索は指数時間では終わらない
    • EXPTIMEではなさそう
  • どの局面が既に出現したかという指数的な情報量を覚えておく必要があるため、交代性チューリングマシンの機能を用いて『絶対間違わないプロ棋士』同士を戦わせる方法は多項式空間では足りない
    • APSPACEではなさそう
  • 最善手順は指数的な長さに収まる*10ので、深さ優先探索をすれば指数的な空間を使って解くことができる
    • EXPSPACEに含まれる
  • 最善手順は指数的な長さに収まるので、交代性チューリングマシンの機能を用いて『絶対間違わないプロ棋士』同士を戦わせる方法を使えば指数時間で解ける
    • AEXPTIMEに含まれる

補足

ところで、詰将棋にも千日手の問題がありそうに思われますが、実際はEXPTIMEに収まります。連続王手の千日手は攻方の負け=不詰であることから、攻方に不利にしか働きません。また、千日手にならない程度に同じ手順を繰り返しても手順が長くなるだけであり、やはり攻方に不利にしか働きません。ただし、双玉図式では攻方に有利に働く場合がありうる*11ため必ずしもEXPTIMEに収まるとは限らなくなります。最短路問題に置き換えてみると直感的な理解ができるかもしれません。つまり、普通の詰将棋では単に距離が正の閉路が追加されるだけで、問題が複雑になるわけではありません。一方双玉図式の場合、使える回数に制限のある負閉路が増えた状況にあたり、問題が複雑化します。

日本ルールの囲碁のコウ(劫)ルールは千日手問題と似ていますが、問題を複雑化させるに至らず、EXPTIMEに収まります。囲碁では着手によりその手番の石が盤上に必ず一つ増えることから、元の盤面に戻る着手はその増えた石をとる着手しかありえません。つまり、その増えた石はどの石なのか=直前の着手はなにか、を覚えておく必要がありますが、それ以前の情報を覚えておく必要はありません。チェスの50手ルールも、直前50手のみ覚えておけばいい点で同様です。なお、この50手というのは理論的に導かれたものではなく、実際、一般化される前の普通のチェスでは、50手ルールが悪影響を及ぼす盤面の存在が知られています。そういった問題を避けるためにこの50手という部分がボードゲームサイズに依存して決められる場合、EXPTIMEに収まるとは限らなくなります。

中国ルールの囲碁には、任意の既出局面に戻る着手は禁止される、というスーパー劫ルールが存在します。そのためEXPSPACE完全な雰囲気がありますが、そもそも指数的に長い手順が必要なパターンが知られておらず、スーパー劫ルールを持つ中国ルールの囲碁がEXPSPACE完全かはわかっていないようです。日本ルールの囲碁がEXPTIME完全であるという証明は通常のコウ(劫)ルールに依存しており、スーパー劫ルールを導入すると証明が破壊されるそうです。

余談

将棋の古い千日手ルール「仕掛けたほうが打開する」は、千日手はほとんどの場合取って取り返され打って相手が守りのために打つという一連の手順を繰り返す場合として発生することから定められたルールのようですが、序盤の駒組み(駒の取り合いが発生せず、どちらが仕掛けたともつかない状況)でも発生したことからルールが改正されました。

しかし、その改正された千日手ルール「同一手順で同一局面に戻ることが三回発生した場合」も、同一局面に戻る手順が複数存在する場合に問題となりました。

そこでさらに改正された千日手ルールでは「同一局面四回目」というルールになりました(同一局面に戻る手順が唯一の場合、等価になります)。

他のボードゲームではたいてい「同一局面三回目」というルールになっていますが、これは、同一局面に戻る手順があることは二回目には認識できるため、三回目の発生は打開しなかったことが明白だという考え方に基づくのでしょうか?

余談の余談:同一局面に戻る手順が複数存在する場合にどう問題になるのか?

そのような手順A, Bがあるとします。すると、A B BA BAAB BAABABBA BAABABBAABBABAAB ... のような手順で繰り返す場合、この手順の中にはAAAなどはもちろんのこと、AABAABAABのような一連の手順で同一局面に戻ることが三連続するパターンも存在せず、無限に続くことになります。この手順中に同一手順が三連続するパターンがない(非三連である)ことは直感的には明らかですが、具体的に示すのはちょっと難しいです。

もう少し簡単に示せる構成もあります。

  1. iが三で割って一余る数なら、i回目にはAを指す。
  2. iが三で割って二余る数なら、i回目にはBを指す。
  3. iが三で割り切れる数なら、i回目にはi/3回目と同じ手順を指す。

まず、AAAとBBBのような三手順が全て同じということは絶対にありません。ABABABのような、六手順で、二手順を三回繰り返すようなものが存在しないことも構成から明らかです。問題はABXABXABXのような九手順で、三手順を三回繰り返すようなものがないかですが、そういうのがあるとするとXが全部同じだということになり、三手順すべて同じものはありえない話と矛盾します。以下同様にして、3(3n+1)手順や3(3n+2)手順で同一手順が三連続することがないのは構成から明らかであり、9n手順で同一手順が三連続するパターンがないことは3n手順でそういったものがないことから示されます。

メモ:読んでいない(というか手に入れることができておらず読めていない)論文

  • ローグライクゲームで、「残り体力がXであるとき、脱出できるか?」はNP完全(武永、2005)
    • どういう定式化をしたのか知りたいです。敵は動いたり発生したりしない(ので指数的に長い手順は発生しない)・武器や防具が存在する(のでどの敵から倒すべきかは簡単には決まらない)、あたりでしょうか?World Wide Adventureを思い出します。
  • ローグライクゲームで、空腹度も考えるとPSPACE完全(武永ら、2007)
    • PSPACE完全ということは何かしらの可逆なギミックがあるはずで、どういう定式化をしたのかが知りたいです。無限に敵がわく・その敵の肉を食べることで空腹度を回復できる・ボス敵を倒すためには時間がかかるので途中で雑魚敵を狩って空腹度を回復する手順が挟まる(ので指数的長さの手順が発生しうる)、とかなのかな?
  • 日本ルールの囲碁はEXPTIME完全(Robson, 1983)
    • 日本ルールのコウ(劫)ルールが重要な役割を果たしているらしいのですが、あまり自明ではないため読みたいです。
  • 倉庫番問題のPSPACE完全性をGeneralized geographyの帰着により示した論文(?)
    • なんか昔見た記憶があるのですが、見つかりません(知っている方がいらっしゃいましたら教えてください)。日本語論文だったような気がしますが、うろ覚えです。NP困難性を示したものは、(略証ですが)上原氏によるもの(LA 1999)があり、これの発展形だったように思います。なお、倉庫番はPSPACE完全だと示した最初の論文(Cullberson 1998)は線形拘束オートマトンの帰着です。

*1:自分の選択のみがクリアできるかに関わる、有限確定完全情報ゲーム

*2:二人零和確定有限完全情報ゲーム

*3:余談:対数を二乗すると対数ではなくなるので、対数領域の時はこの議論は使えず、L≠NLかはわかっていません。少なくとも、L⊆NL⊆L2であることはわかっています。また、空間計算量と時間計算量の関係によりL⊆Pであることがわかります。一方、2log x多項式ですが、2(log x)2は超多項式になるため、L2はPに含まれるとは限りません。それとは無関係に、NL完全問題(例えば有向グラフの二点間到達可能性問題)を多項式時間で解く方法(例えば深さ優先探索多項式空間を使うがPなのでこれは許される)は知られているので、NL⊆Pであることがわかっています。

*4:二コリの登録商標です。

*5:メガハウス登録商標です。

*6:Demaineらにより、2016年に示されました。

*7:双玉図式では、最後の審判に代表される、ルールの不備が指摘されています。

*8:終局判定に"両者の同意"なるものが必要になるなど、定式化の障害となる点が残ります。

*9:将棋はEXPTIME完全とする論文では千日手を考慮していません。

*10:あらゆる局面は指数個しかなく、これを(三回)網羅すれば必ず終局するので、手順の長さ自体は指数的な長さに収まります。

*11:実際、最後の審判の作意手順はそれを意図したものです。