최소극대화

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 게임 이론
3. 조합 게임 이론
- 3.1. 최소극대화 알고리즘 (간단한 버전)
- 3.2. 최소극대화 알고리즘 (번갈아 가며 움직이는 경우)
4. 게임 트리
5. 사고 프로그램의 기본 원리
6. 선행 탐색 (미니맥스법 전개)
- 6.1. 필승 수읽기와 완전 수읽기
7. 의사 코드
- 7.1. 네가맥스(Negamax)법
8. 응용 알고리즘
9. 개인 의사 결정에서의 최소극대화
- 9.1. 통계적 의사 결정 이론에서의 최소극대화 기준
10. 정치에서의 최소극대화
참조

1. 개요

최소극대화(Minimax)는 게임 이론에서 상대방의 최악의 수를 고려하여 자신의 최선의 수를 선택하는 의사 결정 방식이다.
게임 이론에서, 최소극대화는 게임 트리를 통해 각 국면의 평가값을 계산하며, 자신의 차례에는 최대값을, 상대방의 차례에는 최소값을 선택하는 방식으로 작동한다. 이러한 방식은 완전 정보 게임의 해법을 찾기 위한 알고리즘으로 사용되며, 특히 2인 제로섬 게임에서 내쉬 균형과 동일한 결과를 도출한다. 최소극대화는 일반 게임, 조합 게임 이론, 그리고 개인의 의사 결정 및 통계적 의사 결정 이론에도 적용될 수 있다.
응용 알고리즘으로는 탐색 효율을 높이기 위한 알파-베타 가지치기가 있으며, 실제 게임 프로그램에 널리 사용된다. 또한, 정치 및 철학 분야에서도 "덜 나쁜 선택" 투표 전략이나, 존 롤스의 정의론에서 차등의 원칙과 관련하여 논의된다.

더 읽어볼만한 페이지

이산수학 정리 - 애로의 불가능성 정리
애로의 불가능성 정리는 3개 이상의 선택지에서 약한 파레토, 무관한 대안으로부터의 독립성, 비독재성을 모두 만족하는 사회 후생 함수는 존재하지 않음을 증명한 정리이다.
이산수학 정리 - 비둘기집 원리
비둘기집 원리는 n개의 비둘기집에 n+1마리 이상의 비둘기를 넣으면 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어간다는 간단한 원리이며, 귀류법으로 증명되고, 소프트볼 팀 구성, 해시 테이블 충돌 등 다양한 분야에 응용된다.
게임 인공지능 - 구글 딥마인드
구글 딥마인드가 개발한 스타크래프트 II 인공지능 알파스타는 프로게이머를 상대로 뛰어난 실력을 입증했으며, 딥마인드는 이를 인공 일반 지능 개발을 위한 시도로 간주한다.
게임 인공지능 - 컴퓨터 올림피아드
컴퓨터 올림피아드는 컴퓨터 프로그램 간의 지능 대결을 펼치는 대회로, 1989년 런던에서 시작되어 1992년 중단되었다가 2000년에 부활했으며, 국제 컴퓨터 게임 협회가 매년 체스, 바둑, 브리지 등 다양한 게임의 컴퓨터 프로그램들을 대상으로 대회를 개최한다.
고정점 - 도메인 이론
도메인 이론은 정보 조각과 부분 계산 결과로 해석되는 부분 순서 집합을 연구하여 정보 확장, 일관성 분석, 계산 과정의 수렴성 및 연속성을 형식화하는 분야로, 람다 대수 의미론 연구에서 동기를 얻어 컴퓨터 과학에 응용된다.
고정점 - 브라우어르 고정점 정리
브라우어르 고정점 정리는 콤팩트 볼록 집합에서 자기 자신으로 가는 연속 함수는 반드시 고정점을 가진다는 정리로, 다양한 공간에서 여러 형태로 표현되며 함수해석학에서 중요한 역할을 한다.

