풀린 게임

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

풀린 게임은 대국자가 완벽한 수를 두었을때 게임의 결과를 알아낸 것을 말한다. 2인용게임의 해결 단계는 아래와 같다.

[1][2]

매우 약함

초기 상태에서 시작할때 승,무,패중 어느쪽으로 만들 수 있는지만 결정된 상태. 실제 대응수를 밝혀내지 못한 비구성적 증명일수도 있다.

약함

초기 상태에서 시작할때 두어가는 수에 따라 한쪽이 이기거나, 어느쪽도 비기게 만들 수 있거나하는 완벽한 수가 양 선수에게 알려진 상태.

강함

어느 상태에 대해서도 완벽한 최선의 수를 결정하는 알고리듬이 찾아낸 상태. 두명이서 두는 유한가지 경우의 게임은 미니맥스 원리에 따라 게임 트리를 만들 수 있다.

풀린 게임과 그 게임을 두는 사람의 흥미는 직접적인 연관은 없다. 매우 약하게 해결된 게임이라도 필승법이 알기 쉬운 경우 흥미를 잃을 수 있고 반대로 필승법이나 필무법을 알기 어려운 경우 흥미에 영향을 받지 않는다.

사례[편집]

  • Hex: 존 내시가 만든 따라하기 전략을 통해 정사각형 판형에서 첫 번째 사람이 지지 않음을 증명했다. 비길 수 없으므로 첫사람이 이김을 뜻한다. 판의 크기가 정사각형이 아닌 경우 짧은 변을 만들어야 하는 사람이 이긴다.
  • 마하라자와 세포이 세포이쪽이 이긴다.
  • 오목 아무 제한도 없는 경우 흑이 이긴다. 현재 15x15판까지 흑이 이김이 알려졌다.
  • 님게임
  • 나인 멘스 모리스

부분적으로 풀린 게임[편집]

  • 체스 역분석으로 킹을 포함해 기물이 6개 이하인 경우 해결되었다.
  • m,n,k-게임

주석[편집]

  1. V. Allis, Searching for Solutions in Games and Artificial Intelligence. PhD thesis, Department of Computer Science, University of Limburg, 1994. Online: pdf
  2. H. Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck, Games solved: Now and in the future, Artificial Intelligence 134 (2002) 277–311.