Alpha-Beta Pruning
많은 사람들이, 한 판의 바둑 (baduk) 에 몰입한 조치훈 9단의 모습을 보면 '세상 고민을 혼자 다 짊어지고 가는 사람 같다'는 말을 합니다. 구도(求道)의 가시밭길을 걷는 수행자가 따로 없다는 거죠. ..... 누가 보아도 뻔한 곳에서 장고(長考)에 장고를 거듭하는 것이 지극히 당연한 일인지도 모릅니다. 오래 전 장고에 관련된 고백 비슷한 인터뷰를 읽은 기억이 납니다. 라이벌 고바야시 고이치 9단과 비유를 하고 있더군요. '나는 고바야시 9단을 보면 부럽다. 그는 생각의 줄기를 알맞게 잘라낼 줄 아는 사람이다. 더 이상 생각해봐야 도움이 되지 않는 곳을 잘 알고 제 때에 가지치기 (pruning) 를 한다. 나는 그게 안된다. 끝없이 생각의 가지가 뻗어나간다. 그 끝에 닿지 않으면 불안해서 견딜 수가 없고 비슷한 길이 나오면 그 선택에서도 갈등이 심하다.' ..... '단점인 줄은 알지만 고치지 못한다' 는 마무리말에서 어떤 숙명 같은 것이 느껴지더군요. ..... source (고바야시는 휴리스틱 탐색 (Heuristic Search) 를 하고 조치훈은 무정보 탐색 (Uninformed or Blind Search) 를 한다. ? )
Alpha-beta pruning 은 게임 (Game) 플레이어가 분석 해본 결과 명백하게 관심이 없어진 (상대에게는 중요할 수 있는지도 모르지만) 탐색 트리의 가지들을 더 이상 탐색 (Search) 하지 않는 기술이라고 간단하게 설명할 수 있다. .... Arthur Samuel
.... 컴퓨터 프로그램과 관련된 2 개의 값을 알파와 베타 라고 임의로 정한 것이다. 그것이 fred-jim pruning, p-q pruning, foo-bar pruning 라고 불러도 상관없다. 알파 베타 절단을 사용함으로써 얻는 이점은 체스 챔피언 카스파로프가 당신에게 다음 돌의 움직임을 가르쳐주는 것을 상상하여 보면 된다..... Alpha-beta pruning (알파 베타 절단) : A. N. Walker : Game Theory
... Alpha-beta pruning 은 두명이 참여하는 게임을 위한 최소최대 (Mini-max) 알고리즘에 의해 평가되는 노드들의 수를 감소시키기 위한 기술이다. 즉 게임에서 상대방은 절대 도달하지 못하도록 나에게만 유리하게 탐색트리의 일부분을 잘라내는 것이다..... Alpha-beta pruning을 가진 minimax 는 가지치기를 하지 않는 minimax 와 같은 결과를 보이지만 훨씬 더 효율적이다. 보통 효율적인 분기요소 (branching factor) 를 square root 까지 감소시키고, 같은 시간내에 탐색할 수 있는 가지 (ply) 의 수를 두배로 만든다. .... 두 값 알파와 베타는, maximizing player 가 보장하는 (assured of) 최소 점수이며 마찬가지로 minimizing player 가 보장하는 최대 점수를 나타낸다. 처음에 알파는 마이너스 무한대 (minus infinity) 베타는 플러스 무한대 이다. 그 과정이 반복됨에 따라 "window" 는 더 작게된다. 베타가 알파보다 작게되면, 그것은 현재의 위치가 두 플레이어에 의한 가장 좋은 플레이의 결과일 수 없다는 것을 의미하고, 따라서 더 이상의 탐색은 할 필요가 없게된다. ... Wikipedia : Alpha-beta pruining
term :
인공지능 (Artificial Intelligence) 체스 (Chess) 바둑 (baduk) 게임 (Game) 탐색 (Search) 게임 이론 (Game Theory)
site :
Wikipedia : Alpha-beta pruining
paper :
알파 베타 방법 (The Alpha-Beta Procedure) : Nils J.Nilsson
"덩어리" 만들기 [응축] 와 체스 실력 : Douglas R. Hofstadter