네가막스

Negamax 검색은 2인용 게임의 제로섬 속성에 의존하는 미니맥스 검색의 변형 형태입니다.

This algorithm relies on the fact that ${\displaystyle \max(a,b)=-\min(-a,-b)}$ to simplify the implementation of the minimax algorithm.보다 정확하게 말하면, 이러한 게임에서 플레이어 A에 대한 위치의 값은 플레이어 B에 대한 값의 부정이다.따라서, 이동 중인 플레이어는 이동으로 인한 가치의 부정을 극대화하는 이동을 찾습니다. 즉, 이 후임자 자리는 당연히 상대방이 평가한 것이어야 합니다.앞의 문장의 추론은 A와 B 중 어느 쪽이 이동 중이든 상관없습니다.즉, 단일 절차를 사용하여 두 위치를 모두 평가할 수 있습니다.이는 minimax에 대한 부호화 단순화로, A는 최대값의 successor를 사용한 이동을 선택하고 B는 최소값의 successor를 사용하여 이동을 선택해야 합니다.

1980년대에 발견된 알파 베타 가지치기를 교묘하게 사용하여 미니맥스 또는 네거맥스 값을 빠르게 계산하는 알고리즘인 negascout과 혼동해서는 안 된다.알파 베타 프루닝 자체는 특정 비대상 위치 검색을 피함으로써 위치의 최소값 또는 음의 값을 빠르게 계산하는 방법입니다.

대부분의 적대적 검색 엔진은 네거맥스 검색을 사용하여 코드화됩니다.

네가막스 기저 알고리즘

NegaMax는 미니맥스 검색 알고리즘에서 사용되는 것과 동일한 게임 트리에서 작동합니다.트리의 각 노드와 루트 노드는 2인용 게임의 게임 상태(예를 들어 게임 보드 구성)이다.하위 노드로의 전환은 지정된 노드에서 재생하려는 플레이어가 사용할 수 있는 이동을 나타냅니다.

네거맥스 검색의 목적은 루트 노드에서 플레이하는 플레이어의 노드 점수 값을 찾는 것입니다.다음의 의사 코드는, 최대 검색 심도에 대해서 설정 가능한 제한을 가지는 negamax ^[1]베이스 알고리즘을 나타내고 있습니다.

