探索の並列化
一つの探索木Tを、N CPUで分担して行う探索と、1 CPUでシーケンシャルに行った探索とは結果が一致して欲しい。今日わ、そうするための必要十分条件におそらくｶﾅｰﾘ近いであろう十分条件を明らかにしてみ鯛。
定義
窓（αβウィンドウ）と探索結果の両方に、クリーンとダーティーの概念を導入する：
- クリーンな窓
- 探索木Tを根rからノードnまでトラバースした結果得たαβウィンドウであって、rからnまでをαβ法に従いシーケンシャルかつ省略（ノードのスキップ）無くトラバースして得る窓と一致する保証があるもの
- ダーティーな窓
- クリーンな窓である保証が無い窓。
- クリーンな探索結果
- 探索木Tの部分木T'の探索結果であって、T'をクリーンな窓wの下でαβ法に従いシーケンシャルかつ省略無く探索して得た結果と同等である保証があるもの*1
- ダーティーな探索結果
- クリーンな探索結果である保証が無い探索結果。
また、探索を遂行する主体として、Tを分担して並列探索するスレーブ（複数）と、それらに仕事を割り振るマスタ、という区別を考える。スレーブには他のスレーブに仕事を割り振る機能は無い。マスタとスレーブへのCPU割り当てはここでは特定しない*2。
例
- マスタが行う探索で、根からノードnに至るまでの間にスレーブに探索を割り当てず自力で探索した場合、nの入り口におけるαβウィンドウはクリーンな窓である*3。
- 部分木T'以下の探索をクリーンな窓とともにスレーブに依頼して得た探索結果はクリーンな探索結果である*4。
- 部分木T''の探索結果であって、その結果を得る際、T''の中でトラバースをスキップしたノードn''があるものは、少なくともn''以下の探索結果が明らかになるまでの間はダーティーな探索結果である*5。
- 探索木Tを根rからノードnまでトラバースした経路の中にダーティーな探索結果をもつノードが全く含まれなかった場合、nの入り口におけるαβウィンドウはクリーンな窓である。
ダーティーな窓の拭き方
上の定義や例でわかるとおり、ダーティーな窓や探索結果はいったん生じると引き続く窓や探索結果もダーティーになってしまう。
しかし、ダーティーな探索結果を、再探索することなくクリーンな探索結果同然に活用できるケースがある。
- クリーンな窓[a, b)の下で行ったn''以下の探索結果がαカットでもβカットでなかった場合、以降、そのとき得た評価値vを包含する任意の窓[a'', b'')の下で、n''の評価値をvとして良い。
∵res''がもつ評価値vは、この場合n''以下の部分木のPVの評価値（＝正確なミニマックス値）であるから。 - クリーンか否か不分明な窓[a'', b'')の下で行ったn''以下の探索結果がβカットであった（すなわち戻ってきた評価値vが、v≧b''であった)場合、[a'', b'')に包含される任意の窓の下で、n''の評価値をvとして良い。
∵vは正確なミニマックス値でないが、当該状況で必ずβカットを引き起こす。それが結論ということでおk - クリーンか否か不分明な窓[a'', b'')の下で行ったn''以下の探索結果がαカットであった（すなわち戻ってきた評価値vが、v＜a''であった)場合、[a'', b'')に包含される任意の窓の下で、n''の評価値をvとして良い。
∵vは正確なミニマックス値でないが、当該状況で必ずαカットを引き起こす。それが結論ということでおk*6 - クリーンか否か不分明な窓[a'', b'')の下で行ったn''以下の探索結果res''は、当の窓[a'', b'')がノードn''入り口でのクリーンな窓[a, b)を包含するとわかって以降は、クリーンな窓[a, b)を包含する任意の窓の下で、評価結果として通用する。
∵res''がもつ評価値vは、この場合n''以下の部分木のPVの評価値（＝正確なミニマックス値）であるから。
このように、スレーブへの探索の依頼から少し遅れて得るn''以下の探索結果res''は、n''入り口でのクリーンな窓が明らかになる等の特定条件の下で、再探索することなくクリーンな探索結果同然に活用できることがあるのだ☆
再探索することなく活用できるのであるから、これは辞書にしておく価値が大いにある。一方、探索結果の辞書の存在を前提とすれば、探索木T全体をαβ法にしたがい根から高速に再トラバース可能である。
ので、スレーブに依頼したノードn''の探索の結果は、得られ次第ダーティーかクリーンかを気にせずどんどん辞書化し*7 *8、探索木T全体を渡り終えたら、再びTを根からαβ法に従いトラバースしつつ、次の処理を、その時点での、窓がクリーンな窓でなくなるところまでやれば宜しい:
- スレーブが探索中のノードn''に行き当たったなら、n''をスキップしてn''の兄弟ノードに進む*9
- n''の入り口におけるクリーンな窓に基づき、辞書から引いた（ダーティーだった探索結果）res''がクリーンな探索結果であるか判定し、クリーンと判定されればその結果をn''以下の探索結果として採択し、n''の次の兄弟ノードに進む。
- 辞書から引いたres''がクリーンと判定されなかった場合、n''以下をクリーンな窓に基づき再探索する。
- 辞書に載っておらず、スレーブが探索中でもないノードn'''に行き当たれば、それは未探索のノードなので新規探索する。
なお、新規探索や再探索は、マスタ自身が探索するか、手すきのスレーブに依頼する*10
以上を続け、窓がクリーンな窓でなくなったらどうするか？処理を止めることを望まないならTのトラバースを続け、スレーブに依頼したノードn''の探索の結果は、得られ次第ダーティーかクリーンかを気にせずどんどん辞書化する。
T全体のトラバースを終えたら、再びTを根から再トラバース…
これを、クリーンな窓のままT全体のトラバースが完了するまで反復すれば良い。
クリーンな窓のまま推移するrからnまでのトラバース量（ノード数）は単調増加するので、まあいつか停止することは明らか。
以上を、並列探索に関するNB0AMG法とでも呼ぶことにする。
追記
早速追記だが、Tのトラバースを反復する過程でオーダリングが変化し、同じn''でも入り口における窓が変化したり、そもそもn''を通過しなくなることもある。つまり、Tのトラバースし直しによって、以前はクリーンな探索結果であったものが、無条件にはクリーンとみなせなくなる。そのような場合は、探索結果をTの再トラバース前にいったんダーティー扱いとし、上記の2.や3.の規則に従いクリーンな探索結果として復活させれば宜しい→これは一重に、クリーンな窓というものがオーダリング依存（ていうかかなり敏感）であるため。しかし本文の誤りを正したところ、辞書として記憶する内容からクリーン／ダーティービットは不要となったため、この節で述べたことは関係無くなった！
…ハズ
追記 1/16
申し訳ないが全面的に書き直させてもらった。
ある親の子を、同じαβウィンドウで一斉に探索するスプリットに重きをおく既知の方法とは別次元の世界を切り開いているのではないかと思ういや知らんけど*11
辞書が登場するから置換表とおなじようなものとおもいきや、よく考えたら置換表というのはクリーンな窓とクリーンな探索結果しか扱っていない。並列探索においては、辞書の正当性が別物の法則に支配されるのである。こういうのは面白い
追記 1/20
最終回答を得た↓
2013年1月20日のエントリ
上述のダーティーな窓の拭き方はこれに訂正される。
*1:wの下でシーケンシャルかつ省略無く行った場合の探索結果との評価値（ミニマックッス値）の一致が必要十分。
*2:しても良いが、今日のエントリには関係ない。
*3:シーケンシャルかつ省略無き探索故。
*4:T'以下はシーケンシャルかつ省略無くトラバースして更新される窓に基づき、シーケンシャルに探索される故。
*5:処理を止めることを望まないなら、マスタは、n''以下の探索をスレーブに仕事を割り振ったなら、結果が戻ってくるまで待つことなくn''をスキップしてTの残り（未トラバース）の部分の探索を続行せねばならない。このようにして並列探索では普通にノードのスキップが生じる。
*6:もちろん、ネガアルファ系アルゴリズムでは3.は生じず、かわりに2.が生じる。
*7:辞書には当然探索開始時の窓[a'', b'')およびダーティー/クリーンビットも記録しておく。
*8:辞書への追加は基本的にマスタと非同期に行えば良いが、マスタと同期して行いロックを削減する方法はある。ここでは省略。
*10:採用する処理分配アルゴリズムとそのときの条件による。スレーブに依頼した場合、その時点で窓はダーティーになる。
*11:年明けぐらい誇大妄想を許してもらいたい。
