该笔记还未完成整理,待日后继续整理……
博弈论
博弈论简介
在OI中,博弈论一般就是两位玩家玩游戏,游戏有一定规则,双方均在这规则之下进行回合制游戏,并且最终一定会分出胜负。
同时这两位玩家都是超高校级的游戏玩家x,一定会按照当前最优策略进行游戏(就是想方设法让自己赢)。
而你任务则为试着分析出这两位最终的输赢情况。
公平组合游戏
OI中所玩的博弈论游戏,几乎都是“公平组合游戏”(Impartial Combinatorial Games, ICG)。
也就是说:几乎所有博弈论问题都可以建模为基本的ICG来分析处理。
满足以下条件的游戏是ICG:
- 竞争性:只有两名玩家,且两名玩家交替行动。
- 公平性:在游戏进程的任意游戏状态,可以执行的行动只取决于当前局面,而与轮到哪名玩家、以前的任何操作等其他因素无关。
象棋等常见棋类不属于ICG则正是因为这个原因。
因为每个人只能移动自己势力的棋子,而不是所有棋子。
使得自己不能移动对方的棋子而执行某一行动,从而使能执行的行动取决于轮到哪名玩家。 - 不可回溯性:游戏中的同一个游戏状态不可能再次抵达。
也就是说,ICG为线性游戏,不可能回到之前经历过的某一游戏状态。 - 有穷性:游戏以玩家无法行动为结束,并一定会在有限步后以非平局结束。
必胜必败状态
首先对于公平组合游戏,我们需要了解两个奇妙的状态,他们是:
定义
- 必胜状态:处于该状态的玩家,至少能有一种行动,让接下来的状态变为必败状态留给另一位玩家,使其面临必败。
一般称必胜状态为N-Position,简称为N状态。部分也称为非奇异状态、非平衡状态。 - 必败状态:无论怎么行动,只能使接下来的状态变为必胜状态留给另一位玩家,使其必胜。(或者说不可能走到必败状态,使另一位玩家陷入必败从而扭转局势)
一般称必败状态为P-Position,简称为P状态,部分也称为奇异状态、平衡状态。
以下为了区分必胜必败状态与场上游戏状态(局面),特将“游戏状态”统称为“局面”。
性质
由定义,我们可以找到必胜必败状态的基本性质,或者说判别必胜必败状态的基本方式:
- 必胜状态:可以走到某一个必败状态。
- 必败状态:只能走到必胜状态,或说走不到任何一个必败状态。
性质
对于ICG,存在性质:
性质1:游戏中每一种局面,对处于该局面的玩家来说,只有可能是必胜或必败状态,并且无法逆转局势(也就是不存在不确定状态)。
那么由此可以得到推论:
推论1-1:游戏的开始局面也处于必胜状态或必败状态,因此对于先手玩家来说,其胜负是一开始就被决定好了的。
推论1-2:整个游戏的流程是按照:“A处于必胜状态→B处于必败状态→A处于必胜状态→……→A最终获胜”(或者反之)来进行的。
关于终止局面的误区:
- 终止局面:无法行动/没有子状态的游戏状态。
不一定最终局面是必败状态,只是因为一般都规定:终止局面为必败状态——当某一方无法行动宣布败北。
但也完全可以规定终止局面为必胜状态——当某一方无法行动宣布胜利。
要根据题目游戏规则,确定终止局面是必败状态还是必胜状态。
如果只听了结论感觉有点疑惑,可以点开这个看看x……
其实个人对于这里纠结理解了很久,
主要疑惑就在于:
- 为什么一定只存在必胜或必败状态,而不存在一个中间或不确定状态,此时玩家的行动不会决定结果?
- 这给目为什么一开始就决定好了玩家的胜负,不能靠自己的操作改变命运?
- 为什么会有必败状态,处于此状态的玩家为什么不能一转攻势?
等等等等之类的问题……
其实这种疑问主要来自于我们日常玩的游戏都不是ICG,
并且我们也不是智械文明,很难保证每次都能找到并选择最优策略。
首先,对于最难绕过来的第一个问题,其实可以这样想:
首先如果某状态不是“不确定状态”,又因为游戏最终只有某方胜或败的结果,
那么该状态肯定就是必胜或必败状态,
也就是只可能存在:必胜、必败、不确定三种状态。
这点是可以肯定的吧!……
那么排列组合,对于某一状态,其子状态(之后可以到达的状态)只有7种情况:
- 全是不确定状态
- 全是必胜状态
- 全是必败状态
- 既有不确定状态、也有必胜状态
- 既有不确定状态、也有必败状态
- 既有必胜状态、也有必败状态
- 不确定状态、必胜状态、必败状态都有
根据两玩家都总会选择最优策略的思想,以及必胜必败状态的定义可以知道:
- 对于情况②,则该状态一定为必败状态(玩家在这里怎么行动,都会让对方必胜)
- 对于情况③、⑤、⑥、⑦,则该状态一定是必胜状态(玩家在这里只要走向必败状态,就能让对方陷入必败)
所以只有子状态情况为①和④的状态,才能将该状态称为“不确定状态”。
下面来分析这两种“不确定状态”中玩家的选择:
由于玩家都要确保自己尽量能赢,所以自己的回合,除非万不得已只能选择必胜状态行动,将胜利拱手让给对方(即自己陷入了必败状态),否则自己肯定打死不走必胜状态。
因此对于情况④,处于这种“不确定状态”,当前玩家肯定会选择走“不确定状态”。 对于情况①,没什么说的,只能走“不确定状态”。
这两情况发现什么没?
就:若处于“不确定状态”,玩家只会选择继续走“不确定状态”!
那么场面就会变得奇怪了起来:
明明ICG的定义就说好最终会分出胜负,但却一直处于“不确定状态”。
因此直接異議あり!断言不可能存在“不确定状态”。
可能有人最后这里还有点小疑惑:
如果就让双方就这样一直在“不确定状态”下反复横跳,直到最终有人只能走那个“必胜状态”输掉游戏怎么样?
请牢记:如果只能走必胜状态,那么该状态就是必败状态了。
【感觉有点哲学是吧23333……
那么如果第一个问题明白了,其他问题也就好解决了。
因为不存在不确定状态,命运就像链条一样被决定好了,不然怎么叫必胜和必败呢?
注意:对于必胜状态和必败状态,我们统一是针对于先手来分析的。
由此自然而然我们可以想到一种解决博弈问题的思路:
由题目要求得到终止局面是必胜状态还是必败状态,
再由终止局面反推,得到某一局面是必胜状态还是必败状态。
这种思路也就是搜索解法。
但需要注意的是有可能不能直接分析出终止局面是(先手)必败状态还是必胜状态,
需要先倒推到终止局面的前驱局面,分析这一局面是什么状态,才能得到终止局面是什么状态。
或者不用分析终止局面是什么状态,直接由终止局面的前驱局面来倒推分析。
如下例中的“皇后问题”。
博弈状态图
我们将每一个局面视为一个节点**,再从每个局面向它的后继局面连边,这样就能得到一个博弈状态图。
结合上面提到的倒推解题思路,我们可以从终止局面节点搜索,得到各种局面的状态。
可将处于必败状态的节点成为P节点,必胜状态的节点成为N节点。
引例——挪动皇后游戏
游戏规则:
将一个皇后放在棋盘(任意$n*n$大小)上某一格子内,皇后只能向左、下、正左下(即同时向左和向下走相同格数)走任意格且至少移动1格,最先到达最左下角的玩家胜利。
我们就这个引例来分析其博弈状态图。
先可将局面抽象为皇后在棋盘上的坐标,如$(2,3)$、$(5,5)$。
则对于任意局面$(n,m)$,其后继局面为:
- $(n-k,m) (k∈N^+)$
- $(n,m-k) (k∈N^+)$
- $(n-k,m-k) (k∈N^+)$
我们可以用棋盘本身来代表状态图。
而对于处于坐标$(n,m)$格子上的皇后,其可移动局面即为横向向左,竖向向下、斜向向左下直线的所有格子。
那么对于这个问题来说,其终止局面为$(0,0)$。
而从$(0,0)$反推,其右方、上方、右上方的节点均对于(先手)必胜状态。
则由$(0,0)$局面易得出处于N状态(必胜状态)的局面,如下图绿色区域表示:
接下来根据必胜必败状态的性质,可以发现有且仅有$(1,2)$、$(2,1)$这两点,无论怎么移动都只能到达必胜状态(如蓝箭头所示)。
因此这两点即为P节点。
接下来我们又可以从找到的P节点倒推,得到新的N节点(其右、上、右上的节点,如蓝箭头所示)。
(为了区别将第一次倒推出的N节点颜色加深了。)
最终这么分析下去,会得到如下博弈状态图。
其中蓝色节点为必胜节点,白色部分为必败节点。
图片来自于Matrix67的笔记“捡石子游戏、Wythoff数表和一切的Fibonacci数列”。
可能有同学就会发现,在这里的P节点有点规律的样子,大致好像连成了一条直线。
其实这个发现是正确的,这个游戏也叫做“威佐夫博弈”(Wythoff Game),将在后面的部分具体讲解。
作用
对于任何ICG,其都可以转化为一种“有向图游戏”。
有向图游戏:
给定一个有向无环图,图中有一个唯一的起点(初始局面),在起点上有一枚棋子。
两名玩家需要交替地将该棋子沿着有向边进行移动,每次必须移动一步。
无法移动者(来到终止局面)将被判负(也有可能判赢)。
具体转换方法为:
- 将每一种局面看成有向无环图的节点。
- 对于每一种局面,和能合法到达的下一种局面,将这两节点建立有向边。
这样,我们就能将各种博弈问题转化为统一的一种模型,方便我们思考与解决。