게임 복잡도

1. 개요

게임 복잡성은 게임의 난이도를 측정하는 척도로, 주 공간 복잡성, 게임 트리 크기, 의사결정 트리, 계산 복잡성 등 다양한 요소로 평가된다. 주 공간 복잡성은 도달 가능한 게임 위치의 경우의 수를 의미하며, 게임 트리 크기는 가능한 모든 게임 플레이의 경우의 수를 나타낸다. 의사결정 트리는 각 위치의 가치를 평가하는 데 사용되며, 계산 복잡성은 게임을 해결하는 데 필요한 자원과 시간을 나타낸다. 게임별 복잡성은 틱택토, 체스, 바둑 등 다양한 게임을 예시로 들어 상태 공간, 게임 트리, 평균 게임 길이, 분기 계수 등을 비교하여 설명한다.

2. 게임 복잡성 측정

게임의 복잡성은 다양한 방법으로 측정될 수 있다. 이 섹션에서는 게임 복잡성을 측정하는 몇 가지 방법에 대해 설명한다.

아래 표는 다양한 게임들의 복잡성을 나타낸다. 게임 복잡성이 크기 때문에 로그의 밑은 10을 사용한다.

2.1. 주 공간 복잡성

게임의 주 공간 복잡성은 게임을 처음 위치에서 시작했을 때 도달할 수 있는 합법적인 게임 위치의 수이다. 게임을 계산하기 너무 어려울 때는 가끔 일부 속임수를 써서 상한을 계산할 수도 있는데, 이는 게임 과정에서 절대 일어날 수 없는 포지션을 의미한다.

2.2. 게임 트리 크기

게임 트리 크기는 게임을 시작하여 나올 수 있는 모든 경우의 수를 나타내는 것으로, 게임의 초기 위치를 루트로 하는 게임 트리의 잎 노드 수이다.

게임 트리는 일반적으로 상태 공간 크기보다 훨씬 크다. 동일한 위치가 서로 다른 순서로 움직여 여러 게임에서 발생할 수 있기 때문이다. 예를 들어, 틱택토 게임에서 보드에 X 두 개와 O 하나가 있는 위치는 첫 번째 X의 위치에 따라 두 가지 다른 방식으로 도달할 수 있다. 게임 트리 크기의 상한은 게임 트리 크기를 증가시키는 방식으로(예: 불법적인 움직임을 허용) 게임을 단순화하여 계산할 수 있다.

보드 크기 또는 위치 반복에 대한 규칙에 의해 이동 횟수가 제한되지 않는 게임의 경우, 게임 트리는 일반적으로 무한하다.

2.3. 의사결정 나무

의사결정 트리는 게임의 특정 상태에서 최적의 수를 찾기 위한 의사 결정 과정을 나타내는 트리 구조이다. 각 위치는 "플레이어 A 승리", "플레이어 B 승리", "무승부" 중 하나로 표시된다. 이는 그래프 내 다른 위치를 통해 해당 값을 증명할 수 있을 때(양측의 최적 플레이 가정)를 기준으로 한다.

터미널 위치(게임의 최종 상태)는 바로 표시할 수 있다. 플레이어 A가 이동할 차례인 위치는 A에게 승리하는 다음 위치가 있으면 "플레이어 A 승리", 모든 다음 위치가 B에게 승리하면 "플레이어 B 승리", 모든 다음 위치가 무승부이거나 B에게 승리하면 "무승부"로 표시한다. B가 이동하는 위치도 이와 유사하게 적용된다.

2.3.1. 의사 결정 복잡성

게임의 초기 위치의 가치를 확립하는 최소 의사 결정 트리의 리프 노드 수이다.

2.3.2. 게임 트리의 복잡성

게임의 트리 복잡성은 초기 위치의 가치를 결정하는 가장 작은 전체 너비 의사결정 트리의 리프 노드 수이다. 전체 너비 트리는 각 깊이에 있는 모든 노드를 포함한다.

이것은 초기 위치의 값을 결정하기 위해 미니맥스 검색에서 평가해야 할 위치의 수에 대한 추정치이다.

게임 트리의 복잡성을 추정하기는 어렵지만, 일부 게임의 경우 게임의 평균 분기 계수 b를 평균 게임의 수 d만큼 거듭제곱하여 근사값을 구할 수 있다.

