四目並べとその別種の解析
長原詩桜 (指導教員：長尾篤樹)

1

はじめに

2.2

二人完全情報ゲームに対する先手必勝手順の計算両に関する研究として，一般化五目並べの PSPACE 完全性が証明されている [3]. この証明には, 一般化しりとりからの多項式時間帰着が使われている.
一般化しりとりは, 以下の設定で行われるゲームである. 有向グラフの頂点上で行う 2 人ゲームで, 先行は開始頂点上にあるマーカーを, 有向辺で隣接している頂点の中で好きな頂点へ移動させる. 次のターンからは, プレイヤーは交互にまだ一度もマーカーが置かれていない頂点へマーカーを移動させる. 移動できるのは, もといた頂点からその頂点への有向辺がある場合のみである. 最初に動かせなくなったプレイヤーが負ける.
この一般化しりとりの入力として与えられるグラフを, 五目並べの盤面に変換することで先行研究ではPSPACE 困難性を証明している. 一般化しりとりは, そのグラフが以下の制約を満たしていても PSPACE 完全であると知られている.[2]理論計算機科学の分野では, 計算の複雑さを定量化して, ある問題の複雑さを解析する研究が行われている.
計算量理論は, ゲームを考える際に応用される. ゲー
ムではそのルールに従い適切な挙動を行い, 目的 (パズルが解ける/勝利する) を達成できるかどうかを判定する事が複雑な問題になることがあるため, ゲームを対象とした問題がどの計算量クラスに入るかが議論されている. このような観点から, 複雑な計算量クラスに属するゲームほど難しいゲームであると考えられる. 本研究では, 一般化しりとりからの多項式時間帰着を示すことにより, 一般化 Quarto!の先手必勝判定問題の計算量クラスが PSPACE 完全であることの証明をした.

2

数学的準備

この章では一般化 Quarto!の PSPACE 完全性を証明するにあたって必要な, Quarto!のルールと, 一般化しりとりからの帰着によって一般化五目並べの PSPACE 完全性が証明された先行研究を紹介する.

2.1

PSPACE 完全性を示した研究

1. 平面 2 部グラフ.
2. すべての頂点は格子点上に位置し, 辺は水平または垂直.
3. すべての辺の長さは 1 または 2.
4. 同じ点から始まる 2 つの辺のなす角は 180 度
5. 開始頂点を除くすべての頂点は入次数と出次数がどちらも 1 以上.

Quarto!とはQuarto![1] はスイスの数学者ブレイズ・ミュラーによって考案された 2 人用ボードゲームである. このゲー
ムは,4 × 4 の盤面と 4 種類の特徴 (色, 形, 穴の有無, 高さ) を組み合わせた 16 個の駒を使用する. まず先手が,相手の置く駒を選択する. 次に, 後手は選ばれた駒を盤面の空いている好きなところに置き, 先手の置く駒を選択して先手の番に戻る. これを交互に繰り返し, 同じ特徴の駒の 1 列を完成させたプレイヤーが勝利する. このゲームの四目並べとは違う特徴的なルールは, 自分の置く駒を対戦相手が選ぶことである.
Quarto！は四目並べの別種と言える．通常の四目並べは先手必勝ですぐに勝負がついてしまう簡単なゲームである一方, Quarto!の必勝戦略はまだ確認されていない．そのために, 本研究では Quarto!の必勝手順に関する計算量を解析する.
本研究では議論を簡潔にするために駒の種類を〇と×の 2 種類に限定し, 盤面を n × n に拡張した一般化
Quarto!について考える. この一般化 Quarto!の任意の盤面における先手必勝判定問題の計算量の解析を行う.
一般化 Quarto!の勝利条件は, 同じ駒を縦・横・斜めのいずれかで 4 つ並べることである. 以上の条件を元に，一般化 Quarto!を以下のように定義する．

この制約の上では, すべてのグラフは以下の部分グラフだけで構成される.

図1

一般化しりとりのグラフを構成するパーツ

この部分グラフと同じ働きをする一般化五目並べの部分盤面を作ることで, 任意の一般化しりとりの入力を一般化五目並べの盤面へと変換することができる. この部分盤面のことをガジェットとよぶ.
グラフの頂点間の移動を五目並べ表現する方法として，以下のような変換が提案されている.

入力：Quarto!の盤面
出力：入力された盤面に先手必勝手順が存在するな
らば yes, そうでないならば no.
一般化 Quarto!は有限の盤面に高々 1 回しか駒を配置できないため, 任意の盤面において先手必勝かどうかを判定するためには, 入力サイズ n に対し O(n2 ) 領域あればよい. よって, 一般化 Quarto!は PSPACE に属することが簡単に確認できる.

