알파베타 가지치기

알파베타 가지치기(Alpha–beta pruning)는 탐색 트리에서 최소극대화(minimax) 알고리즘을 적용할 때 평가하는 노드의 수를 줄이기 위한 알고리즘이다. 최소극대화, 즉 미니맥스 알고리즘을 더 효율적으로 사용하기 위해 고안되었다.

개요

알파베타 가지치기는 더 탐색할 필요가 없는 노드들은 무시하여 탐색 시간을 줄이는 알고리즘이다. 가지치기는 불필요한 행동을 모두 무시하여 상태를 제한하는 것을 의미하며, 알파베타 가지치기는 탐색 트리에서 최소극대화 알고리즘을 적용할 때 탐색하고 평가하는 노드를 줄이기 위해 사용된다. 적대 탐색 알고리즘이라고도 불리고, 게임이나 바둑, 틱택토 등의 게임을 하는 기계에 주로 사용된다. 이전에 탐색한 노드보다 현재 탐색하는 노드가 더 가치 있다면 탐색을 중단하고, 남은 자식 노드와 형제 노드들은 가지치기한다. 따라서 최종 결정에 영향을 미치지 않는 가지들과 노드들은 가지치기 되어 탐색이 이뤄질 수 없다. 바둑과 체스 같은 게임에서는 상대방이 다음에는 어디에 어떤 수를 놓을지 생각해야 한다. 따라서 만약 게임을 할 수 있는 인공지능을 개발해야 한다면, 상대방이 어떤 식으로 나왔을 때 어떻게 반응해야 할지 최대한 많은 경우를 고려하는 코드를 구현해야 한다. 이와 같은 게임 프로그램과 머신 러닝의 경우, 최소최대 알고리즘, 알파베타 가지치기와 같은 적대 탐색 알고리즘들이 적용된다. 알파베타 가지치기는 주로 2인용 보드게임의 분석 등에 사용되며, 최소최대 알고리즘의 탐색 시간을 줄이기 위해 사용되기도 한다. 더 이상 계산할 필요가 없는 경로를 제거하여 계산량을 대폭 절감시키는 효과를 볼 수 있다.

또, 알파베타 가지치기는 탐색 트리에서 최소극대화 알고리즘을 적용할 때 평가하는 노드의 수를 줄이기 위해 사용되는데, 여기서 최소극대화는 추정되는 최대의 손실을 최소화하는 알고리즘을 말한다. 최소극대화 알고리즘은 최악의 경우에 발생할 수 있는 최대 손실을 최대한 감소하기 위한 의사결정 원칙으로, 게임이론에서 서로 적대 관계인 경기자의 이익은 최대로, 상대로부터 받는 피해는 최소로 만들기 위해 행동한다는 원리이다. 탐색에서 가장 중요한 것은 시간이기 때문에, 알파베타 가지치기는 유용하게 사용된다. 다음은 알파베타 가지치기를 설명하기 위한 최소최대 알고리즘 예시와 조건이다.

MAX 

ⓐ

MIN 

ⓑ ⓒ

MAX 

ⓓ ⓔ ⓕⓖⓗ

MIN 

ⓘ ⓙⓚ ⓛ ⓜⓝ ⓞⓟ

조건

• MAX 노드의 알파 값은 감소하지 않으며, 알파 값은 현재까지 지식 노드의 전달 값 중 가장 큰 값이다.
• MIN 노드의 베타 값은 증가하지 않으며, 베타 값은 현재까지 자식 노드의 전달 값 중 가장 작은 값이다.
• MIN은 가능한 경우에서 가장 평가를 낮게 받은 노드를 선택하고, MAX는 가장 높게 받은 노드를 선택한다.

MAX 노드의 알파 값은 감소하지 않으며, 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의 자식들은 탐색할 필요가 없기 때문에 굳이 탐색할 필요가 없는 노드들을 가지치기 하여 탐색 시간 자원을 절약한다. 바둑 인공지능의 경우 바둑을 트리로 표현하면 $250^{150}$개의 노드를 갖게 되므로, 알파베타 가지치기가 바둑 인공지능 구현에는 매우 비효율적이라는 견해도 있다. 알파베타 가지치기 외에도 Negascout 이나 MTD-f 와 같은 최적화 알고리즘이 있다.

의사 코드

다음은 페일 소프트(fail-soft) 버전 의사 코드이다. 페일 소프트의 알파베타 가지치기는 알파와 베타 값 범위를 넘는 v 값을 반환할 수 있다 ( $v<\alpha$ or $v>\beta$ ). 반면에 페일 하드 알파베타 가지치기는 반환하는 값을 알파와 베타의 범위로 제한한다($\alpha \leq v\leq \beta$).

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

