코드: Minimax 재귀

실행하는 데 몇 초 걸려. 컴퓨터가 미래 모든 게임을 다 보고 있는 거.

결과를 보면 모든 자리가 0점이야. 무슨 의미일까?

🎯 결과 해석 — "틱택토는 무승부 게임"

점수 0은 무승부야. 어떤 자리에 두더라도, 두 사람이 최선을 두면 결과는 무승부. 이게 1950년대 이미 알려진 사실이고, 우리 코드가 이를 직접 증명한 거.

그래서 어린 시절 친구랑 틱택토 두면서 "맨날 무승부"라고 느낀 게 진실 — 두 사람이 진지하게 두면 절대 결판 안 남.

코드 핵심은 진짜 10줄:

def minimax(state, is_max):
    if 게임끝: return 점수
    if is_max:
        return max(자식들의 minimax 값)
    else:
        return min(자식들의 minimax 값)

💡 재귀의 우아함

이 짧은 함수가 트리 전체를 자동으로 훑어. 깊이가 9든 100이든 함수는 똑같이 동작. 컴퓨터 과학에서 가장 우아한 알고리즘 중 하나야.

틱택토는 다 볼 수 있어서 무패가 가능. 그런데 더 복잡한 게임에서는 끝까지 못 봐. 깊이 제한이 필요하지.

PYTHON

# Minimax 재귀. 의외로 짧다 — 10줄.
# 핵심: 현재 노드가 MAX면 max, MIN면 min. 자식들 점수 재귀로 계산.

def minimax(state, is_max):
    """현재 상태의 minimax 값.
    state: 게임 상태 (보드 + 차례)
    is_max: True면 내 차례(MAX), False면 상대(MIN)
    반환: 이 상태의 점수 (-1, 0, +1)"""

    # 종료: 게임 끝났으면 점수 그대로
    terminal, winner = is_terminal(state)
    if terminal:
        if winner == X: return 1
        if winner == O: return -1
        return 0  # draw

    # MAX 차례: 자식들 중 최대값
    if is_max:
        best = -float('inf')
        for child, _ in possible_moves(state):
            v = minimax(child, False)  # 다음은 MIN 차례
            best = max(best, v)
        return best
    # MIN 차례: 자식들 중 최소값
    else:
        best = float('inf')
        for child, _ in possible_moves(state):
            v = minimax(child, True)  # 다음은 MAX 차례
            best = min(best, v)
        return best


# === 틱택토 헬퍼 (Ch 1과 동일) ===
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


# === 첫 수 분석 ===
print("=== 빈 보드에서 첫 수 후보들의 minimax 점수 ===")
print("(X가 두는 입장 — MAX. O는 MIN.)")
print()

state = initial_state()
results = []
for child, pos in possible_moves(state):
    score = minimax(child, False)  # 다음은 O 차례 = MIN
    results.append((pos, score))
    r, c = pos // 3, pos % 3
    print(f"  자리 ({r},{c}): minimax = {score:+d}")

print()
best = max(results, key=lambda x: x[1])
print(f"최선의 첫 수: 자리 {best[0]} (점수 {best[1]:+d})")

출력

기대 출력:

=== 빈 보드에서 첫 수 후보들의 minimax 점수 ===
(X가 두는 입장 — MAX. O는 MIN.)

  자리 (0,0): minimax = +0
  자리 (0,1): minimax = +0
  자리 (0,2): minimax = +0
  자리 (1,0): minimax = +0
  자리 (1,1): minimax = +0
  자리 (1,2): minimax = +0
  자리 (2,0): minimax = +0
  자리 (2,1): minimax = +0
  자리 (2,2): minimax = +0

최선의 첫 수: 자리 0 (점수 +0)

← 이전 점수 전파 — Leaf에서 Root로 다음 → 깊이 제한 + Heuristic — 끝까지 못 갈 때