최소극대화
개요
종류	의사 결정 규칙
목표	최악의 시나리오에서 발생 가능한 손실을 최소화
특징	보수적인 접근 방식
활용 분야	게임 이론 의사 결정 이론 통계
상세 내용
설명	최소극대화 (Minimax)는 게임 이론, 의사 결정 이론, 통계에서 불확실성 하에서 최악의 시나리오에 대한 가능한 손실을 최소화하기 위해 사용하는 의사 결정 규칙이다. 원래는 영합 게임 이론에서, 한 플레이어의 손실은 다른 플레이어의 이득이 되도록, 두 플레이어의 상황을 다루기 위해 고안되었다. 최소극대화는 상대방이 최고의 패를 둔다고 가정하고 자신의 최악의 결과를 최소화하는 전략을 선택한다.
게임 이론에서의 최소극대화
정의	게임 이론에서 최소극대화는 플레이어가 상대방이 어떤 행동을 취하든 자신의 잠재적 손실을 최소화하는 전략을 찾는 것이다. 이는 특히 두 플레이어가 서로 반대되는 목표를 가진 영합 게임에서 유용하다.
예시	틱택토와 같은 게임에서, 플레이어는 상대방이 최선의 수로 응수할 것이라고 가정하고, 자신이 질 가능성을 최소화하는 수를 선택한다.
의사 결정 이론에서의 최소극대화
정의	의사 결정 이론에서 최소극대화는 불확실한 상황에서 최악의 결과가 가장 덜 나쁜 선택을 하는 것이다. 즉, 가능한 결과 중 가장 나쁜 결과를 개선하는 데 초점을 맞춘다.
활용	재무: 투자자가 시장이 하락할 경우 발생할 수 있는 최대 손실을 최소화하는 포트폴리오를 선택할 수 있다. 보험: 보험 회사가 최악의 시나리오에서 발생할 수 있는 최대 지급액을 최소화하는 보험 상품을 설계할 수 있다. 공급망 관리: 기업이 공급망 중단으로 인한 최대 손실을 최소화하는 공급망 전략을 수립할 수 있다.
통계에서의 최소극대화
정의	통계에서 최소극대화는 추정량의 최대 위험 (최대 오류)을 최소화하는 추정량을 찾는 방법이다. 이는 추정량의 성능이 특정 분포에 의존하지 않도록 하는 데 유용하다.
활용	로버스트 통계: 이상치에 덜 민감한 통계적 추정량을 개발하는 데 사용된다. 비모수 통계: 데이터의 분포에 대한 가정을 최소화하는 통계적 방법을 개발하는 데 사용된다.
관련 개념
최대최소화 (Maximin)	최소극대화와 반대되는 개념으로, 최악의 시나리오에서 얻을 수 있는 최대 이익을 극대화하는 전략이다. 이는 낙관적인 접근 방식으로, 최상의 결과를 기대하며 의사 결정을 내린다.
장단점
장점	구현이 비교적 간단하다. 최악의 시나리오에 대한 대비를 할 수 있다. 불확실성이 높은 상황에서 유용하다.
단점	지나치게 보수적인 전략으로 이어질 수 있다. 평균적인 결과는 고려하지 않는다. 모든 상황에 적합한 것은 아니다.
기타
주의 사항	최소극대화는 항상 최선의 선택을 보장하지는 않는다. 상황에 따라 다른 의사 결정 규칙이 더 적합할 수 있다.

2. 게임 이론

최소극대화 알고리즘은 주로 2인 제로섬 게임에서 사용되며, 각 플레이어는 상대방의 가능한 전략을 고려하여 자신의 최선의 전략을 선택한다.^[4]

2인 제로섬 게임에서 최소극대화 해는 내쉬 균형과 동일하다. 최소극대화라는 이름은 각 플레이어가 상대방의 최대 보상을 최소화하려고 하기 때문에 붙여졌다. 유한한 수의 전략을 가진 모든 2인 제로섬 게임에 대해, 값 와 각 플레이어에 대한 혼합 전략이 존재한다.

(a) 플레이어 2의 전략이 주어지면, 플레이어 1이 얻을 수 있는 최고의 보상은 이다.
(b) 플레이어 1의 전략이 주어지면, 플레이어 2가 얻을 수 있는 최고의 보상은 −이다.

이는 플레이어 1의 전략은 플레이어 2의 전략에 관계없이 보상 를 보장하며, 마찬가지로 플레이어 2는 보상 −를 보장할 수 있다는 것과 같다.

align="bottom" style="caption-side: bottom" | A의 보수 행렬
	B는 B1을 선택	B는 B2를 선택	B는 B3을 선택
A는 A1을 선택	+3	−2	+2
A는 A2를 선택	−1	0	+4
A는 A3을 선택	−4	−3	+1

'''A'''와 '''B'''가 동시에 움직이는 제로섬 게임을 예시로 들어보자. 각 플레이어가 세 가지 선택지를 가지고 있고, 표("A의 보수 행렬")에 표시된 '''A'''의 보수 행렬을 고려한다. '''B'''의 보수 행렬은 부호가 반대인 동일한 행렬이라고 가정한다.

이 경우, '''A'''의 최소극대화 선택은 A2인데, 최악의 결과는 1을 지불해야 하는 것이기 때문이다. 반면 '''B'''의 간단한 최소극대화 선택은 B2인데, 최악의 결과는 지불이 없는 것이기 때문이다. 하지만 이 해법은 불안정하다. 만약 '''B'''가 '''A'''가 A2를 선택할 것이라고 믿는다면, '''B'''는 B1을 선택하여 1을 얻을 것이고, 그러면 '''A'''는 A1을 선택하여 3을 얻을 것이고, 그러면 '''B'''는 B2를 선택할 것이며, 결국 두 플레이어 모두 선택하기 어렵다는 것을 깨닫게 될 것이다. 따라서 더 안정적인 전략이 필요하다.

