【算法】博弈论（C/C++）

个人主页：摆烂小白敲代码

创作领域：算法、C/C++

持续更新算法领域的文章，让博主在您的算法之路上祝您一臂之力

欢迎各位大佬莅临我的博客，您的关注、点赞、收藏、评论是我持续创作最大的动力

博弈论：

1. Grundy数与Nim博弈

Nim博弈规则：

Grundy数的计算：

例题：

2. 极大极小算法与α-β剪枝

α-β剪枝：

例题：

3. SG函数（Sprague-Grundy函数）

步骤：

例题：

4. 动态规划 + 博弈问题

步骤：

例题：

5. 后悔最小化算法（Regret Minimization）

6. 莫拉尔博弈（Impartial Games）

7. 合作博弈与流问题

8. 博弈树与搜索

例题：

原题链接：1388. 游戏 - AcWing题库

解题思路：

AC代码：

题后总结：

博弈论：

在算法竞赛中，博弈论算法也比较容易出现，一般出了博弈论的题目多少是有点难度的。博弈论算法常用于解决涉及对抗、策略选择、最优决策等问题。这类问题通常涉及两名或多名玩家在某种规则下的竞争，一般每个玩家都绝对聪明试图通过选择最优策略获胜。常见的博弈论问题类型包括零和博弈、格局游戏（如Nim博弈）、棋类游戏以及其他涉及策略选择的问题。下面介绍常见的博弈论算法。

1. Grundy数与Nim博弈

Grundy数是博弈论中一个重要的工具，常用于解具备“可分解性”的博弈问题。特别是Nim博弈是一种经典的组合博弈论问题，很多算法竞赛题目都会使用Grundy数来解，出现在算法竞赛中的概率还是非常大的。

Nim博弈规则：

- 有若干堆石子，两名玩家轮流从任意一堆中取任意数量的石子（至少取一颗）。
- 拿走最后一颗石子的玩家获胜。

Grundy数的计算：

- 对于单堆游戏，Grundy数就是该堆石子数量。
- 对于更复杂的游戏，可以将博弈分解为多个独立的子博弈。 - 将每个子博弈的Grundy数用异或操作组合起来。若异或结果为0，则当前玩家必输；否则当前玩家有必胜策略。

例题：

- 经典的Nim游戏题目。
- 使用Grundy数来解决变种的Nim博弈问题，例如多堆不同规则的Nim变种。

2. 极大极小算法与α-β剪枝

极大极小算法常用于棋类博弈（如国际象棋、五子棋等），这种算法通过递归地模拟两名玩家的所有可能行动，并假设对手总是做出最优决策。它用于确定当前玩家的最佳决策。

α-β剪枝：

α-β剪枝是极大极小算法的优化版，它通过在搜索博弈树时剪枝，减少不必要的计算。即当发现某个分支不可能提供更优的结果时，立即停止对该分支的进一步探索。

例题：

- 两人棋类游戏问题（如五子棋、国际象棋简化版）。
- 石子堆、格子游戏等需要递归搜索最优策略的题目。

3. SG函数（Sprague-Grundy函数）

SG函数（或Sprague-Grundy定理）是组合博弈中广泛使用的一种理论。它用于解决那些可以分解为“无环图”（acyclic graph）的博弈问题。这种方法本质上是计算每个局面状态的Grundy数，然后使用Nim博弈的胜负判定法则来判断游戏结果。这种问题就比较有难度了，做出来一般银牌打底了。

步骤：

1. 对每个状态，计算它的所有可能转移的后继状态。
2. 计算这些后继状态的SG值，并将SG值取为0开始，寻找使得所有后继状态的最小非负整数（Mex，minimum excludant）。
3. 使用SG函数判断博弈的结果：如果当前局面SG值为0，则处于必败态；否则为必胜态。

例题：

- 可以使用SG函数的格子类博弈，例如某些棋盘类问题（Knight's Tour，Queen问题的变种等）。
- 拆分石子堆的问题，或者分解成多种状态的小博弈组合的问题。

4. 动态规划 + 博弈问题

在博弈论中，有许多问题可以通过动态规划（DP）来求解，特别是当游戏状态有限时。这类问题的关键在于构建一个状态转移方程来描述每个局面下的最优决策。我们平时训练所做的题目一般以此为主，这种题目也是很大概率出现在赛场上的，也是相较于其他比较简单的，也是可以做出来的，动态规划+博弈论也是出题者所爱，最下面的例题则以区间DP+博弈论的问题。

步骤：

1. 定义每个状态的胜负状态（胜者或败者）。
2. 使用递归或迭代的方式填充DP表，通常可以从最终状态（例如，游戏结束状态）开始逆推。
3. 根据前一步的状态计算当前状态的胜负。

例题：

- 经典的取石子问题，玩家轮流从石子堆中取石子，可以通过DP表存储每个状态的最优策略。
- 多种棋类游戏问题，例如在有限格子中的博弈问题。

5. 后悔最小化算法（Regret Minimization）

在某些博弈中，可能需要解决多次重复的对抗问题，这种情况下后悔最小化算法可以帮助选择最优策略，使得长期的损失最小化。这个方法在算法竞赛中较少单独使用，但可以用来解决涉及多轮博弈或策略更新的问题。

6. 莫拉尔博弈（Impartial Games）

在莫拉尔博弈中，每个玩家面临相同的规则，没有特权或区别，策略的结果仅取决于游戏的状态。这类问题的分析通常借助Grundy数或者SG函数来解决，适用于算法竞赛中的许多组合博弈问题。

7. 合作博弈与流问题

