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

个人主页：把烂小白敲代码。

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

算法领域的文章不断更新，让博主在你的算法之路上祝你一臂之力。

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

目录。

游戏论：

1. Grundy数与Nim博弈。

Nim游戏规则：

计算Grundy数：

例题：

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

α-β剪枝： 。

例题：

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

步骤：

例题：

4. 动态规划 + 博弈问题。

步骤：

例题：

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

6. 莫拉尔博弈#xff08;Impartial Games）

7. 合作博弈与流问题。

8. 游戏树和搜索。

例题：

原始链接󿄚1388. 游戏 - AcWing题库。

解题思路：

AC代码：

总结问题后：

游戏论：

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

1. Grundy数与Nim博弈。

Grundy数。是博弈论中的重要工具，常用于解具”。可分解性。游戏问题。特别是Nim游戏是一个经典的组合游戏问题，Grundy数用于许多算法竞赛题目，算法竞赛中出现的概率还是很大的。

Nim游戏规则：

- 有几堆石头，两名玩家轮流从任何一堆中取任何数量的石头（至少取一个）。
- 拿走最后一块石头的玩家获胜。

计算Grundy数量：

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

例题：

- 经典的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函数c;例如，一些棋盘问题（Knight's Tour，Queen问题的变种等）。
- 石堆拆分问题，或分解成各种状态的小游戏组合的问题。

4. 动态规划 + 博弈问题。

在博弈论中，有许多问题可以通过。动态规划。（DP）求解，尤其是游戏状态有限的时候。这类问题的关键在于构建一个状态转移方程来描述每种情况下的最佳决策。我们平时在训练中做的题目一般都是以此为主，这类话题也很有可能出现在赛场上，与其他相比，它也相对简单，也可以做，动态规划+博弈论也受到作者的喜爱，以区间DP+为例;博弈论的问题。

步骤：

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

例题：

- 经典的取石问题，玩家轮流从石堆里取石头，每个状态的最佳策略都可以通过DP表存储。
- 各种棋类游戏问题，比如有限格子中的游戏问题。

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

在某些游戏中，可能需要解决。多次重复。对抗问题，在这种情况下，后悔最小化算法有助于选择最佳策略，长期使用。损失最小化。。该方法在算法竞赛中很少单独使用，但是，它可以用来解决涉及多轮游戏或战略更新的问题。

6. 莫拉尔游戏（Impartial Games）

在莫拉尔博弈中，每个玩家都面临着相同的规则，没有特权或差异，战略的结果只取决于游戏的状态。Grundy数或SG函数通常用于解决这类问题c;许多组合游戏问题适用于算法竞赛。

7. 合作博弈与流问题。

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

8. 游戏树和搜索。

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

例题：

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

在算法竞赛中，Grundy数、大大小小算法、SG函数和动态规划是游戏算法中常见的技能。这些算法适用于解决“对抗”或“合作”的问题，比如两人对抗的棋类游戏，石堆游戏等等。在比赛中掌握这些技能󿀌不仅可以解决单一游戏问题，它还可以应用于更复杂的场景，以下是例题区间DP+解释博弈论问题，他们是怎么玩的？

---

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

玩家一和玩家二一起玩一个小游戏。

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

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

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

当所有数字都完成时󿀌游戏结束。

得分较高的一方获胜。

请计算，如果。在游戏中，双方都采取了最佳策略。，游戏结束时，双方的分数是多少？

输入格式。

第一行包含整数 N。

后面包含了几行 N 整数，表示这个序列。请注意，每行不一定只包含一个数字。。

输出格式。

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

数据范围。

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

输入样本：

64 7 2 95 2。

输出样本：

18 11。

---

解题思路：

这种决策游戏，思想上还是有博弈论的，玩家一和玩家二都绝对聪明，都有上帝的视角，让自己得到最大的分数󿀌也让对方得到尽可能少的分数，两个玩家都是最好的策略，没有一方每次都拿最大的，每次对方拿最小的，而且每个玩家都应该有上帝的视角。

示例：4，7，2，9，5，2。
玩家1（先手）：拿两边的4或2，但是我拿了4个玩家，2个玩家拿了7࿰。c;我拿2，玩家二要么拿4，要么拿5，这样7或9我势必得到，所以想了想，我拿了2。
此时样例：4，7，2，9，5。
此时的样例󿄚4，7，2，9，5.玩家2：如果玩家拿4，玩家会拿7，我拿5的话，玩家会得到9，9>7，还是拿4划算。
此时样例：7，2，9，5。
玩家1：这个时候一定要拿7󿀌拿5的话，9被玩家二拿走了。
此时样例：2，9，5。
玩家2：不管你拿2󿼀，不管你拿2�9被玩家1拿走，#xff0c;所有5�尽量保证自己更大。
此时的样例󿄚2，9。
玩家1：拿9。

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

那么如何计算他们的分数࿰呢？c;这就要求我们定义一个二维DP󿼌可以看到样本中间隔长度不断下降的，每一个决定都会减少一个数字，然后一个状态的DP可以从前一个状态转移到，前者要么取左边，要么取右边󿀌DP࿰形成这种状态c;这不是区间DP࿰吗？c;dp[i][j]表示区间下表为i~j先手人获得的最大分数。。

。状态转移方程：dp[i][j]=max(w[i]+-dp[i+1][j],  w[i]+ 。

-dp[i][j-1])。

dp在这里定义[i][j]表示区间下表为i~j先手获得的最大分数，假设选择最好的左边󿀌既然选择了，就要+w[i]，为什么要加一个区间和（i<k<=j）还要减去dp[i+1][j],这里解释一下，既然选择了左端点，然后区间就变成了[i+1,j]，玩家2的最佳决策必须是dp[i+1][j],在这种状态下，转移玩家第二次的最佳决策，presum[j]-presum[i]为玩家2选择的区间和，减去玩家2的最佳决策得分，然后剩下的就是玩家以前状态的累计分数。

---

为了让我们的状态从最后一个小状态转移到，外循环枚举区间长度，这样就保证了状态转移方程中的数据已经更新，内循环枚举区间起点󰀌知道起点和区间长度，然后可以计算终点。

AC代码：

---

#include<iostream>using namespace std;int n;int w[105],dp[105][105],presum[105];//dp[i][j]i~j先手获得最大分数 main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>w[i]; presum[i]=presum[i-1]+w[i]; }///区间DP for(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;}。

总结问题后：

这个问题和蓝桥杯练习系统的问题很像，但是很久没有写࿰了c;也忘记了࿰的想法c;区间DP感觉很难理解#xff0c;代码很简单。y总是说另一个定义，dp的含义是先手玩家和后手玩家分数的差异，虽然很容易理解一点，但这个定义通常是无法想象的，在这里，我们使用最一般的定义来编写，希望大家能理解。重点和难点在于状态转移方程󿀌建议自己模拟过程，很容易理解，文章更多，如有错误，请指出。重点和难点在于状态转移方程󿀌建议自己模拟过程，很容易理解，文章更多，如有错误，请指出。到目前为止，写作，感觉彼多�全文将至󿼌写作结束，感谢您的支持。