首页 > 其他分享 >博弈论学习笔记(2024.8.17)

博弈论学习笔记(2024.8.17)

时间:2024-09-20 19:03:17浏览次数:8  
标签:10 石子 博弈 17 2024.8 博弈论 leq Game 获胜

基本概念

博弈定义:在一定条件下,遵守一定的规则,一个或几个拥有绝对理性思维的人或团队,从各自允许选择的行为或策略进行选择并加以实施,并从中各自取得相应结果或收益的过程。

举几个例子来说说什么是博弈:

  • 经济学:股市是按照这样的方式运行的:每个人可以持有股票,如果抛出过多股票则股价下跌,没有抛股票的人血亏。因此当金融危机发生时,如果有某些消息让一部分股民抛售了股票,剩下的人也必须跟着抛售,抛售越晚越亏。

  • 买卖交易:一般买东西的时候,由商家先给出一个价格,随后顾客将这个价格压低,随后商家再
    将这个压低的价格抬高,重复过程。顾客会希望最小化最终价格,而商家会希望最大化。

  • 小学数学:桌子上有 20 个硬币。Alice 和 Bob 两个人依次取硬币,每次可以取一枚或两枚,Alice 先开始取。取到最后一枚硬币的人获胜。问谁会获胜。


一些定义:

  • Game theory:传统意义上的博弈论,涉及经济学,逻辑学,计算机科学等。

  • Combinatorial game theory:Game theory 的一部分,主打的是 “sequential gameswith perfect information”。“sequential” 指的是双方交替行动, 而非同时行动,“perfect information” 指的是双方在做决策的时候都知道当前局面处于什么状态,以
    及可以向什么状态转移。

  • Complete information game theory:指的是博弈双方都清楚双方的目标(或者采取某些操作对双方的收益)。当然 OI 范围内的一般都是完全信息博弈。

  • impartial game:在博弈的同一状态下,如果不论是谁做操作,可能做出的决策集合是相同的, 那么就是一个平等博弈。平等博弈意味着我们不用区分一个状态下是 “Alice 做操作” 还是 “Bob 做操作”,因此只要博弈可以终止,递归可证一个局面要么是 “先手必胜” 的,要么是 “后手必胜”的。

象棋/围棋:perfect & complete。

扑克牌:imperfect & complete。你在打牌的时候是不知道对手的手牌的,也即不知道现在是处于博弈的哪个状态的。

狼人杀/三国杀:imperfect & incomplete,此时不仅你不知道对手有哪些可能的决策,甚至不知道对手的身份,也就对应不知道对手的获胜目标。

这三者都不是平等博弈。


OI 比赛中常见的博弈有如下的几种类型:

  • 传统组合数学意义上的经典模型,如 Nim 博弈,Nash 博弈等。

  • 没什么经典模型,但是比较考验选手对整个博弈的细致分析的,比如仔细考虑博弈双方的最优策略等。

  • 完全是套了一个博弈的壳,其实是在考察其它内容,比如组合数学/图论等。

经典模型

有向图博弈(Game on DAG)

有一张有向无环图,其中一个节点上有一个棋子。从 Alice 开始游戏,Alice 和 Bob 轮流将这个棋子沿着一条有向出边移动,无法移动者判负。问最后谁会获胜。

解:注意到这是一个平等博弈,那么我们可以从无法移动的点回推,就可以判断到这个点时是先手必胜还是后手必胜。

Ferguson Game

有两堆石子分别 \(n, m\) 个。双人博弈,每次操作是清空其中一堆石子并将另一堆石子分成非空的两堆新的石子。 无法操作者输。问最后谁会获胜。

解:平等博弈。我们将先手必胜状态设为 \(N\),先手必败状态设为 \(P\) (下同),先打表找规律:

m\n 1 2 3 4
1 P N P N
2 N N N N
3 P N P N
4 N N N N

猜想:两堆石子均为奇数则先手必败,否则先手必胜。

证:考虑数学归纳法。

对于 \(m = 1\) 且 \(n = 1\) 的情况,先手必败(\(P\)),猜想成立。

当 \(\max(n, m) = 2\) 时,根据打表结果,对于 \(n = 2, m = 1\)、\(n = 1, m = 2\) 和 \(n = 2, m = 2\) 的情况,先手必胜(\(N\)),猜想成立。

假设猜想对于 \(\max(n, m) < k\) 时成立,现在证明对于 \(\max(n, m) = k\) 时猜想也成立。

若 \(n, m\) 中有一偶数,假设是 \(n\),则先手可以将另外那堆石子清空,将 \(n\) 划分成两个奇数 \(a, b\),发现 \(a, b < n \leq k\),且此时先后手交换,根据假设,此时是先手必败状态(\(P\)),也就是操作前的先手必胜状态(\(N\))

若 \(n, m\) 都是奇数,则先手将一堆石子清空,将 \(n\) 划分成一个奇数 \(a\) 和一个偶数 \(b\),发现 \(a, b < n \leq k\),且此时先后手交换,根据假设,此时是先手必胜状态(\(N\)),也就是操作前的先手必败状态(\(P\))

