주변동 검색

Principal variation search

주요 변동 검색(때로는 실질적으로 동일한 NegaScout과 동일)은 알파 베타 프루닝보다 더 빠를 수 있는 네거맥스 알고리즘입니다.알파 베타 프루닝과 마찬가지로 NegaScout은 트리에서 노드의 최소값을 계산하는 방향 검색 알고리즘입니다.알파 베타 플루닝은 알파 베타에 의해 플루닝될 수 있는 노드를 검사하지 않는다는 점에서 지배적입니다.다만, 이 장점을 이용하려면 정확한 노드 순서에 의존합니다.

NegaScout은 이동 순서가 적절할 때 가장 잘 작동합니다.실제로 이동 순서는 종종 이전의 얕은 곳 검색에 의해 결정됩니다.첫 번째 탐색 노드가 최선이라고 가정하여 알파 베타보다 더 많은 컷오프를 생성합니다.즉, 첫 번째 노드가 주요 변동에 있다고 가정합니다.그런 다음 일반 알파 베타 창에서 검색하는 것보다 빠른 null 창(스카우트 창이라고도 함)을 사용하여 나머지 노드를 검색함으로써 해당 노드가 사실인지 여부를 확인할 수 있습니다.증명에 실패하면 첫 번째 노드가 주 변동에 속하지 않고 일반 알파 베타로 검색이 계속됩니다.따라서 NegaScout은 이동 순서가 적절할 때 가장 잘 작동합니다.랜덤 이동 순서를 사용하면 NegaScout은 일반 알파 베타보다 더 많은 시간이 소요됩니다. 알파 베타가 탐색하지 않은 노드를 탐색하지는 않지만 많은 노드를 다시 검색해야 합니다.

알렉산더 레이네펠트는 알파 베타 가지치기 발명 후 수십 년 후에 NegaScout을 발명했습니다.그는 그의 [1]책에서 NegaScout의 정확성에 대한 증거를 제시한다.

SSS*라고 하는 다른 검색 알고리즘을 사용하면 이론적으로 검색되는 노드의 수가 줄어들 수 있습니다.그러나 원래의 공식은 실질적인 문제를 안고 있으며(특히, 저장을 위해 OPEN 목록에 크게 의존함), 오늘날 대부분의 체스 엔진은 여전히 검색에 NegaScout의 형식을 사용합니다.대부분의 체스 엔진은 검색 트리의 관련 부분이 저장되는 전치 테이블을 사용합니다.트리의 이 부분은 SSS*의 OPEN 목록과 [2]같은 크기입니다.MT-SSS*라고 하는 리폼에서는, 전치 테이블을 사용하는 Alpha-Beta(또는 NegaScout)에의 일련의 늘 윈도우 콜로서 실장할 수 있게 되어, 게임 플레이 프로그램을 사용해 직접 비교할 수 있게 되었습니다.실제로 NegaScout을 능가하지는 않았습니다.그러나 실제로는 NegaScout보다 더 나은 경향이 있는 또 다른 검색 알고리즘은 MTD(f)라고 불리는 최선의 우선 알고리즘이지만, 어느 알고리즘도 다른 알고리즘보다 우세하지 않다.NegaScout이 SSS* 또는 MTD(f)보다 적은 수의 노드를 검색하는 트리가 있습니다.또, 그 반대도 마찬가지입니다.

NegaScout은 1980년 Judea Pearl에 의해 발명된 스카우트를 따랐습니다.이 알고리즘은 알파 베타보다 성능이 뛰어나고 [3][4]점근적으로 최적의 것으로 입증된 최초의 알고리즘입니다.음수 설정에서 β=α+1인 Null 창은 J.P에 의해 독립적으로 발명되었습니다.Fishburn은 박사 [5]논문의 부록, 병렬 알파 베타 알고리즘 [6]및 검색 트리 루트 [7]노드의 마지막 하위 트리에서 스카우트와 유사한 알고리즘에 사용되었습니다.

아이디어

대부분의 움직임은 두 선수 모두 받아들일 수 없기 때문에 정확한 점수를 얻기 위해 모든 노드를 완전히 검색할 필요는 없습니다.정확한 점수는 루트까지 전파될 것으로 예상되는 주요 변동(두 선수 모두 허용 가능한 일련의 움직임)에서만 필요하다.반복적인 심층 검색에서, 이전 반복은 이미 그러한 순서를 확립했다.스코어가 창 안에 있는 노드(PV 노드)에서는 최적이라고 생각되는 첫 번째 동작을 전체 창에서 검색하여 경계를 확립합니다.그것은 다른 움직임이 용납될 수 없다는 것을 증명하기 위해 필요하다.우리는 더 나은 이동이 가능한지 테스트하기 위해 제로 윈도우 검색을 실시했습니다.제로 윈도우 검색은 훨씬 저렴하기 때문에, 많은 수고를 덜 수 있습니다.이동이 알파를 높일 수 있는 경우 전체 창을 사용하여 다시 검색하여 정확한 점수를 얻습니다.[8] [9]

유사 코드

함수 pvs(node, depth, α, β, color)는 깊이 = 0 또는 노드가 터미널 노드인 경우 색상 × 반환하고 어린이가 첫째 아이인 경우 노드의 각 자녀에 대한 노드의 휴리스틱 값을 점수:= -pvs(child, depth - 1, -β, -α, -color) elor eloper := -pvs(child, null, nullor)이다.ndow *) α < 점수 < β이면 점수 := -pvs(child, depth - 1, -β, -score, -color) (* 하이에 실패하면 전체 재검색 실행*) α := max(α, 점수) β가 β이면 β가 반환되고 (* 베타 컷오프 *)가 반환됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ A. 라인펠트스필바움 수크베르파렌Informatik-Fachbericht 200, 베를린, 스프링거-벨라그(1989년) ISBN3-540-50742-6
  2. ^ Plaat, Aske; Jonathan Schaeffer; Wim Pijls; Arie de Bruin (November 1996). "Best-first Fixed-depth Minimax Algorithms". Artificial Intelligence. 87 (1–2): 255–293. doi:10.1016/0004-3702(95)00126-3.
  3. ^ J. Pearl, J., "SCOUT: 입증된 최적 특성을 가진 단순한 게임 검색 알고리즘", 스탠포드 대학, 제1회 인공지능에 관한 전국 연차 회의의 진행, 1980년 8월 18-21페이지 143-145.
  4. ^ 펄, J., "미니맥스 나무의 점근적 특성과 게임 검색 절차", 인공지능, 제14권, 제2호, 페이지 113-138, 1980년 9월.
  5. ^ Fishburn, J.P., "분산 알고리즘에서의 속도 향상 분석", UMI Research Press ISBN 0-8357-1527-2, 1981, 1984.
  6. ^ Fishburn, J.P., Finkel, R.A. 및 Lawless, "Parallel Alpha-Beta Search on Arachne" Proceedings 1980 Int. Conf. Parallel Processing, IEEE, 1980년 8월 26-29일, 페이지 235-243.
  7. ^ Fishburn, J.P., "An Optimization of Alpha-Beta Search" ACM SIGART Bulletin, 제72호, 1980년 7월, 페이지 29-31.
  8. ^ 유대 진주(1980).미니맥스 트리의 점근 특성 및 게임 검색 절차.인공지능 제14권 제2호
  9. ^ 머레이 캠벨, 토니 마스랜드(1983년).Minimax Tree Search 알고리즘 비교인공지능, 제20권, 제4호, 347-367페이지.ISSN 0004-3702

외부 링크