게임 트리 탐색: 미니맥스와 몬테카를로 트리 탐색(Game-tree search: minimax and Monte Carlo tree search)

틱택토에서 내 차례라고 합시다. 둘 수 있는 칸마다 그 수를 둔 판을 그리고, 그 판마다 상대가 둘 수 있는 수를 다시 그리고, 게임이 끝날 때까지 이어 가면 트리⁠(tree)⁠ 하나가 생깁니다. 이것이 게임 트리입니다. 끝난 판(잎⁠, leaf⁠)에는 내 쪽에서 본 점수를 붙입니다. 이기면 +1, 비기면 0, 지면 −1입니다. 이제 잎에서 거꾸로 올라오며 값을 채웁니다. 내 차례인 노드(MAX)에서는 자식들 가운데 가장 큰 값을, 상대 차례인 노드(MIN)에서는 가장 작은 값을 고릅니다. 상대도 최선을 다한다고 가정하는 것입니다. 이렇게 끌어올린 뿌리의 값이 서로 최선을 다할 때의 결과이고, 그 값을 준 자식이 둘 수입니다. 이것이 미니맥스이며, 트리를 내려갔다 올라오는 재귀⁠(recursion)⁠로 짧게 적힙니다.

$$v(n) = \max_{c}\, v(c)\ \ (n\text{: MAX}), \qquad v(n) = \min_{c}\, v(c)\ \ (n\text{: MIN})$$

이 논리를 끝까지 밀면 다음 결론이 나옵니다. 우연이 끼지 않고, 두 사람이 판 전체를 보며 번갈아 두고, 반드시 유한한 수 안에 끝나는 게임에서는, 한쪽이 반드시 이기는 방법을 갖거나 양쪽 모두 지지 않는 방법을 갖습니다. 1913년 에른스트 체르멜로의 체스 논문에서 비롯해 흔히 체르멜로 정리라 부르는 결과입니다. 체스라면 백 필승, 흑 필승, 무승부 가운데 하나가 이미 정해져 있다는 뜻입니다. 다만 그것이 어느 쪽인지는 아무도 모릅니다. 틱택토의 값은 무승부이고, 끝까지 둔 게임의 가짓수가 255,168가지라서 컴퓨터로 금방 다 볼 수 있습니다. 체커는 2007년 조너선 섀퍼의 연구진이 18년에 걸친 계산 끝에 무승부임을 증명했습니다. 체스는 사정이 다릅니다. 한 국면에서 둘 수 있는 수가 평균⁠(mean)⁠ 35개쯤이고 한 판이 양쪽 합쳐 80수 안팎이면, 잎은 대략 35⁸⁰ ≈ 3 × 10¹²³개입니다. 1950년 클로드 섀넌은 비슷한 셈으로 10¹²⁰이라는 어림을 냈습니다. 바둑은 둘 수 있는 수가 250개쯤, 한 판이 150수쯤이라 250¹⁵⁰ ≈ 10³⁶⁰입니다. 그래서 실제 프로그램은 몇 수 앞까지만 펼치고, 멈춘 국면의 값을 평가 함수(남은 말의 가치, 말의 자리 등으로 매긴 점수)로 어림합니다. 섀넌이 1950년 논문에서 제안한 방법입니다.

알파–베타 가지치기. 미니맥스를 곧이곧대로 하면 모든 잎을 봐야 할 것 같지만, 결과를 바꿀 수 없는 가지는 건너뛸 수 있습니다. 아래는 MAX와 MIN이 두 번씩 번갈아 오는 깊이 4의 트리입니다. 가지치기: · 자식의 순서: · 새 잎 값

