アルファベータ枝刈り

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

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

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

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

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

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

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

分岐係数がb (平均または定数) で、探索深度がd pliesの場合、評価される葉ノード位置の最大数 (移動順序が最悪の場合) はO ( b ^d ) で、単純なミニマックス探索と同じです。探索の移動順序が最適 (常に最良の移動が最初に探索される) の場合、評価される葉ノード位置の数は、奇数深度の場合は約O ( b ×1× b ×1×...× b )、偶数深度の場合はO ( b ×1× b ×1×...×1) または${\displaystyle O\left(b^{\frac {d}{2}}\right)=O\left({\sqrt {b^{d}}}\right)}$。

後者の場合、探索のプライが偶数であれば、有効な分岐係数はその平方根に減少します。つまり、同じ計算量で探索の深さを2倍にすることができます。^{[ 14 ]} b ×1× b ×1×...の説明は、最良の手を見つけるために最初のプレイヤーのすべての手を研究する必要があるが、それぞれについて、最初の（最良の）最初のプレイヤーの手以外のすべてを反駁するには、2番目のプレイヤーの最良の手だけが必要であるということです。アルファベータは、他の2番目のプレイヤーの手を考慮する必要がないことを保証します。ノードがランダムな順序で考慮される場合（つまり、アルゴリズムがランダム化する場合）、漸近的に、バイナリの葉値を持つ均一な木で評価されるノードの期待値は${\displaystyle \Theta \left(\left({\frac {b-1+{\sqrt {b^{2}+14b+1}}}{4}}\right)^{d}\right)}$ [ ^{12 ]​}

同じツリーで、葉の値に値が互いに独立して割り当てられ、例えばゼロとイチがどちらも同じ確率で発生する場合、評価されるノードの期待値は${\displaystyle \Theta \left(\left(b/2\right)^{d}\right)}$これは、前述のランダム化アルゴリズムによって行われる作業よりもはるかに小さく、このようなランダムツリーにとって最適です。^{[ 10 ]}葉の値が互いに独立して選択されるが、${\displaystyle [0,1]}$区間が一様にランダムに、評価されるノードの期待値は${\displaystyle \Theta \left(b^{d/\log(d)}\right)}$で${\displaystyle d\to \infty }$制限、^{[ 11 ]}これはこの種のランダムツリーにとって最適です。 の「小さい」値に対する実際の作業は${\displaystyle d}$より近似するには${\displaystyle 0.925d^{0.747}}$[ ^{11 ] [ 10 ]​}

1ノードあたり平均36の分岐を持つ4プライを探索するチェスプログラムは、100万を超える終端ノードを評価します。最適なアルファベータ剪定では、約2,000の終端ノードを除いてすべて削除され、99.8%の削減になります。^{[ 13 ]}

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

さらに、このアルゴリズムは簡単に変更でき、スコアに加えて主変奏全体を返すようにすることも可能です。MTD (f)のようなより高度なアルゴリズムでは、このような変更は容易にはできません。

アルファベータ枝刈り付き深さ制限ミニマックスの擬似コードは次のとおりです。^{[ 15 ]}

function alphabeta(node, depth, α, β, maximizingPlayer) is if depth == 0 or node is terminal then return the heuristic value of node if maximizingPlayer then value := − ∞ for each child of node do value := max(value, alphabeta(child, depth − 1, α, β, FALSE)) if value ≥ β then break (* β cutoff *) α := max(α, value) 値 を返す場合、そうでなければ value := +∞ 各ノードの子ノードについて、 value := min(value, alphabeta(child, depth − 1, α, β, TRUE)) を実行し、 value ≤ αの場合はループを抜ける（* α カットオフ *） β := min(β, value) 戻り値

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

アルファベータ枝刈りの実装は、「フェイルソフト」か「フェイルハード」かによって区別されることが多い。擬似コードはフェイルソフトのバリエーションを示している。フェイルソフトのアルファベータでは、alphabeta関数は、関数呼び出し引数で設定されたαとβの範囲を超える値(v)を返す可能性がある(v < αまたはv > β)。これに対し、フェイルハードのアルファベータでは、関数の戻り値はαとβの範囲内に制限される。

精度を犠牲にすることなく、アルファ・ベータカットオフを引き起こす可能性が高いツリーの早い部分を探索する順序付けヒューリスティックを使用することで、さらなる改善が達成できます。たとえば、チェスでは、駒を取る手は取らない手よりも先に検討され、ゲームツリー分析の以前のパスで高いスコアを獲得した手は他の手よりも先に評価される可能性があります。もう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。
• Pearl, Judea (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving . Addison-Wesley. ISBN 978-0-201-05594-8OCLC 1035596197。​ 
• フィッシュバーン、ジョン・P. (1984). 「付録A：α-β探索の最適化」. 『分散アルゴリズムにおける高速化の分析』（1981年博士論文の改訂版） . UMIリサーチプレス. pp. 107–111 . ISBN  0-8357-1527-2。