後期引越しの削減

コンピュータ チェスやコンピュータがプレイする他のゲームでは、後手削減は、ゲーム検索ツリーをより効率的に調査しようとするアルファ ベータ アルゴリズムとそのバリエーションに対する非ゲーム固有の拡張機能です。これは、ゲーム固有の適切な移動順序によって、プログラムが最も可能性の高い移動を早期に検索するという仮定を使用します。検索でカットオフが発生する場合、最初の数手がその原因となる可能性が最も高くなります。チェスなどのゲームでは、ほとんどのプログラムが最初に勝利のキャプチャと「キラー ムーブ」を検索します。後手削減により、特定のノードで後で検索される移動の検索深度が削減されます。これにより、プログラムは重要なラインに沿ってより深く検索し、より優れたプレイが可能になります。

ほとんどのチェス プログラムは、ノードの最初の数手について完全な深さまで検索します。深さを減らした手に対するスコアがアルファより小さい場合、その手は悪い手であるとみなされます。ただし、スコアがアルファより大きい場合、縮小検索では何もわからないため、完全な検索 (フェイル ロー) を実行する必要があります。

この検索削減により、純粋なアルファベータ方式とは異なる検索空間が生まれ、異なる結果が得られる可能性があります。削減基準の選択には注意が必要です。そうしないと、検索で深刻な脅威が見逃されてしまいます。

• 後期引越し削減の紹介