조합 게임 이론

CGT(Combinatory Game Theory)는 수학 및 이론 컴퓨터 과학의 한 분야로, 일반적으로 완벽한 정보를 가진 순차적 게임을 연구합니다.연구는 주로 정해진 방식으로 번갈아 가거나 정해진 승리 조건을 달성하기 위해 이동하는 포지션을 가진 2인용 게임으로 제한되었습니다.CGT는 전통적으로 운명의 게임이나 불완전하거나 불완전한 정보를 사용하는 게임을 연구하지 않았으며,^[1] 게임의 상태와 이용 가능한 일련의 움직임을 항상 알고 있는 완벽한 정보를 제공하는 게임을 선호한다.그러나 수학 기술이 발전함에 따라 수학적으로 분석할 수 있는 게임의 종류가 확대되어 그 분야의 경계가 끊임없이 ^[2]변화하고 있다.학자들은 일반적으로 논문의 첫머리에서 "게임"이 의미하는 바를 정의합니다.이러한 정의는 분석 대상 게임에만 한정되어 있고 해당 분야의 전체 범위를 나타내기 위한 것이 아니기 때문에 종종 달라집니다.

콤비네이션 게임에는 사소하다고 여겨지는 체스, 체커, 바둑과 같은 유명한 게임과 "해결하기 쉽다"는 의미에서 사소하다고 여겨지는 틱택토 등이 있다.어떤 조합 게임들은 무한 체스와 같은 무한 플레이 영역을 가지고 있을 수도 있다.CGT에서 이러한 게임과 다른 게임에서의 움직임은 게임 트리로 표현됩니다.

조합 게임에는 스도쿠와 같은 1인 조합 퍼즐이나 콘웨이의 게임 오브 라이프와 같은 노플레이어 오토마타가 포함되어 있습니다(가장 엄격한 정의에서는 게임에는 1인 이상의 참가자가 필요하다고 할 수 있습니다).따라서 "퍼즐"과 "오토마타"^[3]의 명칭이 있습니다).

게임 이론에는 일반적으로 우연의 게임, 불완전한 지식의 게임, 플레이어가 동시에 움직일 수 있는 게임이 포함되며, 그것들은 실제 의사결정 상황을 나타내는 경향이 있다.

CGT는 처음에는 단순한 조합 구조를 가진 게임을 연구하기 위해 개발된 "전통적인" 또는 "경제적인" 게임 이론과는 다른 강조점을 가지고 있다(순차적인 움직임도 고려하지만 광범위한 형태의 게임 참조).본질적으로 CGT는 게임 트리를 분석하기 위한 새로운 방법을 제공했습니다. 예를 들어 초현실적인 숫자를 사용하는 것은 모든 2인용 완벽한 정보 ^[3]게임의 하위 클래스입니다.CGT에 의해 연구된 게임의 종류 또한 인공지능, 특히 자동화된 계획과 스케줄링에 관심이 있다.CGT에서는 (대부분의 인공지능 교과서에 포함된 알파-베타 가지치기 휴리스틱과 같은) 실용적인 검색 알고리즘의 정교화에 대한 강조는 덜했지만, 기술적 이론적 결과(알고리즘을 반드시 명시하지 않고 게임 복잡성 측정 또는 최적의 솔루션 존재 증명과 같은)에 대한 강조는 더 많았다.h)를 strategy-module 인수로 지정합니다.

CGT에서 중요한 개념은 해결된 게임의 개념입니다.예를 들어, 틱택토우는 두 플레이어가 최적으로 플레이하면 어떤 게임이든 무승부가 된다는 것을 증명할 수 있기 때문에 해결된 게임으로 간주됩니다.풍부한 조합 구조를 가진 게임에서 유사한 결과를 도출하는 것은 어렵습니다.예를 들어, 2007년에 체커가 약하게 해결되었다고 발표되었는데, 양측의 최적 플레이는 무승부로 이어졌지만, 이 결과는 컴퓨터 지원의 ^[4]증거였다.다른 현실 세계의 게임들은 대부분 너무 복잡해서 오늘날 완전한 분석을 할 수 없다. 비록 이 이론이 최근에 바둑 엔드게임을 분석하는 데 성공했지만 말이다.위치에 CGT를 적용하면 게임이 종료될 때까지 양쪽 플레이어의 최적의 이동 시퀀스를 결정하고, 이를 통해 어떤 위치에서든 최적의 이동을 발견할 수 있습니다.실제로 이 과정은 게임이 매우 간단하지 않으면 고문적으로 어렵다.

