오목이나 바둑, 체스와 같은 게임을 해본 적이 있나요? 두뇌 스포츠 혹은 마인드 스포츠라고도 하는 이 보드 게임들은 준비물이 간단하면서도 다양한 게임 전략을 펼칠 수 있어 전 세계에서 오랫동안 사랑을 받고 있습니다.
우리는 게임을 할 때, 여러 가지 수 중 어떤 수를 두어야 나에게 유리할지 고민하고는 합니다. 따라서 이 문제도 문제의 해를 여러 가지 탐색하는 ‘탐색 문제’로 다룰 수 있습니다. 이번 장에서는 게임 탐색 문제와 게임 탐색에서 자주 사용하는 알고리즘을 알아보겠습니다.
1. 몇 수 앞을 내다볼 수 있다면? - Mini-Max 알고리즘
게임 탐색에서 ‘게임’이란 규칙을 따르며 상대방과의 승부를 겨루는 것입니다. 그러므로 혼자 하는 게임과는 달리 나와 상대방이 번갈아 수를 두게 됩니다. 상대방의 수를 예상하고 이에 적절하게 대응하는 것이 승리의 지름길입니다. 만약 여러분이 상대방의 수를 모두 내다볼 수 있다면 어떨까요?
프로 바둑기사들은 바둑을 둘 때 상대방의 수를 10수, 20수 또 100수 앞까지 생각해볼 수 있다고 합니다. 하지만 집중력이 흐트러져 실수를 하게 되거나 경기가 잘 풀리지 않을 때에는 수를 예상하는 데 한계가 있기 마련인데요. 여기 항상 집중력을 유지하고 많은 수를 내다볼 수 있는 게이머가 있습니다. 바로 컴퓨터입니다. 컴퓨터가 게임을 할 때의 탐색 방법인 민맥스 혹은 미니맥스 알고리즘(Mini-max Algorithm)을 알아봅시다.
국민 게임, 오목을 생각해 볼까요? 오목을 할 때 우리는 상대방이 어떤 수를 낼지 예상해보고 나에게 유리한 곳에 수를 두고자 노력합니다. ‘좋은 수’를 컴퓨터가 이해할 수 있도록 수에 값(점수)을 매겨 봅시다.
예를 들어, 오목에서는 컴퓨터가 백돌일 때, 백돌이 연속으로 2개가 놓여있다면 10점, 3개면 30점, 3개지만 한 쪽이 막혀있다면 20점과 같은 방식으로 평가할 수 있습니다.
컴퓨터 차례라면 값(점수)이 큰 수를 선택할 것입니다. 상대방도 역시 자신에게 점수가 큰 수를 선택할 것입니다. 상대방에게 좋은 수는 곧 컴퓨터에게 불리한 수이므로 이 값은 작을 것입니다. 그러므로 컴퓨터와 상대방이 번갈아 두다보면 점수가 큰 값과 점수가 작은 값이 번갈아 선택되게 됩니다.
즉 민맥스 혹은 미니맥스 알고리즘(Mini-max Algorithm)이란 최저(Mini)와 최고(Max) 연산을 번갈아 하는 알고리즘입니다.
2. 틱텍토로 Mini-max 알고리즘을 살펴봅시다.
오목은 상태 공간이 크므로 오목보다 경우의 수가 작은 삼목, 틱택토 게임으로 예를 들어 보겠습니다. 틱-택-토(Tic-Tac-Toe) 게임은 가로·세로 3칸, 총 9칸의 작은 공간에서도 즐길 수 있습니다. 게임 참여자는 번갈아가며 O 혹은 X를 두며, 가로나 세로 혹은 대각선으로 같은 문양 세개가 이어지면 이기는 간단한 게임입니다. 비교적 간단한 규칙으로 직접 해보는 것이 더 이해가 쉬울 것입니다. 스크래치 프로그램으로 컴퓨터와 틱택토 게임을 해보세요. 컴퓨터가 X, 여러분이 O입니다.
틱택토 게임 상황을 다음과 같은 트리 구조로 정리하였습니다. 이것을 ‘게임 트리’(Game Tree)라고 합니다. 각 상태를 나무줄기의 마디를 나타내는 노드(Node)라고 부릅니다. 그림에는 총 4개의 노드가 보이네요. 맨 위의 노드(A)를 뿌리 노드, 즉 루트 노드(Root Node)라고 합니다. 앞으로는 각 노드에서 아래로 뻗어나가면 자식 노드, 각 노드가 속한 노드는 부모 노드라고 부르겠습니다. 예를 들어 A의 자식 노드는 B, C, D이고 B의 부모 노드는 A입니다.
[1단계] 현재 상태(루트 노드)에서 게임이 끝날 때까지의 수를 내다봅니다.
먼저 위의 게임 트리에서 A노드를 살펴봅시다. 컴퓨터가 X, 상대방인 사람이 O를 둡니다. 지금은 컴퓨터가 둘 차례네요. 컴퓨터가 게임이 끝날 때까지 수를 본다고 생각하고 노드를 확장해보겠습니다.(아직 실제로 두는 것은 아닙니다.) A 상태에서 컴퓨터는 ④, ⑥, ⑦의 위치에 X를 둘 수 있습니다. 그러므로 B, C, D의 상태로 노드를 확장합니다. 깊이1에 자식 노드 B, C, D가 만들어 졌습니다. D 노드를 보니 이미 X의 승리로 게임이 끝났습니다. D노드는 자식 노드가 더 나올 수 없으므로 탐색을 멈춥니다.
깊이2로 탐색을 이어나가보겠습니다. B와 C노드 상태에서는 이제 상대방이 O를 둘 차례입니다. 남은 칸이 2개이므로 각각 2개의 자식 노드가 생성됩니다. B의 자식 노드 E와 F, C의 자식 노드 G와 H가 생겼습니다. 이와 같이 더 이상 탐색할 것이 없을 때 까지 탐색을 이어가면 깊이3까지 탐색하게 되고 아래와 같은 게임 트리가 완성됩니다.
[2단계] 휴리스틱을 사용하여 노드를 평가합니다.
앞서 오목에서는 오목이 연속한 개수를 점수화 하여 평가하였습니다. 여기서는 간단하게 컴퓨터인 X가 이기면 10점, X가 지면(O가 이기면) -10점, 비기면 0점으로 설정하도록 하겠습니다. 게임 결과가 나온 노드를 평가하면 X가 이긴 노드 D, I, J는 각각 10점을, O가 이긴 노드 E, H는 각각 –10점을 받게 됩니다.
[3단계] 아래에서 위로 MIN과 MAX 연산을 번갈아 수행합니다. 루트 노드에 도달할 때 까지 반복합니다.
A노드에서 컴퓨터의 선택을 돕기 위해 아래에서 위로 연산을 수행합니다. 아래부터 수행하는 이유는 예상한 결과(아래로 갈수록 미래)가 현재의 선택(루트 노드)에 도움을 줄 수 있기 때문입니다.
(잠깐!) 연산을 수행하지 않아도 되는 노드가 있네요. 맨 아래 잎 노드(Leaf NODE) I의 부모 노드는 F 하나이므로 F의 점수는 I의 점수와 같이 10점입니다. G도 이와 마찬가지입니다.
B상태는 상대방의 차례입니다. B의 자식 노드 E와 F를 살펴보니 E는 –10점, F는 +10점이네요. 점수가 작으면 상대방에게 유리하고 점수가 크면 컴퓨터에게 유리하다고 했습니다. 그러므로 상대방은 E와 F중 자신에게 유리한 E를 선택할 것입니다. 따라서 B의 점수는 –10점이 됩니다.(MIN 연산) C도 이와 마찬가지입니다.
이제 다시 원래의 A로 돌아왔습니다. A는 컴퓨터의 차례입니다. 자식노드 B, C, D를 살펴보니 각각 –10, -10, +10점이네요. 컴퓨터는 자신에게 유리한 수를 두어야 하므로 당연히 점수가 제일 큰 D노드를 선택하는 것이 좋겠습니다.(MAX연산) B와 C를 선택하게 되면 상대방은 자연스럽게 승리하게 될 테니까요.
사실 이 예시는 미니-맥스 알고리즘의 설명을 돕기 위해 만든 것으로, 비기는 경우가 나와 있지 않아 실제 게임 상황과 거리가 멉니다. 또 이 예시에서는 탐색을 끝까지 하지 않아도 됩니다. 탐색을 줄일 수 있는 효율적인 방법이 있습니다.
3. 필요한 부분만 탐색해요. - α-β 가지치기
사실 앞서 살펴본 게임 트리에서는 아래와 같이 깊이1까지만 탐색해도 괜찮습니다. 컴퓨터가 바로 D노드를 선택한다면 게임이 끝나게 될 테니까요. B와 C는 아직 승부가 나지 않았으므로 비긴 것으로 생각하면 B와 C의 점수는 0점이됩니다. 그렇다면 가장 빨리 이길 수 있는 길은 D가 되겠지요?
민맥스 알고리즘을 수행할 때는 이와 같이 탐색 공간을 줄일 수 있는 방법이 있습니다. 탐색 공간을 줄인다는 것은 게임 상황이 너무나도 확실하여 더 이상 탐색할 필요가 없을 때 탐색할 것이 있어도 탐색하지 않는 것을 뜻합니다. 이 방법을 α-β 가지치기(α-β Pruning)라고 합니다. α-β 가지치기 알고리즘을 활용하면 불필요한 탐색 부분을 줄여 시간 및 공간(메모리) 복잡도를 줄일 수 있습니다.
여기 깊이3까지 깊이 우선 탐색을 마친 트리 구조가 있습니다. 게임의 형세를 휴리스틱으로 하여 잎 노드(Leaf Node) 평가 값 계산까지 마친 상태입니다. 여기서 Mini-Max 알고리즘을 수행하여 보겠습니다. 먼저 D 노드는 MAX노드입니다. 즉 컴퓨터한테 유리한 값을 선택해야 하므로 3과 4중 4를 선택하겠습니다. 곧이어 노드 B는 MIN노드입니다. 즉 상대방에게 유리한 값이 선택될 것입니다. 다시 말하면 4와 아직 계산하지는 않았지만 E의 값 중에서 작은 것이 선택될 것이므로 B의 평가 값은 4보다 작거나 같습니다. 마찬가지로 노드 A는 MAX노드이므로 B, C 중 큰 수를 선택할 것입니다. 즉 A는 4보다 크거나 같습니다.
이제 노드 E를 탐색하겠습니다. 노드 E의 자식노드를 살펴보니 5가 있네요. E는 5보다 크거나 같을 것입니다. 그런데 노드 B는 노드 D(4)와 노드 E(5 예상) 중 작은 값, 즉 노드 D(4)를 고를 것입니다. 노드 E의 자식 노드를 더 탐색해 나가서 작은 값 혹은 큰 값을 발견해도 노드 A와 B의 값은 변하지 않습니다. 왜냐하면 노드 E는 항상 최고값을, 노드 B는 최소값을 고르려고 할 테니까요. 그러므로 여기서 탐색을 멈춥니다. 즉 MAX 노드의 현재 값이 부모 노드보다 크거나 같을 때 탐색을 멈추는 것을 β-자르기(cut-off)라고 합니다. β-자르기는 MAX노드 밑에서 일어납니다.
이제 노드 F의 자식 노드를 살펴보겠습니다. F는 MAX노드이므로 1을 선택합니다. C는 MIN노드이므로 자연스럽게 1보다 작거나 같게 됩니다. 계속 위로 뻗어나가 A를 살펴봅시다. A는 MAX노드이므로 B와 C중 큰 값을 고릅니다. 그러면 현재 B는 4이고, C가 1보다 같거나 작으므로 더 큰 값인 B를 고를 것입니다. C는 앞으로 1보다 큰 수가 나올 가능성이 전혀 없고, 또 1보다 작은 수가 나올 가능성 또한 없습니다. G의 자식 노드가 큰 수가 나와도 깊이1의 MIN연산에서 탈락되고, 작은 수가 나와도 깊이2의 MAX연산에서 탈락되기 때문입니다. 그로므로 G의 탐색을 멈춥니다. 즉 MIN 노드의 현재 값이 부모 노드보다 작거나 같을 때 탐색을 멈추는 것을 α-자르기(cut-off)라고 합니다. α-자르기는 MIN노드 밑에서 일어납니다.
4. Mini-Max와 α-β 가지치기로 모든 수를 내다볼 수 있을까요?
앞서서는 틱텍토 게임이 끝날 때까지의 수를 모두 게임 트리로 나타냈지만 실제로는 그렇지 않습니다. 틱텍토의 경우 총 9칸의 공간에서 이루어집니다. 틱텍토에서 나타날 수 있는 게임의 수를 단순 계산해봅시다. 첫 수는 9개 중 한 칸에 둘 수 있고, 그 다음 수는 9칸을 제외한 8칸에 둘 수 있으므로 2수까지 9×8=72의 경우의 수가 있습니다. 이와 같이 계속 계산하면 9×8×7×6×5×4×3×2×1, 즉 9!를 계산하면 됩니다. 총 362,880가지의 경우의 수가 나오는 군요! 약 36만이라고 하니 생각보다 경우의 수가 커서 놀랐지요? 하지만 현재 컴퓨터 기술력으로 이 정도의 연산 수행은 크게 어렵지 않습니다.
바둑은 어떨까요? 바둑판은 가로 세로 19칸으로 이루어져 있습니다. 틱텍토와 같이 바둑 규칙을 고려하지 않고 단순 계산만 해서 비교해보겠습니다. 바둑판은 19×19이므로 총 361칸이네요. 경우의 수를 계산해보자면 361!, 즉 361×360×359×…×3×2×1입니다. 이를 계산하면 769자리의 엄청난 수가 나옵니다.
하지만 바둑의 특성상, 상대방의 돌을 따낸 경우 돌이 놓여있지 않게 되므로 경우의 수는 이보다 더 늘어납니다. 다른 방법으로 바둑 한 판 동안 프로 기사들의 수와 착수 가능한 수를 평균 내어 계산한다면 약 250^150≈10^360개의 조합이 있게 됩니다. 우주 전체에 있는 원자의 수가 약 10^80(10의 80제곱, 1e+80)개라고 하니 얼마나 큰 수인지 감이 오지 않지요?
바둑에서 가능한 게임의 조합을 컴퓨터가 모두 저장하여 관리하는 것은 현존하는 최고의 슈퍼컴퓨터로도 불가능한 일입니다. 하지만 2016년 구글의 인공지능 바둑기사, 알파고(AlphaGo Lee)는 최고의 프로기사 이세돌 9단과 대국을 겨뤄 4:1로 승리하였습니다.(사실 이세돌 9단이 같은 실수를 절대 하지 않는 인공지능을 이긴 것은 정말 대단한 일입니다.) 이후로도 알파고는 꾸준히 성능이 향상되어 중국 기사 커제를 포함, 60명이 넘는 사람과 대국을 하였으며 전승을 거두기도 했습니다.(AlphaGo Master)
바둑의 탐색 공간이 무한에 가깝다고 느껴질 정도로 무척 크기 때문에 이를 보완하기 위한 다른 탐색 방법이 필요했습니다. 알파고는 다음 수를 결정하기 위해 많은 시물레이션을 거치는 ‘몬테카를로 트리 탐색’ 방법을 활용합니다. 또 기계학습 방법을 활용하여 짧은 시간에 효율적인 선택을 내리도록 고안되었습니다. 기계학습과 관련된 내용은 ‘Chapter4. 자료와 학습’에서 살펴보도록 하겠습니다.
퀴즈
민맥스 알고리즘은 루트 노드가 자식 노드들 중 최대값을 갖는 것을 선택하도록 돕는다.
민맥스 알고리즘에 대한 올바른 설명이다.
민맥스 알고리즘은 위에서 아래 방향으로 최저-최고 연산을 수행한다.
잎 노드에서 뿌리 노드 까지 아래에서 위 방향으로 수행한다.
어떤 노드의 현재 값이 3이고 부모 노드의 값이 1보다 작거나 같을 때 탐색을 중지하는 것은?
이 문제에서 부모노드는 MIN 노드이므로 어떤 노드는 MAX 노드가 된다. MAX 노드의 현재 값이 부모 노드보다 크므로 탐색을 중지하는 것은 β -자르기이다.
참고문헌
- 이건명, 「인공지능 튜링테스트에서 딥러닝까지」, 생능출판(2018)
4. 예제 출처 https://www.youtube.com/watchv=trKjYdBASyQ&ab_channel=TheCodingTrain