이론 미니맥스(MiniMax) 알파베타 가지치기(Alpha-beta pruning)

[peedy]

가장 간단한 알고리듬이라면 현재 노드로부터 선택 가능한 모든 노드에 대해서 평가함수를 적용하고, 그 중에서 가장 큰 값(좋은 평가)을 보이는 노드로 분기하는 방법을 들 수 있겠다. 그러나, 평가 함수는 기본적으로 한 노드에만 국한된 평가를 하므로, 선택한 노드가 현재는 최선이라고 할지라도 결과적으로 승리를 이끌 수 있는 노드인지는 알 수가 없다. 보다 그럴듯한 인공지능을 구현하기 위해서는 몇 수 앞까지를 미리 예측할 필요가 있으며, 그러려면 상대방의 움직임도 가정을 해야 하는데, 이런 것을 내다보기(look ahead) 프로시져라고 한다. 미니맥스 알고리듬은 상대방도 항상 최선의 선택을 한다고 가정하는 내다보기 프로시져이다. 이 가정으로부터, 우리는 선택 가능한 노드 중에서 가장 높은 평가값을 가진 것을 선택하는 최대화 플레이어(maximizing player)가 되며, 반대로 상대방은 가장 낮은 평가값을 선택하는 최소화 플레이어(minimizing player)가 된다.
그림 3은 미니맥스 알고리듬을 그림으로 나타낸 것이다. 동그랗게 표시된 노드는 우리 자신 즉, 최대화 플레이어이며, 네모로 표시된 노드는 최소화 플레이어를 나타낸다. 이 예는 A 노드의 상황으로부터 두 수 앞까지를 내다보는 경우인데, 두 수 앞에서 가능한 노드 D, E, F, G의 평가값이 각각 7, 4, 2, 8인 경우를 가정한 것이다. 우리로서는 C 노드를 거쳐 평가값이 8인 G 노드로 가는 것이 최선의 진행일 것이다. 하지만 상대방은 반대로 평가값이 낮은 노드를 선택할 것이라고 가정했으므로, B 노드와 C 노드의 상황에서 상대방은 각각 E 노드와 F 노드를 선택하리라 예상할 수 있다. 결과적으로 우리는 B 노드를 선택해서 E 쪽으로 진행하는 편이 두 수 앞에서 최선의 결과를 얻을 수 있는 선택이 되는 것이다.

보충자료
--------------------

http://ailab.kyungpook.ac.kr/Seminar/20011031/main.htm


minimax를 발전시킨 알고리즘 MTD(f) 현재로선 자료 불충분 위와 같은 미니맥스 알고리듬은 실로 단순 방법이지만, 컴퓨터들의 최대 강점이 바로 우직한 계산 능력과 엄청난 용량의 탐색 공간 아닌가. 만약 터미널 노드까지의 모든 노드들을 탐색할 수 있다면, 세계 최고의 플레이어라도 능히 이겨낼 수 있게 되는 것이다. 하지만, 모든 노드들을 탐색하기 위해서는 만만치 않은 비용이 들게 된다. 틱택토 처럼 작은 규격의 간단한 보드 게임이라면 노드의 수가 수십만개 정도에 그치지만, 장기의 경우 각 노드에서 분기할 수 있는 노드의 수(유효 분기율)가 평균 50 정도가 되며, 게임이 끝나기까지 보통 100 수 정도가 두어져야 하므로, 완전 탐색을 위해서는 50^100 개의 노드를 검색해야 한다. 일 분에 50^6 노드(2억 6천만 노드/초)를 처리한다고 해도 50^90년 이상이라는 어마어마한 세월이 필요하게 되는 것이다. 이런 사태를 조합 폭발이라고 한다. 조합 폭발을 막기 위해서는, 무작정 끝까지 계산하려고 할 것이 아니라 적당한 시간 안에 답이 나올 수 있는 곳 까지만 계산할 필요가 있다. 문제에 다라 다르지만, 3~4 수 앞까지를 내다보는 것이 일반적이다. 또 한가지 방법으로, 검색하지 않아도 되는 노드를 미리 잘라내어 탐색을 고속화 하는 방법이 있는데, 이 대표적인 방법이 알파 베타 가지치기이다. 다시 그림 3을 살펴 보자.