この盤面で白が 1 または 1a 以外に置いた場合, 次の黒手番で 1 に置かれるため白の負ける状況が確定する.
白が 1a に置いた場合, 次の黒手番で潜在的な脅威である 5 に置かれるため, 白の負ける状況が確定する. 白が1 に置いた場合, 黒は負けないために 2 か 2a に置く. す1なわち, この盤面で白が効果的に黒の勝利を妨げるためには, 白は 1 に置く必要がある. このようにして 1,2,3,4と順に石が置かれて五目並べの盤面が変化していく.
長さ 1 の辺と, 入次数が 1, 出次数が 2 のガジェット
はこのようになる.
図 7 180 度の合流の頂点
図 8 90 度の合流の頂点
図2

長さ 1 の辺
図33

図 1 の一番右の頂点に対応するガジェットを, 分岐ガジェットと呼ぶ. 分岐ガジェットも完成すると, 以下の補題を使うことにより, 次の証明が完成する．
Lemma 1. 任意の長方形に対し, ○もしくは×が縦・横・ナナメに 4 連続しない配置が存在する．
Theorem 2. 一般化 Quarto!は PSPACE 完全である．

入次数 1, 出自数 2

Quarto!の多項式時間帰着

Quarto!は五目並べと同様，格子盤面上に二人のプレイヤーが交互に駒置くゲームであるため，先行研究の証明を参考に一般化 Quarto!の計算量解析を行う. つまり, 一般化 Quarto!の PSPACE 完全性を証明のために, 一般化しりとりからの多項式時間帰着を試みる. 一
般化五目並べと同じように, グラフを構成する各部分グラフを Quarto!での部分盤面に変換する. Quarto!のガジェットの変換を考える上でも五目並べのように, 相手の勝利を阻止しながらも自身の勝利に近づく手を取ることで相手に妨害を強要させ, 盤面を変化させていく.

図4

Proof. 一般化 Quarto!が PSPACE に含まれる事に関しては既に議論済みである．
よって, 一般化 Quarto!が PSPACE 困難であることを示す．一般化しりとりの入力グラフの各頂点は, それぞれ図 5–図 8 のように固定長の一般化 Quarto!のガジェットに変換でき, 一般化しりとりの入力グラフの頂点の数の線形時間で一般化 Quarto!の盤面に変換できる. また, 補題 1 より, 一般化しりとりのグラフに変換した一般化 Quarto!の頂点と道に対応する場所以外は,すべて, 勝利条件を満たさないような駒で埋め尽くすことができる. 以上から, 一般化 Quarto!の盤面を作ることにより, 一般化 Quarto!のプレイヤーは元の一般化しりとりのグラフから逸脱した場所に駒を置くことはできないため, 一般化しりとりで先攻が勝利するとき, またそのときのみ, 一般化 Quarto!でも先攻が勝利する.
よ っ て, 一 般 化 Quarto!は PSPACE に 含 まれ,PSPACE 困 難 で も あ る た め,PSPACE 完 全 で ある.

長さ 1 の辺

この盤面で 1 に×の駒が置かれたとする. このとき×のリーチが発生し, 相手に置かせる駒は必然的に〇になる. 次のプレイヤーはどこに〇の駒を置いても必ず〇のリーチが発生する盤面であれば,2 以外に〇の駒を置くと×と〇の両方でリーチが発生して, 次のターンで相手にどの駒を渡しても負けが確定する. したがって, 次のプレイヤーは〇の駒を×のリーチを防ぐことができる
2 に置く必要があり, それによって〇のリーチが発生し,その次のプレイヤーに置かせる駒は×に限定される.
このような操作に基づいて図 1 に挙げた一般化しりとりに存在する各頂点を,Quarto!の各ガジェットに変換する. 各変換を以下の図 5–図 8 で紹介する．

4

まとめと今後の課題

一般化しりとりを一般化 Quarto!に帰着させるための 6 種類のガジェットのうち,5 種類のガジェットを構成した. また, 残りの一つである分岐ガジェットが構成できれば, 一般化 Quarto!が PSPACE 完全であることを証明した.
駒が〇と×の二種類では分岐ガジェットを構成することは難しく, 駒のもつ特徴を二属性に増やし, 四種類の駒の場合を検証をする必要があると考えられる.

参考文献

図5

長さ 2 の辺

図6[1] Quarto - jeu de réﬂexion et de société - gigamic
https://www.gigamic.com/jeu/quarto.
[2] David Lichtenstein and Michael Sipser. Go ispspace hard. In 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), pages
48–54. IEEE Computer Society, 1978.
[3] Stefan Reisch. Gobang ist pspace-vollständig.
Acta Informatica, 13(1):59–66, 1980.

曲がる頂点

これらは図 1 の一番右の頂点以外の変換である. 一
般化しりとりのグラフの長さ 1 が Quarto!の 9 マスに相当する. 一か所のみに×または〇でリーチを作る. これが図 1 の一番左の開始頂点に対応する.

2