• Mini-max 알고리즘은 의사 결정 및 게임 이론에 사용되는 재귀 또는 역추적 알고리즘입니다. 상대방도 최적의 플레이를 하고 있다는 가정 하에 플레이어에게 최적의 움직임을 제공합니다.
• Mini-Max 알고리즘은 재귀를 사용하여 게임 트리를 검색합니다.
• Min-Max 알고리즘은 주로 AI 게임 플레이에 사용됩니다. 체스, 체커, 틱택토, 바둑 및 다양한 견인 게임 등이 있습니다. 이 알고리즘은 현재 상태에 대한 최소최대값 결정을 계산합니다.
• 이 알고리즘에서는 두 명의 플레이어가 게임을 하며, 하나는 MAX라고 하고 다른 하나는 MIN이라고 합니다.
• 상대방 플레이어가 최소한의 이익을 얻고 최대 이익을 얻으므로 두 플레이어 모두 싸웁니다.
• 게임의 두 플레이어는 서로 상대이며 MAX는 최대화된 값을 선택하고 MIN은 최소화된 값을 선택합니다.
• 미니맥스 알고리즘은 완전한 게임 트리 탐색을 위해 깊이 우선 검색 알고리즘을 수행합니다.
• minimax 알고리즘은 트리의 터미널 노드까지 계속 진행한 다음 재귀로 트리를 역추적합니다.

MinMax 알고리즘의 의사 코드:

 function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva 

최초 통화:

Minimax(노드, 3, 참)

최소-최대 알고리즘 작동:

• Minimax 알고리즘의 작동은 예를 사용하여 쉽게 설명할 수 있습니다. 아래에서는 2인용 게임을 나타내는 게임 트리의 예를 살펴보았습니다.
• 이 예에는 Maximizer와 Minimizer라는 두 개의 플레이어가 있습니다.
• Maximizer는 가능한 최대 점수를 얻으려고 시도하고 Minimizer는 가능한 최소 점수를 얻으려고 시도합니다.
• 이 알고리즘은 DFS를 적용하므로 이 게임 트리에서는 리프를 통해 터미널 노드에 도달해야 합니다.
• 터미널 노드에는 터미널 값이 제공되므로 해당 값을 비교하고 초기 상태가 발생할 때까지 트리를 역추적합니다. 다음은 2인용 게임 트리를 해결하는 주요 단계입니다.

1 단계: 첫 번째 단계에서 알고리즘은 전체 게임 트리를 생성하고 유틸리티 함수를 적용하여 최종 상태에 대한 유틸리티 값을 얻습니다. 아래 트리 다이어그램에서 A가 트리의 초기 상태라고 가정하겠습니다. 최대화기가 최악의 초기값 =-무한대를 갖는 첫 번째 회전을 취하고, 최소화기가 최악의 초기값 = +무한대를 갖는 다음 회전을 취한다고 가정합니다.

2 단계: 이제 먼저 Maximizer의 유틸리티 값을 찾습니다. 초기 값은 -이므로 최종 상태의 각 값을 Maximizer의 초기 값과 비교하여 더 높은 노드 값을 결정합니다. 그것은 모든 것 중에서 최대값을 찾을 것입니다.

• 노드 D의 경우 max(-1,- -무한대) => max(-1,4)= 4
• 노드 E의 경우 max(2, -) => max(2, 6)= 6
• 노드 F의 경우 max(-3, -) => max(-3,-5) = -3
• 노드 G의 경우 max(0, -무한대) = max(0, 7) = 7

3단계: 다음 단계에서는 최소화에 대한 차례이므로 모든 노드 값을 + 과 비교하여 3을 찾습니다.^rd레이어 노드 값.

• 노드 B= min(4,6) = 4
• 노드 C= min (-3, 7) = -3

4단계: 이제 Maximizer의 차례이며 다시 모든 노드 값의 최대값을 선택하고 루트 노드의 최대값을 찾습니다. 이 게임 트리에는 4개의 레이어만 있으므로 루트 노드에 즉시 도달하지만 실제 게임에서는 4개 이상의 레이어가 있습니다.

• 노드 A의 경우 max(4, -3)= 4

이것이 Minimax 2인용 게임의 전체 작업 흐름이었습니다.

Mini-Max 알고리즘의 속성:

완벽한-최소-최대 알고리즘이 완료되었습니다. 유한 검색 트리에서 확실히 해결책(존재하는 경우)을 찾을 것입니다.최적-Min-Max 알고리즘은 두 상대 모두 최적의 플레이를 하고 있을 때 최적입니다.시간복잡도 -게임 트리에 대해 DFS를 수행하므로 Min-Max 알고리즘의 시간 복잡도는 다음과 같습니다. 오(b^중) 여기서 b는 게임 트리의 분기 요소이고 m은 트리의 최대 깊이입니다.공간 복잡도 -Mini-max 알고리즘의 공간 복잡도는 DFS와 유사합니다. 에 대한 .

minimax 알고리즘의 한계:

미니맥스 알고리즘의 가장 큰 단점은 체스, 바둑 등과 같은 복잡한 게임의 경우 속도가 매우 느려진다는 것입니다. 이러한 유형의 게임은 분기 요인이 크며 플레이어가 결정할 수 있는 선택권이 많습니다. Minimax 알고리즘의 이러한 제한은 다음을 통해 개선될 수 있습니다. 알파베타 가지치기 이에 대해서는 다음 주제에서 논의했습니다.