Alpha-Beta-Pruning 알고리듬의 이해
https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning
http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html
깊이 우선 트리탐색(Depth-First Search)
Alpha Beta Pruning
Alpha : Maximum value found so far (나에게 유리한 정도, Alpha값이 클수록 나에게 유리함)
Beta : Minimum value found so far (나에게 불리한 정도, Beta값이 작을수록 나에게 불리함)
평가함수: 나에게 유리한 정도를 수로 표현하는 함수.
Alpha-cutoff : MIN 노드의 값(v)과 Alpha값을 비교하여 v<=Alpha 인 경우, MIN노드 하위에 연결된 MAX 노드를 잘라내는 것
Beta-cutoff : MAX 노드의 값(v)과 Beta값을 비교하여 v>=Beta 인 경우, MAX노드 하위에 연결된 MIN 노드를 잘라내는 것
By Jez9999 at the English language Wikipedia, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=3708424
Alpha-cutoff, Beta-cutoff 의 예
가지치기 조건
MAX 노드에서 beta cut : Value 가 beta 보다 크거나 같을 때, ( V >= beta )
MIN 노드에서 alpha cut : Value 가 alpha 보다 작거나 같을 때, ( V<= alpha )
위의 그림에 대한 설명
Alpha-Beta Pruning 연습용 그림
위의 그림에 표시된 트리구조에 Alpha-Beta Pruning 알고리듬을 적용한 결과 A-B-E-M 노드가 최종적으로 선택된다
