Mini-max
Mini-max 는 예상되는 최대의 손실 (maximum loss)를 최소화시키기 (minimize) 위해 사용하는 의사결정이론 (Decision Theory) 의 한 방법이다. 바둑 (baduk) 과 같은 두명의 게임 참여자가 서로 번갈아 가면서 돌을 움직이든가 (alternate moves) 동시에 움직이는 경우를 (simultaneoue moves) 모두 다루는 zero-sum 게임이론 (Game Theory) 에서 출발한 것이다. 이것이 더욱 복잡한 게임 (Game) 으로 확장되었고, 어떤 불확실성 (Uncertainty) 이 존재하는 상황에서의 일반적인 의사결정을 하는데 까지 확장되었다. ..... (Wikipedia : Minimax)
대부분의 게임에서 완전한 탐색 (Search) (승패에 대한) 은 실질적으로 불가능하다. 체스 (chess) 의 경우 완전한 게임 그래프에는 1040 개의 노드가 있는 것으로 추정된다. 자식 노드들을 1/3 나노 초마다 하나씩 생성할 수 있다고 가정해도 체스에 대한 완전한 탐색 그래프를 만들어내는 데는 약 1022 세기가 걸린다 (참고로, 우주의 나이는 약 108 세기로 추정된다). 더욱이, 휴리스틱 탐색 (Heuristic Search) 기법도 실질적인 분기 계수를 도움이 될 만큼 충분히 줄이지는 못한다. 따라서 복잡한 게임에 있어서는 게임의 끝까지 탐색한다는 것은 (게임의 마지막 부분에서는 가능할 수도 있지만) 불가능하다는 것을 받아들여야만 한다.
종료 조건이 바뀌어야 한다는 것을 제외하고는 너비우선 탐색 (Breadth-first Search) 이나 깊이우선 탐색 (Depth-first Search)또는 휴리스틱 (Heuristic) 방법 등을 사용할 수 있다. 몇 가지 인위적인 종료 조건이 시간 제한, 메모리 제한, 또는 탐색트리에서 노드의 깊이에 대한 제한 등을 기반으로 정해질 수 있다. 또한 예를 들어 체스 같은 게임에서는 만일 경계에 있는 노드가 즉각적으로 유리한 교환을 할 수 있는 라이브 (live) 위치를 표현하고 있다면 탐색을 중단하지 않는 것이 일반적이다.
탐색이 끝나면 탐색트리로부터 최상이라고 추정되는 행동을 찾아내야 한다. 이러한 추정값은 탐색트리의 단말 (leaf) 노드에 정적 평가 함수 (static evaluation function) 를 적용하여 얻을 수 있다. 평가 함수는 단말 노드의 가치를 계산한다. 이러한 계산은 노드의 가치에 영향을 미친다고 생각되는 다양한 특징을 기반으로 이루어진다. 예를 들어 체스에서 유용한 특징들은 상대적인 말의 이점, 중심의 제어권, 킹에 의한 중심의 제어 여부 등을 들 수 있다. 게임트리를 분석할 때 MAX 에 유리한 상태에서는 평가 함수값이 양수, MIN 에 유리한 상태에서는 평가 함수값이 음수, 그리고 MAX 나 MIN 어느 편에 특별히 유리하지 않은 상태에서는 0 에 가까운 값을 갖도록 하는 것이 보통이다. ..... 좋은 첫 번째 행동은 최대최소 절차 (minimax procedure) 라고 하는 방법에 의해 선정될 수 있다.... (Nils J.Nilsson 1998)
알파베타 가지치기 (Alpha-Beta Pruning) 은 두명이 참여하는 게임을 위한 최소최대 (Mini-max) 알고리즘에 의해 평가되는 노드들의 수를 감소시키기 위한 기술이다. 즉 게임에서 상대방은 절대 도달하지 못하도록 나에게만 유리하게 탐색트리의 일부분을 잘라내는 것이다..... Alpha-beta pruning을 가진 minimax 는 가지치기를 하지 않는 minimax 와 같은 결과를 보이지만 훨씬 더 효율적이다.
term :
게임 (Game) 탐색 (Search) 불확실성 (Uncertainty) 휴리스틱 (Heuristic) 알파베타 가지치기 (Alpha-Beta Pruning) 최소최대 (Mini-max)
site :
paper :
최대최소 방법 (The Minimax Procedure) : Nils J.Nilsson
최소최대정리 (Min-max theorem) : 권오헌. 윤태환
최소 최대 추정량과 베이즈 추정량으로서의 Kalman 필터에 관하여 (On the Kalman Filter as the Bayes Estimator and the minimax Estimator) : 김지곤, 상명대 자연과학연구소, 1998
Game Tree Searching by Min/Max Approximation : Ronald L. Rivest, Artificial Intelligence 34,1 (Dec. 1987), 77-96. 1987