최소극대화

최소극대화() 또는 미니맥스는 결정이론, 게임이론, 통계학, 철학에서 사용하는 개념으로 최악의 경우 발생가능한 손실(최대 손실)을 최소화 한다는 규칙이다. 손실이 아니라 이익이 기준이라면 최소 이익을 극대화한다는 의미에서 "maximin" 이라고 부르기도 한다. 원래 두 명의 참가자가 존재하는 제로섬 게임 이론으로부터 시작하였으나 (두 참가자가 순차적으로 행동하는 경우와 동시에 행동하는 경우 모두 포함), 더 복잡한 게임과 불확실성이 존재할 때의 일반적인 의사결정에 이르기까지 널리 쓰이고 있다

 게임 이론 

 일반적인 게임에서 
최소극대화 값은 다른 플레이어의 행동을 알지 못하더라도 플레이어가 얻을 수 있다고 확신할 수 있는 가장 높은 값이다. 동일하게, 다른 플레이어들이 플레이어의 행동을 알 때 플레이어가 받을 수밖에 없는 가장 낮은 값이다. 이것의 공식적인 정의는 다음과 같다:

여기서:

 는 해당 플레이어의 인덱스이다.
 는 플레이어 를 제외한 모든 다른 플레이어를 나타낸다.
 는 플레이어 가 취한 행동이다.
 는 다른 모든 플레이어가 취한 행동을 나타낸다.
 는 플레이어 의 가치 함수이다.

플레이어의 최소극대화 값을 계산하는 것은 최악의 경우 접근 방식으로 이루어진다. 플레이어의 각 가능한 행동에 대해, 다른 플레이어들의 모든 가능한 행동을 확인하고 최악의 행동 조합, 즉 플레이어 에게 가장 작은 값을 주는 조합을 결정한다. 그런 다음, 플레이어 가 이 가장 작은 값을 가능한 한 가장 높게 만들기 위해 어떤 행동을 취할 수 있는지 결정한다.

예를 들어, 다음 두 플레이어 게임을 고려해 보자. 첫 번째 플레이어("행 플레이어")는 , , 또는 의 세 가지 이동 중 하나를 선택할 수 있고, 두 번째 플레이어("열 플레이어")는 또는 의 두 가지 이동 중 하나를 선택할 수 있다. 두 이동 조합의 결과는 보수표에 표시된다.

(각 셀의 첫 번째 숫자는 행 플레이어의 보수이고, 두 번째 숫자는 열 플레이어의 보수이다).

예시를 위해 순수 전략만 고려한다. 각 플레이어를 차례로 확인한다.
 행 플레이어는 를 플레이하여 최소 의 보수를 보장받을 수 있다 (를 플레이하면 의 보수로 이어질 수 있으므로 위험하며, 을 플레이하면 의 보수가 나올 수 있다). 따라서: .
 열 플레이어는 을 플레이하여 최소 의 보수를 확보할 수 있다 (을 플레이하면 을 얻을 위험이 있다). 따라서: .

두 플레이어가 각각의 최소극대화 전략 을 플레이하면 보수 벡터는 이다.

플레이어의 극대화 최소 값은 다른 플레이어들이 플레이어의 행동을 알지 못하더라도 플레이어가 받도록 강요할 수 있는 가장 작은 값이다. 동일하게, 플레이어가 다른 플레이어의 행동을 알 때 얻을 수 있다고 확신할 수 있는 가장 큰 값이다. 이것의 공식적인 정의는 다음과 같다:

이 정의는 최소극대화 값과 매우 유사하며, 단지 최대화 및 최소화 연산자의 순서가 역전될 뿐이다. 위 예시에서:
 행 플레이어는 최대 (다른 플레이어가 을 플레이하는 경우) 또는 (다른 플레이어가 을 플레이하는 경우)의 값을 얻을 수 있으므로: 
 열 플레이어는 최대 (다른 플레이어가 를 플레이하는 경우), (을 플레이하는 경우) 또는 (를 플레이하는 경우)의 값을 얻을 수 있다. 따라서: 

