logo

TechCodeview

게임 이론의 Minimax 알고리즘 | 세트 4(알파-베타 가지치기)

전제 조건: 게임 이론의 미니맥스 알고리즘 , 게임이론의 평가기능
알파-베타 가지치기는 실제로 새로운 알고리즘이 아니라 minimax 알고리즘을 위한 최적화 기술입니다. 이는 계산 시간을 크게 줄여줍니다. 이를 통해 훨씬 더 빠르게 검색할 수 있으며 게임 트리의 더 깊은 수준으로 이동할 수도 있습니다. 더 나은 이동 방법이 이미 존재하기 때문에 검색할 필요가 없는 게임 트리의 가지를 잘라냅니다. 이는 minimax 함수에서 2개의 추가 매개변수, 즉 알파와 베타를 전달하기 때문에 알파-베타 가지치기라고 불립니다.

매개변수 알파와 베타를 정의해 보겠습니다.

알파 최고의 가치는 최대화기 현재 해당 수준 이상을 보장할 수 있습니다.
베타 최고의 가치는 최소화 현재는 해당 수준 이하를 보장할 수 있습니다.



유사 코드:

 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)>

위의 알고리즘을 예를 통해 명확하게 만들어 보겠습니다.

알파 베타 가지치기

  • 최초 통화는 다음에서 시작됩니다. ㅏ . 여기서 알파의 값은 다음과 같습니다. -무한대 그리고 베타값은 +무한대 . 이러한 값은 트리의 후속 노드로 전달됩니다. ~에 ㅏ 극대화자는 최대값을 선택해야 합니다. 비 그리고 씨 , 그래서 ㅏ 전화 비 첫 번째
  • ~에 비 최소화 프로그램은 최소값을 선택해야 합니다. 디 그리고 그리고 따라서 호출 디 첫 번째.
  • ~에 디 , 리프 노드인 왼쪽 자식을 봅니다. 이 노드는 값 3을 반환합니다. 이제 알파 값은 디 max( -INF, 3)는 3입니다.
  • 올바른 노드를 살펴볼 가치가 있는지 여부를 결정하기 위해 beta<=alpha 조건을 확인합니다. beta = +INF이고 alpha = 3이므로 이는 거짓입니다. 따라서 검색을 계속합니다.
    • D는 이제 5라는 값을 반환하는 오른쪽 자식을 살펴봅니다. 디 , alpha = max(3, 5) 즉 5입니다. 이제 노드의 값은 디 5입니다. D는 5의 값을 반환합니다. 비 . ~에 비 , beta = min( +INF, 5) 즉 5입니다. 이제 최소화 도구는 5 이하의 값이 보장됩니다. 비 지금 전화해 그리고 5보다 낮은 값을 얻을 수 있는지 확인합니다.
  • ~에 그리고 alpha와 beta의 값은 -INF와 +INF가 아니라 각각 -INF와 5입니다. 왜냐하면 beta의 값이 다음과 같이 변경되었기 때문입니다. 비 그리고 그게 뭐야 비 에 전달 그리고
  • 지금 그리고 왼쪽 자식인 6을 봅니다. 그리고 , alpha = max(-INF, 6) 즉 6입니다. 여기서 조건은 true가 됩니다. 베타는 5이고 알파는 6입니다. 따라서 베타<=알파는 참입니다. 그러므로 그것은 깨지고 그리고 6을 반환합니다. 비
  • 값이 무엇인지는 중요하지 않습니다. 그리고 오른쪽 아이는. +INF 또는 -INF일 수도 있지만 여전히 중요하지 않습니다. 최소값은 5 ​​이하의 값이 보장되었기 때문에 살펴볼 필요조차 없었습니다. 따라서 최대화자는 6을 보자마자 왼쪽에 5를 얻을 수 있기 때문에 최소화자가 결코 이쪽으로 오지 않을 것이라는 것을 알았습니다. 비 . 이렇게 하면 9를 볼 필요가 없어 계산 시간이 절약됩니다.
    • E는 6의 값을 반환합니다. 비 . ~에 비 , beta = min( 5, 6) 즉 5입니다. 노드의 값 비 역시 5

지금까지 이것이 우리 게임 트리의 모습입니다. 9는 계산되지 않았기 때문에 삭제되었습니다.

알파 베타 가지치기 2

    B는 5를 다음에게 반환합니다. ㅏ . ~에 ㅏ , alpha = max( -INF, 5) 즉 5입니다. 이제 최대화 도구는 5 이상의 값을 보장합니다. ㅏ 지금 전화해 씨 5보다 높은 값을 얻을 수 있는지 확인합니다.
  • ~에 씨 , 알파 = 5, 베타 = +INF. 씨 전화 에프
  • ~에 에프 , 알파 = 5, 베타 = +INF. 에프 1인 왼쪽 자식을 봅니다. alpha = max( 5, 1) 은 여전히 ​​5입니다.
    • F는 2인 오른쪽 자식을 봅니다. 따라서 이 노드의 가장 좋은 값은 2입니다. 알파는 여전히 5로 남아 있습니다. F는 값 2를 반환합니다. 씨 . ~에 씨 , 베타 = 최소( +INF, 2). 조건 beta <= alpha는 beta = 2이고 alpha = 5일 때 참이 됩니다. 따라서 이 조건은 깨지며 전체 하위 트리를 계산할 필요도 없습니다. G .
  • 이 중단 뒤에 있는 직관은 다음과 같습니다. 씨 최소화 값은 2 이하로 보장되었습니다. 그러나 최대화자는 그가 선택한 경우 이미 5의 값을 보장받았습니다. 비 . 그럼 왜 극대화자는 선택을 했을까요? 씨 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;> }>

int를 문자열로 C++ 

>

>

자바




// 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.> 

>

>

파이썬3


개발자 모드 끄기



# 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> 

>

>

자바는 난수를 생성

씨#




// 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 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>