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

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

前提

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

方向性

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

なんていうか、

局面の辞書を書いてみたんですが、コレまともに使えるようにするには、詰みの必要十分条件を求めるルーチンが欲しいっすね…
例えば盤全体は11×11=121セルなのに、6×6セルの範囲内の駒の配列だけで詰みが成立する場合、3^(121-36)=3E40もの無駄な組み合わせについて無駄な記憶領域が必要になってしまいかねないということに今更気づく漏れﾊﾞｶｽｗｗｗｗｗ
整数論の定理を証明する類のAI(それそのものよりはまだ簡単でいいと思うが)が本当に必要っぽい。さすがに神であらせられるyaneura○氏の言うことには含蓄があるます(整数論の定理を証明するAI云々は今の問題とはちょっと違う文脈での指摘だったけど)。

無いから仕方なく作ろうとする

目標とする局面辞書は、詰みに関係ない駒の位置がDon't careなビットマップの集まりだ。(ととりあえず現段階では考える。もちろん工夫の余地は多大にある。)
例えば、ノードn、○の手番でセル(5,5)から(9,5)にかけて
　○○＿○○
と並んだ(「＿」は空白）ならその5セルがnの次の局面で○が勝利するための必要十分条件であり、その位置と内容を記憶する。それら以外のセル内容は何であれ○の勝利を覆し得ないのでDon't careと置く。

さて、いま、ノードn1→n2→n3という一連の遷移の最後でプレイヤーpによる詰みが成立した(対戦相手-pが詰まされた)とする。
-pが、仮にn1→n2遷移のかわりにn1→n2'遷移(n2≠n2')を行ったとすれば、n1→n2→n3によるpの勝利の可能性は無くなる。ただしそれとは別の、n2'以降のノード遷移(n2'を根とする部分ゲーム木内)でpの勝利がもたらされるかもしれない。

pの勝利が、n2'以降-pがどのような手を選んでも覆らない(-pがどういう合法手を指そうとも、pが-pの勝利を成立させないまま葉ノードまで誘導する手筋を見出せる)なら、n2'もまたpの必勝ノードである。

さらに、n1からの-pの合法手で得られる全てのノードについて同様であれば、n1もまたpの必勝ノードである。

このようにして、原理上は、任意の勝負において現れたp必勝ノードを全て得ることができる(また副産物としてそれら以外にも多数のp必勝ノードが得られる)。

現実問題としては「pの勝利が、n2'以降-pがどのような手を選んでも覆らない」ことを証明することはn2'以降のノード数の爆発により一般に不可能だ。