[=] 양자컴퓨터를 이용한 바둑

바 둑 철 학 논 문

양자컴퓨터를 이용한 바둑

곽 승 연

(20020607)

물리학과

한 국 과 학 기 술 원

2004

Abstract

현재 컴퓨터 바둑의 주요 당면과제를 대부분 소프트웨어-알고리즘, AI 등-의 측면에서 접근하고 있다. 여기에서는 컴퓨터 바둑의 연산을 하드웨어의 측면의 접근, 특별히 양자컴퓨터와 연관시켜 고찰한다.

먼저 컴퓨터 바둑에서 주로 이용되는 게임이론의 개요를 2장에서 설명한다. 기본 이론을 알아야 가능한 문제에 접근할 수 있기 때문이다. 3장에서는 동일한 게임이론의 바탕에서 계발된 컴퓨터 체스의 발전을 Deep Blue를 통해 살펴보고 체스에서의 컴퓨터 기술이 바둑에서 동일하게 사용될 수 있는지 살펴본다. 그리고 양자컴퓨터의 사용을 통한 문제 해결방안을 제시한다. 이어서 4장에서는 양자컴퓨터에 대한 소개를 하고 양자컴퓨터의 연산능력이 현재 컴퓨터 바둑이 안고 있는 문제를 해결할 수 있는지에 대한 가능성을 모색해본다.

목 차

Abstract

1. 서 론 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 1

2. 게임이론

2.1 최대 최소 탐색과정 (minimax search procedure) ‥‥‥‥‥‥‥‥‥‥‥‥ 2

2.2 알파-베타 자르기 (alpha-beta pruning) ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 3

2.3 휴리스틱 (Heuristic) ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 6

3. 체스에서의 컴퓨터 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 8

3.1 Deep Blue ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 8

3.2 체스와 바둑의 비교와 바둑연산의 한계성 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 8

3.3 바둑연산의 해결방안과 양자컴퓨터와의 관계 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 9

4. 양자컴퓨터 (Quantum Computer) ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 11

4.1 양자컴퓨터의 개요 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 11

4.1.1 양자컴퓨터 (Quantum Computer)란? ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 11

4.1.2 큐빗 (Qubit) ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 12

4.2 연산능력 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 12

5. 결 론 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 14

참고문헌 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ 15

1. 서 론

바둑은 단순한 규칙 속에 많은 경우의 수를 내포하고 있는 ‘Inexact Problem'의 대표적인 게임이다. 최근에 바둑은 게임으로서의 기능을 넘어서 인간의 정신세계의 연구 - 심리학, 인지과학 등- 와 새로운 기술의 개발 - 알고리즘, AI 등- 이라는 학문· 과학 연구 방법(혹은 대상)이 되었다.

물리학도로서 특별히 바둑을 통한 기술 개발이라는 흥미로운 주제를 그냥 넘길 수만은 없을 것 같다. 더군다나 세계의 많은 엔지니어들의 연구와 개발이라는 공격에도 굴하지 않고 여전히 버티고 서있는 저 모습을 본다면 말이다.

컴퓨터 바둑. 정보화시대의 새로운 바둑 문화이다. 컴퓨터 바둑은 두 가지로 나누어서 생각해 볼 수 있겠다. 첫 번째로는 컴퓨터를 매개로 하는 사람-사람간의 바둑이고 두 번째로는 컴퓨터 프로그램과 사람간의 바둑이다. 문제는 두 번째에 해당하는 컴퓨터 바둑인데 이는 과연 바둑 프로그램이 사람을 이길 수 있을 것인가에 대한 궁금증과 도전정신 때문이다. 더욱이 그 연구 과정에서 얻을 수 있는 과학· 기술적 성과와 점점 넓어지고 있는 바둑 시장(market) 등을 생각할 때 컴퓨터 바둑은 많은 사람들이 덤벼들만한 아이템임에 틀림이 없다.

여기에서는 물리학도로서 생각해 볼 수 있는 양자컴퓨터라는 방법을 통해 컴퓨터 바둑을 고찰해보고자 한다.

2. 게임이론

2.1 최대 최소 탐색 과정 (minimax search procedure)

최대 최소 탐색 과정 (minimax search procedure) 은 깊이가 제한된, 깊이 우선의 탐색 과정이다. 현재 위치에서 출발하여, 이길 수 있는 움직임을 만들어 내는 과정을 사용하여, 가능한 다음 번 위치를 만드는 것이 과정의 개념이다. 이들 위치에 정적 평가 함수를 적용하여, 최적 위치를 선택한 후, 출발 위치를 향해 후진하며, 평가된 값을 전달한다. 좋은 상황에 대해 높은 정적 평가 함수의 값이 주어진다고 가정할 경우, 체스에서는 다음 장기판의 위치에 대한 정적 평가 함수의 값을 최대화하는 것이 목표이다.

그림 1 단계 탐색

그림 1 을 예로 하여 이 과정의 작용을 살펴보자. 정적 평가 함수의 범위를 -10 에서 10 사이로 할 때, 10 은 우리의 승리를, -10 은 상대방의 승리를, 0 은 비기는 경우를 나타낸다. 경험적 방법에 사용되는 함수의 값을 최대화하는 것이 목표이기 때문에, 위의 그림에서는 B 로의 움직임을 선택한다. B 의 값을 A 로 후진 전달하면, 8 의 값을 가진 위치로 움직일 수 있다는 것을 알게 되어 A 의 값을 8 로 수정한다.

