조합론적 게임 이론

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

조합론적 게임 이론은 공정 게임 이론에서 파생된 것으로, 게임의 전략과 보상뿐만 아니라 조합론적 수준에서의 고려를 중요하게 여긴다. 1930년대에 스프라그-그런디 정리가 모든 공정 게임이 님 게임과 동일하다는 것을 밝히면서 발전의 계기가 되었다. 1960년대에는 편파 게임 이론이 도입되었고, 콘웨이는 초현실수의 개념을 게임에 적용하여 이론을 확장했다. 조합론적 게임은 두 플레이어가 번갈아 가며 수를 두는 방식으로 진행되며, 게임의 합, 수, 별, 업, 다운, 핫 게임, 님버 등 다양한 개념을 포함한다. 해켄부쉬, 두꺼비와 개구리, 도미니어링, 님, 바둑, 체스 등 다양한 게임을 연구하며, 바둑과 체스는 조합론적 게임 이론의 발전에 영향을 미쳤다.

조합론적 게임 이론

개요

분야	게임 이론
유형	2인용 순차 게임, 완전 정보 게임

역사적 맥락

기원	1930년대, 주로 체스와 바둑 같은 게임 연구
주요 인물	에른스트 체르멜로, 존 폰 노이만, 앨버트 터커

주요 개념

완전 정보	각 플레이어가 게임의 모든 상태를 알고 있음
결정론적	무작위 요소가 없음
순차적	플레이어가 번갈아 가며 행동
2인용	두 명의 플레이어만 참여

게임 유형

조합 게임	님 (게임), 틱택토, 체스, 바둑, 체커 등
비조합 게임	포커, 브리지 등 (확률 요소 포함)

핵심 아이디어

게임 트리	가능한 모든 게임 상태를 나타내는 트리 구조
최소-최대 알고리즘	상대방의 최적 행동을 가정하여 자신의 최적 행동을 선택
알파-베타 가지치기	불필요한 탐색을 줄여 효율성을 높임

해결된 게임 예시

틱택토	선공 플레이어가 무승부를 강제할 수 있음
체커	완벽한 플레이 시 무승부
님 (게임)	수학적으로 완벽하게 해결됨

복잡성

계산 복잡도	많은 조합 게임은 계산적으로 매우 복잡함 (예: 체스, 바둑)
NP-hard/PSPACE-hard	일부 게임은 NP-hard 또는 PSPACE-hard로 분류됨

응용 분야

인공지능	게임 AI 개발에 활용
의사 결정	전략적 의사 결정 모델링
알고리즘 설계	게임 해결 알고리즘 개발

같이 보기

참고 문헌

외부 링크

📚 더 읽어볼만한 페이지