탐색하는 동안 두 수를 들고 다닙니다. α는 뿌리에서 지금 노드까지 오는 길 위의 MAX가 다른 가지를 골라 이미 보장받은 최저 점수, β는 그 길 위의 MIN이 다른 가지로 이미 눌러 둔 최고 점수입니다. MIN 노드에서 자식 하나가 α 이하의 값을 돌려주면, 그 MIN 노드의 값은 이미 α 이하로 정해집니다. 위의 MAX는 다른 길로 α를 확보해 두었으니 이 노드에서는 더 나은 것을 얻을 수 없고, 나머지 자식이 무엇이든 마찬가지라서 볼 필요가 없습니다. MAX 노드에서 β 이상이 나올 때도 같습니다. 이렇게 멈춘 노드가 돌려주는 값은 정확한 값이 아니라 한계(많아야, 적어도)이지만, 뿌리의 판단에는 그것으로 충분합니다. 잘라 낸 뒤에도 뿌리의 값과 고르는 수는 미니맥스와 정확히 같으니, 가지치기는 어림이 아닙니다. 얼마나 잘라 내는지는 순서에 달렸습니다. 지금 평가한 잎은 개입니다. 처음 잎 값에서 주어진 순서로는 16개 가운데 8개를 봅니다. '좋은 수부터'로 바꾸면(같은 게임에서 자식의 순서만 바꾼 것) 7개만 보고, '나쁜 수부터'로 바꾸면 15개를 봐서 거의 잘라 내지 못합니다. 1975년 도널드 커누스와 로널드 무어의 분석에 따르면, 가지가 b개씩이고 깊이가 d인 트리에서 순서가 가장 좋을 때 보는 잎은 $b^{\lceil d/2 \rceil} + b^{\lfloor d/2 \rfloor} - 1$개입니다(여기서는 4 + 4 − 1 = 7). 같은 시간에 거의 두 배 깊이까지 볼 수 있다는 뜻입니다. 잎의 값이 무작위일 때의 평균적인 효율은 1980년대 초 주디아 펄 등이 분석했습니다. 실제 프로그램은 좋아 보이는 수를 먼저 보도록 순서를 정하는 데 공을 들입니다.

1997년 5월 가리 카스파로프를 이긴 IBM의 딥 블루는 이 알파–베타 탐색을 전용 칩으로 1초에 약 2억 개의 국면에 적용했고, 평가 함수⁠(evaluation function)⁠는 사람이 설계한 수천 개의 항목으로 이루어졌습니다. 그러나 바둑에서는 이 방법이 잘 통하지 않았습니다. 가지가 너무 많은 데다, 돌이 놓인 국면이 누구에게 얼마나 유리한지를 수로 매기는 좋은 평가 함수를 사람이 적기 어려웠기 때문입니다.

몬테카를로 트리 탐색. 평가 함수를 적을 수 없다면 끝까지 두어 보면 됩니다. 한 국면에서 양쪽이 무작위로 두는 대국(플레이아웃⁠, playout⁠)을 여러 번 해서 이긴 비율을 세면 그것이 그 국면의 거친 평가가 됩니다(몬테카를로 방법⁠(Monte Carlo method)⁠). 큰 수의 법칙⁠(law of large numbers)⁠에 따라 대국 수 n을 늘릴수록 이 비율은 그 국면에서 무작위로 두었을 때의 승률에 다가가고, 흔들림은 $1/\sqrt n$에 비례해 줄어듭니다. 다만 무작위로 둘 때의 승률은 서로 최선을 다할 때의 결과와 같지 않습니다. 그래서 유망한 수를 더 자주, 더 깊이 살피도록 트리를 키워 갑니다. 2006년 레미 쿨롱이 이름 붙인 몬테카를로 트리 탐색(MCTS)은 한 번 탐색할 때마다 네 단계를 밟습니다. 뿌리에서 규칙에 따라 자식을 골라 내려가고(선택), 트리의 끝에 새 노드를 하나 붙이고(확장), 거기서 무작위 대국을 끝까지 두고(시뮬레이션), 결과를 지나온 노드들의 승패 기록에 더합니다(역전파⁠(backpropagation)⁠. 신경망⁠(neural network)⁠의 역전파와 이름만 같습니다). 같은 해 레벤테 코치시스와 차바 세페슈바리가 제안한 UCT는 선택 단계에서 다음 값이 가장 큰 자식을 고릅니다.

$$\frac{w_i}{n_i} + c\,\sqrt{\frac{\ln N}{n_i}}$$

