A Pruning, Alpha-Beta Pruning, Mover Ordering

The Problem with Minimax Search

- 재귀적으로 구현된 minimax search 는 depth search 와 비슷하고, 이는 O(b^m) 의 시간복잡도를 가지기 때문에 실용적이지 않다.

- 그러나 어떤 경우에는 모든 노드에 대해 검사를 하지 않더라도 정확한 minimax value 를 알 수 있게 된다.

 

 

 

A Pruning Example

(a) 에서 [-무한, +무한] 은 A가 가질 수 있는 utility value 의 범위를 뜻한다. B를 방문하더라도 아직 알려진 것이 없기 때문에 B의 utility 범위도 [-무한, +무한] 이 된다. 이때 3을 방문하게 되면, B에서는 utility value 의 최댓값을 3으로 보장할 수 있게 되는 것이다. 다른 노드들을 방문해서 3보다 크다면, 3을 선택하면 되는 것이고, 3보다 작을 경우를 대비하여

[-무한, 3] 으로 B의 범위를 설정한다.

 

(b) 12 노드를 탐색했을 때, B의 범위는 변하지 않는다.

 

(c) 8 노드를 탐색했을 때, B의 자식 노드들은 모두 결정되었으므로 B의 범위는 [3,3] 으로 결정된다. 그 순간 A의 최소값은 3으로 결정된다. A는 MAX 값을 취해야 하는데, 만약 B를 선택한다면 최소 3점은 보장받을 수 있기 때문이다. 만약, C D 에서 3점보다 높은 값을 얻을 수 있다면 그곳으로 갈 것이기 때문에 [3, +무한] 의 범위를 가진다.

 

(d) C노드의 경우 2를 방문한 후 [-무한, 2] 의 범위를 결정하게 되었다. 이때, MAX 의 입장에서 B가 아닌 C를 선택한다면 최대 2점을 얻을 수 있기 때문에, C가 아닌 B를 선택할 것이다. 따라서 C의 자식 노드들을 탐색할 필요가 없다. -> Proning

 

(d) D노드의 경우 max 값이 [-무한, 14] 로 정해졌다. 이때, C 노드와는 다르게 A가 선택할 가능성이 생기게 되었다. 따라서 자식 노드들을 더 탐색하였는데, 최소 노드가 2이기 때문에 D 의 범위는 [2,2] 로 정해지게 되었다. 따라서 A는 B쪽으로 가는 것이 optimal 하다.

 

-> 13개의 노드 중 11개의 노드만 탐색하였다. (Alpha-Beta Pruning)

 

 

 

The General Case for Alpha-Beta Pruning

Alpha : 값을 쭉 따라갔을 때 MAX 가 얻을 수 있는 최고값 (최대 점수)

Beta : 값을 쭉 따라갔을 때 MIN 이 얻을 수 있는 최고값 (최소 점수)

-> 노드별로 Alpha, Beta 값을 유지하면서 Search 를 아래로 더 이상 진행하지 않을 수 있다.

 

 

 

Mover Ordering

노드를 조사하는 순서가 매우 중요하다.

B,C 의 값이 정해진 상태에서, D를 조사할 때 d1을 먼저 검사한 경우 총 13개의 노드 중 11개의 노드를 검사하였다.

만약, d1이 아니라 d3부터 검사를 한다면 최대값이 2이기 때문에 d1,d2 를 검사할 필요가 없게 된다. 따라서 13개 중 9개의 노드만 검사하여도 된다.

따라서, 자식 노드를 방문하는 순서에 따라서 alpha-beta proning 정도가 차이가 나게 된다.

만약 가장 좋은 자식을 제일 먼저 방문한다면, effective branching factor 은 제곱근이 되게 된다.

b^m -> b^(2/m) -> (루트b)^,m 

실제로 체스의 경우, simple heuristic ordering 을 통해 이를 성공하였다.

그러나, 실제로 best successor 를 결정하는 것은 어렵기 때문에, 구현이 어렵다.