조합론적 게임 이론 - 젠가
젠가는 54개의 나무 블록으로 타워를 쌓아 블록을 제거하고 위에 올려 타워를 무너뜨리지 않고 버티는 게임이며, 마지막으로 턴을 완료한 플레이어가 승리한다.
조합론적 게임 이론 - 게임 복잡도
게임 복잡도는 상태 공간, 게임 트리 크기, 결정 복잡성, 게임 트리 복잡도, 계산 복잡성과 같은 척도를 사용하여 게임의 난이도와 경우의 수를 정량적으로 측정하는 개념이다.
분류 값 없이 쓰인 위키공용분류 - 라우토카
라우토카는 피지 비치레부섬 서부에 위치한 피지에서 두 번째로 큰 도시이자 서부 지방의 행정 중심지로, 사탕수수 산업이 발달하여 "설탕 도시"로 알려져 있으며, 인도에서 온 계약 노동자들의 거주와 미 해군 기지 건설의 역사를 가지고 있고, 피지 산업 생산의 상당 부분을 담당하는 주요 기관들이 위치해 있다.
분류 값 없이 쓰인 위키공용분류 - 코코넛
코코넛은 코코넛 야자나무의 열매로 식용 및 유지로 사용되며, 조리되지 않은 과육은 100g당 354kcal의 열량을 내는 다양한 영양 성분으로 구성되어 있고, 코코넛 파우더의 식이섬유는 대부분 불용성 식이섬유인 셀룰로오스이며, 태국 일부 지역에서는 코코넛 수확에 훈련된 원숭이를 이용하는 동물 학대 문제가 있다.
표시 이름과 문서 제목이 같은 위키공용분류 - 라우토카
라우토카는 피지 비치레부섬 서부에 위치한 피지에서 두 번째로 큰 도시이자 서부 지방의 행정 중심지로, 사탕수수 산업이 발달하여 "설탕 도시"로 알려져 있으며, 인도에서 온 계약 노동자들의 거주와 미 해군 기지 건설의 역사를 가지고 있고, 피지 산업 생산의 상당 부분을 담당하는 주요 기관들이 위치해 있다.
표시 이름과 문서 제목이 같은 위키공용분류 - 코코넛
코코넛은 코코넛 야자나무의 열매로 식용 및 유지로 사용되며, 조리되지 않은 과육은 100g당 354kcal의 열량을 내는 다양한 영양 성분으로 구성되어 있고, 코코넛 파우더의 식이섬유는 대부분 불용성 식이섬유인 셀룰로오스이며, 태국 일부 지역에서는 코코넛 수확에 훈련된 원숭이를 이용하는 동물 학대 문제가 있다.

2. 역사

조합론적 게임 이론은 한쪽 플레이어에게 가능한 모든 수가 다른 플레이어에게도 가능한 공정 게임 이론과 관련하여 등장했다. 님 게임은 완전히 해결 가능한 공정 게임 중 하나이다. 1930년대 스프라그-그런디 정리는 모든 공정 게임이 님 게임의 묶음과 동일하다는 것을 보여주면서, 조합론적 수준에서 고려되는 게임에서 주요한 통일을 가능하게 했다.

1960년대 엘윈 R. 버렐캠프, 존 호턴 콘웨이, 리처드 K. 가이는 한쪽 플레이어에게 가능한 수가 양쪽 모두에게 가능한 조건이 완화된 편파 게임 이론을 공동으로 도입했다. 이들의 결과는 1982년 수학적 게임을 위한 승리 전략에 출판되었다. 이 주제에 관해 처음 출판된 작품은 1976년 콘웨이의 수와 게임에 관하여로, 초현실수의 개념과 게임으로의 일반화를 소개했다. 수와 게임에 관하여는 버렐캠프, 콘웨이, 가이 간의 공동 작업의 결실이었다.

조합론적 게임은 일반적으로 상대방이 더 이상 움직일 수 없을 때 한쪽 플레이어가 이기는 형태로 만들어진다. 가능한 결과가 두 가지뿐인 모든 유한 게임은 이 규칙이 적용되는 동일한 게임으로 쉽게 변환할 수 있다. 조합론적 게임 이론에서 가장 중요한 개념 중 하나는 두 게임의 합인데, 각 플레이어가 어느 시점에서든 한 게임 또는 다른 게임에서 움직이도록 선택할 수 있고, 상대방이 두 게임 중 어느 쪽에서도 움직일 수 없을 때 플레이어가 승리하는 게임이다.

콘웨이는 수와 게임에 관하여에서 편파 게임 이론은 바둑 종국이 종종 서로 다른 보드 부분에서 분리된 더 간단한 종국의 합으로 분해될 수 있다는 그의 관찰에서 영감을 받았다고 언급했다.

2.1. 공정 게임과 님 게임

조합론적 게임 이론은 한쪽 플레이어에게 가능한 모든 수가 다른 플레이어에게도 가능한 공정 게임 이론과 관련하여 등장했다. 그러한 게임 중 하나가 완전히 해결 가능한 님 게임이다. 님 게임은 두 명의 플레이어를 위한 공정 게임이며, 움직일 수 없는 플레이어가 지는 일반 플레이 조건을 따른다. 1930년대에 스프라그-그런디 정리는 모든 공정 게임이 님 게임의 묶음과 동일하다는 것을 보여주었다.

