체르멜로 정리
1. 개요
독일의 수학자 어네스트 체르멜로가 1913년 발표한 정리. 두 명이서 하는 모든 게임에는, 현재와 과거의 상태만으로 결정가능한 필승전략이 양쪽 중 적어도 한 쪽에는 반드시 있다는 정리이다.
현재의 정보를 알고 있다는 것이 조건이므로, 가위바위보에서의 필승전략은 상대방이 가위를 내면 바위를 내고… 이런 것이다. 또 카드 게임이라면 현재 상대방이 들고 있는 카드, 앞으로 뽑을 카드 같은 것도 알아야 한다. 그리고 자신의 턴이 필승전략이 없는 턴이면 상대방이 실수하기를 기다리는 수 밖에…
실제로는 과거의 상태만으로 결정가능한 필승전략이 존재함을 보이는 정리도 있는데, 대신 게임자체에 조건이 붙어 복잡해진다.[1] 하지만 체스나 틱택토같은 게임은 주로 턴이라는 개념이 있어 현재의 상태로부터 알 수 있는 정보가 없으니 어차피 상관 없다.
보통 게임 이론의 탄생으로 여겨지는 존 폰 노이만의 1944년 저 <게임이론과 경제행동> 보다 30년을 앞서있다보니 학계 일부는 이 정리를 게임이론의 진정한 태동으로 보기도 한다.
2. 증명
증명은 간단하다. 두 플레이어를 각각 A, B라고 하자.
- A에게는 필승 전략이 있거나 없을 수밖에 없다.(배중률)[2]
- A에게 필승 전략이 있다고 가정한다면 정리가 이미 성립한다. 증명 끝!
- A에게 필승 전략이 없다고 가정한다면(귀류법), A가 어떤 선택을 해도 B의 움직임에 따라 A가 승리하지 못할 수 있다는 것이다.
- 이를 B의 입장에서 다시 말하면, A의 선택에 상관 없이 A가 승리하지 못하게 할 B의 움직임이 반드시 존재하는 것이다.
- 이러한 B의 움직임들은 B의 필승 전략을 이룬다. 따라서 이 경우 B의 필승 전략이 존재한다.
- 결과적으로, A가 필승 전략을 갖거나 B가 필승 전략을 갖는다.(둘 다 필승 전략을 가지게 될 수도 있는데, 이 경우 비기게 된다. 사례가 틱택토)
3. 영향
이 법칙은 필승 전략의 존재는 보장하지만, 그 필승 전략이 무엇인지 가르쳐주지는 않는다. 또한 필승 전략이 밝혀진다고 해도 그게 실제로 실행 가능한지는 또 다른 이야기다. 반면에 '''실행 가능한''' 필승 전략이 알려진다면 그 게임의 수명은 끝난 것이나 다름 없다. 사실상 필승 전략을 가진 사람의 실수만 바라고 하는 게임이 되기 때문인데, 가장 널리 알려진 예는 위에서도 언급한 틱택토나 고누, 돌가르기[3] 등이 있다. 그 밖에도 오목 같은 경우도 고모쿠룰이나 일반룰 같은 간단한 규칙으로 두는 경우는 이미 필승 전략이 너무 잘 알려져 있어서 국제 대회에서는 그러한 규칙을 사용하지 않는다. 이에 대해서는 문서 참조.
바꿔 말하면, 필승 전략이 있다는 걸 알더라도 필승 전략 자체는 알 수 없게 만들거나[4] 현재 정보의 일부에 임의성을 부여하고 플레이어들이 그걸 예측할 수 없게 만듦으로써 필승 전략을 무의미하게 한다든가[5] 하는 식으로 어떻게든 이 문제를 피해서 게임을 디자인할 수 있다.
4. 외부링크
[1] 체스 문서에 있는 2인 확정 유한 완전 정보 게임 언급이 이것에 대한 것이다. [2] 여기서 필승 전략이란, A가 어떤 움직임을 선택한다면 이후의 전개와 상관없이 A가 절대로 지지 않는다(이기거나 비긴다)는 것을 의미한다.[3] 돌무더기를 앞에 두고 양쪽이 일정량을 가져가서 마지막 돌을 가져가는 사람이 패배하는 게임. 이를 여러명으로 확장한 것이 술게임 배스킨라빈스이다. 필승전략은 문서 참고.[4] 바둑, 체스 등. 조합론적으로 필승 전략을 찾을 수야 있지만 영원한 시간이 걸린다.[5] 앞서 언급한 가위바위보 등. 이 경우는 그 임의성이 사실상 승패를 결정짓는다.