모든 플레이어 에 대해 최소극대화 값은 극대화 최소 값보다 작거나 같다.

직관적으로, 최소극대화에서는 최소화 후에 최대화가 오므로, 플레이어 는 다른 플레이어들이 무엇을 할지 알기 전에 자신의 값을 최대화하려고 노력한다. 극대화 최소화에서는 최대화가 최소화보다 먼저 오므로, 플레이어 는 훨씬 더 유리한 위치에 있다. 그들은 다른 플레이어들이 무엇을 했는지 알고 자신의 값을 최대화한다.

표기법을 이해하는 또 다른 방법은 오른쪽에서 왼쪽으로 읽는 것이다.

라고 쓸 때, 초기 결과 집합 는 와 모두에 의존한다. 우리는 먼저 의 모든 가능한 값에 대해 에 대해 최대화함으로써 에서 를 주변화하여 에만 의존하는 주변 결과 집합 를 생성한다. 그런 다음 이러한 결과에 대해 에 대해 최소화한다. (최소극대화는 그 반대이다.)

와 이 항상 참이지만, 두 플레이어가 그들의 극대화 최소 전략을 플레이한 결과로 나오는 보수 벡터, 의 경우 또는 의 경우 는 두 플레이어가 최소극대화 전략을 플레이한 결과로 나오는 보수 벡터 와 유사하게 순위가 매겨질 수 없다.

 제로섬 게임에서 

두 플레이어 제로섬 게임에서는 극대화 최소 해가 내시 균형과 동일하다.

제로섬 게임의 맥락에서 극대화 최소 정리는 다음을 의미한다:

유한한 수의 전략을 가진 모든 2인 제로섬 게임에 대해, 값 와 각 플레이어에 대한 혼합 전략이 존재하여
(a) 플레이어 2의 전략이 주어졌을 때, 플레이어 1에게 가능한 최고의 보수는 이고,
(b) 플레이어 1의 전략이 주어졌을 때, 플레이어 2에게 가능한 최고의 보수는 −이다.
동일하게, 플레이어 1의 전략은 플레이어 2의 전략에 관계없이 그들에게 의 보수를 보장하며, 유사하게 플레이어 2는 그들에게 −의 보수를 보장할 수 있다. 극대화 최소라는 이름은 각 플레이어가 상대방에게 가능한 최대 보수를 최소화하기 때문에 생겨났다. 게임이 제로섬이므로, 그들은 또한 자신의 최대 손실을 최소화한다 (즉, 자신의 최소 보수를 최대화한다).
값이 없는 게임의 예도 참조하라.

 예시 

다음은 A와 B가 동시에 움직이는 제로섬 게임의 예시로, 최소극대화 해법을 보여준다. 각 플레이어가 세 가지 선택지를 가지고 있다고 가정하고 테이블에 표시된 A의 보수 행렬을 고려하자 ("플레이어 A의 보수 행렬"). B의 보수 행렬은 부호가 반대인 동일한 행렬이라고 가정하자 (즉, A1과 B1을 선택하면 B가 A에게 3을 지불한다). 그러면 A의 최소극대화 선택은 A2이다. 최악의 경우 1을 지불해야 하지만, B의 단순 최소극대화 선택은 B2이다. 최악의 경우 지불이 없기 때문이다. 그러나 이 해법은 안정적이지 않다. 왜냐하면 B가 A가 A2를 선택할 것이라고 믿으면 B는 1을 얻기 위해 B1을 선택할 것이고, A가 B가 B1을 선택할 것이라고 믿으면 A는 3을 얻기 위해 A1을 선택할 것이고, 그러면 B는 B2를 선택할 것이고, 결국 두 플레이어 모두 선택의 어려움을 깨달을 것이기 때문이다. 따라서 더 안정적인 전략이 필요하다.

