코드: 알파-베타 minimax

실행 결과를 보면 약 30배 빨라짐. 결과는 정확히 같고.

틱택토 빈 보드 minimax는 약 55만 노드를 봐. 알파-베타는 1.8만 노드만. 97%의 노드를 안 봐도 됨. 그런데 답은 똑같이 정확.

🔑 추가된 코드는 4줄

alpha = max(alpha, v)        # MAX 노드: 보장된 최소 갱신
if beta <= alpha: break       # 베타 컷: 더 안 봄

beta = min(beta, v)           # MIN 노드: 보장된 최대 갱신
if beta <= alpha: break       # 알파 컷: 더 안 봄

알고리즘의 본질은 완전 같아. 그저 "범위 추적 + 조건문 한 줄". 그런데 효과는 30배.

💡 이론적 상한 — sqrt(b^d)

이상적인 경우(수 순서가 완벽할 때) 알파-베타는 b^d 대신 b^(d/2) 노드만 봐. 사실상 분기 인자가 b → √b로 감소한 효과. 체스(b=35)에서는 √35 ≈ 6으로 감소.

이게 1990년대 컴퓨터 체스가 인간을 넘어선 비결 — 같은 시간에 깊이를 2배로 더 볼 수 있게 됨.

그런데 "수 순서가 완벽"이라는 게 핵심. 다음 페이지.

PYTHON

# 알파-베타 minimax. 기본 minimax에 α, β 추적과 가지치기 조건만 추가.
# 결과는 같고 속도만 빨라짐.

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

def initial_state(): return ([EMPTY]*9, X)

def possible_moves(state):
    board, turn = state
    return [((board[:i]+[turn]+board[i+1:], O if turn==X else X), i)
            for i in range(9) if board[i] == EMPTY]

def is_terminal(state):
    board, _ = state
    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


# === 기본 Minimax (비교용) ===
nodes_visited_basic = 0

def minimax(state, is_max):
    global nodes_visited_basic
    nodes_visited_basic += 1
    terminal, winner = is_terminal(state)
    if terminal:
        return 1 if winner == X else (-1 if winner == O else 0)
    if is_max:
        return max(minimax(c, False) for c, _ in possible_moves(state))
    else:
        return min(minimax(c, True) for c, _ in possible_moves(state))


# === 알파-베타 Minimax ===
nodes_visited_ab = 0

def minimax_ab(state, is_max, alpha=-float('inf'), beta=float('inf')):
    global nodes_visited_ab
    nodes_visited_ab += 1
    terminal, winner = is_terminal(state)
    if terminal:
        return 1 if winner == X else (-1 if winner == O else 0)

    if is_max:
        v = -float('inf')
        for child, _ in possible_moves(state):
            v = max(v, minimax_ab(child, False, alpha, beta))
            alpha = max(alpha, v)
            if beta <= alpha:  # 🔑 베타 컷 (MIN이 안 보내줄 가지)
                break
        return v
    else:
        v = float('inf')
        for child, _ in possible_moves(state):
            v = min(v, minimax_ab(child, True, alpha, beta))
            beta = min(beta, v)
            if beta <= alpha:  # 🔑 알파 컷 (MAX가 안 보내줄 가지)
                break
        return v


# === 비교 ===
state = initial_state()

print("=== 기본 Minimax (빈 보드 평가) ===")
nodes_visited_basic = 0
score = minimax(state, True)
print(f"점수: {score}, 노드 방문 수: {nodes_visited_basic:,}")

print()
print("=== 알파-베타 (빈 보드 평가) ===")
nodes_visited_ab = 0
score_ab = minimax_ab(state, True)
print(f"점수: {score_ab}, 노드 방문 수: {nodes_visited_ab:,}")

print()
ratio = nodes_visited_basic / nodes_visited_ab
print(f"=== 가지치기 효과 ===")
print(f"  방문 노드 감소: {nodes_visited_basic:,} → {nodes_visited_ab:,}")
print(f"  속도 향상:     {ratio:.1f}배")
print(f"  결과 동일:     {score == score_ab}")

출력

기대 출력:

=== 기본 Minimax (빈 보드 평가) ===
점수: 0, 노드 방문 수: 549,946

=== 알파-베타 (빈 보드 평가) ===
점수: 0, 노드 방문 수: 18,297

=== 가지치기 효과 ===
  방문 노드 감소: 549,946 → 18,297
  속도 향상:     30.1배
  결과 동일:     True

← 이전 가지치기 단계별로 — 시각화 다음 → 수 순서 — 가지치기 효율의 비밀