일부 선택은 다른 선택에 ''지배''당하며 제거될 수 있다. '''A'''는 A3을 선택하지 않을 것이다. 왜냐하면 '''B'''가 무엇을 선택하든 A1 또는 A2가 더 나은 결과를 낼 것이기 때문이다. '''B'''는 B3을 선택하지 않을 것이다. 왜냐하면 '''A'''가 무엇을 선택하든 B1과 B2의 일부 혼합이 더 나은 결과를 낼 것이기 때문이다.

플레이어 '''A'''는 A1을 1/6의 확률로 선택하고 A2를 5/6의 확률로 선택하여 1/3 이상을 예상하여 지불하는 것을 피할 수 있다. 마찬가지로, '''B'''는 B1을 1/3의 확률로 선택하고 B2를 2/3의 확률로 선택하는 무작위 전략을 사용하여 최소 1/3의 예상 이익을 보장할 수 있다. 이러한 혼합된 최소극대화 전략은 개선될 수 없으며 이제 안정적이다.

2. 1. 일반 게임에서의 최소극대화

일반적인 게임에서 최소극대화 값은 상대방이 어떤 행동을 하든 상관없이 내가 확실하게 얻을 수 있는 가장 높은 값이다. 반대로, 최소최대화 값은 상대방이 나의 행동을 알고 있을 때, 상대방이 나에게 강요해서 내가 받을 수밖에 없는 가장 작은 값이다. 최소극대화 값은 항상 최소최대화 값보다 작거나 같다.

최소극대화 값을 구하는 공식은 다음과 같다.

:

\underline{v_i} = \max_{a_i} \min_{a_{-i}} {v_i(a_i,a_{-i})}

: 값을 구하고자 하는 플레이어
$-i$ : 를 제외한 다른 모든 플레이어
$a_i$ : 플레이어 의 행동
$a_{-i}$ : 다른 모든 플레이어의 행동
$v_i$ : 플레이어 의 가치 함수

최소극대화 값을 계산할 때는, 내가 어떤 행동을 했을 때 상대방이 최악의 선택을 한다고 가정한다. 각각의 내 행동에 대해 상대방의 모든 행동을 고려하여 가장 낮은 값을 찾고, 그 낮은 값들 중에서 가장 높은 값을 만드는 나의 행동을 선택한다.

예를 들어, 다음 표와 같은 게임을 생각해 보자.

	L	R
T	3, 1	2, -20
M	5, 0	-10, 1
B	-100, 2	4, 4

행 플레이어 (첫 번째 플레이어)는 T, M, B 중 하나를 선택
열 플레이어 (두 번째 플레이어)는 L, R 중 하나를 선택
표 안의 숫자는 (행 플레이어의 보상, 열 플레이어의 보상)

행 플레이어는 T를 선택하면 최소 2를 얻을 수 있다. (M을 선택하면 -10, B를 선택하면 -100을 받을 수도 있기 때문). 따라서 행 플레이어의 최소극대화 값은

\underline{v_{row}} = 2

이다. 열 플레이어는 L을 선택하면 최소 0을 얻을 수 있다. (R을 선택하면 -20을 받을 수도 있기 때문). 따라서 열 플레이어의 최소극대화 값은

\underline{v_{col}} = 0

이다.

최소최대화 값은 최소극대화 값과 반대로, 상대방이 나의 행동을 알고 있다고 가정한다. 공식은 다음과 같다.

:

\overline{v_i} = \min_{a_{-i}} \max_{a_i} {v_i(a_i,a_{-i})}

위의 표에서 행 플레이어는 상대방이 R을 선택하면 최대 4, L을 선택하면 최대 5를 얻을 수 있다. 따라서 행 플레이어의 최소최대화 값은

\overline{v_{row}} = 4

이다. 열 플레이어는 상대방이 T를 선택하면 최대 1, M을 선택해도 최대 1, B를 선택하면 최대 4를 얻을 수 있다. 따라서 열 플레이어의 최소최대화 값은

\overline{v_{col}} = 1

이다.

최소극대화 값은 항상 최소최대화 값보다 작거나 같다. (

\underline{v_i} \leq \overline{v_i}

) 직관적으로 생각하면, 최소극대화는 상대방이 무엇을 할지 모르는 상태에서 나의 최선의 값을 찾는 것이고, 최소최대화는 상대방이 나의 행동을 알고 있다는 유리한 조건에서 값을 계산하기 때문이다.

최소최대화 값의 표기법은 오른쪽에서 왼쪽으로 읽으면 이해하기 쉽다.

:

\overline{v_i} = \min_{a_{-i}} \max_{a_i} {v_i(a_i,a_{-i})} = \min_{a_{-i}} \Big( \max_{a_i} {v_i(a_i,a_{-i})} \Big)

먼저 모든 가능한

a_i

에 대해

v_i(a_i, a_{-i})

를 최대화하여

a_i

를 제외하고,

a_{-i}

에만 의존하는 결과

v'_i(a_{-i})

를 만든다. 그 다음 이 결과에 대해

a_{-i}

를 최소화한다.

\underline{v_{row}} \leq \overline{v_{row}}

