정지 검색
Quiescence search| 이 기사는 에 관한 시리즈의 일부분이다. |
| 체스 프로그래밍 |
|---|
 |
정지 검색은 일반적으로 게임을 하는 컴퓨터 프로그램에서 미니맥스 게임 트리의 불안정한 노드에서 검색을 확장하기 위해 사용되는 알고리즘이다.정적으로 평가될 수 있을 정도로 위치가 안정될 때까지 평가를 미루는 것, 즉 직위의 이력이나 향후 그 직위로부터의 이동을 고려하지 않고 평가하는 것이 평가 기능의 연장이다.체스, 바둑 등 다양한 게임에서 AI 엔진이 직면한 지평선 문제의 효과를 완화한다.
인간의 플레이어는 보통 나쁜 인상을 주는 행동을 버릴지 아니면, 유망한 행동을 아주 깊이 탐구할지를 결정할 수 있는 충분한 직관을 가지고 있다.정지 검색은 컴퓨터에 "휘발성" 위치를 "조용한" 위치보다 더 깊이 검색하여 숨겨진 트랩이 없는지 확인하고 그 값을 더 잘 추정하도록 지시함으로써 이러한 동작을 모방하려고 시도한다.
"조용한" 위치와 "휘발성" 위치를 구별하기 위해 분별 있는 기준을 사용할 수 있다.하나의 공통된 기준은 체스나 바둑에서의 포획과 같이 직위의 가치평가를 획기적으로 변화시킬 수 있는 위치에 움직임이 존재한다는 것이다.정지 검색의 주요 동기는 정적 평가 기능에서 안정적인 값을 얻는 것이므로, 단순 휴리스틱 평가자가 몇 가지 플라이, 즉 이력 기준에 대해 반환하는 값의 큰 변동을 감지하는 것도 이치에 맞을 수 있다.기준에 따라 위치가 변동성을 유지함에 따라 정지 검색이 계속된다.정지 검색이 종료되도록 하기 위해 플라이는 보통 체스에서 포획 및 탈환(흔히 '캡쳐 검색'이라고 함)하는 움직임과 같이 위협을 직접 다루는 동작으로 제한된다.바둑과 리버스티와 같은 매우 "안정되지 않는" 게임에서는 컴퓨터 시간의 상당 부분을 정지 검색에 사용할 수 있다.
수평선 효과
게임 트리의 주어진 노드에서 고정된 깊이까지 모든 이동이 검색될 때 발생할 수 있는 인공지능의 지평선 효과는 문제다.검색 범위를 벗어난 위협과 기회는 발견되지 않은 채로 남아 있을 것이다.이것은 프로그램이 검색 깊이나 "수평"을 넘어 위협을 밀어낼 때까지 위치를 떨어뜨리는 지연 동작을 하는 독특한 계략을 초래할 수 있다.위협을 다루어야 할 때쯤에는 그 지위가 너무 저하되어 인양할 수 없게 되었다.정지 검색은 경험적 값이 이동 사이에 큰 변동이 있을 수 있는 휘발성 위치에서 검색 깊이를 확장하여 이 문제를 완화하려고 시도한다.
가성음
이 유사코드는 개념을 알고리즘적으로 보여준다.
함수 중지_검색(노드, 깊이)은 노드가 조용한 것으로 보이거나 노드가 터미널 노드 또는 깊이 = 0인 경우 다른 노드의 예상 값 반환(정지_search가 있는 반복 검색 노드 하위) 정상_검색(노드, 깊이) 노드가 터미널 노드인 경우 노드의 예상 값을 반환하는 것이다.깊이 = 0인 경우 노드가 정숙하게 나타나는 경우 노드의 예상 값을 반환하지 않고 중지_검색(노드, 합리적_깊이_값)에서 추정 값을 반환하지 않으면(정상_search가 있는 노드 하위 반복 검색) 하위 노드의 예상 값 반환
참조
- Beal, Don (April 1990). "A generalised quiescence search algorithm". Artificial Intelligence. 43: 85–98. doi:10.1016/0004-3702(90)90072-8.
