アルファベータ剪定

アルファベータ剪定

クラス	検索アルゴリズム
最悪の場合の パフォーマンス	${\displaystyle O(b^{d})}$
最高の パフォーマンス	${\displaystyle O\left({\sqrt {b^{d}}}\right)}$

アルファベータ剪定は、探索木においてミニマックスアルゴリズムによって評価されるノードの数を減らすことを目的とする探索アルゴリズムである。これは、2人用の組み合わせゲーム（三目並べ、チェス、コネクト4など）を機械でプレイする際によく使用される敵対的探索アルゴリズムである。このアルゴリズムは、以前に検討した動きよりも悪い動きである可能性が少なくとも1つ見つかった時点で、動きの評価を停止する。このような動きはそれ以上評価する必要はない。標準的なミニマックス木に適用すると、ミニマックスと同じ動きが返されるが、最終決定に影響を与える可能性のない枝は剪定される。^[1]

ジョン・マッカーシーはダートマス工房でチェスのプログラムを書いていたIBMのアレックス・バーンスタインと出会った。マッカーシーはアルファベータ探索を発明し、彼にそれを勧めたが、バーンスタインは「納得しなかった」。^[2]

1958年にジョン・マッカーシーが「近似」^[3]と呼ぶものを使用したアレン・ニューウェルとハーバート・A・サイモンは、アルファベータは「何度も再発明されたようだ」と書いています。^[4]アーサー・サミュエルはチェッカーシミュレーション用の初期バージョンを持っていました。リチャーズ、ティモシー・ハート、マイケル・レビン、ダニエル・エドワーズも米国で独立してアルファベータを発明しました。 [ ^{5]マッカーシーは1956年の}ダートマスワークショップで同様のアイデアを提案し、 1961年にMITのアラン・コトックを含む学生のグループにそれを提案しました。^[6]アレクサンダー・ブルードノはアルファベータアルゴリズムを独自に考案し、1963年に結果を発表しました。^[7]ドナルド・クヌースとロナルド・W・ムーアは1975年にアルゴリズムを改良しました。 ^{[8] [9]}ジューディア・パールは2つの論文で、ランダムに割り当てられた葉の値を持つツリーの予想実行時間に関してその最適性を証明しました。^{[10] [11]}ランダム化アルファベータ法の最適性は、マイケル・サックスとアヴィ・ウィグダーソンによって1986年に示された。^[12]

ゲームツリーは、チェス、チェッカー、リバーシなど、 2人プレイのゼロサムゲームを数多く表現できます。ツリー内の各ノードは、ゲームで起こり得る状況を表します。枝の各終端ノード（結果）には、次の動きをするプレイヤーにとっての結果の価値を決定する数値スコアが割り当てられます。^[13]

アルゴリズムは、最大化プレイヤーが保証される最小スコアと最小化プレイヤーが保証される最大スコアを表すアルファとベータという 2 つの値を維持します。最初は、アルファは負の無限大、ベータは正の無限大です。つまり、両方のプレイヤーは最悪のスコアからスタートします。最小化プレイヤー (つまり「ベータ」プレイヤー) が保証される最大スコアが、最大化プレイヤー (つまり「アルファ」プレイヤー) が保証される最小スコアよりも小さくなると (つまりベータ < アルファ)、最大化プレイヤーはこのノードの子孫を考慮する必要はありません。実際のプレイでは、これらの子孫に到達することはないからです。

これを実際の例で説明すると、誰かがチェスをしていて、自分の番になったとします。「A」の動きは、プレーヤーの立場を良くします。プレーヤーは、より良い動きを見逃していないことを確認するために、動きを探し続けます。「B」の動きも良い動きですが、プレーヤーは、相手が 2 手でチェックメイトを強制できることに気づきます。したがって、相手が勝利を強制できるため、動き B をプレイすることによる他の結果は、もはや考慮する必要はありません。「B」の動きの後に相手が強制できる最大スコアは、負の無限大、つまりプレーヤーの負けです。これは、以前に見つかった最小の立場よりも小さいため、「A」の動きは、2 手で強制負けにはなりません。

アルファベータ剪定の利点は、探索木の枝を除去できることです。^[13]この方法では、探索時間を「より有望な」サブツリーに制限し、同じ時間でより深い探索を実行できます。 前身と同様に、これは分岐限定アルゴリズムのクラスに属します。 最適化により、ノードが最適または最適に近い順序で評価される場合、有効な深さは単純なミニマックスの半分強に削減されます（各ノードで最初に順序付けられた移動側のサイドにとって最適な選択）。

