공부하다보면 트리를 서치하는 여러가지 방법이 나온다. 여기서는 두명의 플레이어가 게임을 한다고 가정하고 이야기를 진행해 보겠다. 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의 방식이다. 본 방식은 구현이 매우 간단하다는 장점이 있지만 큰 문제점이 존재한다. 바로 트리의 깊이가 깊어질 수록 복잡도와 탐색 시간이 기하급수적으로