그림 2.2 단계 탐색

그러나, 체스에서는 상대방에 의해 다음 번에 수행될 움직임과, 위의 레벨로 후진될 단말 값을 고려해야 한다. 우리가 B 로 움직였다고 가정하자. 이때 상대방은 E, F 와 G 중의 하나를 선택한다. 상대방의 목표는 평가 함수의 값을 최소화하는 것이기 때문에 F 로 움직일 것이다. 만약 B 로 움직인다면, 한번 움직인 후, 연이어 발생될 실제 위치는 우리에게 매우 불리하다. 만약 상대방이 노드 E 를 선택한다면 우리에게 유리하지만, 이 단계는 상대방이 움직일 차례이기 때문에, 상대방은 노드 E 를 택하지 않을 것이다. 그림 3 은 새로운 값을 트리의 위쪽으로 전달한 결과를 나타낸다. 상대방이 선택할 차례에서는 그 레벨에서 가장 작은 값이 선택되어 후진 전달되며, 우리가 선택할 차례에서는 그 레벨에서 가장 큰 값이 선택되어 후진 전달된다.

그림 3 단계 탐색의 값의 후진 전달

두번 움직였을 때의 값을 후진시키면 우리는 C 로 움직이는 것이 유리하다는 것을 알 수 있다. 왜냐하면, 이용 가능한 정보가 주어졌을 때, 상대방이, -2 보다 더 낮은 값을 만들기 위해, 그곳에서 할 수 있는 일이 전혀 없기 때문이다. 시간이 허용하는 한 이러한 과정을 여러번 반복 수행하고, 루트 노드가 있는 레벨에서 최적의 움직임을 선택하기 위해, 이 과정의 실행에 의해 만들어진 좀 더 자세한 평가를 사용한다. 평가로부터 얻은 값을 후진시킬 때 교대로 최대값과 최소값을 선택하는 것은 두 경기자의 상반되는 전략을 설명하며, 이로 인해 이 과정이 최대 최소 방법이라 불려진다.

2.2 알파-베타 (α-β) 자르기 (alpha-beta pruning)

최대 최소 과정은 깊이 우선 탐색 과정이다. 시간이 허용되는 범위내에서 가능한 한 많은 경로를 조사하고 정적 평가 함수를 경로의 마지막 레벨의 게임 위치에 적용하여 얻어진 값을 한번에 한 레벨씩 경로 위로 후진하며 전달한다. 깊이 우선 탐색 과정의 한 가지 장점은 이미 알려진 해답보다 부적합한 것으로 판명된 부분적인 해답은 조사하지 않는 분기와 한계 방법을 사용하여, 이 과정의 효율성을 향상시킬 수 있다는 점이다. 세일즈 맨의 방문 문제가 좋은 예이다. 이 문제의 경우, 지금까지 발견된 최적 경로를 기억하는 것만이 필요한 작업이다. 만약, 후에 조사된 부분적인 경로가 이 한계보다 커지면, 이 경로의 탐색을 중단한다. 경기자의 최대화와 최소화를 모두 처리할 수 있도록 탐색 과정을 수정했던 것처럼, 각 경기자에 대해 하나씩 두 개의 한계를 포함하도록 분기와 한계 방법을 수정할 필요가 있다. 이 수정된 방법을 알파-베타 자르기 (alpha-beta pruning) 라 한다. 알파-베타 자르기의 수행을 위해 두 개의 출발 값이 사용되는데, 한 값은 최대화를 목표로 하는 노드에 배정될 값의 하한값 (알파라 부른다) 이며, 다른 한 값은 최소화를 목표로 하는 노드에 배정될 값의 상한값 (베타라 부른다) 을 나타낸다.

그림 4 알파 자르기

그림 4 에 보여진 예를 사용하여 알파-베타 자르기의 작용 방법을 알아 보자. 노드 F 를 조사하고 우리는 상대방이 -5 이하의 값을 배정받을 노드 C 를 선택할 것임을 알 수 있다 (상대방은 최소화를 목표로 하기 때문이다). 그러나 또한 우리는, 만약 노드 B 로 움직인다면, 노드 A 에 적어도 3 의 값이 배정된다는 것도 알 수 있다. 3 보다 적은 값을 만드는 노드로 움직이는 것은 노드 B 로 움직이는 것보다 부적합하다.

따라서 그러한 노드로의 움직임은 무시할 수 있다. 또한 노드 F 만을 조사하고도 노드 G 의 값에 관계없이, 노드 C 로 가는 것은 부적합하다는 것을 확신할 수 있다. 그러므로 노드 G 를 조사할 필요가 없다. 물론, 하나의 노드를 잘라 버림으로써 한계를 기억하고, 이들을 조사하기 위해 필요한 비용을 정당화할 수 있는 것은 아니지만, 만약 여섯 단계 이상의 트리를 조사해야 한다면, 단 하나의 노드만이 제거되는 것이 아니라, 전체 트리의 세 단계를 조사하지 않을 수도 있다.

