ウホッ、いいアイデア！！

よさげなアイデアが浮かんだので、局面Nが詰みか否か判定するという目標は修正しなくていい。

前提

学習すべきパターンの集合が学習の進度依存で変化するような学習システムは学習の挙動が予測し難いので避けるべき。特に今の構想だと集合の中身が入れ替わる形で変化した場合、期待する学習結果から外れたところに収束する恐れが以下略
あくまで学習が進行しても学習すべきパターンが増えこそすれ、変化はしないやり方を目指す。この実現のためにはあるノードが詰みか否かを、厳密なやり方で(多少時間がかかってもいいがパーセプトロンを使わずに)判定する必要がある。

方向性

さて、巻き戻しに関してゲーム木だけを前提とする一般論はやめて(無理っぽいので)、以下必要に応じてゲームの詳細に立ち入っていく。まず、盤が2次元配列として記述でき、そのセルに駒を配置するタイプのゲームだとしよう。
黒が座標(x,y)に駒を配置したことによって葉ノードに達した(白の合法手がなくなり黒の勝ちで終了した)とすれば、勝負が決した(葉ノード)または詰んだ局面の1つ前の局面限定で、時間計算量O(n^2)で済む黒の詰み可能性のテストを構成できるんだなこれが。
ここでnは盤の長辺の長さ(セル数)。これはゲームを決めたとき決まる定数なので、時間計算量はO(1)であるとも言えてものは言い様だ。
このテストによりどれぐらいの割合でガチの探索をせずに済むかはいまいちよく分からないが、これに賭けることにする。
以下ガチ実装モードになるのでしばらく沈没(ﾌﾞｸﾌﾞｸ