GA将?作ってます 〜強化学習一発芸!!!〜 RSSフィード

2017/09/01

[]合議は「無駄の多い」「ダメな」アルゴリズムなのか? 12:29

前書き

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

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


「同一局面を複数回探索する」=「無駄が多い」なのか?

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

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

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

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


並列αβ探索には無駄が無いのか?

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

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

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


「ダメ」かどうかをどう判断するか?

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

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

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

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


【蛇足】「無駄の無いαβ探索は存在しない」

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

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

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

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

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

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

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

トラックバック - http://d.hatena.ne.jp/Gasyou/20170901/1504236578