미니맥스

Minimax(MinMax, MM^[1] 또는 새들^[2] 포인트)는 인공지능, 의사결정 이론, 게임 이론, 통계 및 철학에서 사용되는 결정 규칙이며 최악의 경우(최대 손실) 시나리오에서 발생할 수 있는 손실을 최소화합니다.이익에 대처하는 경우는, 최소 이익을 최대화하기 위해서 「maximin」이라고 불립니다.원래는 여러 명의 플레이어로 구성된 제로섬 게임 이론으로, 플레이어가 번갈아 움직이는 경우와 그들이 동시에 움직이는 경우를 모두 포함하며, 불확실한 상황에서 더 복잡한 게임과 일반적인 의사 결정으로 확장되었습니다.

게임 이론

일반 게임에서는

최대값은 플레이어가 다른 플레이어의 행동을 알지 않고도 얻을 수 있는 가장 높은 값이다.따라서, 이것은 플레이어의 행동을 알고 있을 때 다른 플레이어가 강제로 받을 수 있는 가장 낮은 값이다.공식 정의는 다음과 같습니다.^[3]

({displaystyle {v_{i}}=\max _{a_{i}}\min _{a_{-i}}{v_{i}(a_{i},a_{-i}}})

장소:

$i$ 는 관심 있는 플레이어의 색인입니다.
$-i$ $\displaystyle -i$ 는 $-i$ $플레이어$ i를 제외한 다른 모든 플레이어를 나타냅니다.
${$ }}는 $a_{i}$ $플레이어$ i에 의해 실행되는 액션입니다.
$a_{-i}$ a $a_{-i}$ - $a_{-i}$ { $displaystyle$ a $_$ { - $i}$ $a_{-i}$ 、 다른 모든 참가자가 취한 액션을 나타냅니다.
$($ 스타일) $v_{i$ })는 $v_{i}$ $플레이어$ i의 가치 함수입니다.

플레이어의 최대값을 계산하는 방법은 최악의 경우입니다.플레이어의 가능한 각 동작에 대해 다른 플레이어의 가능한 모든 동작을 체크하고 가능한 최악의 액션 조합( $플레이어$ i에게 가장 작은 값을 주는 것)을 결정합니다.그런 다음 이 최소값이 가능한 한 높은지 확인하기 위해 사용할 수 있는 액션 $플레이어$ 를 결정합니다.

예를 들어, 두 명의 플레이어에 대해 다음 게임을 고려합니다. 첫 번째 플레이어("열 플레이어")는 T, $M$ $또는$ B로 $표시$ 된 세 가지 동작 중 하나를 선택하고 두 번째 플레이어("컬럼 플레이어")는 L $또는$ $R$ 의 두 가지 동작 중 하나를 선택할 수 있습니다.두 움직임의 조합의 결과는 보수 표에 표시됩니다.

