일반 지리학

Generalized geography

계산 복잡도 이론에서 일반화된 지리는 잘 알려진 PSPACE-완전 문제이다.

서론

지리는 아이들이 하는 놀이이며, 플레이어들은 세계 어디에서나 번갈아 가며 도시 이름을 짓는다.선택한 각 도시는 이전 도시 이름을 끝낸 동일한 문자로 시작해야 합니다.반복은 허용되지 않습니다.게임은 임의의 출발도시에서 시작되어 플레이어가 계속할 수 없게 되어 질 때 종료된다.

그래프 모형

게임을 시각화하기 위해, 세계의 각 도시를 노드들로 하는 유향 그래프를 구성할 수 있습니다.도시 라벨2 N이 도시 라벨 노드1 N의 이름을 끝낸 문자로 시작하는 경우에만1 노드 N에서2 노드 N에 화살표를 부가한다.즉, 게임 규칙에 따라 첫 번째 도시가 두 번째 도시로 이어질 수 있다면 우리는 한 도시에서 다른 도시로 화살표를 그립니다.방향 그래프의 각 교대 에지는 각 플레이어에 대응합니다(두 플레이어 게임의 경우).패스를 연장할 수 없는 첫 번째 플레이어가 패합니다.아래 그림에 게임(미시간의 일부 도시 포함)의 그림이 나와 있습니다.

Generalized geography 1.svg

GG(Generalized Geography) 게임에서는 도시 이름 그래프를 임의의 방향 그래프로 대체합니다.다음 그래프는 일반화된 지리 게임의 예입니다.

Generalized geography 2.png

게임하기

P를 1차 이동 플레이어로2, P를 2차 이동 플레이어로 정의하고1 노드1 N에서 N으로n 명명합니다.상기1 그림에서 P는 노드2 N과 노드3 N만을 포인트 하는 당첨1 전략을 가지고 있다.따라서1 P의 첫 번째 동작은 이 두 가지 선택 중 하나여야 합니다.P는1 N을 선택합니다2(P가1 N을 선택하면3 P는2 N을 유일한 옵션으로 선택하고91 P는 패합니다).다음2 P는 N을 선택합니다4.N이 유일한 선택이기 때문입니다.P는1 N을 선택하고52 P는 N 또는 N을7 선택합니다3.P의 선택에 관계없이2 P는1 N을 선택하고92 P는 남은 선택지가 없어 게임에서 집니다.

계산의 복잡성

일반 지리 게임에서 어떤 플레이어가 승리 전략을 가지고 있는지 결정하는 문제는 PSPACE-complete입니다.

일반화된 지리는 PSPACE에 있습니다.

GG = { gG, b1 } P가 노드 b }에서 시작하는 그래프 G에서 실행되는 일반화 지리 게임의 승리 전략을 가지고 있다고 하자. GG p PSPACE를 나타내기 위해 우리는 어느 플레이어가 승리 전략을 가지고 있는지를 결정하는 다항 공간 재귀 알고리즘을 제시한다.GG, "Gstart, n" 인스턴스의 경우 G는 유도 그래프, n은start 지정 시작 노드입니다.알고리즘 M은 다음과 같이 진행됩니다.

M('G, nstart'):

  1. 노드start n의 out-degree를 측정합니다.이 정도가 0이면 반환한다.플레이어 1에 사용할 수 있는 이동이 없기 때문에 거부합니다.
  2. n에서 도달start 가능한 모든 노드의 목록을 n, n2, n, ..., ni 에지로 작성합니다1.
  3. G에서 n과 n에 연결된 모든 엣지를start 제거하여1 G를 형성합니다.
  4. 리스트1 n, ..., ni 의 각 노드j n 에 대해서, M( 「G1, nj」)을 호출합니다.
  5. 이러한 콜이 모두 받아들여지면 P가 어떤 결정을1 내리든 P는 승리하기2 위한 전략을 가지고 있기 때문에 Reject를 반환한다.그 이외의 경우(콜 중 하나가 reject를 반환하는 경우1) P에는 P에 대한2 성공한 전략을 거부하는 옵션이 있으므로 accept를 반환하십시오.

알고리즘 M은 GG를 명확하게 결정한다.소비되는 눈에 띄지 않는 다항식 워크스페이스만 재귀 스택에 있기 때문에 PSPACE에 있습니다.재귀 스택이 소비하는 공간은 다항식입니다.재귀의 각 레벨은 스택에1개의 노드를 추가하기 때문입니다.여기서 n은 G의 노드 수입니다.이는 기본적으로 깊이 우선 검색과 동일합니다.

일반화된 지리는 PSPACE-hard

다음 증거는 데이비드 리히텐슈타인과 마이클 [1]십서에게 있다.

