3分クッキング

はい、ではこちらに完成した巻き戻しエンジンが用意してありますん

巻き戻しに大切なこと

巻き戻しはとにかく高速にやりたい。バット、複雑なアルゴリズムは実装したくない。
1局面戻る度に詰みか否かの探索を反復するような実装では遅すぎる。
また、プログラムが{複雑さ}×{複雑さ}になってプログラムする人(＝漏れ)の知能で成し得る範囲を超える事態は避けたい。
というわけで、詰んだ局面から1段戻った局面のみ与える前提で、平均的に一瞬で詰み判定を終えてしかも単純なアルゴリズムを狂ったようになって考えるスレ。

詰みと葉

先手(後手)の詰みとは先手(後手)が以降どのような合法手を指そうとも、後手(先手)が以降ミスしない限り後手(先手)の勝利を覆せない状態のこと。個々の詰みは、完全ゲーム木が与えられた下で、それに含まれるノードとして記述される。
詰みとゲームの終了(実際に勝負がつくこと)をここでは区別する。ゲームの終了条件は、あくまでゲームのルールにのっとりプレイヤーのどちらかが合法手を全く指せなくなること、とする。
ゲーム木の葉ノードは、詰みではなくゲームが終了した状態の局面にあたる(とする)。ゲーム木業界のコンセンサスはよく知らんが、多分こういう定義でいいんじゃね？

よりkwsk

ゲームの妥当なルール一式が与えられると(完全)ゲーム木が定まり、そのルールの下での任意のプレイはゲーム木の根から葉に向かうパスとして表現される(ループになることもある)。
ゲーム木のノードは根からの深さ(経由するノードの数)が偶数のものと奇数のものに分けられるが、偶数のものは先手が手番の局面、奇数のものは後手が手番の局面をそれぞれ表す。長いのでここではそれらを単に偶ノード、奇ノードと呼ぼう。根ノードは根からの距離=0の偶ノード。
まず、簡単のためループは全部展開して考えよう。つか本来二人零和有限確定完全情報ゲームではループを展開しようが何をしようが完全ゲーム木の高さは有限のはずでこの操作は妥当。
こうした準備の下で、あるノードNが詰みであるとは、次のように定義される。

• Nを根とする部分木の葉の全てが偶ノードか奇ノードのどちらかである。

全て偶なら先手の詰み、全て奇なら後手の詰み。

ﾏﾃ;

よく考えたら上の定義は詰みの定義としては厳しすぎる。
詰ませようとする側がミスしようが何をしようが合法手を指し続ける限りいずれ必ず勝つことまでは要求されない。詰ませようとする側はミスをしない、これが大前提となる。
しかし手がミスかミスでないかをゲーム木の葉まで完全に読み切らずに判断できるぐらいなら、そもそも思考ルーチンや評価関数の有り様で悩むことはない。
局面Nが詰みか否か判定するという目標は修正した方がいいようだ。