알파와 베타가 모두 사용되는 방법을 보기 위해, 그림 5 에 소개된 예를 살펴보자. 이 트리를 탐색할 때, 노드 B 를 루트로 한 부분 트리를 모두 조사하여, 노드 A 에 적어도 3 의 값이 배정될 것임을 예측할 수 있다. 노드 F 를 지나 아래로 탐색해 갈 때, 알파 값을 사용하여 노드 L 은 조사할 필요가 없음을 알 수 있다. 이것의 이유를 알아보자. 노드 K 를 조사한 후, 노드 I 의 최대값으로 0 으로 주어져, 노드 F 의 최소값은 0 이 된다. 그러나 이 값은 알파 값 3 보다 적기 때문에 노드 I 의 후계 노드들은 조사할 필요가 없다. 최대화를 목표로 하는 경기자는 노드 C 를 지나 노드 I 로 가는 움직임을 택하면, 결과적으로 획득한 값이 0 보다 좋지 못하다는 것을 예측할 수 있기 때문에, 노드 B 로 움지인다. 다음은 베타 값이 어떻게 사용되는 지 알아 보자. 노드 I 에 대한 탐색을 중단한 후, 노드 J 를 조사하여 노드 F 의 값을 지정될 5 를 얻는데, 이 값은 노드 C 에 대한 베타 값이 된다. 이것은 노드 C 의 값으로 5 이하의 값이 배정됨을 의미한다. 노드 G 를 전개 팽창하여 노드 M 을 조사하고 7 의 값을 얻어, 이 값을 노드 G 에 후진 전달한다. 노드 C 에서 움직일 차례가 된 경기자는 최소화를 목표로 하기 때문에, 7 과 베타 (5) 를 비교하여 5 보다 큰 값 7 을 갖고 있는 노드 G 를 선택하지 않고, 5 를 갖는 노드 F 로 움직인다. 따라서 노드 G 의 후계 노드들은 탐색할 필요가 없다.

그림 5 알파-베타 자르기

앞의 예로부터, 최대화를 목표로 하는 단계에서는 현재의 하한값보다 작은 값을 가진 노드로의 탐색은 중단되고 최소화를 목표로 하는 단계에서는 현재의 상한값보다 큰 값을 가진 노드로의 움직임은 제거됨을 알 수 있다. 최대화를 목표로 하는 경기자에 대해 가능한 움직임을 제거하는 것은 사실상 최소화를 목표로 하는 단계에 대한 탐색의 중단을 의미한다. 다시 그림 4 의 예를 살펴보자. 일단 노드 C 가 노드 A 로부터의 부적합한 움직임으로 결정되면, 노드 C 이하의 최소화를 목표로 하는 단계에 있는 노드 G 나 혹은 다른 어떤 경로도 조사할 필요가 없다. 알파와 베타가 실제로 사용되는 방법은 최소화를 목표로 하는 단계에서 알파 값보다 작은 값을 가진 노드가 발견되면, 그 노드로의 탐색을 중단하고, 최대화를 목표로 하는 단계에서 베타 값보다 큰 값을 가진 노드가 발견되면 그 노드로의 탐색을 중단하는 것이다. 최대화를 목표로 하는 단계에서 높은 값이 발견되면 탐색을 중단한다는 것은 언뜻 보아서는 이상하게 여겨지겠지만, 이것은 최대화를 목표로 하는 단계 위에 있는 최소화를 목표로 하는 경기자가 특정한 노드를 선택할 경우, 최대화를 목표로 하는 단계에서 그 노드를 찾아야만 하기 때문이다.

알파-베타 자르기 과정의 효율성은 조사되는 경로의 순서에 크게 좌우된다. 만약 가장 나쁜 경로가 가장 먼저 조사된다면, 어떤 탐색의 중단도 발생되지 않을 것이다. 그러나 물론 최적 경로를 예측하여, 그것을 항상 가장 먼저 조사한다면, 탐색 과정은 불필요하다. 그러나 완전한 상황에서 자르기 기법이 얼마나 효과적인지 알 수 있다면, 다른 상황에서 이 기법의 수행 능력에 대한 상한값을 정할 수 있다. 만약 노드가 완전하게 순서화되어 있다면, 알파-베타 자르기를 사용하여 깊이 D 까지의 탐색에 의해 조사될 단말 노드의 수는 알파-베타를 사용하지 않고, 깊이 D/2 까지의 탐색에 의해 만들어진 단말 노드 수의 거의 2 배이다. 탐색을 수행할 깊이를 두 배로 하면, 더욱 중요한 이득을 얻게 된다. 비록 일반적으로 이러한 향상을 모두 실현할 수는 없지만, 알파-베타 자르기 기법은 최대 최소 탐색 과정을 효율적으로 향상시킨 기법이다.

