どうぶつしょうぎ>後退解析

全局面の生成ができたので、次は「後退解析」で、全局面の解析を行なう。

「後退解析」とは、評価が確定した局面から順に順に局面の評価を確定していく処理だ。
評価とは 勝ち・負け・引き分けのいずれかだ。
最初は全ての局面の評価を不明(UNKNOWN)にしておき、ある局面について、その子局面を生成し、
・子局面のどれかひとつが勝ちであれば、勝ち
・子局面の全てが負けであれば、負け
という処理を行い、局面の評価が変化しなくなるまで繰り返せばよい。
このとき、問題になるのはどの局面を調べるか?ということだ。
全局面数がそう多くなければ、全局面について処理を行なっても速度的に問題はないが、局面数が膨大な場合はちょっと遠慮したくなる。
どうぶつしょうぎの場合は末端局面を覗いても約100M局面もあるので、かなり膨大だ。
どうしよう?