合議は「無駄の多い」「ダメな」アルゴリズムなのか？

　以前、とある方から「何で合議という無駄の多いアルゴリズムを使っているんですか？並列αβ探索で良いじゃないですか。」という趣旨のメールを頂きました。

　そのメールには単に「並列αβ探索より合議の方が強くなったので採用しています。」とだけ返信しましたが、せっかくのネタなのでもうちょっと詳しくブログに書いてみます。

　上記のメールの方は、複数のクライアントが同一局面を探索する場合があるので、それを指して「無駄」と呼んでいた様です。

　では、本当にそうなんでしょうか？

　例えば、多くのコンピュータ将棋ソフトで使用されている「反復深化」や「LMR」も、合議と同じく「同一局面を複数回探索する」可能性が有ります。ですが、これを「無駄」と呼んでいる人はほとんど居ないと思います。

　という訳で、上記の問いに対する私の答えは「NO」です。

　まだデュアルコアCPUが出るか出ないかという時期だったと思いますが、「コア数がN倍になっても√N倍程度の高速化率しか達成出来ない」と言う話があったと思います。

　本当に√なのか、それとも0.75乗なのか、あるいはもっと1.0乗に近いのかは私には分かりませんが、少なくとも「コア数がN倍になったら、それに比例して高速化する」という実験結果は見た事がありません。

　つまり、並列αβ探索にも無駄が存在する、というのが私の考えです。

　私は趣味でコンピュータ将棋を開発していますので、「GA将が強くなる事」がまず重要です。

　で、「ダメ」かどうかの判断基準も単純で、「強くなれば良いアルゴリズム、弱くなればダメなアルゴリズム」と考えています。

　その上で、私の実装した並列αβ探索と合議を比較すると、合議の方が強くなったので、私にとっては合議の方が「良い」アルゴリズムです。

　もちろん、並列αβ探索のアルゴリズムや実装、レーティング計測の条件等によって並列αβ探索と合議のどちらが優れているかは変化する事は、公正の為に明記しておきたいと思います。

　まず、αβ探索が最高の性能を発揮する為には、ムーブオーダリングの時点で最善手が先頭に来る必要が有ります。

　で、私の知る限りそういうムーブオーダリングを実装出来ているソフトは存在しません。

　つまり、この世のほぼ全てのコンピュータ将棋ソフトは「無駄のある」探索ルーチンを採用している事になります。

　では、仮に「任意の残り探索深さdでの最善手を先頭に持って来れるムーブオーダリングアルゴリズム」を実装出来たとします。この場合、無駄は無くなるでしょうか？

　この場合、d=∞に設定してムーブオーダリングすれば、真の*1最善手が得られる訳です。つまり、探索する事自体が無駄、という事になります。

　という訳で、「どうあがいてもαβ探索には無駄が存在しますよ」という蛇足でした。

*1:完全解析した結果と一致する

GA将？開発日記～王理のその先へ～