主页
Featured image of post ACM学习笔记——博弈论……

ACM学习笔记——博弈论……

数论——博弈论……

文章字数:3708
预计阅读时长: 分钟

该笔记还未完成整理,待日后继续整理……

博弈论

博弈论简介

在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种情况:

  1. 全是不确定状态
  2. 全是必胜状态
  3. 全是必败状态
  4. 既有不确定状态、也有必胜状态
  5. 既有不确定状态、也有必败状态
  6. 既有必胜状态、也有必败状态
  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状态(必胜状态)的局面,如下图绿色区域表示:

第一次倒推 - N节点
第一次倒推 - N节点

接下来根据必胜必败状态的性质,可以发现有且仅有\((1,2)\)\((2,1)\)这两点,无论怎么移动都只能到达必胜状态(如蓝箭头所示)。
因此这两点即为P节点。

第二次倒推 - P节点
第二次倒推 - P节点

接下来我们又可以从找到的P节点倒推,得到新的N节点(其右、上、右上的节点,如蓝箭头所示)。
(为了区别将第一次倒推出的N节点颜色加深了。)

第三次倒推 - N节点
第三次倒推 - N节点


最终这么分析下去,会得到如下博弈状态图。

挪动皇后游戏 - 推导过程
挪动皇后游戏 - 推导过程

挪动皇后游戏 - 博弈状态图
挪动皇后游戏 - 博弈状态图

其中蓝色节点为必胜节点,白色部分为必败节点。

可能有同学就会发现,在这里的P节点有点规律的样子,大致好像连成了一条直线。
其实这个发现是正确的,这个游戏也叫做“威佐夫博弈”(Wythoff Game),将在后面的部分具体讲解。

作用

对于任何ICG,其都可以转化为一种“有向图游戏”

有向图游戏:

给定一个有向无环图,图中有一个唯一的起点(初始局面),在起点上有一枚棋子。
两名玩家需要交替地将该棋子沿着有向边进行移动,每次必须移动一步
无法移动者(来到终止局面)将被判负(也有可能判赢)。

具体转换方法为:

  • 将每一种局面看成有向无环图的节点。
  • 对于每一种局面,和能合法到达的下一种局面,将这两节点建立有向边。

这样,我们就能将各种博弈问题转化为统一的一种模型,方便我们思考与解决。

博弈问题种类

参考资料