함수 negamax(노드, 깊이, 색상)는 깊이 = 0 또는 노드가 터미널 노드인 경우 색상 × 노드 값의 휴리스틱 값: = max(value, -negamax(child, depth - 1, -color) 반환 값입니다.

(* 플레이어 A의 루트 노드에 대한 초기 호출*) negamax(루트 노드, 깊이, 1)

(* 플레이어 B의 루트 노드 *) negamax(루트 노드, 깊이, -1)에 대한 초기 호출

루트 노드는 직계 하위 노드 중 하나에서 점수를 상속합니다.궁극적으로 루트 노드의 최고 점수를 설정하는 하위 노드도 최상의 이동 방법을 나타냅니다.표시된 negamax 함수는 노드의 최고 점수만 반환하지만 실제 negamax 구현에서는 루트 노드에 대한 최상의 이동 및 최상의 점수가 모두 유지되고 반환됩니다.비루트 노드에서는 노드의 최고 점수만 필수적입니다.또한 노드의 최선의 이동은 비루트 노드를 유지하거나 반환할 필요가 없습니다.

혼란스러울 수 있는 것은 현재 노드의 휴리스틱 값이 계산되는 방법입니다.이 실장에서는 색값이 1인 플레이어 A의 시점에서 항상 이 값을 산출한다.즉, 휴리스틱 값이 클수록 항상 플레이어 A에게 유리한 상황을 나타냅니다.이것은, 통상의 미니맥스 알고리즘과 같은 동작입니다.휴리스틱 값은 negamax 및 color 매개 변수에 의한 값 부정으로 인해 노드의 반환 값과 같을 필요는 없습니다.negamax 노드의 반환값은 노드의 현재 플레이어의 관점에서 경험적 점수입니다.

Negamax 점수는 플레이어 A가 플레이하려고 하는 노드 및 플레이어 A가 미니맥스 등가의 최대 플레이어인 노드의 미니맥스 점수와 일치합니다.Negamax는 항상 모든 노드의 최대값을 검색합니다.따라서 플레이어 B 노드의 경우 미니맥스 점수는 해당 마이너맥스 점수를 부정하는 것입니다.플레이어 B는 미니맥스 당량의 최소 플레이어입니다.

negamax 구현의 변형은 색상 매개 변수를 생략할 수 있습니다.이 경우 휴리스틱 평가 함수는 노드의 현재 플레이어의 관점에서 값을 반환해야 합니다.

알파 베타 가지치기 기능이 있는 Negamax

미니맥스에 대한 알고리즘 최적화는 Negamax에도 동일하게 적용됩니다.알파 베타 프루닝은 미니맥스 알고리즘과 함께 사용하는 것과 유사한 방법으로 검색 트리에서 네거맥스 알고리즘이 평가하는 노드의 수를 줄일 수 있습니다.

알파 베타 플루닝을 사용한 깊이 제한 네거맥스 검색의 의사 코드는 ^[1]다음과 같습니다.

함수 negamax(노드, 깊이, α, β, 색상)는 깊이 = 0 또는 노드가 터미널 노드인 경우 색상 × 노드 childNodes의 휴리스틱 값:= generateMoves(노드) childNodes:= orderMoves(childNodes) 값:= max(값, -am -negax, childNodes, childNode) 값입니다.max(α, 값)α β이면 반환값 차단(*컷오프 *)

(* 플레이어 A의 루트 노드에 대한 초기 호출*) negamax(루트 노드, 깊이, -depth, +depth, 1)

알파(α)와 베타(β)는 주어진 트리 깊이에서 하위 노드 값의 하한과 상한을 나타냅니다.Negamax는 루트 노드의 인수α 및 β를 가능한 최저 및 최고값으로 설정한다.negascout 및 MTD(f)와 같은 다른 검색 알고리즘은 트리 검색 성능을 더욱 향상시키기 위해 α 및 β를 대체 값으로 초기화할 수 있습니다.

negamax가 알파/베타 범위를 벗어난 자노드 값에 도달하면 negamax 탐색은 게임 트리의 일부를 탐색에서 제거한다.컷오프는 노드 반환값에 따라 암묵적으로 이루어집니다.초기 α 및 β 범위 내에서 발견된 노드 값은 노드의 정확한(또는 참) 값이다.이 값은 음가막스 기본 알고리즘이 반환하는 결과와 동일하며 컷오프 없이 α 및 β 경계 없이 반환됩니다.노드 반환값이 범위를 벗어나면 이 값은 노드의 정확한 값의 상한(α 값일 경우) 또는 하한(β 값일 경우)을 나타냅니다.알파 베타 플루닝은 결국 값 바인딩 결과를 모두 폐기합니다.이러한 값은 루트 노드의 negamax 값에 영향을 주지 않습니다.

이 의사 코드는 알파 베타 플루닝의 페일소프트 변형을 나타내고 있습니다.Fail-soft는 노드 값으로 α 또는 β를 직접 반환하지 않습니다.따라서 노드 값은 negamax 함수 호출에 의해 설정된 초기 α 및 β 범위 범위를 벗어날 수 있습니다.반대로 페일하드 알파 베타 프루닝은 항상 α와 β의 범위에서 노드값을 제한한다.

이 실장에서는 자녀 노드를 평가하는 포어치루프 이전의 옵션의 이동 순서도 표시됩니다.이동^[2] 순서는 알파 베타 프루닝에 대한 최적화로 노드의 점수를 산출하는 가장 가능성이 높은 하위 노드를 추측하려고 시도합니다.알고리즘은 먼저 이러한 하위 노드를 검색합니다.정확한 추측의 결과는 더 빨리 나타나며 알파/베타 컷오프가 더 자주 발생하므로 검색 트리에서 추가 게임 트리 브랜치 및 남아 있는 하위 노드를 제거한다.

알파 베타 가지치기 및 전치표가 있는 Negamax

전치 테이블은 게임 트리 내의 노드 값을 선택적으로 메모한다.전위는 다른 게임 이동 시퀀스를 사용하여 주어진 게임 보드 위치에 여러 가지 방법으로 도달할 수 있다는 용어 참조입니다.

negamax가 게임 트리를 검색하여 같은 노드를 여러 번 마주칠 경우, 치환 테이블은 노드의 값이 길고 중복될 수 있는 재연산을 건너뛰고 이전에 계산된 값을 반환할 수 있다.Negamax의 성능은 특히 동일한 노드에 공통으로 연결되는 경로가 많은 게임 트리에서 향상됩니다.

알파/베타 프루닝으로 negamax에 전치 테이블 함수를 추가하는 의사 코드는 다음과 같습니다.^[1]

함수 negamax(node, depth, α, β, color)는 alphaOrig : =α (*Ttransposition Table Lookup (node)는 ttEntry가 유효하고 ttEntry.depth = intract이면 ttentry 값을 반환합니다.:= max(α, tTEntry.value) else tTEntry.flag = UPERBOUND이면 β : = min (β, tTEntry.value)이고 깊이 = 0 또는 노드가 터미널 노드인 경우 tTEntry.value를 반환하고 색상 × generateMoves(nodes : generateMoves : childNodes) ChildNodes = ChildNodes : = 차일드Nodes : 순서:또는 childNodes의 각 자녀는 값 : = max(value, -negamax(child, depth - 1, -β, -α, -color)α : α β이면 break(* Transposition Table Store, node는 ttEntry *) tTEntry.value = 값이 α인 경우 값입니다.value:tTEntry.flag := LOWERBOUND else tTEntry.flag := EXCRUCT tTEntry.depth := 깊이 transpositionTableStore(노드, ttEntry) 반환값

(* 플레이어 A의 루트 노드에 대한 초기 호출*) negamax(루트 노드, 깊이, -depth, +depth, 1)

알파/베타 프루닝과 네거맥스 내 최대 검색 깊이 제약은 게임 트리 내 노드의 부분적이고 부정확하며 완전히 건너뛴 평가를 초래할 수 있습니다.이로 인해 negamax에 대한 전치 테이블 최적화를 추가하는 작업이 복잡해집니다.값이 노드의 실제 값이 아닐 수 있으므로 테이블에서 노드의 값만 추적하는 것은 충분하지 않습니다.따라서 코드는 알파/베타 매개 변수 및 각 전치 테이블 항목에 대한 검색 깊이와의 값 관계를 보존하고 복원해야 합니다.

전치 테이블은 일반적으로 손실이 발생하며 테이블에서 특정 게임 트리 노드의 이전 값을 생략하거나 덮어씁니다.노드 negamax 방문 수가 종종 전치 테이블 크기를 훨씬 초과하기 때문에 이 작업이 필요합니다.테이블 엔트리의 손실 또는 누락은 중요하지 않으며 negamax 결과에 영향을 주지 않습니다.단, 손실된 엔트리는 특정 게임 트리 노드 값을 더 자주 재계산해야 하므로 성능에 영향을 미칠 수 있습니다.

레퍼런스

• George T. Heineman; Gary Pollice & Stanley Selkow (2008). "Chapter 7:Path Finding in AI". Algorithms in a Nutshell. Oreilly Media. pp. 213–217. ISBN 978-0-596-51624-6.
• John P. Fishburn (1984). "Appendix A: Some Optimizations of α-β Search". Analysis of Speedup in Distributed Algorithms (revision of 1981 PhD thesis). UMI Research Press. pp. 107–111. ISBN 0-8357-1527-2.

외부 링크

• 체스 프로그래밍 위키의 네가막스
• Tic-Tac-Toe 게임용 Negamax 알고리즘 C99 구현