logo

ゲーム理論におけるミニマックス アルゴリズム |セット 4 (アルファ-ベータ プルーニング)

前提条件: ゲーム理論におけるミニマックスアルゴリズム 、ゲーム理論における評価関数
アルファベータ プルーニングは実際には新しいアルゴリズムではなく、ミニマックス アルゴリズムの最適化手法です。計算時間が大幅に短縮されます。これにより、検索がはるかに速くなり、ゲーム ツリーのより深いレベルにまで進むこともできます。これは、利用可能なより良い手がすでに存在するため、検索する必要のないゲーム ツリー内の枝を切り取ります。これは、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 は計算されなかったため、取り消し線が引かれています。

アルファ ベータ プルーニング 2

    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 計算されていないため、取り消し線が引かれています。



イーディス・マック・ハーシュ

アルファ ベータ プルーニング 3

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>