N은 부모를 거쳐 간 횟수, $n_i$와 $w_i$는 자식 i를 거쳐 간 횟수와 그중 이긴 횟수입니다. 첫 항은 지금까지의 승률(활용)이고, 둘째 항은 적게 가 본 자식일수록 커지는 덤(탐험)입니다. 여러 슬롯머신 가운데 어느 것을 당길지 정하는 문제에서 온 규칙(UCB1)이라, 좋은 자식에 탐색이 점점 몰리지만 어떤 자식도 완전히 버려지지는 않습니다. 고정된 깊이까지 모두 펼치고 거기서 평가 함수를 믿는 미니맥스와 달리, MCTS는 불확실한 값을 표본⁠(sample)⁠으로 어림하며 탐색할 곳을 유망한 쪽에 더 많이 나눠 줍니다. 이 방법으로 바둑 프로그램은 2010년 무렵 아마추어 유단자 수준에 이르렀지만, 프로 기사와는 여전히 차이가 컸습니다.

알파고. 2016년 딥마인드의 알파고는 MCTS에 신경망 둘을 붙였습니다. 국면을 보고 유망한 수의 확률⁠(probability)⁠을 내는 정책망⁠(policy network)⁠은 살펴볼 가지를 좁힙니다. 국면의 승률을 어림하는 가치망⁠(value network)⁠은 끝까지 두어 보는 대국과 함께 트리 끝의 값을 매겼는데, 이 대국은 완전히 무작위가 아니라 작고 빠른 정책으로 둔 것이었습니다. 정책망은 먼저 사람의 기보로 배우고, 이어 자기 자신과의 대국으로 강화 학습⁠(reinforcement learning)⁠을 했습니다. 이듬해의 알파고 제로는 사람의 기보 없이 자기 대국만으로 배웠고, 끝까지 두어 보는 대국 없이 가치망의 어림만 썼습니다. 두 경우 모두 트리 탐색이 뼈대이고, 학습은 무엇을 살필지와 멈춘 곳의 값을 어림하는 일을 맡았습니다.

이어지는 곳. 게임 트리⁠(game tree)⁠는 트리의 한 예이고, 같은 국면에 여러 길로 도달할 때 값을 표에 적어 다시 쓰는 요령은 동적 계획법⁠(dynamic programming)⁠과 같습니다. 값을 끌어올리는 이 계산에서 상대 대신 주사위처럼 확률로 움직이는 환경이 있으면, 최솟값 대신 기댓값⁠(expected value)⁠을 끌어올리게 되고 이것이 강화 학습의 벨먼 방정식입니다. 무작위 대국으로 값을 어림하는 방법의 근거는 몬테카를로 방법과 큰 수의 법칙에 있습니다. 두 사람이 동시에 수를 고르는 유한한 영합 게임(한쪽의 이득이 곧 다른 쪽의 손해인 게임)에서도, 확률적으로 섞은 전략⁠(mixed strategy)⁠까지 허용하면 max-min과 min-max가 같습니다. 1928년 폰 노이만이 증명한 이 미니맥스 정리⁠(minimax theorem)⁠는 선형 계획법⁠(linear programming)⁠의 쌍대성⁠(duality)⁠으로도 증명됩니다. 판을 n × n으로 키운 체스는 지수 시간에 풀리는 문제 가운데 가장 어려운 부류(EXPTIME-완전)에 듭니다. 지수 시간 문제 가운데 다항 시간⁠(polynomial time)⁠에 풀 수 없는 것이 있다는 것은 증명되어 있으므로(시간 계층 정리), 일반화한 체스는 다항 시간에 풀 수 없습니다. 아직 답이 없는 P 대 NP 문제와 달리 이쪽은 증명된 사실입니다. 컴퓨터 체스의 설계도를 일찍 적은 사람으로는 섀넌과 튜링이 있고, 가지치기의 효율은 커누스와 펄이 분석했습니다. 스스로와 두며 평가를 고쳐 가는 생각은 새뮤얼의 체커에서 알파고까지 이어집니다.