審判込みの一般化詰将棋問題を考えよう　その①

ちゃんと書こうとしたらがっしゃがしゃになりました。

たすけて。

前回

uso-800-plus-alpha.hatenablog.com

１　趣旨とかの説明

（１）一般化詰将棋問題の説明

計算論においては、例えば素数判定のような問題の計算複雑性を調べる場合、入力するデータの大きさ（仮にNとする）と比べて、時間（計算ステップ数）がどのくらい掛かるのか（Nの多項式か指数関数か）だったり、空間（必要メモリ数）がどのくらい掛かるのかだったりを調べたりします。

将棋や詰将棋の場合、9×9マス＆40枚の駒という固定されたデータでは、上記の比較が出来ません。したがって、何らかの手段で「一般化」をしてやる必要があります。通常使われる方法は、n×nマス＆ $O(n)$ 枚の駒というマス目ベースの一般化です。（というかそれ以外知りません）

この設定の将棋盤駒で、何らかの局面を与えてやります。このとき、その与えられた局面が詰むか不詰か判定する問題を「一般化詰将棋問題」と呼びます。

それじゃ、「一般化詰判定問題」じゃないかと思いましたが、些末でしょうか･･･

今回は、一般化詰将棋問題に「最後の審判」を入れたときに何が起こるのかについて、考えてみます。

（２）構成するゲームの説明

今回は、”Provably Difficult Combinatorial Games”という論文の $G _ 3$ というゲームをベースに構成を行います。幸い、一般化詰将棋のEXPTIME論文でこの構成がなされているため、ルールや例示は、そちらから引用することにします。（ごめんなさい）

$G _ 3$ のルール

論理変数の集合 $A = \{ a _ 1, …, a _ k\}，B=\{b_1, …, b_k\}$ と $A∪B$ 上の積和形式の論理関数

$A-LOSE = A _ 1 ∨ A _ 2 ∨ … ∨ A _ p,$

$B-LOSE = B _ 1 ∨ B _ 2 ∨ … ∨ B _ q$

が与えられる。ただし、 $A _ i，B _ i$ は高々12個のリテラルからなる． $G_3$ のプレイヤーは交互に，先手はAの変数，後手はBの変数のうちの1変数の値を変更する．先手（後手）が変数の値を変更した後で，A-LOSE（B-LOSE）が真なら，先手（後手，括弧内それぞれ）の負けである．

つまり、

・先手が変更可能な変数と後手が変更可能な変数を準備する。

（※変数は論理変数なので、取り得る値は真か偽かの2値）

・それぞれの敗北条件を選言標準形の論理式として準備する。

で、

・交互に変数の真偽を1つ変更していく。

・変更後に自分の敗北条件を満たしてしまったら負け。

次に追加ルールについて

Robson(1984)は、 $G _ 1$ から $G _ 1’$ を構成していたのですが、このときに”A player loses if, after his move, ∃ some earlier move M such that all variables have the same values as after M.”という”no-repetiton rule”を追加していました。たぶん過去の同一局面を再現する手を指したら負けなのだと思うので、これをそのまま使うことにします。CONCLUSIONSを読む分にはそのまま使っても大丈夫だと思う。

$G _ 3$ + no-repetition rule を $G _ 3’$ と呼ぶことにします。

次回

uso-800-plus-alpha.hatenablog.com