다음 조건을 만족하는 게임에 대해 논의할 것이다.
이는 backward induction을 위한 조건으로 볼 수 있다.
Combinatorial game
1. 두 명의 플레이어가 번갈아가면서 게임을 진행한다.
2. 플레이어는 게임의 상태를 모두 알 수 있다.
3. 행동에 따른 게임 상태의 변화가 운에 의해 결정되지 않고 확정적이다.
4. 게임은 반드시 종료된다. (무한히 진행되지 않는다.)
5. 게임의 승패가 반드시 결정된다. (무승부가 존재하지 않는다.)
Impartial game
취할 수 있는 행동은 오직 게임 상태에 의해 결정된다.
플레이어에 따라 취할 수 있는 행동이 달라지지 않는다.
ex) Nim, 31 게임 cf. 체스
Normal game: 마지막에 움직이는 플레이어가 승리한다.
Misére game: 마지막에 움직이는 플레이어가 패배한다.
스프라그-그런디 함수
$$ g(x) = \begin{cases}
0 & \text{if x is a terminal position} \\
mex\{g(y) : y \in F(x)\} & \text{else}
\end{cases} $$ $X$ : 가능한 모든 게임 상태들의 집합
$F(x)$ : $x \in X$에서 행동을 취했을 때 얻을 수 있는 모든 게임 상태들의 집합. $F(x) = \emptyset$이면 $x$는 terminal position이다. (더 이상 진행이 불가능한 게임 상태)
terminal position을 base case로 두면 backward induction을 통해 모든 $g(x)$ 값을 구할 수 있다.
그런디 함수의 값은 어떤 의미를 가질까? (Normal game 기준)
1) $g(x) = 0$ $\rightarrow$ $x$ is a losing position
2) $g(x) \ne 0$ $\rightarrow$ $x$ is a winning position
증명)
유한한 차례 안에 반드시 terminal position에 도달한다.
terminal position의 $g$ 값은 $0$이다.
$g(x) = 0$이면 다음 상태의 $g$ 값은 항상 $0$이 아니다.
$g(x) \ne 0$이면 다음 상태의 $g$ 값을 $0$으로 만들 수 있다.
예시) Nim
게임 상태 = 더미 안에 남아있는 돌의 개수
$g(0) = 0$ // base case
$g(1) = mex\{g(0)\} = 1$
$g(2) = mex\{g(0), g(1)\} = 2$
$g(3) = mex\{g(0), g(1), g(2) \} = 3$
$\cdots$
$\therefore g(n) = n$
스프라그-그런디 정리
$$g((x_1, x_2, \dots, x_n)) = g(x_1) \oplus g(x_2) \oplus \cdots \oplus g(x_n)$$여러 게임을 동시에 진행하는 경우의 그런디 넘버는 각 게임판의 그런디 넘버를 xor한 값과 같다.
증명)
$ x := (x_1, x_2, \dots, x_n) $
$ b := g(x_1) \oplus g(x_2) \oplus \cdots \oplus g(x_n)$
(1) $\forall a \in [0, b)$ $\exists y \in F(x)$ $g(y) = a$
$d := a \oplus b$
$k := $ a positive integer such that $2^{k-1} \le d \lt 2^k$
정의를 풀어쓰면, $a$와 $b$의 비트 표현이 달라지기 시작하는 지점이 (오른쪽으로부터) $k$-th 비트라는 뜻이다.
이때 $a \lt b$이므로 $a$의 $k$-th 비트는 $0$, $b$의 $k$-th 비트는 $1$이다.
$b$의 정의에 의해 $g(x_i)$의 $k$-th 비트가 $1$인 $i$가 반드시 존재한다. (WLOG, $i = 1$)
$d \oplus g(x_1) < g(x_1)$이므로 $g(x_1') = d \oplus g(x_1)$를 만족하는 $x_i' \in F(x_1)$가 반드시 존재한다.
$$
\begin{equation}
\begin{aligned}
g((x_1', x_2, \dots , x_n)) &= g(x_1') \oplus g(x_2) \oplus \cdots \oplus g(x_n) \\
&= d \oplus g(x_1) \oplus \cdots \oplus g(x_n) \\
&= d \oplus b \\
&= a
\end{aligned}
\end{equation}
$$
(2) $\nexists y \in F(x)$ $g(y) = b$
(귀류법) $\exists y \in F(x)$ $g(y) = b$라고 가정하자. $$
\begin{align}
g(x_1') \oplus g(x_2) \oplus \cdots \oplus g(x_n) &= g(x_1) \oplus g(x_2) \oplus \cdots \oplus g(x_n) \\
\therefore g(x_1') &= g(x_1)
\end{align}
$$ 이는 그런디 함수 정의에 모순이다.
문제 풀이
11868번 - 님 게임 2
게임 상태 = 더미 안에 남아있는 돌의 개수
$g(n) = n$
$x :=$ 각 더미 안에 있는 돌의 개수를 xor한 값
$x \ne 0$이면 선공이 이기고, $x = 0$이면 후공이 이긴다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int x = 0;
while (n--) {
int a; cin >> a;
x ^= a;
}
if (x) cout << "koosaga";
else cout << "cubelover";
return 0;
}
|
cs |
16895번 - 님 게임 3
님 게임 2에서는 누가 이기는 지를 물었고, 이 문제는 어떻게 이기는 지를 묻는다.
다음 상태의 그런디 넘버가 $0$이 되도록 만들면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<int> v(n);
int x = 0;
for (int i = 0; i < n; i++) {
cin >> v[i];
x ^= v[i];
}
if (x) {
int ans = 0;
for (int i: v) {
if ((x^i) < i) ans++;
}
cout << ans;
}
else cout << 0;
return 0;
}
|
cs |
16877번 - 핌버
일반 님 게임과 규칙이 다르다.
그런디 넘버를 새로 구해야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <bits/stdc++.h>
using namespace std;
const int MAX = 3e6;
const int MAX2 = 32;
int dp[MAX+1];
int fibo[MAX2] = {1, 2};
vector<bool> visited(MAX2);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
for (int i = 2; i < MAX2; i++) {
fibo[i] = fibo[i-1] + fibo[i-2];
}
for (int i = 1; i <= MAX; i++) {
visited.assign(MAX2, false);
for (int j = 0; j < MAX2 && i - fibo[j] >= 0; j++) {
visited[dp[i - fibo[j]]] = true;
}
for (int j = 0; j < MAX2; j++) {
if (!visited[j]) {
dp[i] = j;
break;
}
}
}
int n; cin >> n;
int x = 0;
while (n--) {
int a; cin >> a;
x ^= dp[a];
}
cout << (x ? "koosaga" : "cubelover");
return 0;
}
|
cs |
11871번 - 님 게임 홀짝
이 문제 역시 그런디 넘버를 새로 구해야 한다.
$g(0) = 0$ // base case
$g(1) = mex\{g(0)\} = 1$
$g(2) = 0$ // base case
$g(3) = mex\{g(0), g(1)\} = 2$
$g(4) = mex\{g(2)\} = 1$
$g(5) = mex\{g(0), g(1), g(3)\} = 3$
$g(6) = mex\{g(2), g(4)\} = 2$
$\cdots$
\(\therefore g(n) =
\begin{cases}
0 & n = 0, 2 \\
\frac{n+1}{2} & \text{if $n$ is odd} \\
\frac{n-2}{2} & \text{if $n$ is even and $n \gt 2$}
\end{cases}
\)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int x = 0;
while (n--) {
int a; cin >> a;
if (a & 1) x ^= (a + 1 >> 1);
else x ^= (a - 1 >> 1);
}
cout << (x ? "koosaga" : "cubelover");
return 0;
}
|
cs |
13034번 - 다각형 게임
선분을 그으면 선분을 기준으로 게임이 분할된다.
게임 상태 = 꼭짓점의 개수
$g(0) = g(1) = 0$ // base case
$g(2) = 1$ // base case
$g(3) = mex\{g(0) \oplus g(1)\} = 0$
$g(4) = mex\{g(0) \oplus g(2), g(1) \oplus g(1)\} = 2$
$g(5) = mex\{g(0) \oplus g(3), g(1) \oplus g(2)\} = 2$
$g(6) = mex\{g(0) \oplus g(4), g(1) \oplus g(3), g(2) \oplus g(2)\} = 1$
$\cdots$
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<int> dp(n+1);
vector<bool> visited(16);
dp[2] = 1;
for (int i = 3; i <= n; i++) {
visited.assign(16, false);
for (int j = 0; j <= i - 2 - j; j++) {
visited[dp[j] ^ dp[i - 2 - j]] = true;
}
for (int j = 0; j < 16; j++) {
if (!visited[j]) {
dp[i] = j;
break;
}
}
}
cout << (dp[n] ? 1 : 2);
return 0;
}
|
cs |
3596번 - 크로스와 크로스
이미 'x' 마크가 있는 칸을 중심으로 두 칸 이하 떨어진 곳에 마크하면 패배한다.
이를 게임이 분할되는 것으로 볼 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
vector<int> dp(2001);
vector<bool> visited(100);
dp[1] = dp[2] = dp[3] = 1;
for (int i = 4; i <= 2000; i++) {
visited.assign(100, false);
for (int j = 1; j <= (i + 1 >> 1); j++) {
int tmp = dp[i-j-2] ^ (j - 3 > 0 ? dp[j-3] : 0);
visited[tmp] = true;
}
for (int j = 0; j < 100; j++) {
if (!visited[j]) {
dp[i] = j;
break;
}
}
}
int n; cin >> n;
cout << (dp[n] ? 1 : 2);
return 0;
}
|
cs |
11717번 - Wall Making Game
어떤 cell에 마크하면 게임판이 해당 cell 기준 top-left, top-right, bottom-left, bottom-right으로 나뉜다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <bits/stdc++.h>
using namespace std;
int h, w;
const int MAX = 23;
const int MAX2 = 100;
string board[MAX];
int dp[MAX][MAX][MAX][MAX];
inline bool outsideBoard(int y, int x) {
return y < 0 || y >= h || x < 0 || x >= w;
}
int f(int i, int j, int p, int q) {
if (outsideBoard(i, j) || outsideBoard(p, q) || i > p || j > q) return 0;
if (dp[i][j][p][q] != -1) return dp[i][j][p][q];
vector<bool> visited(MAX2);
for (int a = i; a <= p; a++) {
for (int b = j; b <= q; b++) {
if (board[a][b] == 'X') continue;
int tmp = 0;
tmp ^= f(i, j, a - 1, b - 1);
tmp ^= f(i, b + 1, a - 1, q);
tmp ^= f(a + 1, j, p, b - 1);
tmp ^= f(a + 1, b + 1, p, q);
visited[tmp] = true;
}
}
for (int t = 0; t < MAX2; t++) {
if (!visited[t]) {
return dp[i][j][p][q] = t;
}
}
return 0;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> h >> w;
for (int i = 0; i < h; i++) {
cin >> board[i];
}
memset(dp, -1, sizeof(dp));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
dp[i][j][i][j] = (board[i][j] == '.');
}
}
cout << (f(0, 0, h - 1, w - 1) ? "First" : "Second");
return 0;
}
|
cs |
18937번 - 왕들의 외나무다리 돌게임
이 게임은 impartial game이 아니고, 유한한 차례 안에 반드시 종료되지도 않는다.
그러나 잘 생각해보면 Nim과 동일함을 알 수 있다.
상대방이 뒤로 물러설 경우 같은 거리만큼 이동하여 따라가면 된다.
게임 상태 = Whiteking과 Blackking 사이 빈 칸의 개수
$g(n) = n$
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int a, x = 0;
while (n--) {
cin >> a;
x ^= a - 2;
}
string s; cin >> s;
cout << ((s[0] != 'W') == !x ? "Whiteking" : "Blackking");
return 0;
}
|
cs |
11694번 - 님 게임
지금까지 다룬 게임들은 모두 Normal game이다.
Misére game은 Normal game과 비슷하지만 살짝 다르다.
// 풀이 추가 예정
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int x = 0;
int flag = 0;
while (n--) {
int a; cin >> a;
if (a > 1) flag++;
x ^= a;
}
if (flag && !x || !flag && x == 1)
cout << "cubelover";
else
cout << "koosaga";
return 0;
}
|
cs |
11062번 - 카드 게임
그런디 없이 게임 이론으로 푸는 문제이다.
$dp[i][j]$: $[i, j]$ 구간에서 얻을 수 있는 최대 점수
\(
dp[i][j] =
\begin{cases}
v[i] & \text{if $i = j$} \\
max(v[i]+psum[i+1 \dots j] - dp[i+1][j], \\
\quad \quad \, v[j]+psum[i \dots j-1] - dp[i][j-1]) & \text{else}
\end{cases}
\)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <bits/stdc++.h>
using namespace std;
int main(void) {
cin.tie(NULL);
ios::sync_with_stdio(false);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> v(n), psum(n+1);
for (int i = 0; i < n; i++) {
cin >> v[i];
psum[i+1] = psum[i] + v[i];
}
vector<vector<int> > dp(n, vector<int>(n, -1));
for (int i = n-1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (i == j) {
dp[i][j] = v[i];
}
else {
dp[i][j] = v[i] + psum[j+1] - psum[i+1] - dp[i+1][j];
dp[i][j] = max(dp[i][j], v[j] + psum[j] - psum[i] - dp[i][j-1]);
}
}
}
cout << dp[0][n-1] << '\n';
}
return 0;
}
|
cs |
참고 자료
https://web.mit.edu/sp.268/www/nim.pdf
https://sites.oxy.edu/ron/math/400/09/The%20Game%20Of%20Nim.pptx
'알고리즘' 카테고리의 다른 글
| Equivalence Relation and Partition (0) | 2022.07.06 |
|---|---|
| 이분 탐색 (0) | 2021.07.15 |