알파베타 가지치기

Alpha–beta pruning
기타 용도에 대해서는 알파벳(동음이의하게 설명)을 참조하십시오.
알파베타 가지치기
학급검색 알고리즘
최악의 경우 성능
베스트 케이스 성능

알파-베타 가지치기는 검색 트리에서 미니맥스 알고리즘에 의해 평가되는 노드의 수를 줄이려는 검색 알고리즘입니다. 2인 콤비네이션 게임(틱택토, 체스, 커넥트 4 등)의 머신 플레이에 일반적으로 사용되는 적대적 검색 알고리즘입니다. 이전에 검토한 동작보다 동작이 더 나쁘다는 것을 증명하는 하나 이상의 가능성이 발견되면 동작 평가를 중지합니다. 이러한 움직임은 더 이상 평가할 필요가 없습니다. 표준 미니맥스 트리에 적용하면 미니맥스와 동일한 움직임을 반환하지만 최종 결정에 영향을 미칠 수 없는 가지를 잘라냅니다.[1]

역사

다트머스 워크숍 동안 존 매카시는 체스 프로그램을 쓰고 있던 IBM의 알렉스 번스타인을 만났습니다. 매카시는 알파 베타 검색을 발명하고 그에게 추천했지만 번스타인은 "확신할 수 없었다"고 말했습니다.[2]

앨런 뉴웰과 허버트 A. 1958년 존 매카시가 "근사"[3]라고 부르는 것을 사용한 사이먼은 알파-베타가 "여러 번 재창조된 것으로 보인다"고 썼습니다.[4] 아서 사무엘은 체커 시뮬레이션을 위한 초기 버전을 가지고 있었습니다. 리차드, 티모시 하트, 마이클 레빈 및/또는 다니엘 에드워즈 또한 미국에서 독립적으로 알파-베타를 발명했습니다.[5] McCarthy는 1956년 Dartmouth 워크숍에서 비슷한 아이디어를 제안했고 1961년 MIT의 Alan Kotok을 포함한 그의 학생 그룹에게 제안했습니다.[6] Alexander Brudno는 독자적으로 알파-베타 알고리즘을 고안하여 1963년에 그의 결과를 발표했습니다.[7] 도널드 크누스(Donald Knuth)와 로널드 W. 무어(Ronald W. Moore)는 1975년에 알고리즘을 개선했습니다.[8][9] 유대 펄은 두 편의 논문에서 무작위로 잎값이 할당된 나무의 예상 실행 시간 측면에서 최적성을 입증했습니다.[10][11] 무작위 버전의 알파-베타의 최적성은 1986년 Michael Saks와 Avi Wigderson에 의해 보여졌습니다.[12]

핵심 아이디어

게임 트리는 체스, 체커, 리버스와 같은 많은 2인용 제로섬 게임을 나타낼 수 있습니다. 트리의 각 노드는 게임에서 가능한 상황을 나타냅니다. 분기의 각 터미널 노드(결과)에는 다음 동작으로 플레이어에게 결과 값을 결정하는 숫자 점수가 할당됩니다.[13]

알고리즘은 알파와 베타의 두 가지 값을 유지하는데, 이 값은 각각 최대화 플레이어가 보장하는 최소 점수와 최소화 플레이어가 보장하는 최대 점수를 나타냅니다. 처음에 알파는 음의 무한대이고 베타는 양의 무한대입니다. 즉, 두 플레이어 모두 최악의 점수로 시작합니다. 최소화 플레이어(즉, "베타" 플레이어)가 보장하는 최대 점수가 최대화 플레이어(즉, "알파" 플레이어)가 보장하는 최소 점수(즉, "베타 < 알파" 플레이어)보다 작을 때마다, 최대화 플레이어는 실제 플레이에서 결코 도달할 수 없기 때문에 이 노드의 더 이상의 후손을 고려할 필요가 없습니다.