및

\underline{v_{col}} \leq \overline{v_{col}}

임에도 불구하고, 두 플레이어가 각각 최소최대화 전략을 플레이하여 얻는 보상 벡터는

(2, -20)

(

(T, R)

의 경우) 또는

(-10, 1)

(

(M, R)

의 경우)이다. 이는 두 플레이어가 최소극대화 전략을 플레이하여 얻는 보상 벡터

(3, 1)

과 순위를 비교할 수 없다.

2. 2. 제로섬 게임에서의 최소극대화

제로섬 게임과 같은 2인 제로섬 게임에서 최소극대화 해는 내쉬 균형과 동일하다. 최소극대화라는 이름은 각 플레이어가 상대방의 최대 보상을 최소화하려고 하기 때문에 붙여졌다.^[4]

유한한 수의 전략을 가진 모든 2인 제로섬 게임에 대해, 값 와 각 플레이어에 대한 혼합 전략이 존재한다.

(a) 플레이어 2의 전략이 주어지면, 플레이어 1이 얻을 수 있는 최고의 보상은 이다.
(b) 플레이어 1의 전략이 주어지면, 플레이어 2가 얻을 수 있는 최고의 보상은 −이다.

이는 플레이어 1의 전략은 플레이어 2의 전략에 관계없이 보상 를 보장하며, 마찬가지로 플레이어 2는 보상 −를 보장할 수 있다는 것과 같다.

align="bottom" style="caption-side: bottom" | A의 보수 행렬
	B는 B1을 선택	B는 B2를 선택	B는 B3을 선택
A는 A1을 선택	+3	−2	+2
A는 A2를 선택	−1	0	+4
A는 A3을 선택	−4	−3	+1

'''A'''와 '''B'''가 동시에 움직이는 제로섬 게임을 예시로 들어보자. 각 플레이어가 세 가지 선택지를 가지고 있고, 표("A의 보수 행렬")에 표시된 '''A'''의 보수 행렬을 고려한다. '''B'''의 보수 행렬은 부호가 반대인 동일한 행렬이라고 가정한다.

이 경우, '''A'''의 최소극대화 선택은 A2인데, 최악의 결과는 1을 지불해야 하는 것이기 때문이다. 반면 '''B'''의 간단한 최소극대화 선택은 B2인데, 최악의 결과는 지불이 없는 것이기 때문이다. 하지만 이 해법은 불안정하다. 만약 '''B'''가 '''A'''가 A2를 선택할 것이라고 믿는다면, '''B'''는 1을 얻기 위해 B1을 선택할 것이고, 그러면 '''A'''는 '''B'''가 B1을 선택할 것이라고 믿는다면 3을 얻기 위해 A1을 선택할 것이고, 그러면 '''B'''는 B2를 선택할 것이며, 결국 두 플레이어 모두 선택하기가 어렵다는 것을 깨닫게 될 것이다. 따라서 더 안정적인 전략이 필요하다.

일부 선택은 다른 선택에 ''지배''당하며 제거될 수 있다. '''A'''는 A3을 선택하지 않을 것이다. 왜냐하면 '''B'''가 무엇을 선택하든 A1 또는 A2가 더 나은 결과를 낼 것이기 때문이다. '''B'''는 B3을 선택하지 않을 것이다. 왜냐하면 '''A'''가 무엇을 선택하든 B1과 B2의 일부 혼합이 더 나은 결과를 낼 것이기 때문이다.

플레이어 '''A'''는 A1을 1/6의 확률로 선택하고 A2를 5/6의 확률로 선택하여 1/3 이상을 예상하여 지불하는 것을 피할 수 있다. 마찬가지로, '''B'''는 '''A'''가 무엇을 선택하든 B1을 1/3의 확률로 선택하고 B2를 2/3의 확률로 선택하는 무작위 전략을 사용하여 최소 1/3의 예상 이익을 보장할 수 있다. 이러한 혼합된 최소극대화 전략은 개선될 수 없으며 이제 안정적이다.

2. 3. 최소극대화와 최대최소화 (Maximin)

최소극대화 값은 상대방이 어떤 행동을 할지 모르는 상황에서 플레이어가 확실하게 얻을 수 있는 가장 높은 값이다. 반면, 최대최소화 값은 상대방이 플레이어의 행동을 알고 있을 때, 상대방이 플레이어가 받도록 강요할 수 있는 가장 낮은 값이다.^[4]

최소극대화 값을 구하는 공식은 다음과 같다.

:

\underline{v_i} = \max_{a_i} \min_{a_{-i}} {v_i(a_i,a_{-i})}

여기서,

i는 플레이어의 인덱스이다.
$-i$ 는 플레이어 i를 제외한 다른 모든 플레이어를 의미한다.
$a_i$ 는 플레이어 i의 행동이다.
$a_{-i}$ 는 다른 모든 플레이어들의 행동이다.
$v_i$ 는 플레이어 i의 가치 함수이다.

