코드: 게임 상태 노드 + DFS

핵심 세 함수:

possible_moves(state) — 현재 상태에서 가능한 모든 다음 상태 (자식들)
is_terminal(state) — 게임 끝났나? 끝났으면 승자도 알려줌
count_nodes(state, depth) — DFS로 트리 노드 개수 세기 (재귀!)

실행 결과를 보면 지수 폭발이 한눈에:

깊이 1: 10 노드
깊이 5: 16,114 노드 (1600배)
깊이 9: 887,338 노드 (90만 개) — 틱택토 전체 분석에 가까움

💡 DFS 재귀 패턴

count_nodes는 자기 자신을 호출. "현재 노드 1개 + 모든 자식들 노드 수 합". 이 단순한 재귀가 트리 전체를 훑어. 다음 챕터의 minimax도 똑같은 재귀 패턴이야 — 단지 "노드 세기" 대신 "점수 계산".

틱택토는 90만 노드면 끝. 1초 안에 다 볼 수 있어. 그래서 틱택토 AI는 무패가 가능해. 다음 페이지에서 바둑으로 가면 이야기가 완전히 달라지지.

PYTHON

# 게임 트리를 코드로 표현. 핵심은 두 가지:
# 1) 게임 상태(노드)를 표현하는 방법
# 2) 그 상태에서 가능한 다음 상태들(자식)을 만드는 방법
#
# 우리는 틱택토로 시작. 보드 = 9칸 리스트, 'X'/'O'/' '.

EMPTY = ' '
X = 'X'
O = 'O'

def initial_state():
    """빈 보드 + 누구 차례"""
    return ([EMPTY] * 9, X)  # X가 항상 선

def show_board(board):
    """보드를 줄로 출력"""
    for r in range(3):
        print(' | '.join(board[r*3:(r+1)*3]))
        if r < 2: print('-' * 9)

def possible_moves(state):
    """현재 상태에서 가능한 다음 상태들 반환"""
    board, turn = state
    children = []
    for i in range(9):
        if board[i] == EMPTY:
            new_board = board[:]
            new_board[i] = turn
            next_turn = O if turn == X else X
            children.append(((new_board, next_turn), i))  # (다음상태, 둔자리)
    return children

def is_terminal(state):
    """게임 끝났는가? 끝났으면 승자도 반환"""
    board, _ = state
    # 가로/세로/대각선 8줄 체크
    lines = [
        (0,1,2),(3,4,5),(6,7,8),   # 가로
        (0,3,6),(1,4,7),(2,5,8),   # 세로
        (0,4,8),(2,4,6),           # 대각선
    ]
    for a, b, c in lines:
        if board[a] != EMPTY and board[a] == board[b] == board[c]:
            return True, board[a]
    if EMPTY not in board:
        return True, 'draw'
    return False, None


# === DFS로 트리 탐색 (몇 노드인지 세기) ===
def count_nodes(state, depth):
    """깊이 depth까지 탐색하면서 노드 개수 반환"""
    if depth == 0:
        return 1
    terminal, _ = is_terminal(state)
    if terminal:
        return 1
    total = 1  # 현재 노드
    for child, _ in possible_moves(state):
        total += count_nodes(child, depth - 1)
    return total


# === 테스트 ===
print("=== 초기 상태 ===")
state = initial_state()
show_board(state[0])

print()
print("=== 첫 수 후보들 (9개) ===")
for child_state, pos in possible_moves(state):
    print(f"  {pos}자리에 X 둠 → 다음 차례: {child_state[1]}")

print()
print("=== 깊이별 트리 크기 ===")
for d in range(1, 10):
    n = count_nodes(initial_state(), d)
    print(f"  깊이 {d}: {n:>7,} 노드")

출력

기대 출력:

=== 초기 상태 ===
  |   |  
---------
  |   |  
---------
  |   |  

=== 첫 수 후보들 (9개) ===
  0자리에 X 둠 → 다음 차례: O
  1자리에 X 둠 → 다음 차례: O
  2자리에 X 둠 → 다음 차례: O
  3자리에 X 둠 → 다음 차례: O
  4자리에 X 둠 → 다음 차례: O
  5자리에 X 둠 → 다음 차례: O
  6자리에 X 둠 → 다음 차례: O
  7자리에 X 둠 → 다음 차례: O
  8자리에 X 둠 → 다음 차례: O

=== 깊이별 트리 크기 ===
  깊이 1:      10 노드
  깊이 2:      82 노드
  깊이 3:     586 노드
  깊이 4:   3,610 노드
  깊이 5:  18,730 노드
  깊이 6:  73,450 노드
  깊이 7: 221,626 노드
  깊이 8: 422,074 노드
  깊이 9: 549,946 노드

← 이전 틱택토의 완전 트리 다음 → 바둑의 트리는 얼마나 큰가