FPGAでコンピュータ将棋を作る(4)
■ 並列化αβ探索
αβ探索をN台のマシンで並列化して行なう場合、√Nぐらいの効果しか無いとされる。しかしそれは粒度の大きな分割を行なう場合の話だ。
FPGAのように他の探索コアが同一チップ上にあって、通信遅延がほぼ0だと仮定できる場合、並列化効率はもっと良い。
今回は、その並列化効率を試算してみよう。
通常のmini-max法でD手先まで全幅探索を行なう場合、(80)**D の局面を調べなければならない。80というのは将棋の局面に対する平均的な合法手の数、**はべき乗を意味する。
αβ探索では、調べなければならない局面の数は、だいたいこの平方根ぐらいになる。(sqrt(80))**D ≒ (8.9)**D である。このとき、beta cutが何回ぐらい行なわれているかと言うと、(私の実験のよると) (8.9)**D / 80 程度である。だいたい、beta cutの回数は合法手の数に反比例するようである。
beta cutが行われた場合、探索している他のコアにそれを伝達し、探索中の内容を破棄すると仮定しよう。ここでは、その情報の伝達コストは0と仮定しよう。
8コアで探索していると、10回に1回ぐらいの割合でこのbeta cutが発生し、そのときに探索していた内容が無駄になるという計算になる。つまり、(大雑把に計算するなら)1/10の割合で無駄が出るだけで、(指し手生成器は事前にbeta cutが行われたときの局面まで事前に準備できているとすれば、そこでのロスはないので)8コア×90% = 7.2倍の速度アップとみなされる。√8 ≒ 2.8倍と比べると大差だ。
ここで、αβ探索に加えて、反復深化やnull moveなどによってbest firstっぽく探索するように修正した場合はどうだろう？このとき、(sqrt(80)/2)**D ぐらいの探索局面(stand-patを評価する局面数)に収まるようである。*1
このとき、どれくらいの頻度で beta cutが行なわれているかと言うと、私の実験によると 5**D / 10ぐらいの回数のbeta cutが行なわれれば、5**Dぐらいの探索局面となるようである。つまりは8コアで探索すると(概算で)1.25回に1回の割合で探索中の内容が無駄になる計算になる。かなり性能が悪い。
とまあ、効率的に探索すればするほど台数効果が乏しくなって行くという当たり前の結論に行きつくのだが、台数の平方根というのはワーストケースで、コア間の通信コストが小さければもっといい数字になるとだけ書いておく。