최소극대화 값을 계산할 때는, 먼저 플레이어가 선택 가능한 각 행동에 대해 상대방이 할 수 있는 모든 행동을 고려하여 최악의 경우를 찾는다. 그 후, 이 최악의 경우 중 가장 나은 결과를 가져오는 플레이어의 행동을 선택한다.

예를 들어, 두 플레이어가 참여하는 게임에서 각 플레이어의 선택에 따른 보상은 다음 표와 같다.

두 플레이어 게임의 보상표
	플레이어 2: L	플레이어 2: R
플레이어 1: T	3, 1	2, -20
플레이어 1: M	5, 0	-10, 1
플레이어 1: B	-100, 2	4, 4

플레이어 1은 T를 선택하면 최소 2를 얻을 수 있다. (M을 선택하면 -10, B를 선택하면 -100을 얻을 수 있으므로 T가 최선이다.) 따라서 플레이어 1의 최소극대화 값은 2이다.
플레이어 2는 L을 선택하면 최소 0을 얻을 수 있다. (R을 선택하면 -20을 얻을 수 있으므로 L이 최선이다.) 따라서 플레이어 2의 최소극대화 값은 0이다.

최대최소화 값은 다음과 같이 정의된다.

:

\overline{v_i} = \min_{a_{-i}} \max_{a_i} {v_i(a_i,a_{-i})}

최소극대화 값과 비슷하지만, 최대와 최소 연산자의 순서가 반대이다. 위의 예시에서,

행 플레이어는 최대 4의 값을 얻을 수 있다(다른 플레이어가 R을 플레이하는 경우) 또는 5의 값을 얻을 수 있다(다른 플레이어가 L을 플레이하는 경우). 따라서 $\overline{v_{row}} = 4$ 이다.
열 플레이어는 최대 1의 값을 얻을 수 있다(다른 플레이어가 T를 플레이하는 경우), 1 (M의 경우) 또는 4 (B의 경우). 따라서 $\overline{v_{col}} = 1$ 이다.

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

:

\underline{v_i} \leq \overline{v_i}

제로섬 게임에서 최소극대화 해는 내쉬 균형과 같다.

비제로섬 게임에서 최소극대화는 자신의 최소 이익을 최대화하는 전략을 의미하며, 이는 상대방의 최대 이익을 최소화하는 것이나 내쉬 균형 전략과는 다를 수 있다.

최소극대화 값은 반복 게임에서 중요한 개념이며, 민속 정리에서 핵심적인 역할을 한다.

3. 조합 게임 이론

조합 게임 이론에서는 게임의 해법을 찾기 위해 최소극대화 알고리즘을 사용한다. 이 알고리즘은 틱택토와 같이 각 플레이어가 이기거나, 지거나, 비길 수 있는 게임에서 최적의 수를 찾는 데 활용된다. 최소극대화 알고리즘은 게임의 끝에서부터 역으로 최고의 수를 찾는 방식으로 작동하며, 각 단계에서 플레이어 A는 자신의 승리 가능성을 최대화하고, 다음 차례의 플레이어 B는 A의 승리 가능성을 최소화(즉, B 자신의 승리 가능성을 최대화)하려고 한다고 가정한다.

3. 1. 최소극대화 알고리즘 (간단한 버전)

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

아래에 설명된 최소극대화 ''알고리즘''의 '''단순한''' 버전은 각 플레이어가 이기거나, 지거나, 비길 수 있는 틱택토와 같은 게임을 다룬다. 만약 플레이어 A가 한 번의 수로 이길 ''수'' 있다면, 그들의 최고의 수는 그 이기는 수이다. 만약 플레이어 B가 한 번의 수가 플레이어 A가 한 번의 수로 이길 ''수'' 있는 상황으로 이어진다는 것을 알고 있고, 다른 수는 플레이어 A가 기껏해야 비길 수 있는 상황으로 이어진다면, 플레이어 B의 최고의 수는 비기는 수로 이어지는 수이다. 게임 후반에는 "최고의" 수가 무엇인지 쉽게 알 수 있다. 최소극대화 알고리즘은 게임의 끝에서부터 역으로 작업하여 최고의 수를 찾는 데 도움을 준다. 각 단계에서 플레이어 A는 A가 이길 가능성을 '''최대화'''하려고 하고, 다음 차례에서 플레이어 B는 A가 이길 가능성을 '''최소화'''하려 한다고 가정한다(즉, B가 이길 가능성을 최대화).^[5]

3. 2. 최소극대화 알고리즘 (번갈아 가며 움직이는 경우)

Minimax algorithm^영어(번갈아 가며 움직이는 경우)은 게임에서 다음 수를 선택하기 위한 재귀적 알고리즘이다.^[5] 게임의 각 위치나 상태에는 위치 평가 함수를 사용하여 계산된 값이 할당되는데, 이는 해당 위치에 도달하는 것이 얼마나 유리한지를 나타낸다. 플레이어는 상대방의 가능한 다음 수에 의해 발생하는 위치의 최소값을 최대화하는 수를 둔다. 만약 '''A'''의 차례라면, '''A'''는 자신의 모든 가능한 수에 값을 부여한다.

