专栏文章

基础博弈论学习笔记

FFuyuki
算法·理论参与者 58已保存评论 76

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
76 条
当前快照
1 份
快照标识符
@mhz5sz9p
此快照首次捕获于
2025/11/15 01:56
4 个月前
此快照最后确认于
2025/11/29 05:24
3 个月前
查看原文
这里记录了一些最基本的博弈论问题以及解决方式
定义组合游戏的意义如下：
11、两个玩家L,R进行博弈。
22、每一回合，双方可选的合法操作有限。
33、对于任意一组合法局面，当前决策与之前的操作无关。
44、最后总能到达一种状态使得至少有一方的可操作性集合为0，这时游戏结束。
在这基础上加上一些别的条件，就组成了不同种类的组合游戏。
其中主要分为回合制与非回合制两种。
可以证明，回合制组合游戏总是存在最优纯策略：即每一步都有一种确定最优的决策方式。
而非回合制组合游戏不一定存在纯策略，但一定存在最优的混合策略，即以一定的概率随机的选择一种决策。
一般来讲，纯策略是混合策略的特殊情况。因为混合策略涉及到概率，所以通常与纯策略的博弈问题有着不同的处理方式。

回合制有向图游戏

在组合游戏的基础上，增加条件：
11、双方交替进行操作，每次操作与当前的玩家无关。
22、最先无法进行合法操作的一方判负。
所以有向图游戏是存在纯策略的博弈问题，因此可以使用对抗搜索解决，或者使用SG函数解决。

SG函数

对于游戏的每个子游戏，存在一种衡量局面优劣的函数SG函数，整个游戏的SG函数就是各个子游戏的异或和。
每个局面的SG函数为当前局面的后继状态的SG函数集合中最小的没有出现的非负整数，可以发现对于某一状态而言：
11、如果没有后继状态，SG函数为0，表示必败。
22、如果后继状态中存在必败状态，那么SG函数为正，表示必胜。
33、如果后继状态全是必胜，那么SG函数为0，表示必败。
这和对抗搜索的想法完全一致，只不过SG函数提供了量化的方法，因此允许快速合并多个子局面。

e.g. P2197 Nim游戏

n堆石子，每人每次选择一堆至少取走一颗，问先手是否有必胜策略。
Nim游戏的各个子游戏的SG函数值就是石子个数(想一想，为什么)，然后异或起来看是不是0就行了。

为什么是异或？

看这个，有各种解释，群论、线性基、还有我的瞎搞

非回合制零和博弈

在组合游戏的基础上，增加条件：
11、每一步操作会对某一方带来收益，同时让另一方支付代价。任意时刻，双方的收益和为0。
在这里如果双方交替操作的话，就一定存在纯策略，那就可以用对抗搜索解决。但是如果是同时操作，就一般不存在纯策略作为最优决策，问题就变成了混合决策问题。
所谓混合决策，就是一方的最优策略是以不同概率使用不同的决策。
对于每种局面，首先画出对应的收益矩阵E=[eij]n×mE=[e_{ij}]_{n\times{m}}，在这里假设玩家1（叫做L）有n种不同的决策，玩家2（叫做R）有m种不同的决策，eije_{ij}就表示当L选择i决策，R选择j决策时L的收益，这个矩阵就叫L的收益矩阵，R的收益矩阵就是E[−eji]m×nE[-e_{ji}]_{m\times{n}}。
设玩家L选取各个决策的概率为{l1,l2,l3,...,ln}\begin{Bmatrix}l_1,l_2,l_3,...,l_n\end{Bmatrix}。
玩家R选取各个决策的概率为{r1,r2,r3,...,rn}\begin{Bmatrix}r_1,r_2,r_3,...,r_n\end{Bmatrix}。
双方的目标都是最大化己方的收益，最大化对方的支出。
感觉上，一方的最优策略应该满足：无论对方怎么选择决策，己方的收益都不会小于某个值，而对方的收益都不会大于某个值。
当一方采用最优策略时，另一方无论怎么调整都不会是收益更大。
这个概念叫做纳什平衡，有兴趣的话可以去查一下百科。
双方都采用最优策略时的收益叫做收益矩阵的值，双方的决策方式叫做平衡点。

求解收益矩阵

由上述可知，一方的任意策略满足在任意情况下收益都不会低于某个值，而最优策略使得这一值最大化。
设该值为V(V>0)V(V>0)。
问题就变成了：
∑i=1nli=1\sum_{i=1}^n l_i=1
∑i=1nlieij≥V\sum_{i=1}^nl_i e_{ij}\geq V
求此时VV的最大取值。
第一个式子就是各个决策的概率和为1，第二个式子表示在极端情况下（R碰巧采用了针对己方混合策略的最优纯策略）也能保证收益，因为在R使用各个纯策略的情况下都能最大化最小收益，所以j是要从1枚举到m的。
设Li=liVL_i=\frac{l_i}{V}，问题就变成了：
∑i=1nLieij≥1\sum_{i=1}^nL_i e_{ij}\geq 1
求{∑i=1nLi}min\text{求}\begin{Bmatrix}\sum_{i=1}^n L_i\end{Bmatrix}_{min}
或者变个形式：
∑i=1n−Lieij≤1\sum_{i=1}^n-L_i e_{ij}\leq 1
求{∑i=1n−Li}max\text{求}\begin{Bmatrix}\sum_{i=1}^n -L_i\end{Bmatrix}_{max}
这就是一个标标准准的线性规划问题了。
对于非零和博弈的话，就不存在纳什平衡，因为纳什平衡只适用于非合作性博弈问题当中，自然不能用收益矩阵求解。
反过来说，只要是非合作性博弈问题就可以使用这种方法，而不仅仅限于零和博弈问题了。

