체르멜로 정리

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

1. 개요

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

2인 유한 턴제 확정 완전정보 게임이란,

2인(2-person): 둘이서 하는
유한(finite): 게임 상태의 수가 유한한
턴제(alternating moves): 둘이 번갈아 가면서 행동을 결정하는
확정(deterministic): 행동에 따른 게임 상태의 변화가 운에 의해 결정되지 않고 확정적인
완전정보(complete information): 게임의 (모든) 상태가 양쪽 플레이어에게 알려져 있는

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

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

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

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

2. 증명

증명은 간단하다. 두 플레이어를 각각 A, B라고 하고, A부터 차례를 가진다고 하자.

A에게 지지 않을 전략이 있다면, 정리가 이미 성립한다.
A에게 지지 않을 전략이 없다면, B는 유한한 차례 내에 이길 수 있다.
즉 B에게 이길 전략이 있다.
결과적으로 두 플레이어 중 한 명은 반드시 지지 않을 전략이 있다.

위 증명을 논리적으로 더 엄밀하게 풀어 쓰면 다음과 같다. 마찬가지로 A부터 차례를 가질 때,

선공 A에게 지지 않을 전략이 있다고 가정해보자. 이는 다음 명제 : "선공 A가 후공 B의 모든 전략, 모든 플레이 수순에 대해 게임 결과를 반드시 자신의 승리나 무승부로 만들 수 있다." 가 참이라는 뜻이다. 이 경우 체르멜로 정리가 성립한다.[2]
앞선 가정이 거짓이라 해보자. 즉 A에게 지지 않을 전략이 없으며 위 명제가 거짓이라 해 보자. 그러면 배중률에 의해 앞선 명제의 부정 명제 : "선공 A는 후공 B의 어떤 전략, 어떤 플레이 수순에 대해서는 게임 결과를 자신의 승리로도 무승부로도 만들 수 없다.[3]" 가 참이 된다.
이는 후공 B가 필승전략을 가진다는 뜻이다. 따라서 체르멜로 정리가 성립한다.[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인 한정. 근대적인 보드게임들 중 드물게 운적인 요소가 아예 없는 완전정보 게임이므로 이에 해당한다.