前向き枝刈りは悩ましい

今は、macOS版MRWorkerの開発フェーズで、評価精度の向上用作業を完了した。その成果はMasterReversi本体にも反映するので、更新版(Ver1.5.8)を作成して微調整中なのだが、前向き枝刈りの調整は悩ましい。

普通、リバーシソフトの評価関数は、現在の局面の数手先、または、終局までを探索して、その最善進行でたどり着いた評価値をその局面の評価値にする。

この時、ネットなんかにアップされている教科書通りのαβ探索を行う場合、全ての局面で、その着手候補の全てについて評価値を求め、その最大となる評価値を、その局面の評価値として採用する。

その親となる局面の評価値は、その局面の全ての着手候補に対して、上記の様にして得られた評価値を採用しつつ、一番大きな評価値を自らの評価値として採用する。

もっとも、実は、上記はαβ探索とは関係ない話で、巷では、ミニマックス法と呼ばれている。

αβ探索というのは、そのミニマックス法を効率的に行える様にしたアルゴリズムで、例えば、自分が既に10石勝ちの手を確保できていた場合、相手の手番で相手が8石負けに抑えられる手が発見されると、その局面の探索を打ち切る！ みたいな事を行うアルゴリズムになる。

何故、そんな事が出来るのか、と言うと、相手が8石負けで抑えられる、という事は、自分は8石勝ちにしかならないので、ミニマックス法に従うと、既に10石勝ちの手筋を確保している自分は、そんな手筋は採用しないからだ。

なので、相手が8石負けで抑えられる手を発見したので、その局面は重要！ という事で、その局面の他の手の探索を続ければ、6石負けで抑えられる手を発見できた！ かもしれないのだが、どの道、その局面に至る手筋は採用されないので、そんな探索をしても無駄！ という事で、そんな局面の探索は行わない様にする訳だ。

上記の様にして、探索範囲を狭めて高速化する手法をβカットという。

と、言う事で、リバーシ用の評価関数は、普通はミニマックス法に従って先読みから評価値を決めるのだが、その時のアルゴリズムとしてαβ法を使うと、採用される事がない手筋を早期に見つけ出し、無駄になる探索を早期に打ち切る事ができるので、効率的な探索、つまり、高速な探索を実現できる。

αβ探索を知らなかった人の場合、上記は凄いアルゴリズムだ！ と、思うかもしれないのだが、リバーシソフトの多くは、上記とは別の高速化手法も用いている。

具体的には、より探索する局面数、つまり、ノード数を減らす手法を用いているのだが、その中で、精度を落とさずに行えるのは、確定石を吟味する評価方法だ。

リバーシの場合、置いた石は後からひっくり返されるのも普通なので、ある局面で自石が40石あって、相手の石が10石しかなかったとしても、終局時に自石が40石残る事すら確定はしていない。

なので、自石が40石になった局面で、64-40 = 24なので、少なくとも40-24 = 16石勝ちは確定した！ とは言えないのだが、もし、その40石の中に、どんな手筋になっても、ひっくり返される可能性がない石が34石あるとすると、少なくとも終局時には34石の自石が残るので、終局時のスコアは、少なくとも34 - (64-34) = 4となるので、4石勝ち以上は確定する事になる。

と、言う事なので、もし、相手が勝つ手筋を発見している場合、自分が4石勝ちを確定できる事が発見されると、その手筋は採用されない事が確定するので、それ以上の探索を行う必要はなくなる。

つまり、αβ探索というのは、普通は、予め決めた手数だとか終局まで、探索局面を進めて、その時の評価値を採用するのだが、上記の様な確定石チェックを行うと、決めた手数や終局まで探索を進めなくても、その手筋の途中で、探索を打ち切る事が可能になる。

なので、確定石を鑑みた評価値チェックを行えば、アルゴリズム的には、より高速な探索が可能になるのだが、実際のリバーシソフトの多くは、他の高速化手法も取り入れている。

その中には、置換表を使った枝刈りもある。

具体的には、置換表に既に探索した結果の評価値を入れておき、探索中の局面が置換表に存在していた場合、その評価値を利用する事で、再度の探索を省略する。

ここまでは、上手く実装すれば、探索の精度を落とさずに、探索処理の高速化が行える手法になるのだが、これだけの手法を用いても、まだ遅い！ と、言うユーザーもいたりするので、巷のリバーシソフトでは、その他の高速化手法も取り入れている。

それらの高速化手法では、普通は、高速化しようとすればするほど、精度が低下する危険性があるので、上記の様な手法よりも、実装が悩ましかったりもする。

具体的には、普通のαβ探索の場合、その局面の評価値は、その子ノードに対する探索を全て終えて、その最善手進行から得られる。

なので、前述したβカットを実現するためには、少なくとも、最善手進行については、予め決めた手数分の探索を進める必要があるのだが、その為には、それなりの処理時間が必要になる。

