제르멜로 정리(게임이론)
Zermelo's theorem (game theory)게임 이론에서, 저멜로의 정리는 플레이어들이 교대로 움직이고 우연이 의사 결정 과정에 영향을 미치지 않는 완벽한 정보의 유한한 2인 게임에 관한 정리입니다. 게임이 무승부로 끝날 수 없다면, 두 플레이어 중 한 명이 승리 전략을 가져야 합니다(즉, 승리를 강요할 수 있음). 다른 진술은 이제 무승부가 가능하다는 조건을 제외한 모든 조건을 충족하는 게임의 경우 첫 번째 플레이어가 승리를 강요하거나 두 번째 플레이어가 승리를 강요하거나 두 플레이어 모두 최소한 무승부를 강요할 수 있다는 것입니다.[1] 이 정리는 1913년 체스의 예제 게임에 대한 정리를 증명한 독일의 수학자이자 논리학자인 에른스트 제르멜로의 이름을 따서 지어졌습니다.
예
저멜로 정리는 완전한 정보와 교대하는 움직임으로 모든 유한 단계 2인 게임에 적용할 수 있습니다. 게임은 다음과 같은 기준을 충족해야 합니다: 게임에는 두 명의 플레이어가 있습니다; 게임은 완벽한 정보를 가지고 있습니다; 보드 게임은 유한합니다; 두 플레이어는 교대로 교대로 할 수 있습니다; 그리고 찬스 요소는 없습니다. Zermelo는 이런 종류의 게임이 많이 있다고 말했지만, 그의 정리는 대부분 체스 게임에 적용되었습니다.[2][3]
체스에 적용할 때, 저멜로의 정리는 "흰색이 승리를 강요할 수도 있고, 검은 색이 승리를 강요할 수도 있고, 양쪽이 적어도 무승부를 강요할 수도 있다"[2][3]고 말합니다.
저멜로의 알고리즘은 게임 이론의 초석이 되는 알고리즘이지만, 유한 게임 이외의 영역에도 적용할 수 있습니다. 체스 외에도 저멜로의 정리는 컴퓨터 과학의 모든 분야에 적용됩니다. 특히 모델 점검 및 가치 상호 작용에 적용됩니다.[4]
제르멜로 정리의 결론
저멜로의 연구는 완벽한 정보를 가진 2인 제로섬 게임에서 한 플레이어가 승리하는 위치에 있다면, 그 플레이어는 다른 플레이어가 어떤 전략을 사용하든 항상 승리를 강요할 수 있다는 것을 보여줍니다. 또한 결과적으로 플레이어가 승리하는 위치에 있을 경우 게임 내 위치보다 더 많은 이동이 필요하지 않습니다(이동할 플레이어뿐만 아니라 조각의 위치로 정의되는 위치).[1]
출판이력
1912년 케임브리지에서 열린 제5차 국제 수학자 대회에서 에른스트 제르멜로는 두 번의 회담을 했습니다. 첫 번째는 수학적 학문의 기초에서 공리적 방법과 유전적 방법을 다루었고, 두 번째 연설은 체스 게임에 관한 것이었습니다. 두 번째 연설은 저멜로가 게임 이론에 관한 논문을 쓰도록 자극했습니다. 열렬한 체스 선수인 저멜로는 체스 게임에 세트 이론을 적용하는 것에 관심이 있었습니다. 이 정리를 설명하는 제르멜로의 원래 논문, "Uberine Anwendung der Mengenlehreuf der Theorye des Schachspiels"는 1913년 독일어로 출판되었습니다. 게임 이론에 관한 최초의 알려진 논문으로 생각할 수 있습니다.[5] 울리히 슈왈베(Ulrich Schwalbe)와 폴 워커(Paul Walker)는 1997년 저멜로의 논문을 영어로 번역하여 저멜로와 게임이론의 초기 역사 부록에 번역본을 실었습니다.[1]
세부 사항
저멜로는 선수들이 엄격하게 대립하는 이해관계를 가지고 있고 유한한 수의 포지션만 가능한 기회 없는 2인 게임 클래스를 고려합니다. 게임에서는 유한하게 많은 포지션만 가능하지만, 저멜로는 규칙을 멈추는 것을 고려하지 않기 때문에 무한한 움직임의 시퀀스를 허용합니다. 따라서 무한한 게임의 가능성을 허용합니다. 그런 다음 그는 두 가지 문제를 해결합니다.
- 플레이어가 '이기는' 위치에 있다는 것은 무엇을 의미하며 이를 객관적인 수학적 방식으로 정의할 수 있습니까?
- 플레이어가 승리 위치에 있을 경우, 승리를 강제하기 위해 필요한 수를 결정할 수 있습니까?
첫 번째 질문에 답하기 위해, Zermelo는 필요하고 충분한 조건은 특정 세트의 비어 있지 않은 상태이며, 다른 플레이어가 플레이하는 방식에 관계없이 승리할 수 있도록 모든 가능한 일련의 동작을 포함한다고 말합니다. 그러나 이 세트가 비어 있으면 플레이어가 달성할 수 있는 최선은 무승부입니다. 따라서 Zermelo는 플레이어가 무한한 수의 움직임에 대해 손실을 연기할 수 있도록 가능한 모든 움직임 시퀀스를 포함하는 또 다른 세트를 정의합니다. 이는 무승부를 의미합니다. 이 세트는 또한 비어있을 수 있습니다. 즉, 플레이어는 상대방이 정확하게 플레이할 경우 유한하게 많은 동작 동안만 손실을 피할 수 있습니다. 그러나 이것은 상대가 승리를 강요할 수 있는 것과 같습니다. 이것은 모든 현대판 제르멜로 정리의 기초입니다.
두 번째 질문에 대해, Zermelo는 게임에서 포지션이 있는 것보다 더 많은 움직임을 취하지 않을 것이라고 주장했습니다. 그의 증명은 모순에 의한 증명입니다. 선수가 포지션 수보다 많은 수에서 승리할 수 있다고 가정합니다. 비둘기집 원칙에 따라 최소 한 번의 우승 자리가 두 번 등장했을 것입니다. 따라서 플레이어는 첫 번째 발생 시 두 번째 발생 시와 동일한 방식으로 경기를 할 수 있었고 따라서 포지션이 있는 경우보다 적은 수의 움직임으로 승리할 수 있었습니다.
1927년 헝가리의 수학자 데니스 코니그는 저멜로의 논문을 수정하고 원본 작업의 일부 공백을 지적했습니다. 우선, 코니그는 제르멜로가 예를 들어 화이트와 같이 승리하는 위치에 있는 선수가 게임 내 위치 수보다 작은 움직임을 보임으로써 항상 승리를 강요할 수 있다는 것을 증명하지 못했다고 주장합니다. 저멜로는 화이트가 관련된 승리 포지션이 있을 가능성이 있는 한 처음부터 행동을 바꿀 수 있으며 반복 없이 승리할 수 있다고 주장했습니다. 그러나 코닝은 한 경기에서 가능한 포지션 수 이하로 이동 수를 줄이는 것만으로는 부족하기 때문에 이러한 주장은 옳지 않다는 입장을 고수하고 있습니다. 따라서, Zermelo는 승리하는 선수가 항상 반복 없이 승리할 수 있다고 주장했지만 보여주지는 않았습니다. Konig의 두 번째 목표는 이 위치에서 블랙이 움직일 차례라면 '첫 번째 위치에서 두 번째 위치와 동일하게 수행하므로 더 적은 움직임으로 승리한다'는 전략을 세울 수 없다는 것입니다. 그러나 제르멜로는 흑과 백 중 두 가지 입장을 다르게 여겼기 때문에 이 주장은 옳지 않습니다.[5]
저멜로 정리와 역귀납
저멜로가 자신의 증명 방법으로 역귀납법을 사용했다고 믿어졌습니다. 그러나 최근 제르멜로 정리에 대한 연구는 역방향 귀납법이 체스 뒤의 전략을 설명하는 데 사용되지 않았음을 보여줍니다. 통념과 달리 체스는 오십진법이나 삼배반복법 중 적어도 하나가 없으면 유한한 게임이 아닙니다. 엄밀히 말하면 체스는 무한한 게임이기 때문에 후진 귀납법은 이 게임에서 minmax 정리를 제공하지 않습니다.[6]
후진 귀납법은 시간을 거슬러 추론하는 과정입니다. 완벽한 정보의 광범위한 폼 게임을 분석하고 해결하는 데 사용됩니다. 이 방법은 마지막에 게임을 시작으로 분석한 다음 역으로 작동하여 시작에 도달합니다. 그 과정에서 백워드 인덕션은 마지막 동작을 한 선수에게 가장 적합한 전략을 결정합니다. 그런 다음 게임의 다음에서 마지막으로 움직이는 플레이어를 위한 궁극적인 전략이 결정됩니다. 게임에서 찾은 모든 포인트에 대해 최고의 액션을 결정하는 과정이 다시 반복됩니다. 따라서 백워드 귀납법은 원래 게임의 모든 하위 게임의 내쉬 균형을 결정합니다.[4]
후진 귀납법이 Zermelo의 원본 논문에 존재하지 않는 이유는 다음과 같습니다.
첫째, Schwalbe and Walker(2001)의 최근 연구는 Zermelo의 논문에 역방향 귀납법에 대한 기본 개념이 포함되어 있음을 보여주었지만, Zermelo는 그 정리에 대해 공식적인 진술을 하지 않았습니다. 저멜로의 독창적인 방법은 비반복의 아이디어였습니다. 후진 유도에 대한 최초의 언급은 1928년 László Kalmarr에 의해 제공되었습니다. 칼마르는 "추상적 게임 이론에 대하여"라는 논문에서 제르멜로와 코니그의 업적을 일반화했습니다. 칼마르는 "승리 포지션을 감안할 때, 얼마나 빨리 승리를 강요할 수 있는가?"라는 질문에 대해 우려했습니다. 그의 논문은 선수가 승리하는 포지션이라는 점을 감안할 때 반복 없이 승리하는 것이 가능하다는 것을 보여주었습니다. 칼마르의 비반복 증명은 역귀납에 의한 증명이었습니다. 칼마르는 논문에서 서브게임과 전술의 개념을 소개했습니다. 칼마르의 핵심 주장은 선수가 유한한 수의 움직임으로 승리할 수 있어야만 포지션이 승리 포지션이 될 수 있다는 것이었습니다. 또한, A 선수의 승리 포지션은 항상 B 선수의 패배 포지션입니다.[7]
참고문헌
- ^ a b c Schwalbe, Ulrich; Walker, Paul. "Zermelo and the Early History of Game Theory" (PDF).
- ^ a b MacQuarrie, John (January 2005). "Mathematics and Chess, Fundamentals". Archived from the original on January 12, 2017.
- ^ a b Aumann, R. J. (1989). Lectures on Game Theory (PDF). Boulder, CO: Westview Press. p. 1.
- ^ a b Wooldridge, Michael (17 March 2015). "Thinking Backward with Professor Zermelo". IEEE Intelligent Systems. 30 (2): 62–67. doi:10.1109/MIS.2015.36. S2CID 12397521. Retrieved 24 April 2021.
- ^ a b Ebbinghaus, Heinz-Dieter (14 October 2010). Ernst Zermelo: An Approach to His Life and Work (2 ed.). Berlin: Springer. p. 150. ISBN 9783642080500. Retrieved 26 April 2021.
- ^ Ewerhart, Christian (May 2002). "Backward Induction and the Game-Theoretic Analysis of Chess". Games and Economic Behavior. 39 (2): 206–214. doi:10.1006/game.2001.0900.
- ^ Schwalbe, Ulrich; Paul, Walker (January 2001). "Zermelo and the Early History Game Theory". Games and Economic Behavior. 34 (1): 123–137. doi:10.1006/game.2000.0794. Retrieved 26 April 2021.