e.g. P4232 无意识之外的捉迷藏

两个人在一个nn个点的DAGDAG上走，两人走到同一节点时游戏结束，或者游戏到了TT时刻没有结束，游戏视作在T+1T+1时刻结束。每一时刻双方同时走一步，可以走到用有向边相连的相邻节点处。
设游戏结束时刻为t0t_0，一方收益为t0t_0，另一方收益为−t0-t_0。
双方都采用最优策略时，求游戏的期望结束时间。n,T≤20n,T\leq 20
这个是求收益矩阵的模板了，状态f[i,j,k]f[i,j,k]表示一个人在ii点，一个人在jj点，时刻为k的期望还有多久结束，每一个状态的后继状态就是遍历两点的所有出边，然后构造并求解收益矩阵即可。

不平等回合制博弈

不平等博弈就是在组合游戏上追加：
11、双方交替进行操作，最先不能操作的一方判负。
22、双方的决策不一定完全相同。
在处理不平等博弈的时候，除了利用其纯策略的性质而使用万能的对抗搜索之外，还有一种有力工具就是Surreal NumberSurreal\ Number(超现实数)。

Surreal NumberSurreal\ Number

（下面内容大部分来自 方展鹏《浅谈如何解决不平等博弈问题》，这里只是一个简单的概述，即根据自己的理解组成的不完整但是够用的内容）
11、一个超现实数由两个集合组成{L∣R}\begin{Bmatrix}L|R\end{Bmatrix}，每个集合要么为空，要么是由若干个超现实数组成的集合。
22、对于x={XL∣XR}x=\begin{Bmatrix}X_L|X_R\end{Bmatrix}，y={YL∣YR}y=\begin{Bmatrix}Y_L|Y_R\end{Bmatrix}，当且仅当不存在xi∈XLx_i\in{X_L}使得y≤xiy\leq x_i并且不存在yi∈YRy_i\in{Y_R}使得yi≤xy_i\leq x。
这些定义都是递归给出的，值得注意的是这里的≤\leq不是指小于等于，而是类似于集合中的偏序概念。不过之后会说到，超现实数集合是一个全序集，所以理解成小于等于也未尝不可。
然后通过下面的达利函数，我们可以构建出有理数与超现实数的对应关系：
δ(x)={{∣},x=0{δ(x−1)∣},x>0,x∈Z{∣δ(x+1)},x<0,x∈Z{δ(j−12k)∣δ(j+12k)},x=j2k,j,k∈Z,k>0\delta(x)=\begin{cases}\begin{Bmatrix}|\end{Bmatrix},x=0\\\begin{Bmatrix}\delta(x-1)|\end{Bmatrix},x>0,x\in Z\\\begin{Bmatrix}|\delta(x+1)\end{Bmatrix},x<0,x\in Z\\\begin{Bmatrix}\delta(\frac{j-1}{2^k})|\delta(\frac{j+1}{2^k})\end{Bmatrix},x=\frac{j}{2^k},j,k\in{Z},k>0\\\end{cases}
解释一下这个第四条，就是左右两个数加在一起取个平均数。

基本定理

11、对于x={L∣R}x=\begin{Bmatrix}L|R\end{Bmatrix},有Lmax≤x≤RminL_{max}\leq x\leq R_{min}，x={Lmax∣Rmin}x=\begin{Bmatrix}L_{max}|R_{min}\end{Bmatrix}
22、对于x={XL∣XR},y={YL∣YR}x=\begin{Bmatrix}X_L|X_R\end{Bmatrix},y=\begin{Bmatrix}Y_L|Y_R\end{Bmatrix}:
x+y={XL∣XR}+{YL∣YR}={XL+y,x+YL∣XR+y,x+YR}\qquad x+y=\begin{Bmatrix}X_L|X_R\end{Bmatrix}+\begin{Bmatrix}Y_L|Y_R\end{Bmatrix}=\begin{Bmatrix}X_L+y,x+Y_L|X_R+y,x+Y_R\end{Bmatrix}
33、对于x={XL∣XR}x=\begin{Bmatrix}X_L|X_R\end{Bmatrix},有−x={−XR∣−XL}-x=\begin{Bmatrix}-X_R|-X_L\end{Bmatrix}

与不平等博弈的关系

如果游戏GG等价于x={L∣R}x=\begin{Bmatrix}L|R\end{Bmatrix}，其中两个集合表示两个玩家的决策所产生的的后继状态集合：
x>0 Lx>0 \ L必胜，x<0 Rx<0 \ R必胜，x=0x=0后手必胜。
x>0x>0时：LL先手时总能将xx转移到一个大于等于0的状态，RR先手只能将其转移到大于0的状态。轮到LL时恒有x>0x>0，左集合始终不为空，LL必胜。
x<0x<0时同理。
x=0x=0时，LL先手会将局面变成x<0x<0，RR先手会将局面变成x>0x>0，然后同上。
将一个游戏的多个子游戏合并就是将其对应的Surreal NumberSurreal\ Number对应的值相加。

e.g.Procrastination

nn个有黑白正方体堆成的柱子，先手只能拿白色，后手只能拿黑色。每人每次选择一个柱子拿走一个对应颜色的正方体，然后将该正方体上面的所有正方体（包括这个）全部拿走。一方不能操作时判负，判断先手是否存在必胜策略。
n,hi≤50n,h_i\leq 50，hih_i表示第ii个柱子的高度。
根据定义O(n)O(n)递推然后相加即可，就是从下向上维护双方决策的最值，或者按照论文中的做法推式子。

评论

共 76 条评论，欢迎与作者交流。

正在加载评论...