:$GTC\; \backslash geq\; b^d$

2.4. 계산 복잡성

게임의 계산 복잡성은 게임이 임의적으로 커질 때, 즉 빅 오 표기법이나 복잡도 클래스의 멤버십으로 표현될 때 나타나는 점증적 난이도를 설명한다. 이 개념은 특정 게임이 아니라, n-by-n 보드에서 게임을 함으로써 임의적으로 크게 만들 수 있도록 일반화된 게임들에 적용된다.

점증적 복잡성은 게임을 해결하기 위해 가장 효율적인 알고리즘에 의해 정의된다. 가장 일반적인 복잡성 측정(컴퓨팅 시간)은 가능한 모든 경우에 솔루션 알고리즘이 작동해야 하기 때문에 점증적 상태-공간 복잡성의 로그에 의해 항상 경계를 낮춘다. 그것은 게임 패밀리에 작용하는 어떤 특정한 알고리즘의 복잡성에 의해 상한선이 될 것이다. 유사한 언급이 두 번째로 일반적으로 사용되는 복잡성 측정치, 즉 계산에 사용되는 공간이나 컴퓨터 메모리의 양에도 적용된다. 알고리즘이 게임 상태를 저장할 필요가 없기 때문에 일반적인 게임의 공간 복잡성에 하한선이 있다는 것은 명백하지 않다. 그러나 관심 있는 많은 게임들은 PSPACE-hard로 알려져 있고, 그들의 공간 복잡성은 점증적 상태-공간 복잡성의 로그에 의해 하한선이 될 것이다.

* 깊이 우선 미니맥스 전략은 전체 트리를 탐구해야 하기 때문에 게임의 트리-복잡성에 비례하는 계산 시간과 알고리즘이 가능한 각 이동 깊이에 트리의 한 노드를 항상 저장해야 하기 때문에 트리-복잡성의 로그에 메모리 다항식의 양이 사용되며, 그리고 가장 높은 이동 깊이에서 노드 수를 항상 저장해야 하기 때문이다.
* 후진 귀납법은 각 가능한 위치에 대해 정확한 이동을 계산하고 기록해야 하므로 상태-공간 복잡성에 비례하는 메모리와 시간을 모두 사용한다.

3. 게임별 복잡성

3.1. 틱택토

틱택토는 3x3 크기의 보드에서 진행되는 게임으로, 가능한 상태의 상한은 3⁹ = 19,683이다. 하지만 이 중에는 5개의 X가 있고 O가 없는 경우나, 두 플레이어 모두 3개의 행을 가진 경우 등 불가능한 경우도 포함되어 있다. 이러한 불가능한 경우를 제외하면 5,478가지의 상태가 존재한다. 또한, 위치의 회전 및 반사를 고려하면 765개의 본질적으로 다른 위치만 남는다.

게임 트리를 살펴보면, 초기에는 9가지 가능한 이동이 있고, 그 다음에는 8가지 가능한 응답이 있는 등 최대 9! = 362,880개의 게임이 가능하다. 하지만 실제로는 9번 미만의 이동으로 게임이 끝날 수 있으므로, 가능한 게임은 255,168개이다. 여기서 위치의 회전 및 반사를 고려하면 26,830개의 가능한 게임만 남는다.

틱택토의 계산 복잡성은 일반화 방식에 따라 달라진다. 일반적인 m,n,k-게임은 m x n 크기의 보드에서 진행되며, k개를 연속으로 먼저 놓는 플레이어가 승리한다. 이 게임은 전체 게임 트리를 검색하여 DSPACE(mn)에서 해결할 수 있으며, 이는 PSPACE 복잡도 클래스에 해당한다. 더 나아가 PSPACE-완전 문제임이 밝혀졌다.

3.2. 차이니즈 체커

샹치^중국어에 대한 내용은 중국 장기 문서를 참고하고, Chinese Checkers^영어에 대한 내용은 차이니즈 체커 문서를 참고하라.

주어진 소스에는 차이니즈 체커에 대한 내용이 없다. 따라서, 섹션 제목에 해당하는 내용을 작성할 수 없다.