minmax search 와 알파-베타 가지치기

 공부하다보면 트리를 서치하는 여러가지 방법이 나온다. 여기서는 두명의 플레이어가 게임을 한다고 가정하고 이야기를 진행해 보겠다. 

1. 개요 

만일 당신이 누군가와 체스를 두고 있다. 당신은 지금 폰을 움직여 상대 비숍을 잡을 수도 있고 룩을 움직여 상대 폰을 잡을 수도 있다. 이런 상황이면 대부분의 사람들은 폰을 움직여 비숍을 잡으려 할 것이다. 왜냐하면 그게 자신의 차례에서 최대의 이득이 되니까이다. 하지만 폰을 움직이게 되면 본인의 퀸이 잡힌다면? 그러면 그런 수는 두지 않을 것이다. 

오늘 설명하려는 알고리즘도 이와 같다. 자신의 차례에는 자신의 이득을 최대한으로 하려고 하고 이와 마찬가지로 상대 역시 상대 편에는 나의 이득을 최대한 줄이는 방법을 선택하려고 할 것이다. 

그중 첫번째로 볼 것은 min-max tree sreach이다.

2. min-max tree sreach

일단 기본적인 min-max의 알고리즘을 확인해보겠다. 

트리는 다음과 같이 4,6,7,9,1,2,0,1,8,1,9,2의 말단 노드를 가지고 있다. 이때 min-max의 경우 처음은 본인의 차례로 생각하면 된다 그럼 각 말단 노드에서 비교하여 가장 큰 것을 확인해 선택하게 된다.(본인 차례에서는 최대의 이득을 얻는 것이 목표이므로) 

따라서 그 다음 노드는  4 - 6 => 6, 7 - 9 => 9 .....etc로 만들어 진다. 그리고 여기서 이제는 상대편으로 넘어가게 되는데 상대편은 상대 자신의 이득을 높이고 싶어하지 나의 이득을 높이고 싶어하지는 않는다. 즉 상대는 선택할 수 있는 값 중 최소의 선택을 하려 할 것이다. 따라서 방금 올라온 6과 9 중에서 상대는 6을 선택하게 될 것이다. 이런 식으로 모든 노드를 탐색, 비교하게 되면 결국은 8이 내가 선택할 수 있는 최선의 값이 되게 된다. 이게 min-max의 방식이다. 

본 방식은 구현이 매우 간단하다는 장점이 있지만 큰 문제점이 존재한다. 바로 트리의 깊이가 깊어질 수록 복잡도와 탐색 시간이 기하급수적으로 늘어난다는 것이다. 이는 근본적으로 줄일 수는 없다. 따라서 조금이라도 탐색 시간을 줄이기 위해 등장한 것이 바로 알파-베타 가지치기이다. 

3 알파-베타 가지치기

알파 베타 가지치기는 위의 min-max알고리즘을 따라 가다보면 탐색할 가치가 없는 노드를 미리 추론 할 수 있고 그런 가지는 과감히 버림으로써 시간 복잡도를 낮출 수 있다는 것이 가장 큰 장점이다. 그럼 위의 트리를 예시로 설명하겠다. 

1. 가장 먼저 트리의 가장 오른쪽인 노드로 탐색한다. (4)

2. 그다음 연결되어있는 옆 노드를 탐색해 6이라는 값을 얻은 후 4와 6을 비교한다. (4)

3. 6이 더 크므로 저장되어있던 4를 버리고 6을 업데이트 한다. (4) -> (6)

4. 다음 옆 노드로 넘어가 탐색해 7이라는 값을 얻는다. (6)

자 여기서 알파 베타 가지치기가 작용한다. 

다음과 같은 위치에서 현재 우리는 '7' 노드를 탐색하고 (아직 옆 노드가 9인지는 모른다!) 이쪽 값이 최소 7이상이 되는 것을 확인했다. 왜냐하면 만일 옆 노드가 1,3,5 등 7보다 작을 경우 우리는 우리의 이득을 최대한으로 해야하기 때문에 7을 고를 것이고 만일 옆 노드가 7보다 클 경우 우리는 그것을 선택할 것이다. 따라서 여기 노드의 최솟값은 7이다. 

그런데 우리는 시선을 조금만 더 넓게 볼 필요가 있다.

딱 한개 노드만 더 위로 보았다. 우리는 방금 전 옆 쪽에서 최선의 선택을 6으로 잡았다. 그리고 이쪽 노드의 최솟값은 7이다. 그럼 만일 이대로 올라가면 어떻게 될까? 상대는 나의 값을 최소로 하는 방식을 택할 것이고 당연히 7이상 보다 6을 택할 것이다. 

따라서 우리는 7이라는 데이터를 얻은 순간 이 노드는 어차피 상대에 의해 버려질 것임을 알 수 있다. 즉 우리는 9를 탐색하지 않고 가지를 칠 수 있다는 뜻이다. 이게 바로 알파 베타 가지치기이다.  방금 우리는 추론을 통해 하나의 노드를 탐색하지 않고 넘길 수 있었다. 

이번에도 메커니즘은 똑같지만 조금 다른 가지치기를 보겠다. 중간의 1,2,0,1의 말단 값을 가지는 노드로 가보자.

여기도 똑같이 우리는 1을 탐색하고 2와 비교하여 최대 값이 2임을 알 수 있다. 그리고 옆 노드로 넘어가서 0을 탐색, 확인할 수 있다. 이때 우리가 조금만 더 넓게 보자.  

우리는 옆에서 상대가 최솟값을 고르고 나오는 게 6임을 알 수 있었다. 그런데 지금 노드는? 현재 최대로 선택 할 수 있는 값이 2이다. 즉 0과 1이 값이 몇이든 100이든 1000이든 10000이든 상대는 최솟값을 선택할 것이고 이 노드에서 나올 수 있는 최대값은 2일 수 밖에 없다. 즉 전체적으로 이 노드가 필요 없다고 판단할 수 있다. 

정리하면 이번 가지치기는 현재 우리가 보유한 최대값보다 무조건 작게 나오는 노드를 탈락 시킨것이며 이전 가지치기는 상대의 선택에 따라 최솟값보다 무조건 크게 나오는 노드를 탈락시켰다는 차이가 있다. 따라서 이를 잘 구분하고 사용해야할 것이다.