요즘 올블로그에 바둑과 체스에 대한 이야기가 많군요. 저의 경우, 두 게임 모두 실력은 형편없지만, 둘 다 기본 규칙은 나름대로 정확히 알고 있다고 생각합니다. 어느 한 쪽의 편을 들기 위한 글이 아니며, 순수하게 제가 궁금해서;;; 계산해 본 것임을 미리 말씀드립니다.


이해를 돕기 위해, 여기에 G라는 가상의 게임이 있다고 해 봅시다. 이 게임 G는 두 명이 서로 경쟁하는 게임으로, 각각 번갈아 가며 한 수씩 두는 게임입니다.

우선, 수를 분석하기 위해서는, 한 번 계산할 때에 얼마나 많은 경우의 수를 따져야 하는지를 알아야 합니다. 한 번의 차례가 돌아올 때에, 한 쪽이 둘 수 있는 경우의 수가 n이라고 해 봅시다. 그러면, 컴퓨터가 한 수를 앞서 보고, 그 중 가장 좋은 수를 계산하기 위해서는 n 가지 수를 따져봐야 합니다. 여기까지 어렵지 않죠?

그러면 두 수를 보기 위해서는 어떨까요? 처음 한 수의 n 가지 경우에 대해, 각각에 대해 상대방 역시 n 가지 수를 둘 수 있기 때문에, 경우의 수는 n * n 가지 수가 됩니다.

그럼 세 수를 보기 위해서는 n * n * n, 즉 n의 3승인 n^3이 됩니다. k 개의 수를 앞서 보기 위해서는 n^k 만큼의 계산이 필요하게 되는 것이죠. 이 공식으로 대략적인 복잡도를 예상해 볼 수 있을 것입니다.



그러면, 이 공식을 이용하여, 바둑과 체스의 복잡도를 한 번 예상해 봅시다.

앞으로의 k 개의 수를 앞서 보는 것은 n^k 만큼의 계산이 필요하다고 했죠? k의 값은 조절하기에 달렸겠지만, 통일성을 부여하기 위해 두 게임 모두 10개의 수를 앞서 보는 것으로 생각하겠습니다. 즉 계산 복잡도는 n^10 입니다.


우선, 계산이 좀 더 쉬운 바둑부터.

바둑판은 19 * 19 = 361개의 칸이 있습니다. 그리고, 이 모든 칸에 바둑돌을 두는 것이 가능하죠. 물론, 이미 다른 돌이 존재하는 칸에는 다시 둘 수 없어 게임의 후반으로 갈수록 이 값이 줄어들겠지만, 일단 게임 초반으로 가정하겠습니다. 그러면 361^10 = 37,589,973,457,545,958,193,355,601 ~= 3.8 * 10^25 정도군요.

이게 어느 정도 큰 숫자인지 감이 오십니까? 참고로, 그 어렵다는 로또 1등 당첨 확률은 8,145,060 ~= 8 * 10^6 분의 1입니다. 로또 1등에 연속 4 번 당첨될 확률과 대략 비슷하네요. :)


그러면, 체스의 경우는 어떨까요?

체스의 경우, 8 * 8 넓이의 칸에, 한 쪽에는 총 16개의 말이 있습니다. 각각에 대해 움직일 수 있는 최대값을 한 번 따져 보도록 하죠. 말들은 다음과 같습니다.

우선, 8개의 폰(Pawn). 이들은 무조건 앞으로만 가고, 대각선 앞에 상대 말이 있을 경우 그들을 잡을 수 있습니다. 편의상, 이들의 움직임은 3이라고 하죠. 그러면 8 * 3 = 24.

2개의 루크(Rook). 이들은 가로/세로 일직선으로만 움직입니다. 완전히 오픈된 공간에서 그들이 갈 수 있는 칸 수는 가로 7, 세로 7입니다. 2 * (7 + 7) = 28.

2개의 나이트(Knight). 이들은 장기의 마와 같이, '날 일' 자 모양으로 움직입니다. 완전히 오픈된 공간에서 갈 수 있는 칸 수는 총 8개입니다. 2 * 8 = 16.

2개의 비숍(Bishop). 이들은 대각선으로만 움직이죠. 완전히 오픈된 공간을 생각해보면 최대 13칸으로 이동이 가능하다는 것을 알 수 있습니다. 2 * 13 = 26.

1개의 킹(King). 상하좌우대각선으로 1칸씩 이동 가능합니다. 8.

1개의 퀸(Queen). 퀸은 루크와 비숍의 자유도를 합친 이동을 하죠. 결국 14 + 13 = 27.

여기에서, 킹과 루크의 캐슬링(Castling) 움직임이나, 폰의 특수 공격인 앙 파상(En passant) 등은 계산에서 제외하기로 합니다. 아주 제한된 때에만 가능하기 때문이죠.

그러면, 이 값을 모두 더하면 129. 이것을 위의 식에 대입해 보면 129 ^ 10 = 1,276,136,419,117,121,619,201 ~= 1.3 * 10^21 입니다. 역시나 어마어마한 수죠.



"와아, 저런 엄청난 경우의 수를 다 계산해서 인간 챔피언을 이기다니, 역시 컴퓨터는 대단해!"라고 생각하고 계신가요? 하지만, 아마도 딥 프리츠(Deep Fritz)는 이런 무시무시한 계산을 다 하지는 않았을 겁니다. ^^ 왜냐고요? 시간이 너무 오래 걸리기 때문이죠.

걸리는 시간을 한 번 계산해 보도록 하죠. 어느 가상의 컴퓨터가 1초에 1경 = 10000조 개의 수를 계산할 수 있다고 가정해 봅시다. (물론 오늘날의 컴퓨터는 이 가상의 컴퓨터보다 성능이 훨씬 떨어집니다)

그러면 체스의 10개의 수를 내다보기 위해 필요한 시간은 약 1276136419 초 ~= 354482 시간 ~= 14770 일 ~= 40 년 입니다. 아하하. -_- (참고로, 같은 컴퓨터에서 바둑은 약 117만 년이 걸립니다)


그러면 딥 프리츠는 어떻게 된 것이냐고요? 아마도, 모든 경우의 수를 계산하지 않고도 최선의 수에 가까운 수를 찾을 수 있는 유사 알고리즘을 사용하였을 것으로 추측됩니다. 이러한 유사 알고리즘과, 과거 경기 데이터베이스 검색을 결합하여 사람으로서는 이기기 어려운 체스 실력을 갖출 수 있지 않았을까 추측해 봅니다.


체스의 모든 수를 계산/비교하여 최선의 수를 찾는 컴퓨터는 오늘날 사용하고 있는 컴퓨터의 구조로는 앞으로도 아마 나오기 힘들 것이라 생각합니다.

(뭔가 평소에 올리던 글과는 다른 분위기의 글이 되어버렸군요;;;)


* 올블로그 태그 : 딥 프리츠 , 체스 , 바둑