위키원
알파베타 가지치기
알파베타 가지치기(Alpha–beta pruning)는 탐색 트리에서 최소극대화 알고리즘을 적용할 때 평가하는 노드의 수를 줄이기 위한 알고리즘이다.
개요
알파베타 가지치기는 더 탐색할 필요가 없는 노드들은 무시하여 탐색 시간을 줄이는 알고리즘이다. 가지치기는 불필요한 행동을 모두 무시하여 상태를 제한하는 것을 의미하며, 알파베타 가지치기는 탐색 트리에서 최소극대화 알고리즘을 적용할 때 탐색하고 평가하는 노드를 줄이기 위해 사용된다. 적대탐색 알고리즘이라고도 불리며, 게임이나 바둑, 틱택토 등의 게임을 하는 기계에 주로 사용된다. 이전에 탐색한 노드보다 현재 탐색하는 노드가 더 가치 있다면 탐색을 중단하고, 남은 자식노드와 형제노드들은 가지치기한다. 최종 결정에 영향을 미치지 않는 가지들과 노드들은 가지치기되어 탐색이 이뤄질 수 없다.
게임 프로그램과 머신 러닝의 경우, 최소최대 알고리즘, 알파베타 가지치기와 같은 적대탐색 알고리즘들이 적용된다. 바둑과 체스같은 게임에서는 상대방이 다음에는 어디에 어떤 수를 놓을지 생각해야한다. 따라서 만약 게임을 할 수 있는 인공지능을 개발해야한다면, 상대방이 어떤 식으로 나왔을 때 어떻게 반응해야할지 최대한 많은 경우를 고려하는 코드를 구현해야한다. 이 때 사용하는 알고리즘이 최소최대 알고리즘이고, 알파베타 가지치기는 최소최대 알고리즘의 탐색시간을 줄이기 위해 사용되기도 한다. 더 이상 계산할 필요가 없는 경로를 제거하여 계산량을 대폭 절감시키는 효과를 볼 수 있고, 탐색에서 가장 중요한 것은 시간이기 때문에, 유용하게 사용되는 방식이다. 다음과 같은 최소최대 알고리즘 예시가 있다고 하자.
- 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년에 알파베타에 대한 연구가 여러번 이뤄졌다. 아서 새뮤얼은 알파베타 프루닝의 초기 버전을 발표했고, Richards, Hart, Levine, Edwards는 알파베타의 기초를 세웠다. 존 매카시도 1956년 다트머스 회의에서 비슷한 아이디어를 내면서 '근사치'라는 용어를 사용했으며,
각주
참고자료
- 알파-베타 가지치기 위키백과 - 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
같이 보기
| ||||||||||||||||||||||||||||||||||