일부 선택은 다른 선택에 의해 지배되므로 제거할 수 있다. A는 B가 무엇을 선택하든 A1 또는 A2가 더 나은 결과를 낳기 때문에 A3을 선택하지 않을 것이다. B는 A가 무엇을 선택하든 B1과 B2의 일부 혼합이 더 나은 결과를 낳기 때문에 B3을 선택하지 않을 것이다.

플레이어 A는 A1을 확률 로, A2를 확률 선택함으로써 예상 지불액이 보다 커지는 것을 피할 수 있다. A의 예상 보수는 B가 B1을 선택한 경우 이고, B가 B2를 선택한 경우 이다. 유사하게, B는 B1을 확률 로, B2를 확률 로 선택하는 무작위 전략을 사용하여 A가 무엇을 선택하든 최소 의 예상 이득을 보장할 수 있다. 이러한 혼합 극대화 최소 전략은 더 이상 개선될 수 없으며 이제 안정적이다.

 최소극대화 
자주, 게임 이론에서 최소극대화는 극대화 최소와 구별된다. 극대화 최소는 제로섬 게임에서 상대방의 최대 보수를 최소화하는 것을 나타내는 데 사용된다. 제로섬 게임에서는 이는 자신의 최대 손실을 최소화하고 자신의 최소 이득을 최대화하는 것과 동일하다.

"최소극대화"는 비제로섬 게임에서 자신의 최소 보수를 최대화하는 전략을 설명하는 데 흔히 사용되는 용어이다. 비제로섬 게임에서는 이는 일반적으로 상대방의 최대 이득을 최소화하는 것과 같지 않으며, 내시 균형 전략과도 같지 않다.

 반복 게임에서 
극대화 최소 값은 반복 게임 이론에서 매우 중요하다. 이 이론의 핵심 정리 중 하나인 민속 정리는 극대화 최소 값에 의존한다.

 조합론적 게임 이론 
조합론적 게임 이론에서는 게임 해법을 위한 극대화 최소 알고리즘이 있다.

아래에 설명된 극대화 최소 알고리즘의 간단한 버전은 틱택토와 같이 각 플레이어가 이기거나, 지거나, 비길 수 있는 게임을 다룬다. 플레이어 A가 한 수로 이길 수 있다면, 그들의 최선의 수는 그 이기는 수이다. 플레이어 B가 한 수는 플레이어 A가 한 수로 이길 수 있는 상황으로 이끌고, 다른 한 수는 플레이어 A가 최대로 비길 수 있는 상황으로 이끈다는 것을 알고 있다면, 플레이어 B의 최선의 수는 비기는 상황으로 이끄는 수이다. 게임 후반에는 "최선"의 수가 무엇인지 쉽게 알 수 있다. 극대화 최소 알고리즘은 게임의 끝에서부터 역으로 추적하여 최선의 수를 찾는 데 도움을 준다. 각 단계에서 플레이어 A는 A가 이길 확률을 최대화하려고 하고, 다음 차례에 플레이어 B는 A가 이길 확률을 최소화하려고 (즉, B 자신의 이길 확률을 최대화하려고) 한다고 가정한다.

 교대 이동이 있는 극대화 최소 알고리즘 
극대화 최소 알고리즘은 n인 게임, 보통 2인 게임에서 다음 수를 선택하기 위한 재귀 알고리즘이다. 각 위치 또는 게임 상태에는 값이 연결된다. 이 값은 위치 평가 함수를 통해 계산되며, 플레이어가 그 위치에 도달하는 것이 얼마나 좋은지를 나타낸다. 플레이어는 상대방의 가능한 다음 수로 인해 발생하는 위치의 최소값을 최대화하는 수를 둔다. 만약 A의 차례라면, A는 자신의 각 합법적인 수에 값을 부여한다.

