Impartial Games

algorithm , game-theory

$Impartial$ $game$ 의 예로 우리가 흔히하는 베스킨라빈스 31이라는 게임이 있는데, 이 게임은 모든 플레이어가 동일하게 현재 숫자에서 1 ~ 3 사이의 수만큼 증가시키고 31이 될 경우 지게되는 게임이다. 이러한 $Impartial$ $game$에서 두 명의 플레이어가 있을 때 서로 최적으로 game을 진행 하였을 때 이기는 것이 누구인지 판별 할 수 있는 $Nim$ $game$과, $Grundy$ $number$에 대해서 공부하였습니다.

2. Nim of game

Nim game이란?

$Nim$ $game$은 $Impartial $ $game$중 하나로 내용은 다음과 같습니다.

“여러가지 돌 무더기가 있는데, 두 사람이 차례를 번갈아가면서 게임을 합니다. 자신의 차례에 하나의 돌 무더기를 선택하여 1개 이상의 원하는 만큼의 돌무더기를 제거할 수 있습니다. 이 때, 자신의 차례에서 더 이상 제거할 돌이 없을 경우에 패배를 하게 됩니다.”

서로 최적으로 게임을 할때 누가 이기는지 판별을 하는 것은 간단합니다. 맨 처음의 돌 무더기에 있는 돌의 개수를 모두 XOR 연산을 했을 때 값이 0이 나오면 처음 시작하는 사람이 지고 0이 아닐 경우에는 처음 시작하는 사람이 이깁니다.

Nim game 증명

$Nim$ $game$ 승자를 위와 같은 이유로 판별할 수 있는 이유는 다음과 같습니다. 전체 무더기의 돌의 개수를 모두 XOR한 값을 편의상 $x$ 라고 하면, 자신의 차례때 $x=0$ 을 만드는 것이 이 게임의 최적의 전략입니다. 이 전략이 최적의 전략이 되기 위해서는 2가지의 증명이 있어야 합니다.

첫번째, $x=0$일 경우, 그 다음은 무조건 $x \ne 0$이 됩니다.

자신의 차례 일 때 $x=0$일 경우, 하나의 무더기를 선택해서 돌을 제거 한다고 가정을 하자. 선택한 무더기에 있는 돌의 개수를 $a$(단, $ a>0$)라고 하고 선택된 무더기를 제외한 나머지 돌을 XOR연산 한것을 $b$라고 하면 $a \oplus b = 0$ 이 됩니다. 여기서 선택한 무더기에 있는 돌을 1개 이상 제거해야 하는데 제거한 것의 개수를 $n$(단, $1<=n<=a$)라고 하면 $(a-n) \oplus b \ne$ 0이 됩니다.

두번째, $x \ne 0$일 경우, 그 다음은 무조건 $x=0$을 만들 수 있다.

$x$를 2진법으로 표현했을 때 가장 큰 1비트의 위치를 $y$라고 하자. $y$가 1이라는 것은 돌무더기 중에 $y$비트를 포함한 돌 무더기가 존재한다는 것이다. 그렇다면 $y$를 포함한 돌 무더기를 선택하여 $y$를 0으로 만들고 그 이하의 비트들도 다 0으로 만들도록 제거를 하면 $x=0$ 이 된다.

예를 들어 $x = 0100011_{(2)}$ 일 경우 가장 큰 비트는 2번째 비트가 될 것입니다. 그렇다면 돌무더기 중에 2번째 비트를 포함한 것이 있을텐데 그 돌무더기를 선택하여 2번째 비트를 없애기 위해서는 (1 ~ $2^5-1$)중 제거를 하여 2번째 비트를 없애 줄 수 있는데 2번째 비트를 없애면 그 이하의 비트는 다 0으로 만들어 줄 수가 있다. 그렇기 때문에 무조건 $x=0$ 으로 만들어 주는 것이 가능하다.

