모든 하위 섹션, 전략이 미니맥스 알고리즘에서 가장 최적임을 증명하는 방법은 무엇입니까?

Question

질문은 제목에서 알 수 있듯이입니다.

나는 Minimax 알고리즘이 2인 게임에서 이 작업을 수행한다는 것을 알고 있습니다(A의 이익을 최대화하고 싶다고 가정).A의 차례에서는 A의 이익을 최대화하기 때문에 하위 값의 최대값을 취하고, B의 차례에서는 B의 이익을 최소화하기 위해 하위 값의 최소값을 취합니다.

그러나 위의 논리가 모든 하위 문제, 전략이 미니맥스 알고리즘에서 가장 최적이라는 것을 증명한다고는 생각하지 않습니다.제가 제안한 질문에 대한 힌트나 해결책이 있나요?위의 논리가 그렇다면 이에 대해 자세히 설명할 수 있습니까?

Answer 1

minimax의 주장은 다음과 같습니다.Minimax는 다른 플레이어도 동일한 전략을 사용하는 경우 최적의 전략을 제공합니다.

베이스:게임 트리의 리프에는 단 하나의 전략이 있으며, minimax가 분명히 선택하는 전략은 유일한 전략이기 때문에 최적입니다.
가설:minimax는 깊이 있는 게임을 위한 최적의 전략을 선택합니다. d.
증거:

깊이 있는 게임을 살펴보자 d+1.분명히 두 가지 가능한 시나리오가 있습니다.

1. 차례다 - 이것이다 max 단계.이 경우 우리가 할 수 있는 모든 가능한 동작 중에서 minimax는 각 전략에 대한 최소-최대 값을 재귀적으로 평가하고 이 동작을 선택한 '하위 게임'에 대한 최적의 결과를 제공합니다.이 하위 게임 각각은 깊이가 있습니다. d, 귀납 가설로부터 최적이다.
   이것이 최대 단계이기 때문에 min-max 알고리즘은 우리에게 최적의 솔루션인 최대값을 선택합니다.
2. 상대 차례다 - 이것이다 min 단계.위의 논리와 마찬가지로 minimax는 사례를 상대방이 할 수 있는 모든 가능한 동작으로 분할하고 결과를 평가합니다.귀납-가설에서 평가는 최적이며 우리는 그 중에서 최소값을 선택합니다. 이는 상대방이 선택했을 것이며 그에게 최적의 전략입니다(그리고 상대방이 모든 단계에서 최적으로 선택한다고 가정합니다). 상대방은 우리의 이익을 최소화하고 따라서 자신의 이익을 최대화하는 최소 평가를 선택합니다.

QED

이를 바탕으로 미니맥스에 대한 또 다른 주장을 결론 내릴 수 있습니다. 전략에 의해 반환되는 값은 (상대방의 전략에 관계없이) 실제로 얻을 수 있는 값보다 작지 않습니다.이는 위의 것과 매우 유사하게 유도에 의해 증명될 수 있습니다.

지침:

베이스:하나의 전략만 사용하고 '나무'가 실제로 잎인 경우 이를 반환합니다.
주장하다:깊이 게임에 대해 minimax가 반환한 값 d 이는 미니맥스에 따라 선택한 이 레벨에서 플레이되는 모든 게임에 대한 하한이며 상대에 대한 제한은 없습니다.
증거:

심도게임을 살펴보자 d+1.

1. 그것이 당신의 차례라면, 당신은 여기서 선택의 여지가 있기 때문에 모든 잎 중 최대를 선택했습니다.각각의 잎은 최소한 값을 (유도 가설) 보장하고 최대를 선택함으로써 선택된 값도 보장합니다.
2. 상대방의 차례인 경우 선택을 통제할 수 없습니다.당신은 그가 어떤 행동을 선택할 것인지 확신할 수 있을 뿐이고 어떤 행동을 선택할지는 알 수 없습니다.그러나 가능한 모든 움직임에 대해 깊이 있는 새로운 '하위 게임'을 얻게 됩니다. d, 유도 가설이 유지되는 곳입니다.상대방은 이러한 동작 중 하나를 선택할 수 있으므로 이 동작 후에는 최소한 min{game after opponent move}, 이는 정확히 최소 단계가 반환하는 것입니다.

QED.

Answer 2

MiniMax가 플레이어의 이익을 극대화하려고 시도하지 않기 때문에 미니 맥스가 플레이어의 이익을 극대화 할 수 없다는 것을 증명할 수는 없습니다.

어떤 MiniMax가 플레이어의 가능한 손실 을 최소화하는 것입니다.즉, 의사 결정은 보수적이며 최악의 시나리오 (다른 플레이어가 최적의 재생)를 가정합니다.그것을 증명해보십시오.훨씬 더 간단합니다.