가능한 할당 방법은 A의 확실한 승리를 +1로, B의 확실한 승리를 −1로 할당하는 것이다. 이는 존 H. 콘웨이가 개발한 조합론적 게임 이론으로 이어진다. 대안은 이동의 결과가 A의 즉각적인 승리이면 양의 무한대를 할당하고, B의 즉각적인 승리이면 음의 무한대를 할당하는 규칙을 사용하는 것이다. 다른 모든 이동에 대한 A의 값은 B의 가능한 각 응답으로 인해 발생하는 값 중 최대값이다. 이러한 이유로 A는 최대화 플레이어라고 불리며 B는 최소화 플레이어라고 불린다. 따라서 극대화 최소 알고리즘이라는 이름이 붙었다. 위 알고리즘은 모든 위치의 값이 일부 최종 승리 또는 패배 위치의 값이 되므로 모든 위치에 양 또는 음의 무한대 값을 할당한다. 이는 일반적으로 체스나 바둑과 같은 복잡한 게임의 마지막에만 가능하며, 게임이 완료될 때까지 모두 내다보는 것은 계산적으로 불가능하다. 대신, 위치에는 플레이어 중 한 명의 승리로 이어질 것이라는 믿음의 정도를 추정하는 유한한 값이 주어진다.

가능한 모든 전체 시퀀스를 고려하지 않고 비최종 게임 상태에 값을 부여하는 휴리스틱 평가 함수를 제공할 수 있다면 이를 확장할 수 있다. 그러면 극대화 최소 알고리즘을 특정 수의 이동만 미리 살펴보는 것으로 제한할 수 있다. 이 숫자를 "탐색 깊이"라고 하며 "플라이" 단위로 측정한다. 예를 들어, 체스 컴퓨터 딥 블루 (당시 세계 챔피언 가리 카스파로프를 처음으로 이긴 컴퓨터)는 최소 12 플라이를 미리 내다본 다음 휴리스틱 평가 함수를 적용했다.

이 알고리즘은 노드를 탐색하는 것으로 생각할 수 있다. 트리의 유효 분기 요소는 각 노드의 평균 자식 수 (즉, 한 위치에서 가능한 합법적인 이동의 평균 수)이다. 탐색할 노드의 수는 일반적으로 플라이 수에 따라 기하급수적으로 증가한다 (강제 이동 또는 반복 위치를 평가하는 경우 지수보다 작다). 따라서 게임 분석을 위해 탐색할 노드의 수는 대략 분기 요소의 플라이 수 제곱이다. 따라서 극대화 최소 알고리즘을 사용하여 체스와 같은 게임을 완전히 분석하는 것은 비실용적이다.

순진한 극대화 최소 알고리즘의 성능은 알파-베타 가지치기를 사용하여 결과에 영향을 주지 않으면서 크게 향상될 수 있다. 다른 휴리스틱 가지치기 방법도 사용될 수 있지만, 모든 방법이 가지치기하지 않은 검색과 동일한 결과를 보장하는 것은 아니다.

순진한 극대화 최소 알고리즘은 극대화 최소 점수와 함께 전체 주요 변형을 추가로 반환하도록 사소하게 수정될 수 있다.

 의사코드 
깊이 제한 극대화 최소 알고리즘의 의사코드는 다음과 같다.

 함수 minimax(노드, 깊이, maximizingPlayer) 은
 만약 깊이 = 0 또는 노드가 터미널 노드 이면
 반환 노드의 휴리스틱 값
 만약 maximizingPlayer 이면
 값 := −∞
 각 노드의 자식 에 대해
 값 := max(값, minimax(자식, 깊이 − 1, FALSE))
 반환 값
 그렇지 않으면 (* 최소화 플레이어 *)
 값 := +∞
 각 노드의 자식 에 대해
 값 := min(값, minimax(자식, 깊이 − 1, TRUE))
 반환 값

 (* 초기 호출 *)
 minimax(원점, 깊이, TRUE)