공정 게임은 게임의 모든 위치에서 두 플레이어에게 동일한 이동이 가능한 게임이다. 예를 들어, 님은 한 플레이어가 제거할 수 있는 모든 객체를 다른 플레이어도 제거할 수 있기 때문에 공정 게임이다. 모든 서수에 대해, 각 이동에서 어느 플레이어든 숫자를 더 작은 서수로 바꿀 수 있는 공정 게임을 정의할 수 있는데, 이러한 방식으로 정의된 게임을 님버라고 한다. 스프라그-그런디 정리는 일반 플레이 규칙 하에서 모든 공정 게임이 님버와 동일하다고 말한다. "가장 작은" 님버 - 서수의 일반적인 순서에서 가장 단순하고 가장 작은 님버는 0과 ∗이다.

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)는 수직 도미노가 오른쪽 하단 구석에 놓인 게임 위치를 나타낸다. 그러면 초기 위치는 조합론적 게임 이론 표기법으로 다음과 같이 표현할 수 있다.

: $\{(\mathrm{A}1,\mathrm{A}2),(\mathrm{B}1,\mathrm{B}2),\dots|(\mathrm{A}1,\mathrm{B}1), (\mathrm{A}2,\mathrm{B}2),\dots\}.$

표준적인 크로스-크램 게임에서 플레이어는 교대로 턴을 갖지만, 이러한 교대는 조합론적 게임 이론의 정의에 의해 암묵적으로 처리된다.

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

위 게임은 두 플레이어 중 한 명에게만 한 수의 기회가 남았고, 어느 플레이어가 그 수를 두면 그 플레이어가 이기는 시나리오를 설명한다. 각 플레이어의 수 목록에 있는 {|} (수에 따른 남은 하나의 사각형에 해당)는 영 게임이라고 하며, 0으로 줄여서 표기할 수 있다. 영 게임에서는 두 플레이어 모두 유효한 수가 없으므로, 영 게임이 되면 턴이 있는 플레이어는 자동으로 진다.

위 다이어그램의 게임 유형은 별 게임이라고 하며, *로 줄여서 표기할 수도 있다. 별 게임에서 유일한 유효한 수는 영 게임으로 이어지므로, 별 게임 중에 턴이 오는 사람은 자동으로 이긴다.

체커와 같이 '왼쪽' 또는 '오른쪽'의 유효한 수가 다시 첫 번째 게임으로 이어질 수 있는 '루프' 게임도 존재한다. 이러한 수를 갖지 않는 게임을 '루프 없는' 게임이라고 한다.

또한 '왼쪽'과 '오른쪽'이 무한한 수의 목록을 갖는 '초한' 게임도 존재한다.

3.2. 게임의 종류

조합론적 게임 이론은 '왼쪽'과 '오른쪽' 두 플레이어가 할 수 있는 가능한 "수" 목록으로 게임을 정의한다. 각 수는 또 다른 게임 위치로 이어질 수 있으며, 이는 '{L|R}' 표기법을 사용하는 재귀적인 수학적 정의로 표현된다. 여기서 L은 왼쪽 플레이어가 이동할 수 있는 게임 위치의 집합이고, R은 오른쪽 플레이어가 이동할 수 있는 게임 위치의 집합이다.

도미니어링 게임을 예로 들면, 4x4 보드의 초기 위치는 다음과 같이 표현할 수 있다.

: $\{(\mathrm{A}1,\mathrm{A}2),(\mathrm{B}1,\mathrm{B}2),\dots|(\mathrm{A}1,\mathrm{B}1), (\mathrm{A}2,\mathrm{B}2),\dots\}.$

크로스-크램 게임처럼 플레이어들이 교대로 턴을 갖는 경우, 조합론적 게임 이론에서는 이러한 교대가 게임 상태에 이미 포함되어 있다고 간주한다.

두 플레이어 모두 유효한 수가 없는 영 게임에서는 턴을 가진 플레이어가 패배한다. 반면, 별 게임에서는 유일한 유효한 수가 영 게임으로 이어지므로 턴을 가진 플레이어가 승리한다.

