게임 트리

3. 게임 트리의 특징

게임 트리는 다음과 같은 특성을 가진다.^[7]

• 선도마디와 연결되는 가지는 단 하나이다.
• 어느 한 가지의 출발 마디와 도착 마디가 같을 수 없다. 만약 출발 마디와 도착 마디가 같다면 의사결정을 할 것인지 의사결정을 한 결과에 도달한 것인지 구분할 수 없게 된다.
• 임의의 마디에서 시간을 거슬러 올라가면 유일한 게임의 뿌리에 도달하게 된다.

4. 게임 트리 이해

게임 트리는 대결 게임을 분석하여 플레이어가 승리하기 위해 취하는 행동을 결정하는 기법이다. 게임 이론에서 게임 트리는 노드가 게임의 위치(예: 보드 게임에서 말의 배열)이고 에지가 이동(예: 보드의 한 위치에서 다른 위치로 말을 이동)인 유향 그래프이다.^[1]

확장형 게임 표현에서 얻은 트리와 동일한, 초기 위치에서 시작하여 각 위치에서 가능한 모든 이동을 포함하는 게임 트리를 '''완전 게임 트리'''라고 한다.

게임 트리는 인공 지능에서 중요한데, 체스와 같은 더 큰 게임의 완전 게임 트리는 탐색하기에 너무 크기 때문이다. 그래서 체스 프로그램은 '''부분 게임 트리'''를 탐색한다. 일반적으로 현재 위치에서 사용 가능한 시간 내에 탐색할 수 있는 수만큼의 수를 탐색한다. "병리적" 게임 트리의 경우^[3]를 제외하면 탐색 깊이를 늘릴수록 최상의 수를 선택할 확률이 높아진다. 게임에서 최상의 수를 선택하는 방법은 수많은 트리 탐색 알고리즘 중 하나를 사용하여 게임 트리를 탐색하고, 트리를 가지치기하는 미니맥스와 같은 규칙을 결합하는 것이다.

2인 게임은 AND-OR 트리로도 나타낼 수 있는데, 선공 플레이어가 이기려면 후공 플레이어의 모든 수에 대해 승리하는 수가 존재해야 한다. 이는 AND-OR 트리에서 선공 플레이어의 대안적인 수를 나타내는 데 논리합을 사용하고 후공 플레이어의 모든 수를 나타내는 데 논리곱을 사용하여 표현된다.

4. 1. 완전 게임 트리의 구성 요소

• 이해관계자가 취할 수 있는 행동의 순서
• 각 의사결정 지점에서의 선택
• 각 이해관계자가 의사결정을 내릴 때 다른 이해관계자가 취한 행동에 대한 정보
• 모든 가능한 게임 결과의 이점

4. 2. 예시: 틱택토

5. 게임 트리 해결

완전한 게임 트리가 있다면 게임을 "해결"할 수 있다. 즉, 첫 번째 또는 두 번째 플레이어가 어떤 경로로 게임을 진행해야 하는지 알 수 있고, 그 경로를 따르면 최소한 지지 않는다는 것을 보장할 수 있다.^[4]

완전 게임 트리가 주어지면 게임을 푸는 방법은 다음과 같다.

# 최종적인 판면에서 플레이어 1이 이기는 판면은 파란색, 플레이어 2가 이기는 판면은 빨간색, 비기는 판면은 회색으로 칠한다.

# 한 수 전(판면)을 보고, 그 레벨의 판면이 되는 수를 자신의 수로 한다. 상대가 이기는 판면이 자식 노드로 하나라도 존재하면, 이 노드를 상대의 색으로 칠한다. 바로 아래 자식 노드의 색이 모두 같다면 이 노드도 같은 색으로 칠한다. 그렇지 않으면 비기는 색으로 칠한다.

# 위 과정을 순차적으로 반복하여 모든 노드를 색칠한다. 루트 노드의 색깔에 따라 이 게임의 성질이 결정된다.

오른쪽 그림은 위의 알고리즘에 따라 색칠한 게임 트리를 나타낸 것이다.

많은 게임에서, 동일한 플레이어에게 유리한 다른 수가 있다면 특정 수를 분석할 필요가 없기 때문에, 게임 트리의 일부만 사용하여 게임을 해결하는 것이 가능하다. (예: 알파-베타 가지치기)