某些问题涉及多个玩家的合作，通常可以通过流网络或图算法来解决。在算法竞赛中，这类问题一般涉及资源分配、网络流等问题，而合作博弈的模型可以帮助找到多方的平衡点。

8. 博弈树与搜索

对于有限状态和动作的博弈，博弈树是非常有效的工具。可以通过DFS/BFS或回溯的方法遍历整个博弈树，找到所有可能的行动路径，并根据不同策略来评估每个路径的结果。

例题：

- 棋类游戏，如井字棋、迷宫类博弈问题。 - 需要完整搜索的简单策略问题。

在算法竞赛中，博弈论算法常见的技巧包括Grundy数、极大极小算法、SG函数和动态规划。这些算法适用于解具备“对抗性”或者“合作性”的问题，如两人对抗的棋类游戏、石子堆博弈等。比赛中掌握这些技巧，不仅可以解决单一博弈问题，还能应用到更多复杂的场景中，下面就以例题区间DP+博弈论的问题讲解一下，它们是如何博弈的。

原题链接：1388. 游戏 - AcWing题库

玩家一和玩家二共同玩一个小游戏。

给定一个包含 N 个正整数的序列。

由玩家一开始，双方交替行动。

每次行动可以在数列的两端之中任选一个数字将其取走，并给自己增加相应数字的分数。（双方的初始分都是 0 分）

当所有数字都被取完时，游戏结束。

分更高的一方获胜。

请计算，如果双方都采取最优策略进行游戏，则游戏结束时，双方的得分各是多少。

输入格式

第一行包含整数 N。

后面若干行包含 N 个整数，表示这个序列。注意每行不一定恰好包含一个数。

输出格式

共一行，两个整数，分别表示玩家一和玩家二的最终得分。

数据范围

2≤N≤100,
数列中的数字的取值范围为 [1,200]。

输入样例：

6
4 7 2 9
5 2

输出样例：

18 11

解题思路：

又是这种决策游戏，思想上还是有博弈论的，玩家一与玩家二都绝对的聪明都具有上帝视角，既让自己获得分数最大，也让对方获得的分数尽量少，两个玩家都是最优策略，不存在一方每次拿最大的，另一方每次拿最小的，而且应该每个玩家都有上帝视角。

样例：4，7，2，9，5，2
玩家一（先手）：拿两边的4或2，但是我拿了4玩家二会拿7，我拿2，玩家二要么拿4要么拿5，这样7或9我势在必得一个，于是想了想我拿2
此时样例：4，7，2，9，5
玩家二：拿4的话玩家一会拿7，我拿5的话，玩家一会拿9，9>7，还是拿4划算
此时样例：7，2，9，5
玩家一：这时候肯定拿7，拿5的话，9就被玩家二拿去了
此时样例：2，9，5
玩家二：不管拿2，5都会让9被玩家1拿走，所有拿5，尽可能保证自己更大。
此时样例：2，9
玩家一：拿9

此时样例：2
玩家二：拿2，结束。

那么如何计算他们的分数呢，这就需要我们定义一个二维DP，可以看出样例中区间长度时不断递减的，每一次决策都会减少一个数，那么一个状态的DP可以由前一个状态转移过来，前一个要么取左边要么取右边，形成了此状态的DP，这不就是区间DP吗，dp[i][j]表示区间下表为i~j先手人获得的最大分数。

状态转移方程：dp[i][j]=max(w[i]+ $\sum w[k] (i<k<=j)$ -dp[i+1][j], w[i]+ $\sum w[k](i<=k<j)$ -dp[i][j-1])

这里定义的是dp[i][j]表示区间下表为i~j先手人获得的最大分数，假设选左边最优，既然选了那就要+w[i]，为什么还要加上一个区间和（i<k<=j）还要减去dp[i+1][j],这里解释一下，既然选了左端点，那么区间就变为[i+1,j]，玩家二的最优决策肯定时是dp[i+1][j],这个状态去转移玩家二下一次的最优决策，presum[j]-presum[i]为玩家二所能选的区间和，减去玩家二的最优决策所获得的分数，那么剩下的就是玩家一前一个状态的累计分数。

为了我们的状态能由上一个小状态转移过来，我们外循环枚举区间长度，这样保证了状态转移方程里面的数据已经更新了，内循环枚举区间起点，知道起点和区间长度，那么终点就可以计算出来。

AC代码：

#include<iostream>
using namespace std;
int n;
int w[105],dp[105][105],presum[105];//dp[i][j]为区间为i~j先手获得最大分数
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>w[i];presum[i]=presum[i-1]+w[i];}//区间DPfor(int len=1;len<=n;len++){//枚举区间长度for(int i=1;i+len-1<=n;i++){//枚举左端点int j=i+len-1;//右端点dp[i][j]=max(w[i]+presum[j]-presum[i]-dp[i+1][j],w[j]+presum[j-1]-presum[i-1]-dp[i][j-1]);//状态转移}}cout<<dp[1][n]<<" "<<presum[n]-dp[1][n]<<endl;return 0;
}

题后总结：

这道题跟蓝桥杯练习系统的一个题很像，但好久没有写了，也忘记思路的，区间DP感觉很难理解，代码倒是很简洁。y总讲的是另一种定义，dp的含义是先手玩家与后手玩家分数的差值，虽然好理解一点，但是这种定义一般是想不出来的，这里就用了最一般的定义去写的，望大家理解。重难点在于状态转移方程，建议自己模拟一下过程，就很好理解了，文章说的比较多，若有错误的地方请大家指出。执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。