The Deep Dark Relationship Between GAME THEORY and DYNAMIC PROGRAMMING

博弈论与DP不可不说的神秘羁绊

Table of Contents

  1. Overview
  2. Examples
    1. Problem 1 USACO Training Section 3.3 A Game
      1. Description
      2. Solution
      3. Code
    2. Problem 2 UVa 10891
      1. Description
      2. Solution
      3. Code
    3. Problem 3 CF786A
      1. Description
      2. Solution
      3. Code
    4. Problem 4 JZOJ 5778
      1. Description
      2. Solution
      3. Code
    5. Problem 5 [N/A N/A]
      1. Description
      2. Solution
  3. Summary

Overview

见博弈想DP? 果然我见题少. 这是一篇有一些博弈+DP的总结.

Examples

Problem 1 USACO Training Section 3.3 A Game

Description

给定一个正整数数列, 每次可以从左端或右端取一个数, 得分记为所取数的和. 现有两人博弈, 欲使得分最大. 计算双方均采取最优策略下两玩家得分情况.

Solution

既然双方均采取最优策略, 我们就可以定义一个先手最优状态, 显然每个玩家操作时, 把她视为先手, 采用这个策略就可以了.

博弈的套路一般是从最终结果倒推, 本题是计分游戏, 所以我们定义最终的状态就是取最后一个数的贡献, 即$f[i][i] = a[i]$.

对于状态 $f[i][j]$ 考虑还原一步, 则上一手一定是$f[i - 1][j]$ 或 $f[i][j+1]$, 这也就是说, $f[i][j]$一定由$f[i + 1][j], f[i][j - 1]$转移而来.

考虑最大化$f[i][j]$, 由于这一步的贡献将是$sum[i, j] - f[i + 1]j$, 所以我们要在两种状态中选一个较小的.

注意! 为了保证每次决策都是先手最优策略, 在博弈问题中通常不对单个点进行决策, 而是从上一步的最优策略转移而来, 对于本题, 意味着我们不要考虑怎样对于一个状态决策选左端还是右端来推进游戏, 而是决策选左端还是右端的最优策略来还原游戏.

Code

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using std::min;
using std::memset;

const int maxn = 105;

int n;
int a[maxn], sum[maxn], f[maxn][maxn];

int main()
{
    scanf("%d", &n);
    memset(f, 0, sizeof f);
    memset(sum, 0, sizeof sum);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
    for(int i = 1; i <= n; ++i) f[i][i] = a[i];
    for(int len = 2; len <= n; ++len)
        for(int l = 1; l <= n - len + 1; ++l)
        {
            int r = l + len - 1;
            int s = min(f[l + 1][r], f[l][r - 1]);
            f[l][r] = sum[r] - sum[l - 1] - s;
        }
    printf("%d %d\n", f[1][n] , (sum[n] - f[1][n]));
    return 0;
}

Problem 2 UVa 10891

Description

给定一个整数序列, 两人轮流从左端或右端取走一段连续的数, 得分为数字的和, 双方均采取最优策略, 求最后先手和后手的分差.

Solution

进阶的上一题, 除了取数方式的变化, 还引入了负数, 但本质思想是不变的.

转移从左端和右端变为了一段, 所以增加一层循环枚举断点, 仍然是$sum - f[][]$, 需要注意的是, 由于可以把一整段全取走, 而不给对手留机会, 也就是$0$可能比$f[][]$ 更优, 所以我们需要用$0$和$f$数组取最小值.

Code

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using std::min;
using std::memset;

const int maxn = 105;

int n;
int a[maxn], sum[maxn], f[maxn][maxn];

int main()
{
    while(scanf("%d", &n) && n)
    {
        memset(f, 0, sizeof f);
        memset(sum, 0, sizeof sum);
        for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
        for(int i = 1; i <= n; ++i) f[i][i] = a[i];
        for(int len = 2; len <= n; ++len)
            for(int l = 1; l <= n - len + 1; ++l)
            {
                int r = l + len - 1;
                int s = 0;
                for(int k = l; k < r; ++k)
                    s = min(s, min(f[l][k], f[k + 1][r]));
                f[l][r] = sum[r] - sum[l - 1] - s;
            }
        printf("%d\n", f[1][n] - (sum[n] - f[1][n]));
    }
    return 0;
}

Problem 3 CF786A

Description

两个人轮流选择手中一张卡, 值为$v_i$, 移动怪物, 怪物将由当前位置在环上前进$v_i$步, 怪物进入1则胜利, 另一方失败. 可能平局(无限循环). 计算怪物初始位置为$[2, n]$, 两人分别先手时的游戏情况.

Solution

依然是从最终状态反推, 当怪物在格子1时游戏结束, 我们选取它作为最终态, 同样, 这是一个先手状态. 由于上一步的人已经赢了, 所以这个状态必败.

接下来是转移, 如果一个人从$pos$出发, 使用所有的卡到达的都是先手必胜态, 则这个状态必败, 只要有一张卡能到达先手必败态, 这就是一个先手必胜态.

如果始终没有访问过这个状态, 说明该状态是平局.

用队列BFS来做转移, 因为跳步比较乱, 而且是在环上.

Code

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using std::memset;
using std::queue;

const int maxn = 7005;

struct sta
{
    int pos, id, wn;
    constexpr sta(int p = 0, int i = 0, int w = 0):
        pos(p), id(i), wn(w) {}
    //wn: 0 first lose, 1 first win.
};
int n, k[3], s[3][maxn], f[maxn][3], sum[maxn][3];
bool vis[maxn][3];
queue<sta> q;

