알파베타 가지치기

알파베타 가지치기(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의 자식들은 탐색할 필요가 없기 때문에 굳이 탐색할 필요가 없는 노드들을 가지치기하여 탐색 시간 자원을 절약한다. 바둑 인공지능의 경우 바둑을 트리로 표현하면 $250^{1}50$개의 노드를 갖게 되므로, 알파베타 가지치기가 바둑 인공지능 구현에는 매우 비효율적이라는 견해도 있다.

역사

앨런 뉴얼과 허버트 사이먼에 따르면, 1958년에 알파베타에 대한 연구가 여러번 이뤄졌다. 아서 새뮤얼은 알파베타 프루닝의 초기 버전을 발표했고, Richards, Hart, Levine, Edwards는 알파베타의 기초를 세웠다. 존 매카시도 1956년 다트머스 회의에서 비슷한 아이디어를 내면서 '근사치'라는 용어를 사용했으며, 1961년 매사추세츠 공과대학교에 다니는 앨런 코톡에게도 가르쳤다. 1963년,

의사코드

다음은 페일 소프트(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

참고자료

• 알파-베타 가지치기 위키백과 - 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

같이 보기

• 알고리즘

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

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