분기 인자 b — 왜 그렇게 큰가
각 게임의 평균 분기 인자 b 를 다시 정리:
| 게임 | 평균 b | 왜 그런가 |
|---|---|---|
| 틱택토 | ~4 | 9칸이지만 후반엔 자리 많이 채워짐 |
| 체커 | ~10 | 각 말이 1~2칸씩만 움직임 |
| 체스 | ~35 | 16개 기물 × 평균 2~3가지 이동 |
| 바둑 9x9 | ~50 | 빈 자리 어디든 가능 (81칸 중 빈 자리) |
| 바둑 19x19 | ~250 | 361칸 중 빈 자리 거의 다 가능 |
🔑 바둑의 분기 인자가 큰 이유
두 가지 본질적 차이:
- 모든 빈 자리에 둘 수 있음. 체스는 기물이 정해진 움직임만 하지만, 바둑은 어디든 OK.
- 보드가 크다. 19×19 = 361칸. 빈 자리 거의 다 합법.
두 요소가 곱해져서 분기 인자가 250 안팎. 체스의 7배.
b가 7배면 같은 깊이에서 노드는 7^d 배 더 많아. 깊이 5면 16,807배. 깊이 10이면 2.8억 배.
이게 컴퓨터 바둑의 핵심 장애였어. 같은 시간에 체스는 깊이 15-20을 보는데, 바둑은 깊이 5-7 정도밖에 못 봄. 그것도 알파-베타 적용해야 그 정도.