2.games

게임이론 주제는 코포나 ps에 있어서 굉장히 자주 나오는 주제이다.

애초에 수학적으로 재밌는 주제이기도 하고, ps에서는 dp라는 해결방식을 통해, 컴퓨터의 계산능력을 이용해서 무지성으로 뚫어버리는 풀이가 가능하기 때문에 자주 사용하는 것 같다.

 

우선 이 글에서 스프라그-그런디 정리는 배제하고 설명하겠다.

(스프라그 그런디 정리는 궁금하면 꼭 찾아보길 바란다. 코포에 안나오기는 하는데, 백준 연습문제도 많고 icpc셋 돌다가 한 두번 마주친 것 같다.)

 

 

 

 

game 문제를 풀 때 중요하게 생각해야 할 것은 4가지 정도가 있는 것 같다.

 

 

1.지는 상태를 회피 할 수 있는가?

 

2.항상 이기는 전략이 존재하는가?

 

3.전략은 모르지만 규칙성이 존재하는가?

 

4.무지성 dp로 해결이 가능한가?

 

 

 

 

 

1. 지는 상태를 회피 할 수 있는가?

 

순차적으로 조금은 더 세부적으로 설명을 하겠다.

우선 나는 1번과 같은 유형을 굉장히 좋아한다.

지는 상태를 회피하는 전략으로 해결가능한 문제라 함은,

 

 

지금 게임판의 상황에서 최적으로 플레이했을때 내가 이기면 플레이하고 패배하면 상대에게 동일한 상태로 넘겨주기

즉 같은 상태에서 턴을 바꿔버려서 내가 이기기

 

아니 이게 무슨 말이지?

이거.. 의외로 문제로 보는게 더 이해가 편할 수 있다.

 

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

정말 이 유형의 대표적인 문제이다.

기본 문제를 던져 주었기 때문에 풀이를 먼저 설명하겠다.

n이 1이 아니면 선공이 승리한다.

왜 그럴까? 지는 상태를 회피 할 수 있다는 관점에서 접근을 해보자.

우리가 어떤 수를 고르면, 약수를 모두 지운다...

그런데 1은 모든 수의 약수이다.

이말에 숨겨진 뜻은, 선공이 어떤 수를 선택을 하던, 1은 없어진다는 것이다.

즉 1은 있든 없든, 비슷한 게임판인다.

 

그렇다면 선공은 이러한 전략을 취한다.

이 게임판이 선공이 지는 게임판이면, 1을 고른다. 그러면 동일한 게임판을 상대가 선공,내가 후공인채로 시작하게 된다. 즉 지는 게임을 회피할 수 있다.

이기는 게임판이면, 최적의 전략이 뭔지 모르겠지만, 승리한다.

 

이렇듯, 최적의 전략은 알필요도 없고, 위와 같은 전략만으로도, 항상 승리하는 그런 유형이다.

 

*연습문제

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

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

 

 

 

 

 

 

 

2. 항상 이기는 전략이 존재하는가?

이 유형이 제일 어렵다... 그냥 그리디 문제 푸는거랑 똑같은 느낌이라고 보면 된다. 

말 그대로 최적의 전략이 존재해서, 그걸 택하는 방식으로 승리할 수 있다는 것이 보장되는가?

라는걸 묻고 있는데... 1번유형과 다르게 최적의 전략을 찾아야 한다.

 

사실 이 문제가 극한의 애드혹인데, 그래도 어느정도 팁을 찾아주자면... 상대방이 무엇을 하던 동일한 상태를 보장할 수 있는 방법이 있는가? 처럼 접근을 하면 조금은 도움이 된다. 근데 그냥 어렵다 ㅠ 많이 풀어보는게 좋을 것 같다.

 

 

*연습문제
https://codeforces.com/contest/1527/problem/B2

(이 문제는 B1부터 읽고 푸는걸 추천한다. B2만 있었다면 난이도는 2배 이상 올라갔을 것이다.)
https://codeforces.com/problemset/problem/1147/C

