WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数学部分简介
符号
复数
位运算
快速幂
进位制
高精度计算
平衡三进制
素数
最大公约数
欧拉函数
筛法
欧拉定理 & 费马小定理
类欧几里德算法
裴蜀定理
乘法逆元
线性同余方程
中国剩余定理
二次剩余
BSGS
原根
卢卡斯定理
莫比乌斯反演
杜教筛
Min_25 筛
分解质因数
多项式部分简介
拉格朗日插值
快速傅里叶变换
快速数论变换
快速沃尔什变换
多项式求逆
多项式开方
多项式除法|取模
多项式对数函数|指数函数
多项式牛顿迭代
多项式多点求值|快速插值
多项式三角函数
多项式反三角函数
常系数齐次线性递推
生成函数简介
普通生成函数
指数生成函数
向量
矩阵
高斯消元
线性基
线性规划简介
单纯形算法
排列组合
卡特兰数
斯特林数
贝尔数
伯努利数
康托展开
容斥原理
抽屉原理
概率初步
置换群
斐波那契数列
博弈论
牛顿迭代法
数值积分
分段打表
64 objects
本站非官方,所收集资源均来源于网络。
博弈论 - 数学
author: cutekibry, zj713300 **博弈论** ,是经济学的一个分支,主要研究具有竞争或对抗性质的对象,在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为,并研究它们的优化策略。 通俗地讲,博弈论主要研究的是:在一个游戏中,进行游戏的多位玩家的策略。 ## 公平组合游戏 公平组合游戏的定义如下: - 游戏有两个人参与,二者轮流做出决策,双方均知道游戏的完整信息; - 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关,而与游戏者无关; - 游戏中的同一个状态不可能多次抵达,游戏以玩家无法行动为结束,且游戏一定会在有限步后以非平局结束。 大部分的棋类游戏都 **不是** 公平组合游戏,如国际象棋、中国象棋、围棋、五子棋等(因为双方都不能使用对方的棋子)。 ## Nim 游戏 $n$ 堆物品,每堆有 $a_i$ 个,两个玩家轮流取走任意一堆的任意个物品,但不能不取。 取走最后一个物品的人获胜。 例如,如果现在有 $n=3$ 堆物品,而每堆分别有 $2, 5, 4$ 个,那么可以取走第 $1$ 堆中的 $2$ 个物品,局面就变成了 $0, 5, 4$ ;或者也可以取走第 $2$ 堆的 $4$ 个物品,局面就变成了 $2, 1, 4$ 。 如果现在的局面为 $0, 0, 5$ ,甲取走了第 $3$ 堆的 $5$ 个物品,也就是取走了最后一个物品,此时甲获胜。 ## 博弈图和状态 如果将每个状态视为一个节点,再从每个状态向它的后继状态连边,我们就可以得到一个博弈状态图。 例如,如果节点 $(i, j, k)$ 表示局面为 $i, j, k$ 时的状态,则我们可以画出下面的博弈图(由于篇幅有限,故仅显示部分状态节点和部分边): ![博弈图的例子](../images/game1.png) 定义 **必胜状态** 为 **先手必胜的状态** , **必败状态** 为 **先手必败的状态** 。 通过推理,我们可以得出下面三条定理: - 定理 1:没有后继状态的状态是必败状态。 - 定理 2:一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。 - 定理 3:一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。 对于定理 1,如果游戏进行不下去了,那么这个玩家就输掉了游戏。 对于定理 2,如果该状态至少有一个后继状态为必败状态,那么玩家可以通过操作到该必败状态;此时对手的状态为必败状态——对手必定是失败的,而相反地,自己就获得了胜利。 对于定理 3,如果不存在一个后继状态为必败状态,那么无论如何,玩家只能操作到必胜状态;此时对手的状态为必胜状态——对手必定是胜利的,自己就输掉了游戏。 如果博弈图是一个有向无环图,则通过这三个定理,我们可以在绘出博弈图的情况下用 $O(N+M)$ 的时间(其中 $N$ 为状态种数, $M$ 为边数)得出每个状态是必胜状态还是必败状态。 ## Nim 和 让我们再次回顾 Nim 游戏。 通过绘画博弈图,我们可以在 $O(\prod_{i=1}^n a_i)$ 的时间里求出该局面是否先手必赢。 但是,这样的时间复杂度实在太高。有没有什么巧妙而快速的方法呢? 定义 Nim 和 $=a_1 \oplus a_2 \oplus \ldots \oplus a_n$ 。 当且仅当 Nim 和为 $0$ 时,该状态为必败状态;否则该状态为必胜状态。 ### 证明 为什么异或值会和状态的胜负有关?下面给出了这个定理的证明过程。 为了证明该定理,只需要证明下面三个定理: - 定理 1:没有后继状态的状态是必败状态。 - 定理 2:对于 $a_1 \oplus a_2 \oplus \ldots \oplus a_n \neq 0$ 的局面,一定存在某种移动使得 $a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0$ 。 - 定理 3:对于 $a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0$ 的局面,一定不存在某种移动使得 $a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0$ 。 对于定理 1,没有后继状态的状态只有一个,即全 $0$ 局面。此时 $a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0$ 。 对于定理 2,不妨假设 $a_1 \oplus a_2 \oplus \ldots a_n = k \neq 0$ 。如果我们要将 $a_i$ 改为 $a_i'$ ,则 $a_i'=a_i \oplus k$ 。 根据异或定义,一定有奇数个 $a_i$ 在 $k$ 在二进制下的最高位为 $1$ 。满足这个条件的 $a_i$ 一定也满足 $a_i > a_i \oplus k$ ,因而这也是个合法的移动。 对于定理 3,如果我们要将 $a_i$ 改为 $a_i'$ ,则根据异或运算律可以得出 $a_i=a_i'$ ,因而这不是个合法的移动。 ## 有向图游戏与 SG 函数 有向图游戏是一个经典的博弈游戏——实际上,大部分的公平组合游戏都可以转换为有向图游戏。 在一个有向无环图中,只有一个起点,上面有一个棋子,两个玩家轮流沿着有向边推动棋子,不能走的玩家判负。 定义 $\operatorname{mex}$ 函数的值为不属于集合 $S$ 中的最小非负整数,即: $$ \operatorname{mex}(S)=\min\\{x\\} \quad (x \notin S, x \in N) $$ 例如 $\operatorname{mex}(\\{0, 2, 4\\})=1$ , $\operatorname{mex}(\\{1, 2\\})=0$ 。 对于状态 $x$ 和它的所有 $k$ 个后继状态 $y_1, y_2, \ldots, y_k$ ,定义 $\operatorname{SG}$ 函数: $$ \operatorname{SG}(x)=\operatorname{mex}\\{\operatorname{SG}(y_1), \operatorname{SG}(y_2), \ldots, \operatorname{SG}(y_k)\\} $$ 而对于由 $n$ 个有向图游戏组成的组合游戏,设它们的起点分别为 $s_1, s_2, \ldots, s_n$ ,则有定理: **当且仅当 $\operatorname{SG}(s_1) \oplus \operatorname{SG}(s_2) \oplus \ldots \oplus \operatorname{SG}(s_n) \neq 0$ 时,这个游戏是先手必胜的。** 这一定理被称作 SG 定理。 ## 将 Nim 游戏转换为有向图游戏 我们可以将一个有 $x$ 个物品的堆视为节点 $x$ ,则当且仅当 $y