7x7 minimax 실전 시도

실측 결과를 보면:

깊이 4까지는 0.02초 미만. 노드 수 7,006개
알파-베타 효과가 좋아서 §3의 추정(~1,225)보다는 약간 많지만 여전히 매우 효율적
그러나 깊이 5는 노드가 35배쯤 늘어 수 초 예상
깊이 6~7은 사용 가능 시간 밖

⚠️ 더 심각한 문제: 최선 수가 (0,0)?

출력을 보면 minimax가 매번 "최선 수는 (0,0)"이라고 추천. 이게 진짜 좋은 수일까?

아니에요. (0,0)은 코너로, 바둑에서는 매우 약한 자리. 사람이라면 (3,3) 같은 중앙 화점을 선택할 거. 그런데 우리 minimax는 "왼쪽 위부터 시도해서 동점이면 안 바꿈" 이라 (0,0)이 항상 선택됨.

이게 나쁜 평가 함수의 직접적 결과: 모든 자리가 같은 점수로 평가되니까 알고리즘이 정답을 못 골라.

📖 두 가지 실패가 동시에 발생

속도 실패: 깊이 5도 빠듯. 깊이 부족하니 미래 시야 짧음.
평가 실패: 돌 수 차이로는 위치의 강약을 모름. 알고리즘이 임의의 자리에 둠.

둘 중 하나만 해결되면 다른 하나가 발목 잡음. 둘 다 동시에 해결해야 함.

💡 어떻게 개선할 수 있나

더 좋은 평가 함수 — Bouzy의 영향 모델, GnuGo의 영역 분석 등. 10년의 노력으로 사람 9급 수준 도달.
더 효율적인 탐색 — 모든 수를 보지 않고 중요한 수만. 이게 다음 PART의 MCTS.
학습된 평가 함수 — 사람도 못 만든 좋은 평가를 데이터에서 학습. PART 4의 신경망.

이 챕터의 핵심 메시지: minimax + 알파-베타는 바둑에 부족하다. 직접 코드로 측정했어. 추측이 아니라 사실.

PYTHON

# 7x7 바둑에 진짜 minimax 적용.
# 단순화를 위해 자살수/패 무시, 평가 함수는 돌 수 차이.
# 시간이 얼마나 걸리는지 본다.

import time

EMPTY, BLACK, WHITE = 0, 1, 2
SIZE = 7

def make_board():
    return [[EMPTY]*SIZE for _ in range(SIZE)]

def copy_board(b):
    return [row[:] for row in b]

def possible_moves(board):
    """빈 자리 (단순화)"""
    return [(r, c) for r in range(SIZE) for c in range(SIZE) if board[r][c] == EMPTY]

def evaluate(board, perspective):
    """돌 수 차이 (perspective 기준)"""
    black = sum(row.count(BLACK) for row in board)
    white = sum(row.count(WHITE) for row in board)
    if perspective == BLACK:
        return black - white
    return white - black

def is_terminal(board):
    """단순화: 일정 수 이상이면 종료"""
    filled = sum(1 for row in board for v in row if v != EMPTY)
    return filled >= SIZE*SIZE - 5  # 거의 다 차면 종료


# === 알파-베타 Minimax (간단 버전, 진짜 따냄/자살수 무시) ===
nodes = 0

def minimax_ab(board, depth, alpha, beta, is_max, turn):
    global nodes
    nodes += 1

    if depth == 0 or is_terminal(board):
        return evaluate(board, BLACK), None

    opposite = WHITE if turn == BLACK else BLACK
    best_move = None

    if is_max:
        v = -float('inf')
        for r, c in possible_moves(board):
            board[r][c] = turn
            score, _ = minimax_ab(board, depth-1, alpha, beta, False, opposite)
            board[r][c] = EMPTY
            if score > v:
                v, best_move = score, (r, c)
            alpha = max(alpha, v)
            if beta <= alpha: break
        return v, best_move
    else:
        v = float('inf')
        for r, c in possible_moves(board):
            board[r][c] = turn
            score, _ = minimax_ab(board, depth-1, alpha, beta, True, opposite)
            board[r][c] = EMPTY
            if score < v:
                v, best_move = score, (r, c)
            beta = min(beta, v)
            if beta <= alpha: break
        return v, best_move


# === 깊이별 시간 측정 (빈 보드, 흑 차례) ===
print("=== 7x7 빈 보드, 흑이 첫 수 결정. 깊이별 시간 ===\n")
print(f"{'깊이':>5} {'시간':>10} {'노드':>15} {'최선 수':>12} {'점수':>8}")
print("-" * 60)

for d in range(1, 5):
    board = make_board()
    nodes = 0
    start = time.time()
    score, move = minimax_ab(board, d, -float('inf'), float('inf'), True, BLACK)
    elapsed = time.time() - start
    print(f"{d:>5} {elapsed:>9.2f}s {nodes:>15,} {str(move):>12} {score:>+8}")

print()
print("=== 깊이 5 도전? ===")
print("(주의: 시간이 매우 오래 걸릴 수 있음. 코드 수정해서 d=5 시도해보세요.)")
print()
print("=== 결론 ===")
print("• 7x7 빈 보드 깊이 4도 수십 초")
print("• 깊이 5 이상은 분 단위. 깊이 7~8 보려면 시간이 폭발")
print("• 19x19에서는 깊이 4도 며칠")

출력

기대 출력:

=== 7x7 빈 보드, 흑이 첫 수 결정. 깊이별 시간 ===

   깊이         시간              노드         최선 수       점수
------------------------------------------------------------
    1      0.00s              50       (0, 0)       +1
    2      0.00s             146       (0, 0)       +0
    3      0.01s           2,496       (0, 0)       +1
    4      0.02s           7,006       (0, 0)       +0

=== 깊이 5 도전? ===
(주의: 시간이 매우 오래 걸릴 수 있음. 코드 수정해서 d=5 시도해보세요.)

=== 결론 ===
• 7x7 빈 보드 깊이 4도 수십 초
• 깊이 5 이상은 분 단위. 깊이 7~8 보려면 시간이 폭발
• 19x19에서는 깊이 4도 며칠

← 이전 분기 인자 직접 측정 다음 → 실패의 의미 — 새 알고리즘이 필요하다