符合数学归纳法,猜想成立。

Chomp Game

有一块 \(n \times m\) 的网格。双人博弈,每次操作是选中其中一个未被删除的格子 \((x_0, y_0)\),将所有 \(x \geq x_0\) 且 \(y \geq y_0\) 的格子 \((x, y)\) 删除。删除 \((1, 1)\) 的人输。问最后谁会获胜。

解:平等博弈。先打表找规律。

m\n 1 2 3 4
1 P N N N
2 N N N N
3 N N N N
4 N N N N

猜想:只要 \(n \neq 1\) 或 \(m \neq 1\),那么这个游戏一定先手获胜。

证:考虑反证法。

假设先手必败,无论先手怎么取,后手都能获胜。假设先手取 \((n, m)\),后手会通过某种取法进入必胜状态,考虑到任何一种取法都会取到 \((n, m)\),那么先手可以先采用后手的必胜策略进入必胜状态,这与一开始的假设错误,因此假设不成立。

\(\therefore\) 猜想成立。

Bash Game

有一堆石子共 \(n\) 个。双人博弈,每次从石子堆中取出 \(1\) 到 \(m\) 个石子。无法操作者输。问最后谁会获胜。

解:平等博弈。先打表找规律。

m\n 1 2 3 4 5
1 N P N P N
2
3
4
5

SG函数与SG定理

例题

Nim Game

洛谷 P2197 【模板】Nim 游戏

完整代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 9;
int a[N], T, n;
signed main(){
	scanf("%lld", &T);
	while(T--){
		scanf("%lld", &n);
		for(int i = 1; i <= n; i++)
			scanf("%lld", &a[i]);
		int ans = a[1];
		for(int i = 2; i <= n; i++)
			ans ^= a[i];
		if(!ans)
			printf("No\n");
		else
			printf("Yes\n");
	}
	return 0;
} 

Lasker's Nim Game

现在有 \(n\) 堆石子,第 \(i\) 堆有 \(a_i\) 个。双人博弈,每次从一个当前非空的石子堆当中取至少一个,或者选取一个石子堆分成两个非空的石子堆。无法操作者输。问最后谁会获胜。

\(n \leq 10^5, a_i \leq 10^9\)

Anti-Nim Game

Nim 游戏,但是变为不能取石子的人获胜。

\(n \leq 10^5, a_i \leq 10^9\)

Nimk Game

现在有 \(n\) 堆石子,第 \(i\) 堆有 \(a_i\) 个。双人博弈,每次从至多 \(k\) 个当前非空的石子堆当中取至少一个。无法操作者输。问最后谁会获胜。

\(n, k \leq 10^5, a_i \leq 10^9\)

Crosses and Crosses Game

有一个 \(1 \times n\) 的纸条,初始全部为空。双人博弈,每次选取一个空白的位置涂黑。第一个满足 “操作后有连续三个位置被涂黑” 的人获胜。问最后谁会获胜。

\(n \leq 5000\)

K倍动态减法游戏

HDUOJ A simple stone game

各种棋盘游戏(Chess Game)

有一个 \(m \times m\) 的棋盘和 \(n\) 个棋子,初始位置给定。双人博弈,每次选取一个在 \((x, y)\)的棋子移动到 \((x − k, y)\) 或 \((x, y − k)\) 或 \((x − k, y − k)\)。第一个将其中一个棋子放置到 \((0, 0)\) 的人获胜。问最后谁会获胜。

\(m \leq 100\)

POJ A Chess Game

各种翻转游戏(Ruler Game)

有 \(n\) 个硬币排成一排,其中 \(m\) 个初始向上,其余向下。双人博弈,每次选取一个区间,并将区间内的硬币全部翻面,要求区间右端点的硬是从向上翻到向下。无法操作者输,问最后谁会获胜。

\(n \leq 10^9, m \leq 10^5\)

HDUOJ 朋友

洛谷 P3179 [HAOI2015] 数组游戏

各种数字游戏(Number Game)

POJ A multiplication game

解:平等博弈,

初始有两个数 \(a, b\)。双人博弈,每次操作依次进行:

  • 如果 \(a > b\),则交换 \(a, b\);

  • 如果 \(a = 0\),则当前玩家失败,游戏结束;

  • 玩家选择:将 \(b\) 变为 \(b \bmod a\),或者选定一个 \(k \geq 1\) 并将 \(b\) 减去 \(a^k\)。

问最后谁会获胜。

\(a, b \leq 10^{18}\)

各种树上游戏(Tree Game)

洛谷 [AGC010F] Tree Game

