알파-베타 가지치기

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기
알파-베타 가지치기
분류 검색 알고리즘
최악 시간복잡도
최선 시간복잡도

알파-베타 가지치기(Alpha–beta pruning)는 탐색트리에서 미니맥스 알고리즘에 의해 평가되는 노드의 수를 줄이기 위한 검색 알고리즘이다. 이 알고리즘은 적대탐색 알고리즘이라고도 불리는데, 기계가 플레이하는 2인용게임(틱택토, 체스, 바둑)에 주로 사용된다. 이 알고리즘은 이전에 평가한 이동보다 평가하고 있는 이동이 더 좋지 않다는 가능성이 하나라도 발견된다면 평가하고 있는 이동의 평가를 완전히 멈춘다. 이러한 이동은 더 이상 평가될 필요가 없다. 이 알고리즘이 표준 미니맥스 트리에 적용된다면 미니맥스와 똑같은 결과를 반환할 것이지만, 마지막 결정에 영향을 미치지 않는 가지들은 잘라낼 것이다.[1]

역사[편집]

John McCarthy가 "근사치"[2]로 부른 것을 사용한 Allen Newell과 Herbert A. Simon은 1958년에 알파-베타는 여러 번 재조명된 것 같다고 적었다.[3] Arthur Samuel은 초기버전을 가지고 있었고, Richards, Hart, Levine 그리고/혹은 Edwards는 미국에서 독립적으로 알파-베타의 기초를 세웠다.[4] McCarthy는 비슷한 아이디어를 1956 Dartmouth 회의에서 제안하였고, 이 의견을 1961년에 MIT에 다니는 Alan Kotok을 포함한 그의 학생들에게 제안하였다.[5] Alexander Brudno는 독립적으로 알파-베타 알고리즘을 발견하였고, 1963년에 그의 결과를 발표하였다.[6] Donald Knuth와 Ronald W. Moore는 1975년에 알고리즘을 재정립하고,[7] 1982년 Judea Pearl가 이 방법이 최선임을 증명하였다.

소박한 미니맥스 너머의 발전[편집]

알파-베타 가지치기의 이점은 탐색트리의 가지가 제거될 수 있다는 점에 있다. 이러한 경우 검색 시간은 ‘더 유망한’ 서브트리에 한해서 이루어지고, 같은 시간 안에 더 깊은 검색을 수행할 수 있다. 알파-베타 알고리즘은 이전 모델처럼 분기 한정법 알고리즘으로 분류된다. 노드가 최적의, 혹은 거의 최적의 순서대로 평가된다면, 최적화는 실질적인 깊이를 기본적인 미니맥스의 깊이 반 이상으로 줄일 수 있다.

분기 계수를 b라고 하고, ply(한 턴의 1/2)의 검색 깊이를 d라고 한다면, (이동순서가 최악이라면) 평가된 잎 노드 위치는 O(b*b*...*b) = O(b**d) - 기본적인 미니맥스 검색과 같다. 만약 검색의 이동순서가 최적이라면, 평가된 잎 노드의 수는 홀수깊이일 때 약 O(b*1*b*1*...*b) 이고, 짝수깊이일 때 O(b*1*b*1*...*1) 즉, O(b**d/2) 이다. 후자의 경우 사실상의 분기 계수는 제곱근으로 줄어든다. 다시 말해 검색이 같은 양의 연산 작업으로 거의 두 배 만큼 더 깊이 검색을 할 수 있다는 것이다. b*1*b*1... 식의 설명은 최적의 이동을 찾기 위해서는 첫 번째 플레이어의 이동은 반드시 연구돼야 하지만, 사실은 두 번째 플레이어의 최적의 움직임은 첫 번째 플레이어의 첫 번째 움직임 빼고 모든 움직임을 반박하기 위해 필요하다. 노드가 랜덤으로 정돈됐다면, 평균적으로 평가된 노드의 수는 약 O(b**3d/4)이다.

의사코드[편집]

알파-베타 가지치기의 페일 소프트 변형의 의사코드는 다음과 같다:

01 function alphabeta(node, depth, α, β, maximizingPlayer)
02      if depth = 0 or node is a terminal node
03          return the heuristic value of node
04      if maximizingPlayer
05          v := -∞
06          for each child of node
07              v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
08              α := max(α, v)
09              if β ≤ α
10                  break (* β cut-off *)
11          return v
12      else
13          v := ∞
14          for each child of node
15              v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
16              β := min(β, v)
17              if β ≤ α
18                  break (* α cut-off *)
19          return v

페일 소프트 알파-베타에서, 알파-베타 기능은 알파와 베타의 경계를 초과하는 값을 반환한다. 이에 비해, 페일 하드 알파-베타는 이것의 기능을 알파와 베타의 광대한 영역으로 값을 반환하도록 제한한다.

각주[편집]

  1. Russell, Stuart J.; Norvig, Peter (2010). 《Artificial Intelligence: A Modern Approach》 3판. Upper Saddle River, New Jersey: Pearson Education, Inc. 167쪽. ISBN 0-13-604259-7. 
  2. McCarthy, John (2006년 11월 27일). “Human Level AI Is Harder Than It Seemed in 1955”. 2006년 12월 20일에 확인함. 
  3. Newell, Allen; Herbert A. Simon (March 1976). “Computer Science as Empirical Inquiry: Symbols and Search” (PDF). 《Communications of the ACM》 19 (3): 113. doi:10.1145/360018.360022. 2007년 6월 28일에 원본 문서 (PDF)에서 보존된 문서. 2006년 12월 21일에 확인함. 
  4. Edwards, D.J.; Hart, T.P. (1961년 12월 4일). “The Alpha–beta Heuristic (AIM-030)”. Massachusetts Institute of Technology. 2006년 12월 21일에 확인함. 
  5. Kotok, Alan (2004년 12월 3일). “MIT Artificial Intelligence Memo 41”. 2006년 7월 1일에 확인함. 
  6. Marsland, T.A. (May 1987). “Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)” (PDF). J. Wiley & Sons. 159–171쪽. 2008년 10월 30일에 원본 문서 (PDF)에서 보존된 문서. 2006년 12월 21일에 확인함. 
  7. Knuth, D. E.; Moore, R. W. (1975). “An Analysis of Alpha–Beta Pruning” (PDF). 《Artificial Intelligence》 6 (4): 293–326. doi:10.1016/0004-3702(75)90019-3. [깨진 링크(과거 내용 찾기)]

참고 문헌[편집]

  • George T. Heineman, Gary Pollice, and Stanley Selkow (2008). 〈Chapter 7: Path Finding in AI〉. 《Algorithms in a Nutshell》. 오라일리 미디어. 217–223쪽. ISBN 978-0-596-51624-6. 
  • 유디 펄, Heuristics, Addison-Wesley, 1984
  • John P. Fishburn (1984). 〈Appendix A: Some Optimizations of α-β Search〉. 《Analysis of Speedup in Distributed Algorithms (revision of 1981 PhD thesis)》. UMI Research Press. 107–111쪽. ISBN 0-8357-1527-2.