풀린 게임

풀린 게임은 대국자가 완벽한 수를 두었을 때 게임의 결과를 알아낸 것을 말한다. 2인용 게임의 해결 단계는 아래와 같다.V. Allis, Searching for Solutions in Games and Artificial Intelligence. PhD thesis, Department of Computer
Science, University of Limburg, 1994. Online: pdfH. 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.

매우 약함

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

약함

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

강함

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

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

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

 부분적으로 풀린 게임 
 체스 역분석으로 킹을 포함해 기물이 6개 이하인 경우 해결되었다.
 m,n,k-게임
 체커 미국 식 룰에서는 무승부로 알려져 있다.

 같이 보기 
 컴퓨터 체스
 컴퓨터 바둑
 게임 복잡도
 각주 

분류:조합론적 게임 이론
분류:수학 게임