3.2.1. 루프 없는 게임과 루프 게임

루프 없는 게임은 '왼쪽' 또는 '오른쪽' 플레이어의 유효한 수가 다시 첫 번째 게임으로 이어지지 않는 게임이다. 반면, 체커와 같이 '왼쪽' 또는 '오른쪽'의 유효한 수가 다시 첫 번째 게임으로 이어질 수 있는 게임은 '루프' 게임이라고 한다. 체커에서 말 중 하나가 승진하면 루프가 되는데, 그 후 두 개 이상의 사각형 사이를 끊임없이 순환할 수 있다.

3.2.2. 유한 게임과 초한 게임

가장 단순한 형태의 게임은 '왼쪽'과 '오른쪽'이라고 불리는 두 명의 플레이어가 할 수 있는 가능한 "수"의 목록이다. 어떤 수의 결과로 나온 게임 위치는 또 다른 게임으로 간주될 수 있다. 이러한 아이디어를 다른 게임으로 이동할 수 있는 가능한 수를 통해 게임을 보는 것은 조합론적 게임 이론에서 표준적인 게임의 재귀적인 수학적 정의로 이어진다. 이 정의에서 각 게임은 {L|R} 표기를 갖는다. L은 왼쪽 플레이어가 이동할 수 있는 게임 위치의 집합이고, R은 오른쪽 플레이어가 이동할 수 있는 게임 위치의 집합이다. L과 R의 각 위치는 동일한 표기를 사용하여 게임으로 정의된다.

도미니어링을 예로 들어, 4x4 보드의 16개 상자를 맨 위 왼쪽 사각형은 A1, 위에서 두 번째 줄의 왼쪽에서 세 번째 상자는 C2 등으로 표시한다. 예를 들어 (D3, D4)는 수직 도미노가 오른쪽 하단 구석에 놓인 게임 위치를 나타낸다. 그러면 초기 위치는 조합론적 게임 이론 표기법으로 다음과 같이 설명할 수 있다.

: $\{(\mathrm{A}1,\mathrm{A}2),(\mathrm{B}1,\mathrm{B}2),\dots|(\mathrm{A}1,\mathrm{B}1), (\mathrm{A}2,\mathrm{B}2),\dots\}.$

표준적인 크로스-크램 게임에서 플레이어는 교대로 턴을 갖지만, 이러한 교대는 게임 상태 내에 인코딩되기보다는 조합론적 게임 이론의 정의에 의해 암묵적으로 처리된다.

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

위의 게임은 두 플레이어 중 한 명에게만 한 수의 기회가 남았고, 어느 플레이어가 그 수를 두면 그 플레이어가 이기는 시나리오를 설명한다. (C3의 관련 없는 열린 사각형은 다이어그램에서 생략되었다.) 각 플레이어의 수 목록에 있는 (수에 따른 남은 하나의 사각형에 해당)은 영 게임이라고 하며, 실제로 0으로 줄여서 표기할 수 있다. 영 게임에서는 두 플레이어 모두 유효한 수가 없으므로, 영 게임이 되면 턴이 있는 플레이어는 자동으로 진다.

위 다이어그램의 게임 유형도 간단한 이름이 있다. 이는 별 게임이라고 하며, ∗로 줄여서 표기할 수도 있다. 별 게임에서 유일한 유효한 수는 영 게임으로 이어지므로, 별 게임 중에 턴이 오는 사람은 자동으로 이긴다.

체커는 말 중 하나가 승진하면 루프가 되는데, 그 후 두 개 이상의 사각형 사이를 끊임없이 순환할 수 있기 때문이다. 이러한 수를 갖지 않는 게임을 '루프 없는' 게임이라고 한다.

또한 무한히 많은 위치를 갖는 '초한' 게임이 있는데, 즉 '왼쪽'과 '오른쪽'은 유한이 아닌 무한한 수의 목록을 갖는다.

3.3. 게임의 연산

