静止検索

静止探索は、ゲームをプレイするコンピュータ プログラムで、ミニマックス ゲーム ツリーの不安定なノードで探索を拡張するために通常使用されるアルゴリズムです。これは、位置が十分に安定して静的に評価されるまで、つまり位置の履歴や位置からの将来の動きを考慮することなく評価を延期する評価関数の拡張です。チェスや囲碁などのさまざまなゲームのAIエンジンが直面する地平線問題の影響を軽減します。

人間のプレイヤーは通常、悪い動きを放棄するか、有望な動きを深く探索するかを判断できるほどの直感力を持っています。静止探索は、隠れた罠がないことを確認し、その価値をより正確に見積もるために、コンピューターに「不安定な」位置を「静かな」位置よりも深く探索するように指示することで、この動作を模倣しようとします。

「静かな」ポジションと「不安定な」ポジションを区別するために、任意の適切な基準を使用できます。一般的な基準の 1 つは、チェスや囲碁の捕獲など、ポジションの評価を劇的に変える可能性のある動きがポジションに存在することです。静止検索の主な目的は静的評価関数から安定した値を取得することであるため、いくつかのプレイ、つまり履歴基準にわたって単純なヒューリスティック評価器によって返される値の大きな変動を検出することも意味があります。静止検索は、ポジションが基準に従って不安定である限り続行されます。静止検索を終了するために、プレイは通常、チェスの捕獲と再捕獲 (「捕獲検索」と呼ばれることが多い) の動きなど、脅威に直接対処する動きに制限されます。囲碁やリバーシなどの非常に「不安定な」ゲームでは、かなり多くのコンピューター時間が静止検索に費やされる可能性があります。

地平線効果は、ゲーム ツリーの特定のノードからのすべての動きが固定された深さまで検索されるときに発生する可能性のある人工知能の問題です。検索深さを超える脅威と機会は検出されません。これにより、プログラムが遅延移動を行って位置を低下させ、脅威を検索深さまたは「地平線」を超えるまで押し続けるという奇妙な策略が発生する可能性があります。脅威に対処しなければならないときには、位置は回復できないほど低下しています。静止検索は、ヒューリスティック値が動きの間で大幅に変動する可能性のある不安定な位置での検索深さを拡張することで、この問題を軽減しようとします。

この疑似コードは、概念をアルゴリズム的に示しています。

関数quiescence_search(node, depth)は、
    ノードが静止しているか、ノードが終端ノードであるか、またはdepth = 0である場合は
        ノードの
    推定値を返します。それ 以外の場合は( quiescence_search を使用してノードの子を再帰的に検索し)、子の推定値を返します。
        
        

関数normal_search(node, depth)は、
    ノードが終端ノードの場合は
        ノードの推定値
    を返します。そうでない場合は、 depth = 0で、ノードが静止している場合はノードの推定値
        を返します。そうでない場合は、quiescence_search(node, reasonable_depth_value) から推定値を
    返します。そうでない場合は(normal_search を使用してノードの子を再帰的に検索し)、子の推定値を
返します。
        
            
            
        
        

• Beal, Don (1990 年 4 月)。「一般化された静止検索アルゴリズム」。人工知能。43 : 85–98。doi : 10.1016 /0004-3702(90)90072-8。