극대화 최소 함수는 리프 노드 (터미널 노드 및 최대 검색 깊이의 노드)에 대한 휴리스틱 값을 반환한다. 비리프 노드는 후손 리프 노드로부터 값을 상속받는다. 휴리스틱 값은 최대화 플레이어에게 노드의 유리함을 측정하는 점수이다. 따라서 최대화 플레이어에게 승리와 같은 유리한 결과를 낳는 노드는 최소화 플레이어에게 더 유리한 노드보다 높은 점수를 갖는다. 터미널 (게임 종료) 리프 노드의 휴리스틱 값은 최대화 플레이어의 승리, 패배 또는 무승부에 해당하는 점수이다. 최대 검색 깊이의 비터미널 리프 노드의 경우 평가 함수는 노드의 휴리스틱 값을 추정한다. 이 추정치의 품질과 검색 깊이가 최종 극대화 최소 결과의 품질과 정확도를 결정한다.

극대화 최소는 코드에서 두 플레이어(최대화 플레이어와 최소화 플레이어)를 별도로 취급한다. 라는 관찰을 기반으로, 극대화 최소는 종종 네가맥스 알고리즘으로 단순화될 수 있다.

 예시 
섬네일|400px|극대화 최소 트리 예시
섬네일|400px|초기 무한대 (또는 임의로 큰) 값을 비어있음으로 대체하고 네가맥스 코딩 단순화를 피함으로써 인간 친화적으로 만들려고 시도하는 애니메이션 교육 예시.

플레이어당 한 턴에 최대 두 가지 움직임만 가능한 게임을 가정해 보자. 알고리즘은 오른쪽에 트리를 생성한다. 여기서 원은 알고리즘을 실행하는 플레이어(최대화 플레이어)의 움직임을 나타내고, 사각형은 상대방(최소화 플레이어)의 움직임을 나타낸다. 위에서 설명했듯이 계산 리소스의 한계 때문에 트리는 4단계 미리 보기로 제한된다.

알고리즘은 휴리스틱 평가 함수를 사용하여 각 리프 노드를 평가하여 표시된 값을 얻는다. 최대화 플레이어가 승리하는 움직임에는 양의 무한대가 할당되고, 최소화 플레이어가 승리하는 움직임에는 음의 무한대가 할당된다. 레벨 3에서 알고리즘은 각 노드에 대해 자식 노드 값 중 가장 작은 것을 선택하고 이를 해당 노드에 할당한다 (예: 왼쪽 노드는 "10"과 "+∞" 중에서 최소값을 선택하여 "10"을 자신에게 할당한다). 레벨 2의 다음 단계는 각 노드에 대해 자식 노드 값 중 가장 큰 것을 선택하는 것이다. 다시 한번, 값은 각 부모 노드에 할당된다. 알고리즘은 루트 노드에 도달할 때까지 자식 노드의 최대값과 최소값을 번갈아 평가하며, 가장 큰 값을 가진 움직임을 선택한다 (그림에서 파란색 화살표로 표시). 이것이 플레이어가 가능한 최대 손실을 최소화하기 위해 취해야 할 움직임이다.

 개별 결정에서 

 불확실성에 직면하여 
극대화 최소 이론은 다른 플레이어가 없지만 결정의 결과가 알려지지 않은 사실에 의존하는 결정으로 확장되었다. 예를 들어, 광물 탐사를 결정하는 것은 비용을 수반하며, 광물이 존재하지 않으면 낭비되지만, 존재하면 큰 보상을 가져온다. 한 가지 접근 방식은 이를 자연과의 게임으로 취급하고 (자연의 움직임 참조), 머피의 법칙 또는 저항주의 (철학)와 유사한 사고방식을 사용하여 최대 예상 손실을 최소화하는 접근 방식을 두 플레이어 제로섬 게임과 동일한 기술을 사용하여 취하는 것이다.

