해시넷
최소최대 알고리즘
최소최대 알고리즘(Minimax algorithm)은 인공지능, 결정이론, 게임이론, 통계학, 철학에서 사용하는 개념으로 최악의 경우 발생할 수 있는 손실을 최소화하기 위한 규칙이다. 최소최대 알고리즘은 최대최소 알고리즘으로 불리기도 한다. 손실이 아니라 이익이 기준이라면 최소 이익을 극대화한다는 의미에서 'maximin' 이라고 부르기도 한다.
개요[편집]
최소최대 알고리즘은 예상되는 최대의 손실을 최소화하기 위해 사용하는 이론 중 하나다. 최소 최대 원리에 따라 어떤 계획의 성공에 의한 효과를 생각하는 게 아니라, 실패했을 때 어떻게 될지를 생각하여 그 손실이 최소가 되도록 세우는 전략이다.[1] 바둑, 체스와 같은 두 명의 게임 참여자가 서로 번갈아 행동하거나 동시에 움직이는 경우를 모두 다루는 제로섬 게임 이론으로부터 시작하였으나, 더 복잡한 게임과 불확실성이 존재하는 일반적인 의사결정을 포함해 널리 쓰이고 있다. 특정 게임 상태에서 다음 수를 예측하기 위해서는 수읽기를 통해 가장 승률이 높은 수를 선택해야 한다. 게임에서 한 참여자에게 유리한 수는 상대 참여자에게 불리한 수이다. 상대의 이익을 최소화하고 자신의 이익을 최대화하는 것이 게임에서 승리하는 방법이기 때문에, 이 경로를 찾는 것이 인공지능 게임 프로그램의 핵심이다. 최소최대 알고리즘의 트리 탐색 과정은 깊이 우선 탐색을 수행한 후, 서브 트리의 탐색이 끝나면 기존에 탐색 된 노드들을 역으로 거슬러 올라가면서 상위노드로 평갓값을 반영한다. 이때, 최댓값과 최솟값은 교대로 비교하며 최종 서브 트리를 선택한다. 평갓값이 자식 노드에서 상위 노드로 전파될 때마다 해당 상위 노드의 자식 노드 간의 비교를 진행하고, 나의 수에서는 가장 큰 값을, 상대의 수에서는 가장 작은 값을 선택한다.
MAX가 컴퓨터, MIN이 상대라고 할 때, MAX는 최댓값을, MIN은 최솟값을 선택한다. 위의 사진은 4수 앞을 예측한 트리 노드로, 0, 2, 4는 컴퓨터의 차례, 1, 3은 상대방의 차례이다. 4번 줄의 값은 컴퓨터가 선택한 최댓값이다. 3번 줄에서는 상대방이 하위 노드인 4번 줄의 값 중 최솟값을 선택한다. 2번 줄에서는 다시 컴퓨터가 3번 줄의 값 중 최댓값을 선택하고, 이 과정을 반복해 실제 차례인 0번 줄에서는 1번 줄의 -10과 -7 중 더 높은 값인 -7을 선택하게 된다. 잎 노드에는 10이나 무한대 등 더 좋은 최댓값이 있지만, 상대방의 선택으로 선택할 수 없게 된다.[2] 최종적으로 선택된 서브 트리는 참여자와 상대가 모두 최선의 선택을 한 결과물이다. 최소최대 알고리즘의 경우 트리의 모든 노드를 탐색해야 하기 때문에 트리의 깊이가 많아질수록 계산 시간을 늘어난다. 게임의 복잡도가 큰 대부분의 게임에서는 트리를 전부 확장한 완전한 탐색은 실질적으로 불가능하다. 체스 한 판에 대한 완전한 탐색 그래프를 만드려면 약 10^22세기가 걸린다고 한다. 비교적 간단한 휴리스틱 탐색 기법도 실질적인 분기 계수를 도움이 될 만큼 충분히 줄이지는 못하므로, 복잡한 게임을 끝까지 탐색한다는 것을 불가능하다는 것을 받아들여야 한다.[3][4] 이러한 문제를 해결하기 위해 어느 정도 깊이의 수까지 탐색한 후 판정하는 휴리스틱이나 탐색할 필요가 없는 노드를 탐색에서 제외하는 기법인 알파베타 가지치기를 사용한다.[5] 최소최대 알고리즘은 최댓값을 선택함으로써 안정적으로 얻을 수 있는 차선의 수를 놓칠 수도 있다.
역사[편집]
폰 노이만(John von Neumann), 에밀 보렐(Emil Borel), 찰스 배비지(Charles Babbage) 중 누가 시초인지에 대해 논의가 있지만, 폰 노이만이 게임으로부터 나온 가치에 기초해 최소최대 알고리즘을 정의한 것이 가장 보편적인 의견이다. 노버트 위너(Norbert Wiener)는 최소최대 알고리즘을 게임의 끝에서 거리가 멀고 휴리스틱의 진화에 기초해 제안했다.[6] 카네기멜론 대학교의 앨런 뉴얼(Allen Newell)과 허버트 사이먼(Herbert Simon), 랜드 연구소(Rand Corporation)의 클리프 쇼(Cliff Shaw)는 컴퓨터 체스 프로그램 뒤에 있는 몇 가지 기본적인 프로그래밍 아이디어를 개발했다. 연구팀은 인공지능에 대한 연구로 컴퓨터 체스를 연구했고, 1958년 NSS 체스 프로그램을 개발했다. 이 프로그램은 최소최대 알고리즘과 알파베타 가지치기 기술을 결합했다. 컴퓨터는 최소최대 알고리즘을 사용해 가장 좋은 움직임과 나쁜 움직임을 평가했고, 알파베타 가지치기 기술을 사용해 덜 유리한 결과를 내는 트리를 제거해 시간을 절약했다. 대부분의 2인 게임 플레이 프로그램은 최소최대 알고리즘과 알파베타 가지치기를 사용한다.[7]
유사 코드[편집]
깊이가 제한된 최소최대 알고리즘에 대한 유사 코드는 다음과 같다.
function minimax(node, depth, maximizingPlayer) is
if depth = 0 or node is a terminal node then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, minimax(child, depth − 1, FALSE))
return value
else (* minimizing player *)
value := +∞
for each child of node do
value := min(value, minimax(child, depth − 1, TRUE))
return value
각주[편집]
- ↑ 최대 최소 전략 네이버 지식백과 - https://terms.naver.com/entry.nhn?docId=829503&cid=50376&categoryId=50376
- ↑ 복습은만점의지름길, 〈Minimax Algorithm, 미니맥스 알고리즘〉, 《네이버 블로그》, 2019-12-06
- ↑ 벌꿀 오소리, 〈AlphaGo의 인공지능 알고리즘 분석 3〉, 《티스토리》, 2016-06-24
- ↑ 오현석, 〈Mini-max〉, 《개인 블로그》
- ↑ 박준화, 〈(인공지능) 탐색과 최적화 - 게임에서의 탐색〉, 《티스토리》, 2019-10-05
- ↑ Minimax Chess Programming Wiki - https://www.chessprogramming.org/Minimax
- ↑ 〈THE MINIMAX ALGORITHM AND ALPHA-BETA PRUNING〉, 《Computer History Museum》
참고자료[편집]
- 최소극대화 위키백과 - https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%86%8C%EA%B7%B9%EB%8C%80%ED%99%94
- Minimax Wikipedia - https://en.wikipedia.org/wiki/Minimax
- Minimax Chess Programming Wiki - https://www.chessprogramming.org/Minimax
- 짝짜꿍, 〈(#Game) Minimax Algorithm, Alpha-Beta Pruning〉, 《네이버 블로그》, 2014-06-15
- 벌꿀 오소리, 〈AlphaGo의 인공지능 알고리즘 분석 3〉, 《티스토리》, 2016-06-24
- 박준화, 〈(인공지능) 탐색과 최적화 - 게임에서의 탐색〉, 《티스토리》, 2019-10-05
- 복습은만점의지름길, 〈Minimax Algorithm, 미니맥스 알고리즘〉, 《네이버 블로그》, 2019-12-06
같이 보기[편집]
| ||||||||||||||||||||||||||||||||||
