YBWCの効率的な実装
#オセロAI の #並列化 に使う #YBWC という #アルゴリズム は、効率的にうまく実装するのが難しい気がする。
効果があったこと、なかったこと、考えていることなどをここに(雑多に)まとめる。
親の探索打ち切りを子に伝える
親から探索中フラグとしてboolのポインタ(または参照)を子に伝えて、子は探索しながらそれを見れば良い
親の親とか、親の親の親とかのフラグも伝えなければいけないので、vectorにフラグ(ポインタ)を格納して、vector内で一つでもfalseのフラグがあれば探索を打ち切るようにした
子のfail highを他の子に伝える
#NWS でYBWCしたときは、子が(親にとって)fail highしたらただちに他の子の探索を打ち切って良い。子の間でboolポインタを共有して、fail high時に子が探索中フラグ(boolポインタ)の指す値を変更することで他の子の探索を終了させると良い。
実装としては、親が管理するフラグを子で共有し、子の探索終了時にfail highが確認できたらフラグをオフにすることで、ただちに他の子の探索を終了できる。
子のfail highをメインスレッドに伝える
YBWCで子をsplitしたスレッドは、いくらかの子を手元に残しておいて、splitしたタスクを待つ間にそれらを探索するという方法を取る。このとき、splitした子がfail highしたら自分の探索をただちに終了したい。やはりここもboolポインタを共有しておく必要がある
実装としては、上の子で共有するフラグを親の(子を待つ時間に行う)探索でも探索中フラグとして使えば、親の探索も即座に打ち切れる。