先日、将棋ソフトにおける並列探索のトレンドは、YBWCからLazySMPに移り変わったという話を書いたが、YBWCの何が駄目なのかというのがそもそもわからない人がそこそこいるのだなということに気づいた。今回はこれについて詳しく説明を書く。

まず、並列探索で効率が出ないのは何故なのか。

将棋のようなゲーム木探索について詳しくない人は、さぼっている(仕事を割り振られていない)スレッドがあるからだと思うらしい。いや、そもそもプログラマーでない人には「スレッド」自体が意味不明なのかも知れん。「スレッド」はワーカー(労働者的な意味の)だと思って欲しい。

さぼっている奴、もしくは仕事が割り振られずに遊んでいる奴がいると、10スレッドあっても5スレッド分の仕事しか出来ない。これは直感的だし、わかりやすい。

しかし、残念ながら、将棋におけるゲーム木探索というのは、そういう状況とはかけ離れているのだ。

例えば、昔の将棋ソフト――Bonanzaあたりが適当だろうか――を動かして、WindowsのタスクマネージャーでCPU負荷率を見てもらいたい。コンピューターが思考中はCPU負荷率がほとんど100%に張り付いているだろう。(ハイパースレッディングありにして、物理コアの数だけのスレッド数にした場合は50%に張り付く。念のため。)

つまり、Bonanzaにしても、さぼってるスレッドなどいないのだ。

言うまでもなく、BonanzaにもYBWCが使われている。YBWCでも仕事はほぼ100%割り振られているのだ。LazySMPは言うまでもない。

では何故、並列化効率が悪いのか？10スレッドあるのに10倍の仕事が出来ないのか？何倍なら出来るのか？みたいな話になる。

これを説明するのが、実は結構難しい。αβ探索の動作原理を理解していないと理解できないからだ。αβ探索をプログラマーに説明するのすら結構難しい。まして、プログラミングの素養のない人にわかってもらうのは不可能に近い。

そこで、αβ探索ではなく、1手詰めの探索の説明をして、わかってもらおうと思う。

まず、1手詰めの局面があるとする。その局面での王手となる指し手は10通りあるが、詰むのは1手のみであるものとする。

これを10個のスレッドで10個の指し手について並行して詰むかどうかを調べるとする。

また、詰むかどうかを調べるのには、詰まないときと詰むときとで同じだけの計算コストが必要であるものとする。

そうすると、このとき10個のスレッドすべてに指し手を1つずつ、うまく仕事を割り振れて、遊んでいるスレッドもないし、効率が1スレッドのときの10倍出たように思える。ところがこれが間違いなのである。

1スレッドでこの10個の指し手について調べていくなら、平均的には5個調べると詰みの指し手が見つかる。だから、均して考えると5個分を調べるコストだけで良いのだ。

つまり10スレッドでやっても1スレッドのときの5倍の効率アップにしかなっていないのである。

αβ探索のほうも似たような状況で、遊んでいるスレッドはないのだが、NスレッドでやってもN倍の効率アップにはならず、√N倍程度の効率アップにしかならない。実際は、√Nよりは少し効率が良いようだが、ともかく、そういう状況だ。

結局、遊んでいるスレッドなどいないのである。だけど1スレッドのときよりは無駄がかなり出るということであるな。上の1手詰めの例を見てもわかるように、無駄が出るのは原理的に仕方ないわけであるが、なるべく無駄が減るような投機的実行の手段が問われている。

まだ少し書き足りないが、長くなってきたので今回はここまで。