$Nim$ $game$ 모든 돌의 개수가 0이되면 더이상 제거 할 돌이 없기 때문에 패배하게 된다. 모든 돌의 개수가 0이면 $x$는 당연히 0이다. 그렇다면 자신의 차례에 항상 $x\ne0$이 아니라면 이기게 될 것이고 상대에게 차례가 넘어갈 때 $x=0$을 만든다면 최적이 될 것이 자명하다.

이러한 이유로, 맨 초기의 $x=0$이면 처음에 선택을 하는 사람이 지게 되는 것이고, $x\ne0$이면 이기게 되는 것이다.

Nim game 문제

https://www.acmicpc.net/problem/11871

이 문제의 경우 돌무더기에 돌의 개수가 홀수일 때와 짝수일 때를 구분하여 보면 돌의 개수가 짝수인 돌무더기에 돌이 $n$개 있으면 $(2, 4,6, … ,n-2)$개를 제거할 수 있고, $n=2$인 경우는 제거할 수 없고, 돌의 개수가 홀수인 돌무더기에 돌이 $n$개 있으면$(2,4,6,…,n-2,n-1)$개를 제거할 수 있다. 두 개의 다른점은 홀수인 무더기는 0개까지 다 없앨 수 있다는 점이고 짝수인 무더기는 2개까지 없앨 수 있다는 점이다.

돌이 $n$개가 있는 짝수 돌무더기를 돌이 $(n-2)$개가 있는 짝수 돌무더기로 변환하고 돌을 모두 없앨 수 있다($2, 4,6, … ,n-2$까지 제거가 가능) 하고, 돌이 $n$개가 있는 홀수 돌무더기를 돌이 $(n+1)$개 있는 짝수 돌무더기로 변환하고 돌을 모두 없앨 수 있다($2,4,6,…,n+1$) 하면 홀수와 짝수 동일한 관점에서 볼 수 있고, 변환해도 전혀 문제가 없다.

결국 이 문제는 전체를 2로 나눈다면 위의 $Nim$ $game$과 동일해진다.

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int main() {
	ll n, sum = 0;
	scanf("%lld", &n);
	for (int i = 0; i < n; i++)
	{
		ll p;
		scanf("%lld", &p);
		if (p % 2)
			p++;
		else
			p -= 2;
		sum ^= p;
	}
	if (sum) puts("koosaga");
	else puts("cubelover");
}

3. Grundy number

Grundy number란?

Grundy number는 $Impartial$ $game$에서 게임 상황을 $Nim$ $game$으로 변환 시켜주는 과정이라고 보면 된다. 먼저 Grundy number를 보기전에 $Mex$에 대해서 알아보자. $Mex$는 Minimum excludant의 줄인말로 어느 숫자 집합에서 그 집합에 없는 숫자중 음수가 아닌 제일 작은수를 의미한다.

예를들면 ,$mex({1,2,3})=0$ 이고, $mex({0,2,4,6,…..}) = 1$ , $mex({0,1,2,3,4,……n})=n+1$ 이 된다.

Grundy number 계산

Grundy number를 정의할 때 Grundy number가 0인 경우 게임에서 진다고 정의하자. 또한 상대편의 플레이어가 선택할 수 있는 Grundy number중 mex라고 정의하자. 편의상 상태 n에서의 Grundy number 를 $g(n)$이라고 표현 하면, $n$에서 갈수있는 곳 $a,b,c$가 있다고 정의했을 때 $g(n)=mex(g(a),g(b),g(c))$라고 보면 된다.

글로만 보면 이해하기 힘들 수 있기 때문에 Grundy number를 계산하는 것의 예시 2가지를 보도록 하자.

1. n개의 돌이 있다고 가정 하였을 때 두 플레이어가 제거 할 수 있는 돌의 개수는 1개 이상 자신이 제거 하고 싶은만큼 제거하는 게임이 있다고 하자.