가장 단순한 형태의 게임은 '왼쪽'과 '오른쪽' 두 명의 플레이어가 할 수 있는 가능한 "수"의 목록으로 나타낼 수 있다. 어떤 수의 결과로 나온 게임 위치는 또 다른 게임으로 간주될 수 있다. 이러한 아이디어를 바탕으로, 조합론적 게임 이론에서는 게임을 다음과 같이 재귀적으로 정의한다.

각 게임은 {L|R} 표기를 갖는다. 여기서 L은 왼쪽 플레이어가 이동할 수 있는 게임 위치의 집합이고, R은 오른쪽 플레이어가 이동할 수 있는 게임 위치의 집합이다. L과 R의 각 위치는 동일한 표기를 사용하여 게임으로 정의된다.

도미니어링 게임을 예로 들어보자. 4x4 보드의 16개 상자를 맨 위 왼쪽 사각형은 A1, 위에서 두 번째 줄의 왼쪽에서 세 번째 상자는 C2 등으로 표시한다. 예를 들어 (D3, D4)는 수직 도미노가 오른쪽 하단 구석에 놓인 게임 위치를 나타낸다. 그러면 초기 위치는 조합론적 게임 이론 표기법으로 다음과 같이 표현할 수 있다.

: $\{(\mathrm{A}1,\mathrm{A}2),(\mathrm{B}1,\mathrm{B}2),\dots|(\mathrm{A}1,\mathrm{B}1), (\mathrm{A}2,\mathrm{B}2),\dots\}.$

표준적인 크로스-크램 게임에서 플레이어는 교대로 턴을 갖지만, 이러한 교대는 조합론적 게임 이론의 정의에 의해 암묵적으로 처리된다.

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

위의 게임은 두 플레이어 중 한 명에게만 한 수의 기회가 남았고, 어느 플레이어가 그 수를 두면 그 플레이어가 이기는 시나리오를 설명한다. (C3의 관련 없는 열린 사각형은 다이어그램에서 생략되었다.) 각 플레이어의 수 목록에 있는 {|} (수에 따른 남은 하나의 사각형에 해당)은 영 게임이라고 하며, 실제로 0으로 줄여서 표기할 수 있다. 영 게임에서는 두 플레이어 모두 유효한 수가 없으므로, 영 게임이 되면 턴이 있는 플레이어는 자동으로 진다.

위 다이어그램의 게임 유형은 별 게임(*)이라고도 부른다. 별 게임에서 유일한 유효한 수는 영 게임으로 이어지므로, 별 게임 중에 턴이 오는 사람은 자동으로 이긴다.

체커와 같이 '루프'가 있는 게임도 존재한다. 예를 들어, 체커에서 말 중 하나가 승진하면 두 개 이상의 사각형 사이를 끊임없이 순환할 수 있기 때문에 루프가 된다. 이러한 수를 갖지 않는 게임을 '루프 없는' 게임이라고 한다.

또한 '왼쪽'과 '오른쪽'이 무한한 수의 목록을 갖는 '초한' 게임도 존재한다.

3.3.1. 분리적 합

두 게임의 분리적 합은 각 플레이어가 게임의 어느 시점에서든 한 게임 또는 다른 게임에서 움직이도록 선택할 수 있는 게임이다.

3.4. 게임의 값

조합론적 게임 이론에서 가장 단순한 형태의 게임은 '왼쪽'과 '오른쪽' 두 명의 플레이어가 할 수 있는 가능한 "수"의 목록으로 나타낼 수 있다. 어떤 수의 결과로 나온 게임 위치는 또 다른 게임으로 간주될 수 있다. 조합론적 게임 이론에서는 게임을 다른 게임으로 이동할 수 있는 가능한 수를 통해 보는 것이 표준적인 재귀적인 수학적 정의로 이어진다. 이 정의에서 각 게임은 {L|R} 표기를 갖는다. L은 왼쪽 플레이어가 이동할 수 있는 게임 위치의 집합이고, R은 오른쪽 플레이어가 이동할 수 있는 게임 위치의 집합이다. L과 R의 각 위치는 동일한 표기를 사용하여 게임으로 정의된다.

