Minimax(때로는 Minmax, MM 또는 saddle point)은 인공지능, 결정 이론, 조합 게임 이론, 통계학, 철학에서 사용되는 결정 규칙이다. 이는 최악의 경우(최대 손실 시나리오)에 대해 가능한 손실을 최소화하는 것을 목표로 한다. 이득을 다룰 때는 'maximin' - 최소 이득을 최대화하는 것 - 으로 불린다. 원래 여러 플레이어의 제로섬 게임 이론을 위해 공식화되었으며, 플레이어들이 번갈아 움직이는 경우와 동시에 움직이는 경우를 모두 다루며, 더 복잡한 게임과 불확실성 하의 일반적인 의사 결정으로도 확장되었다.
이 개념은 한 플레이어의 이득이 다른 플레이어의 손실이 되는 적대적 설정에서 핵심적이다. 이러한 맥락에서 minimax는 보수적인 전략을 제공한다: 상대방이 항상 당신에게 최악인 행동을 선택할 것이라고 가정하고, 보장된 보상을 최대화하는 움직임을 선택하는 것이다. 이 원리는 머신 러닝과 딥 러닝의 많은 알고리즘, 특히 생성 모델 훈련과 견고한 시스템 설계의 기초가 된다.
게임 이론 기초
게임 이론에서 maximin 값은 다른 플레이어들의 행동을 알지 못한 채 플레이어가 확실히 얻을 수 있는 가장 높은 값이며, 동등하게는 다른 플레이어들이 플레이어의 행동을 알 때 그 플레이어가 받도록 강제할 수 있는 가장 낮은 값이다. 공식 정의는 다음과 같다: v_i_underline = max_{a_i} min_{a_{-i}} v_i(a_i, a_{-i}), 여기서 i는 플레이어의 인덱스, a_i는 플레이어 i가 취한 행동, a_{-i}는 다른 모든 플레이어의 행동, v_i는 플레이어 i의 가치 함수이다.
maximin 값을 계산하는 것은 최악의 경우 접근법을 사용한다: 플레이어의 각 가능한 행동에 대해 다른 플레이어들의 모든 가능한 행동을 확인하고 최악의 조합 - 가장 작은 값을 주는 조합 - 을 결정한다. 그런 다음 이 가장 작은 값을 가능한 한 높게 만드는 행동을 선택한다. 예를 들어, 행 플레이어가 T, M, B를 선택할 수 있고 열 플레이어가 L 또는 R을 선택할 수 있는 2인 게임을 고려해 보자. 보상은 표에 나와 있다. 행 플레이어는 T를 플레이하여 최소 2의 보상을 보장할 수 있으며(B는 -100의 위험이 있고, M은 -10을 초래할 수 있음), 따라서 v_row_underline = 2이다. 열 플레이어는 L을 플레이하여 최소 0을 확보할 수 있으며(R은 -20의 위험이 있음), 따라서 v_col_underline = 0이다. 둘 다 maximin 전략(T, L)을 플레이하면 보상 벡터는 (3, 1)이다.
플레이어의 minimax 값은 다른 플레이어들이 플레이어의 행동을 알지 못한 채 그 플레이어가 받도록 강제할 수 있는 가장 작은 값이며, 동등하게는 다른 플레이어들의 행동을 알 때 플레이어가 확실히 얻을 수 있는 가장 큰 값이다. 공식 정의는 다음과 같다: v_i_overline = min_{a_{-i}} max_{a_i} v_i(a_i, a_{-i}). 제로섬 게임에서 각 플레이어의 minimax 값은 maximin 값과 같으며, 이는 minimax 정리로 이어진다.
Minimax 정리와 제로섬 게임
1928년 John von Neumann이 증명한 minimax 정리는 유한한 2인 제로섬 게임에서 혼합 전략을 사용할 때 maximin 값이 minimax 값과 같다고 명시한다. 이 정리는 균형 분석의 기초를 제공한다. 이러한 게임에서 게임의 가치는 두 플레이어가 최적으로 플레이할 때의 기대 보상이다. 정리는 플레이어가 최소한 이 값을 보장할 수 있고, 상대방이 그 값을 넘지 않도록 제한할 수 있음을 보장한다.
동시 이동 게임의 경우, 개념은 순수 행동에 대해 무작위화하는 혼합 전략으로 확장된다. minimax 정리는 혼합 전략에서 안장점의 존재를 보장하며, 이는 어느 플레이어도 일방적으로 이탈하여 보상을 개선할 수 없는 전략 쌍이다. 이 결과는 신경망 훈련에서 근본적이며, 적대적 예제가 유사한 최악의 경우 원리를 사용하여 분석된다.
인공지능에서의 응용
AI에서 minimax는 게임 및 적대적 시나리오의 의사 결정에 널리 사용된다. 전형적인 예는 체스, 체커 또는 틱택토와 같은 2인 턴제 게임을 위한 minimax 알고리즘이다. 알고리즘은 상대방이 최적으로 플레이한다고 가정하고 게임 트리를 재귀적으로 평가한다. 각 노드에서 플레이어는 최소 이득을 최대화하는 움직임을 선택하고, 상대방은 플레이어의 최대 이득을 최소화하는 움직임을 선택한다. 이는 종종 알파-베타 가지치기와 결합되어 계산 복잡성을 줄인다.
대규모 언어 모델과 트랜스포머 아키텍처에서 minimax 원리는 적대적 훈련에 나타나며, 모델이 최악의 경우 섭동에 대해 견고하도록 훈련된다. 예를 들어, 생성적 적대 신경망(GAN)은 minimax 목적 함수를 사용한다: 생성자는 판별자가 실제 데이터와 가짜 데이터를 구별하는 능력을 최소화하려 하고, 판별자는 정확도를 최대화하려 한다. 이 적대적 과정은 딥 러닝에서 minimax의 직접적인 응용이다.
확장과 변형
Minimax는 더 복잡한 게임으로 확장되었으며, 기회가 있는 게임(예: 백개먼)은 expectiminimax를 사용하고, 불완전 정보 게임은 counterfactual regret minimization과 같은 기법을 사용한다. 강화 학습에서 minimax는 견고한 제어 및 다중 에이전트 설정에 사용되며, 에이전트는 최악의 경우 상대방 행동을 고려해야 한다. 이 개념은 최대 위험을 최소화하는 minimax 추정량이 있는 최적화 및 통계학에도 나타난다.
컴퓨터 체스 및 기타 게임 플레이 AI에서 알파-베타 가지치기를 사용한 minimax는 핵심 기법으로 남아 있지만, OpenAI 및 Google DeepMind와 같은 현대 시스템은 종종 minimax 유사 목적 함수를 통합한 머신 러닝 접근법을 사용한다. 이 원리는 불확실성 하에서 행동을 선택할 때 최악의 경우 손실을 최소화하는 옵션을 선택하는 결정 이론에서도 관련이 있다.
역사적 맥락과 관련 개념
Minimax 규칙은 John von Neumann과 Oskar Morgenstern과 같은 수학자들의 기여로 게임 이론과 결정 이론에 뿌리를 두고 있다. 이는 최적화의 안장점 개념 및 비제로섬 게임의 내시 균형과 밀접하게 관련된다. 철학에서 minimax는 합리성과 위험 회피에 대한 논의에서 사용된다.
현대 AI에서 minimax는 최악의 경우 가정 대신 사전 확률을 사용하는 베이지안 결정 이론과 종종 대조된다. minimax는 보수적인 반면, 베이지안 방법은 더 유연할 수 있다. 이 둘 사이의 선택은 확률적 정보의 가용성에 달려 있다. AI 연구에서 minimax는 특히 적대적 환경에서 의사 결정 알고리즘을 평가하는 기준점으로 남아 있다.
같이 보기
- 알파-베타 가지치기
- 게임 이론
- 제로섬 게임
- 적대적 머신 러닝