mir.pe (일반/어두운 화면)
최근 수정 시각 : 2024-02-09 12:05:02

체르멜로 정리

1. 개요2. 증명3. 영향4. 이 정리에 해당하는 게임5. 외부 링크

1. 개요

독일의 수학자 에른스트 체르멜로가 1913년 발표한 정리. 2인 유한 턴제 확정 완전정보(2-person finite alternative deterministic game with complete information and alternating moves) 게임에서, 둘 중 한 명은 반드시 지지 않을 전략을 가지고 있다는 정리이다.

2인 유한 턴제 확정 완전정보 게임이란, 게임을 말한다. 지지 않을 전략이라는 것은 정확히 말하자면, 상대가 최선을 다하더라도 유한한 차례 내에 자신이 이기거나 비기게 만들 수 있는 전략을 뜻한다. 이 경우 영원히 게임이 끝나지 않는 것도 무승부로 간주한다.[1]

여기서 게임에 무승부가 없다는 조건이 추가가 되면( 제로섬 게임과는 다르다. 제로섬 게임에서는 비기는 것도 가능하다.), 지지 않을 전략은 곧 이기는 전략이 되어, 둘 중 한 명이 반드시 필승전략을 갖게 된다.

일부 학자들은 게임에 일부 임의성이 있다고 하더라도 그 정보가 모두에게 공개되는 경우엔 완전정보 게임이라고 간주하기도 한다. 이 정의에 따르면 백개먼이나 주사위 게임 같은 일부 게임도 정리가 성립한다.

보통 게임 이론의 탄생으로 여겨지는 존 폰 노이만의 1944년 저 <게임이론과 경제행동> 보다 30년을 앞서있다보니 학계 일부는 이 정리를 게임이론의 진정한 태동으로 보기도 한다.

2. 증명

증명은 간단하다. 두 플레이어를 각각 A, B라고 하고, A부터 차례를 가진다고 하자.
  1. A에게 지지 않을 전략이 있다면, 정리가 이미 성립한다.
  2. A에게 지지 않을 전략이 없다면, B는 유한한 차례 내에 이길 수 있다.
  3. 즉 B에게 이길 전략이 있다.
  4. 결과적으로 두 플레이어 중 한 명은 반드시 지지 않을 전략이 있다.

위 증명을 논리적으로 더 엄밀하게 풀어 쓰면 다음과 같다. 마찬가지로 A부터 차례를 가질 때,
  1. 선공 A에게 지지 않을 전략이 있다고 가정해보자. 이는 다음 명제 : "선공 A가 후공 B의 모든 전략, 모든 플레이 수순에 대해 게임 결과를 반드시 자신의 승리나 무승부로 만들 수 있다." 가 참이라는 뜻이다. 이 경우 체르멜로 정리가 성립한다.[2]
  2. 앞선 가정이 거짓이라 해보자. 즉 A에게 지지 않을 전략이 없으며 위 명제가 거짓이라 해 보자. 그러면 배중률에 의해 앞선 명제의 부정 명제 : "선공 A는 후공 B의 어떤 전략, 어떤 플레이 수순에 대해서는 게임 결과를 자신의 승리로도 무승부로도 만들 수 없다.[3]" 가 참이 된다.
  3. 이는 후공 B가 필승전략을 가진다는 뜻이다. 따라서 체르멜로 정리가 성립한다.[4]
  4. 즉, 선공 A가 지지 않을 전략을 갖거나, 그렇지 않으면 후공 B가 지지 않을 전략을 갖는다. 모든 경우에 체르멜로 정리가 성립한다.

3. 영향

이 법칙은 지지 않을 전략의 존재는 보장하지만 그 전략이 무엇인지 가르쳐주지는 않는다. 또한 지지 않을 전략이 밝혀진다고 해도 그게 실제로 실행 가능한지는 또 다른 이야기다.

만일 실행 가능한 지지 않을 전략이 알려진다면 그 게임의 수명은 끝난 것이나 다름 없다. 사실상 지지 않을 전략을 가진 사람의 실수만 바라고 하는 게임이 되기 때문이다. 가장 널리 알려진 예는 틱택토[5]나 고누, NIM 게임[6] 등이 있다. 그 밖에도 오목 같은 경우도 고모쿠룰이나 일반룰 같은 간단한 규칙으로 두는 경우는 이미 지지 않을 전략이 너무 잘 알려져 있어서 국제 대회에서는 그러한 규칙을 사용하지 않는다. 이에 대해서는 문서 참조.

바꿔 말하면, 지지 않을 전략이 있다는 걸 알더라도 지지 않을 전략 자체는 알 수 없게 만드는[7] 식으로 어떻게든 이 문제를 피해서 게임을 디자인할 수 있다.

3인 이상에서는 이 정리의 성립이 불가능한데, 두 플레이어가 담합해서 한 명을 무한히 견제할 수 있기 때문하다.

4. 이 정리에 해당하는 게임

운이 가미되어 있지 않고 완전정보가 양측에게 제공되는 2인 유한 턴제 게임 모두가 이에 해당되며, 몇 가지 잘 알려진 예시들이 있다. 지지 않는 전략이 알려져 있는 경우 ★.

5. 외부 링크



[1] 실제 바둑이나 체스, 장기 모두 게임이 무한히 지속될 경우 무승부로 할 수 있는 규칙이 있다. 바둑의 경우 삼패빅, 장생 등의 경우가 있고, 체스의 경우 50수 무승부 및 3회 반복 무승부 등의 룰, 장기의 경우에도 비슷한 룰이 있다. [2] 이 때 후공 B는 지지 않을 전략을 가질 수도, 가지지 않을 수도 있다. [3] 즉 패배할 수 밖에 없다. [4] 필승 전략 역시 지지 않을 전략이다. [5] 3x3 틱택토의 경우 지지 않을 전략을 아주 쉽게 찾을 수 있다. [6] 돌무더기를 앞에 두고 양쪽이 일정량을 가져가서 마지막 돌을 가져가는 사람이 패배하는 게임. 이를 여러명으로 확장한 것이 술게임 배스킨라빈스이다. 필승 전략은 문서 참고. [7] 바둑, 체스 등. 조합론적으로 지지 않을 전략을 찾을 수야 있지만 탐색 공간이 우주만큼이나 넓다. [8] 2인 한정. 근대적인 보드게임들 중 드물게 운적인 요소가 아예 없는 완전정보 게임이므로 이에 해당한다.

분류