또한, 주사위와 같은 우연이 요소로 작용하는 2인 게임을 위해 기대 극대화 최소 트리가 개발되었다.

 통계적 의사결정 이론에서의 기준 

고전적인 통계적 결정 이론에서 우리는 매개변수 를 추정하는 데 사용되는 추정량 를 가지고 있다. 또한 일반적으로 손실 함수의 적분으로 지정되는 위험 함수 를 가정한다. 이 프레임워크에서 는 다음을 만족하면 극대화 최소라고 불린다.

 

결정 이론적 프레임워크의 대안적인 기준은 사전 분포 가 있는 경우 베이즈 추정량이다. 추정량은 평균 위험을 최소화하면 베이즈이다.

 

 비확률적 결정 이론 
극대화 최소 의사결정의 핵심 특징은 비확률적이라는 것이다. 기댓값이나 기대효용을 사용하는 결정과 달리, 다양한 결과의 확률에 대한 가정을 하지 않고 가능한 결과가 무엇인지에 대한 시나리오 분석만 수행한다. 따라서 다른 결정 기술과 달리 가정 변경에 강건하다. 이 비확률적 접근 방식의 다양한 확장이 존재하며, 특히 최소극대화 후회와 정보 공백 의사결정 이론이 있다.

더욱이, 극대화 최소는 서수 측정 (결과를 비교하고 순위를 매기는 것)만 요구하며, 간격 측정 (결과에 "얼마나 더 좋거나 나쁜지" 포함하는 것)을 요구하지 않으며, 모델링된 결과만을 사용하여 서수 데이터를 반환한다. 극대화 최소 분석의 결론은 "이 전략은 최악의 경우가 (결과)이며, 이는 다른 어떤 전략보다 덜 나쁘기 때문에 극대화 최소이다"이다. 결론이 "이 전략은 와 같은 형태인 기댓값 분석과 비교해 보라. 따라서 극대화 최소는 서수 데이터에 사용할 수 있으며 더 투명할 수 있다.

 극대화 최소 
"차악" 투표 (LEV) 개념은 유권자들이 두 명 이상의 후보자에 직면했을 때 가장 해롭지 않거나 "차악"이라고 인식하는 후보자를 선택하는 극대화 최소 전략의 한 형태로 볼 수 있다. 이를 위해 "투표는 우리의 가치를 반영하지 못하거나 기업 엘리트들이 수용할 수 있는 선택지로 제한하도록 고안된 부패한 시스템에 대한 보복으로 향하는 개인적인 자기 표현이나 도덕적 판단의 한 형태로 간주되어서는 안 되며," 오히려 피해나 손실을 줄이는 기회로 간주되어야 한다.

 철학에서 최소극대화 
철학에서 "최소극대화"라는 용어는 존 롤스의 정의론에서 차등 원칙과 관련하여 자주 사용된다. 롤스는 이 원칙을 "사회 및 경제적 불평등은 사회의 가장 불리한 구성원에게 가장 큰 이익이 되도록 배열되어야 한다"고 명시하는 규칙으로 정의했다.

 같이 보기 
 기회비용

 각주 

 외부 링크 
 A visualization applet
 "Maximin principle" from A Dictionary of Philosophical Terms and Names.
 Play a betting-and-bluffing game against a mixed minimax strategy
 The Dictionary of Algorithms and Data Structures entry for minimax.
 Minimax (with or without alpha-beta pruning) algorithm visualization — game tree solving (Java Applet), for balance or off-balance trees.
 Minimax Tutorial with a Numerical Solution Platform
 Java implementation used in a Checkers Game

분류:게임 인공지능
분류:그래프 알고리즘
분류:검색 알고리즘
분류:게임 이론
분류:결정 이론
분류:고정점
분류:이산수학 정리
분류:최적화 알고리즘