ミニマックスとアルファベータ枝刈りの基本を理解しています。すべての文献で、最良のケースの時間計算量は O(b^(d/2)) であると述べています。ここで、b = 分岐係数、d = ツリーの深さであり、基本ケースはすべての優先ノードが最初に展開。
私の「最良のケース」の例では、4 レベルのバイナリ ツリーがあるため、16 のターミナル ノードのうち、最大で 7 つのノードを展開する必要があります。これは O(b^(d/2)) とどのように関係していますか?
どのようにして O(b^(d/2)) になるのかわかりません。
O(b^(d/2)) は、アルファベータ枝刈りの最良のケースの時間計算量に対応します。説明:
(平均または定数) 分岐係数が b で、検索深度が d plies の場合、評価されるリーフ ノード位置の最大数 (移動順序がペシマルの場合) は O(b b ...*b) = O( b^d) – 単純なミニマックス検索と同じ。検索の移動順序が最適である場合 (つまり、最良の移動が常に最初に検索されることを意味します)、評価されるリーフ ノード位置の数は、深さが奇数の場合、O(b*1*b*1*...*b) であり、O です。 (b*1*b*1*...*1) 偶数の深さ、または O(b^(d/2))。後者の場合、検索の層が偶数である場合、有効な分岐係数はその平方根に減少します。つまり、同じ量の計算で検索を 2 倍深くすることができます。
b*1*b*1*... の説明は、最初のプレーヤーのすべての動きを調べて最良の動きを見つけなければならないということですが、それぞれについて、最初のプレーヤー以外のすべてを反駁するには、最良の 2 番目のプレーヤーの手だけが必要です (そしてベスト) 最初のプレーヤーの動き - アルファ-ベータにより、他の 2 番目のプレーヤーの動きを考慮する必要がないことが保証されます。
簡単に言えば、2 つのレベルごとに「スキップ」します。
O は、引数が特定の値または無限大に向かう傾向がある場合の関数の制限動作を説明するため、あなたのケースでは O(b^(d/2)) を b および d の小さな値と正確に比較しても意味がありません。