mini-max 게임 트리
저는 오목을 좋아하는 편이에요.
그래서 mini-max 게임 트리를 배울 때, 뭔가 오목에서 이길 때 생각하는 방식과 같아서 이에 대해서 다뤄보려고 합니다.
오목을 둘 때는 상대방의 한 수에 많은 수를 내다보고 승리할 수 있도록 하나하나 고심하여 두어야 합니다. 이를 트리 형태로 표현할 수 있는데, 제일 위 노드를 '자신' 상태로 두고, 아래 자식 노드를 '상대방' 상태로 두는 둥 번갈아 나타냅니다. 아래 사진 보시면 '컴퓨터 차례', '상대방 차례'가 있는 것을 알 수 있죠?
사진 출처 : https://lordofkangs.tistory.com/204
우리가 게임 진행 중 이기려고 하는 판단 과정은 게임 트리 속에서는 Min과 Max 연산이 이뤄집니다. 트리의 각 단말 노드에는 '자신'에게 유리한 정도를 휴리스틱을 통해 계산한 판세 평가값이 표시되어 있습니다. 그러면 이 값이 높으면 높을 수록 자신에게 유리한 것입니다.
Max : 항상 큰 값을 선택한다.
Min : 항상 작은 값을 선택한다.
게임에서도 나의 차례가 오고, 상대방의 차례가 오가는 것을 알 수 있죠? 이 때, 나에게 유리한 것을 선택해야하는 차례를 게임 트리의 관점에서는 MAX노드라고 해요. 그럼 당연히 상대방이 유리한 것을 선택하는 건 나에게 불리한 것이니까 MIN노드라고 하겠죠? 이제 우리는 MAX노드가 뭔지, MIN노드가 뭔지 알게 되었어요~!
그럼 한 번 예시를 통해 알아볼게요~!
이 사진에는 모든 노드에 값이 한꺼번에 나타나 있지만, 원래는 단말 노드에만 판세 평가값이 들어가 있어요.
(이렇게 아래만 채워져 있고 비어있어요)
원래는 맨 아래 단말 노드의 이 숫자들만 들어가 있었겠죠~?
단말노드에서부터 의미있는 수만 위로 올라가게 되는데, 여기서 MIN노드와 MAX노드인지를 고려해야해요~!
그 다음은 MAX노드이기에, 2와 3중에서는 3이, 5와 9중에서는 9가 선택되는 과정, 즉 큰 값이 골라지겠죠?
그리고 그 위는 MIN노드이기에, 작은 값들이 올라오네요~!
이 값들 중에서 이제, 루트 노드에 최종적으로 MAX노드가 적용되어 '3'이 올라오게 됩니다.
'자신'과 '상대방' 모두 최선의 선택을 했는데, 가져갈 수 있는 최대 이익값이 3이라니, 나는 9라도 가져갈 수 있을 줄 알았는데.. 그쵸~? 이것이 현실이에요~
하지만, 실제 게임에서 저 판단을 따라간다면, 유리한 고점을 취할 수 있을 거에요!
지금까지 제가 설명한 것이 mini-max 알고리즘 입니다~!
"일정 깊이의 게임 트리를 만들고, 단말 노드들을 휴리스틱을 사용하여 평가하고, 아래에서 위로 MIN과 MAX 연산을 번갈아 수행하여 노드 값을 결정한다. 그러고 나서 루트 노드의 자식 노드들 중에서 최대값을 갖는 것에 해당하는 행동을 선택하는 알고리즘을 mini-max 알고리즘이라고 한다."
가지치기
우리는 앞서 mini-max알고리즘를 배웠을 거에요~~ (재강조)
"일정 깊이의 게임 트리를 만들고, 단말 노드들을 휴리스틱을 사용하여 평가하고, 아래에서 위로 MIN과 MAX 연산을 번갈아 수행하여 노드 값을 결정한다. 그러고 나서 루트 노드의 자식 노드들 중에서 최대값을 갖는 것에 해당하는 행동을 선택하는 알고리즘을 mini-max 알고리즘이라고 한다."
하지만, mini-max알고리즘은 맨 아래에서부터 비교하기 위해, 게임 트리 전체를 메모리에 가지고 있어야 합니다. 이는 점점 트리가 커질수록 부담이 커지겠죠?
그래서, 똑똑한 사람들이 굳이 탐색해볼 필요가 없는 노드를 판단해서 잘라내기 시작했어요. 이를 α-β 가지치기 알고리즘이라고 합니다~!
α-β 가지치기는 α-자르기, β-자르기로 이루어졌어요.
왜 두 개 일까요?
mini-max알고리즘이 MIN노드와 MAX노드로 이루어지는 특징때문이에요~
먼저 어떻게 이뤄지는 지 볼까요?
탐색 방식 : 깊이 우선 탐색
위와 같은 자신에서, 뭔가 가지치기 당한 느낌의 노드들이 있어요.
왜 저런 가지치기를 당했을까요?
이제부터 알아볼 것입니다.
단말노드에서 MIN노드로 올라오면서, 5와 6중 5가 올라가고, 그리고 부모노드에 임시로 올라가고 그 다음 형제노드를 생각하게 되겠죠?
7을 탐색하고, 4를 탐색하고.. 자연스레 5를 탐색하기 전에 메모리의 사정으로 우리는 생각을 하게 됩니다. 굳이 5도 탐색해야할까?
답은 아닙니다. 우리는 현재 MIN노드와 MAX노드가 번갈아 나타난다는 점을 기억해야해요. 이제 한 번 경우의 수를 생각해봅니다.
1. 만약 4보다 높은 수가 나온다면? -> MIN노드로 더 작은 값을 선택하기에, 상대방이 택하지 않고 최소의 수인 4를 택한다.
2. 만약 4보다 낮은 수가 나온다면? -> 상대방은 4보다 낮은 이 수를 택할 것이다 -> 하지만 다음 내 차례에서 5보다 낮기에 내가 택하지 않는다.
뭔가 MIN노드도 사용하고, MAX노드의 값도 비교해서 사용하는 느낌이네요~
MIN노드의 현재 값이 부모 노드(즉, MAX노드)가 현재 가지고 있는 값보다 작거나 같다면, MIN노드의 자식 노드들을 탐색해 볼 필요가 없다.
이와 같이 MIN노드에서 더 이상 자식 노드를 탐색해 볼 필요가 없을 때, 탐색을 그만두는 것을 α-자르기라고 한다.
이제 빨간 박스 안의 상황을 보겠습니다. 첫 번째 6은 다른 선택이 없어 6이 선택되었고 6, 9가 있는 노드 중 6이 들어 있는 노드를 탐색했습니다. 이제 9가 들어있는 노드를 탐색하기 전에
3. 만약 이 노드가 6보다 높은 수가 나온다면? -> 상대방은 이 숫자를 택하지 않고 이전에 검색된 6을 선택한다.
4. 만약 이 노드가 6보다 낮은 수가 나온다면? -> 상대방은 6보다 낮은 숫자를 택하게 되지만 다음 내 차례에서 이 숫자를 택하지 않는다.
즉 만약 가지치기하지 않고 9가 탐색된다면 상대방은 6, 9 중 6을 택하게 됩니다. 반대로 6보다 낮은 수 예를 들어 3이 탐색되었다고 가정하면 상대방이 3를 택하게 됩니다. 하지만 다음 내 차례에서 6, 3중 6를 택하게 됩니다.
다시 말해서 어떤 수가 나오던지 상대방 혹은 내가 택하지 않게 되기에 검색할 필요가 없는 것입니다.
다시 빨간 화살표가 표시된 노드까지 올라가서 8이 들어가 있는 노드부터 검색해보려 합니다. 하지만 8이 들어간 노드가 화살표로 표시된 노드인
5. 만약 5 보다 크다면? -> 상대방의 차례에서 선택하지 않고 이전에 검색된 5를 택한다.
6. 만약 5 보다 작다면? -> 만약 8이 아니라 2라고 가정했을 때 상대방은 5, 2 중 2를 택하게 되지만 다음 내 차례에서 이미 검색된 3, 6 보다 작은 수이기에 내가 선택하지 않는다.
다시 말해서 5보다 큰 수는 상대방이 선택하지 않고 5보다 작은 수는 다음 차례의 내가 선택하지 않는다.
자, 모두 α-자르기 입니다.
이제 한번 β-자르기를 볼까요?
이처럼 MAX노드의 현재 값이 부모 노드(즉, MIN노드)의 값보다 크거나 같다면, 부모 노드의 값을 줄일 가능성이 전혀 없기 때문에 마찬가지 이유로 자식 노드를 더 이상 탐색해볼 필요가 없다. 이와 같은 상황에서 아래 노드에 대한 탐색을 그만 두는 것을 β-자르기라고 한다.
모두 현재 노드와 현재 노드의 부모 노드를 비교하지만, MIN노드에 있는지, MAX노드인지만 확인하면 α-자르기, β-자르기를 구별할 수 있답니당~~!
메모리를 아끼는 α-β 가지치기를 알아보았어요~ 다들 어떠셨나요? 유익한 시간 되셨길 바라용~!
