알파-베타 — minimax의 마법
👋 이 챕터에서 배울 것
Minimax의 결과는 그대로, 속도만 100배 이상 빠르게. 알파-베타 가지치기(Alpha-Beta Pruning)의 마법.
지난 챕터에서 본 minimax는 트리의 모든 노드를 다 봤어. 그런데 가만 생각해보면 — 어떤 가지는 더 안 봐도 결론을 알 수 있지 않을까?
💡 핵심 직관
상대(MIN)가 어떤 가지에서 이미 매우 작은 점수를 발견했다고 하자. 그 가지의 다른 자식들은 더 작을 수도 있지만 — 어쨌든 상대는 그 작은 점수 이하로 끌고 갈 거. 그러면 나(MAX)는 그 가지로 가지 않을 거야. 다른 가지가 이미 더 큰 점수를 보장하니까.
그래서 그 가지의 나머지를 볼 필요가 없다. 가지치기 끝.
1956년 John McCarthy(LISP 만든 사람)이 처음 아이디어를 냈고, 1958년 Allen Newell과 Herbert Simon이 정식화. 60년이 넘은 알고리즘인데 여전히 모든 체스 엔진의 기반이야 (Stockfish 포함).
이 챕터:
- α (알파)와 β (베타) — 두 경계 값의 의미
- 가지치기 작동 시점 — 시각화로 단계별
- 코드: minimax 위에 두 줄만 추가하면 끝
- 속도 측정: 가지치기 전 후 비교
- 수 순서가 가지치기 효율을 좌우