체스에는 약 10¹²⁰개의 게임이 있고 바둑에는 약 10³⁶⁰개의 경우가 있다는 표현을 자주 봅니다. 두 수는 모두 게임이 얼마나 큰지를 보여 주지만 같은 대상을 정확히 센 값은 아닙니다. 10¹²⁰은 클로드 섀넌이 체스의 게임 트리 규모를 설명하기 위해 제시한 유명한 추정이고, 10³⁶⁰도 바둑의 평균 분기 수와 게임 길이를 바탕으로 한 게임 트리 추정입니다.
한편 19×19 바둑판의 합법적인 정적 위치 수는 존 트롬프의 계산으로 약 2.08168199382×10¹⁷⁰입니다. 이것은 10³⁶⁰과 모순되지 않습니다. 하나는 한 시점의 가능한 판 상태를 세고, 다른 하나는 처음부터 끝까지 이어지는 서로 다른 진행 경로의 규모를 추정하기 때문입니다.
상태 공간은 ‘가능한 장면의 수’, 게임 트리는 ‘그 장면들로 이어지는 가능한 이야기의 수’입니다.
게임 복잡도는 하나의 숫자가 아니다
| 지표 | 무엇을 세나 | 주의할 점 |
|---|---|---|
| 상태 공간 복잡도 | 규칙상 가능한 서로 다른 위치 | 같은 위치에 여러 경로로 도달할 수 있음 |
| 게임 트리 복잡도 | 시작부터 종료까지 가능한 게임 진행 | 규칙과 종료 조건에 따라 달라짐 |
| 분기 계수 | 한 위치에서 가능한 다음 수의 개수 | 경기 중 계속 변함 |
| 해결 복잡도 | 완벽한 결과를 계산하는 데 필요한 자원 | 알고리즘과 목표에 따라 달라짐 |
체스판의 한 위치를 두 장의 사진처럼 비교하면 배치가 같을 수 있습니다. 하지만 그 위치에 이른 수순은 여러 가지일 수 있습니다. 반복, 캐슬링 권리, 앙파상 가능 여부처럼 과거 수순이 합법성에 영향을 주는 정보까지 상태에 포함해야 하는 경우도 있습니다. 따라서 단순한 말 배치 수와 규칙상 완전한 게임 상태 수 역시 구분해야 합니다.
섀넌 수 10¹²⁰은 어떻게 나온 추정인가
클로드 섀넌은 1950년 논문 ‘Programming a Computer for Playing Chess’에서 컴퓨터가 체스를 두는 문제를 다뤘습니다. 그는 전형적인 위치에서 약 30개의 합법 수가 있고, 백과 흑이 한 번씩 두는 한 쌍의 수에는 대략 10³개의 선택이 생긴다고 보았습니다. 전형적인 게임을 약 40쌍의 수로 잡으면 (10³)⁴⁰=10¹²⁰입니다.
체스 게임 트리 추정: 약 10³ 선택/한 쌍의 수 × 40쌍 → (10³)⁴⁰=10¹²⁰
이는 모든 합법 체스 게임을 정확히 열거한 결과가 아닙니다. 평균 분기 계수와 대표적인 게임 길이를 단순화해 규모를 보여 주는 계산입니다. 실제 분기 수는 체크 상황, 말의 수, 승진 가능성 등에 따라 바뀌고 게임 길이도 일정하지 않습니다. 오늘날 ‘섀넌 수’라는 이름은 보통 이 10¹²⁰ 규모의 게임 트리 추정을 가리킵니다.
왜 bᵈ가 게임 트리의 기본 계산인가
매 단계마다 선택지가 평균 b개이고 게임이 d단계 이어진다고 단순화하면 끝까지 이어지는 경로 수는 대략 bᵈ입니다. 첫 단계에 b개, 각 가지에서 다음 단계에 다시 b개가 뻗으므로 깊이가 하나 늘 때마다 b를 곱합니다. 정확한 트리에서는 각 노드의 분기 수가 다르지만 규모 비교에는 평균 유효 분기 계수를 씁니다.
| 평균 분기 b | 깊이 d | 단순 추정 bᵈ |
|---|---|---|
| 10 | 20 | 10²⁰ |
| 30 | 80 | 약 1.48×10¹¹⁸ |
| 250 | 150 | 약 10³⁵⁹.7 |
바둑 예시의 250¹⁵⁰에 상용로그를 취하면 150log₁₀250≈359.69이므로 약 10³⁶⁰입니다. 이 계산도 실제 모든 게임을 하나씩 세지 않습니다. 대표적인 분기 계수 250과 게임 길이 150을 놓은 추정입니다.
바둑 10³⁶⁰은 상태 공간이 아니라 게임 트리 추정
19×19 바둑판에는 361개의 교차점이 있습니다. 초반에는 대부분의 빈 점에 둘 수 있어 체스보다 분기 수가 큽니다. 빅터 앨리스가 사용한 대표적 추정에서는 전문가 게임의 길이를 약 150수, 평균 선택 수를 약 250으로 보아 250¹⁵⁰≈10³⁶⁰이라는 게임 트리 규모를 얻습니다.
이 수를 ‘바둑판 상태 수’라고 부르면 잘못입니다. 정적 위치 하나가 여러 수순으로 만들어질 수 있고, 패 규칙과 반복 금지 규칙은 가능한 진행을 제한합니다. 게임 트리에서는 수순이 다르면 마지막 판이 같더라도 다른 경로로 셀 수 있습니다.
합법적인 바둑 위치 약 2.08×10¹⁷⁰
각 교차점이 빈칸, 흑돌, 백돌 가운데 하나라고만 생각하면 3³⁶¹≈1.74×10¹⁷²개의 색칠이 나옵니다. 그러나 잡힌 돌 없이 숨을 쉴 수 없는 돌무리처럼 규칙상 합법적인 판이 아닌 색칠도 포함됩니다. 따라서 3³⁶¹은 단순한 상한 성격의 값이지 합법 위치의 정확한 수가 아닙니다.
존 트롬프는 연결된 돌무리와 빈 교차점의 조건을 반영해 19×19 바둑의 합법 위치 수를 약 2.08168199382×10¹⁷⁰으로 계산했습니다. 이 수는 여전히 엄청나지만 10³⁶⁰보다 훨씬 작습니다. 상태 하나를 여러 순서로 방문할 수 있으므로 게임 경로 수가 상태 수보다 훨씬 커지는 것은 자연스럽습니다.
체스 상태 공간과 섀넌 수를 섞지 말아야 한다
섀넌의 논문에는 약 10⁴³이라는 체스 위치 규모의 추정도 등장하지만, 10¹²⁰은 전체 게임 트리의 규모를 보여 주는 값입니다. 이후 연구에서는 합법 위치를 세는 방법과 상태 정의에 따라 다른 추정이 제시되었습니다. 따라서 10⁴³이나 10⁴⁷ 같은 값을 ‘정확한 체스 상태 수’라고 단정하기보다 어떤 정의와 추정법을 썼는지 밝혀야 합니다.
특히 체스의 동일한 말 배치라도 어느 쪽 차례인지, 캐슬링 권리가 남아 있는지, 앙파상 포획이 가능한지에 따라 다른 게임 상태가 됩니다. 위치의 정의가 달라지면 개수도 달라집니다. 반면 섀넌 수는 정확한 상태 열거가 아니라 완전 탐색이 얼마나 비현실적인지를 설명하는 보수적인 규모 추정입니다.
모든 경우를 찾지 않아도 좋은 수를 둘 수 있다
게임 트리가 크다고 해서 매 수마다 끝까지 모든 경로를 조사해야 하는 것은 아닙니다. 미니맥스 탐색은 양쪽이 최선으로 둔다고 가정해 선택을 평가하고, 알파–베타 가지치기는 최종 선택에 영향을 주지 않는 가지를 건너뜁니다. 좋은 수를 먼저 검사할수록 더 많은 가지를 자를 수 있습니다.
현대 게임 프로그램은 제한된 깊이의 탐색, 위치 평가 함수, 반복 심화, 전이표, 몬테카를로 트리 탐색, 학습된 정책과 가치 함수 등을 사용합니다. 방법은 게임마다 다릅니다. 바둑에서 널리 쓰인 몬테카를로 트리 탐색은 모든 수순을 동일하게 펼치지 않고 표본과 평가를 통해 유망한 가지에 계산을 집중합니다.
전이표가 상태 공간과 게임 트리의 중복을 줄인다
서로 다른 수순이 같은 상태에 도달하는 현상을 전이라고 합니다. 게임 트리를 그대로 펼치면 같은 상태 아래의 계산을 여러 번 반복할 수 있습니다. 전이표는 이미 평가한 상태를 해시 키와 함께 저장해 중복 계산을 줄입니다. 이것이 게임 경로 수와 서로 다른 상태 수를 구분하는 실용적인 이유이기도 합니다.
다만 전이표가 게임 전체를 작게 만드는 것은 아닙니다. 저장 공간이 제한되어 있고, 충돌 처리와 상태 식별이 필요하며, 과거 정보가 규칙에 영향을 주면 키에 그 정보도 포함해야 합니다. 그래도 같은 위치를 다시 만나는 게임에서는 탐색 효율을 크게 높일 수 있습니다.
큰 숫자가 곧 계산 난이도의 완전한 순위는 아니다
게임 트리 추정이 더 크다고 해서 모든 의미에서 반드시 더 어렵다고 말할 수는 없습니다. 규칙 구조, 대칭성, 가지치기 가능성, 평가 함수의 정확도, 승패를 증명하는 데 필요한 깊이가 모두 영향을 줍니다. 상태 공간이 크더라도 강한 규칙성이 있으면 압축할 수 있고, 작은 게임도 최적 전략의 증명이 까다로울 수 있습니다.
또한 ‘게임을 잘 둔다’와 ‘게임을 해결한다’는 다릅니다. 강한 프로그램은 대부분의 사람보다 잘 둘 수 있지만, 모든 합법 상태에서 최선 결과를 증명한 것은 아닐 수 있습니다. 약하게 해결했다는 말은 초기 상태에서 완벽한 결과를 알았다는 뜻이고, 강하게 해결했다는 말은 모든 도달 가능 상태에서 최선 수를 안다는 더 강한 뜻으로 쓰입니다.
정확한 수와 추정치를 구분하는 읽기법
- 숫자가 위치 수인지 전체 수순 수인지 확인합니다.
- 정확한 열거인지 평균 분기 계수에 기반한 추정인지 확인합니다.
- 보드 크기와 반복·무승부·패 규칙을 확인합니다.
- 한 수를 한 단계로 세는지 백·흑 한 쌍을 한 단계로 세는지 확인합니다.
- 상한, 하한, 대표값 가운데 무엇인지 확인합니다.
10¹²⁰과 10³⁶⁰은 유효 자릿수까지 정확한 계측값이 아닙니다. 지수의 규모가 핵심인 추정입니다. 반면 약 2.08168199382×10¹⁷⁰이라는 바둑 합법 위치 수는 특정한 합법성 정의에 따라 계산한 정밀한 열거 결과입니다. 숫자 표기만 보고 같은 종류의 값으로 다루면 안 됩니다.
네트워크 문제와 게임 트리의 공통점
게임 트리는 위치를 꼭짓점으로, 합법적인 수를 방향 있는 변으로 표현한 그래프입니다. 링크를 따라 이동하는 확률의 정상분포를 구하는 구글 페이지랭크의 마르코프 전이 계산도 웹을 그래프로 바꾼다는 점에서는 닮았습니다. 다만 페이지랭크는 장기 방문 확률을 구하고, 게임 탐색은 경쟁하는 선택에서 최선의 결과를 구합니다.
모든 다리를 한 번씩 지나는 쾨니히스베르크 다리 문제의 오일러 경로 판정은 변의 사용 여부가 핵심입니다. 게임 트리에서는 같은 상태에서 뻗는 선택지와 깊이가 핵심입니다. 같은 그래프 표현도 질문에 따라 계산법이 달라집니다.
게임 복잡도 FAQ
체스의 경우의 수는 정확히 10¹²⁰개인가요?
아닙니다. 10¹²⁰은 섀넌이 평균 선택 수와 전형적인 게임 길이로 제시한 게임 트리 규모의 추정입니다. 모든 합법 게임을 정확히 센 값이 아닙니다.
바둑의 경우의 수는 10¹⁷⁰인가요, 10³⁶⁰인가요?
둘은 다른 대상을 말합니다. 약 2.08×10¹⁷⁰은 19×19 바둑의 합법적인 정적 위치 수이고, 약 10³⁶⁰은 대표적인 분기 계수와 게임 길이로 추정한 게임 트리 규모입니다.
상태 공간보다 게임 트리가 큰 이유는 무엇인가요?
같은 상태에 서로 다른 수순으로 도달할 수 있고, 한 게임은 수많은 상태가 이어진 경로이기 때문입니다. 상태의 목록과 상태를 잇는 모든 가능한 순서의 목록은 크기가 다릅니다.
핵심 정리
섀넌 수 약 10¹²⁰은 체스의 정확한 위치 수가 아니라 평균 분기와 게임 길이로 계산한 게임 트리 추정입니다. 바둑의 약 10³⁶⁰도 같은 종류의 대표적 게임 트리 추정이며, 약 2.08168×10¹⁷⁰이라는 합법 위치 수와 구분해야 합니다.
기본 계산은 평균 분기 계수 b와 깊이 d를 이용한 bᵈ입니다. 이 수들은 완전 탐색의 폭발적 증가를 보여 주지만 게임 난이도를 하나의 숫자로 완전히 설명하지는 않습니다. 숫자를 인용할 때는 상태 공간인지 게임 트리인지, 정확한 열거인지 추정인지, 어떤 규칙과 보드 크기를 전제로 하는지 함께 적어야 합니다.