도미니어링 게임을 예로 들어보면, 초기 위치는 조합론적 게임 이론 표기법으로 다음과 같이 표현할 수 있다.

: $\{(\mathrm{A}1,\mathrm{A}2),(\mathrm{B}1,\mathrm{B}2),\dots|(\mathrm{A}1,\mathrm{B}1), (\mathrm{A}2,\mathrm{B}2),\dots\}.$

표준적인 크로스-크램 게임에서 플레이어는 교대로 턴을 갖지만, 조합론적 게임 이론에서는 이러한 교대가 게임 상태 내에 인코딩되어 암묵적으로 처리된다.

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

위 게임은 두 플레이어 중 한 명에게만 한 수의 기회가 남았고, 어느 플레이어가 그 수를 두면 이기는 시나리오를 나타낸다. 각 플레이어의 수 목록에 있는 {|} (수에 따른 남은 하나의 사각형)은 영 게임이라고 하며, 0으로 줄여서 표기할 수 있다. 영 게임에서는 두 플레이어 모두 유효한 수가 없으므로, 턴이 있는 플레이어는 자동으로 진다.

위 다이어그램의 게임 유형은 별 게임(*)이라고 하며, 유일한 유효한 수는 영 게임으로 이어지므로, 별 게임 중에 턴이 오는 사람은 자동으로 이긴다.

체커와 같이 '왼쪽' 또는 '오른쪽'의 유효한 수가 다시 첫 번째 게임으로 이어질 수 있는 '루프' 게임도 있다. 이러한 수를 갖지 않는 게임을 '루프 없는' 게임이라고 한다. 또한, '왼쪽'과 '오른쪽'이 무한한 수의 목록을 갖는 '초한' 게임도 존재한다.

3.4.1. 수

숫자는 특정 플레이어에게 유리한 정도를 나타낸다. 양수는 Left(왼쪽)에게 유리함을, 음수는 Right(오른쪽)에게 유리함을 나타낸다. 이는 0을 기본으로 하여 재귀적으로 정의된다.
: 0 =

👆

좌우로 밀어서 보기

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

제로 게임은 먼저 시작하는 플레이어에게는 패배이다.

수 게임의 합은 정수처럼 작동한다. 예를 들어, 3 + −2 = 1이다.

모든 게임 수는 초현실수 클래스에 속한다.

3.4.2. 별 (Star)

별(*)은 {0|0}으로 표기하며, 선공이 승리하는 게임이다. 어느 쪽이 먼저 움직이든 0 게임으로 이동해야 하므로, 결과적으로 먼저 움직이는 쪽이 승리한다.

: ∗ + ∗ = 0이다. 먼저 움직이는 쪽이 * 중 하나를 0으로 만들면, 상대방은 남은 *를 0으로 만들어야 한다. 이 시점에서 먼저 움직인 쪽은 0 + 0이 되어 더는 움직일 수 없으므로 패배한다.

게임 *는 긍정적이지도, 부정적이지도 않다. 이 게임과 선공이 승리하는 다른 모든 게임은 0과 혼동된다고 하며, 기호로는 ∗ || 0으로 쓴다.

3.4.3. 업 (Up)과 다운 (Down)

업(Up)은 ↑ 기호로 나타내는 조합 게임 이론에서의 위치이다. 표준 표기법으로는 ↑ = {0|∗}이다.

: −↑ = ↓ (다운)

업은 엄격하게 양수(↑ > 0)이지만 무한소이다. 업은 수학적 게임의 승리 방법(Winning Ways for your Mathematical Plays)에 정의되어 있다.

다운(Down)은 ↓ 기호로 나타내며, 조합론적 게임 이론에서의 위치이다. 표준 표기법으로는 ↓ = {∗|0}이다.

: −↓ = ↑ (업)

다운은 엄격하게 음수(↓ < 0)이지만, 무한소이다. 다운은 수학적 게임의 승리 방법(Winning Ways for your Mathematical Plays)에 정의되어 있다.