일반적으로 두 명의 플레이어가 참여하는 n인 게임에서 사용된다.^[5]

가능한 할당 방법은 '''A'''의 승리를 +1, '''B'''의 승리를 -1로 할당하는 것이다. 이는 존 H. 콘웨이가 개발한 조합 게임 이론으로 이어진다. 또 다른 방법은 수의 결과가 '''A'''의 즉각적인 승리라면 양의 무한대를, '''B'''의 즉각적인 승리라면 음의 무한대를 할당하는 것이다. 다른 모든 수에 대한 '''A'''의 값은 '''B'''의 가능한 각 응답에서 발생하는 값 중 최댓값이다. 이러한 이유로 '''A'''는 "최대화 플레이어", '''B'''는 "최소화 플레이어"라고 불리며, "최소극대화 알고리즘"이라는 이름이 붙었다.

위의 알고리즘은 모든 위치의 값이 최종 승리 또는 패배 위치의 값이 되기 때문에 모든 위치에 양의 무한대 또는 음의 무한대 값을 할당한다. 이는 체스나 바둑과 같이 복잡한 게임의 마지막 단계에서만 가능하다. 게임 완료까지 예측하는 것은 계산적으로 불가능하므로, 유한한 값을 부여하고 휴리스틱 평가 함수를 통해 최종적이지 않은 게임 상태에 값을 부여하여 확장할 수 있다.^[6]

최소극대화 알고리즘은 특정 수의 수만 앞을 내다보도록 제한할 수 있다. 이 숫자는 "수"로 측정되는 "예측"이라고 한다. 예를 들어, 체스 컴퓨터 딥 블루는 최소 12수 앞을 내다본 후 휴리스틱 평가 함수를 적용했다.^[6]

알고리즘은 ''게임 트리''의 노드를 탐색하는 것으로 생각할 수 있다. 트리의 ''유효 분기 계수''는 각 노드의 평균 자식 수이다. 탐색해야 할 노드의 수는 일반적으로 수의 수에 따라 지수적으로 증가한다. 따라서 게임 분석을 위해 탐색해야 할 노드의 수는 대략 분기 계수를 수의 수만큼 거듭제곱한 값이다. 따라서 최소극대화 알고리즘을 사용하여 체스와 같은 게임을 완전히 분석하는 것은 비실용적이다.

알파-베타 가지치기를 사용하면 순진한 최소극대화 알고리즘의 성능을 크게 향상시킬 수 있다.

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

'''함수''' 최소극대화(노드, 깊이, 최대화 플레이어) '''는'''

'''만약''' 깊이 = 0 '''또는''' 노드가 터미널 노드 '''이면'''

'''반환''' 노드의 휴리스틱 값

'''만약''' 최대화 플레이어 '''이면'''

값 := −∞

'''노드의 각''' 자식에 대해 '''반복'''

값 := max(값, 최소극대화(자식, 깊이 − 1, FALSE))

'''반환''' 값

'''그렇지 않으면''' ''(* 최소화 플레이어 *)''

값 := +∞

'''노드의 각''' 자식에 대해 '''반복'''

값 := min(값, 최소극대화(자식, 깊이 − 1, TRUE))

'''반환''' 값

''(* 초기 호출 *)''

최소극대화(기원, 깊이, TRUE)

최소극대화 함수는 잎 노드에 대한 휴리스틱 값을 반환한다. 비 잎 노드는 후손 잎 노드에서 값을 상속받는다. 휴리스틱 값은 최대화 플레이어에게 노드의 유리함을 측정하는 점수이다. 터미널(게임 종료) 잎 노드의 휴리스틱 값은 최대화 플레이어의 승리, 패배, 무승부에 해당하는 점수이다. 최대 탐색 깊이에서 비 터미널 잎 노드의 경우, 평가 함수가 노드에 대한 휴리스틱 값을 추정한다.

최소극대화는

\ \max(a,b) = -\min(-a,-b)\ ,

의 관찰을 바탕으로 네가맥스 알고리즘으로 단순화될 수 있다.

4. 게임 트리

완전 정보 게임은 서로가 어떤 수를 두었는지에 따라 어떤 국면이 나타나는지를 경우에 따라 구분함으로써 게임 전개를 수형도로 나타낼 수 있는데, 이를 '''게임 트리'''라고 한다.^[5]

게임 트리는 각 단계에서 분기되지만, 분기 수는 플레이어의 선택지 수만큼 있으며, 게임 트리를 따라 내려갈수록(더 멀리 내다볼수록) 국면(노드)의 수는 급격히 증가한다.

5. 사고 프로그램의 기본 원리

사고 프로그램의 기본 원리는 국면이 어느 정도 자신에게 유리한지 점수를 매기는 '평가'에 기반한다. 만약 현재 국면의 유리함을 적절하게 평가할 수 있다면, 자신이 둘 수 있는 수 중에서 가장 평가가 높은 국면을 만드는 수를 선택하면 된다.

