前提条件: ゲーム理論におけるミニマックスアルゴリズム 、ゲーム理論における評価関数
アルファベータ プルーニングは実際には新しいアルゴリズムではなく、ミニマックス アルゴリズムの最適化手法です。計算時間が大幅に短縮されます。これにより、検索がはるかに速くなり、ゲーム ツリーのより深いレベルにまで進むこともできます。これは、利用可能なより良い手がすでに存在するため、検索する必要のないゲーム ツリー内の枝を切り取ります。これは、minimax 関数で 2 つの追加パラメーター、つまりアルファとベータを渡すため、アルファ-ベータ プルーニングと呼ばれます。
パラメーター alpha と beta を定義しましょう。
アルファ が最高の値です マキシマイザー 現時点ではそのレベル以上を保証できます。
ベータ が最高の値です ミニマイザー 現在、そのレベル以下を保証できます。
疑似コード:
function minimax(node, depth, isMaximizingPlayer, alpha, beta): if node is a leaf node : return value of the node if isMaximizingPlayer : bestVal = -INFINITY for each child node : value = minimax(node, depth+1, false, alpha, beta) bestVal = max( bestVal, value) alpha = max( alpha, bestVal) if beta <= alpha: break return bestVal else : bestVal = +INFINITY for each child node : value = minimax(node, depth+1, true, alpha, beta) bestVal = min( bestVal, value) beta = min( beta, bestVal) if beta <= alpha: break return bestVal>
// Calling the function for the first time. minimax(0, 0, true, -INFINITY, +INFINITY)>
上記のアルゴリズムを例を使って明確にしましょう。
- 最初の通話は次から始まります あ 。ここでのアルファの値は -無限大 そしてベータの値は +INFINITY 。これらの値は、ツリー内の後続のノードに渡されます。で あ マキシマイザーは最大値を選択する必要があります B そして C 、 それで あ 電話 B 初め
- で B ミニマイザーは最小値を選択する必要があります D そして そして したがって、呼び出します D 初め。
- で D 、葉ノードである左側の子を調べます。このノードは値 3 を返します。今度はアルファの値が D max( -INF, 3) は 3 です。
- 正しいノードを調べる価値があるかどうかを判断するために、条件 beta<=alpha をチェックします。 beta = +INF および alpha = 3 であるため、これは false です。したがって、検索が続行されます。 D は、値 5.At を返すその右側の子を調べます。 D 、alpha = max(3, 5)、つまり 5。今度はノードの値です。 D は 5 D は値 5 を返します B 。で B , beta = min( +INF, 5) これは 5 です。ミニマイザーの値は 5 以下であることが保証されるようになりました。 B 今電話します そして 5 より低い値を取得できるかどうかを確認します。
- で そして ベータの値が変更されたため、アルファとベータの値は -INF と +INF ではなく、それぞれ -INF と 5 になります。 B それが何ですか B に受け継がれた そして
- 今 そして は、その左の子である 6 を見ます。 そして , alpha = max(-INF, 6) つまり 6 です。ここで条件は true になります。ベータは 5、アルファは 6 です。つまり、ベータ<=アルファは true です。したがって、壊れてしまい、 そして 6を返します B
- の値がどのように重要ではなかったかに注意してください。 そして の右の子がそうです。 +INF または -INF の可能性がありますが、それでも問題ではありません。ミニマイザーの値は 5 以下であることが保証されているため、それを見る必要さえありませんでした。したがって、マキシマイザーが 6 を見た瞬間に、ミニマイザーがこの方向に来ることは決してないことがわかりました。なぜなら、マキシマイザーは左側に 5 を取得できるからです。 B 。こうすることで、9 を調べる必要がなくなり、計算時間が節約されました。 E は値 6 を返します。 B 。で B , beta = min( 5, 6) これは 5 です。ノードの値 B も5です
これまでのところ、ゲーム ツリーは次のようになります。 9 は計算されなかったため、取り消し線が引かれています。
- B は 5 を返します あ 。で あ , alpha = max( -INF, 5) は 5 です。これで、マキシマイザーの値は 5 以上が保証されます。 あ 今電話します C 5 より大きい値を取得できるかどうかを確認します。
- で C 、アルファ = 5、ベータ = +INF。 C 電話 F
- で F 、アルファ = 5、ベータ = +INF。 F は 1 である左の子を調べます。 alpha = max( 5, 1) ですが、これは 5 のままです。 F は、その右側の子である 2 を調べます。したがって、このノードの最良の値は 2 です。アルファは依然として 5 のままです。F は値 2 を返します。 C 。で C 、ベータ = min( +INF, 2)。条件 beta <= alpha は、beta = 2 および alpha = 5 の場合に true になります。したがって、これは壊れ、次のサブツリー全体を計算する必要さえありません。 G 。
- この中断の背後にある直観は次のとおりです。 C ミニマイザーの値は 2 以下であることが保証されていました。しかし、マキシマイザーは、彼が選択した場合、すでに値 5 が保証されています。 B 。では、なぜマキシマイザーはこれを選択するのでしょうか C 2 未満の値を取得しますか?ここでも、最後の 2 つの値が何であるかは重要ではないことがわかります。また、サブツリー全体をスキップすることで、多くの計算量を節約しました。 C は値 2 を返すようになりました。 あ 。したがって、最高の価値は あ max( 5, 2) は 5 です。
- したがって、マキシマイザーが取得できる最適な値は 5 です。
最終的なゲーム ツリーは次のようになります。ご覧のように G 計算されていないため、取り消し線が引かれています。
イーディス・マック・ハーシュ
CPP
// C++ program to demonstrate> // working of Alpha-Beta Pruning> #include> using> namespace> std;> // Initial values of> // Alpha and Beta> const> int> MAX = 1000;> const> int> MIN = -1000;> // Returns optimal value for> // current player(Initially called> // for root and maximizer)> int> minimax(> int> depth,> int> nodeIndex,> > bool> maximizingPlayer,> > int> values[],> int> alpha,> > int> beta)> {> > > // Terminating condition. i.e> > // leaf node is reached> > if> (depth == 3)> > return> values[nodeIndex];> > if> (maximizingPlayer)> > {> > int> best = MIN;> > // Recur for left and> > // right children> > for> (> int> i = 0; i <2; i++)> > {> > > int> val = minimax(depth + 1, nodeIndex * 2 + i,> > false> , values, alpha, beta);> > best = max(best, val);> > alpha = max(alpha, best);> > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> > else> > {> > int> best = MAX;> > // Recur for left and> > // right children> > for> (> int> i = 0; i <2; i++)> > {> > int> val = minimax(depth + 1, nodeIndex * 2 + i,> > true> , values, alpha, beta);> > best = min(best, val);> > beta = min(beta, best);> > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> }> // Driver Code> int> main()> {> > int> values[8] = { 3, 5, 6, 9, 1, 2, 0, -1 };> > cout <<> 'The optimal value is : '> << minimax(0, 0,> true> , values, MIN, MAX);;> > return> 0;> }> |
>
>
ジャワ
// Java program to demonstrate> // working of Alpha-Beta Pruning> import> java.io.*;> class> GFG {> // Initial values of> // Alpha and Beta> static> int> MAX => 1000> ;> static> int> MIN = -> 1000> ;> // Returns optimal value for> // current player (Initially called> // for root and maximizer)> static> int> minimax(> int> depth,> int> nodeIndex,> > Boolean maximizingPlayer,> > int> values[],> int> alpha,> > int> beta)> {> > // Terminating condition. i.e> > // leaf node is reached> > if> (depth ==> 3> )> > return> values[nodeIndex];> > if> (maximizingPlayer)> > {> > int> best = MIN;> > // Recur for left and> > // right children> > for> (> int> i => 0> ; i <> 2> ; i++)> > {> > int> val = minimax(depth +> 1> , nodeIndex *> 2> + i,> > false> , values, alpha, beta);> > best = Math.max(best, val);> > alpha = Math.max(alpha, best);> > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> > else> > {> > int> best = MAX;> > // Recur for left and> > // right children> > for> (> int> i => 0> ; i <> 2> ; i++)> > {> > > int> val = minimax(depth +> 1> , nodeIndex *> 2> + i,> > true> , values, alpha, beta);> > best = Math.min(best, val);> > beta = Math.min(beta, best);> > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> }> > // Driver Code> > public> static> void> main (String[] args)> > {> > > int> values[] = {> 3> ,> 5> ,> 6> ,> 9> ,> 1> ,> 2> ,> 0> , -> 1> };> > System.out.println(> 'The optimal value is : '> +> > minimax(> 0> ,> 0> ,> true> , values, MIN, MAX));> > > }> }> // This code is contributed by vt_m.> |
>
>
Python3
# Python3 program to demonstrate> # working of Alpha-Beta Pruning> # Initial values of Alpha and Beta> MAX> ,> MIN> => 1000> ,> -> 1000> # Returns optimal value for current player> #(Initially called for root and maximizer)> def> minimax(depth, nodeIndex, maximizingPlayer,> > values, alpha, beta):> > > # Terminating condition. i.e> > # leaf node is reached> > if> depth> => => 3> :> > return> values[nodeIndex]> > if> maximizingPlayer:> > > best> => MIN> > # Recur for left and right children> > for> i> in> range> (> 0> ,> 2> ):> > > val> => minimax(depth> +> 1> , nodeIndex> *> 2> +> i,> > False> , values, alpha, beta)> > best> => max> (best, val)> > alpha> => max> (alpha, best)> > # Alpha Beta Pruning> > if> beta <> => alpha:> > break> > > return> best> > > else> :> > best> => MAX> > # Recur for left and> > # right children> > for> i> in> range> (> 0> ,> 2> ):> > > val> => minimax(depth> +> 1> , nodeIndex> *> 2> +> i,> > True> , values, alpha, beta)> > best> => min> (best, val)> > beta> => min> (beta, best)> > # Alpha Beta Pruning> > if> beta <> => alpha:> > break> > > return> best> > # Driver Code> if> __name__> => => '__main__'> :> > > values> => [> 3> ,> 5> ,> 6> ,> 9> ,> 1> ,> 2> ,> 0> ,> -> 1> ]> > print> (> 'The optimal value is :'> , minimax(> 0> ,> 0> ,> True> , values,> MIN> ,> MAX> ))> > # This code is contributed by Rituraj Jain> |
>
Javaのインターフェース
>
C#
// C# program to demonstrate> // working of Alpha-Beta Pruning> using> System;> > class> GFG> {> // Initial values of> // Alpha and Beta> static> int> MAX = 1000;> static> int> MIN = -1000;> // Returns optimal value for> // current player (Initially called> // for root and maximizer)> static> int> minimax(> int> depth,> int> nodeIndex,> > Boolean maximizingPlayer,> > int> []values,> int> alpha,> > int> beta)> {> > // Terminating condition. i.e> > // leaf node is reached> > if> (depth == 3)> > return> values[nodeIndex];> > if> (maximizingPlayer)> > {> > int> best = MIN;> > // Recur for left and> > // right children> > for> (> int> i = 0; i <2; i++)> > {> > int> val = minimax(depth + 1, nodeIndex * 2 + i,> > false> , values, alpha, beta);> > best = Math.Max(best, val);> > alpha = Math.Max(alpha, best);> > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> > else> > {> > int> best = MAX;> > // Recur for left and> > // right children> > for> (> int> i = 0; i <2; i++)> > {> > > int> val = minimax(depth + 1, nodeIndex * 2 + i,> > true> , values, alpha, beta);> > best = Math.Min(best, val);> > beta = Math.Min(beta, best);> > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> }> // Driver Code> public> static> void> Main (String[] args)> {> > > int> []values = {3, 5, 6, 9, 1, 2, 0, -1};> > Console.WriteLine(> 'The optimal value is : '> +> > minimax(0, 0,> true> , values, MIN, MAX));> }> }> // This code is contributed by 29AjayKumar> |
>
>
JavaScript
> // Javascript program to demonstrate> // working of Alpha-Beta Pruning> // Initial values of> // Alpha and Beta> let MAX = 1000;> let MIN = -1000;> // Returns optimal value for> // current player (Initially called> // for root and maximizer)> function> minimax(depth,nodeIndex,maximizingPlayer,values,alpha,beta)> {> > // Terminating condition. i.e> > // leaf node is reached> > if> (depth == 3)> > return> values[nodeIndex];> > > if> (maximizingPlayer)> > {> > let best = MIN;> > > // Recur for left and> > // right children> > for> (let i = 0; i <2; i++)> > {> > let val = minimax(depth + 1, nodeIndex * 2 + i,> > false> , values, alpha, beta);> > best = Math.max(best, val);> > alpha = Math.max(alpha, best);> > > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> > else> > {> > let best = MAX;> > > // Recur for left and> > // right children> > for> (let i = 0; i <2; i++)> > {> > > let val = minimax(depth + 1, nodeIndex * 2 + i,> > true> , values, alpha, beta);> > best = Math.min(best, val);> > beta = Math.min(beta, best);> > > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> }> // Driver Code> let values=[3, 5, 6, 9, 1, 2, 0, -1];> document.write(> 'The optimal value is : '> +> > minimax(0, 0,> true> , values, MIN, MAX));> // This code is contributed by rag2127> > |
タイプスクリプトスイッチ
>
>出力
The optimal value is : 5>