KENTOという赤字を垂れ流し続けている(?)オンラインの棋譜解析サービスがあります。
このKENTOでは、棋譜解析の時短のために棋譜の複数局面を同時に解析するというのをやっています。Amazon Lambdaというサービスを利用すると、必要な時に必要な数だけ同時にインスタンスを起動することができるので、こういうことに適しています。
KENTO開発室 #2 『KENTOってどれくらい強いの？』
https://note.com/shogi_kento/n/ncc05cc261b7e
KENTOの場合、棋譜を6手ごとにグループ分けして、それぞれのグループに対して、Amazon Lambdaのインスタンス(1スレッド？)に解析をさせているようです。
1手ごとに異なるインスタンスに解析をさせれば6倍速くなりそうなものですが、棋譜解析というのは連続する局面ですから、前の情報が置換表に残っているほうが探索効率が良い意味はあります。
もう少し一般化して考えてみましょう。
問題) いま、Nスレッドのご家庭のPCがあるとする。Nスレッドで一つの局面を探索した時は、√Nの実効であるとする。このPCで棋譜解析を行う時に、1スレッドごとに異なる局面を割り当てて、並列的に棋譜解析をすることを考える。本当にそうしたほうが得であるか？
思考時間は探索深さに応じて指数関数的に増大します。
Bonanzaの時は(Bonanzaの発表スライドによると)序盤で\(3^n\)、終盤で\(5^n\)とあります。
最近のStockfishの探索はそれより枝刈りが激しく、また評価関数の精度も高くなってきているので、それよりは小さな数字になっています。
教師生成のときにdepthを1上げたときに探索時間が何倍になるかは、昨年のやねうら王の実験ではdepth 8,10,12の時の平均node数はおおよそ以下のようになっていたので、depth 2増えると3.5倍程度のようです。
depth 8 : 2k nodes
depth 10 : 7k nodes
depth 12 : 20k nodes
そんなわけで、depth 1増えると√3.5 ≒ 1.87倍。ある局面の探索の結果は、次の局面において、これの逆数である1/1.87 = 0.535 (53.5%) が再利用できると考えられます。(ただし、置換表サイズは無限であり、破壊されないものとする。)
この0.535 = rとおくと、ある局面の探索の結果は、1手先で\(r\) , 2手先で\(r^2\) , n手先で\(r^n\)だけ再利用できます。
手数制限がない場合、n→∞なので、これは初項\(r\)、公比\(r\)の(無限)等比級数です。等比級数の和の公式により、\(\frac{r}{(1-r)} = \frac{0.535}{1-0.535} ≒ 1.15 \)となります。
ゆえに、ある局面の結果は(置換表が無限にあり、手数が無限であるというような楽観的な条件で)115%が再利用されると評価できます。
例)
3スレッドだと実効が√3 = 1.73、115%upなので、1.73×2.15(115%up) ≒ 3.72 となり、1スレッドずつ異なる局面を探索させずに、Nスレッドで1つの局面を探索して棋譜解析したほうが効率が良いことがわかる。
逆にNがいくらなら、1スレッドずつ異なる局面を探索したほうが効率が良いのかと言うと、\( \sqrt{N} × 2.15 < N\) になるNなので、\(N > 2.15^2 = 4.62\) のとき。
5スレ以上ですと1スレッドずつ異なる局面を探索したほうが良さそうです。
結論1) 1局面1スレ解析は、5スレ以上のCPUでないと意味がない。
結論2) 棋譜解析の時、置換表が再利用できると探索効率は「115%up」。
WCSC29では、クラスター(複数台PC)で、pre-ponderを採用しているチームがいくつかありましたが、どのチームも置換表を共有していない実装でした。
pre-ponder時の損失とは少し異なりますが、通常対局で置換表が1手ごとにクリアされる時にどれくらいの損失がでるかは、次のように計算できます。
棋譜解析の時と異なり、自分の手番側だけ考えればいいので、この時、無駄になる置換表は2手先で\(r^2\)、4手先で\(r^4\)、…。これは初項\(r^2\)、公比\(r^2\)の(無限)等比級数。その和は、\(\frac{r^2}{1-r^2} = \frac{0.535^2}{1-0.535^2}\) ≒ 0.401。
そんなわけで、置換表を共有しないクラスター探索では、この40.1%upが得られないということになりそうですね。わりとでかい？
評価関数や探索の精度が上がると、ここの40.1%はさらに上がることになって、置換表を共有しないタイプのクラスター並列化は、効果が薄そうですね。
1.87はさすがに小さいですね。
うちの計測では序盤の2くらいが最小で中盤3近くなりました。
それに平均値で議論していいのやらって問題もありますね。
定跡掘ってても１個だけ不思議に遅いケースも実際結構あります。
> 定跡掘ってても１個だけ不思議に遅いケースも実際結構あります。
depth固定で掘ると王手がかかっていると1手延長するので詰将棋みたいなやつでえらい時間がかかるやつがあります(´ω｀)
チェスではそこまで王手が続かないんでしょうけども、将棋の場合、あの延長は制限したほうがよさげです。(強さにどの程度影響があるかはわかりませんが..)
> それに平均値で議論していいのやらって問題もありますね。
序中盤と終盤で平均分岐数が大きく異なると、そういう話になりますね…。まあ、今回のはざっくりと概算を出してみたということで、これ以上の詳細な議論は誰かが引き継いでくれることを期待しております。
目の付け所がすごいです
置換を共有すると【排他ロック】か【排他ロックを使わなくても良い手法の開発】のどちらかが必要か？
またキャッシュに乗ってる乗ってないも影響するか？
いまのやねうら王は置換表を1PCでスレッド並列で探索する場合も、lockしてませんけどね…。(´ω｀) locklessアルゴリズムでもなくて。
なので、クラスター間で置換表を共有する(この5月にあったWCSO1でtanuki-チームがやっている)場合でも、まあ、lockなんぞしなくとも…。
並列書き込みとかするのに、lockをしないのはrock。
それ考えるのに要した時間は、locklessならぬpriceless
115%upなら、2.25ではなく2.15なのでは？
「6スレ以上ですと1スレッドずつ異なる局面を探索したほうが良さそう」というのは、裏を返すと分けられるものなら16スレッドを4スレッドずつに分けるなどしたほうがいいということでしょうか？
最初読み始めたときは「棋譜を6手ごとにグループ分けして」の部分の6手という数字がいかに導き出されたかという話かと思いましたが、そこはあくまで人間が待てる時間とのバランスを人間的に考えた結果で、後段の話はあくまで「1手ごとだと非効率」という解説ですね。
> 115%upなら、2.25ではなく2.15なのでは？
普通に寝ぼけてました(^^ゞ 本文、修正しておきました。
> 後段の話はあくまで「1手ごとだと非効率」という解説ですね。
ですです。
KENTO紹介してくださってありがとうございます、いつもお世話になっていますm(_ _)m
この問題気になっていたので、考察とても有り難いです！
> ある局面の探索の結果は、次の局面において、これの逆数である1/1.87 = 0.535 (53.5%) が再利用できる
ある局面の探索ツリーの「1つ浅い部分木」が、そのまま次の局面の探索ツリーとの共通部分だと考えられるから、っていう考え方であってますか？
似た問題として、連続解析の時間配分どうするのが合理的か、というのがありまして、（今は均等に割り振ってるんですが）
上記の考え方でいうと、2手目以降は葉ノードだけ探索できる程度の時間 (1手目の半分くらい) で十分と言えるんでしょうか。
> ある局面の探索ツリーの「1つ浅い部分木」が、そのまま次の局面の探索ツリーとの共通部分だと考えられるから、っていう考え方であってますか？
ですです。
> 似た問題として、連続解析の時間配分どうするのが合理的か、というのがありまして、（今は均等に割り振ってるんですが）
連続解析の時間配分は、やねうら王の探索部のtime managementみたいなことをするのが本当はよろしいですね。
https://github.com/yaneurao/YaneuraOu/blob/1048b6a1874ead3e385e5c62064cf790a9bdebea/source/engine/yaneuraou-engine/yaneuraou-search.cpp#L1022
それで、上のtime managementをエンジンの外部でやるのは、わりかし面倒なので、例えば、持ち時間を固定してのgoコマンドを送信することでやねうら王側のtime managementに任せるという方法が考えられますね。
go btime XXXX wtime XXXX byoyomi 0
> 上記の考え方でいうと、2手目以降は葉ノードだけ探索できる程度の時間 (1手目の半分くらい) で十分と言えるんでしょうか。
楽観的にはそうですね。ただ、長い時間を思考させた時にも、この記事のrぐらいの値になるかはよくわかりません。(そこまでデータ取ってませんでした。48さんのコメントの数値のほうが正しいかもです。) また、終盤は悪化(rが下がる)しそうですね…。
やねうら王をずっと前に購入して以降よく使っております。
コンピュータ将棋にあまり詳しくないのですが、ここ数年での進歩が凄いとか！？
今度やねうら王2？が出るようですが、前に購入したものにもパワーアップしたやねうら王は更新してもらえるのでしょうか？？
やねうら王１の次のアップデートで、外部エンジンが使えるようになるです(｀･ω･´)ｂ