위키원
알파베타 가지치기
알파베타 가지치기(Alpha–beta pruning)는 탐색 트리에서 최소극대화(minimax) 알고리즘을 적용할 때 평가하는 노드의 수를 줄이기 위한 알고리즘이다.
개요
알파베타 가지치기는 더 탐색할 필요가 없는 노드들은 무시하여 탐색 시간을 줄이는 알고리즘이다. 가지치기는 불필요한 행동을 모두 무시하여 상태를 제한하는 것을 의미하며, 알파베타 가지치기는 탐색 트리에서 최소극대화 알고리즘을 적용할 때 탐색하고 평가하는 노드를 줄이기 위해 사용된다. 적대탐색 알고리즘이라고도 불린다. 게임이나 바둑, 틱택토 등의 게임을 하는 기계에 주로 사용된다. 이전에 탐색한 노드보다 현재 탐색하는 노드가 더 가치 있다면 탐색을 중단하고, 남은 자식노드와 형제노드들은 가지치기한다. 따라서 최종 결정에 영향을 미치지 않는 가지들과 노드들은 가지치기되어 탐색이 이뤄질 수 없다.
바둑과 체스같은 게임에서는 상대방이 다음에는 어디에 어떤 수를 놓을지 생각해야한다. 따라서 만약 게임을 할 수 있는 인공지능을 개발해야한다면, 상대방이 어떤 식으로 나왔을 때 어떻게 반응해야할지 최대한 많은 경우를 고려하는 코드를 구현해야한다. 이와 같은 게임 프로그램과 머신 러닝의 경우, 최소최대 알고리즘, 알파베타 가지치기와 같은 적대탐색 알고리즘들이 적용된다. 알파베타 가지치기는 주로 2인용 보드게임의 분석 등에 사용되며, 최소최대 알고리즘의 탐색시간을 줄이기 위해 사용되기도 한다. 더 이상 계산할 필요가 없는 경로를 제거하여 계산량을 대폭 절감시키는 효과를 볼 수 있다.
또, 알파베타 가지치기는 탐색 트리에서 최소극대화 알고리즘을 적용할 때 평가하는 노드의 수를 줄이기 위해 사용되는데, 여기서 최소극대화는 추정되는 최대의 손실을 최소화하는 알고리즘을 말한다. 최소극대화 알고리즘은 최악의 경우에 발생할 수 있는 최대 손실을 최대한 감소하기 위한 의사결정 원칙으로, 게임이론에서 서로 적대 관계인 경기자의 이익은 최대로, 상대로부터 받는 피해는 최소로 만들기 위해 행동한다는 원리이다.
탐색에서 가장 중요한 것은 시간이기 때문에, 알파베타 가지치기는 유용하게 사용되는 방식이다. 예를 들어 다음과 같은 최소최대 알고리즘 예시가 있다고 가정한다면,
- MAX
- ⓐ
- MIN
- ⓑ ⓒ
- MAX
- ⓓ ⓔ ⓕⓖⓗ
- MIN
- ⓘ ⓙⓚ ⓛ ⓜⓝ ⓞⓟ
a는 b와 c로 갈리고, b는 d와 e로 갈리며, d는 i로, e는 j와 k로 나뉜다. 마찬가지로 c도 f, g, h로 갈리고, f는 l로, g는 m와 n으로, h는 o와 p로 갈린다. 여기서 만약 i의 값이2이고 j의 값이 4이고 k가 가지치기 당한다면, d는 자식노드의 2가 자동으로 선택되고, e는 자식노드의 최댓값인 4를 선택한다. MIN의 b는 d와 e를 비교하여 가장 작은 수를 선택해야하는데, 2<4이므로 b는 d를 선택한다. 결국 b는 최종적으로 d와 e중 최솟값을 선택할 것이고, 따라서 k와 k 이외의 e의 자식들은 탐색할 필요가 없기 때문에 굳이 탐색할 필요가 없는 노드들을 가지치기하여 탐색 시간 자원을 절약한다.[1] 바둑 인공지능의 경우 바둑을 트리로 표현하면 개의 노드를 갖게 되므로, 알파베타 가지치기가 바둑 인공지능 구현에는 매우 비효율적이라는 견해도 있다.[2][3]
역사
앨런 뉴얼과 허버트 사이먼에 따르면, 1958년에 알파베타에 대한 연구가 여러번 이뤄졌다. 아서 새뮤얼(Arthur Samuel)은 알파베타 프루닝의 초기 버전을 발표했고, Richards, Hart, Levine, Edwards는 알파베타의 기초를 세웠다. 존 매카시도 1956년 다트머스 회의에서 비슷한 아이디어를 내면서 '근사치'라는 용어를 사용했으며, 1961년 매사추세츠 공과대학교에 다니는 앨런 코톡에게도 가르쳤다. 1963년, 알렉산더 브루노(Alexander Brudno)는 알파베타에 대해 독자적으로 발표했으며, 1975년에 도널드 커누스와 로널드 무어가 알고리즘을 재정립했다. 1982년에는 유디 펄이 알파베타 가지치기가 최적임을 증명했다.
특징
알파베타 가지치기의 장점이자 가장 큰 특징은 탐색 트리의 가지를 쳐낼 수 있다는 것이다. 덕분에 탐색 트리의 탐색은 더 가능성 있는 서브 트리에서만 이뤄질 수 있고, 같은 시간 안에 더 깊은 노드까지 탐색할 수 있게 된다. 알파베타 가지치기는 분기 한정법의 일종이다. 노드가 최적 또는 최적에 가까운 순서대로 평가된다면, 탐색하는 깊이가 기본적인 최소극대화의 반 이하가 되도록 최적화할 수 있다.
의사코드
다음은 페일 소프트(fail-soft) 버전 의사코드이다. 페일 소프트의 알파베타 가지치기는 알파와 베타값 범위를 넘는 v값을 반환할 수 있다 ( or ). 반면에 페일 하드 알파베타 가지치기는 반환하는 값을 알파와 베타의 범위로 제한한다().[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
각주
- ↑ HA_Kwon, 〈최소최대 알고리즘〉, 《티스토리》, 2018-03-21
- ↑ Silver, D. et al.,〈[Mastering the game of Go with Deep neural networks and tree search]〉, 《Nature vol 529》, 2016-01-28
- ↑ 추형석, 안성원, 김석원,〈[AlphaGo의 인공지능 알고리즘 분석]〉, 《소프트웨어 정책연구소》, 2016-01-28
- ↑ 알파-베타 가지치기 위키백과 - 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://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
- Silver, D. et al., 〈[Mastering the game of Go with Deep neural networks and tree search]〉, 《Nature vol 529》, 2016-01-28
- 추형석, 안성원, 김석원, 〈[알파고의 인공지능 알고리즘 분석]〉, 《소프트웨어 정책연구소》, 2016-03-03
- HA_Kwon, 〈최소최대 알고리즘〉, 《티스토리》, 2018-03-21
같이 보기
| ||||||||||||||||||||||||||||||||||