역사

앨런 뉴얼과 허버트 사이먼에 따르면, 1958년에 알파베타에 대한 연구가 여러 번 이뤄졌다. 아서 새뮤얼(Arthur Samuel)은 알파베타 프루닝의 초기 버전을 발표했고, Richards, Hart, Levine, Edwards는 알파베타의 기초를 세웠다. 존 매카시도 1956년 다트머스 회의에서 비슷한 아이디어를 내면서 '근사치'라는 용어를 사용했으며, 1961년 매사추세츠 공과대학교에 다니는 앨런 코톡에게도 가르쳤다. 1963년, 알렉산더 브루노(Alexander Brudno)는 알파베타에 대해 독자적으로 발표했으며, 1975년에 도널드 커누스와 로널드 무어가 알고리즘을 재정립했다. 1982년에는 유디 펄이 알파베타 가지치기가 최적임을 증명했다.

특징

알파베타 가지치기의 장점이자 가장 큰 특징은 탐색 트리의 가지를 쳐낼 수 있다는 것이다. 덕분에 탐색 트리의 탐색은 더 가능성 있는 서브 트리에서만 이뤄질 수 있고, 같은 시간 안에 더 깊은 노드까지 탐색할 수 있게 된다. 알파베타 가지치기는 분기 한정법의 일종이다. 노드가 최적 또는 최적에 가까운 순서대로 평가된다면, 탐색하는 깊이가 기본적인 최소극대화의 반 이하가 되도록 최적화할 수 있다. 만약 분기 계수를 b라고 하고, 같은 시간 내에 탐색할 수 있는 가지(ply)의 검색 깊이를 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)$ 이다.

또, 알파베타 가지치기는 노드 생성과 동시에 평가 함수를 적용하는 기능적인 부분에서의 특이점을 갖고 있다. 대부분의 경우에는 모든 노드를 포함한 트리를 생성한 후에 평가 함수를 적용하지만, 알파베타 가지치기는 트리 생성과 동시에 평가 함수를 적용하기 때문에 불필요한 탐색을 피할 수 있다.

예시

• 체스

알고리즘은 알파와 베타라는 두 가지 값을 가지는데, 두 값은 각각 최대화 플레이어가 보장하는 최솟값과 최소화 플레이어가 보장하는 최댓값을 나타낸다. 각각 알파는 음의 무한대, 베타는 양의 무한대로 최악의 점수로 시작한다. 베타 같은 최소화 플레이어의 경우 최대 점수가 최대화 플레이어가 보장되는 최솟값보다 적을 때마다 최대화 플레이어는 실제 플레이에서는 절대 도달할 수 없기 때문에, 이 노드의 추가 하위 노드를 고려할 필요가 없다. 이는 누군가가 체스를 하는 상황을 예로 들어볼 수 있다. 플레이어 A와 B가 겨루고 있을 때, A가 체스 말을 옮기면 판의 흐름은 플레이어 A에게 유리한 방향으로 흘러간다. 그래서 더 좋은 수가 없을까 싶어 플레이어 B가 다음 차례에 체스 말을 옮긴다. B의 수도 좋았지만, 뒤이어 B는 상대방이 말을 두 번 움직이면 체크 메이트를 외칠 수 있다는 것을 깨닫게 된다. 여기서 B가 이동한 후에 강제할 수 있는 최댓값은 음의 무한, 즉 패배다. 이는 이전에 발견된 최소 위치보다 작으며, A가 이동해도 두 번의 이동으로 강제 손실이 발생하지 않는다.

• 오목

