알파베타 가지치기(Alpha-Beta Pruning) 알고리즘

오목 알고리즘을 만들면서 학과 수업시간에 공부한 내용 일부 발췌 및 정리

https://ko.wikipedia.org/wiki/%EC%95%8C%ED%8C%8C-%EB%B2%A0%ED%83%80_%EA%B0%80%EC%A7%80%EC%B9%98%EA%B8%B0

https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning

한글 위키 페이지보다 영문위키페이지가 더 자세하게 잘 설명되어있는 듯하다. 궁금하거나 필요한 분은 영문위키페이지를 보길 바랍니다.

알파베타 가지치기 알고리즘은 분기한정법(branch and bound)의 한 종류이며 두 사람이 두는 게임, 예로 틱택토, 오목, 바둑 등에 많이 적용하는 알고리즘이다. 미니막스 알고리즘을 기반으로 하여 응용된 것이 알고리즘으로 이름붙여진 것이다. 미니막스 알고리즘은 깊이우선 검색(Depth First Search)로서 모든 노드를 다 계산해야 하는 무식한 Brute Force 방법이라고 할 수 있다. 이런 단점을 보완하기 위해서 더이상 검색해봐야 의미없는 노드의 가지들을 잘라내어서 검색속도를 획기적으로 빠르게 만들 수 있는 알고리즘이다. 

오목알고리즘에서는 알파베타 가지치기 (Alpha- Beta Pruning)알고리즘이 오목의 결과를 평가해주는 것은 아니며, 평가함수가 수행할 노드들을 전체 경우의 수를 다 평가하는 것이 아닌 가지치기 한 나머지의 노드들만을 평가할 수 있도록 도와주는 알고리즘 기술이다. 결국 오목 알고리즘의 성능 자체가 알파베타 가지치기(Alpha-Beta Pruning)알고리즘에 의해 오목의 지능이 높아지는 것은 아니며 결국은 평가함수를 어떻게 만드느냐에 따라 오목의 지능이 달라지게 되는 것이다. 다만 노드 검색을 위해서 불필요한 검색을 방지해주어 검색 성능을 끌어올려주는 데에 기여를 하는 알고리즘이라 할 수 있다.  

아래 수도 코드를 참고하자 

1. MiniMax Search Algorithm

Mini-Max(node, depth) 
{ 
     if (depth == 0) 
          return value(node); 
     else { /* depth is greather than 0 */ 
          if (node is black's move) { 
               max = -infinity; 
               for (each child c-node of node) 
                    max = max{max, Mini-Max(c-node, depth-1)}; 
               return max; 
          } 
          else { /* node is white's move) 
               min = +infinity; 
               for (each child c-node of node) 
                    min = min{min, Mini-Max(c-node, depth-1)}; 
               return min; 
          } 
     } 
} 

2. Alpha-Beta Pruning Algorithm  

/*Initially Alpha-Beta is called with alpha = -infinity, beta = +infinity */
Alpha-Beta(node, depth, alpha, beta) 
{ 
     if (depth == 0) 
          return value(node); 
     else { /* depth is greater than 0 */ 
          if (node is black's move) { 
               for (each child c-node of node) { 
                    v = Alpha-Beta(c-node, depth-1, alpha, beta); 
                    alpha = max{alpha, v}; 
                    if (alpha >= beta) 
                         return alpha; 
               } 
               return alpha; 
          } 
          else { /* node is white's move */ 
               for (each child c-node of node) { 
                    v = Alpha-Beta(c-node, depth-1, alpha, beta); 
                    beta = min{beta, v}; 
                    if (alpha >= beta) 
                         return beta; 
               } 
               return beta; 
          } 
     } 
}