ゲームツリーを探索するいくつかのプログラムに関する実験

人工知能における多くの問題は、大きな選択肢の木を探索することを含む—例えば、ゲームプレイや定理証明など。大きな木を効率的に探索する問題が議論されている。「動的順序付け」と呼ばれる新しい方法が説明され、旧来のミニマックス法およびアルファ-ベータ法が比較の目的で説明される。カラのゲームの6つのバリエーションに対する性能指標が示される。「深さ比」と呼ばれる量が導出され、これは探索手続きの効率を測る尺度となる。効率の理論的限界が計算され、動的順序付け手続きがその限界に近づくことが実験的に示される。