博弈论
博弈论 ,是经济学的一个分支,主要研究具有竞争或对抗性质的对象,在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为,并研究它们的优化策略。
通俗地讲,博弈论主要研究的是:在一个游戏中,进行游戏的多位玩家的策略。
公平组合游戏¶
公平组合游戏的定义如下:
-
游戏有两个人参与,二者轮流做出决策,双方均知道游戏的完整信息;
-
任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关,而与游戏者无关;
-
游戏中的同一个状态不可能多次抵达,游戏以玩家无法行动为结束,且游戏一定会在有限步后以非平局结束。
大部分的棋类游戏都 不是 公平组合游戏,如国际象棋、中国象棋、围棋、五子棋等(因为双方都不能使用对方的棋子)。
Nim 游戏¶
取走最后一个物品的人获胜。
例如,如果现在有
如果现在的局面为
博弈图和状态¶
如果将每个状态视为一个节点,再从每个状态向它的后继状态连边,我们就可以得到一个博弈状态图。
例如,如果节点
定义 必胜状态 为 先手必胜的状态 , 必败状态 为 先手必败的状态 。
通过推理,我们可以得出下面三条定理:
- 定理 1:没有后继状态的状态是必败状态。
- 定理 2:一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
- 定理 3:一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。
对于定理 1,如果游戏进行不下去了,那么这个玩家就输掉了游戏。
对于定理 2,如果该状态至少有一个后继状态为必败状态,那么玩家可以通过操作到该必败状态;此时对手的状态为必败状态——对手必定是失败的,而相反地,自己就获得了胜利。
对于定理 3,如果不存在一个后继状态为必败状态,那么无论如何,玩家只能操作到必胜状态;此时对手的状态为必胜状态——对手必定是胜利的,自己就输掉了游戏。
如果博弈图是一个有向无环图,则通过这三个定理,我们可以在绘出博弈图的情况下用
Nim 和¶
让我们再次回顾 Nim 游戏。
通过绘画博弈图,我们可以在
但是,这样的时间复杂度实在太高。有没有什么巧妙而快速的方法呢?
定义 Nim 和
当且仅当 Nim 和为
证明¶
为什么异或值会和状态的胜负有关?下面给出了这个定理的证明过程。
为了证明该定理,只需要证明下面三个定理:
- 定理 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,没有后继状态的状态只有一个,即全
对于定理 2,不妨假设
根据异或定义,一定有奇数个
对于定理 3,如果我们要将
有向图游戏与 SG 函数¶
有向图游戏是一个经典的博弈游戏——实际上,大部分的公平组合游戏都可以转换为有向图游戏。
在一个有向无环图中,只有一个起点,上面有一个棋子,两个玩家轮流沿着有向边推动棋子,不能走的玩家判负。
定义
例如
对于状态
而对于由
这一定理被称作 SG 定理。
将 Nim 游戏转换为有向图游戏¶
我们可以将一个有
那么,由
根据上面的推论,可以得出
参考文献¶
(转载)Nim 游戏博弈(收集完全版)- exponent - 博客园
[组合游戏与博弈论]【学习笔记】- Candy? - 博客园
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:cutekibry, zj713300
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用