위키원
"최소최대 알고리즘"의 두 판 사이의 차이
dlwldms1012 (토론 | 기여) (→개요) |
dlwldms1012 (토론 | 기여) |
||
| 2번째 줄: | 2번째 줄: | ||
==개요== | ==개요== | ||
| − | 최소최대 알고리즘은 예상되는 최대의 손실을 최소화하기 위해 사용하는 이론 중 하나다. 최소 최대 원리에 따라 어떤 계획의 성공에 의한 효과를 생각하는 게 아니라, 실패했을 때 어떻게 될지를 생각하여 그 손실이 최소가 되도록 세우는 전략이다.<ref>최대 최소 전략 - https://terms.naver.com/entry.nhn?docId=829503&cid=50376&categoryId=50376</ref> 바둑, 체스와 같은 두 명의 게임 참여자가 서로 번갈아 행동하거나 동시에 움직이는 경우를 모두 다루는 제로섬 게임 이론으로부터 시작하였으나, 더 복잡한 게임과 불확실성이 존재하는 일반적인 의사결정을 포함해 널리 쓰이고 있다. 특정 게임 상태에서 다음 수를 예측하기 위해서는 수읽기를 통해 가장 승률이 높은 수를 선택해야 한다. 게임에서 한 참여자에게 유리한 수는 상대 참여자에게 불리한 수이다. 상대의 이익을 최소화하고 자신의 이익을 최대화하는 것이 게임에서 승리하는 방법이기 때문에, 이 경로를 찾는 것이 인공지능 게임 프로그램의 핵심이다. 최소최대 알고리즘의 트리 탐색 과정은 깊이 우선 탐색을 수행한 후, 서브 트리의 탐색이 끝나면 기존에 탐색 된 노드들을 역으로 거슬러 올라가면서 상위노드로 평갓값을 반영한다. 이때, 최댓값과 최솟값은 교대로 비교하며 최종 서브 트리를 선택한다. 평갓값이 자식 노드에서 상위 노드로 전파될 때마다 해당 상위 노드의 자식 노드 간의 비교를 진행하고, 나의 수에서는 가장 큰 값을, 상대의 수에서는 가장 작은 값을 선택한다. 최종적으로 선택된 서브 트리는 참여자와 상대가 모두 최선의 선택을 한 결과물이다. 최소최대 알고리즘의 경우 트리의 모든 노드를 탐색해야 하기 때문에 트리의 깊이가 많아질수록 계산 시간을 늘어난다. 게임의 복잡도가 큰 대부분의 게임에서는 트리를 전부 확장한 완전한 탐색은 실질적으로 불가능하다. 비교적 간단한 휴리스틱 탐색 기법도 실질적인 분기 계수를 도움이 될 만큼 충분히 줄이지는 못하므로, 복잡한 게임을 끝까지 탐색한다는 것을 불가능하다는 것을 받아들여야 한다.<ref>벌꿀 오소리, 〈[https://honeybadger333.tistory.com/10 AlphaGo의 인공지능 알고리즘 분석 3]〉, 《티스토리》, 2016-06-24</ref><ref>오현석, 〈[http://www.aistudy.com/heuristic/mini-max.htm Mini-max]〉, 《개인 블로그》</ref> 이러한 문제를 해결하기 위해 어느 정도 깊이의 수까지 탐색한 후 판정하는 휴리스틱이나 탐색할 필요가 없는 노드를 탐색에서 제외하는 기법인 [[알파베타 가지치기]]를 사용한다.<ref>박준화, 〈[https://everyyy.tistory.com/80 (인공지능) 탐색과 최적화 - 게임에서의 탐색]〉, 《티스토리》</ref> 최소최대 알고리즘은 최댓값을 선택함으로써 안정적으로 얻을 수 있는 차선의 수를 놓칠 수도 있다. | + | 최소최대 알고리즘은 예상되는 최대의 손실을 최소화하기 위해 사용하는 이론 중 하나다. 최소 최대 원리에 따라 어떤 계획의 성공에 의한 효과를 생각하는 게 아니라, 실패했을 때 어떻게 될지를 생각하여 그 손실이 최소가 되도록 세우는 전략이다.<ref>최대 최소 전략 - https://terms.naver.com/entry.nhn?docId=829503&cid=50376&categoryId=50376</ref> 바둑, 체스와 같은 두 명의 게임 참여자가 서로 번갈아 행동하거나 동시에 움직이는 경우를 모두 다루는 제로섬 게임 이론으로부터 시작하였으나, 더 복잡한 게임과 불확실성이 존재하는 일반적인 의사결정을 포함해 널리 쓰이고 있다. 특정 게임 상태에서 다음 수를 예측하기 위해서는 수읽기를 통해 가장 승률이 높은 수를 선택해야 한다. 게임에서 한 참여자에게 유리한 수는 상대 참여자에게 불리한 수이다. 상대의 이익을 최소화하고 자신의 이익을 최대화하는 것이 게임에서 승리하는 방법이기 때문에, 이 경로를 찾는 것이 인공지능 게임 프로그램의 핵심이다. 최소최대 알고리즘의 트리 탐색 과정은 깊이 우선 탐색을 수행한 후, 서브 트리의 탐색이 끝나면 기존에 탐색 된 노드들을 역으로 거슬러 올라가면서 상위노드로 평갓값을 반영한다. 이때, 최댓값과 최솟값은 교대로 비교하며 최종 서브 트리를 선택한다. 평갓값이 자식 노드에서 상위 노드로 전파될 때마다 해당 상위 노드의 자식 노드 간의 비교를 진행하고, 나의 수에서는 가장 큰 값을, 상대의 수에서는 가장 작은 값을 선택한다. |
| + | [[파일:최소최대_알고리즘.png|썸네일|400픽셀|가운데|'''최소최대 알고리즘'''(Minimax algorithm)]] | ||
| + | MAX가 컴퓨터, MIN이 상대라고 할 때, MAX는 최댓값을, MIN은 최솟값을 선택한다. 위의 사진은 4수 앞을 예측한 트리 노드로, 0, 2, 4는 컴퓨터의 차례, 1, 3은 상대방의 차례이다. 4번 줄의 값은 컴퓨터가 선택한 최댓값이다. 3번 줄에서는 상대방이 하위 노드인 4번 줄의 값 중 최솟값을 선택한다. 2번 줄에서는 다시 컴퓨터가 3번 줄의 값 중 최댓값을 선택하고, 이 과정을 반복해 실제 차례인 0번 줄에서는 1번 줄의 -10과 -7 중 더 높은 값인 -7을 선택하게 된다. 잎 노드에는 10이나 무한대 등 더 좋은 최댓값이 있지만, 상대방의 선택으로 선택할 수 없게 된다.<ref>복습은만점의지름길, 〈[https://going-to-end.tistory.com/entry/Minimax-algorithm-%EB%AF%B8%EB%8B%88%EB%A7%A5%EC%8A%A4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 Minimax Algorithm, 미니맥스 알고리즘]〉, 《네이버 블로그》, 2019-12-06</ref> | ||
| + | 최종적으로 선택된 서브 트리는 참여자와 상대가 모두 최선의 선택을 한 결과물이다. 최소최대 알고리즘의 경우 트리의 모든 노드를 탐색해야 하기 때문에 트리의 깊이가 많아질수록 계산 시간을 늘어난다. 게임의 복잡도가 큰 대부분의 게임에서는 트리를 전부 확장한 완전한 탐색은 실질적으로 불가능하다. 비교적 간단한 휴리스틱 탐색 기법도 실질적인 분기 계수를 도움이 될 만큼 충분히 줄이지는 못하므로, 복잡한 게임을 끝까지 탐색한다는 것을 불가능하다는 것을 받아들여야 한다.<ref>벌꿀 오소리, 〈[https://honeybadger333.tistory.com/10 AlphaGo의 인공지능 알고리즘 분석 3]〉, 《티스토리》, 2016-06-24</ref><ref>오현석, 〈[http://www.aistudy.com/heuristic/mini-max.htm Mini-max]〉, 《개인 블로그》</ref> 이러한 문제를 해결하기 위해 어느 정도 깊이의 수까지 탐색한 후 판정하는 휴리스틱이나 탐색할 필요가 없는 노드를 탐색에서 제외하는 기법인 [[알파베타 가지치기]]를 사용한다.<ref>박준화, 〈[https://everyyy.tistory.com/80 (인공지능) 탐색과 최적화 - 게임에서의 탐색]〉, 《티스토리》, 2019-10-05</ref> 최소최대 알고리즘은 최댓값을 선택함으로써 안정적으로 얻을 수 있는 차선의 수를 놓칠 수도 있다. | ||
{{각주}} | {{각주}} | ||
| 16번째 줄: | 19번째 줄: | ||
* [[알파베타 가지치기]] | * [[알파베타 가지치기]] | ||
| + | {{사진 수정 필요}} | ||
{{알고리즘|토막글}} | {{알고리즘|토막글}} | ||
2020년 7월 28일 (화) 13:28 판
최소최대 알고리즘(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] 최종적으로 선택된 서브 트리는 참여자와 상대가 모두 최선의 선택을 한 결과물이다. 최소최대 알고리즘의 경우 트리의 모든 노드를 탐색해야 하기 때문에 트리의 깊이가 많아질수록 계산 시간을 늘어난다. 게임의 복잡도가 큰 대부분의 게임에서는 트리를 전부 확장한 완전한 탐색은 실질적으로 불가능하다. 비교적 간단한 휴리스틱 탐색 기법도 실질적인 분기 계수를 도움이 될 만큼 충분히 줄이지는 못하므로, 복잡한 게임을 끝까지 탐색한다는 것을 불가능하다는 것을 받아들여야 한다.[3][4] 이러한 문제를 해결하기 위해 어느 정도 깊이의 수까지 탐색한 후 판정하는 휴리스틱이나 탐색할 필요가 없는 노드를 탐색에서 제외하는 기법인 알파베타 가지치기를 사용한다.[5] 최소최대 알고리즘은 최댓값을 선택함으로써 안정적으로 얻을 수 있는 차선의 수를 놓칠 수도 있다.
각주
- ↑ 최대 최소 전략 - 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
참고자료
- 최소극대화 위키백과 - 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
같이 보기
이 문서는 사진 수정이 필요합니다.
| ||||||||||||||||||||||||||||||||||