이미 조사된 경로에 비해 매우 적게 향상된 부수적인 경로를 조사하지 않는 것으로까지 알파-베타 자르기 과정의 개념을 확장시킬 수 있다. 5-4 단계에서, 조사 중인 경로가 이미 발견된 다른 경로보다 비효율적이라면, 탐색을 중단한다. 그러나 그림 6 에 보인 상황을 살펴 보자. 노드 G 를 조사한 후 노드 C 로 움직일 때 얻을 수 있는 최적값이 3.2 임을 알게 된다. 만약, 노드 B 로 움직인다면, 3 점을 얻는다. 3.2 으로부터 얻어지는 효율성과 3 으로부터 얻어지는 효율성 간에 별다른 차이가 존재하지 않기 때문에 노드 C 에 대한 탐색을 중단하고, 더 많은 이득을 얻을 수 있는 트리의 다른 부분을 조사한다. 이미 알려진 경로에 비해 향상에 대한 가능성이 거의 없는 부분 투리의 탐색을 중단하는 것을 효과 없는 탐색의 중단 (futility cutoff) 이라 한다.

그림 6 효과없는 탐색의 중단

2.3 휴리스틱 (Heuristic)

Heuristic 은 그리스어 "heutiskein" 가 어원이며 "to discover" 라는 의미를 가진다. 즉 이미 정립된 공식에 의해서가 아니라, 정보가 완전하지 않은 상황에서 노력을 통해서 시행착오 (trial and error) 를 거처, 또는 경험을 통해서 주먹구구식의 규칙(rule of thumb) 을 통해 지식을 알게되는 과정을 의미한다. 잘 추측하는 기술 (art of good guessing) 이라고 표현하기도 한다. algorithm과는 달리 heuristic은 해결책의 발견을 보장하지 않는다. 그러나 heuristic은 algorithm보다 효율적이다. 왜냐하면 많은 쓸모없는 대안책들을 실제 시도하지 않고도 배제시킬 수 있기 때문이다. 효율적인 algorithm이 명백하게 바람직한 반면, 불행하게도 어떤 문제들은 (체계적인 탐색처럼) 단지 비효율적인 algorithm만 있게 되며 커다란 문제에 있어서 이러한 접근은 컴퓨터조차 가혹한 것이 된다. 아직 다른 유형의 문제들이 있기 때문에 이론가들은 어떠한 효율적인 algorithm이 가능한지에 대해 의심한다. 예를 들어, '판매원의 지도(travelling salesman)' 문제라고 부르는 것은 지도에 표시된 많은 점(판매원이 방문해야 하는 도시 또는 지점)들을 모두 연결하는 가장 짧은 경로를 발견하는 문제이다. 이 경우 체계적인 탐색 작업은 그다지 효율적이지 않다. 더욱이 점의 수가 증가할수록 계산 량은 거대해진다. 이처럼 적절한 algorithm이 존재하지 않는 상황에서는 다른 전략이 사용되어야 한다.

이미 언급했지만 algorithm은 문제의 해결책을 찾는데 비효율적인 수단이 될 수도 있다. 이를 설명하기 위해, 체스를 두고 있다고 가정해 보자. 최선의 행마를 선택하기 위한 algorithm은 현재의 위치에서 가능한 모든 움직임의 연속을 추적해 보아야 한다. 평균적으로 체스판의 특정한 한 위치에서 움직일 수 있는 곳은 35가지가 되기 때문에 가능한 행마의 추적을 통해 최선의 움직임을 발견하는 데 백만 년의 시간이 걸리게 된다. 다음의 세 번의 움직임에 대한 가능한 모든 순서를 따르는 algorithm을 이용한다 해도 평균 18억 번의 움직임에 대한 분석이 필요하게 된다. 공식적인 체스 게임의 제한 시간은 5시간이므로 세계 챔피언이라 하더라도 algorithm에 의존하지 못하게 된다. 대신 그들은 heuristic이라는 문제 해결 전략에 의존한다.

다양한 문제에 이용될 수 있는 것으로 확인된 많은 일반적인 heuristic이 있다. 이러한 전략들에는 역행하여 작업하기, 하위 목표를 만들기, 그리고 은유와 비유를 이용하기 등이 포함된다.

역행하여 작업하기 (backtracking) : 목표로부터 현 상황을 역으로 추적하는 것을 포함한다. 예를 들어, 당신이 무엇인가를 잃어버렸다면 당신은 그것을 가지고 있었던 최후의 장소에서부터 역으로 추적하는 것이다.

하위 목표를 만들기 (problem reduction) : 문제를 보다 작은 것들로 쪼개어 보다 다루기 쉬운 문제들로 만드는 것을 말한다. 예를 들어 '오염을 어떻게 중지시킬것인가?'라는 질문은 오염의 종류, 오염원 등으로 나눌 수 있다. 일단 하위 목표가 확인되고 나면 그것들을 개별적으로 처리할 수 있다.

은유와 비유 (analogy) : 외견상으로는 다른 맥락 간에 유사점을 찾아보는 것이 포함된다. 예를 들어, "인간의 눈과 카메라가 어떻게 같은가"라는 질문은 카메라의 자동초점거리 맞추기와 자동노출체계를 개발하도록 유도하였다. 유사하게 어두운 동굴 속을 빠른 속도로 날아다니는 박쥐의 물체 탐지 능력은 음파탐지기나 레이더 같은 장비의 개발로 이어졌다.

3. 체스에서의 컴퓨터

3.1 Deep Blue

