錯誤の代償(適当

昨日のエントリは深夜に書いたせいかほどよく錯誤していたorz
いきなり詰み局面から着手して巻き戻そうとすると、話が爆発するのは当然だ。
昨日のエントリで

例えば、ノードn、○の手番でセル(5,5)から(9,5)にかけて

　○○＿○○

と並んだ(「＿」は空白）ならその5セルがnの次の局面で○が勝利するための必要十分条件であり、その位置と内容を記憶する。それら以外のセル内容は何であれ○の勝利を覆し得ないのでDon't careと置く。

としたとおり、ゲームの終了(実際に勝負がつくこと)ノードから話を始め、あくまでそういう終了の仕方限定の必要十分条件を求めることに問題を縮小すれば、計算量もまた現実的な規模に縮小できる。
わざわざ太字にしてまで強調した部分を自分自身が無視していたという、、

錯誤2

駄目だった。
上の問題を定式化すると

n1->n2->n3という遷移でpが勝利した場合、n3において成立した勝利条件は(ここでのゲームの仮定の下では)

• (セルの空間的範囲)×(その中の駒の種類)

として記述できる。
このとき、n1においてどのセルの内容がn3におけるpの勝利に無関係か。

だが、太字部分を真に受けると簡単に解ける反面、結果が自明すぎて無意味(だから今日の昼の考えは駄目)。一方、太字部分を無視して広く一般的にpの勝利に無関係なセルを探そうとすると、そのようなセルはpの駒、-pの駒、空白の何だっていいわけで、実際変えてみるとn2以外のノードに遷移して、以降の展開は予測困難(n3とは似ても似つかないノードが無数に発生してその末端ノードでp/-pの勝敗が決まる)ので昨晩の話になる。
この際下手な考えは不要で、普通にdf-pn(証明数と反証数に基づく反復深化手法)の使い所っぽい。