GG의 PSPACE-hardness를 확립하기 위해 다항식 시간(P)에 FORMAL-GAME 문제(PSPACE-hard로 알려져 있음)를 GG로 줄일 수 있다.간단히 말해서, FORMAL-GAME 문제의 인스턴스는 정량화된 부울 공식 φ = xx1 xx2 xx3 ...로 구성됩니다.Qxk(')는 " 또는 " 중 하나입니다.게임은 P와 P의e 두 플레이어가a 번갈아 연속된 x의i 값을 선택합니다. 공식e ends가 참이면 P가 이기고a ends가 거짓이면 P가 승리합니다.식 θ는 접속 정규형이라고 가정한다.

이 증명에서는 단순성을 위해 수량화 리스트가 존재 한정자 ,로 시작 및 종료된다고 가정합니다.에 표시되지 않는 더미 변수를 추가하면 모든 식을 이 형식으로 변환할 수 있습니다.

Generalized geography 3.png

위와 같은 그래프 G를 작성함으로써 P의 최적1 전략은 P의 최적e 전략과 동등하고 P의 최적2 전략은 P의 최적a 전략과 동등한 Generalized Geography의 인스턴스로 축소할 수 있음을 알 수 있다.

노드의 왼쪽 수직 체인은 FORMAL-GAME 변수 값을 선택하는 절차를 모방하도록 설계되어 있습니다.각 다이아몬드 구조는 정량화된 변수에 대응합니다.플레이어는 각 분기 노드에서 돌아가면서 경로를 결정합니다.첫 번째 수량자가 존재한다고 가정했기 때문에 P는1 먼저 x가 참이면1 왼쪽 노드를 선택하고 x가 거짓이면 오른쪽1 노드를 선택합니다.그런 다음 각 플레이어는 강제로 돌아가며 P는2 x 값을 선택합니다2.이러한 교대 할당은 왼쪽 아래로 계속됩니다.두 플레이어가 모든 다이아몬드를 통과하고 나면, 우리는 마지막 수량자가 존재한다고 가정했기 때문에 다시1 P의 차례가 된다.P는1 그래프의 오른쪽 경로를 따를 수밖에 없습니다.그러면 P가 움직일 차례야2.

플레이가 그래프의 오른쪽에 있을 때, 그것은 공식 게임의 플레이의 끝과 유사합니다.공식 게임에서는 θ가 참이면 P가 이기고ea θ가 거짓이면 P가 이긴다는 점에 유의하십시오.그래프의 오른쪽은 P가 이긴 경우에만e P가 이기고1 P가 이긴 경우에만a P가2 이기는 것을 보증합니다.

먼저 P가 이겼을a 때 P가 항상 이긴다는2 것을 보여줍니다.P가 이기면a false가 됩니다.①이 false일 경우 불만족스러운 조항이 존재합니다.P는2 만족스럽지 못한 조항을 선택하여 이긴다.그리고 P의 차례가 되면1 그는 P가 선택한2 절에서 리터럴을 선택해야 한다.절의 모든 리터럴이 false이므로 왼쪽 수직 체인에서 이전에 방문한 노드에는 연결되지 않습니다.이를 통해 P는 왼쪽 체인의 다이아몬드에 있는 해당 노드에 대한 연결을 추적하여 선택할 수 있습니다2.다만1, P는 인접 노드를 선택할 수 없게 되어 없어집니다.

이제 우리는 P가 이겼을e 때 항상 P가 이긴다는1 것을 보여줍니다.P가 이기면e is가 됩니다." 가 true일 경우 그래프 우측의 모든 구에 진정한 리터럴이 포함됩니다.P는2 임의의 절을 선택할 수 있습니다.그런1 다음 P는 참인 리터럴을 선택합니다.그리고 그것이 사실이기 때문에 왼쪽 수직 노드의 인접 노드가 이미 선택되었기 때문에2 P는 움직일 수 없고 손실됩니다.

PSPACE-완전 평면 일반 지리

일반화된 지리는 평면 그래프에서 재생되는 경우에도 PSPACE-완전입니다.다음 증명은 [1]의 정리 3에서 나온 것이다.

평면 GG는 GG의 특수한 경우이며, GG는 PSPACE에 있으므로 평면 GG는 PSPACE에 있습니다.평면 GG가 PSPACE-hard임을 나타내는 것은 아직 남아 있습니다.이것은 임의의 그래프를 평면 그래프로 변환하는 방법을 보여줌으로써 증명될 수 있으며, 이 그래프에서 실행되는 GG 게임이 원래 그래프와 같은 결과를 얻을 수 있다.

그러기 위해서는 원래 그래프의 모서리 교차를 모두 제거하면 됩니다.한 점에서 세 개의 가장자리가 교차하지 않도록 그래프를 그리고 두 개의 가장자리가 같은 게임에서 모두 사용될 수 없도록 그립니다.이것은 일반적으로 가능하지 않지만 FORMAL-GAME 인스턴스에서 생성된 그래프에서는 항상 가능합니다. 예를 들어 교차에 관련된 절 정점의 가장자리만 가질 수 있습니다.이제 각 교차로를 이 구조로 교체합니다.

The intersection is eliminated by adding 9 vertices and redrawing the edges as shown.

결과는 평면 그래프이며, 같은 플레이어는 원래 그래프와 같이 승리를 강요할 수 있습니다. 변환된 게임에서 플레이어가 V에서 "위로" 이동하도록 선택할 경우, 두 플레이어는 계속해서 "위로" 이동하거나 즉시 패해야 합니다.변형된 게임에서 V에서 "위로" 이동하면 원래 게임에서 V→W 이동이 시뮬레이션됩니다.V→W가 승부수라면, 변형된 게임에서 V에서 "업"하는 것도 승부수이며, 그 반대도 마찬가지입니다.

따라서 변환된 그래프에서 실행되는 GG 게임은 원래 그래프와 동일한 결과를 얻을 수 있습니다.이 변환에는 원래 그래프에 있는 모서리 교차점의 수에 대한 상수 배수인 시간이 걸리기 때문에 다항식 시간이 걸립니다.

따라서 평면 GG는 PSPACE-완전입니다.

최대도 3의 평면 이분 그래프

최대 도수가 3인 평면 이분 그래프에서 재생되는 GG는 3보다 높은 도수의 정점을 최대 도수가 3인 정점의 체인으로 대체함으로써 여전히 PSPACE-완전이다.Proof는 다음과 같은 구조를 사용합니다.[1]

Generalized geography 3-planar transformation.svg

한 플레이어가 이 건물의 출입구 중 하나를 사용할 경우, 다른 플레이어는 사용할 출구를 선택합니다.또한 중심 정점은 항상 방문되기 때문에 구성을 한 번만 통과할 수 있습니다.따라서 이 구성은 원래 정점과 동일합니다.

엣지리

GG의 변형은 에지 지리라고 불리는데, 각 이동 후에 플레이어가 통과한 에지가 지워집니다.이것은 원래 GG와 대조적으로, 각 이동 후에 플레이어가 있던 정점이 지워집니다.이 뷰에서 원래 GG는 정점 지리라고 할 수 있습니다.

엣지 지리는 PSPACE-완전입니다.이것은 정점 [2]지리에 사용된 것과 같은 구조를 사용할 수 있다.

무방향 지리

또한 지리 게임을 무방향 그래프(즉, 모서리를 양방향으로 횡단할 수 있음)로 플레이하는 것도 고려할 수 있습니다.Fraenkel, Sheinerman 및 Ullman은[3] 무방향 정점 지리는 다항식 시간에 풀 수 있는 반면, 무방향 엣지 지리는 최대 도수가 3인 평면 그래프에서도 PSPACE-완전함을 보여준다.그래프가 초당인 경우 무방향 에지 지리는 다항식 시간으로 해결할 수 있습니다.

결과들

GG가 PSPACE-완전이라면, P = PSPACE가 아닌 한 GG에서 최적의 플레이를 위한 다항 시간 알고리즘은 존재하지 않는다.그러나 특정 게임(체스 등)에는 한정된 수의 게임 위치가 포함되어 있어 PSPACE-완전 문제에 대한 매핑을 작성하는 것이 어렵거나 불가능하기 때문에 다른 게임의 복잡성을 증명하는 것은 쉽지 않을 수 있습니다.그럼에도 불구하고, 특정 게임의 복잡성은 일반화를 통해 여전히 분석될 수 있다(예: n × n 보드).GG의 완전성을 증명하는 결과로 일반화된 바둑에 대한 증명은 참조를 참조하십시오.

레퍼런스

  1. ^ a b c Lichtenstein, David; Sipser, Michael (April 1980). "Go Is Polynomial-Space Hard" (PDF). Journal of the ACM. 27 (2): 393–401. doi:10.1145/322186.322201.
  2. ^ Schaefer, Thomas J. (1978). "On the complexity of some two-person perfect-information games". Journal of Computer and System Sciences. 16 (2): 185–225. doi:10.1016/0022-0000(78)90045-4.
  3. ^ Fraenkel, Aviezri; Scheinerman, Edward; Ullman, Daniel (1993). "Undirected edge geography". Theoretical Computer Science. 112 (2): 371–381. doi:10.1016/0304-3975(93)90026-p.
  • Michael Sipser, PWS, 1997.