바둑의 트리는 얼마나 큰가
틱택토는 깊이 9, 분기 평균 4 정도. 다 볼 수 있어.
바둑은? 보드별 평균 분기 인자 b 와 평균 게임 길이 d:
| 게임 | 분기 b | 깊이 d | b^d (대략) | 실제 분석 |
|---|---|---|---|---|
| 틱택토 | ~4 | 9 | 10^4 | ✅ 완전 풀림 |
| 체커 | ~10 | ~50 | 10^31 | ✅ 풀림 (2007) |
| 체스 | ~35 | ~80 | 10^120 | ⚡ Stockfish/AlphaZero |
| 바둑 5x5 | ~20 | ~25 | 10^25 | ✅ 풀림 (2002) |
| 바둑 7x7 | ~40 | ~50 | 10^60 | ⚠️ 미풀림 |
| 바둑 19x19 | ~250 | ~150 | 10^360 | ❌ 영원히 못 풀 |
⚠️ 10^360이라는 수
참고로 우주에 있는 원자 수는 약 10^80. 우주의 나이는 10^17초. 매 초 우주 원자 하나씩 노드를 세도 우주 나이 동안 셀 수 있는 건 10^97개. 우리가 봐야 할 10^360에 한참 못 미쳐.
요점: 완전 분석은 불가능하다. 이게 PART 2 모든 알고리즘의 시작점이야.
그래서 우리가 해야 할 일은 둘 중 하나:
- 깊이를 제한한다 — 끝까지 안 가고 적당히 보고, 어림짐작(heuristic)으로 점수 매김
- 가지치기한다 — 명백히 나쁜 가지는 안 봄 (알파-베타)
둘 다 다음 챕터들에서 다룸. 그래도 바둑은 부족해서 PART 3에서 더 똑똑한 방법(MCTS)이 나오고, PART 4에서 진짜 끝판왕(신경망)이 나와.
다음 챕터: Minimax — 컴퓨터가 미래를 읽는 가장 고전적인 방법.