렌주 룰(renju rule)을 규칙의 기준으로 15X15 바둑판 오목을 두는 지능적 프로그램을 설계하고 구현한 예시가 있다.문제 분석을 통해 분석된 가중치를 오목에서 돌을 놓을 때 평가 기준으로 두었다. 해당 프로그램에는 최소최대 게임 트리가 사용되었고, 제한된 시간 안에 최대한 신속하게 응답할 수 있도록 알파베타 가지치기가 사용되었다. 먼저 플레이어가 돌을 놓을 차례인 하단 노드에서 가중치를 구한다. 부모 노드가 자식 노드의 가중치 중 가장 큰 값을 선택해야하므로, 노드의 깊이가 홀수인 경우에는 최하단 노드의 부모 노드가 자식의 가중치 중 최솟값을 선택하고, 노드의 깊이가 짝수인 경우에는 최댓값을 선택한다. 이는 부모 노드가 선택한 수를 가장 유리한 수라고 판단해야 오목 프로그램에 적절하게 사용될 수 있기 때문이다. 렌주룰 오목은 오목 돌을 둘 수 있는 자리가 15X15로 총 225칸이다. 초기에 트리 깊이를 3까지 내다본다고 가정했을 때 자신에게 유리하게 돌을 놓을 자리를 계산하면 연산이 필요한 노드 수는 총 225X224X223=11,236,200개가 나온다. 이대로 노드를 구현하면 한 노드에 1us 걸린다고 가정해도 10초가 걸리며, 이를 해결하기 위해 알파베타 가지치기가 적용되었다. 깊이 우선 탐색을 수행하지만, 현재까지 나온 값들을 참고해서 더 탐색할 필요가 없을 때 탐색을 멈출 수 있어, 알파베타 가지치기를 도입하면 약 30% 이상의 효율을 기대할 수 있기 때문이다.

최소극대화 트리를 기반으로 가지치기를 진행하며 최하단 노드로부터 값을 선택한 뒤에는 옆 노드를 방문한다. 만약 선택한 값이 8이고 옆 노드의 자식 노드가 5라고 할 때, 옆 노드 또한 5를 가진다. 여기서 5가 발견된 순간 알고리즘은 이를 방문할 필요가 없다고 판단하고 가지치기한다. 하지만 루트 노드에서 선택하는 것은 최댓값이므로, 8보다 같거나 작은 값이 발견되면 8보다 큰 값이 선택될 수 없어서 이 또한 가지치기한다. 짧은 예시로는 효율성이 크게 느껴지지 않지만, 앞에서 계산한 바와 같이 오목 게임 초기에 노드의 수가 최소 11,239,200개 전개되는 것을 생각하면 알파베타 가지치기는 대략 30% 이상의 가지치기 효율을 기대할 수 있다.

휴리스틱 개선

알파베타 컷오프를 강요할 가능성이 있는 탐색 트리는 초기 부분을 검색하기 위해 순서 휴리스틱을 사용하여 개선할 수 있다. 물론 이 과정에서 정확도는 떨어지지 않는다. 예를 들어 체스의 경우, 게임 트리 분석을 통해 이전 단계에서 높이 평가받은 동작은 다른 동작보다 먼저 평가받을 수 있다. 또 다른 휴리스틱은 킬러 휴리스틱이다. 킬러 휴리스틱은 일반적이고 비용면에서 매우 저렴한 휴리스틱으로, 트리 검색에서 동일한 트리 수준의 베타 차단을 일으킨 마지막 동작이 항상 먼저 검사받는다. 시간에 따라 다른 개선이 제안되기도 했고, 실제로 존 피쉬번(John Fishburn)의 'fail-soft alpha-beta'는 거의 보편적이고 수정된 형태로 통합되었다.

다른 알고리즘

최소극대화 알고리즘과 그 변형은 본질적으로 깊이 우선이기 때문에, 반복 심화와 같은 전략은 일반적으로 알파베타 가지치기와 함께 사용된다. 따라서 알고리즘이 실행을 마치기 전에 중단되더라도 합리적으로 이동할 수 있다. 반복 심화의 또 다른 이점으로는 얕은 검색에서의 이동 순서에 대한 힌트를 제공하는 것이다. 이에 반면 SSS와 같은 알고리즘들은 최상의 전략을 사용한다. 잠재적으로 시간 효율성을 높일 수는 있겠지만, 일반적으로 공간 효율성 면에서는 막대한 비용적 부담이 들 수 있다.

참고자료

• 알파-베타 가지치기 위키백과 - 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
• Alpha-beta pruning 위키백과 - https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning
• 포풍포풍,〈알파-베타 가지치기(Alpha-beta pruning) : 턴제 게임의 인공지능〉, 《티스토리》, 2014-02-15
• 안경잡이개발자,〈(인공지능 강좌) 11. 적대적 탐색〉, 《네이버 블로그》, 2015-12-28
• 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
• 이경호, 한원근, 〈게임 트리와 알파-베타 가지치기를 이용한 오목 프로그램의 설계 및 구현〉, 《한국컴퓨터정보학회 하계학술대회 논문집》, 2018-07

같이 보기

• 알고리즘
• 최소최대 알고리즘

이 알파베타 가지치기 문서는 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 BM25 • FAISS • 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 벡터검색 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 역문서빈도(IDF) • 용어빈도(TF) • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반