이것을 실제 예로 들어 설명하자면, 누군가 체스를 하고 있고, 그들의 차례라고 가정해 보세요. "A"를 움직이면 플레이어의 위치가 향상됩니다. 플레이어는 더 나은 움직임을 놓치지 않기 위해 계속해서 움직임을 찾고 있습니다. "B"를 움직이는 것도 좋은 방법이지만, 플레이어는 두 가지 동작으로 상대가 강제로 체크메이트를 할 수 있다는 것을 깨닫습니다. 따라서, 상대방이 승리를 강요할 수 있기 때문에 더 이상 동작 B를 플레이하는 다른 결과를 고려할 필요가 없습니다. "B"를 이동한 후 상대가 강제할 수 있는 최대 점수는 음의 무한대, 즉 플레이어의 손실입니다. 이는 이전에 발견된 최소 위치보다 작습니다. "A"를 이동해도 두 번의 이동에서 강제로 손실되지 않습니다.

neive minimax에 비해 향상된 성능

알파-베타 가지치기의 예시. 회색으로 표시된 부분 트리는 (왼쪽에서 오른쪽으로 이동을 평가할 때) 탐색할 필요가 없습니다. 부분 트리 그룹은 전체적으로 동일한 부분 트리 또는 더 나쁜 부분 트리의 값을 산출하므로 최종 결과에 영향을 줄 수 없다고 알려져 있기 때문입니다. 최대 레벨과 최소 레벨은 각각 플레이어와 상대의 턴을 나타냅니다.

알파-베타 가지치기의 이점은 검색 트리의 가지를 제거할 수 있다는 사실에 있습니다.[13] 이렇게 하면 검색 시간을 '더 유망한' 하위 트리로 제한할 수 있고, 동시에 더 깊은 검색을 수행할 수 있습니다. 이전 모델과 마찬가지로 분기 및 바인딩된 알고리즘 클래스에 속합니다. 최적화는 노드가 최적 또는 거의 최적의 순서로 평가될 경우 유효 깊이를 단순 최소값의 절반 이상으로 약간 줄입니다(각 노드에서 먼저 순서가 지정된 사이드 온 무브에 대한 최선의 선택).

b의 (평균 또는 상수) 분기 계수와 dplies의 검색 깊이를 사용하여 평가된 리프 노드 위치의 최대 수(이동 순서가 페시멀인 경우)는 O(b×b×...×b) = O(b) – 단순한 최소값 검색과 동일합니다. 검색에 대한 이동 순서가 최적인 경우(항상 가장 좋은 이동이 먼저 검색됨을 의미함), 평가된 리프 노드 위치의 수는 약 O(b×1×b×1×)...홀수 깊이 및 O(b×1×b×1×1)에 대하여 ×b)...×1) 짝수 깊이의 경우 또는 / 2) = O ) {\displaystyle O(b^{d/2}) = O({\sqrt {b^{d}})}입니다. 후자의 경우 검색의 플라이가 짝수인 경우 유효 분기 계수가 제곱근으로 감소하거나 동일한 계산량으로 검색이 두 배 깊이로 이동할 수 있습니다. b×1×b×1×1의 설명... 즉, 첫 번째 플레이어의 모든 동작을 연구하여 가장 좋은 동작을 찾아야 하지만, 각각의 경우 첫 번째(그리고 가장 좋은) 첫 번째 플레이어의 동작을 제외한 모든 동작을 반박하기 위해 두 번째 플레이어의 가장 좋은 동작만 필요합니다. 알파 – beta는 다른 두 번째 플레이어의 동작을 고려할 필요가 없음을 보장합니다. 노드를 무작위 순서(즉, 알고리즘이 무작위화)로 고려할 때, 점근적으로 이진 리프 값을 가진 균일한 트리에서 평가된 예상 노드 수는θ 1 + +b + )/ 4) d ) 4)^{d}입니다. 동일한 트리의 경우, 값이 리프 값에 서로 독립적으로 할당되고 0과 1이 모두 동등하게 가능하다고 말할 때 평가된 예상 노드 수는 위에서 언급한 무작위 알고리즘에 의해 수행된 작업보다 훨씬 작은θ θ((b/ 2 d) / 2d})}입니다. 그리고 그러한 무작위 트리에 다시 최적입니다.[10] 리프 값이 서로 독립적으로 선택되지만[ 1 간격에서 일정하게 임의로 선택되면 평가된 예상 노드 수가 d→∞ d\to \infty } 에서 θ( d /(d)) d / log (d))}로 증가합니다. 이런 종류의 무작위 나무에 최적입니다. 의 "작은" 값에 대한 실제 작업은 0 d을 사용하여 더 잘 추정됩니다[11][10]

