분기 인자 직접 측정

측정 결과 두 가지가 명확:

7x7 바둑의 분기 인자가 30~49 — 게임 초반엔 49, 후반엔 줄어들지만 전체 평균 ~35.
알파-베타 이상치 가정해도 깊이 7~8이 한계 — 1수에 1~2초. 19x19은 훨씬 심함 (b=250).

📊 19x19 바둑의 같은 계산

b=250이면:

깊이 6 (알파-베타 이상): 250^3 ≈ 1500만 노드 — 15초
깊이 8 (이상): 250^4 ≈ 40억 노드 — 1시간
깊이 10 (이상): 250^5 ≈ 1조 노드 — 11일

알파-베타 이상치는 "수 순서가 완벽"할 때. 바둑에서는 좋은 수 순서 휴리스틱이 어려워서 실제로는 더 느림.

⚠️ 깊이 7수는 무엇을 의미하나

한 영역에서 작은 전투 정도 (한쪽이 한 그룹 죽이거나 살리는 정도). 전체 판세는 안 보임. 19점 차이 같은 큰 그림은 영원히 못 봄.

사람 아마추어 5단도 머릿속에서 15~20수 정도는 봐. 컴퓨터가 깊이로 사람한테 뒤짐.

그러면 실제로 7x7 minimax를 돌려보면 어떤 결과가 나올까? 다음 페이지.

PYTHON

# 7x7 바둑에서 매 수의 분기 인자가 어떻게 변하는가?
# 흑/백 번갈아 둘 때 빈 자리 수를 그대로 분기 인자로 봄 (단순화).

import random

EMPTY, BLACK, WHITE = 0, 1, 2

def make_board(size=7):
    return [[EMPTY]*size for _ in range(size)]

def possible_moves(board):
    """빈 자리 리스트 (실제로는 자살수/패 제외해야 하지만 여기선 단순화)"""
    moves = []
    for r in range(len(board)):
        for c in range(len(board)):
            if board[r][c] == EMPTY:
                moves.append((r, c))
    return moves


# === 실험: 무작위 게임 진행하며 분기 인자 측정 ===
random.seed(42)
board = make_board(7)
turn = BLACK

print("=== 7x7 바둑: 매 수 분기 인자 ===\n")
print(f"{'수':>5} {'차례':>5} {'분기 인자':>12}")
print("-" * 30)

for move_num in range(1, 31):  # 30수 진행
    moves = possible_moves(board)
    b_factor = len(moves)
    print(f"{move_num:>5} {('흑' if turn==BLACK else '백'):>5} {b_factor:>12}")
    # 무작위 한 수
    r, c = random.choice(moves)
    board[r][c] = turn
    turn = WHITE if turn == BLACK else BLACK

print()
print(f"=== 분기 인자 요약 ===")
print(f"7x7 바둑: 초반 49 → 게임 진행 따라 감소")
print(f"평균 분기 인자 (게임 전체) ≈ 35~40")
print()

# === b^d 노드 수 계산 ===
import math
print(f"=== 평균 b=35로 봤을 때 minimax 노드 수 ===")
for d in range(1, 9):
    n_basic = 35 ** d
    n_ab = 35 ** (d/2)  # 알파-베타 이상치
    print(f"  깊이 {d}: 기본 {n_basic:>20,.0f}    알파-베타(이상) {n_ab:>15,.0f}")

print()
print("=== 1초당 100만 노드 처리 시 깊이별 시간 ===")
for d in range(1, 9):
    n_ab = 35 ** (d/2)
    sec = n_ab / 1_000_000
    if sec < 1:
        time_str = f"{sec*1000:.1f} ms"
    elif sec < 60:
        time_str = f"{sec:.1f} 초"
    elif sec < 3600:
        time_str = f"{sec/60:.1f} 분"
    else:
        time_str = f"{sec/3600:.1f} 시간"
    print(f"  깊이 {d}: {time_str}")

출력

기대 출력:

=== 7x7 바둑: 매 수 분기 인자 ===

    수    차례        분기 인자
------------------------------
    1     흑           49
    2     백           48
    3     흑           47
    4     백           46
    5     흑           45
    6     백           44
    7     흑           43
    8     백           42
    9     흑           41
   10     백           40
   11     흑           39
   12     백           38
   13     흑           37
   14     백           36
   15     흑           35
   16     백           34
   17     흑           33
   18     백           32
   19     흑           31
   20     백           30
   21     흑           29
   22     백           28
   23     흑           27
   24     백           26
   25     흑           25
   26     백           24
   27     흑           23
   28     백           22
   29     흑           21
   30     백           20

=== 분기 인자 요약 ===
7x7 바둑: 초반 49 → 게임 진행 따라 감소
평균 분기 인자 (게임 전체) ≈ 35~40

=== 평균 b=35로 봤을 때 minimax 노드 수 ===
  깊이 1: 기본                   35    알파-베타(이상)               6
  깊이 2: 기본                1,225    알파-베타(이상)              35
  깊이 3: 기본               42,875    알파-베타(이상)             207
  깊이 4: 기본            1,500,625    알파-베타(이상)           1,225
  깊이 5: 기본           52,521,875    알파-베타(이상)           7,247
  깊이 6: 기본        1,838,265,625    알파-베타(이상)          42,875
  깊이 7: 기본       64,339,296,875    알파-베타(이상)         253,652
  깊이 8: 기본    2,251,875,390,625    알파-베타(이상)       1,500,625

=== 1초당 100만 노드 처리 시 깊이별 시간 ===
  깊이 1: 0.0 ms
  깊이 2: 0.0 ms
  깊이 3: 0.2 ms
  깊이 4: 1.2 ms
  깊이 5: 7.2 ms
  깊이 6: 42.9 ms
  깊이 7: 253.7 ms
  깊이 8: 1.5 초

← 이전 평가 함수의 첫 시도 다음 → 7x7 minimax 실전 시도