세계 체스대회에서 12년간 체스챔피언을 지낸 카스파로프와 IBM의 과학자들이 8년에 걸쳐 개발한 슈퍼컴퓨터, ‘딥 블루(Deep Blue)’의 체스시합은 IBM 사가 10억원의 상금을 걸고 특별기획 사업으로 추진함으로써 일어나게 되었다.

카스파로프의 연산능력은 500만개의 뇌신경세포에서 얻어지며, 1초에 2가지의 행마를 검토할 수 있고 보통 10수 앞을 내다볼 수 있다. 한편, ‘딥 블루(Deep Blue)’의 계산능력은 512개의 체스 전용칩의 보조를 받는 32개의 마이크로프로세서에서 얻어지며, 행마의 계산속도는 1초당 2억 회로써 최대 74수까지 미리 계산할 수 있다. 이 컴퓨터에는 과거 100년간 열린 주요 체스 경기의 기보와 유명 체스 선수들의 경기 스타일이 내장되어 있다.

96년 2월에 미국 필라델피아에서 열린 인간과 컴퓨터의 체스대결 제 1차 시합에서 인간은 3승2무1패로 승리하였다. 그러나 여기에서 있었던 1패를 두고 조만간 기계가 인간을 이길 것이라는 관측이 여러 곳에서 나오자 자존심이 상한 카스파로프는 전승을 올려 보이겠다고 IBM에 재대결을 제의하였으며, 그 결과 1년 후인 97년 5월 3일부터 5월 11일까지 미국 뉴욕에 있는 에퀴터블 센터에서 제 2차전이 벌어지게 되었다.

제 2차 체스대결의 결과는 2승3무1패로 컴퓨터의 승리였다. 첫 대국은 카스파로프가 따내었으나, 두 번째는 '딥 블루'가 이겼으며, 계속 이어진 3회의 대국은 팽팽한 무승부의 행진이었다. 그러나 5차 대국 바로 다음날 벌어진 마지막 대국에서 육체적인 피로와 심리적인 부담 속에 어이없는 실수를 저지른 카스파로프가 경기시작 1시간 만에 돌을 던진 것이다.

'딥 블루'가 수억 번의 수순을 정확히 선택하는 것은 '혁신적인 소프트웨어 기술과 강력한 병렬과정 처리능력의 콤비네이션'으로 풀이된다. 즉, 네 가지의 기본적인 기준인 체스말의 우선가치, 효과적인 행마, 왕의 안전성, 그리고 진행속도를 계산하는 것으로 둔다는 것이다.

3.2 바둑과 체스의 비교와 바둑연산의 한계성

인공지능을 연구하는 학자들은 체스에 이어 바둑 프로그램을 만드는데 관심을 모으고 있다. 바둑에는 학습과 의사 결정 방식, 전략적 사고, 지식 표현, 패턴 인식, 직관 등 인공지능연구의 핵심적인 과제들이 모두 관련되기 때문이다.

바둑은 체스와는 비교도 안 될 정도로 복잡한 지능을 요구한다. 바둑은 그 복잡도가 체스보다 천문학적으로 크기 때문이다. 체스의 게임 트리에는 10150정도의 변화 가능성이 존재한다. 그에 비하여 바둑의 게임 트리에는 10750정도의 가능성이 존재한다. 좀 더 정확하게 계산해보자. 바둑판은 3백61개의 점으로 이뤄져있다. 바둑에서 경우의 수를 단순하게 생각하면 처음에는 3백61가지, 그 다음은 3백60가지, 이렇게 계속 가짓수가 줄어간다. 이를 모두 계산하면 361x360x359x358x… = 361! ≒ 1.44X10768에 해당하는 경우수가 나온다. 바둑판이 대칭성을 띠기 때문에 대각선을 기준으로 서로 같은 경우가 발생하면 이를 반으로 줄여서 계산하고, 죽은 돌이 생기거나 패가 생겨서 경우수가 늘어날 때는 수를 증가시켜야 하는 특성까지 감안해도 여전히 엄청난 경우의 수가 존재한다. 단순히 비교했을 때 바둑의 경우의 수는 체스의 경우의 수의 10600배가 되는 것이다.

그리고 서로 다른 게임의 룰, 즉 체스에 비해 바둑에 자유도(degree of freedom)가 크기 때문에 바둑의 복잡성은 체스의 그것에 비해 더욱 커지게 된다. 체스는 우선 졸(卒)과 비숍, 나이트, 루크, 퀸 등 16개의 말이 움직이는 길이 정해져 있지만 바둑은 돌을 어디에 둘 지 알 수 없어 변수가 무궁무진하다. 전문가들은 경기 시작 후 4수를 둘 때까지 체스가 1백50만 가지의 ‘가능성’을 갖고 있는 반면 바둑은 16억 가지의 변화가 예상된다고 분석한다. 바둑은 또 5수까지의 변화의 수가 1017(10경, 1조의 1만 배)을 넘어서기 때문에 1초당 2억 번의 변화를 검토할 수 있는 슈퍼컴퓨터 ‘딥 블루’조차 약 16년 동안 장고해야 한수의 해답을 내놓을 수 있다. ‘딥 블루’가 1초에 74수를 읽는 것을 고려할 때 ‘딥 블루’가 3초 만에 하는 수읽기를 바둑에서 실현하면 현재 컴퓨터의 성능으로 3만년이 넘게 걸릴 것으로 예측된다.

