並列化による棋力の向上について - ひよこ将棋、はじめました。

普通、Nコアで探索を並列化すれば実効として√N倍であるというのが定説ですが、ではそれによってRがいくら上がるのかというとよくわかっていない意味があります。

まず、優れた評価関数で優れた探索を行なっているソフトがあるとします。いまのトップ付近に位置するコンピューター将棋ソフトはすべてそうですね。

優れた評価関数の場合、探索量が(実効で)2倍になったときの向上が凄まじいです。逆に下手な評価関数ですと探索量が2倍になっても下手の考え休むに似たりであって、あまり強くなりません。

その評価関数として最底辺のものを搭載しているのがひよこカルロ将棋(駒得のみ!!)でして、これ以上ひどい評価関数というのはそうそうお目にかかれないという代物です。

このような質の悪い評価関数の場合、探索量が2倍になったところでR50〜80ぐらいしかあがらないだろうと言われています。逆に質の良い評価関数の場合、R100〜150ぐらい上がるのではないかと言われています。

このように探索量が2倍になったときにどれだけ強くなるのかというのは評価関数に結構依存する意味があると私は思っています。

それに対して、並列化によってどれだけ実効で何倍上がるのかというのは、こちらは探索に係わるファクターです。なぜなら、ざっくざくに枝刈りを実施しているプログラムの場合ですと、並列化しても並列的に探索している途中で枝刈りが発生する確率が高く、探索していたものが無駄になる可能性が高いわけです。

すなわち、探索部が適当な作りで枝刈り性能が悪ければ悪いほど並列化の効率自体は良いということになります。

つまり、並列化の恩恵を一番受けるパターンというのは、評価関数だけが良くてなおかつ探索であまり枝刈りをしていないプログラムです。まあ、そんなコンピュータープログラムいまどきあまりないでしょうけども。

逆に言えば、32コアぐらいで並列探索をするのであれば探索のほうで頑張って枝刈りをしまくるよりは、枝刈りはあえてほどほどにしておいて、並列化での向上を期待する態度のほうが正しいと私は思います。

特にネットワーククラスターで並列化をしようと思ったときに、その効果は顕著で、枝刈りがあまりされないことがわかっている枝を慎重に選び、なおかつ安易に枝刈りしない探索を心がけるべきだと私は思います。

話を戻しまして、ひよこカルロ将棋は評価関数は駒得のみというシンプルなものですが、探索手法自体はBonanzaで使われているような
・null move
・dual killer(killer×2)
・history heuristic
・LMR
・futility
と言ったいまどきのコンピューター将棋では常識となりつつあるものをすべて採用しています。つまり、探索手法自体は結構優れていて、枝刈りはしているほうに属すると思うのですが、評価関数は悪く、なおかつ探索手法は優れているということになり、上の理論からすると、それは並列化で一番Rが伸びないパターンだというのがわかります。

要するに、ひよこカルロ将棋は並列化してもほとんど強くならないのではないかという疑念があります。また序盤が改善されるわけではないので、序盤で大差をつけられていればどうしようもないものがあります。

ゆえに並列化してもほとんどRは変わらないのではないかという結論になるのですが、本当にそうなのかどうかは興味深いところでして、いまfloodgateに投入しているひよこカルロ将棋v0.19が100戦終わり次第、並列化版を投入したいと考えています。

まずはひよこカルロ将棋v0.19の活躍に期待しましょう。