게임 복잡도

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

게임 복잡도(Game complexity)는 체스, 바둑, 장기와 같은 조합론적 게임 이론에서 게임이 얼마나 복잡한지를 나타낸다.

종류[편집]

위치 복잡도[편집]

위치 복잡도는 올바른 행마를 통해 처음 상태에서 도달할 수 있는 말의 위치의 수이다.

게임 트리 크기[편집]

게임 트리의 크기는 모든 가능한 게임의 수를 나타낸다. 하지만 이것은 움직이는 수가 제한되지 않은 경우, 또는 반복에 제한이 없는 경우 무한이 될 수도 있다..........

게임 트리 복잡도[편집]

게임 트리 복잡도는 모든 가능한 노드의 수를 가리킨다.

계산 복잡도[편집]

게임에서 최적의 수를 찾기 위한 계산의 복잡도를 점근 표기법에 따라 나타낼 수 있다. 하지만 특정한 게임에서 필요한 계산은 유한하기 때문에, 어떤 게임을 임의로 크게 일반화할 수 있는 경우에 정의할 수 있다.