또한 체스가 말을 모두 배치해놓고 유(有)에서 무(無)로 게임을 진행하지만 바둑은 거꾸로 무에서 유로 진행된다는 점도 변화기능성을 갈수록 기하급수적으로 상승하게 하는 요인이다.

이와 같이 단순 산술적인 계산으로 미루어보아도 현재의(2장에서 언급된) 알고리즘과 하드웨어의 성능으로는 절대적으로 바둑에서의 ‘딥 블루’는 존재할 수 없다.

3.3 바둑연산의 해결방안과 양자컴퓨터와의 관계

결국 컴퓨터 바둑에 대한 문제 해결의 접근 방식으로는 첫 번째로 알고리즘의 빠른 연산이 필요하다. 알고리즘 자체의 효율성도 중요하지만 하드웨어의 발달 또한 중요하다. 현재 널리 쓰이고 있는 컴퓨터(Classical Computer)는 어떤 복잡한 계산도, 결국 덧셈과 자리 옮김으로 쪼갠 다음에 처리하는 것이다. 이런 알고리즘의 계산에서는 제약이 발생한다.

Computational Complexity란 어떤 알고리즘이 수행되는데 필요한 공간적, 시간적인 요구를 분석하는 것이다. 어떤 계산을 수행하는데 있어서, 필요한 시간은 계산횟수에 비례한다. 이런 표현을 간단하게 Big-O 표기법(O는 orderly)으로 표현하면 다음과 같다.

일반적으로 덧셈 및 곱셈은 자릿수의 증가에 따라 필요한 시간이 O(log N) 으로 나타난다. 하지만 이런 연산은 우리가 요구하는 분야에 적용하기에는 아주 적은 부분일 뿐이다. 따라서 우리는 간단하게 보이는 몇가지 문제를 컴퓨터를 사용하여 계산하기에는 너무 시간이 오래 걸리는 경우가 있다. 이런 예 중에서 가장 흔히 볼 수 있는 것이 바로, 소인수분해와 곱셈의 관계이다. 두 소수를 서로 곱하는 것은 매우 단순한 알고리즘으로 해결할 수 있다. 또, 그 중 한 수를 알고 있을 경우, 다시 나누는 것도 곱셈과 거의 비슷한 속도로 해결할 수 있다. 하지만, 두 소수를 모르는 경우에 소인수분해하는 경우는 상당히 복잡해진다.

소인수분해(factoring) 문제는 현재 사용하는 암호화 기법의 가장 흔한 예이다. 즉 암호를 알고 있는 경우에는 해독이 간단하지만[O(log N)], 암호를 모르는 경우에는 해독을 하는데 오랜 시간이 걸린다[O(exp(N)]. 최근에 양자컴퓨터(Quantum Computer)에서 사용할 수 있는 소인수분해 알고리즘이 개발되었는데(Shor 알고리즘으로 알려져 있다.) O((logN)2+x))로 실행된다(x는 작다). 즉, 덧셈 및 곱셈의 속도로 연산이 가능한 것이다.

이와 같이 양자컴퓨팅을 이용하면 새로운 연산방법으로써 알고리즘의 빠른 동작을 가능하게 할 수 있다.

두 번째로 heuristic이 강조되어야 하겠다. 게임을 배울 수 있어야 하며 여러 가지 움직임에 따른 변화되는 조건에 적응하는 적응형 지능이 필요하다. 즉, 자기 스스로 '논리'와 '사고체계' 두 가지 능력을 모두 다 갖추어야 하는 것이다. heuristic한 접근 방식으로써 첫 걸음은 바둑 정석, 묘수풀이, 사활문제와 유명 바둑기사들의 경기 스타일과 기보들을 Knowledge base로 만들어서 입력해야 할 것이다. 또한 실제로 경기를 치름으로써 이에서 얻어지는 교훈과 정보를 효율적으로 저장해야 할 것이다. 이 heuristic 방식은 그 Data base가 많으면 많을수록 깊이 있는 수가 나올 수 있다.

문제는 이 base가 커지면 검색과 분석에 시간이 오래 걸리기 때문에 제약이 생긴다는 것이다. 고대 아프리카 퍼즐게임을 완벽하게 분석하는 데에 200Tb(200Gb의 1024배, 대략 CD 30만장 분량)의 data용량이 필요했다고 한다. 그렇다면 바둑의 data의 크기는 얼마나 커져야 할 것인가? 따라서 Knowledge base를 빠르게 검색할 수 있는 능력의 컴퓨팅이 필요한 것이다.

양자 컴퓨터의 빠른 연산 능력에 대해서는 다음 4장에서 자세히 언급하도록 하겠다.

4. 양자컴퓨터(Quantum Computer)

4.1 양자컴퓨터의 개요

4.1.1 양자컴퓨터(Quantum Computer)란?