int main()
{
    scanf("%d", &n);
    scanf("%d", &k[1]); for(int i = 1; i <= k[1]; ++i) scanf("%d", &s[1][i]);
    scanf("%d", &k[2]); for(int i = 1; i <= k[2]; ++i) scanf("%d", &s[2][i]);
    q.push(sta(1, 1, 0)); vis[1][1] = 1; f[1][1] = 0;
    q.push(sta(1, 2, 0)); vis[1][2] = 1; f[1][2] = 0;
    while(!q.empty())
    {
        sta u = q.front(); q.pop();
        int curid = 3 - u.id;
        if(u.wn == 0)
        {
            for(int i = 1; i <= k[curid]; ++i)
            {
                int npos = (u.pos - s[curid][i] + n) % n;
                if(npos == 0) npos = n;
                if(!vis[npos][curid])
                {
                    f[npos][curid] = 1;
                    q.push(sta(npos, curid, 1));
                    vis[npos][curid] = 1;
                }
            }
        }
        else
        {
            for(int i = 1; i <= k[curid]; ++i)
            {
                int npos  = (u.pos - s[curid][i] + n) % n;
                if(npos == 0) npos = n;
                sum[npos][curid]++; //统计必胜态数量
                if(!vis[npos][curid] && sum[npos][curid] == k[curid])
                {
                    f[npos][curid] = 0;
                    q.push(sta(npos, curid, 0));
                    vis[npos][curid] = 1;
                } 
            }
        }
    }
    for(int i = 2; i <= n; ++i)
    {
        if(vis[i][1])
        {
            if(f[i][1]) printf("Win ");
            else printf("Lose ");
        }
        else printf("Loop ");
    }
    putchar('\n');
    for(int i = 2; i <= n; ++i)
    {
        if(vis[i][2])
        {
            if(f[i][2]) printf("Win ");
            else printf("Lose ");
        }
        else printf("Loop ");
    }
}

Problem 4 JZOJ 5778

Description

有一个环, 环上的两种人轮流报数, 一定比上一个人大, 同时有区间限制, 先报数到上限的阵营输, 计算以第$i$个人开始的游戏情况.

Solution

最终态是先手报出 $m$ 必败, 由于我们不知道游戏在哪里结束, 所以从最坏情况开始, 也就是从第 $n$ 个动物开始, 每次$+1$, 这意味着最多到第 $n + m - 1$ 个动物, 把环复制一下.

考虑转移, 由于这不是一个双人博弈游戏, 需要考虑的变多了.

如果上一个人在有效区间内没有必胜态(计数优化一下), 若她是队友, 则这个人报出这个数也是一个必败态, 反之是必胜态.
如果有必胜态, 且她是队友, 则这个人报出这个数是必胜态, 反之是必败态.

这和上一题的转移差不多, 但加入了下一个人是不是队友的考量, 很新颖.

最终答案就看从这个人开始, 首次报数区间内有没有必胜态, 有就必胜, 没有则必败.

Code

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using std::min;
using std::max;
using std::memset;

const int maxn = 5005;

int n, m, k, f[maxn << 1][maxn];
int a[maxn << 1];

int main()
{
	freopen("vode.in", "r", stdin);
	freopen("vode.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for(int i = n + 1; i <= n + m; ++i) a[i] = a[i - n];
	for(int i = n + m - 1; i; --i)
	{
		int lst = -1; 
		for(int j = m - 1; j >= 1; --j)
		{
			if(lst == -1 || lst - j > k) f[i][j] = (a[i] != a[i + 1]);
			else f[i][j] = (a[i] == a[i + 1]);
			if(f[i + 1][j]) lst = j;
		}
	}
	for(int i = 1; i <= n; ++i)
	{
		bool sol = false;
		for(int j = 1; j <= k; ++j)
		{
			if(f[i][j]) {sol = true; break;}
		}
		printf("%d ", sol ? a[i] : (a[i] ^ 1));
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Problem 5 [N/A N/A]

Description

有一列正整数, 每次可以任意取几个, 按其中最小值计分, 目标是最大化分差, 双方都采取最优策略, 计算最大分差.

Solution

首先, 按最小值计分, 取太大的一定不会更优, 而取数没有位置限制, 所以我们把数从小到大排序, 每次取一段或者一个, 这一定不会更劣.

考虑转移, 这一次我们要顺推, 因为下一步的最优策略的计算基于上一步的最优策略. 而取完最后一个数的状态是明确的, 反而第$0$步的分差是明确的.

定义一个先手最大分差状态 $f[i]$, 即取到第 $i$ 位的先手最大分差, 根据定义显然 $f[0] = 0$. 对于一个状态 $f[i]$, 考虑怎样最大化这一步的分差.
如果我们就取第 $i$ 个(此时取后面的没有用), 那么最终分差就是 $a[i] - f[i-1]$, 注意到这样的策略可能并不是最优的, 这时我们就可以连 $i-1$ 一起取了, 因为取后面的不会对最小值产生影响, 取前面的会, 贡献就是取 $i-1$ 的先手最大分差. 这是什么? $f[i-1]$啊.

方程: $f[i] = max(f[i - 1], a[i] - f[i - 1]), (f[0] = 0)$

Summary

两类博弈问题: 胜负博弈/计分博弈

通常的套路都是从最终状态反向转移.T5是例外.

对于胜负类博弈问题, 通常对下一步的先手必胜态进行计数,前/后缀和优化, 然后还原这一步的状态, 如T3/4的转移方式保证了每一步选择的都是最优策略.

对于计分类博弈问题, 通常在上/下一步的几个最优策略中作比较, 注意也有可能存在这一步直接结束游戏(不给下一个先手留机会), 或者吞并上一步的最优策略的情况, 这取决于游戏规则的限制.

经典操作是计算每一个状态时转换先手, 然后让上/下一步的先手最劣(或吞并), 从而取得这一步的最优.