미니맥스(Minimax)는 상대방도 최적으로 플레이한다는 가정 하에 플레이어에게 최적의 움직임을 찾기 위해 의사 결정 및 게임 이론에 사용되는 일종의 역추적 알고리즘입니다. Tic-Tac-Toe, Backgammon, Mancala, Chess 등과 같은 2인용 턴제 게임에 널리 사용됩니다.
Minimax에서는 두 플레이어를 최대화기(maximizer)와 최소화기(minimizer)라고 합니다. 그만큼 최대화기 가능한 가장 높은 점수를 얻으려고 노력하는 동안 최소화 그 반대를 시도하고 가능한 가장 낮은 점수를 얻으려고합니다.
모든 보드 상태에는 이와 관련된 값이 있습니다. 주어진 상태에서 최대화자가 우위를 점한다면 보드의 점수는 어느 정도 긍정적인 값이 되는 경향이 있습니다. 해당 보드 상태에서 최소화 장치가 우위에 있으면 음수 값이 되는 경향이 있습니다. 보드의 값은 모든 게임 유형에 고유한 일부 경험적 방법을 통해 계산됩니다.
예:
4개의 최종 상태가 있고 최종 상태에 도달하는 경로가 아래와 같이 루트부터 완전 이진 트리의 4개 잎까지인 게임을 생각해 보세요. 당신이 최대화 플레이어이고 움직일 수 있는 첫 번째 기회를 얻었다고 가정합니다. 즉, 당신은 루트에 있고 상대는 다음 레벨에 있습니다. 상대방도 최적으로 플레이한다는 점을 고려하면 최대화 플레이어로서 어떤 움직임을 취하시겠습니까?
이는 역추적 기반 알고리즘이므로 가능한 모든 이동을 시도한 다음 역추적하여 결정을 내립니다.
- Maximizer가 왼쪽으로 이동: 이제 Miniizer가 회전합니다. 이제 최소화 도구는 3과 5 사이에서 선택할 수 있습니다. 최소화 도구이기 때문에 둘 중 가장 작은 것, 즉 3을 선택하게 됩니다.
- Maximizer가 오른쪽으로 이동: 이제 Miniizer의 차례입니다. 이제 최소화 프로그램은 2와 9 사이에서 선택할 수 있습니다. 두 값 중 가장 작은 값인 2를 선택합니다.
최대화자는 더 큰 값인 3을 선택합니다. 따라서 최대화자의 최적 이동은 왼쪽으로 이동하는 것이며 최적 값은 3입니다.
이제 게임 트리는 아래와 같습니다:
위의 트리는 최대화가 왼쪽과 오른쪽으로 움직일 때 가능한 두 가지 점수를 보여줍니다.
참고: 오른쪽 하위 트리에 값 9가 있더라도 최소화 프로그램은 이를 선택하지 않습니다. 우리는 항상 상대방이 최적의 플레이를 한다고 가정해야 합니다.
아래는 동일한 구현입니다.
C++
라인 오토캐드 명령
// A simple C++ program to find> // maximum score that> // maximizing player can get.> #include> using> namespace> std;> // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is> // of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> int> minimax(>int> depth,>int> nodeIndex,>bool> isMax,> >int> scores[],>int> h)> {> >// Terminating condition. i.e> >// leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> >// If current move is maximizer,> >// find the maximum attainable> >// value> >if> (isMax)> >return> max(minimax(depth+1, nodeIndex*2,>false>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>false>, scores, h));> >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> min(minimax(depth+1, nodeIndex*2,>true>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>true>, scores, h));> }> // A utility function to find Log n in base 2> int> log2(>int> n)> {> >return> (n==1)? 0 : 1 + log2(n/2);> }> // Driver code> int> main()> {> >// The number of elements in scores must be> >// a power of 2.> >int> scores[] = {3, 5, 2, 9, 12, 5, 23, 23};> >int> n =>sizeof>(scores)/>sizeof>(scores[0]);> >int> h = log2(n);> >int> res = minimax(0, 0,>true>, scores, h);> >cout <<>'The optimal value is : '> << res << endl;> >return> 0;> }> |
>
>
변수 전역 자바스크립트
자바
// A simple java program to find maximum score that> // maximizing player can get.> import> java.io.*;> class> GFG {> > // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> >static> int> minimax(>int> depth,>int> nodeIndex,>boolean> isMax,> >int> scores[],>int> h)> {> >// Terminating condition. i.e leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> >// If current move is maximizer, find the maximum attainable> >// value> >if> (isMax)> >return> Math.max(minimax(depth+>1>, nodeIndex*>2>,>false>, scores, h),> >minimax(depth+>1>, nodeIndex*>2> +>1>,>false>, scores, h));> >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> Math.min(minimax(depth+>1>, nodeIndex*>2>,>true>, scores, h),> >minimax(depth+>1>, nodeIndex*>2> +>1>,>true>, scores, h));> }> // A utility function to find Log n in base 2> >static> int> log2(>int> n)> {> return> (n==>1>)?>0> :>1> + log2(n/>2>);> }> // Driver code> >public> static> void> main (String[] args) {> >// The number of elements in scores must be> >// a power of 2.> >int> scores[] = {>3>,>5>,>2>,>9>,>12>,>5>,>23>,>23>};> >int> n = scores.length;> >int> h = log2(n);> >int> res = minimax(>0>,>0>,>true>, scores, h);> >System.out.println(>'The optimal value is : '> +res);> > >}> }> // This code is contributed by vt_m> |
>
>
씨#
소프트웨어 테스트 및 유형
// A simple C# program to find maximum score that> // maximizing player can get.> using> System;> public> class> GFG> {> > // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> static> int> minimax(>int> depth,>int> nodeIndex,>bool> isMax,> >int> []scores,>int> h)> {> >// Terminating condition. i.e leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> >// If current move is maximizer, find the maximum attainable> >// value> >if> (isMax)> >return> Math.Max(minimax(depth+1, nodeIndex*2,>false>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>false>, scores, h));> >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> Math.Min(minimax(depth+1, nodeIndex*2,>true>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>true>, scores, h));> }> // A utility function to find Log n in base 2> static> int> log2(>int> n)> {> >return> (n==1)? 0 : 1 + log2(n/2);> }> // Driver code> static> public> void> Main ()> {> >// The number of elements in scores must be> >// a power of 2.> >int> []scores = {3, 5, 2, 9, 12, 5, 23, 23};> >int> n = scores.Length;> >int> h = log2(n);> >int> res = minimax(0, 0,>true>, scores, h);> >Console.WriteLine(>'The optimal value is : '> +res);> > }> }> // This code is contributed by ajit.> |
>
>
파이썬3
# A simple Python3 program to find> # maximum score that> # maximizing player can get> import> math> def> minimax (curDepth, nodeIndex,> >maxTurn, scores,> >targetDepth):> ># base case : targetDepth reached> >if> (curDepth>=>=> targetDepth):> >return> scores[nodeIndex]> > >if> (maxTurn):> >return> max>(minimax(curDepth>+> 1>, nodeIndex>*> 2>,> >False>, scores, targetDepth),> >minimax(curDepth>+> 1>, nodeIndex>*> 2> +> 1>,> >False>, scores, targetDepth))> > >else>:> >return> min>(minimax(curDepth>+> 1>, nodeIndex>*> 2>,> >True>, scores, targetDepth),> >minimax(curDepth>+> 1>, nodeIndex>*> 2> +> 1>,> >True>, scores, targetDepth))> > # Driver code> scores>=> [>3>,>5>,>2>,>9>,>12>,>5>,>23>,>23>]> treeDepth>=> math.log(>len>(scores),>2>)> print>(>'The optimal value is : '>, end>=> '')> print>(minimax(>0>,>0>,>True>, scores, treeDepth))> # This code is contributed> # by rootshadow> |
>
단어 빠른 액세스 도구 모음
>
자바스크립트
> // Javascript program to find maximum score that> // maximizing player can get.> // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> >function> minimax(depth, nodeIndex, isMax,> >scores, h)> {> >// Terminating condition. i.e leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> > >// If current move is maximizer, find the maximum attainable> >// value> >if> (isMax)> >return> Math.max(minimax(depth+1, nodeIndex*2,>false>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>false>, scores, h));> > >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> Math.min(minimax(depth+1, nodeIndex*2,>true>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>true>, scores, h));> }> > // A utility function to find Log n in base 2> >function> log2(n)> {> return> (n==1)? 0 : 1 + log2(n/2);> }> > // Driver Code> >// The number of elements in scores must be> >// a power of 2.> >let scores = [3, 5, 2, 9, 12, 5, 23, 23];> >let n = scores.length;> >let h = log2(n);> >let res = minimax(0, 0,>true>, scores, h);> >document.write(>'The optimal value is : '> +res);> > > > |
자바의 이진 검색
>
>
산출:
The optimal value is: 12>
시간 복잡도 : O(b^d) b는 분기 인자이고 d는 그래프 또는 트리의 깊이 또는 겹 수입니다.
공간 복잡도 : b가 d로의 분기 인자인 O(bd)는 DFS와 유사한 트리의 최대 깊이입니다.
이 글의 목적은 간단한 예를 들어 Minimax를 소개하는 것입니다.
- 위의 예에서 플레이어에게는 두 가지 선택 사항만 있습니다. 일반적으로 더 많은 선택이 있을 수 있습니다. 이 경우 가능한 모든 이동에 대해 반복하여 최대값/최소값을 찾아야 합니다. 예를 들어, Tic-Tac-Toe에서는 첫 번째 플레이어가 9개의 가능한 움직임을 만들 수 있습니다.
- 위의 예에서는 점수(게임 트리의 잎)가 우리에게 제공됩니다. 일반적인 게임의 경우 이러한 값을 도출해야 합니다.
우리는 곧 Minimax 알고리즘을 이용한 Tic Tac Toe를 다루게 될 것입니다.
이 기사는 기고자: Akshay L. Aradhya.