탐색 게임

탐색 게임 또는 서치 게임(search game)은 탐색 공간이라는 특정 공간에서 벌어지는 두 명의 플레이어 간 전략적 제로섬 게임이다. 서치어라 불리는 한 명의 플레이어는 최대 속도 제한을 준수하면서 연속된 궤적을 선택할 수 있다. 다른 한 명인 히더는 발견 반경 거리가 단정지어지는 순간까지 숨어 있으려고 노력한다.

이 게임에서는 서로가 발견 반경 내에 들어올 때까지 상대방의 움직임을 사전에 알 수 없다. 이 개념은 어린이들이 하는 숨바꼭질부터 전술적 군사 상황의 표현까지 수학적 모델에 적용된다. 탐색 게임 분야는 루퍼스 아이삭스의 고전인 "Differential Games"의 마지막 장에서 처음 소개되었으며, 쉬뮬 갈 과 스티브 알퍼른 같은 학자들에 의해 발전되었다.

공주와 괴물 게임은 움직이는 대상과 관련된 변형된 형태로, 추적이 더 복잡해지는 게임이다.

전략

그래프에서 정지된 대상을 찾기 위한 자연스러운 전략은 모든 아크를 포함하는 최소한의 닫힌 곡선 L을 찾는 것이다. (L은 중국 우체부 투어라고 불린다). 그런 다음 L을 양방향으로 확률 1/2로 탐색한다. 이 전략은 그래프가 오일러 그래프인 경우에는 잘 작동하는 것으로 보인다. 일반적으로, 이 무작위 중국 우체부 투어는 그래프가 트리 모양의 오일러 그래프 집합으로 이루어져 있다면 최적의 탐색 전략이다. 이 그래프가 아닌 경우, 잘못된 단순한 예시로, 세 개의 아크로 연결된 두 노드로 이루어진 그래프가 있다. 무작위 중국 우체부 투어(랜덤한 순서로 세 개의 아크를 탐색하는 것과 동일함)는 최적이 아니며, 이 세 개의 아크를 탐색하는 최적의 방법은 복잡하다.

무제한 도메인

일반적으로, 온라인 알고리즘과 같은 무한 영역을 탐색하는 합리적인 프레임워크는 정규화된 비용 함수를 사용하는 것이다. (컴퓨터 과학 문헌에서 경쟁 비율이라 불림). 이 유형의 문제에 대한 미니맥스 경로는 항상 기하급수적인 시퀀스(또는 연속적인 문제에 대한 지수 함수)이다. 이 결과는 전체 경로 공간을 탐색하는 대신 이 시퀀스의 생성자 중심으로 최소화함으로써 최단 경로를 찾는 간단한 방법을 제시한다. 이 도구는 몇십 년 동안 많은 관심을 받아온 무한 선 상의 타겟을 찾는 선형 탐색 문제에 사용되었으며, 이는 탐색 게임으로 분석되었다. 또한 동시적인 광선 집합을 탐색하는 최소 최대 경로를 찾기 위해 사용되었다. 평면에서의 최적 탐색은 지수적인 나선형을 사용하여 수행된다. 동시적인 광선 집합을 탐색하는 문제는 후에 '소금길 문제'로서 컴퓨터 과학 문헌에서 재발견되었다.