分岐係数(平均または定数)がbで、検索の深さがd 層の場合、評価されるリーフ ノード位置の最大数 (移動順序が最小の場合) はO ( b ^d ) で、単純なミニマックス検索と同じです。検索の移動順序が最適 (つまり、最適な移動が常に最初に検索される) である場合、評価されるリーフ ノード位置の数は、奇数深さの場合は約O ( b × 1× b ×1×...× b )、偶数深さの場合はO ( b ×1× b ×1×...×1)、つまり になります。後者の場合、検索の層が偶数であるため、有効な分岐係数はその平方根に減少します。つまり、同じ計算量で検索を 2 倍深くすることができます。^[14] b ×1× b ×1×...の説明は、最善のものを見つけるには最初のプレーヤーのすべての動きを研究する必要があるが、それぞれについて、最初の（そして最良の）最初のプレーヤーの動き以外のすべてを反駁するには、2番目のプレーヤーの最善の動きだけが必要であるということです。アルファ-ベータにより、他の2番目のプレーヤーの動きを考慮する必要がなくなります。ノードがランダムな順序で考慮される場合（つまり、アルゴリズムがランダム化する場合）、漸近的に、バイナリリーフ値を持つ均一ツリーで評価されるノードの期待数はです 。^[12] 同じツリーで、値が互いに独立してリーフ値に割り当てられ、0と1が両方とも同じ確率である場合、評価されるノードの期待数は であり、これは、上記のランダム化アルゴリズムによって行われる作業よりもはるかに小さく、このようなランダムツリーに最適です。^[10]リーフ値が互いに独立して、区間から均一にランダムに選択される場合、評価されるノードの期待数は の極限でに増加し、^[11]この種のランダムツリーに最適です。の「小さな」値に対する実際の仕事は、を使用してよりよく近似されることに注意してください。^{[11] [10]}${\displaystyle O(b^{d/2})=O({\sqrt {b^{d}}})}$${\displaystyle \Theta (((b-1+{\sqrt {b^{2}+14b+1}})/4)^{d})}$${\displaystyle \Theta ((b/2)^{d})}$${\displaystyle [0,1]}$${\displaystyle \Theta (b^{d/log(d)})}$${\displaystyle d\to \infty }$${\displaystyle d}$${\displaystyle 0.925d^{0.747}}$

平均36の枝を持つ4つの層を探索するチェスプログラムは、100万以上の末端ノードを評価します。最適なアルファベータプルーニングでは、約2,000の末端ノードを除いてすべて削除され、99.8％の削減になります。^[13]

通常、アルファ-ベータ中、サブツリーは、最初のプレーヤーの優位性（最初のプレーヤーの多くの手が正しく、各検索の深さで最初のプレーヤーによってチェックされた最初の手は適切であるが、2 番目のプレーヤーのすべての応答が反論を見つける必要がある場合）またはその逆によって一時的に支配されます。この優位性は、手の順序が間違っていると、検索中に何度も切り替わることがあり、そのたびに非効率性につながります。検索される位置の数は、現在の位置に近づくたびに指数関数的に減少するため、初期の手のソートにかなりの労力を費やす価値があります。どの深さでもソートを改善すると、検索される位置の合計数が指数関数的に減少しますが、ルート ノードに近い深さのすべての位置をソートすることは、それらの数が非常に少ないため、比較的安価です。実際には、手順序は、反復深化など、以前の小さな検索の結果によって決定されることがよくあります。

さらに、このアルゴリズムは、スコアに加えて主要なバリエーション全体を返すように簡単に変更できます。MTD (f)などのより積極的なアルゴリズムでは、このような変更は簡単には許可されません。

アルファベータ剪定による深さ制限ミニマックスの疑似コードは以下のとおりです。^[15]

アルファベータ プルーニングの実装は、多くの場合、「フェイルソフト」か「フェイルハード」かで区別できます。フェイルソフト アルファベータでは、alphabeta 関数は、関数呼び出し引数で設定された α および β の境界を超える (v < α または v > β) 値 (v) を返す場合があります。これに対して、フェイルハード アルファベータでは、関数の戻り値が α と β の包括範囲に制限されます。フェイルソフト実装とフェイルハード実装の主な違いは、α と β がカットオフ チェックの前と後のどちらで更新されるかです。チェック前に更新された場合、初期境界を超える可能性があり、アルゴリズムはフェイルソフトになります。

次の疑似コードはフェイルハードバリエーションを示しています。^[15]

関数alphabeta(node, depth, α, β, maximizingPlayer)は
    、 depth == 0またはノードが終端の場合は
        ノードのヒューリスティック値
    を返します。maximizingPlayerの場合は
        値 := −∞
        ノードの各子に対して
            値 := max(値, alphabeta(子, 深さ − 1, α, β, FALSE))
            値 > βの場合、
                ブレーク (* β カットオフ *)
            α := max(α, 値)
        戻り値
    それ以外
        値:= +∞
        ノードの各子に対して
            値 := min(値, alphabeta(子, 深さ − 1, α, β, TRUE))
            値 < αの場合、
                ブレーク (* α カットオフ *)
            β := min(β, 値)
        戻り値

