performance - 反復深化または試行錯誤？

Question

ボードゲームをコーディングしています。アルファベータ法を使用してゲームツリーを生成しました。2つのオプションがあります。

1. 反復深化を使用してアルファベータを最適化し、時間が経過するまでもう1つの層を生成し続けるようにします。
2. 試行錯誤の結果、事前に下層を検査しなくても、制限時間内にすべてのボード構成で到達可能な最大深度がわかりました。

どちらのアプローチが優れており、検索がより深く到達するようになりますか？たとえば、最初は、利用可能なすべての時間を消費する深さXのツリーを生成できることを知っています...反復深化はさらに深さを追加できますか？

もっと明確にできるかどうか教えてください...

Answer 1

分岐係数と評価関数の所要時間が異なるラウンド間でほぼ同じである場合は、オプション2を使用できる可能性があります。しかし、それは非常に難しいように思われます。

オプション1には、完全な移動順序がまだない場合に、アルファベータのパフォーマンスを劇的に向上させる機能があります。d-1までの前回の検索で見つかったすべてのノードで最良の動きを保存し、次にそれを最初に検索するようにalpha-betaに指示します。これは転置テーブルと呼ばれ、これを実装できる場合は、オプション1がオプション2を支配します。

転置テーブルについて初めて聞いたときは、それほど大きな違いはないと思いましたが、最大検索深度が50％増加しました。