트리의 해부 — 노드, 간선, 깊이, 분기 인자
위 그림이 가장 작은 게임 트리야. 네 가지 핵심 용어:
📖 트리 용어
- 노드(node) — 게임 상태 하나. 위에서는 ▲ ▼ ● 모양들.
- 루트(root) — 트리 맨 위, 현재 보드 상태.
- 간선(edge) — 한 수를 두는 동작. 부모와 자식을 연결하는 선.
- 깊이(depth, d) — 루트에서 몇 수 진행됐는가. 위 트리는 깊이 2.
- 분기 인자(branching factor, b) — 각 노드에서 갈 수 있는 수의 개수. 위에서는 b=3.
- 리프(leaf) — 더 갈 곳이 없는 끝 노드. 게임 종료 또는 우리가 정한 깊이 한계.
이 작은 트리에서 노드는 총 1 + 3 + 9 = 13개. 깊이 2까지 가는 데 13 노드.
⚠️ 깊이 d, 분기 b면 총 노드 수는 약 b^d
깊이가 1 늘 때마다 노드 수가 b배. 그래서 트리는 지수적으로 폭발해. 이게 PART 2 후반의 핵심 키워드 — 탐색 공간 폭발.
예시:
- 틱택토: 평균 b ≈ 4, 최대 깊이 9 → 약 26만 노드 (다 볼 수 있음)
- 체스: 평균 b ≈ 35, 한 게임 평균 80수 → 10^120 노드 (못 봄)
- 바둑 19x19: 평균 b ≈ 250 → 10^170 (절대 못 봄)
먼저 가장 작은 게임 — 틱택토부터 트리를 그려보자.
컴포넌트 로딩 중...