주로 수학자와 과학자들이 고민하고 풀어야 할 관심의 조합적인 "수학 게임"과 오락과 경쟁의 ^[5]한 형태로서 일반 대중들에게 관심 있는 조합적인 "놀이 게임"을 구별하는 것은 도움이 될 수 있습니다.하지만, 많은 게임들이 두 가지 카테고리로 분류된다.예를 들어, Nim은 CGT의 기초가 된 플레이 게임 도구이자 최초의 컴퓨터 게임 ^[6]중 하나입니다.틱택토(Tic-tac-toe)는 여전히 컴퓨터 공학 ^[7]학생들에게 게임 AI 디자인의 기본 원리를 가르치는 데 사용되고 있다.

역사

조합 게임 이론은 한 플레이어가 이용할 수 있는 모든 플레이를 다른 플레이어도 이용할 수 있어야 하는 공평한 게임의 이론과 관련하여 생겨났다.그런 게임 중 하나가 님인데, 완전히 해결될 수 있다.님은 두 선수에게 공평한 경기로 정상적인 플레이 조건, 즉 움직일 수 없는 선수가 지는 게임입니다.1930년대에, 스프래그-그룬디 정리는 모든 공정한 게임이 님에 있는 무더기와 동등하다는 것을 보여주었고, 따라서 조합적인 수준에서 고려되는 게임에서는 주요 통합이 가능하다는 것을 보여주었고, 그 결과뿐만 아니라 세부적인 전략이 중요하다.

1960년대에 엘윈 R. Berlekamp, John H. Conway, Richard K. 가이는 한 명의 플레이어가 플레이를 이용할 수 있다는 조건이 완화되는 당파적 게임의 이론을 공동으로 도입했다.그들의 결과는 1982년 그들의 책인 Winning Ways for your Mathemical Plays에 발표되었습니다.하지만, 이 주제에 대해 출판된 첫 번째 작품은 ONAG로도 알려진 Conway의 1976년 책 On Numbers and Games입니다. 이 책은 초현실적인 숫자의 개념과 게임의 일반화를 소개했습니다.On Numbers and Games는 또한 Berlekamp, Conway, 그리고 Guy의 협업의 산물이었다.

조합게임은 일반적으로 한 사람이 다른 사람이 더 이상 움직이지 않을 때 이기는 형태로 되어 있다.두 가지 결과만 있는 유한 게임을 이 규칙이 적용되는 경우 동등한 게임으로 변환하는 것은 쉽습니다.조합 게임 이론에서 가장 중요한 개념 중 하나는 두 게임의 합이다. 두 게임은 각 플레이어가 게임의 어느 한 지점에서든 움직일 수 있고, 상대방이 어느 한 게임에서든 움직일 수 없을 때 승리하는 게임이다.게임을 결합하는 이러한 방법은 풍부하고 강력한 수학적 구조를 이끌어낸다.

콘웨이는 On Numbers and Games에서 당파적 게임의 이론의 영감은 바둑 엔드게임에서의 플레이에 대한 그의 관찰에 기초하고 있다고 말했다. 바둑 엔드게임은 종종 보드의 다른 부분에서 서로 격리된 단순한 엔드게임의 합으로 분해될 수 있다.

예

소개 텍스트 Winning Ways는 많은 게임을 소개했지만, 소개 이론의 동기 부여 사례로 다음과 같은 것이 사용되었습니다.

• Blue-Red Hackenbush - 유한 수준에서, 이 당파적 조합 게임은 2진수 유리수의 가치를 가진 게임을 구성할 수 있습니다.무한한 수준에서, 초현실적인 숫자의 클래스에 속하는 많은 무한한 가치들뿐만 아니라 모든 실제 가치들을 구성할 수 있게 해준다.
• 파란색 – 빨간색 – 녹색 Hackenbush - 전통적인 의미의 숫자가 아닌 추가 게임 값을 허용합니다(예: 별).
• 두꺼비와 개구리 - 다양한 게임 값을 사용할 수 있습니다.대부분의 다른 게임과 달리, 위치는 짧은 문자열로 쉽게 표현됩니다.
• 지배 - 핫 게임과 같은 다양한 흥미로운 게임들이 지배의 포지션으로 등장합니다. 왜냐하면 때로는 움직이려는 동기가 있고 때로는 그렇지 않기 때문입니다.이를 통해 게임의 온도를 논의할 수 있습니다.
• 님 - 공정한 게임입니다.이를 통해 민첩성을 확보할 수 있습니다.(청-적-녹색 해켄부시의 녹색 전용 사례로도 볼 수 있습니다.)