노드당 평균 36개의 분기로 4개의 플라이를 검색하는 체스 프로그램은 100만 개 이상의 터미널 노드를 평가합니다. 최적의 알파 베타 프룬은 99.8%[13] 감소한 약 2,000개의 말단 노드를 제외한 모든 노드를 제거할 것입니다.

초기 무한(또는 임의로 큰) 값을 비어 있음에 대체하고 네가맥스 코딩 단순화를 사용하지 않음으로써 인간 친화적이 되려고 시도하는 애니메이션 교육학적 예시.

일반적으로 알파-베타 동안 하위 트리는 일시적으로 첫 번째 플레이어의 이점(많은 첫 번째 플레이어의 움직임이 좋고 각 탐색 깊이에서 첫 번째 플레이어가 확인한 첫 번째 움직임이 적절하지만 모든 두 번째 플레이어의 응답은 반박을 찾기 위해 필요합니다)에 의해 지배됩니다. 이 이점은 이동 순서가 틀릴 경우 검색 중 여러 번 측면을 전환할 수 있으며, 매번 비효율적으로 이어질 수 있습니다. 검색된 위치의 수가 현재 위치에 가까워질 때마다 기하급수적으로 감소하므로 초기 이동을 정렬하는 데 상당한 노력을 기울일 가치가 있습니다. 임의의 깊이에서 개선된 정렬은 검색된 총 위치 수를 기하급수적으로 감소시키지만, 루트 노드 근처의 깊이에서 모든 위치를 정렬하는 것은 그 수가 너무 적기 때문에 상대적으로 저렴합니다. 실제로 이동 순서는 반복적인 심화와 같이 이전의 소규모 검색 결과에 따라 결정되는 경우가 많습니다.

또한 이 알고리즘은 점수 외에 전체 주요 변동을 반환하도록 사소한 수정을 할 수 있습니다. MTD(f)와 같은 더 공격적인 알고리즘은 이러한 수정을 쉽게 허용하지 않습니다.

의사코드

알파-베타 가지치기를 사용한 깊이 제한 최소값에 대한 의사 코드는 다음과 같습니다.[15]

알파-베타 가지치기의 구현은 종종 "실패-소프트"인지 "실패-하드"인지에 따라 설명될 수 있습니다. 페일 소프트 알파-베타의 경우, 알파벳 a 함수는 함수 호출 인수에 의해 설정된 α 및 β 경계(v < α 또는 v > β)를 초과하는 값(v)을 반환할 수 있습니다. 이에 비해 실패-하드 알파-베타는 함수 반환 값을 α와 β의 포함 범위로 제한합니다. Fail-soft 구현과 Fail-hard 구현의 주요 차이점은 α와 β가 컷오프 검사 전 또는 후에 업데이트되는지 여부입니다. 검사 전에 업데이트된 경우 초기 한계를 초과할 수 있으며 알고리즘이 페일 소프트입니다.

다음 의사 코드는 고장 경도 변화를 보여줍니다.[15] 

