최소최대 알고리즘

최소최대 알고리즘(Minimax algorithm)은 인공지능, 결정이론, 게임이론, 통계학, 철학에서 사용하는 개념으로 최악의 경우 발생할 수 있는 손실을 최소화하기 위한 규칙이다. 최소최대 알고리즘은 최대최소 알고리즘으로 불리기도 한다. 손실이 아니라 이익이 기준이라면 최소 이익을 극대화한다는 의미에서 'maximin' 이라고 부르기도 한다.

개요

최소최대 알고리즘은 예상되는 최대의 손실을 최소화하기 위해 사용하는 이론 중 하나다. 최소 최대 원리에 따라 어떤 계획의 성공에 의한 효과를 생각하는 게 아니라, 실패했을 때 어떻게 될지를 생각하여 그 손실이 최소가 되도록 세우는 전략이다. 바둑, 체스와 같은 두 명의 게임 참여자가 서로 번갈아 행동하거나 동시에 움직이는 경우를 모두 다루는 제로섬 게임 이론으로부터 시작하였으나, 더 복잡한 게임과 불확실성이 존재하는 일반적인 의사결정을 포함해 널리 쓰이고 있다. 특정 게임 상태에서 다음 수를 예측하기 위해서는 수읽기를 통해 가장 승률이 높은 수를 선택해야 한다. 게임에서 한 참여자에게 유리한 수는 상대 참여자에게 불리한 수이다. 상대의 이익을 최소화하고 자신의 이익을 최대화하는 것이 게임에서 승리하는 방법이기 때문에, 이 경로를 찾는 것이 인공지능 게임 프로그램의 핵심이다. 최소최대 알고리즘의 트리 탐색 과정은 깊이 우선 탐색을 수행한 후, 서브 트리의 탐색이 끝나면 기존에 탐색 된 노드들을 역으로 거슬러 올라가면서 상위노드로 평갓값을 반영한다. 이때, 최댓값과 최솟값은 교대로 비교하며 최종 서브 트리를 선택한다. 평갓값이 자식 노드에서 상위 노드로 전파될 때마다 해당 상위 노드의 자식 노드 간의 비교를 진행하고, 나의 수에서는 가장 큰 값을, 상대의 수에서는 가장 작은 값을 선택한다.

최소최대 알고리즘(Minimax algorithm)

MAX가 컴퓨터, MIN이 상대라고 할 때, MAX는 최댓값을, MIN은 최솟값을 선택한다. 위의 사진은 4수 앞을 예측한 트리 노드로, 0, 2, 4는 컴퓨터의 차례, 1, 3은 상대방의 차례이다. 4번 줄의 값은 컴퓨터가 선택한 최댓값이다. 3번 줄에서는 상대방이 하위 노드인 4번 줄의 값 중 최솟값을 선택한다. 2번 줄에서는 다시 컴퓨터가 3번 줄의 값 중 최댓값을 선택하고, 이 과정을 반복해 실제 차례인 0번 줄에서는 1번 줄의 -10과 -7 중 더 높은 값인 -7을 선택하게 된다. 잎 노드에는 10이나 무한대 등 더 좋은 최댓값이 있지만, 상대방의 선택으로 선택할 수 없게 된다. 최종적으로 선택된 서브 트리는 참여자와 상대가 모두 최선의 선택을 한 결과물이다. 최소최대 알고리즘의 경우 트리의 모든 노드를 탐색해야 하기 때문에 트리의 깊이가 많아질수록 계산 시간을 늘어난다. 게임의 복잡도가 큰 대부분의 게임에서는 트리를 전부 확장한 완전한 탐색은 실질적으로 불가능하다. 체스 한 판에 대한 완전한 탐색 그래프를 만드려면 약 10^22세기가 걸린다고 한다. 비교적 간단한 휴리스틱 탐색 기법도 실질적인 분기 계수를 도움이 될 만큼 충분히 줄이지는 못하므로, 복잡한 게임을 끝까지 탐색한다는 것을 불가능하다는 것을 받아들여야 한다. 이러한 문제를 해결하기 위해 어느 정도 깊이의 수까지 탐색한 후 판정하는 휴리스틱이나 탐색할 필요가 없는 노드를 탐색에서 제외하는 기법인 알파베타 가지치기를 사용한다. 최소최대 알고리즘은 최댓값을 선택함으로써 안정적으로 얻을 수 있는 차선의 수를 놓칠 수도 있다.

역사

폰 노이만(John von Neumann), 에밀 보렐(Emil Borel), 찰스 배비지(Charles Babbage) 중 누가 시초인지에 대해 논의가 있지만, 폰 노이만이 게임으로부터 나온 가치에 기초해 최소최대 알고리즘을 정의한 것이 가장 보편적인 의견이다. 노버트 위너(Norbert Wiener)는 최소최대 알고리즘을 게임의 끝에서 거리가 멀고 휴리스틱의 진화에 기초해 제안했다. 카네기멜론 대학교의 앨런 뉴얼(Allen Newell)과 허버트 사이먼(Herbert Simon), 랜드 연구소(Rand Corporation)의 클리프 쇼(Cliff Shaw)는 컴퓨터 체스 프로그램 뒤에 있는 몇 가지 기본적인 프로그래밍 아이디어를 개발했다. 연구팀은 인공지능에 대한 연구로 컴퓨터 체스를 연구했고, 1958년 NSS 체스 프로그램을 개발했다. 이 프로그램은 최소최대 알고리즘과 알파베타 가지치기 기술을 결합했다. 컴퓨터는 최소최대 알고리즘을 사용해 가장 좋은 움직임과 나쁜 움직임을 평가했고, 알파베타 가지치기 기술을 사용해 덜 유리한 결과를 내는 트리를 제거해 시간을 절약했다. 대부분의 2인 게임 플레이 프로그램은 최소최대 알고리즘과 알파베타 가지치기를 사용한다.

유사 코드

깊이가 제한된 최소최대 알고리즘에 대한 유사 코드는 다음과 같다.

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://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

같이 보기

• 게임이론
• 결정이론
• 인공지능
• 알파베타 가지치기

이 최소최대 알고리즘 문서는 알고리즘에 관한 토막글입니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 이 문서의 내용을 채워주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 BM25 • FAISS • 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 벡터검색 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 역문서빈도(IDF) • 용어빈도(TF) • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반