앞에서는 D, E, F, G의 평가값을 모두 계산해놓고 시작했지만, 이번엔 순서대로 계산해나가는 것이다. 먼저 B 노드의 하위 노드인 D와 E의 평가값을 계산해서 각각 7과 4가 나왔다면, 미니맥스 알고리듬에 따라 최소화 플레이어는 B에서 4를 선택할 것이라고 예상할 수 있다. 결국 A 노드에서는 잠정적인 최대값으로 4를 가지게 된다. 다음으로 C 노드의 하위 노드인 F와 G의 평가값을 계산하게 되는데, 먼저 F의 평가값으로 2가 나왔다고 하자. 과연 이 이상 평가값을 계산할 필요가 있을까? 눈치가 빠른 독자라면 이미 감을 잡았겠지만, G의 평가값을 계산할 필요가 없어졌다. 왜일까? C 노드의 잠정적인 최소값이 2 이므로 A노드에 있는 최대화 플레이어의 입장에서 보면, C 노드를 통해서는 2보다 큰 값을 기대할 수 없다는 것이다. 그런데, 이는 A노드가 가지고 있는 잠정적인 최대값 4보다 작으므로, 2 이상의 평가값을 기대할 수 없는 C 노드에서는 더이상 평가값을 계산할 필요가 없어지는 것이다. 이와 같이, 잠정적인 최대값을 이용해서 최소값을 계산하는 하위 노드의 가지를 치는 것(필요 없어진 평가값을 계산 않는 것)을 베타 컷이라고 하며, 반대로 잠정적인 최소값을 이용해서 최대값을 계산하는 하위 노드의 가지를 치는 것을 알파 컷이라고 한다. 이렇게 알파 베타 가지치기를 이용하면, 깊이가 깊고 유효 분기율이 큰 트리에서 미니맥스 알고리듬을 사용하는 경우 획기적으로 탐색 속도를 개선할 수 있게 된다. 미니맥스 알고리듬의 약점은 정해진 깊이 이상의 탐색을 할 수 없다는 점에 있다. 이를 수평선 효과(horizon effect)라고 하는데, 정해진 몇 수까지만 내다본 상황에서는 최선의 선택이라고 하더라도, 바로 그 다음에 올 위기 상황이나 치명적인 결과에 대해서는 전혀 고려를 할 수가 없다는 것이다. 이를 극복하기 위한 몇가지 방법에 대해서 간단히 살펴보면 다음과 같다. 점진적 심화(progressive deepening) 방법은 정해진 깊이까지의 미니맥스를 수행한 뒤에도 시간이 아직 남아 있을 경우, 한단계 더 깊은 노드들에 대한 추가 분석을 수행하는 것이다. 휴리스틱에 의한 가지치기(heuristic prunning)는 예측할 필요가 없는 분기에 대한 가지치기를 미리 수행함으로서 알파 베타 가지치기와 함께 탐색 속도를 더욱 개선시킬 수 있다. 피드오버(feedover)는 위험한 상황에 대한 노드에 대해서 선택적으로 심화 탐색을 하는 방법이다. 예를 들어 체스에서 왕이나 퀸이 위험에 처하는 노드의 경우, 문제가 적절히 해결될 수 있는 깊이까지 더 탐색을 한다.

[개과천善]

왜 그림이 안보이는거죠 ㅡ>ㅜ 보구 싶은뎅 슈_슈

[아싸]

아이쿠 이런... 그림을 어느분 홈페이지껄 그대로 링크한건데 그분 홈페이지 가보니 리뉴얼중이내요. 미리 제 계정에 올려놨어야 하는데... 그분께 백업해 놓은게 있는지 문의 메일 보냈는데 메일 확인한뒤 이미지가 없어졌으면 가능한 이미지로 대체하겠습니다. 고마와요 개과천선님.