$n=0$일 경우,돌이 0개있을 경우에는 g(0)은 선택할 것이 없기 때문에 g(0)=0이 된다. $n=1$일 경우,그렇다면 돌이 1개 있을 경우 우리가 갈 수 있는 상태는 1개를 선택했을 때, 즉 0인 경우밖에없다.

$g(1)=>mex({g(0)})=>mex({0})=>1$ , 즉 $g(1)=1$

$n=2$일 경우, 돌을 1개 선택,2개 선택하는 경우가 있다.

$g(2)=>mex({g(0),g(1)})=>mex({0,1})=>2$ 즉 $g(2)=2$

이러한 규칙을 보면 위의 $g(n)=mex({g(0),g(1),…..,g(n-1)})$ 이므로, $g(n)=n$이 되는 것을 볼 수 있다.

2. n개의 돌이 있다고 가정 하였을 때 두 플레이어가 제거 할 수 있는 돌의 개수는 1개 이상 3개 이하 자신이 제거 하고 싶은만큼 제거하는 게임이 있다고 하자.

$n=0$ 일 경우, 돌이 0개인 경우 당연히 $g(0)=0$ 이다.

$n=1$일 경우, 우리가 갈 수 있는 상태는 1개를 선택했을 때, 즉 0인경우 밖에없다.

$g(1)=>mex({g(0)})=>mex({0})=>1$ 즉 $g(1)=1$

$n=2$일 경우 돌을 1개, 2개 선택하는 경우가 있다.

$g(2)=>mex({g(0),g(1)})=>mex({0,1})=>2$ 즉 $g(2)=2$

$n=3$일 경우 돌을 1,2,3개 선택하는 경우가 있다.

$g(3)=>mex({g(0),g(1),g(2)})=>mex({0,1,2})=>3$ 즉 $g(3)=3$

$n=4$일 경우 돌을 1, 2, 3개 선택하는 경우가 있다. 즉 다음으로 갈 수 있는 상태는 1, 2, 3이된다.

$g(4)=>mex({g(1),g(2),g(3)})=>mex({1,2,3})=>0$ 즉 $g(4)=0$

$n=5$일 경우 $g(5)=>mex({g(2),g(3),g(4)})=>mex({2,3,0})=>1$ 즉 $g(5)=1$

$n=6$일 경우 $g(6)=>mex({g(3),g(4),g(5)})=>mex({3,0,1})=>2$ 즉 $g(6)=2$

이러한 규칙을 보면 위의 $g(n)=({g(n-1),g(n-2),g(n-3)})$ 인데 $g(n)=n$% $4$ 로 나타낼 수 있다.

승자 판별법

각 상태의 $Nim$ $game$ 과 동일하게 $Grundy$ $number $값을 구하여 xor연산을 하여 판별 하면된다. $Grundy$ $number$을 구한뒤 xor하는 것이 $Nim$ $game$과 같이 동작 할수 있는데는 다음과 같은 이유가 있다.

1. 다음 선택하는 number를 현재 grundy number보다 작은 것 만을 선택했을 경우 => nim게임과 똑같이 할 수있다.

ex) $g(8)=7$일 경우 다음 grundy number의 상태중 선택가능 한 것은 0 ~ 7이다 이렇게할 경우 항상 grundy number가 작은 것만을 선택할 경우 nim게임과 똑같은 상태가된다.

2. 다음 선택하는 number가 현재 grundy number보다 큰 것일 경우

ex) 현재 상태가 $n$이고 다음 상태가 $x$라고 했을 때 $g(n)<g(x)$인 경우를 뽑았다면 그 다음 사람이 상태 $x$ 에서 $g(n)$과 동일한 grundy number를 찾을 수 있다. 그렇기 때문에 다시 $g(n)$ 으로 돌아올 수 있어서 상태유지가 된다.

이러한 이유로 grundy number를 구한 뒤에는 $Nim$ $game$에서 처럼 xor로 승자를 판별할 수 있습니다