探索ノード数が近づくのは必然

今は、macOS版MRWorkerの開発フェーズで、評価精度の向上用作業を完了した。その成果はMasterReversi本体にも反映するので、更新版(Ver1.5.8)を作成して微調整中なのだが、FFOテスト性能は1割くらい向上している。

FFOテストというのは、終盤の局面を完全読みして最善進行を求めるテストなのだが、完全読みの場合、得られる進行は、普通は、どのソフトでも同じになるので、競われるのは、その処理時間になる。

なので、MasterReversi的にも、FFOテストに関しては、処理時間を短縮できる様に改良してきたのだが、処理時間は、基本的には、ノードあたりの処理時間x探索ノード数になる。

このため、処理時間を減らしたければ、ノードあたりの処理時間を減らす努力をすれば良いのだが、例えば、MasterReversiでAVX2命令を使って高速化しました！ みたいに言っていたのは、このノードあたりの処理時間を減らす改良を行いました！ という事と同義になる。

その結果として、FFOテストの処理時間も短縮される事になったのだが、今回は、そういった処理ルーチンについては、基本的には変更していない。

にも関わらず、FFOテストの処理時間が1割程度短縮できているのは、上記した探索ノード数を1割程度減らせているからだ。

昨日と一昨日書いたように、前向き枝刈りを行うと、探索ノード数は減らせるので、処理時間も短縮できるのだが、既に書いたように、普通は、前向き枝刈りを行うと、評価精度が悪化する。

なので、完全読みの場合、既に書いてきた様な前向き枝刈りは一切使用できない。

と、なれば、探索ノード数を減らしたければ、評価精度に劣化が発生しないαβ法による後ろ向き枝刈りだとか、置換表だとかを使う必要が出てくるのだが、これらは、それなりのリバーシソフトなら、どれでも実装している処理になる。

なので、他ソフトと比べて、より優位に立とうとしても、やれる事は限られてしまうのだが、その第一優先となるのが、評価順の並び替え！ という事になる。

これは、αβ探索の後ろ向き枝刈り、つまりβカットによる速度向上が期待できるのは、最善手に対する評価値が確定した後になるので、評価順としては、まず、最善手を評価した方が、処理時間は短縮できる訳だ。

しかし、探索を開始する前に、最善手なんて判るわけがないだろう！ と、怒りたく人も多い筈だ。

何故なら、そんな事がわかるのなら、普通は、何も探索なんてする必要がないからだ。

なので、上記をもって、「論破！」みたいに言う人も多いかもしれない今日この頃なのだが、それなりのリバーシソフトがアルゴリズム的に最も力を入れているのが、この評価順の並び替えかもしれない。

なので、「論破!」なんて事を言っている人は、研究者だとか開発者には向いていないかもしれないのだが、作者的にも、そんな矛盾に満ちた処理を開発するのはストレスだったりもする。

もっとも、思考実験してみれば明らかなのだが、αβ探索で最高速が出せるのは、全ての局面で、最善手から探索を行えた場合だ。

なので、探索ノード数を減らす改良をして処理速度を向上できる限界も、そこになる。

と、言う事で、完全読みの場合、探索ノード数というのは、いくらでも減らせるモノではなくて、最も減らせるのは、全ての局面で最善手から探索が行えた場合だ。

このため、完全読みが高速なソフトの場合、それに近い速度が出せる感じになっているので、高速なソフトを比較すると、似た様な探索ノード数になっている訳だ。

実際、今回の評価データの改良で、FFOテスト時のMRSolverの探索ノード数は1割くらい減ったのだが、比較してみると、Edaxの探索ノード数と似た様な感じになった。

ノードあたりの処理時間については、既に、頑張って減らしてきているので、後は、違いとしては並列探索の方式！ という事になる。

Edaxは、局所的に見れば、最善手探索はシングルスレッドで行い、残りの着手の評価値がそれ以下になる事をマルチスレッドで確認している。

なので、最善手探索に間違いがなかった時には、αβ探索の本来の効率を維持したまま、マルチスレッドによる高速化が実現できている。

その結果として、MasterReversiと比べると、CPUの使用効率が良いので、サーマルスロットリングが発生し辛いし、ハイパースレッディングによる処理速度の向上比率も高い。

その代わり、最善手探索時にはCPU使用率が低くなりがちだし、もし、その探索で最善手が判定できていなかった場合のペナルティも大きくなりがちだ。

これに対して、MasterReversiの並列演算では、反復深化法みたいな事をやっていて、完全読みの開始段階で、既に、最善手だけではなく、最善評価値も決定してαβ探索の窓も設定済みなので、最善手探索用にシングルスレッドでの探索なんてする必要がない。

つまり、全ての着手候補に対して、最初からマルチスレッドでの探索、というか、評価値の検証を行う事になるので、CPU使用率は常に高くなるので、反復深化法で正しい評価値が得られていた場合には、高速に処理を終えられるのだが、サーマルスロットリングは発生しやすくなる。

また、反復深化法で得られた最善値が間違っていた場合のペナルティは、より大きくなるので、大昔に書いたように、MasterReversiの並列探索は、探索ではなく演算だし、ギャンブル性が高い！ という事になる訳だ。

と、言う事で、上記の様な並列探索の方式の違いによる処理速度の違いは出てきて当然なのだが、探索ノード数については、αβ探索を使う限り、最善値は決まっているので、それよりも良くなる事はない。

なので、探索ノード数については、改良を続けていれば、その最善値に近づく事になるので、色々なソフトで方式が異なったとしても、同じ値に収束する格好になるのは必然だ。

まあ、探索には、ファーステストファースト、みたいな考え方もあるし、確定石チェックだとか置換表を使う事でも、探索ノード数は変わってくるので、収束する最善の探索ノード数の定義も難しい。

しかし、完全読みが高速なソフトでは、それらの効率についても似た様な値に収束してくるので、結局、探索ノード数については、似た様な値に収束しても不思議でもなんでもない今日この頃になる訳だ。