고전 게임인 Go는 초기 조합 게임 이론에 영향을 미쳤고, Berlekamp와 Wolfe는 그 후에 그것을 위한 최종 게임과 온도 이론을 개발했다(참고 자료 참조).이것으로 무장함으로써 그들은 바둑 전문가들에게 어느 쪽이든 선택할 수 있는 그럴듯한 바둑 종반 위치를 구축할 수 있었다.

조합 게임 이론의 맥락에서 연구된 또 다른 게임은 체스이다.1953년 앨런 튜링은 이 게임에 대해 다음과 같이 썼다. "필요한 경우 수학적 기호의 도움을 받아 영어로 아주 명확하게 설명할 수 있다면, 어떻게 계산해야 하는지, 저장 용량이 ^[8]충분하다면, 디지털 컴퓨터가 그 계산을 하도록 프로그래밍하는 것은 언제나 가능하다."1950년 논문에서 클로드 섀넌은 체스의 게임 트리 복잡도의 하한을 10으로¹²⁰ 추정했고, 오늘날 이것은 섀넌 ^[9]수치로 언급된다.비록 슈퍼컴퓨터의 사용을 포함한 광범위한 연구가 체스 엔드게임 테이블베이스를 만들어냈지만 체스는 여전히 미해결 상태로 남아 있다. 이것은 7피스 이하의 모든 엔드게임에 대한 완벽한 플레이의 결과를 보여준다.무한 체스는 체스보다 훨씬 더 큰 조합 복잡성을 가지고 있습니다(단, 제한된 엔드 게임이나 소수의 피스들로 구성된 위치가 연구되지 않는 한).

개요

게임은, 가장 간단한 용어로, 왼쪽과 오른쪽이라고 불리는 두 명의 플레이어가 만들 수 있는 가능한 "움직임"의 목록입니다.어떤 움직임으로 인한 게임 포지션은 다른 게임으로 간주할 수 있다.게임을 다른 게임으로 이동할 수 있는 관점에서 보는 이 아이디어는 조합 게임 이론에서 표준인 게임의 재귀적 수학적 정의를 이끌어냅니다.이 정의에서는 각 게임의 표기는 {L R}입니다.L은 왼쪽 플레이어가 이동할 수 있는 게임 위치 집합이고, R은 오른쪽 플레이어가 이동할 수 있는 게임 위치 집합이며, L과 R의 각 위치는 동일한 표기법을 사용하여 게임으로 정의됩니다.

예를 들어, 4×4 보드의 16개의 상자 각각에, 왼쪽 상단 정사각형에는 A1, 왼쪽 상단부터 두 번째 줄에 있는 세 번째 상자에는 C2로 라벨을 붙입니다.예를 들어 (D3, D4)를 사용하여 오른쪽 하단에 수직 도미노가 배치된 게임 위치를 나타냅니다.그러면, 초기 위치는 조합 게임 이론 표기법으로 설명될 수 있습니다.

$\displaystyle \{(\mathrm {A} 1,\mathrm {A} 2,\mathrm {B} 2,\dots \mathrm {A} 1,\mathrm {B} 1,\mathrm {B} 2,\dots \ .}$

표준 크로스 크램 플레이에서 플레이어는 번갈아 돌아가며 플레이하지만, 이 대체는 게임 상태 내에서 인코딩되기보다는 조합 게임 이론의 정의에 의해 암묵적으로 처리됩니다.

$\displaystyle \{(\mathrm {A} 1,\mathrm {A} 2) (\mathrm {B} 1)=\{\} \{\} \} \}\}.}$

