깊이 제한 + Heuristic — 끝까지 못 갈 때
틱택토는 깊이 9면 끝까지 가니까 minimax가 완벽한 답을 줘. 그런데 체스(깊이 80)나 바둑(깊이 150)은? 절대 끝까지 못 가.
해결책: 적당한 깊이까지만 보고, 거기서 추정 점수를 매긴다.
📖 Heuristic 평가 함수
중간 상태를 보고 "이 상태가 누구한테 얼마나 좋은가"를 어림으로 매기는 함수. heuristic evaluation function.
- 체스 예시:
내 기물 가치 합 - 상대 기물 가치 합(퀸 9점, 룩 5점, ...) - 바둑 예시:
예상 집수 차이또는활로 차이
의사 코드:
def minimax_depth(state, depth, is_max):
if 게임끝 or depth == 0:
return heuristic(state) # ← 추정 점수 사용
if is_max:
return max(minimax_depth(child, depth-1, False) for child in 자식들)
else:
return min(minimax_depth(child, depth-1, True) for child in 자식들)
변경점은 두 줄:
- 종료 조건에
depth == 0추가 - 리프에서
heuristic(state)사용 (게임 결과 대신)
⚠️ 핵심 트레이드오프
깊이가 깊을수록 정확하지만 느려. 분기 b, 깊이 d면 b^d 노드. 체스 b=35, 깊이 6이면 약 10억 노드. 한 게임에 몇 분 걸림.
그래서 평가 함수의 품질이 매우 중요. 적당한 깊이 + 좋은 heuristic = 좋은 AI. 1997년 IBM Deep Blue가 카스파로프를 이긴 것도 이 접근법.
그러나 바둑에는 큰 문제 두 가지:
- 좋은 heuristic 만들기가 어렵다. 체스는 기물 가치가 분명하지만, 바둑은 "이 보드가 흑한테 얼마나 좋은가"를 사람조차 어림 매기기 힘들어.
- 분기 인자가 너무 크다. b=250이면 깊이 5만 봐도 10^12 노드. 한 수에 며칠.
이게 PART 2 Ch 6에서 직접 실패를 체험할 부분. 그 전에 다음 챕터에서 알파-베타 가지치기로 minimax 속도를 100배 빠르게 만드는 법을 배워.