引き続きリバーシの話。
alpha-betaのように、もはやそれ以上の探索の必要がなくなった木の枝を切り捨ててしまうことを枝刈りという。
alpha-betaやNegaScoutのようなタイプは後ろ向き枝刈りと呼ばれるらしいが、いったいアルゴリズムが違うとどれくらい枝刈り性能が違うものなのかを試してみた。
その前にMove Orderingというものを説明しよう。
alpha-beta法から派生したような探索では事前に評価値の良い手に並び替えて探索を始めれば枝刈りが多く発生して探索が速く終わりますよ、という話。
今回そのMove Orderingというものを行ったものと行っていないものの比較もしてみたいと思う。ちなみに、以下に書かれた「Move Orderingあり」の記述は、１回だけ浅い探索を行いその評価値によって手を並び替えた後、深い探索をしたものである。
| 探索方法 | 評価関数呼び出し回数 | 実行時間 |
|---|---|---|
| Move Orderingなし & alpha-beta法 | 9739436回 | 1m3.406s |
| Move Orderingあり & alpha-beta法 | 9638762回 | 1m2.108s |
| Move Orderingなし & NegaScout法 | 10147572回 | 1m5.531s |
| Move Orderingあり & NegaScout法 | 9119705回 | 59.343s |
はてなで表の項目を右寄せにする方法はないのだろうか？
それはともかく上の表のような結果になりました。ただ、実行時間の項目は一度しか計っていないため参考程度です。
Move Orderingを使わないとNegaScout法はalpha-beta法よりも枝刈り性能が悪い、という結果が出ているのだけれども、これはなんだろう。NegaScout法は一番最初の手だけまともにalpha-betaで探索して、後はnull window searchを駆使して枝刈りしていくのだが、その分最初に良い手がこないと性能が落ちてしまうのだろうか？
次に同じNegaScout法だが、今度は全ての枝についてMove Orderingを行ったものとの比較をしてみる。ここで行うMove Orderingは開放度を用いたもので、浅い探索を行うよりも素早く評価値を手に入れることができる。
| 探索方法 | 評価関数呼び出し回数 | 実行時間 |
|---|---|---|
| Move Orderingなし & NegaScout法 | 7525929回 | 56.968s |
| Move Orderingあり & NegaScout法 | 503590回 | 5.562s |
まず最初に、「Move Orderingなし & NegaScout法」の評価関数呼び出し回数が上の表と下の表で異なっているのは、少々評価関数を書き換えたためである。
それにしても、バグではないのかと思ってしまうほど枝刈りが発生したようだ。1/15とは……。きっと評価関数に評価値テーブルと開放度を組み合わせた単純なものを使用していたために枝刈りが多く発生したのだろう。ちゃんとした評価関数を書いたなら、もう少し枝刈り性能が落ちるはずである。
今日はここまで。