국면에 놓인 말의 위치, 수 등만을 사용하여 평가값을 산출하는 것을 '정적 평가값'이라 하고, 이러한 값을 계산하는 함수를 '정적 평가 함수'라고 한다. 여기서 '정적'이라는 표현은 선행 탐색을 하지 않는다는 것을 의미한다. 일반적으로 정적 평가 함수만으로는 국면을 적절하게 평가하기 어렵다. 따라서 이러한 한계를 극복하기 위해 선행 탐색을 활용하는 방법이 최소극대화 방법이다.^[5]

6. 선행 탐색 (미니맥스법 전개)

상대 차례에는 다음에 나타나는 모든 국면 중 상대에게 가장 유리한(평가값이 최소) 수를 둘 것이므로, '''다음에 나타나는 모든 국면의 평가값 중 최소값을 해당 국면의 평가값으로 한다'''.

자신의 차례에는 다음에 나타나는 모든 국면 중 가장 좋은 평가(평가값이 최대)를 받는 수를 둘 수 있으므로, '''다음에 나타나는 모든 국면의 평가값 중 최대값을 해당 국면의 평가값으로 한다'''.

몇 수 앞을 내다볼 것인지에 따라, 해당 깊이까지 전개한 지점에서 정적 평가 함수를 사용하여 탐색을 중단할 수 있다. 게임 트리는 깊어질수록 국면 수가 기하급수적으로 증가하므로, 실용적인 시간 내에 너무 깊이까지 읽는 것은 어렵다.

일반적으로 유한한 깊이까지 읽지만, 게임 종료까지 읽는다면 승패를 완전히 파악하고 최선의 수를 둘 수 있다. 종반의 수읽기나 장기의 마무리 수읽기 등은 완전 수읽기가 이루어지기도 한다.

6. 1. 필승 수읽기와 완전 수읽기

오셀로와 같이 승패뿐만 아니라 돌의 차이도 문제가 되는 게임에서는, 승패만을 파악하는 것을 '''필승 수읽기''', 돌의 차이까지 파악하는 것을 '''완전 수읽기'''라고 구분한다.^[1]

필승 수읽기에서는 각 국면의 평가값이 "승리" 또는 "패배"의 두 가지로 제한된다. 이 경우, 자신의 차례인 국면은 다음 국면에 "하나라도 승리"가 있으면(자신은 해당 국면을 선택하면 되므로) 승리가 결정되고, 상대의 차례인 국면은 다음 국면이 "모두 승리"라면(상대에게는 패배를 막을 선택지가 없으므로) 승리가 결정된다. 이들은 각 국면의 평가값의 논리합(OR), 논리곱(AND)과 같은 것이므로, 각각 OR 노드, AND 노드라고 불린다. 이처럼 평가값이 승패로만 표시되는 게임 트리는 특히 AND/OR 트리라고 불린다.^[1]

7. 의사 코드

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

```text

'''함수''' 최소극대화(노드, 깊이, 최대화 플레이어) '''는'''

'''만약''' 깊이 = 0 '''또는''' 노드가 터미널 노드 '''이면'''

'''반환''' 노드의 휴리스틱 값

'''만약''' 최대화 플레이어 '''이면'''

값 := −∞

'''노드의 각''' 자식에 대해 '''반복'''

값 := max(값, 최소극대화(자식, 깊이 − 1, FALSE))

'''반환''' 값

'''그렇지 않으면''' ''(* 최소화 플레이어 *)''

값 := +∞

'''노드의 각''' 자식에 대해 '''반복'''

값 := min(값, 최소극대화(자식, 깊이 − 1, TRUE))

'''반환''' 값

''(* 초기 호출 *)''

최소극대화(기원, 깊이, TRUE)

```

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

최소극대화 알고리즘을 의사 코드로 작성하면 다음과 같다.

```text

function MIN_MAX(position: 국면, depth: 정수): 정수

begin

if depth=0 then return STATIC_VALUE(position); {읽기 깊이에 도달}

position을 전개 → 모든 자식 노드를 children[]에. 자식 노드의 수를 w에.

if w=0 then return STATIC_VALUE(position); {종국}

if position이 자신의 국면 then begin

max := -∞;

for i:=1 to w do begin

score = MIN_MAX( children[i], depth-1);

if(score>max) max := score;

end;

return max;

end else begin{position은 상대방의 국면}

min := ∞;

for i:=1 to w do begin

score = MIN_MAX( children[i], depth-1);

if(score
end;

return min;

end;

end;

```

7. 1. 네가맥스(Negamax)법

체스와 같이 패스(pass)가 없는 게임에서는 노드마다 평가치의 정/부호를 반전시켜 "상대는 상대에게 유리한 수를 탐색한다"는 방식으로 변경할 수 있다. 이를 네가맥스(Negamax)법이라고 한다. 최소극대화는 코드에서 최대화 플레이어와 최소화 플레이어, 두 플레이어를 별도로 취급한다.

