알파-베타 가지치기

개념

알파-베타 가지치기는 미니맥스 알고리즘에서 결과를 바꾸지 않는 노드를 더 이상 탐색하지 않는 방법이다. pruning 또는 절단이라고도 한다.

알파와 베타

• α(alpha): MAX가 현재까지 확보한 가장 좋은 값
• β(beta): MIN이 현재까지 확보한 가장 좋은 값

탐색 중 β ≤ α가 되면 그 아래를 더 보아도 최종 선택이 바뀌지 않으므로 가지치기한다.

$$\beta \le \alpha ⟹\text{prune}$$

의미

알파-베타 가지치기는 미니맥스의 결과는 유지하면서 탐색할 노드 수를 줄인다. 하지만 게임이 매우 크면 여전히 계산량이 많고, 좋은 휴리스틱 평가 함수가 필요하다.