풀린 게임

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

매우 약함

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

약함

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

강함

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

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

사례

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

부분적으로 풀린 게임

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

같이 보기

• 컴퓨터 체스
• 컴퓨터 바둑
• 게임 복잡도