위의 게임은 어느 한 플레이어에게 한 번의 움직임만 남고, 어느 한 플레이어가 그 동작을 하면 그 플레이어가 승리하는 시나리오를 기술하고 있습니다(C3의 관련 없는 열린 사각형은 다이어그램에서 제외되었습니다).각 플레이어의 이동 목록에 있는 { }(이동 후 남은 1개의 정사각형에 해당)을 제로 게임이라고 하며, 실제로는 0으로 줄여서 사용할 수 있습니다.제로 게임에서는 어느 쪽도 유효한 움직임이 없기 때문에 제로 게임이 시작되면 차례가 된 플레이어가 자동으로 패한다.

위 그림의 게임 종류도 간단한 이름을 가지고 있는데, 이것은 스타 게임이라고 불리며, 줄여서 ∗라고도 할 수 있습니다.스타 게임에서는 유효한 동작만이 제로 게임으로 이어집니다.즉, 스타 게임 중에 차례가 올라오는 사람이 자동으로 승리하는 것입니다.

도미네링에서 찾을 수 없는 또 다른 유형의 게임은 루프형 게임으로, 왼쪽 또는 오른쪽의 유효한 움직임은 첫 번째 게임으로 돌아갈 수 있는 게임입니다.예를 들어, 체커는 두 개 이상의 정사각형 사이를 끝없이 순환할 수 있기 때문에 조각 중 하나가 승격되면 루프 상태가 됩니다.이러한 움직임이 없는 게임을 루프프리라고 합니다.

게임 줄임말

숫자

숫자는 자유 이동 수 또는 특정 플레이어의 이동 이점을 나타냅니다.관례상 양의 숫자는 왼쪽의 장점을 나타내고 음의 숫자는 오른쪽의 장점을 나타냅니다.0이 베이스 케이스인 상태에서 재귀적으로 정의됩니다.

0 = { }

1 = {0 }, 2 = {1 }, 3 = {2 }

−1 = { 0}, −2 = { −1}, −3 = { −2}

제로 게임은 첫 번째 선수에게 지는 게임입니다.

숫자 게임의 합계는 정수처럼 동작합니다(예: 3 + -2 = 1).

별

or 또는 {0 0}으로 표기된 스타는 1인 1승으로, 어느 한 플레이어가 제로 게임으로 이동해야 하므로 승리합니다.

∗ + ∗ = 0. 왜냐하면 첫 번째 플레이어는 ∗의 복사본 하나를 0으로 만들어야 하고, 그 다음 다른 플레이어는 ∗의 다른 복사본도 0으로 만들어야 하기 때문이다. 이때, 0 + 0은 움직임을 허용하지 않기 때문에 첫 번째 플레이어는 패하게 된다.

게임 ①은 긍정도 부정도 아닙니다.게임과 그 외 첫 번째 플레이어가 이긴 모든 게임은 (어느 쪽에 있는가에 관계없이) 0과 애매하거나 혼동된다고 합니다.기호적으로 ② 0이라고 씁니다.

업.

↑로 쓰인 Up은 조합 게임 ^[10]이론의 한 위치입니다.표준 표기법에서는 ↑= {0 }.}입니다.

-↑=↓(아래)

Up은 엄밀하게 양의 값(↑ > 0)이지만 극소수입니다.Up은 Winning Ways for your Mathemical Plays에 정의되어 있습니다.

밑.

↓로 쓰여진 Down은 조합 게임 ^[10]이론의 한 위치입니다.표준 표기법에서는 ↓= {syslog 0}입니다.

-↓=↑(위)

하향은 엄밀하게 음수(↓ < 0)이지만 극소수입니다.Down은 Winning Ways for your Mathemical Plays에 정의되어 있습니다.

핫 게임

{1-1} 게임을 고려하십시오.이 게임에서의 두 동작은 그것을 만드는 플레이어에게 유리하다.그래서 게임은 -1보다 작은 숫자보다 크고 1보다 작은 숫자보다 크고 그 사이에 있는 숫자와 함께 흐릿하다.그것은 ±1로 쓰여 있다.예를 들어, 4 ± 1 = {5 3}과(와) 같은 방법으로 숫자에 추가하거나 양의 값에 곱할 수 있습니다.

님버스