3.4.4. 핫 게임 (Hot Games)

핫 게임(Hot game^영어)은 두 플레이어 모두에게 유리한 수가 있는 게임이다. 예를 들어 {1|−1}과 같은 게임이 있다. 이 게임의 두 수는 모두 수를 두는 사람에게 유리하다. 따라서 이 게임은 "핫"하다고 하며, -1보다 작은 모든 수보다 크고, 1보다 큰 모든 수보다 작으며, 그 사이의 모든 수와는 비교할 수 없다. 이것은 ±1로 표기된다. 예상되는 방식으로 수에 더하거나 양수로 곱할 수 있다. 예를 들어 4 ± 1 = {5|3}이다.

3.5. 님버 (Nimbers)

공정 게임은 게임의 모든 위치에서 두 플레이어에게 동일한 이동이 가능한 게임이다. 예를 들어, 님은 한 플레이어가 제거할 수 있는 모든 객체를 다른 플레이어도 제거할 수 있기 때문에 공정 게임이다. 그러나 도미니어링은 한 플레이어가 가로 도미노를 놓고 다른 플레이어가 세로 도미노를 놓기 때문에 공정 게임이 아니다. 마찬가지로 체커는 플레이어가 서로 다른 색상의 조각을 소유하고 있기 때문에 공정 게임이 아니다. 모든 서수에 대해, 각 이동에서 어느 플레이어든 숫자를 더 작은 서수로 바꿀 수 있는 공정 게임을 정의할 수 있는데, 이러한 방식으로 정의된 게임을 님버라고 한다. 스프라그-그런디 정리는 일반 플레이 규칙 하에서 모든 공정 게임이 님버와 동일하다고 말한다.

"가장 작은" 님버 - 서수의 일반적인 순서에서 가장 단순하고 가장 작은 님버는 0과 ∗이다.

4. 예시 게임

조합론적 게임 이론으로 분석할 수 있는 몇 가지 대표적인 게임은 다음과 같다.

* 님: 두 명의 플레이어가 번갈아 가며 돌 무더기에서 돌을 가져가는 게임으로, 마지막 돌을 가져가는 플레이어가 승리한다. 스프라그-그런디 정리에 의해 완전히 해결되었으며, 모든 공정 게임은 님 게임의 묶음과 동일하다는 것이 밝혀졌다.
* 바둑: 엘윈 R. 버렐캠프, 존 호턴 콘웨이, 리처드 K. 가이는 바둑의 종국이 종종 서로 다른 보드 부분에서 분리된 더 간단한 종국의 합으로 분해될 수 있다는 점에 착안하여 편파 게임 이론을 고안했다.
* 해켄부쉬: 파랑-빨강 해켄부쉬와 파랑-빨강-초록 해켄부쉬가 있으며, 이진 유리수, 초현실수, 별 등 다양한 게임 값을 구성할 수 있다.
* 두꺼비와 개구리: 위치를 짧은 문자열로 쉽게 표현할 수 있다.
* 도미니어링: 핫 게임과 같은 흥미로운 게임이 나타나며, 게임의 온도를 논의할 수 있다.
* 체스: 1950년 클로드 섀넌은 체스의 게임 트리 복잡성 하한을 10¹²⁰으로 추정했으며, 이를 섀넌 수라고 부른다.

4.1. 해켄부쉬 (Hackenbush)

* 파랑-빨강 해켄부쉬는 유한한 수준에서 이진 유리수인 게임 값을 구성할 수 있다. 무한대 수준에서는 모든 실수 값뿐만 아니라 초현실수에 속하는 많은 무한대 값을 구성할 수 있다.
* 파랑-빨강-초록 해켄부쉬는 전통적인 의미의 숫자가 아닌 별과 같은 추가적인 게임 값을 허용한다. 님은 파랑-빨강-초록 해켄부쉬에서 초록색만 있는 특수한 경우로 볼 수 있다.

4.2. 두꺼비와 개구리 (Toads and Frogs)