\ \max(a,b) = -\min(-a,-b)\ ,

라는 관찰을 바탕으로 최소극대화는 종종 네가맥스 알고리즘으로 단순화될 수 있다.

다음은 네가맥스 알고리즘의 의사 코드(pseudo-code)이다.

```text

function NEGA_MAX(position: 국면, depth: integer): integer

begin

if depth = 0 then return STATIC_VALUE(position); {탐색 깊이에 도달}

position을 전개 → 모든 자식 노드를 children[]에 저장. 자식 노드의 수를 w에 저장.

if w = 0 then return STATIC_VALUE(position); {종료}

max := -∞;

for i := 1 to w do begin

score = -NEGA_MAX(children[i], depth - 1);

if (score > max) max := score;

end;

return max;

end;

8. 응용 알고리즘

최소극대화 알고리즘은 모든 국면에 대해 전수 탐색을 수행하므로, 탐색 효율이 떨어진다. 이를 개선한 알고리즘으로 알파-베타 가지치기가 있다.^[5] 알파-베타 가지치기는 읽을 필요가 없는 수를 중단함으로써 속도 향상을 꾀한다. 실제 게임 프로그램에서는 알파-베타 가지치기를 더욱 응용한 알고리즘이 사용되는 경우가 많다.

9. 개인 의사 결정에서의 최소극대화

최소극대화 이론은 불확실한 상황에서 의사 결정을 할 때 최대 예상 손실을 최소화하는 접근 방식을 취한다. 이는 '자연과의 게임'으로 간주될 수 있으며, 머피의 법칙이나 저항주의와 비슷한 관점을 가진다.^[8] 2인 제로섬 게임에서 사용되는 기술과 동일한 방법을 활용한다.

또한, 최소극대화는 존 롤스의 ''정의론''에서 차등의 원칙과 관련하여 철학 분야에서도 사용된다.^[9] 롤스는 사회, 경제적 불평등이 사회에서 가장 어려운 사람들에게 최대 이익을 가져다주도록 조정되어야 한다고 주장했다.^[10]

9. 1. 통계적 의사 결정 이론에서의 최소극대화 기준

통계적 의사 결정 이론에서 최소극대 추정량은 발생 가능한 최대 위험을 최소화하는 추정량이다. 이는 최악의 경우를 고려하여 가장 안정적인 결과를 보장하는 방법이다.^[1]

비확률적 의사 결정 이론에서 최소극대화는 확률에 대한 가정을 하지 않고 가능한 결과에 대한 시나리오 분석만 수행하는 강건한 접근 방식이다. 불확실한 상황에서 최악의 결과를 최소화하는 전략을 선택하는 것이다.^[1]

최소극대화 의사 결정은 다음과 같은 특징을 갖는다.^[1]

비확률적 접근: 확률 가정을 사용하지 않고 시나리오 분석을 통해 최악의 경우를 최소화한다.
강건성: 가정의 변화에 민감하지 않고 안정적인 결과를 제공한다.
서수 측정: 결과의 순위만 고려하며, 결과 간의 차이 크기는 고려하지 않는다.

이러한 특징 덕분에 최소극대화는 불확실성이 높은 상황에서 유용하게 사용될 수 있다.

10. 정치에서의 최소극대화

"덜 나쁜 선택" 투표(LEV)는 유권자들이 둘 이상의 후보를 마주했을 때, 가장 해롭지 않거나 "덜 나쁜 선택"이라고 생각하는 후보를 선택하는 최소극대화 전략의 한 방식이라고 볼 수 있다. "투표는 우리의 가치를 반영하지 못하거나, 기업 엘리트가 허용하는 선택으로 제한하도록 설계된 부패한 시스템에 대한 보복으로 개인적인 자기 표현이나 도덕적 판단의 한 형태로 간주되어서는 안 된다." 투표는 피해나 손실을 줄일 수 있는 기회로 보아야 한다.^[7]

참조

_[1] 보고서 Provincial Healthcare Index 2013 http://www.fraserins[...] Fraser Institute 2013-01
_[2] AV media Turing and von Neumann https://www.youtube.[...]
_[3] 서적 Game Theory Cambridge University Press
_[4] 서적 A Course in Game Theory MIT Press
_[5] 서적 Artificial Intelligence: A Modern Approach Pearson
_[6] 학술지 IBM's Deep Blue chess grandmaster chips IEEE Computer Society
_[7] 뉴스 An Eight Point Brief for LEV (Lesser Evil Voting) https://newpol.org/e[...] New Politics 2016-06-15
_[8] 서적 A Theory of Justice
_[9] 학술지 Some ordinalist-utilitarian notes on Rawls's ''Theory of Justice'' https://www.pdcnet.o[...] 1973-05
_[10] 학술지 Can the maximin principle serve as a basis for morality? a critique of John Rawls's theory http://piketty.pse.e[...] 1975-06
_[11] 서적 A Beautiful Math

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com