연산 혹은 계산(computation)은 주어진 입력에 대하여 적절한 출력을 주는 함수라고 정의할 수 있다. 컴퓨터는 그 동작이 연산으로 해석될 수 있는 물리적 실체(physical object)를 의미한다. 이러한 정의에 근거한다면 양자컴퓨터란 양자계의 상태가 입력, 출력 등의 정보(information)로 해석될 수 있고, 또한 상태의 진화(evolution)가 연산으로 해석될 수 있는 실제적인 양자계라고 말할 수 있다.

이제 기존의 컴퓨터와 양자컴퓨터를 비교하여 살펴보도록 하자.

	electric computer	quantum computer
information	Boolean (0, 1 ; bit)	Boolean (0, 1 ; qubit)
informatin implementation	voltage of wire	two-level system
bit	added or removed	conserved
reversibility	irreversible	reversible
gate	spatially arranged combination of transistors	time-ordered unitary operators

먼저 다루는 정보는 부울 대수로 둘 다 이진수를 기본으로 한다. 정보를 물리적인 실체에 구현하는 방법은 기존의 컴퓨터에서는 전선에 전압이 걸려있는가(1), 아닌가(0)로 표현하며 양자컴퓨터에서는 스핀 1/2 입자의 스핀상태가 up(1)인가 down(0)인가로 표현한다.

그런데 기존의 컴퓨터에서는 기본 게이트를 구성하고 전체 회로를 구성하는 데 있어 얼마든지 전선을 추가하거나 없앨 수 있다. 즉 정보의 최소 단위인 비트가 더해지거나 없어질 수 있는데 반하여 양자컴퓨터에서는 어떤 스핀계를 이용하던지 준비된 양자계의 evolution 동안 스핀을 없애거나 추가할 수 없으므로 큐빗의 수가 보존된다.

또한 기존의 컴퓨터의 경우 게이트는 공간적으로 구성된 전선과 트랜지스터의 조합으로 볼 수 있으며 정보는 공간적으로 지나가면서 연산되는 반면, 양자컴퓨터의 경우 게이트는 스핀계에 순차적으로 적용되는 유니터리 변환으로, 정보는 공간적으로 같은 곳(큐빗)에서 시간의 흐름에 따라 연산된다. 이때 양자계에서 우리가 인위적으로 가할 수 있는 모든 변환은 유니터리이고 시간에 대해 가역적(reversible)이다. 따라서 이 가역성 때문에 게이트를 설계할 때도 논리적으로 가역적으로 구성해야 하며 이는 큐빗의 수가 보존되는 것과도 일관성을 갖는다.

양자컴퓨터에서 8 bit CPU를 만든다면 기존의 컴퓨터에서는 CPU의 회로도를 바탕으로 기본 게이트들을 공간적으로 배열하는 것이겠지만, 양자컴퓨터에서는 8 개의 스핀 1/2 입자들이 전부이다. 이 8 개의 스핀에 8 bit 정보가 표현되고, 처리되며 CPU의 일반적인 기능은 이 스핀계에 가해지는 일련의 유니터리 변환들의 시간적 순서가 되는 것이다. 기존 컴퓨터에서 회로도가 중요하다면 양자컴퓨터에서는 유니터리 변환들의 순서(이것을 대응되는 개념으로 양자회로망;quantum network이라고 한다)가 중요하다.

4.1.2 큐빗(Qubit)

간단한 양자 시스템은 스핀 1/2의 1개의 입자이다. 이것의 베이시스 벡터(basis vector)는 스핀다운(spin down)(|↓>)과 스핀업(spin up)(|↑>)으로 각각 |0>와 |1>로 재표현할 수 있다. 그러한 입자의 상태는 ψ=α|0>+β|1>로 표현할 수 있는데 결론을 먼저 얘기하자면 양자컴퓨터의 계산단위인 큐빗(qubit)이란 바로 이런 각각의 확률을 가진 상태(state)들이 중첩상태(superposition of states)가 된 것을 말한다.

즉, 큐빗의 특징은 0 또는 1의 두 가지 값을 가질 수 있을 뿐 아니라 0과 1을 동시에 지닐 수 있다는 것이다. 이것은 양자역학의 상태가 중첩상태로 존재할 수 있기 때문에 가능하다. 양자역학의 언어로 다시 말하면, 큐빗이란 {|0>, |1>}을 orthogonal basis로 하는 2차원 Hilbert 공간에서의 상태를 의미한다. 따라서 큐빗의 일반적인 상태는 a|0>+b|1>과 같이 나타내며, 여기서 a, b는 |a|2 + |b|2 = 1인 관계를 만족하는 복소수이다.

현재 물리적으로 큐빗은 스핀이 1/2인 입자의 스핀 상태와 광자(photon)의 편광(polarization) 상태가 이용되고 있다. 양자 컴퓨터를 구현하려는 실험들은 스핀 1/2인 입자들의 스핀 상태를 이용하고 있고, 양자정보전송이나 양자암호체계 등의 분야에서의 실험들은 광자의 편광을 이용하고 있다.

4.2 연산능력

일반컴퓨터의 최소 연산단위인 비트(bit)에 대응하여 큐빗은 양자컴퓨터의 연산단위 즉, 퀀텀 비트(quantim bit)를 의미한다. 양자컴퓨터에서 1바이트는 8개나 16개의 큐빗이 모여서 이루어진다. 이것을 스핀 1/2의 입자가 n개 있을 때로 일반화시킨다면 기저상태는 2의 n제곱 개가 존재하게 되는데 n이 증가함에 따라 Hilbert 스페이스의 차원은 지수 함수적으로 증가하게 된다.

