조합론적 게임 이론은 공정 게임 이론에서 파생된 것으로, 게임의 전략과 보상뿐만 아니라 조합론적 수준에서의 고려를 중요하게 여긴다. 1930년대에 스프라그-그런디 정리가 모든 공정 게임이 님 게임과 동일하다는 것을 밝히면서 발전의 계기가 되었다. 1960년대에는 편파 게임 이론이 도입되었고, 콘웨이는 초현실수의 개념을 게임에 적용하여 이론을 확장했다. 조합론적 게임은 두 플레이어가 번갈아 가며 수를 두는 방식으로 진행되며, 게임의 합, 수, 별, 업, 다운, 핫 게임, 님버 등 다양한 개념을 포함한다. 해켄부쉬, 두꺼비와 개구리, 도미니어링, 님, 바둑, 체스 등 다양한 게임을 연구하며, 바둑과 체스는 조합론적 게임 이론의 발전에 영향을 미쳤다.
더 읽어볼만한 페이지
조합론적 게임 이론 - 젠가 젠가는 54개의 나무 블록으로 타워를 쌓아 블록을 제거하고 위에 올려 타워를 무너뜨리지 않고 버티는 게임이며, 마지막으로 턴을 완료한 플레이어가 승리한다.
조합론적 게임 이론 - 게임 복잡도 게임 복잡도는 상태 공간, 게임 트리 크기, 결정 복잡성, 게임 트리 복잡도, 계산 복잡성과 같은 척도를 사용하여 게임의 난이도와 경우의 수를 정량적으로 측정하는 개념이다.
게임 이론 - 대연정 대연정은 의원내각제 또는 이원집정부제 국가에서 대립하는 거대 정당들이 국가적 위기 극복, 정치적 봉쇄, 또는 비례대표제 하의 연립 내각 구성의 필요에 따라 연합하는 정부 형태로, 정치적 안정과 국민 통합에 기여할 수 있지만 유권자 선택권 제한 및 소수 정당 약진의 우려도 있다.
게임 이론 - 완전 정보 완전 정보 게임은 게임 이론에서 모든 플레이어가 게임의 모든 정보를 공유하는 게임을 의미하며, 체스, 틱택토, 오목 등이 이에 해당한다.
수학 - 회귀 분석 회귀 분석은 종속 변수와 하나 이상의 독립 변수 간의 관계를 모델링하고 분석하는 통계적 기법으로, 최소 제곱법 개발 이후 골턴의 연구로 '회귀' 용어가 도입되어 다양한 분야에서 예측 및 인과 관계 분석에 활용된다.
수학 - 수학적 최적화 수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.
조합론적 게임 이론은 한쪽 플레이어에게 가능한 모든 수가 다른 플레이어에게도 가능한 공정 게임 이론과 관련하여 등장했다. 님 게임은 완전히 해결 가능한 공정 게임 중 하나이다. 1930년대 스프라그-그런디 정리는 모든 공정 게임이 님 게임의 묶음과 동일하다는 것을 보여주면서, 조합론적 수준에서 고려되는 게임에서 주요한 통일을 가능하게 했다.
1960년대 엘윈 R. 버렐캠프, 존 호턴 콘웨이, 리처드 K. 가이는 한쪽 플레이어에게 가능한 수가 양쪽 모두에게 가능한 조건이 완화된 편파 게임 이론을 공동으로 도입했다. 이들의 결과는 1982년 ''수학적 게임을 위한 승리 전략''에 출판되었다. 이 주제에 관해 처음 출판된 작품은 1976년 콘웨이의 ''수와 게임에 관하여''로, 초현실수의 개념과 게임으로의 일반화를 소개했다. ''수와 게임에 관하여''는 버렐캠프, 콘웨이, 가이 간의 공동 작업의 결실이었다.
조합론적 게임은 일반적으로 상대방이 더 이상 움직일 수 없을 때 한쪽 플레이어가 이기는 형태로 만들어진다. 가능한 결과가 두 가지뿐인 모든 유한 게임은 이 규칙이 적용되는 동일한 게임으로 쉽게 변환할 수 있다. 조합론적 게임 이론에서 가장 중요한 개념 중 하나는 두 게임의 합인데, 각 플레이어가 어느 시점에서든 한 게임 또는 다른 게임에서 움직이도록 선택할 수 있고, 상대방이 두 게임 중 어느 쪽에서도 움직일 수 없을 때 플레이어가 승리하는 게임이다.
콘웨이는 ''수와 게임에 관하여''에서 편파 게임 이론은 바둑 종국이 종종 서로 다른 보드 부분에서 분리된 더 간단한 종국의 합으로 분해될 수 있다는 그의 관찰에서 영감을 받았다고 언급했다.
2. 1. 공정 게임과 님 게임
조합론적 게임 이론은 한쪽 플레이어에게 가능한 모든 수가 다른 플레이어에게도 가능한 공정 게임 이론과 관련하여 등장했다. 그러한 게임 중 하나가 완전히 해결 가능한 님 게임이다. 님 게임은 두 명의 플레이어를 위한 공정 게임이며, 움직일 수 없는 플레이어가 지는 ''일반 플레이 조건''을 따른다. 1930년대에 스프라그-그런디 정리는 모든 공정 게임이 님 게임의 묶음과 동일하다는 것을 보여주었다.
공정 게임은 게임의 모든 위치에서 두 플레이어에게 동일한 이동이 가능한 게임이다. 예를 들어, 님은 한 플레이어가 제거할 수 있는 모든 객체를 다른 플레이어도 제거할 수 있기 때문에 공정 게임이다. 모든 서수에 대해, 각 이동에서 어느 플레이어든 숫자를 더 작은 서수로 바꿀 수 있는 공정 게임을 정의할 수 있는데, 이러한 방식으로 정의된 게임을 님버라고 한다. 스프라그-그런디 정리는 일반 플레이 규칙 하에서 모든 공정 게임이 님버와 동일하다고 말한다.[4] "가장 작은" 님버 - 서수의 일반적인 순서에서 가장 단순하고 가장 작은 님버는 0과 ∗이다.[4]
2. 2. 편파 게임과 초현실수
1960년대에 엘윈 R. 버렐캠프, 존 호턴 콘웨이, 리처드 K. 가이는 한쪽 플레이어에게 가능한 수가 양쪽 모두에게 가능한 조건이 완화된 편파 게임 이론을 공동으로 도입했다. 이들의 결과는 1982년 저서 ''수학적 게임을 위한 승리 전략''(Winning Ways for your Mathematical Plays)에 출판되었다. 그러나 이 주제에 관해 처음 출판된 작품은 콘웨이의 1976년 저서 ''수와 게임에 관하여''(On Numbers and Games, ONAG)였으며, 초현실수의 개념과 게임으로의 일반화를 소개했다. ''수와 게임에 관하여''는 또한 버렐캠프, 콘웨이, 가이 간의 공동 작업의 결실이었다.
2. 3. 바둑의 영향
콘웨이는 바둑 종국이 서로 다른 보드 부분에서 분리된 더 간단한 종국의 합으로 분해될 수 있다는 점에 착안하여 편파 게임 이론을 발전시켰다. 바둑은 복잡한 계산과 전략이 요구되는 게임으로, 조합 게임 이론의 중요한 연구 대상이 되었다.
3. 주요 개념
조합론적 게임 이론은 두 명의 플레이어가 참여하고, 한쪽 플레이어에게 가능한 모든 수가 다른 플레이어에게도 가능한 공정 게임을 다룬다. 님 게임은 완전히 해결 가능한 대표적인 예시이며, 움직일 수 없는 플레이어가 지는 일반 플레이 조건이 적용된다. 1930년대 스프라그-그런디 정리는 모든 공정 게임이 님 게임의 묶음과 동일하다는 것을 보여주어 조합론적 게임 이론의 중요한 발전을 이루었다.
1960년대 엘윈 R. 버렐캠프, 존 호턴 콘웨이, 리처드 K. 가이는 한쪽 플레이어에게 가능한 수가 양쪽 모두에게 가능하지 않은 편파 게임 이론을 도입했다. 이들의 연구 결과는 1982년 ''수학적 게임을 위한 승리 전략''에 출판되었고, 1976년 콘웨이의 ''수와 게임에 관하여''는 이 주제에 대한 최초의 출판물로 초현실수 개념과 게임으로의 일반화를 소개했다.
조합론적 게임은 일반적으로 상대방이 더 이상 움직일 수 없을 때 한쪽 플레이어가 이기는 형태이다. 핵심 개념 중 하나는 두 게임의 합으로, 각 플레이어는 한 게임 또는 다른 게임에서 움직일 수 있으며, 상대방이 두 게임 중 어느 쪽에서도 움직일 수 없을 때 플레이어가 승리한다. 콘웨이는 바둑 종국이 종종 서로 다른 보드 부분에서 분리된 더 간단한 종국의 합으로 분해될 수 있다는 점을 통해 편파 게임 이론의 영감을 얻었다고 ''수와 게임에 관하여''에서 언급했다.
3. 1. 게임의 표현
조합론적 게임 이론에서 게임은 '왼쪽'과 '오른쪽' 두 명의 플레이어가 할 수 있는 가능한 "수"의 목록으로 표현된다. 어떤 수의 결과로 나온 게임 위치는 또 다른 게임으로 간주될 수 있다. 이러한 아이디어를 바탕으로, 조합론적 게임 이론에서는 게임을 재귀적으로 정의한다. 각 게임은 '''{L|R}''' 표기를 갖는다. L은 왼쪽 플레이어가 이동할 수 있는 게임 위치의 집합이고, R은 오른쪽 플레이어가 이동할 수 있는 게임 위치의 집합이다. L과 R의 각 위치는 동일한 표기를 사용하여 게임으로 정의된다.
도미니어링 게임을 예로 들어보자. 4x4 보드에서 맨 위 왼쪽 사각형을 A1, 위에서 두 번째 줄의 왼쪽에서 세 번째 상자를 C2 등으로 표시한다. (D3, D4)는 수직 도미노가 오른쪽 하단 구석에 놓인 게임 위치를 나타낸다. 그러면 초기 위치는 조합론적 게임 이론 표기법으로 다음과 같이 표현할 수 있다.
:
표준적인 크로스-크램 게임에서 플레이어는 교대로 턴을 갖지만, 이러한 교대는 조합론적 게임 이론의 정의에 의해 암묵적으로 처리된다.
:
위 게임은 두 플레이어 중 한 명에게만 한 수의 기회가 남았고, 어느 플레이어가 그 수를 두면 그 플레이어가 이기는 시나리오를 설명한다. 각 플레이어의 수 목록에 있는
(수에 따른 남은 하나의 사각형에 해당)는 영 게임이라고 하며, 0으로 줄여서 표기할 수 있다. 영 게임에서는 두 플레이어 모두 유효한 수가 없으므로, 영 게임이 되면 턴이 있는 플레이어는 자동으로 진다.
위 다이어그램의 게임 유형은 별 게임이라고 하며, *로 줄여서 표기할 수도 있다. 별 게임에서 유일한 유효한 수는 영 게임으로 이어지므로, 별 게임 중에 턴이 오는 사람은 자동으로 이긴다.
체커와 같이 '왼쪽' 또는 '오른쪽'의 유효한 수가 다시 첫 번째 게임으로 이어질 수 있는 '루프' 게임도 존재한다. 이러한 수를 갖지 않는 게임을 '루프 없는' 게임이라고 한다.
또한 '왼쪽'과 '오른쪽'이 무한한 수의 목록을 갖는 '초한' 게임도 존재한다.
3. 2. 게임의 종류
조합론적 게임 이론은 '왼쪽'과 '오른쪽' 두 플레이어가 할 수 있는 가능한 "수" 목록으로 게임을 정의한다. 각 수는 또 다른 게임 위치로 이어질 수 있으며, 이는 '{L|R}' 표기법을 사용하는 재귀적인 수학적 정의로 표현된다. 여기서 L은 왼쪽 플레이어가 이동할 수 있는 게임 위치의 집합이고, R은 오른쪽 플레이어가 이동할 수 있는 게임 위치의 집합이다.
도미니어링 게임을 예로 들면, 4x4 보드의 초기 위치는 다음과 같이 표현할 수 있다.
:
크로스-크램 게임처럼 플레이어들이 교대로 턴을 갖는 경우, 조합론적 게임 이론에서는 이러한 교대가 게임 상태에 이미 포함되어 있다고 간주한다.
두 플레이어 모두 유효한 수가 없는 영 게임에서는 턴을 가진 플레이어가 패배한다. 반면, 별 게임에서는 유일한 유효한 수가 영 게임으로 이어지므로 턴을 가진 플레이어가 승리한다.
3. 2. 1. 루프 없는 게임과 루프 게임
루프 없는 게임은 '왼쪽' 또는 '오른쪽' 플레이어의 유효한 수가 다시 첫 번째 게임으로 이어지지 않는 게임이다. 반면, 체커와 같이 '왼쪽' 또는 '오른쪽'의 유효한 수가 다시 첫 번째 게임으로 이어질 수 있는 게임은 '루프' 게임이라고 한다. 체커에서 말 중 하나가 승진하면 루프가 되는데, 그 후 두 개 이상의 사각형 사이를 끊임없이 순환할 수 있다.
3. 2. 2. 유한 게임과 초한 게임
가장 단순한 형태의 게임은 '왼쪽'과 '오른쪽'이라고 불리는 두 명의 플레이어가 할 수 있는 가능한 "수"의 목록이다. 어떤 수의 결과로 나온 게임 위치는 또 다른 게임으로 간주될 수 있다. 이러한 아이디어를 다른 게임으로 이동할 수 있는 가능한 수를 통해 게임을 보는 것은 조합론적 게임 이론에서 표준적인 게임의 재귀적인 수학적 정의로 이어진다. 이 정의에서 각 게임은 '''{L|R}''' 표기를 갖는다. L은 왼쪽 플레이어가 이동할 수 있는 게임 위치의 집합이고, R은 오른쪽 플레이어가 이동할 수 있는 게임 위치의 집합이다. L과 R의 각 위치는 동일한 표기를 사용하여 게임으로 정의된다.
도미니어링을 예로 들어, 4x4 보드의 16개 상자를 맨 위 왼쪽 사각형은 A1, 위에서 두 번째 줄의 왼쪽에서 세 번째 상자는 C2 등으로 표시한다. 예를 들어 (D3, D4)는 수직 도미노가 오른쪽 하단 구석에 놓인 게임 위치를 나타낸다. 그러면 초기 위치는 조합론적 게임 이론 표기법으로 다음과 같이 설명할 수 있다.
:
표준적인 크로스-크램 게임에서 플레이어는 교대로 턴을 갖지만, 이러한 교대는 게임 상태 내에 인코딩되기보다는 조합론적 게임 이론의 정의에 의해 암묵적으로 처리된다.