어려운 문제. 찾아보면 풀이가 여기 블로그에 있다.

 

 

 

 

 

 

 

 

 

3.전략은 모르지만 규칙성이 존재하는가?

 

 

 

사실 2번으로 풀리는 문제들이, 3번 문제다. 그런데, 언급했다시피 최적의 전략을 증명하고 찾아내기는 너무 어렵고, 규칙을 찾는다는 접근 방식으로 가서 해결할 수 있는 경우도 있다. 필자도 최근 코포 한 문제를 그렇게 찾아냈다.
보통은 시간복잡도에는 안맞는 dp를 이용하거나, 완전탐색을 이용해서 주어진 input보다 훨씬 작은 input들에 대한 규칙을 찾아내고, 그 규칙을 이용해서, 정답을 도출해내면 된다.

https://codeforces.com/contest/1537/problem/D

정말 답도 없는 문제다.

그런데 dp로 돌려보면 정말정말정말 쉬운 규칙성이 발견된다.

그대로 찾아서 넣어주면 ok이다.

dp로 게임이론을 푸는 방법은 4번에서 설명하겠다.

위 문제의 코드는 다음과 같다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<stack>
#include<map>
#include<set>
#include<deque>
#include<functional>
#include<unordered_map>
#include<list>

//#define double long double
//s.erase(unique(s.begin(),s.end()),s.end())
//written by djs100201
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 3e5 + 100, inf = 1e18, mod = 1e9 + 7, sqrtN = 333, p = 27;
ll n, m, k, tc = 1, a, b, c, d, x, y, z, ans, base;
ll dp[n_];
ll gcd(ll x, ll y) {
	if (!y)return x;
	return gcd(y, x % y);
}
ll f(ll x) {
	if (dp[x] != -1)return dp[x];
	if (x == 116)
		x = 116;
	for (ll i = 2; i * i <= x; i ++) {
		if (x % i)continue;
		if (!f(x - i) || !f(x-x/i))return dp[x] = 1;
	}
	return dp[x] = 0;
}
ll pr(ll x) {
	for (ll i = 3; i * i <= x; i += 2) {
		if (x % i == 0)return false;
	}
	return true;
}
void solve() {
	
	/*for (int i = 1; i <= 10000; i++) {
		if (f(i)) cout << "Alice " << i << '\n';
		else cout << "Bob " << i << '\n';
	}*/
	
	cin >> n;
	if (n % 2)cout << "Bob ";
	else {
		a = 0;
		while (n % 2==0)n /= 2, a++;
		if (n == 1 && a % 2)cout << "Bob";
		else cout << "Alice";
	}
	cout << '\n';
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	memset(dp, -1, sizeof(dp));
	dp[1] = 0, dp[2] = 0, dp[3] = 0;
	cin >> tc;
	while (tc--)solve();
}

 

 

접은 글에는 코드가 공개되어 있는데, 보면 알겠지만 n<=10000인 케이스에 대해 dp로 규칙 처리한 흔적이 보인다. 

 

*연습문제
https://www.acmicpc.net/problem/2373

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

 

 

 

 

 

 

 

 

4.무지성 dp로 해결이 가능한가?

 

 

 

dp로 게임이론 자체를 구체화 시킬 수 있다. 

dp[x]를 x상태일때 선공이 이길 수 있는가? 로 정의하게 되면, 접근 가능한 모든 상태들을 고려하면서 dp table을 모순되지 않게 채워 나갈 수 있다면, dp로 풀면 된다.

 

예를 들어, https://www.acmicpc.net/problem/9655 유명한 돌게임을 예시로 들면,

win[1] = true;
win[2] = false;
win[3] = true;
for (int i = 4; i <= n; i++)
if (!win[i - 1] || !win[i - 3])win[i] = true;

이 부분만 적어주면 충분히 dp로 해결이 가능하다.
dp는, 3번을 이용하는 한 가지 방법이기도 하다.
그런데 dp로 풀리는 문제를 코포에서는 본적이 없다... 백준은 많이 있다.

열공하자

 

*연습문제
https://www.acmicpc.net/problem/11062