{begin{array}{ccc}\hline T&3,1&2,-20\M&5,0&-10,1\B&100,2&4,4\hline \end{array}

(각 셀의 첫 번째 숫자는 열 플레이어의 지불이고 두 번째 숫자는 열 플레이어의 지불입니다.)

예를 들어, 우리는 순수한 전략만을 고려합니다.각 플레이어를 차례로 확인합니다.

행 플레이어는 T를 $플레이$ 할 수 있어 적어도 2의 보수가 보장됩니다(B를 $플레이$ 하는 것은 -100으로 이어질 수 있고 M을 $플레이$ 하는 것은 -10으로 이어질 수 있기 때문에 위험합니다). ${\underline {v_{row}}}=2$ v ${\underline {v_{row}}}=2$ ${\underline {v_{row}}}=2$ _ ${\underline {v_{row}}}=2$ (\ $displaystyle {v_{$ row}} = $2)$ 입니다 ${\underline {v_{row}}}=2$
칼럼 플레이어는 L을 $플레이$ 하고 최소 0의 보상을 확보할 수 있습니다(R을 $플레이$ 하면 $(\displaystyle$ -20 $-20$ ${\underline {v_{col}}}=0$ v ${\underline {v_{col}}}=0$ ${\underline {v_{col}}}=0$ ${\underline {v_{col}}}=0$ _ ${\underline {v_{col}}}=0$ { $displaystyle$ { $v _ col$ } = $0$ } 。

두 플레이어가 각각 최대값 전략 $(T,L)$ $)$ 을 수행하는 경우({displaystyle $(T,L$ 보상 벡터는 $(3,1)$ , $(3,1)$ ) $(3,1)$ { $displaystyle(3,1$ 입니다.

플레이어의 미니맥스 값은 플레이어의 행동을 알지 못한 채 다른 플레이어가 강제로 받을 수 있는 최소값이다.따라서, 플레이어는 다른 플레이어의 행동을 알고 있을 때 얻을 수 있는 가장 큰 값이다.공식 정의는 다음과 같습니다.^[3]

({displaystyle {v_{i}}=\min _{a_{-i}}\max _{a_{i}{v_{i}(a_{i},a_{-i}}})

정의는 maximin 값과 매우 유사하며, 최대 연산자와 최소 연산자의 순서만 역수입니다.위의 예에서는 다음과 같습니다.

행 플레이어는 최대 4(상대방이 R을 $플레이$ 하는 경우) 또는 5(상대방이 L을 $플레이$ 하는 경우)의 $값$ 을 얻을 수 있습니다. ${\overline {v_{row}}}=4\ .$ ${\overline {v_{row}}}=4\ .$ ${\overline {v_{row}}}=4\ .$ ${\overline {v_{row}}}=4\ .$ 4 . \ $displaystyle$ { v _ ${row$ } = ${\overline {v_{row}}}=4\ .$ 4 \ } ${\overline {v_{row}}}=4\ .$ 。
컬럼 플레이어는 최대값 1(상대방이 $T$ 를 플레이하는 경우), 1( $M$ 의 경우), 4( $B$ 의 경우)를 얻을 수 있습니다. ${\overline {v_{col}}}=1\ .$ v ${\overline {v_{col}}}=1\ .$ ${\overline {v_{col}}}=1\ .$ l ${\overline {v_{col}}}=1\ .$ . { $displaystyle$ { $v$ _ { $col$ } = $1 \$ }

모든 $플레이어$ i에 대해 최대값은 최소값입니다.

(\displaystyle {v_{i}}\leq {v_{i}})

직관적으로 최대화는 최소화 후에 이루어지기 $때문$ 에 플레이어 I는 다른 사용자가 무엇을 할지 알기 전에 가치를 최대화하려고 합니다.최소화에서는 최대화가 우선이므로 플레이어 I는 훨씬 더 나은 위치에 있습니다. 즉, $다른$ 사용자가 무엇을 했는지 알 수 있기 때문입니다.

표기법을 이해하는 또 다른 방법은 오른쪽에서 왼쪽으로 읽는 것입니다.우리가 글을 쓸 때

{\displaystyle {v_{i}=\min _{a_{-i}\max _{i}(a_{i},a_{-i})=\min _{a_{-i}{\big_i}(\max _{a_{i}){big_i}{i}(\i})

$\ v_{i}(a_{i},a_{-i})\$ 의 초기 $\ v_{i}(a_{i},a_{-i})\$ 세트 $\ v_{i}(a_{i},a_{-i})\$ $\ v_{i}(a_{i},a_{-i})\$ - $\ v_{i}(a_{i},a_{-i})\$ i) { $displaystyle$ \ $\ {a_{i}}\$ $v_{i}(a_{i$ }, $a_{-i})$ \ $\ {a_{i}}\$ $}$ 은 $\ v_{i}(a_{i},a_{-i})\$ $\ {a_{i}}\$ 는) $\ {a_{i}}\$ $v_{i}(a_{i},a_{-i})$ $displaystyle$ \ { $a_$ ${i$ $}\}$ 과 $\ {a_{i}}\$ $\ {a_{-i}}\ .$ 와) $.$ { $displaystyle$ \ $a_$ ${-i}\}$ 의 $\ {a_{-i}}\ .$ ${a_{i}}$ $\ {a_{i}}\$ 에 따라 달라집니다. 먼저 ${a_{i}}$ i { $displaystyle$ { $v_{i}(a_{i},a_{-i})$ $}$ 에서 i $}$ 를 ${a_{i}}$ 제외합니다. $\displaystyle v_{i}($ $a_{$ i}, $a_{-i$ $})$ 는 $\ {a_{i}}\$ 가능한 ${a_{-i}}$ 값 $)$ $위$ 에 최대화하여 일련의 한계 $\ v'_{i}(a_{-i})\,,$ $\ v'_{i}(a_{-i})\,,$ rox $\ v'_{i}(a_{-i})\,,$ ( $\ v'_{i}(a_{-i})\,,$ - $\ v'_{i}(a_{-i})\,,$ ${a_{-i}}$ $\ v'_{i}(a_{-i})\,,$ ) , $\ v'_{i}(a_{-i})\,,$ { $displaystyle$ ${a_{-i}}$ { $\ {a_{i}}\$ $a$ _ { - i $}$ ) , { displaystyle $v_i$ } (a _ i $}$ ) , { i ${a_{-i}}$ } $}$ } 。 $e$ \ { $a_{-i}\$ $.}$ 이러한 $\ {a_{-i}}\ .$ 결과에 대해 a - i \ $\ {a_{-i}}\$ { $a_{-i}\$ } $\ {a_{-i}}\$ 의 $\ {a_{-i}}\$ 값을 $\ {a_{-i}}\$ 최소화합니다.(역방향으로 maximin).

$\ {\underline {v_{row}}}\leq {\overline {v_{row}}}\$ r $\ {\underline {v_{row}}}\leq {\overline {v_{row}}}\$ $\ {\underline {v_{row}}}\leq {\overline {v_{row}}}\$ _ $\ {\underline {v_{row}}}\leq {\overline {v_{row}}}\$ $\ {\underline {v_{row}}}\leq {\overline {v_{row}}}\$ $\ {\underline {v_{row}}}\leq {\overline {v_{row}}}\$ $\ {\underline {v_{row}}}\leq {\overline {v_{row}}}\$ w $\ {\underline {v_{row}}}\leq {\overline {v_{row}}}\$ {\ 、 { $display$ style } \ $leq$ $\ {\underline {v_{col}}}\leq {\overline {v_{col}}}\,,$ （ $underline$ { $v$ _ { $v$ _ { row } $}$ ） $\ {\underline {v_{col}}}\leq {\overline {v_{col}}}\,,$ v $\ {\underline {v_{col}}}\leq {\overline {v_{col}}}\,,$ $\ {\underline {v_{col}}}\leq {\overline {v_{col}}}\,,$ l _ $\ {\underline {v_{col}}}\leq {\overline {v_{col}}}\,,$ $\ {\underline {v_{col}}}\leq {\overline {v_{col}}}\,,$ \ $display style \$ { { v $_$ { $col }$ }\ $leq$ $\ {\underline {v_{row}}}\leq {\overline {v_{row}}}\$ { 、 v _ $lineoff$ $ooffoff$ {offoff { { { { {off oline_lineoffoff 、 v _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ line {rategies $\ (2,-20)\$ ( $\ (2,-20)\$ - $\ (2,-20)\$ ) $\ (2,-20)\$ $T,$ $)$ 의 $\ (T,R)\$ 경우 $(-10,1)$ $displaystyle \$ (2, - $20)\$ $\ (T,R)\$ $(-10,1)$ ( $\ (M,R)\,,$ R)의 경우 { $(-10,1)$ $\ (T,R)\$ $\$ (- $10, 1)},$ (M, R $)$ 의 경우 { $displaystyle$ \ ( $M, R)$ 의 경우 {displaystyle $\,$ 1 $}$ 은 $\ (2,-20)\$ $\ (T,R)\$ $(-10,1)$ $\ (M,R)\,,$ 벡터 $\ (3,1)\$ off)에 대해 동일하게 지불할 수 없습니다.두 선수 모두 맥시멈 전략을 구사하고 있습니다.

제로섬 게임에서

2인용 제로섬 게임에서 미니맥스 솔루션은 내쉬 균형과 동일합니다.

제로섬 게임에서 미니맥스 정리는 다음과 같습니다.^[4]^{[failed verification]}

모든 2인용 제로섬 게임에는 다양한 전략을 가진 값 $V$ 와 각 플레이어에 대한 혼합 전략이 존재합니다.
(a) 플레이어 2의 전략을 고려할 때 플레이어 1이 얻을 수 있는 최고의 성과는 $V$ 이다.

(b) 플레이어 1의 전략에 따라 플레이어 2가 얻을 수 있는 최선의 보상은 -V이다.

마찬가지로 플레이어 1의 전략은 플레이어 2의 전략에 관계없이 V의 $보상$ 을 보장하며, 마찬가지로 플레이어 2도 -V의 보상을 자신들에게 보장할 수 있습니다.미니맥스라는 이름은 각 플레이어가 상대방이 받을 수 있는 최대 보상을 최소화했기 때문에 생겨났습니다.게임은 제로섬이기 때문에 최대 손실도 최소화합니다(즉, 최소 보상을 최대화).값이 없는 게임의 예를 참조하십시오.

예

플레이어 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에 대한 보상 행렬이 부호가 반전된 동일한 행렬이라고 가정한다(즉, A1과 B1의 경우 B는 A에 3을 지불한다).최악의 결과는 1을 지불해야 하므로 A의 최대 선택지는 A2이고, 최악의 결과는 무지급이므로 B의 단순 최대 선택지는 B2이다.그러나 B가 A2를 선택할 것이라고 믿는다면 B는 B1을 선택하여 1을 얻을 것이고, A가 B1을 선택할 것이라고 믿는다면 A는 A1을 선택하여 3을 얻을 것이고, B는 B2를 선택할 것이고, 결국 B는 B2를 선택할 것이고, 두 플레이어 모두 선택의 어려움을 깨닫게 될 것이기 때문에 이 해결책은 안정적이지 않다.그래서 좀 더 안정적인 전략이 필요하다.

일부 선택지는 다른 선택지가 지배하고 있으며, 이를 제거할 수 있습니다.A1 또는 A2 중 어느 쪽이 더 나은 결과를 얻기 때문에 A3를 선택하지 않을 것이며, B1과 B2의 일부 혼합물이 A가 무엇을 선택하든 더 나은 결과를 낳기 때문에 B는 B3를 선택하지 않을 것이다.

플레이어 A는 다음 이상의 예상 지불을 피할 수 있습니다.1/3 확률 1/6의 A1과 확률 5/6의 A2를 선택함으로써 : A에 대한 기대 보상은 B가 B1을 선택한 경우 3 × 1/6 - 1 × 5/6 = -+1/3이고, B가 B2를 선택한 경우 -2 × 1/6 + 0 × 5/6 = -+1/3이다.마찬가지로, B는 확률 1/3의 B1과 확률 2/3의 B2를 선택하는 랜덤화 전략을 사용함으로써 A가 무엇을 선택하든 최소 1/3의 기대 이득을 보장할 수 있다. 이러한 혼합 미니맥스 전략은 개선될 수 없으며 현재 안정적이다.

막시민

게임 이론에서 맥시민은 종종 미니맥스와 구별된다.미니맥스는 제로섬 게임에서 상대의 최대 보상을 최소화하기 위해 사용됩니다.제로섬 게임에서 이것은 자신의 최대 손실을 최소화하고, 자신의 최소 이득을 최대화하는 것과 같다.

"맥시민"은 보통 논제로섬 게임에서 자신의 최소 수익을 극대화하는 전략을 묘사하기 위해 사용되는 용어이다.넌제로섬 게임에서 이것은 일반적으로 상대의 최대 이득을 최소화하는 것과 같지도 않고 내쉬 균형 전략과도 같지 않다.

반복 게임 내

미니맥스 값은 반복 게임 이론에서 매우 중요합니다.이 이론의 중심 이론 중 하나인 민속 정리는 미니맥스 값에 의존합니다.

조합 게임 이론

조합 게임 이론에는 게임 해법을 위한 미니맥스 알고리즘이 있습니다.

미니맥스 알고리즘의 간단한 버전은 각 플레이어가 이기거나, 지거나, 무승부를 할 수 있는 틱택토와 같은 게임을 다루고 있습니다.만약 A선수가 한 번에 이길 수 있다면, 그들의 최고의 움직임은 그 승부수이다.한 수만 움직이면 A가 한 수, 다른 수로는 A가 기껏해야 무승부로 이어지는 상황을 B가 알고 있다면 B는 무승부로 이어지는 것이 최선이다.게임 후반부에는 "최고의" 움직임이 무엇인지 쉽게 알 수 있습니다.미니맥스 알고리즘은 게임 종료 시부터 뒤로 이동함으로써 최적의 동작을 찾을 수 있습니다.각 단계에서 선수 A는 A의 우승 가능성을 최대화하려고 하고, 다음 단계에서 선수 B는 A의 우승 가능성을 최소화하려고 한다(즉, 자신의 우승 가능성을 최대화하려고 한다).

대체 이동을 사용하는 Minimax 알고리즘

미니맥스^[5] 알고리즘은 보통 2인용 게임인 n플레이어 게임에서 다음 동작을 선택하기 위한 재귀 알고리즘입니다.값은 게임의 각 위치 또는 상태와 관련지어집니다.이 값은 포지션 평가 함수를 통해 계산되며 플레이어가 포지션에 도달하는 것이 얼마나 좋은지를 나타냅니다.그 후 플레이어는 상대의 가능한 후속 동작으로 인해 포지션의 최소값을 최대화하는 동작을 한다.만약 A가 이사할 차례라면, A는 그들의 법적 움직임 하나하나에 가치를 부여한다.

가능한 할당 방법은 A에 대해 +1로, B에 대해 -1로 특정 승리를 할당하는 것입니다.이것은 J.H. Conway에 의해 개발된 조합 게임 이론으로 이어진다.다른 방법으로는 이동 결과가 A에 즉시 승리하면 양의 무한대가 할당되고 B에 즉시 승리하면 음의 무한대가 할당된다는 규칙을 사용하는 것입니다.기타 이동의 A에 대한 값은 B가 응답할 수 있는 각 값의 최대값입니다.이 때문에 A는 최대 플레이어, B는 최소 플레이어라고 불리며 미니맥스 알고리즘이라는 이름이 붙는다.위의 알고리즘은 모든 포지션의 값이 최종 승패 포지션의 값이 되므로 양 또는 음의 무한대 값을 임의의 포지션에 할당합니다.종종 이것은 체스나 바둑과 같은 복잡한 게임의 맨 마지막에만 가능하다. 왜냐하면 게임이 끝날 때까지 앞을 내다보는 것은 계산적으로 가능하지 않기 때문이다. 대신, 포지션은 한 명의 선수나 한 명의 선수에게 승리를 가져다 줄 것이라는 믿음의 정도를 추정하기 위해 유한한 값을 부여받는다.그녀.

완전한 시퀀스에 따라 가능한 모든 것을 고려하지 않고 비최종 게임 상태에 값을 부여하는 휴리스틱 평가 함수를 제공할 수 있다면 이는 확장될 수 있습니다.그런 다음 미니맥스 알고리즘을 특정 수의 전방 이동만을 보도록 제한할 수 있습니다.이 숫자를 "플라이"로 측정한 "룩어헤드"라고 합니다.예를 들어 체스 컴퓨터 딥 블루(당시 세계 챔피언 개리 카스파로프를 이긴 최초의 컴퓨터)는 적어도 12개의 플라이를 앞지른 후 휴리스틱 평가 ^[6]기능을 적용했다.

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

순진한 미니맥스 알고리즘의 성능은 알파 베타 프루닝을 사용함으로써 결과에 영향을 주지 않고 극적으로 개선될 수 있다.다른 경험적 프루닝 방식도 사용할 수 있지만 모든 방법이 프루닝되지 않은 검색과 동일한 결과를 제공하는 것은 아닙니다.

순진한 미니맥스 알고리즘은 미니맥스 점수와 함께 전체 주요 변동을 추가로 반환하도록 수정될 수 있다.

유사 코드

깊이 제한 미니맥스알고리즘의 의사코드를 다음에 나타냅니다.

함수 minimax(node, depth, maximizingPlayer )는 깊이 = 0 또는 노드가 터미널 노드인 경우 노드의 휴리스틱 값을 반환하고 maximizePlayer 그러면 노드 do 값의 각 자식: = max(value, minimax(child, depth - 1, FALSE) 값을 반환하는 것입니다. 그렇지 않으면 (* 최소화 플레이어 *) 값):= +node do value := min( value , minimax ( child , depth - 1, TRUE )의 각 하위 항목에 대한 값 반환

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

minimax 함수는 리프 노드(최대 검색 깊이의 터미널 노드 및 노드)에 대한 휴리스틱 값을 반환합니다.비리프 노드는 하위 리프 노드에서 값을 상속합니다.휴리스틱 값은 최대화 플레이어에 대한 노드의 호감도를 측정하는 점수입니다.따라서 최대 플레이어에게 승리 등의 유리한 결과를 가져오는 노드가 최소 플레이어에게 보다 유리한 노드보다 높은 점수를 가진다.터미널(게임 종료) 리프 노드의 휴리스틱 값은 최대화 플레이어의 승패 또는 무승부에 대응하는 점수입니다.최대 검색 깊이의 비말단 리프 노드에 대해 평가 함수는 노드의 휴리스틱 값을 추정한다.이 추정치의 품질과 검색 깊이에 따라 최종 미니맥스 결과의 품질과 정확도가 결정됩니다.

Minimax는 코드에서 두 플레이어(최대 플레이어 및 최소 플레이어)를 별도로 취급합니다. $\ \max(a,b)=-\min(-a,-b)\ ,$ ( $\ \max(a,b)=-\min(-a,-b)\ ,$ , $\ \max(a,b)=-\min(-a,-b)\ ,$ ) $\ \max(a,b)=-\min(-a,-b)\ ,$ - $\ \max(a,b)=-\min(-a,-b)\ ,$ ( - $\ \max(a,b)=-\min(-a,-b)\ ,$ , - $\ \max(a,b)=-\min(-a,-b)\ ,$ ) , $\ \max(a,b)=-\min(-a,-b)\ ,$ \ $displaystyle \$ \ $max$ ( a , b ) = - \ $min aa$ , - $b$ ) \ , , , , , , $\ \max(a,b)=-\min(-a,-b)\ ,$ } minimax $\ \max(a,b)=-\min(-a,-b)\ ,$ 는 종종 negamax 알고리즘으로 단순화될 수 있다.

예

미니맥스 트리 예시

초기 무한(또는 임의로 큰) 값을 공허에 대입하고 음가막스 부호화의 단순화를 피함으로써 인간 친화적이 되려고 하는 애니메이션 교육학적 예.

각 턴마다 플레이어당 최대 두 번의 이동만 가능한 게임이라고 가정합니다.알고리즘은 오른쪽 트리를 생성합니다.여기서 원은 알고리즘을 실행하는 플레이어(최대화 플레이어)의 움직임을 나타내고 정사각형은 상대(최소화 플레이어)의 움직임을 나타냅니다.위에서 설명한 것처럼 계산 리소스의 제한으로 인해 트리는 4개의 미리 보기로 제한됩니다.

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

개별 의사결정을 위한 최소값

불확실성에 직면했을 때의 미니맥스

미니맥스 이론은 다른 참여자는 없지만 결정의 결과가 알려지지 않은 사실에 의존하는 결정으로 확장되었습니다.예를 들어, 광물을 탐사하기로 결정하는 것은 비용이 수반되는데, 이는 광물이 존재하지 않으면 낭비되지만, 광물이 존재한다면 큰 보상을 가져올 것이다.한 가지 접근법은 이것을 자연에 대한 게임으로 취급하는 것이다(자연의 움직임 참조). 그리고 머피의 법칙이나 저항주의와 유사한 사고방식을 사용하여 2인용 제로섬 게임과 같은 기법을 사용하여 최대 예상 손실을 최소화하는 접근법을 취한다.

또, 기회(예를 들면 주사위)가 요인인 2인용 게임용으로, 기대 미니맥스 트리가 개발되고 있습니다.

통계결정론의 미니맥스 기준

고전적인 통계결정 이론에서는 $\ \theta \in \Theta \ .$ 를 추정하기 위해 사용되는 추정기 $\ \theta \in \Theta \ .$ $δ(\$ displaystyle \\ $delta \)$ 가 $\ \delta \$ 있습니다 $.\displaystyle \theta \$ $.}$ 또한 $\ \theta \in \Theta \ .$ 일반적으로 지정된 a의 손실인 $\ R(\theta ,\delta )\ .$ R $(\displaystyle \ta \delta \)$ 을 $\ R(\theta ,\delta )\ .$ 가정합니다 $.$ n. 이 $\ {\tilde {\delta }}\$ 에서 $\ {\tilde {\delta }}\$ ~ $\ {\tilde {\delta }}\$ {\ $displaystyle\\tilde {delta }}\$ 는 $\ {\tilde {\delta }}\$ 다음을 만족하는 경우 minimax라고 부릅니다.

\displaystyle \sup _{\theta }R(\theta, {\tilde {\theta})=\inf _{\sup _{\theta }\R(\theta,\theta})\.}

의사결정 이론 프레임워크의 대안 기준은 사전 $\Pi \ .$ 가 존재하는 경우의 베이즈 추정치이다 $.$ \\ $displaystyle \Pi$ \ $.}$ 평균 $\Pi \ .$ 위험을 최소화하는 경우 추정치는 베이즈이다.

\displaystyle \int _{\Theta }R(\theta,\delta)\\operatorname {d} \Pi (\theta )\ .}

비확률론적 의사결정 이론

미니맥스 의사결정의 핵심 특징은 비확률적이라는 것이다. 기대치 또는 기대 효용을 사용하는 결정과는 달리, 가능한 결과가 무엇인지에 대한 시나리오 분석만 하고 다양한 결과의 확률에 대한 가정을 하지 않는다.따라서 이러한 다른 의사결정 기법과 달리 가정의 변경에는 강력하다.이 비확률론적 접근방식의 다양한 확장, 특히 미니맥스 후회와 정보격 의사결정 이론이 존재한다.

또한 미니맥스는 간격 측정이 아닌 순서형 측정(결과에 "얼마나 더 좋거나 더 나쁨"이 포함됨)만을 필요로 하며, 모델화된 결과만을 사용하여 순서형 데이터를 반환한다. 미니맥스 분석의 결론은 다음과 같다: "이 전략은 최악의 경우(최악의 경우)보다 나쁜 경우보다 적은 미니맥스이다.다른 전략"이라고 말합니다."이 전략은 δ( $X$ ) = $n$ ."이라는 형식의 기대치 분석과 비교해 보십시오. 따라서 미니맥스는 순서형 데이터에 사용할 수 있으며 보다 투명할 수 있습니다.

철학에서의 막시민

철학에서, "맥시민"이라는 용어는 존 롤스의 정의론에서 종종 사용되며, 그는 차이 원칙의 맥락에서 그것을 언급한다^[7].롤스는 이 원칙을 사회적 경제적 불평등이 사회의 ^[8]^[9]가장 혜택을 받지 못하는 구성원들에게 가장 큰 이익이 되도록 배치되어야 한다고 규정하는 규칙이라고 정의했다.

「」를 참조해 주세요.

레퍼런스

^ Bacchus, Barua (January 2013). Provincial Healthcare Index 2013 (PDF) (Report). Fraser Institute. p. 25.
^ Professor Raymond Flood. Turing and von Neumann (video). Gresham College – via YouTube.
^ ^a ^b Maschler, Michael; Solan, Eilon; Zamir, Shmuel (2013). Game Theory. Cambridge University Press. pp. 176–180. ISBN 9781107005488.
^ Osborne, Martin J.; Rubinstein, A. (1994). A Course in Game Theory (print ed.). Cambridge, MA: MIT Press. ISBN 9780262150415.
^ Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, pp. 163–171, ISBN 0-13-790395-2
^ Hsu, Feng-Hsiung (1999). "IBM's Deep Blue chess grandmaster chips". IEEE Micro. Los Alamitos, CA, USA: IEEE Computer Society. 19 (2): 70–81. doi:10.1109/40.755469. During the 1997 match, the software search extended the search to about 40 plies along the forcing lines, even though the non-extended search reached only about 12 plies.
^ Rawls, J. (1971). A Theory of Justice. p. 152.
^ Arrow, K. (May 1973). "Some ordinalist-utilitarian notes on Rawls's Theory of Justice". Journal of Philosophy. 70 (9): 245–263.
^ Harsanyi, J. (June 1975). "Can the maximin principle serve as a basis for morality? a critique of John Rawls's theory" (PDF). American Political Science Review. 69 (2): 594–606.

외부 링크

"Minimax principle", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
"Mixed strategies". cut-the-knot.org. Curriculum: Games. : 시각화 애플릿
"Maximin principle". Dictionary of Philosophical Terms and Names. Archived from the original on 2006-03-07.
"Quaak rules". bewersdorff-online.de. - 혼합 미니맥스 전략에 대해 내기 및 버프 게임을 하다
"Minimax". Dictionary of Algorithms and Data Structures. US NIST.
"Launch game visual". ksquared.de. Archived from the original on 2015-03-24. - 게임 트리 해결(Java Applet), 알파 베타 프루닝 유무에 관계없이 밸런스 트리 또는 오프 밸런스 트리용 알고리즘 시각화
"MiniMax". apmonitor.com. - 수치 솔루션 플랫폼을 사용한 튜토리얼
"MinimaxAlgorithm.java". github.com. - Checkers 게임에서 사용되는 Java 구현

[1] Bacchus, Barua (January 2013). Provincial Healthcare Index 2013 (PDF) (Report). Fraser Institute. p. 25.

[2] Professor Raymond Flood. Turing and von Neumann (video). Gresham College – via YouTube.

[ZMS2013-3] Maschler, Michael; Solan, Eilon; Zamir, Shmuel (2013). Game Theory. Cambridge University Press. pp. 176–180. ISBN 9781107005488.

[Osborne-4] Osborne, Martin J.; Rubinstein, A. (1994). A Course in Game Theory (print ed.). Cambridge, MA: MIT Press. ISBN 9780262150415.

[5] Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, pp. 163–171, ISBN 0-13-790395-2

[6] Hsu, Feng-Hsiung (1999). "IBM's Deep Blue chess grandmaster chips". IEEE Micro. Los Alamitos, CA, USA: IEEE Computer Society. 19 (2): 70–81. doi:10.1109/40.755469. During the 1997 match, the software search extended the search to about 40 plies along the forcing lines, even though the non-extended search reached only about 12 plies.

[Rawls-1971-7] Rawls, J. (1971). A Theory of Justice. p. 152.

[8] Arrow, K. (May 1973). "Some ordinalist-utilitarian notes on Rawls's Theory of Justice". Journal of Philosophy. 70 (9): 245–263.

[9] Harsanyi, J. (June 1975). "Can the maximin principle serve as a basis for morality? a critique of John Rawls's theory" (PDF). American Political Science Review. 69 (2): 594–606.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v t 게임 이론의 토픽
정의들	폭주 게임 협동 게임 결정성 커밋의 에스컬레이션 확장형 게임 1인자 및 2인자 승리 게임의 복잡성 게임 설명 언어 그래픽 게임 신념의 계층 정보 세트 노멀 폼 게임 선호 연속 게임 동시 게임 동시 액션 선택 해결된 게임 간결한 게임
평형 개념	베이지안 내시 평형 베르주 평형 핵심 상관 평형 엡실론 평형 진화적으로 안정된 전략 깁스 평형 메르텐스 안정 평형 마르코프 완전 평형 내시 평형 파레토 효율 완전 베이지안 평형 적절한 균형 양적 반응 평형 준완전 평형 리스크 우위 만족도 평형 자기확정균형 순차 평형 섀플리 값 강내시 평형 서브게임 퍼펙트 떨리는 손
전략들	역유도 입찰 음영 공모 전진 유도 그림 트리거 마르코프 전략 우세한 전략 순수한 전략 혼합 전략 전략스틸링 인수 대갚음
반 게임의	교섭 문제 시시한 이야기 글로벌 게임 자동 게임 평균 필드 게임 메커니즘 설계 n플레이어 게임 완벽한 정보 대형 포아송 게임 잠재적인 게임 반복 게임 스크리닝 게임 시그널링 게임 슈타켈베르크 경쟁 엄정한 게임 확률 게임 대칭 게임 제로섬 게임
게임.	가세요 체스 무한 체스 체커 틱택토 죄수의 딜레마 선물 교환 게임 선택적 죄수 딜레마 여행자의 딜레마 코디네이션 게임 치킨. 지네 게임 루이스 시그널링 게임 자원봉사자의 딜레마 달러 경매 성대결 사슴 사냥 매칭 페니 얼티메이텀 게임 가위 바위 보 해적 게임 독재자 게임 공공재 게임 블로토 게임 소모전 El Farol Bar 문제 공정분할 공정한 케이크 커팅 쿠르노 게임 교착 상태 다이너 딜레마 평균의 3분의 2를 추측하다 쿤 포커 내쉬 협상 게임 유도 퍼즐 트러스트 게임 공주와 괴물 게임 랑데부 문제
정리	애로우의 불가능성 정리 아우만 합치 정리 민속 정리 미니맥스 정리 내쉬의 정리 정화 정리 계시 원리 체르멜로의 정리
열쇠 수치	앨버트 W.터커 아모스 트베르스키 앙투안 오귀스틴 쿠르노 아리엘 루빈스타인 클로드 섀넌 대니얼 카네만 데이비드 K.레빈 데이비드 크렙스 도날드질리스 드루 푸덴베르크 에릭 마스킨 해럴드 쿤 허버트 사이먼 에르베 물랭 존 콘웨이 장 티롤 장프랑수아 메르텐스 제니퍼 투어 체이스 존 하샤니 존 메이나드 스미스 존 내시 요한 폰 노이만 케네스 애로우 케네스 빈모어 레오니트 후르비츠 로이드 섀플리 멜빈 드레셔 메릴 M.홍수. 올가 본다레바 오스카 모르겐스턴 폴 밀그롬 페이튼 영 라인하르트 셀텐 로버트 액셀로드 로베르트 아우만 로버트 B.윌슨 로저 마이어슨 새뮤얼 볼스 수잔 스카치머 토머스 셸링 윌리엄 빅리
여러가지 종류의	올페이 경매 알파-베타 가지치기 베르트랑의 역설 한정적 합리성 조합 게임 이론 대립 분석 협력 진화 게임 이론 체스의 선점 우위 게임 설명 언어 게임 메카닉 게임 이론 용어집 게임 이론가 목록 게임 이론의 게임 목록 승산이 없는 상황 체스 풀기 위상 게임 공동체의 비극 사소한 결정의 횡포

v t 데이터 구조 및 알고리즘
데이터 구조	어레이 연관 배열 이진 검색 트리 펜윅나무 그래프 해시 테이블 히프 링크 리스트 큐 세그먼트 트리 스택 스트링 트리 트리
알고리즘	역추적 바이너리 검색 폭 우선 검색 깊이 우선 검색 분열시켜 정복하다. 동적 프로그래밍 접다 욕심쟁이 미니맥스 재귀 정렬 스트리밍 스위프 라인 토폴로지 정렬
데이터 구조 목록 알고리즘 목록

Search

미니맥스

네임스페이스

더

목차

게임 이론

일반 게임에서는

제로섬 게임에서

예

막시민

반복 게임 내

조합 게임 이론

대체 이동을 사용하는 Minimax 알고리즘

유사 코드

예

개별 의사결정을 위한 최소값

불확실성에 직면했을 때의 미니맥스

통계결정론의 미니맥스 기준

비확률론적 의사결정 이론

철학에서의 막시민

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

미니맥스

게임 이론

일반 게임에서는

제로섬 게임에서

예

막시민

반복 게임 내

조합 게임 이론

대체 이동을 사용하는 Minimax 알고리즘

유사 코드

예

개별 의사결정을 위한 최소값

불확실성에 직면했을 때의 미니맥스

통계결정론의 미니맥스 기준

비확률론적 의사결정 이론

철학에서의 막시민

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.