점수 전파 — Leaf에서 Root로
위 트리를 손으로 풀어보자. 잎(파란 동그라미)에 이미 점수가 있어. 이 점수를 위로 어떻게 전파?
🔑 전파 규칙
- MAX 노드: 자식들 점수 중 최댓값을 가져온다.
- MIN 노드: 자식들 점수 중 최솟값을 가져온다.
한 단계씩 따라가:
- 왼쪽 MIN 노드: 자식들 점수 = (3, 5). 상대 차례라서 작은 것 고름 → 3.
- 오른쪽 MIN 노드: 자식들 점수 = (2, 9). 작은 것 고름 → 2.
- 루트 MAX 노드: 자식들 점수 = (3, 2). 내 차례라서 큰 것 고름 → 3.
그래서 루트의 minimax 점수는 3. 내가 두 가지 수(왼쪽/오른쪽) 중 왼쪽 가지로 가야 보장된 3점을 얻어. 오른쪽 가면 상대가 -2점으로 끌고 갈 거니까.
💡 핵심 통찰
오른쪽 가지의 9점이 매혹적이지? 그런데 거기로 가는 권한은 내가 아니라 상대야. 상대가 똑똑하니까 9점이 아니라 2점으로 끌고 가. 그래서 9는 함정.
이 "상대가 최악으로 끌고 갈 것"이라는 가정이 minimax의 보수적이지만 안전한 본질이야.
이제 코드로 짜보자. 트리가 무한히 클 수도 있으니 재귀가 자연스러워.
컴포넌트 로딩 중...