完整代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e3 + 9;
struct Edge{
	int v, nex;
} e[N << 1];
int head[N], ecnt;
void addEdge(int u, int v){
	e[++ecnt] = Edge{v, head[u]};
	head[u] = ecnt;
}
int a[N], n;
bool dfs(int u, int fa){
	for(int i = head[u]; i; i = e[i].nex){
		int v = e[i].v;
		if(v == fa)
			continue;
		if(a[u] > a[v] && !dfs(v, u))
			return true;
	}
	return false;
}
signed main(){
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	for(int i = 1; i < n; i++){
		int u, v;
		scanf("%lld%lld", &u, &v);
		addEdge(u, v);
		addEdge(v, u);
	}
	for(int i = 1; i <= n; i++)
		if(dfs(i, 0))
			printf("%lld ", i);
	return 0;
} 

洛谷 [AGC014D] Black and White Tree

HDUOJ Gameia

Green Hackenbush Game

现在有一棵有根树。双人博弈,每次可切断一条边,保留包含根的部分。无法操作者输。问最后谁会获胜。

\(n \leq 10^5\)

标签:10,石子,博弈,17,2024.8,博弈论,leq,Game,获胜
From: https://www.cnblogs.com/JPGOJCZX/p/18423087

相关文章

  • 1,Python数分之Pandas训练,力扣,1783. 大满贯数量
    学习:知识的初次邂逅复习:知识的温故知新练习:知识的实践应用目录 一,原题力扣链接二,题干三,建表语句四,分析四,Pandas解答:五,验证六,总结 一,原题力扣链接.-力扣(LeetCode)二,题干表:Players+----------------+---------+|ColumnName|Type|+--------......
  • 2024.8.30校测
    T1题目描述物理老师YJ有一个长杆天平,天平的两臂长均为\(15\),将长杆看作\(x\)轴,则平衡点在\(0\)位置处,负数位置在左臂上,正数位置在右臂上。长杆上有\(n\)个位置有挂钩可以挂秤砣。YJ有\(m\)个秤砣,质量分别为\(g_i\),每个挂钩可以不挂也可以挂任意个秤砣。YJ想要知道......
  • 分块/莫队学习笔记(一)(2024.8.23)
    分块基本概念分块的基本思想是,通过对原数据的适当划分,并在划分后的每一个块上预处理部分信息,从而较一般的暴力算法取得更优的时间复杂度。分块的时间复杂度主要取决于分块的块长,一般可以通过均值不等式求出某个问题下的最优块长,以及相应的时间复杂度。LOJ小分块#6277.数列分......
  • 2024.8.31校测
    T1题目描述今天的酒席有\(n\)个人,他们要同时举杯,成对碰杯。碰杯的时候,不能有人不参与碰杯,也不希望有手臂交叉这种别扭的情况出现。如下图,左图的情况是好的,右图的情况是不希望出现的。每个人都有一个喜爱的酒种类,每个人想要与和自己喝一样酒的人碰杯,请你设计一个方法,在保证每......
  • 图论进阶学习笔记(三)(2024.8.12)
    二分图定义如果你能把一个图划分成两个集合,集合内部的点没有边相连接,那么这个图就是一个二分图,如图就是一个二分图:交错路:从一个没有被匹配的点出发,依次走非匹配边,匹配边,非匹配边……最后到达另外一部点当中某个没有被匹配的点的路径。增广路:从一个没有被匹配的点出发,依次走......
  • 图论进阶学习笔记(二)(2024.8.1)
    图的连通性强连通分量割点缩点例题一边双连通分量点双连通分量2-SAT例题二例题三欧拉回路例题四......
  • 线段树进阶应用学习笔记(一)(2024.7.19)(2024.8.22)
    线段树优化建图算法流程复杂度分析例题一#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=5e5,M=5e6+9;structEdge{ intv,w,nex;}e[M];inthead[M],ecnt;voidAddEdge(intu,intv,intw){ e[++ecnt]=Edge{v,w,hea......
  • ESXi 8.0 中已弃用且不受支持的设备 (88172)
    ESXi8.0中已弃用且不受支持的设备(88172)请访问原文链接:ESXi8.0中已弃用且不受支持的设备(88172),查看最新版。原创作品,转载请保留出处。作者主页:sysin.org该文为官方KB的翻译和整理,方便查询ESXi8.0中不再支持的硬件设备。描述由于设备供应商已将设备停产,因此ESX......
  • 代码随想录算法训练营第十六天 | Javascript | 力扣Leetcode | 回溯 | 77. 组合、216.
    目录前言简介题目链接:77.组合题目链接:216.组合总和3题目链接:17.电话号码的字母组合前言踏平坎坷成大道,斗罢艰险又出发!自律的尽头是自控,自控的尽头是硬控。愿道友们披荆斩棘,终能得偿所愿。简介本人是小几年经验的前端开发,算法基础只有力扣几十道题,非常薄......
  • 设计原理图:417-基于XCVU9P+ C6678的8T8R的无线MIMO平台
    基于XCVU9P+C6678的8T8R的无线MIMO平台  一、板卡概述     北京太速科技板卡基于TI TMS320C6678DSP和XCVU9P高性能FPGA,FPGA接入4片AD9361无线射频,构建8输入8输出的无线MIMO平台,丰富的FPGA资源和8核DSP为算法验证和信号处理提供强大能力。  ......