알파베타 가지치기

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

개요

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

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

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

최소최대 알고리즘을 예시로 알파베타 가지치기를 설명하자면 다음과 같다.

MAX 

ⓐ

MIN 

ⓑ ⓒ

MAX 

ⓓ ⓔ ⓕⓖⓗ

MIN 

ⓘ ⓙⓚ ⓛ ⓜⓝ ⓞⓟ

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 자리로 움직이는 것도 좋다는 것을 알게되었다. 하지만 뒤이어 플레이어는 상대방이 말을 두번 움직이면 체크 메이트를 외칠 수 있다는 것을 깨달았다. 따라서 B가 이동한 후에 강제할 수 있는 최댓값은 음의 무한, 즉 패배다. 이는 이전에 발견된 최소 위치보다 작으며, A가 이동해도 두 번의 이동으로 강제 손실이 발생하지 않는다.

• 오목 :

참고자료

• 알파-베타 가지치기 위키백과 - 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 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반