게임을 트리로 보다
👋 PART 2 시작 — 알고리즘 시대로
PART 1에서는 바둑 규칙을 코드로 만들었다. 이제부터는 진짜 알고리즘이야. "어디에 둘 것인가"를 결정하는 첫 번째 시도, 탐색(Search)으로 시작해.
두 사람이 바둑을 둔다고 생각해봐. 흑이 먼저 둘 자리를 결정해야 해. 어떻게 결정할까?
똑똑한 사람이라면 이렇게 생각하지:
- 내가 A에 두면 → 상대는 B나 C에 둘 거고 → 그 다음 나는...
- 내가 D에 두면 → 상대는 E나 F에 둘 거고 → 그 다음 나는...
- ... 그래서 결과적으로 가장 좋은 선택은 A.
이게 미리 읽기(reading)야. 바둑 고수들은 머릿속에서 10수, 20수, 30수까지 미리 본다고 해. 컴퓨터도 똑같이 할 수 있어. 단, 컴퓨터의 무기는 정확함과 속도.
이걸 자료구조로 표현하면 자연스럽게 트리(Tree)가 돼. 모든 가능한 미래가 나뭇가지처럼 갈라지지.
이 챕터:
- 게임 트리의 구조 — 노드, 간선, 깊이, 분기 인자
- 틱택토의 완전 트리 시각화
- 코드: 게임 상태를 노드로, DFS로 트리 탐색
- 왜 바둑은 트리가 어마어마하게 큰가