Study/Artificial Intelligence

Alpha-Beta pruning

빨간당무 2010. 9. 29. 21:46
Alpha-Beta pruning 이란?
  • 두명이 참여하는 게임을 위한 최소최대(Mini-max) 알고리즘에 의해 평가되는 노드들의 수를 감소시키기 위한 기술이다.
  • 즉, 게임에서 상대방은 절대 도달하지 못하도록 나에게만 유리하게 탐색트리의 일부분을 잘라내는 것이다.
  • Alpha-beta pruning을 가진 minimax는 가지치기를 하지 않는 minimax와 같은 결과를 보이지만 훨씬 더 효율적이다.
  • 보통 효율적인 분기 요소(branching factor)를 square root 까지 감소시키고, 같은 시간내에 탐색할 수 있는 가지(ply)의 수를 두배로 만든다.
  • 두 값 앞파와 베타는, maximizing player가 보장하는 (assured of) 최소 점수이며 마찬가지로 minimizing player가 보장하는 최대 점수를 나타낸다.
  • 처음에 알파는 마이너스 무한대(minus infinity), 베타는 플러스 무한대이다. 
  • 그 과정이 반복됨에 따라 "window"는 더 작게 된다. 베타가 알파보다 작게 되면, 그것은 현재의 위치가 두 플레이어에 의한 가장 좋은 플레이의 결과일 수 없다는 것을 의미하고, 따라서 더 이상의 탐색은 할 필요가 없게된다.


- 1번 그림


- 2번 그림
2번째 그림에서 발생하는 Alpha pruning은 C의 값이 앞서 R(20)과 S(30)에서 높은 값인 S(30)이 올라와 H가 30으로 지정되고 나서 C가 30으로 지정된다. 
이후 I값을 확인하여야 하나 C에 올라올수 있는 값은 현재 값인 30보다 작아야 하고 A(50)으로 올라가려면 50보다 커야 하는데 그렇다면 A(50) <= C(50 or I값)이고 I(?) < H(30) 보다 작아야 한다는 뜻이된다.
결국 A(50) <= C(50 or <H(30)) 이하여야 하므로 만족하는 값이 나올 수 없기 때문에 I값을 확인하지 않고 가지치기(Pruning)한다. (I, T, U 를 탐색하지 않는다.)
- 2번째 그림에서 C에서 30보다 작은 값만 나올 수 있는 가능성이 있기 때문에 C값은 A값 보다 큰 수를 가질 수 없으므로 올라갈 수 없다. 그러므로 더이상의 탐색은 중단한다. (I, T, U)


- 3번 그림
- 3번째 그림에서 K에서 90보다 큰 값만 나올 수 있는 가능성이 있기 때문에 K값은 C값 보다 작은 수를 가질 수 없으므로 올라갈 수 없다. 그러므로 더이상의 탐색은 중단한다. (Y)
- 3번째 그림에서 발생하는 Beta pruning은 K의 값이 앞서 X(90)으로 인해 K는 90이 되고 Y(20)값을 확인하여 K값을 90 또는 20으로 변경해야 하는데. K의 상위 노드인 D(80)이 갱신되려면 앞서 J(80)보다 작아야 하는데 K(90)에서는 더이상 값이 나올 수 없다.
결국 K(90 or Y값)이므로 90이상 값만 나올 예정이고, D(80) >= K(90이상 예정)이라면 제약조건을 위반하므로 결국 Y값을 확인하지 않고 가지치기(Pruning)한다. (Y 를 탐색하지 않는다.)

- 그림을 그려주신 최자현 누님께 감사드립니다.