게임 트리

이 문서는 유향그래프에 관한 것입니다. 플랫폼에 대해서는 게임트리 (플랫폼) 문서를 참고하십시오.

게임 트리(영어: game tree) 또는 게임 나무는 게임에서 각각의 상황을 수형도로 연결한 유향그래프이다. 이 용어는 전개형 게임중 특히 모든 참여자가 모든 정보를 가지고 두는 게임에서 주로 쓰인다. 인공 지능에서 게임 트리가 중요하게 쓰이는데 체스, 바둑과 같이 매우 복잡한 게임의 경우 앞으로 진행될 몇수에 대한 부분적인 게임 트리를 가지고 최적의 수를 찾는다.

전개형 게임의 게임 트리

용어

• 뿌리는 게임이 시작되는 점을 말한다.
• 가지(branch)는 경기자가 선택하는 각각의 의사결정을 나타내며, 게임 트리에서 실선으로 표시한다.
• 노드(node) 또는 마디는 경기자 중 누군가가 의사결정을 해야 하는 상태 또는 의사결정을 마치고 보수가 주어지는 상태를 표현한다. 게임 트리에서 점으로 표시된다.
• 선도마디(precedent node)는 어느 한 가지가 출발하는 마디를 말한다.

게임 트리의 특징

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

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

같이 보기

• 게임 복잡도