여기에 유니터리 오퍼레이션(unitary operation)이란 작업을 수행하는 것이 양자컴퓨터의 계산 과정의 핵심이라 할 수 있겠는데 8개의 큐빗을 한번에 계산하는 양자컴퓨터(일반 컴퓨터로 얘기하자면 8비트 컴퓨터)라면 2의 8승인 256개의 다른 계산을 동시에 처리할 수 있는 것을 의미한다.(이것을 양자 병렬계산(quantum parallelism)이라 한다.)

보통의 컴퓨터는 전류가 흐르는 상태를 1, 전류가 끊긴 상태를 0으로 하여 8비트 컴퓨터라면 256까지의 계산을 한 번에 하나씩 처리하게 되지만 양자컴퓨터는 그 지수만큼의 수를 동시에 처리하게 되니 얼마나 계산이 빠른지는 비교하기 어려울 정도로 월등한 차이를 나타내는 것이다.

예컨대 일반 64비트 컴퓨터의 경우 한 번에 1개의 64비트 숫자를 처리할 수 있지만 양자컴퓨터는 모든 64비트 숫자들을 단 한번에 처리한다. 즉 2^64 가지의 숫자를 모두 처리한다는 의미인데. 2의 64승은 18,446,744,073,709,551,616으로 64큐빗의 양자컴퓨터는 64비트 일반 컴퓨터보다 18,446,744,073,709,551,616 배만큼 빠르다고 볼 수 있는 것이다. 실로 놀라운 차이가 아닐 수 없다.

이 차이를 체감하기 위해 간단한 비교를 해보자면 일반 컴퓨터가 5천8백억 년 동안 계산해야 될 문제를 양자컴퓨터는 단 1초 만에 풀어낸다.(2의 64승 초를 3600(시간)x24(일)x365(년)으로 나눠보라)

5. 결 론

64큐빗 양자컴퓨터의 경우 기존 컴퓨터보다 1019배나 빠른 계산이 가능하다는 것은 대단한 장점이다. 사실 이처럼 빠른 속도라면 컴퓨터 바둑을 해결할 수 있을 것이라는 생각에서 시작한 고찰이기도 하다. 연구 과정에서 최종적으로 생각하게 된 것은 양자컴퓨터의 빠른 계산 능력과 새로운 계산 방식의 알고리즘은 어느 충분한 정도까지의 컴퓨터 바둑의 성능을 제공할 수 있다는 것이다. 물론 바둑 게임의 경우의 수가 양자컴퓨터의 속도의 수치보다도 훨씬 크기 때문에 속도에만 승부를 걸어서는 안 될 것이다. 앞서 말한바와 같이 잘 개발된 알고리즘과 방대한 Knowledge base를 기초로 하는 heuristic의 방법이 동원되어야 한다. 이는 ‘Deep Blue'가 빠른 하드웨어와 신뢰할만한 소프트웨어를 겸비했을 때 인간을 능가할만한 능력(어쨌든 결과론적으로는)을 보여줄 수 있었던 것과 마찬가지이다.

양자컴퓨터는 21세기를 이끌 10대 기술 중의 하나로 꼽히고 있고 'Science'지에도 자주 연구 성과가 보고되고 있는 분야이다. 미국의 MIT, Stanford 대학 연구소나 IBM 연구소 등에서 연구가 진행되고 있고 이곳 한국과학기술원 물리학과 이순칠 교수 연구실에서도 활발한 연구 중이다. 그럼에도 실용화까지에는 여전히 넘어야할 많은 기술적 장벽들이 앞에 있다. 연구자에 따라 예측이 다르지만 실용화하기까지에는 최소 20년 이상은 족히 걸릴 것으로 보이며 더욱이 개발 불가능이라는 부정적인 관점도 다수 존재한다.

사실 초기 컴퓨터 에니악(Eniac)의 시대에는 지금과 같은 기술의 수준은 절대 가능할 것 같지 않았다. 그러나 퍼스널 컴퓨터(PC)의 시대가 왔고 현재 그 시대를 뛰어넘는 유비쿼터스(Ubiquitous) 시대가 되었다. 양자컴퓨터의 실현의 결과론은 몇 십 년 후에나 펼쳐야겠지만 선택적인(희망적인) 귀납적 모델들에 초점을 맞추며 논문을 맺는다. 언젠가의 벌어질 컴퓨터와 인간 바둑 챔피언 - 물론 한국인일 것이다 - 사이의 바둑 시합을 기대한다.

참고문헌

[1] 박우석, 『바둑철학』, 동연, 2002

[2] Elaine Rich, 『인공지능』, 유석인 외 번역, 상조사, 1986, pp 125~144

[3] 이순칠, 「양자전산(Quantum Computation)」, 한국과학기술원 물리학과

[4] 이순칠, 「공개키 암호체계와 Shor 알고리듬」, 한국과학기술원 물리학과

[5] 김재훈 외 공저, 「Quantum Computation」, 연세대학교 물리학과