틱택토의 완전 트리

틱택토(3x3 OX 게임)는 게임 트리가 작아서 처음부터 끝까지 모든 가능성을 다 그릴 수 있어. 직접 보자.

첫 수에서 X는 9자리 중 어디든 두지. 9개의 자식. 그 후 O는 남은 8자리 중 하나. 각 X 노드마다 8개의 자식. 그 다음 X는 7개... 이런 식.

초기 상태 (X 차례)

X가 가운데 (1,1) 둠

가운데 두는 게 첫 수로 가장 강해 (대각선+가로+세로 다 만들 수 있어서). 이제 O는 8가지 선택. 사각형(코너)에 두는 게 보통 좋아:

O가 (0,0)

O가 (0,1) — 약한 선택

📊 틱택토 트리 규모

각 단계 분기를 다 곱하면: 9 × 8 × 7 × ... × 1 = 9! = 362,880가지 게임. (대칭으로 줄이면 더 적음.)

이 정도면 현대 컴퓨터로 1초 안에 다 분석 가능. 그래서 틱택토는 완전히 풀린 게임 — 두 사람이 최선을 두면 무승부.

1950년대 컴퓨터로도 틱택토를 풀 수 있었어. 트리가 작거든. 핵심은 모든 노드의 결과를 계산해서 위로 전파하는 것. 이게 다음 챕터의 Minimax 알고리즘이야.

그 전에 먼저 — 트리를 코드로 어떻게 표현하지?