함수 alphabeta(node, depth, α, β, maximizingPlayer)는 깊이 == 0인 경우 또는 노드가 말단인 경우 노드의 휴리스틱 값을 반환합니다. 최대화Player는 다음 값 := - ∞를 node do value := max(value, alphabeta(child, depth - 1, α, β, FALSE) value > β이면 break (* β cutoff * ) α : = max(α, value) return value else value : = + node do value : = min(value, alphabeta(child, depth - 1, α, β, TRUE)이면 break (* α cutoff *) β : = min(β), value) 반환값 
(* 초기호 *) 알파벳 a(원점, 깊이, -∞, +∞, TRUE)

다음 의사 코드는 페일 소프트 알파-베타를 보여줍니다. 

함수 alphabeta(node, depth, α, β, maximizingPlayer)는 깊이 == 0인 경우 또는 노드가 말단인 경우 노드의 휴리스틱 값을 반환합니다. 최대화Player는 각 노드 do 값의 자식에 대해 := - ∞ 값을 반환합니다. := max(value, alphabeta(child, depth - 1, α, β, FALS) α:= max(α, value) value ≥ β이면 break (* β cutoff *) return value else value : = + node do value : = min(value, alphabeta(child, depth - 1, α, β, TRUE) β : = min(β, value) 값 ≤ α이면 break (* α cutoff *) return value 
(* 초기호 *) 알파벳 a(원점, 깊이, -∞, +∞, TRUE)

휴리스틱 향상

휴리스틱을 명령하여 알파-베타 컷오프를 강제할 가능성이 있는 트리의 초기 부분을 검색함으로써 정확성을 희생시키지 않고 추가적인 개선을 달성할 수 있습니다. 예를 들어 체스에서는 조각을 캡처하는 동작을 그렇지 않은 동작보다 먼저 검사할 수 있으며, 게임 트리 분석을 통해 이전 패스에서 높은 점수를 받은 동작을 다른 동작보다 먼저 평가할 수 있습니다. 또 다른 일반적이고 매우 저렴한 휴리스틱은 항상 트리 검색에서 동일한 트리 수준에서 베타 컷오프를 일으킨 마지막 동작을 먼저 검사하는 킬러 휴리스틱입니다. 이 아이디어는 또한 일련의 반박 테이블로 일반화될 수 있습니다.

알파-베타 검색은 좁은 검색 창(일반적으로 경험에 기반한 추측에 의해 결정됨)만을 고려함으로써 더욱 빠르게 이루어질 수 있습니다. 이것은 열망 창이라고 알려져 있습니다. 극단적인 경우 알파와 베타가 동일한 상태에서 검색이 수행됩니다. 제로 윈도우 검색, 널 윈도우 검색 또는 스카우트 검색이라고 하는 기술입니다. 이는 좁은 창에서 얻은 추가 깊이와 간단한 승패 평가 기능이 결정적인 결과로 이어질 수 있는 게임 종료 근처의 승패 탐색에 특히 유용합니다. 흡인 검색에 실패하면 높은 상태(창문 가장자리가 너무 낮음) 또는 낮은 상태(창문 가장자리가 너무 높음)에서 실패했는지 여부를 쉽게 감지할 수 있습니다. 위치 재검색에 유용할 수 있는 창 값에 대한 정보를 제공합니다.

시간이 지남에 따라 다른 개선 사항이 제안되었으며 실제로 John Fishburn의 Falphabeta(실패-소프트 알파-베타) 아이디어는 거의 보편적이며 약간 수정된 형태로 위에 이미 통합되었습니다. 피쉬번은 또한 킬러 휴리스틱과 제로 윈도우 검색의 조합을 Lalphabeta("최소 윈도우 알파-베타 검색")라는 이름으로 제안했습니다.

기타 알고리즘

미니맥스 알고리즘과 그 변형은 본질적으로 깊이 우선이기 때문에 알고리즘이 실행을 완료하기 전에 중단되더라도 합리적으로 좋은 움직임을 반환할 수 있도록 반복 심화와 같은 전략이 알파-베타와 함께 일반적으로 사용됩니다. 반복적인 심화를 사용하는 또 다른 이점은 얕은 깊이에서의 검색이 이동 순서에 대한 힌트뿐만 아니라 얕은 알파 및 베타 추정치를 제공한다는 것입니다. 둘 다 다른 방법으로 가능한 것보다 훨씬 더 이른 시간에 더 높은 깊이 검색을 위한 컷오프를 생성하는 데 도움이 될 수 있습니다.

반면 SSS*와 같은 알고리즘은 최선의 방법을 사용합니다. 이를 통해 잠재적으로 시간 효율적이지만 일반적으로 공간 효율성에는 큰 비용이 들 수 있습니다.[16]

참고 항목

참고문헌

  1. ^ 러셀 & 노빅 2021, 페이지 152-161.
  2. ^ McCarthy, John (2006-10-30). "The Dartmouth Workshop--as planned and as it happened". www-formal.stanford.edu. Retrieved 2023-10-29.
  3. ^ McCarthy, John (27 November 2006). "Human Level AI Is Harder Than It Seemed in 1955". Stanford University. Retrieved 2006-12-20.
  4. ^ Newell, Allen; Simon, Herbert A. (1 March 1976). "Computer science as empirical inquiry: symbols and search". Communications of the ACM. 19 (3): 113–126. doi:10.1145/360018.360022.
  5. ^ Edwards, D.J.; Hart, T.P. (4 December 1961). The Alpha–beta Heuristic (Technical report). Massachusetts Institute of Technology. hdl:1721.1/6098. AIM-030.
  6. ^ Kotok, Alan (2004) [1962]. "A Chess Playing Program". Artificial Intelligence Project. RLE and MIT Computation Center. Memo 41. Retrieved 2006-07-01.
  7. ^ Marsland, T.A. (May 1987). "Computer Chess Methods" (PDF). In Shapiro, S. (ed.). Encyclopedia of Artificial Intelligence. Wiley. pp. 159–171. ISBN 978-0-471-62974-0. Archived from the original (PDF) on 2008-10-30.
  8. ^ Knuth, Donald E.; Moore, Ronald W. (1975). "An analysis of alpha-beta pruning". Artificial Intelligence. 6 (4): 293–326. doi:10.1016/0004-3702(75)90019-3. S2CID 7894372.
  9. ^ Abramson, Bruce (1 June 1989). "Control strategies for two-player games". ACM Computing Surveys. 21 (2): 137–161. doi:10.1145/66443.66444. S2CID 11526154.
  10. ^ a b c Pearl, Judea (1980). "Asymptotic Properties of Minimax Trees and Game-Searching Procedures". Artificial Intelligence. 14 (2): 113–138. doi:10.1016/0004-3702(80)90037-5.
  11. ^ a b c Pearl, Judea (1982). "The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and Its Optimality". Communications of the ACM. 25 (8): 559–64. doi:10.1145/358589.358616. S2CID 8296219.
  12. ^ a b Saks, M.; Wigderson, A. (1986). "Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees". 27th Annual Symposium on Foundations of Computer Science. pp. 29–38. doi:10.1109/SFCS.1986.44. ISBN 0-8186-0740-8. S2CID 6130392.
  13. ^ a b c Levy, David (January 1986). "Alpha-Beta Soup". MacUser. pp. 98–102. Retrieved 2021-10-19.
  14. ^ Russell & Norvig 2021, 페이지 155.
  15. ^ a b Russell & Norvig 2021, 페이지 154.
  16. ^ Pearl, Judea; Korf, Richard (1987), "Search techniques", Annual Review of Computer Science, 2: 451–467, doi:10.1146/annurev.cs.02.060187.002315, Like its A* counterpart for single-player games, SSS* is optimal in terms of the average number of nodes examined; but its superior pruning power is more than offset by the substantial storage space and bookkeeping required.

서지학