(* 最初の呼び出し *) 
alphabeta(origin, depth, − ∞ , + ∞ , TRUE)

次の疑似コードは、フェイルソフト アルファ ベータを示しています。

関数alphabeta(node, depth, α, β, maximizingPlayer)は
    、 depth == 0またはノードが終端の場合は
        ノードのヒューリスティック値
    を返します。maximizingPlayerの場合は
        値 := −∞
        ノードの各子に対して
            値 := max(値, alphabeta(子, 深さ − 1, α, β, FALSE))
            α := max(α, 値)
            値 ≥ βの場合、
                ブレーク (* β カットオフ *)
        値
    を返す、そうでない場合は
        値:= +∞
        ノードの各子に対して
            値 := min(値, alphabeta(子, 深さ − 1, α, β, TRUE))
            β := min(β, 値)
            値 ≤ αの場合、
                ブレーク (* α カットオフ *)
        値
を返す

(* 最初の呼び出し *) 
alphabeta(origin, depth, − ∞ , + ∞ , TRUE)

順序付けヒューリスティックを使用して、アルファベータカットオフを強制する可能性のあるツリーの以前の部分を検索することにより、精度を犠牲にすることなくさらなる改善を達成できます。たとえば、チェスでは、駒を捕獲する動きは捕獲しない動きよりも前に調べられ、ゲームツリー分析の以前のパスで高いスコアを獲得した動きは他の動きよりも前に評価されます。もう1つの一般的な、非常に安価なヒューリスティックは、キラーヒューリスティックです。これは、ツリー検索で同じツリーレベルでベータカットオフを引き起こした最後の動きが常に最初に調べられるというものです。このアイデアは、反駁表のセットに一般化することもできます。

アルファベータ検索は、狭い検索ウィンドウ（通常は経験に基づく推測によって決定される）のみを考慮することで、さらに高速化できます。これは、アスピレーションウィンドウと呼ばれます。極端な場合、検索はアルファとベータが等しい状態で実行されます。ゼロウィンドウ検索、ヌルウィンドウ検索、またはスカウト検索と呼ばれる手法です。これは、狭いウィンドウと単純な勝敗評価関数から得られる追加の深さが決定的な結果につながる可能性がある、ゲーム終了近くの勝敗検索に特に役立ちます。アスピレーション検索が失敗した場合、失敗が高い（ウィンドウの上端が低すぎる）か低い（ウィンドウの下端が高すぎる）かを簡単に検出できます。これにより、位置の再検索に役立つウィンドウ値に関する情報が得られます。

時間が経つにつれて、他の改善も提案されてきました。実際、ジョン フィッシュバーンの Falphabeta (フェイルソフト アルファベータ) のアイデアはほぼ普遍的であり、わずかに修正された形ですでに上記に組み込まれています。フィッシュバーンは、キラー ヒューリスティックとゼロ ウィンドウ検索を組み合わせた Lalphabeta (「最小ウィンドウのアルファベータ検索による最後の動き」) という名前も提案しました。

ミニマックスアルゴリズムとそのバリエーションは本質的に深さ優先であるため、反復深化などの戦略は通常、アルファベータと組み合わせて使用​​され、アルゴリズムが実行を完了する前に中断された場合でも、かなり良い動きを返すことができます。反復深化を使用するもう 1 つの利点は、浅い深さでの検索により、動きの順序に関するヒントと浅いアルファおよびベータの推定値が得られ、これらによって、通常よりもはるかに早く、より深い深さの検索のカットオフを生成できることです。

一方、SSS*のようなアルゴリズムはベストファースト戦略を採用しています。これにより、潜在的に時間効率は向上しますが、通常はスペース効率に大きな犠牲を払うことになります。^[16]

• ラッセル、スチュアート J. ;ノーヴィグ、ピーター。 (2021)。人工知能：現代的アプローチ（第4版）。ホーボーケン：ピアソン。ISBN 9780134610993. LCCN  20190474.
• Heineman, George T.; Pollice, Gary; Selkow, Stanley (2008)。「7. AI におけるパス検索」。Algorithms in a Nutshell。Oreilly Media。pp . 217–223。ISBN 978-0-596-51624-6。
• パール、ジューディア(1984)。ヒューリスティックス: コンピュータ問題解決のためのインテリジェントな検索戦略。アディソン・ウェズリー。ISBN 978-0-201-05594-8. OCLC  1035596197.
• Fishburn, John P. (1984)。「付録 A: α-β 検索の最適化」。分散アルゴリズムの高速化の分析 (1981 年の博士論文の改訂版)。UMI Research Press。pp. 107–111。ISBN 0-8357-1527-2。