승리하는 방법에서 소개된 게임 중 하나로, 다양한 게임 값을 허용한다. 다른 대부분의 게임과 달리, 위치는 짧은 문자열로 쉽게 표현된다.

4.3. 도미니어링 (Domineering)

도미니어링은 핫 게임과 같은 다양한 흥미로운 게임이 그 위치로 나타난다. 이는 때때로 움직일 유인이 있고 때로는 그렇지 않기 때문이다. 이를 통해 게임의 온도를 논의할 수 있다.

4.4. 님 (Nim)

님은 공정 게임으로, 님버를 구성하는 데 사용됩니다. 님은 파랑-빨강-초록 해켄부쉬에서 초록색만 있는 특별한 경우로도 볼 수 있습니다.

4.5. 바둑 (Go)

엘윈 R. 버렐캠프, 존 호턴 콘웨이, 리처드 K. 가이는 바둑의 종국이 종종 서로 다른 보드 부분에서 분리된 더 간단한 종국의 합으로 분해될 수 있다는 점에 착안하여 편파 게임 이론을 만들었다. 이들은 수학적 게임을 위한 승리 전략에서 조합 게임 이론을 발표하였고, 수와 게임에 관하여에서 초현실수의 개념과 게임으로의 일반화를 소개하였다.

4.6. 체스 (Chess)

체스는 조합 게임 이론의 맥락에서 연구된 게임이다. 1953년 앨런 튜링은 "저장 용량이 충분하다면, 모든 디지털 컴퓨터를 프로그래밍하여 수학적 기호를 사용한 계산을 수행하는 방법을 영어로 매우 명확하게 설명할 수 있다."라고 썼다. 1950년 클로드 섀넌은 체스의 게임 트리 복잡성 하한을 10¹²⁰으로 추정했으며, 오늘날 이것은 섀넌 수라고 불린다.

4.6.1. 무한 체스 (Infinite Chess)

체스는 아직 해결되지 않았지만, 슈퍼컴퓨터를 이용한 광범위한 연구를 통해 체스 엔드게임 테이블베이스가 만들어졌다. 이는 7개 이하의 말을 가진 모든 엔드게임에 대한 완벽한 플레이 결과를 보여준다. 무한 체스는 체스보다 훨씬 더 큰 조합적 복잡성을 가지고 있다(단, 제한된 엔드게임 또는 소수의 말로 구성된 위치만 연구하는 경우).

분야	게임 이론
유형	2인용 순차 게임, 완전 정보 게임

역사적 맥락

기원	1930년대, 주로 체스와 바둑 같은 게임 연구
주요 인물	에른스트 체르멜로, 존 폰 노이만, 앨버트 터커

주요 개념

완전 정보	각 플레이어가 게임의 모든 상태를 알고 있음
결정론적	무작위 요소가 없음
순차적	플레이어가 번갈아 가며 행동
2인용	두 명의 플레이어만 참여

게임 유형

조합 게임	님 (게임), 틱택토, 체스, 바둑, 체커 등
비조합 게임	포커, 브리지 등 (확률 요소 포함)

핵심 아이디어

게임 트리	가능한 모든 게임 상태를 나타내는 트리 구조
최소-최대 알고리즘	상대방의 최적 행동을 가정하여 자신의 최적 행동을 선택
알파-베타 가지치기	불필요한 탐색을 줄여 효율성을 높임

해결된 게임 예시

틱택토	선공 플레이어가 무승부를 강제할 수 있음
체커	완벽한 플레이 시 무승부
님 (게임)	수학적으로 완벽하게 해결됨

복잡성

계산 복잡도	많은 조합 게임은 계산적으로 매우 복잡함 (예: 체스, 바둑)
NP-hard/PSPACE-hard	일부 게임은 NP-hard 또는 PSPACE-hard로 분류됨

응용 분야

인공지능	게임 AI 개발에 활용
의사 결정	전략적 의사 결정 모델링
알고리즘 설계	게임 해결 알고리즘 개발

같이 보기

참고 문헌

외부 링크