5. 1. 결정적 알고리즘 (역진귀납법/역행 분석)

5. 2. 난수화 알고리즘

6. 게임 트리와 인공지능

게임 트리는 인공 지능에서 중요한데, 게임에서 최상의 수를 선택하는 한 가지 방법이 여러 트리 탐색 알고리즘 중 하나를 사용하여 게임 트리를 탐색하고, 트리를 가지치기하는 미니맥스와 같은 규칙을 결합하는 것이기 때문이다.^[1] 체스와 같은 복잡한 게임의 완전 게임 트리는 탐색하기 어렵기 때문에, 체스 프로그램은 부분 게임 트리를 탐색한다. 일반적으로 현재 위치에서 사용 가능한 시간 내에 탐색할 수 있는 수만큼의 수를 탐색한다. "병리적" 게임 트리의 경우^[3]를 제외하고는 탐색 깊이(탐색된 수의 개수)를 늘리면 일반적으로 최상의 수를 선택할 확률이 높아진다.

2인 게임은 AND-OR 트리로도 나타낼 수 있다. 선공 플레이어가 게임에서 이기려면 후공 플레이어의 모든 수에 대해 승리하는 수가 존재해야 한다. 이는 AND-OR 트리에서 선공 플레이어의 대안적인 수를 나타내는 데 논리합을 사용하고 후공 플레이어의 모든 수를 나타내는 데 논리곱을 사용하여 표현된다.

7. 게임 복잡도

완전한 게임 트리가 있다면 게임을 "해결"할 수 있다. 즉, 첫 번째 또는 두 번째 플레이어가 따라갈 수 있는 수순을 찾아 그 플레이어에게 최상의 결과(일반적으로 승리 또는 무승부)를 보장할 수 있다. 결정적 알고리즘(일반적으로 역진귀납법 또는 역행 분석이라고 함)은 다음과 같이 재귀적으로 설명할 수 있다.

# 게임 트리의 마지막 수를 플레이어 1의 승리는 한 가지 색(다이어그램에서는 파란색), 플레이어 2의 승리는 다른 색(다이어그램에서는 빨간색), 무승부는 세 번째 색(다이어그램에서는 회색)으로 칠한다.

# 그다음 수를 살펴본다. 현재 플레이어와 반대되는 색으로 칠해진 노드가 있다면, 이 노드도 해당 플레이어의 색으로 칠한다. 바로 아래의 모든 노드가 같은 플레이어의 색으로 칠해져 있다면, 이 노드도 같은 플레이어의 색으로 칠한다. 그렇지 않으면 이 노드를 무승부 색으로 칠한다.

# 모든 노드가 색칠될 때까지 위쪽으로 이동하면서 각 수에 대해 이 과정을 반복한다. 루트 노드의 색은 게임의 성격을 결정한다.

많은 게임에서 동일한 플레이어에게 더 유리한 다른 수가 있다면 특정 수를 분석할 필요가 없기 때문에(예: 알파-베타 가지치기는 많은 결정적 게임에서 사용될 수 있음) 게임 트리의 일부만 사용하여 게임을 해결하는 것이 일반적으로 가능하다.

게임을 해결하는 데 사용할 수 있는 모든 하위 트리는 '''결정 트리'''로 알려져 있으며, 다양한 형태의 결정 트리 크기는 게임 복잡도의 척도로 사용된다.^[4]

참조

_[1] 논문 Avoiding game-tree pathology in 2-player adversarial search https://onlinelibrar[...] 2018
_[2] 논문 A novel optimization model based on game tree for multi-energy conversion systems https://www.scienced[...] 2018-05-01
_[3] 논문 An investigation of the causes of pathology in games 1982
_[4] 서적 Searching for Solutions in Games and Artificial Intelligence http://fragrieu.free[...] Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands 1994
_[5] 서적 SI486D: Randomness in Computing, Game Trees Unit https://web.archive.[...] United States Naval Academy, Computer Science Department 2013-04-29
_[6] 논문 Review of Kalah Game Research and the Proposition of a Novel Heuristic–Deterministic Algorithm Compared to Tree-Search Solutions and Human Decision-Making 2020-09
_[7] 서적 게임이론: 전략과 정보의 경제학 박영사 2018