알파베타 가지치기 Alpha-beta pruning 설명

 

알파베타 가지치기에 대한 설명을 찾아보며 학습한 내용입니다.
잘못된 부분이 있다면 알려주시기 바랍니다. 감사합니다!

 
그림과 그림 하단에 설명을 참고하시면 됩니다.
 
 

알파베타 가지치기는 α≥β 이면 가지치기를 하게됩니다. 
 
 

루트 노드에서 시작하게 되는데, 루트노드 우측에 다음을 적어줍니다.
α = -∞ 
β = ∞

좌측의 자식 노드로 내려왔을 때
부모 노드에 있던 α, β값을 그대로 적어줍니다.
α = -∞ 
β = ∞

또, 좌측의 자식 노드로 내려왔을 때
부모 노드에 있던 α, β값을 그대로 적어줍니다.
α = -∞ 
β = ∞

또! 자식 노드로 내려왔을 때
부모 노드에 있던 α, β값을 그대로 적어줍니다.
α = -∞ 
β = ∞

해당 노드는 min 값을 선택해야 하기 때문에 β 값을 수정해주게 됩니다. 이때, ∞ 와 5 중에서 더 min 값은 5가 되기 때문에 β 의 ∞ 를 5로 수정해 줍니다.
5와 6중에 더 min 값은 5이기 때문에 더이상 수정해주지 않고 부모 노드로 올라갑니다.
 
 

현재 노드에서는 max 값을 선택해주기 때문에 α 를 수정해주게 되는데  α 값이 -∞와 β 에서의 5 중 더 max 값은 5이기 때문에  α = -∞를 5로 수정해줍니다.

--

그리고 자식노드로 다시 내려오면서 부모에 있던 값을 그대로 적어주게 됩니다.
α = 5
β = ∞
현재 노드에서는 min 값을 선택해야 하기 때문에  β 를 수정해주게 됩니다. 이떄는 7과  ∞를 비교하는데, 둘 중 더 min은 7이기 때문에  β 를 ∞에서 7로 수정해주게 됩니다. 

그리고 7과 4중 더 min 값인 4를 β = 7 대신 4를 대입해 줍니다. 

이 때, α = 5가 되고 β = 4가 되는데 α≥β 조건으로 인해 그 다음 노드의 탐색을 더이상 진행하지 않고 가지치기를 합니다.