체스보다 복잡한 바둑 인공지능, 몬테카를로 트리 탐색의 선택

체스에서는 딥블루가 세계 챔피언을 꺾은 지 오랜 세월이 흘렀지만, 바둑은 컴퓨터가 인간을 넘어서기까지 수십 년이 더 걸릴 것이라는 예측이 지배적이었다. 가로세로 십구 줄로 이루어진 바둑판에서 가능한 수의 조합은 십의 백칠십 제곱이라는 상상을 초월하는 수치에 달한다. 관측 가능한 우주 전체에 존재하는 모든 원자의 수를 다 합친 것보다도 압도적으로 많은 경우의 수다. 무식하게 모든 수를 계산하는 무차별 대입 기법으로는 슈퍼컴퓨터를 총동원해도 첫 몇 수를 넘기지 못하고 연산 불능 상태에 빠질 수밖에 없었다.

직관의 벽과 바둑의 상태 공간 복잡도

체스는 기물의 움직임이 엄격히 제한되어 있고 각 말의 점수 가치가 명확하여 특정 국면의 유불리를 수식으로 평가하기가 상대적으로 수월했다. 킹을 잡는 목표가 뚜렷하며 착점 가능한 평균 선택지도 서른 개 안팎에 불과하다. 반면 바둑은 모든 돌의 가치가 평등하며 착점 가능한 빈자리가 평균 이백 개가 넘는다.

더욱 까다로운 점은 돌들이 유기적으로 연결되어 만드는 세력과 집의 균형을 계량화하기가 극단적으로 어렵다는 사실이었다. 인간 프로 기사들은 수많은 수 중 좋은 형태를 직관이라는 경험적 감각으로 단숨에 좁혀낸다. 컴퓨터가 이 직관을 흉내 내지 못하는 한 바둑 인공지능의 발전은 요원해 보였다. 이 불가능의 장벽을 허물어뜨린 열쇠가 바로 확률적 무작위 시뮬레이션을 응용한 몬테카를로 트리 탐색이었다.

확률적 샘플링과 승률 역전파가 만드는 수읽기

몬테카를로 기법의 본질은 도저히 끝까지 계산할 수 없는 복잡한 문제를 무작위 표본 조사를 통해 통계적으로 근사하는 것이다. 어떤 착점 후보가 주어졌을 때, 그 자리에서부터 바둑이 끝날 때까지 컴퓨터가 양쪽 돌을 무작위로 빠르게 두어보는 가상 대국을 수만 번 반복한다. 그중 이 착점이 최종 승리로 이어진 비율을 집계하면 복잡한 형세 판단 공식 없이도 착점의 통계적 기대 승률을 계산해낼 수 있다.

몬테카를로 트리 탐색은 크게 네 단계의 순환 루프로 작동한다. 이미 승률이 검증된 유망한 경로를 파고드는 활용과, 아직 가보지 않았지만 잠재력이 있는 새로운 경로를 찔러보는 탐색 사이의 수학적 균형을 어퍼 컨피던스 바운드 공식을 통해 정밀하게 제어한다. 끝까지 가상 시뮬레이션을 돌려 승패 결과를 확인한 뒤, 그 승리 점수를 거쳐온 모든 상위 노드로 역전파하여 판세를 업데이트한다. 컴퓨터 과학과 지능형 알고리즘에 관한 더 깊은 분석은 치약칫솔용품 제작 에서도 확인할 수 있다.

단계	주요 수행 작업	핵심 알고리즘 원리	탐색 효율 기여도
선택 (Selection)	루트 노드에서 가장 유망한 하위 노드로 이동	다중 암드 밴딧 기반 균형 공식	유망한 경로에 계산 자원 집중
확장 (Expansion)	도달한 노드에서 새로운 착점 자식 노드 생성	정책 신경망의 착점 확률 순위	비현실적인 악수를 사전에 배제
시뮬레이션 (Simulation)	판이 끝날 때까지 빠른 속도로 가상 대국 진행	가치 신경망의 즉각적 국면 평가	수백 수 앞의 승패 통계 집계
역전파 (Backpropagation)	대국 결과의 승패 점수를 상위 노드들로 전파	누적 승률 및 방문 횟수 업데이트	전체 트리 신뢰도 지속적 향상

정책망과 가치망의 결합으로 완성된 초인적 지능

초기 몬테카를로 트리 탐색만으로는 프로 기사의 깊은 수읽기를 당해낼 수 없었다. 무작위 대국 과정에서 너무나 엉뚱한 악수들이 빈번하게 섞여 승률 통계가 왜곡되었기 때문이다. 이 한계를 완벽히 극복한 것이 딥마인드의 알파고였다. 심층 인공신경망을 결합하여 인간 기사들의 직관을 수학적으로 모방하는 데 성공한 것이다.

다음 착점 후보의 우선순위를 좁혀주는 정책 신경망과, 판의 형세를 단번에 숫자로 판정해주는 가치 신경망이 투입되었다. 컴퓨터는 더 이상 무작위로 바둑을 끝까지 둘 필요 없이, 정책망이 추천한 몇 가지 핵심 경로만을 몬테카를로 트리로 좁혀 파고들고, 가치망의 평가를 바탕으로 신속하게 승률을 확정했다. 무한에 가까운 경우의 수를 지닌 혼돈의 바둑판 위에서 인공지능은 수학적 확률과 딥러닝의 결합을 통해 인류 지성의 오랜 성채를 넘어섰으며, 복잡계 최적화 문제 해결의 새로운 지평을 열어젖혔다.