計算複雑性理論では、一般化地理学はPSPACE 完全問題としてよく知られています。
導入
地理は、プレイヤーが交代で世界中の都市名を挙げる子供向けゲームです。各都市名は、前の都市名の末尾と同じ文字で始まっていなければなりません。重複は認められません。ゲームは任意の開始都市から始まり、プレイヤーがゲームを続行できなくなった時点で終了します。
グラフモデル
ゲームを視覚化するために、世界の各都市をノードとする有向グラフを構築することができます。ノードN 1からノードN 2 への矢印は、都市ラベルN 2が、ノードN 1の都市名の末尾の文字で始まる場合にのみ追加されます。言い換えれば、ゲームのルールに従って最初の都市から2番目の都市につながることができる場合、1つの都市から別の都市へ矢印を描きます。有向グラフの各交互のエッジは、各プレイヤー（2人プレイの場合）に対応します。パスを延長できなかった最初のプレイヤーは負けます。ゲーム（ミシガン州のいくつかの都市を含む）の図解を下図に示します。
一般化地理ゲーム（GG）では、都市名のグラフを任意の有向グラフに置き換えます。次のグラフは、一般化地理ゲームの例です。
ゲームをプレイする
ここでは、 P 1 を最初に移動するプレイヤー、P 2を2 番目に移動するプレイヤーと定義し、ノードをN 1からN nと名付けます。上の図では、P 1 の勝利戦略は次のとおりです。 N 1は、ノードN 2とN 3のみを指しています。したがって、P 1の最初の移動は、これら 2 つの選択肢のいずれかでなければなりません。P 1はN 2を選択します( P 1 がN 3 を選択した場合、P 2はN 9 が唯一の選択肢であるためそれを選択し、 P 1 は負けます)。次に、P 2 は、残っている唯一の選択肢であるため、 N 4を選択します。ここでP 1 はN 5 を選択し、続いてP 2 はN 3またはN 7を選択します。 P 2の選択に関係なく、P 1 はN 9を選択し、 P 2には選択肢が残っていないため、ゲームに負けます。
計算の複雑さ
一般化された地理ゲームにおいてどのプレイヤーが勝利戦略を持っているかを決定する問題は、PSPACE 完全です。
一般化された地理はPSPACEにあります
GG = { ⟨ G , b ⟩ | P 1は、グラフG上のノードbから始まる一般化地理ゲームにおいて勝利戦略を持つ} とします。GG ∈ PSPACEであることを示すために、どのプレイヤーが勝利戦略を持つかを決定する多項式空間再帰アルゴリズムを提示します。GG のインスタンス ⟨ G , n start ⟩ （Gは有向グラフ、n startは指定された開始ノード）が与えられた場合、アルゴリズムMは以下のように進行します。
M (⟨ G , n start ⟩) について:
- ノードn startの出次数を測定します。この次数が0の場合、プレイヤー1に利用可能な動きがないため、refuse を返します。
- n開始から 1 つのエッジで到達可能なすべてのノードのリストを構築します: n 1、n 2、...、n i。
- Gからn startとそれに接続されているすべてのエッジを削除して、 G 1を形成します。
- リストn 1 , ..., n i内の各ノードn jについて、 M (⟨ G 1 , n j ⟩)を呼び出します。
- これらの呼び出しすべてがaccept を返す場合、 P 1がどのような決定を下しても、P 2 は勝利する戦略を持っているため、reject を返します。それ以外の場合（呼び出しのいずれかがrejectを返す場合）、P 1 はP 2の成功する戦略をすべて拒否する選択肢を持っているため、acceptを返します。
アルゴリズムMは明らかに GG を決定します。これはPSPACE内にあります。なぜなら、消費される非自明な多項式空間は再帰スタックのみだからです。再帰スタックが消費する空間は多項式空間です。なぜなら、再帰の各レベルでスタックにノードが1つ追加され、レベル数は最大でnレベル（nはG内のノード数）だからです。これは本質的に深さ優先探索と同等です。
一般化された地理学はPSPACE困難である
以下の証明はデイヴィッド・リヒテンシュタインとマイケル・シップサーによるものです。[1]
GG のPSPACE 困難性を証明するために、 FORMULA-GAME問題 ( PSPACE 困難であることが知られている) を多項式時間 ( P ) で GG に簡約することができます。簡単に言うと、FORMULA-GAME 問題のインスタンスは、量化されたブール式φ = ∃ x 1 ∀ x 2 ∃ x 3 ... Qx k (ψ) で構成されます。ここで、 Qは ∃ または ڼ です。このゲームは 2 人のプレイヤーP aとP eによってプレイされ、2 人は交互に連続するx iの値を選択します。式 ψ が真になった場合はP e が勝ち、 ψ が偽になった場合はP a が勝ちます。式 ψ は、連言正規形であると仮定されます。
この証明では、簡潔にするために、量指定子リストが存在修飾子∃で始まり、存在修飾子∃で終わると仮定します。ψに現れないダミー変数を追加することで、任意の式をこの形式に変換できることに注意してください。
上記のようなグラフGを構築することにより、FORMULA-GAME の任意のインスタンスを一般化地理のインスタンスに縮小できることを示します。ここで、 P 1の最適戦略はP eの最適戦略と同等であり、 P 2の最適戦略はP aの最適戦略と同等です。
左の垂直のノードのチェーンは、FORMULA-GAME で変数の値を選択する手順を模倣するように設計されています。各ダイヤモンド構造は、量化された変数に対応します。プレーヤーは、各分岐ノードで順番にパスを決定します。最初の量化子は存在的であると想定したため、P 1が最初に進み、x 1がtrueの場合は左のノードを選択し、 x 1がfalseの場合は右のノードを選択します。次に、各プレーヤーは強制的に順番を取り、次にP 2がx 2の値を選択します。これらの交互の割り当ては左側に続きます。両方のプレーヤーがすべてのダイヤモンドを通過した後、最後の量化子は存在的であると想定したため、再びP 1の番になります。 P 1 には、グラフの右側へのパスをたどる以外に選択肢はありません。次に、P 2が移動する番になります。
グラフの右側に到達すると、フォーミュラゲームにおけるプレイ終了時と似た状態になります。フォーミュラゲームでは、ψ が真であればP e が勝ち、ψ が偽であればP a が勝つことを思い出してください。グラフの右側では、 P e が勝つ場合のみP 1 が勝ち、P a が勝つ場合のみP 2が勝つことが保証されます。
まず、 P a が勝った場合、 P 2 も必ず勝つことを示します。P a が勝った場合、 ψ は偽です。 ψ が偽の場合、不満足な節が存在します。P 2は勝つために不満足な節を選択します。次に、P 1の番になると、 P 2が選択した節のリテラルを選択する必要があります。この節のリテラルはすべて偽であるため、左の垂直チェーンで以前に訪れたノードには接続されません。これにより、P 2は左チェーンのダイヤモンド内の対応するノードへの接続をたどり、そのノードを選択できます。ただし、P 1は隣接するノードを選択できなくなり、負けます。
ここで、 P e が勝った場合、 P 1 も必ず勝つことを示します。P e が勝った場合、ψは真です。 ψ が真であれば、グラフの右側にあるすべての節に真のリテラルが含まれます。P 2 は任意の節を選択できます。そして、P 1 は真であるリテラルを選択します。そして、それが真であるため、左の垂直ノードの隣接するノードは既に選択されているため、P 2 は何もできず、負けます。
平面一般化地理学はPSPACE完全である
一般化地理学は、平面グラフ上でプレイした場合でもPSPACE完全である。以下の証明は[1]の定理3による。
平面GGはGGの特別な場合であり、GGはPSPACE内にあるため、平面GGはPSPACE内にあります。平面GGがPSPACE困難であることを示すことが残っています。これは、任意のグラフを平面グラフに変換する方法を示すことで証明できます。このグラフ上でGGをプレイすると、元のグラフと同じ結果になります。
これを実現するには、元のグラフの辺の交差をすべて除去するだけで済みます。3本の辺が1点で交差せず、交差する辺のペアが同じゲームで同時に使用されないようにグラフを描きます。これは一般には不可能ですが、FORMULA-GAMEインスタンスから構築されたグラフでは常に可能です。例えば、交差に関係する節の頂点からの辺のみを持つようにすることができます。ここで、各交差を次の構成に置き換えます。
結果は平面グラフとなり、元のグラフと同様に同じプレイヤーが勝利を強制できます。つまり、変換後のゲームでプレイヤーがVから「上」に移動することを選択した場合、両方のプレイヤーはWまで「上」に移動し続けるか、即座に負けるかのどちらかになります。つまり、変換後のゲームでVから「上」に移動することは、元のゲームにおけるV→Wの移動をシミュレートすることになります。V→Wが勝利の動きであれば、変換後のゲームでVから「上」に移動することも勝利の動きとなり、その逆も同様です。
したがって、変換されたグラフ上でGGゲームをプレイすると、結果は元のグラフと同じになります。この変換には、元のグラフの辺の交差数の定数倍の時間がかかるため、多項式時間がかかります。
したがって平面GGはPSPACE完全である。
最大次数3の平面二部グラフ
最大次数3の平面二部グラフ上で行われるGGは、次数が3より高い頂点を次数が最大3の頂点の連鎖に置き換えることで、依然としてPSPACE完全である。証明は[1]にあり、次の構成を使用する。
片方のプレイヤーがこの構造への入口のいずれかを使用した場合、もう一方のプレイヤーがどの出口を使用するかを選択します。また、中心の頂点は常に通過するため、この構造は一度しか通過できません。したがって、この構造は元の頂点と同等です。
エッジ地理
GGの派生形として「エッジ・ジオグラフィー」と呼ばれるものがあります。これは、プレイヤーが移動した後、通過したエッジが消去されるというものです。これは、プレイヤーが移動した後、以前いた頂点が消去されるオリジナルのGGとは対照的です。この観点から見ると、オリジナルのGGは「頂点ジオグラフィー」と呼ぶことができます。
辺地理はPSPACE完全である。これは頂点地理と同じ構成で証明できる。[2]
無向地理
いずれかの地理ゲームを無向グラフ（つまり、辺が両方向に移動できるグラフ）上でプレイすることも考えられます。Fraenkel、Scheinerman、Ullman [3]は、無向頂点地理は多項式時間で解けるのに対し、無向辺地理は最大次数3の平面グラフであってもPSPACE完全であることを示しています。グラフが二部グラフの場合、無向辺地理は多項式時間で解けます。
結果
GG がPSPACE 完全であることを考えると、 P = PSPACEでない限り、GG における最適なプレイのための多項式時間アルゴリズムは存在しません。しかし、チェスなど、特定のゲームでは局面の数が有限であるため、他のゲームの複雑さを証明するのはそれほど容易ではないかもしれません。そのため、 PSPACE 完全な問題へのマッピングを定式化することは困難（または不可能）です。それでも、特定のゲームの複雑さは、一般化（例えば、 n × n の盤面への）によって分析できます。GGの完全性の証明の系として、 一般化された囲碁の証明については、参考文献を参照してください。
参考文献
- ^ abc Lichtenstein, David; Sipser, Michael (1980年4月). 「囲碁は多項式空間困難である」(PDF) . Journal of the ACM . 27 (2): 393– 401. doi :10.1145/322186.322201.
- ^ Schaefer, Thomas J. (1978). 「いくつかの2人完全情報ゲームの複雑性について」. Journal of Computer and System Sciences . 16 (2): 185– 225. doi :10.1016/0022-0000(78)90045-4.
- ^ フランケル, アヴィエズリ; シェイナーマン, エドワード; ウルマン, ダニエル (1993). 「無向エッジ地理学」.理論計算機科学. 112 (2): 371– 381. doi :10.1016/0304-3975(93)90026-p.
- マイケル・シップサー、「計算理論入門」、PWS、1997 年。
