【算法】博弈论(C/C++)

简介: 【算法】博弈论(C/C++)

博弈论

在算法竞赛中,博弈论算法也比较容易出现,一般出了博弈论的题目多少是有点难度的。博弈论算法常用于解决涉及对抗、策略选择、最优决策等问题。这类问题通常涉及两名或多名玩家在某种规则下的竞争,一般每个玩家都绝对聪明试图通过选择最优策略获胜。常见的博弈论问题类型包括零和博弈、格局游戏(如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]+ -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],玩家二的最优决策肯定时是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];
  }//区间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;
}
题后总结:

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

相关文章
|
5月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
109 2
|
7月前
|
存储 负载均衡 算法
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
180 15
|
2月前
|
机器学习/深度学习 算法 网络性能优化
【EI复现】基于元模型优化算法的主从博弈多虚拟电厂动态定价和能量管理(Matlab代码实现)
【EI复现】基于元模型优化算法的主从博弈多虚拟电厂动态定价和能量管理(Matlab代码实现)
|
7月前
|
存储 算法 数据处理
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中,公司局域网管理至关重要。哈希表作为一种高效的数据结构,通过哈希函数将关键值(如IP地址、账号)映射到数组索引,实现快速的插入、删除与查找操作。例如,在员工登录验证和设备信息管理中,哈希表能显著提升效率,避免传统线性查找的低效问题。本文以C++为例,展示了哈希表在局域网管理中的具体应用,包括设备MAC地址与IP分配的存储与查询,并探讨了优化哈希函数和扩容策略,确保网络管理高效准确。
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
83 0
|
5月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
145 17
|
4月前
|
机器学习/深度学习 存储 算法
基于 C++ 布隆过滤器算法的局域网上网行为控制:URL 访问过滤的高效实现研究
本文探讨了一种基于布隆过滤器的局域网上网行为控制方法,旨在解决传统黑白名单机制在处理海量URL数据时存储与查询效率低的问题。通过C++实现URL访问过滤功能,实验表明该方法可将内存占用降至传统方案的八分之一,查询速度提升约40%,假阳性率可控。研究为优化企业网络管理提供了新思路,并提出结合机器学习、改进哈希函数及分布式协同等未来优化方向。
91 0
|
6月前
|
存储 监控 算法
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中,局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而,出于网络安全管理、资源合理分配以及合规性要求等多方面的考量,对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控,涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法,深入探讨其在局域网计算机监控场景中的应用,并通过详尽的代码示例进行阐释。
119 4
|
7月前
|
存储 算法 安全
企业员工数据泄露防范策略:基于 C++ 语言的布隆过滤器算法剖析[如何防止员工泄密]
企业运营过程中,防范员工泄密是信息安全领域的核心议题。员工泄密可能致使企业核心数据、商业机密等关键资产的流失,进而给企业造成严重损失。为应对这一挑战,借助恰当的数据结构与算法成为强化信息防护的有效路径。本文专注于 C++ 语言中的布隆过滤器算法,深入探究其在防范员工泄密场景中的应用。
115 8
|
8月前
|
存储 监控 算法
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
114 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