공정한 게임은 게임의 모든 위치에서 두 플레이어 모두 동일한 동작을 사용할 수 있는 게임입니다.예를 들어 Nim은 한 플레이어가 삭제할 수 있는 오브젝트 세트를 다른 플레이어가 삭제할 수 있으므로 공평합니다.하지만, 한 선수는 수평 도미노를 놓고 다른 한 선수는 수직 도미노를 놓기 때문에 지배는 공평하지 않다.마찬가지로 체커스는 선수들이 다른 색깔의 작품들을 소유하기 때문에 공평하지 않다.어떤 서수든 Nim을 일반화하는 공평한 게임을 정의할 수 있습니다.이러한 방법으로 정의된 게임을 님이라고 합니다.Sprague-Grundy 정리는 모든 공정한 게임은 민첩성과 동등하다고 말한다.

"가장 작은" 민첩성 – 보통 서수 순서에서 가장 단순하고 가장 작은 –은 0과 ∗입니다.

「 」를 참조해 주세요.

• 알파 베타 프루닝, 게임 트리 검색에 최적화된 알고리즘
• 역방향 유도, 최종 상황에서 역방향 추론
• 냉난방(콤비네이션 게임 이론), 게임의 다양한 변형으로 인해 게임에 더 순응할 수 있습니다.
• 커넥션 게임, 플레이어가 접속을 시도하는 게임
• 엔드게임 테이블베이스, 엔드게임을 플레이하는 방법을 나타내는 데이터베이스
• Minimax 게임 트리를 우연한 요소가 있는 게임에 적응시킨 Expectminimax 트리
• 광범위한 형식의 게임, 플레이어가 이용할 수 있는 보상과 정보가 풍부한 게임 트리
• 게임 분류, 게임 분류 방법을 설명하는 기사
• 게임 복잡도, 게임의 복잡도를 측정하는 방법을 설명하는 기사
• 그룬디의 게임, 산더미처럼 쌓인 물체가 갈라지는 수학 게임
• 복잡한 문제를 해결하기 위한 컴퓨터 시스템의 일종인 멀티 에이전트 시스템
• 포지션 게임(Positional Game)은 플레이어가 이전에 주장하지 않은 포지션을 주장하는 게임의 일종이다.
• 체스 풀기
• 이전에 선택한 정수의 음이 아닌 배수의 합계가 아닌 양의 정수를 선택하는 수학 게임인 실버 코인지
• 위토프의 게임, 한두 개의 말뚝에서 물체를 꺼내는 수학 게임
• 위상 공간에서의 수학 게임인 위상 게임
• 불리할 때 어쩔 수 없이 출전하는 Zugzwang

메모들

레퍼런스

• Albert, Michael H.; Nowakowski, Richard J.; Wolfe, David (2007). Lessons in Play: An Introduction to Combinatorial Game Theory. A K Peters Ltd. ISBN 978-1-56881-277-9.
• Beck, József (2008). Combinatorial games: tic-tac-toe theory. Cambridge University Press. ISBN 978-0-521-46100-9.
• Berlekamp, E.; Conway, J. H.; Guy, R. (1982). Winning Ways for your Mathematical Plays: Games in general. Academic Press. ISBN 0-12-091101-9. 제2판, AKPeters Ltd(2001~2004년), ISBN 1-56881-130-6, ISBN 1-56881-142-X
• Berlekamp, E.; Conway, J. H.; Guy, R. (1982). Winning Ways for your Mathematical Plays: Games in particular. Academic Press. ISBN 0-12-091102-7. 제2판, AKPeters Ltd(2001-2004), ISBN 1-56881-143-8, ISBN 1-56881-144-6.
• Berlekamp, Elwyn; Wolfe, David (1997). Mathematical Go: Chilling Gets the Last Point. A K Peters Ltd. ISBN 1-56881-032-6.
• Bewersdorff, Jörg (2004). Luck, Logic and White Lies: The Mathematics of Games. A K Peters Ltd. ISBN 1-56881-210-8. 특히 섹션 21~26을 참조하십시오.
• Conway, John Horton (1976). On Numbers and Games. Academic Press. ISBN 0-12-186350-6. 제2판, AKPeters Ltd(2001), ISBN 1-56881-127-6.
• Robert A. Hearn; Erik D. Demaine (2009). Games, Puzzles, and Computation. A K Peters, Ltd. ISBN 978-1-56881-322-6.

외부 링크

• 데이비드 엡스타인 홈페이지의 조합 게임 이론 링크 목록
• 디어크 슐라이허와 마이클 스톨의 콘웨이 게임과 숫자 소개
• Bill Spight의 조합 게임 이론 용어 요약
• Banff International Research Station, Combinatory Game Theory 워크숍, 2005년 6월