このため、その探索の途中で、更なる前向きの探索を打ち切れる様にするのが、前向き枝刈りになる。

具体的には、普通は、その局面に対して浅い先読みを行い、得られた評価値が、実際に行う探索により得られる評価値との誤差を考慮に入れても、βカットに相当する評価値となった場合には、探索を打ち切る。

また、α値というのは、自分の最善進行時の評価値になるのだが、上記と同様に、探索の途中で浅い先読みから得られる評価値が、誤差を考慮に入れても、検出済みの最善評価値に満たない場合には、やはり、探索を進めてもその手筋が採用される事はない！ という事で、途中で探索を打ち切る。

この様な手法は、βカットに対応させて、αカットと言っても良いかもしれないのだが、正確なαβ探索では、この様なカットは存在し得ないので、βカットと対にしてαカットと呼ぶと変な話にはなるかもしれない。

と、言う事で、上記の様にする事で、αβ探索を真面目に行なった場合よりも、より早く、不必要な手筋に対する探索を打ち切れるので、より高速化できる様になるのだが、問題は、浅い先読みにより得られる評価値の誤差だ。

その誤差がどれくらいになるのか、というのは、正確には把握できないので、この様な前向き枝刈りについては、確率的な話が伴う事になる。

具体的には、浅い先読みの誤差は、統計的には、この範囲で収まる、みたいな考え方をして処理を進める訳だ。

なので、WZebraだとかEdaxの評価過程を見ていても、73% だとか、99%の様なパーセント表示が出てくるのだが、これが、上記の誤差が正しい範囲に収まる確率になる。

つまり、73%というのは、100回の評価を行うと、73回くらいは、上記の誤差が想定範囲内に収まるので、前向き枝刈りを使って枝刈りしても、本来はカットしてはいけない進行をカットする事はない！ という事になる。

別に言い方をすれば、100回の評価を行うと、27回は、本来ならカットできない筈の進行をカットしてしまうので、前向き枝刈りを行わない正規のαβ探索で得られる評価値とは異なる評価値を算出してしまう！ という事になる訳だ。

と、言う事なので、前向き枝刈りを行わせると、結構な確率で、正しくない評価値が算出されてしまうのだが、上記の73%というのは、Edaxの序盤での前向き枝刈りの設定値になっている。

つまり、評価精度に定評があるEdaxでも、序盤では27%は、正しくない評価値を算出して最善手判定を行うので、悪手を打ったとしてもバグでもなんでもない。

MasterReversiでも、似た様な手法は用いているので、評価過程では%表示が出たりしているのだが、そもそも、上記の27%というのは、100回の評価の内で、間違う可能性がある確率が27%という事だ。

つまり、枝刈りを27%間違う、という事ではないのに注意が必要だ。

何故なら、誤差を間違って枝刈りをしてしまったとしても、その先の進行で、枝刈りが発生していた可能性もあった事を鑑みれば、27%の評価で悪影響が出る、という事もない訳だ。

と、言う事で、このパーセンテージ表示も良くわからない数字になるのだが、この値が小さければ小さいほど、間違った評価値になる可能性が高まるのだが、処理速度は向上する。

なので、前向き枝刈りでは、どこまでの正確性を期待するか、または、どこまでの処理時間を許容するか、みたいな事を鑑みながら、このパーセンテージを決めていく必要がある。

この辺はアナログな感じなので、あるソフトでは、着手は速いのだが負けやすい、だとか、このソフトは強いんだけど打つのが遅い、みたいな感じになっていたりする訳だ。

まあ、打つのが遅い上によく負ける！ みたいなソフトもあるのだが、これは、そもそも、評価値の算出が正確ではないので、そんなソフトの場合、前向き枝刈りをしようがしまいが、正しくない評価値で着手するので、弱くなる訳だ。

なので、評価値に自信がないソフトの場合、せめて、着手を速くしよう！ という事で、前向き枝刈りをより積極的に行う様に、上記のパーセンテージを低く設定しておけば、少なくとも、弱い上に遅い！ みたいに言われる可能性は低くなるかもしれない。

しかし、あまりにも弱いと、もっと考えても良いから、つまり、より遅くなっても良いから強くして！ みたいな要望をもらう事になるかもしれない。

ところが、そもそも、処理時間を短くしているのは、下手な考え休むに似たり！ という事なので、処理時間をかけても強くはならない可能性の方が高いかもしれない。

と、言う事で、実際にリバーシソフトを開発しようとすると、色々な要素が絡み合ってくるので、どんな感じで仕上げるのかは悩ましいので、それだけで、胃が痛くなる人も出てくるかもしれない。

なので、悩みすぎて発狂する様な人は、開発者にはならない方が良いかもしれないのだが、実際の所、開発者の場合、適当に仕事をしていても、それなりの成果は確実にアウトプットできるので、研究者になるよりは、まだマシかもしれない今日この頃だ。