浅谈如何解决不平等博弈问题

所需积分/C币:50 2012-12-21 12:20:03 641KB PDF
收藏 收藏
举报

算法合集之《浅谈如何解决不平等博弈问题》
IO2009冬令营论文方展 正文 、引言 在信息学竞赛中,博弈问题十分常见,下面就是一个例子 引例: Green hackenbush(绎典问题) 给出n棵竹子,高度分别为a1,a2…an,玩家L和R打算在这些竹子上面玩 砍竹子游戏,规则如下 1、两人轮流操作,玩家L先于 2、对于每次操作,先选定一棵高度不为0的个子,然后砍掉该竹子的某 段,并且将与竹子底部不相连的部分也去掉; 3、最先无法进行操作的人输 假设玩家L和R都采取最优策略,请问对于给岀的局面谁会获胜。 Hack This 不难看出,一棵高度为n的竹子,经过一次操作之后可以变成一棵高度为0 到n-1的竹子。因此,一棵高度为n的竹子就等价于一个有n颗石子的石子堆(nim pile)。所以,上面的问题就转化为有n堆石子,石子数分別为a1,a2…an,两个 玩家轮流操作,钶次操作为选取一堆石子并从屮拿走不少于1个,最先无沄进行 操作的人输,问先手必胜还是后手必胜。对于这个问题,根据 The Sprague-Grundy Theoren,我们可以轻松地设计出一个时间复杂度为Om)的算法2 我们发现在 Green Hackenbush中,对于任意局面,玩家L和玩家R的可选 决策都是相冋的,也就是如果玩家L可以对第ⅰ棵竹子的第j段操作,则玩家R 也可以。但是,如果不相同的话会怎么样?我们不妨在游戏规则处再多加一条: 竹子的每一段都被标了L或者R,玩家L只能砍被标上:L的段,玩家R只能 1设g为游戏G1的SG函数,则(=G1(21.Gn的SG函数g(x1x2.xn)=g(x)xorg2(x2)… xor gn(x) 2详见2002年集训队论文《由感性认识到理性认识—透析一·类搏弈游戏的解答过程》张一飞 IO2009冬令营论文方展鹏 砍被标上R的段。加上这条限制以后,玩家L和玩家R的可选决策就不相同了, 同时我们还发现 The Sprague-Grundy Theorem在这类问题上也不再成立。 木文所要探讨的正是如何解决这类两个玩家的可选决策集合不相同的博弈 问题,也称之为不平等博弈问题( Partizan games)。 、另辟蹊径 木节将介绍一个新的工具 Surreal number,并且通过一道例题介绍如何利用 这工具来分析和解决类不平等的组合游戏( Partisan Combinatorial games) 215 urrea| Number介绍 在数学中, surreal number是一个包含无穷大数、无穷小数还有实数的域。下 面将介绍 surreal number的定义以及相关性质。由于本文只是将 surreal number 作为一个分析博究问题的L具引入,所以 surreal number的一些与博究问题关系 不大的性质将不会在本文被提及,有兴趣的读者请参看参考文献[1]。 211 Surrey| Number的构造 定义1一个 surreal number由两个集合组成。我们称这两个集合为“左集合” 与“右集合”。通常情况下,我们会将 surreal number写作{L|R},其中L表小 左集合,R表示右集合。这两个集合中的元素也为 surreal number,且右集合中 不存在一个元素x使得左集合中存在一个元素y满足x≤y。 定义2对于 surreal number x={XL|XR}和y={Yu|YR},我们称x≤y当 H仅当不存在x∈X使得y≤x1以及不存在yn∈Y使得v≤x。为了表述方 便,我们可以将y≤x写作x≥y,将x≤y(y≤x)写作xy,将yx写作x>y, 将x≤y∧y≤x写作x-y。 不难看出上面的两个定义都是基于递归的形式给出的,通过上面的两个定 义,我们可以尝试构造 surreal number 由定义1可知,一个 surreal number由左集合与右集合组成,且这两个集合 IO2009冬令营论文方展 的元素也必须为 surreal number。 但是我们目前连一个 surreal number也不知道, 因此只能令L为空集,R为空集,得出{Φ|Φ},通常情况下会简写成{|}。根据 定义1,我们可以证明{}是一个合法的 surreal number。然后,我们令{|}=0。 同时我们称0是在第0天出生 构造出0之后,我们尝试利用0构造出新的 surreal number,得出{0},{ 0〕以及{00}。根据定义2可知,0≤0,因此{0|0}并不满足定义1,所以{0 10}不是一个 surreal number 利用定义2,我们可以证明{|0}<0≤{01},因此我们令{10}=-1,{01} =1,同时我们称1和-1是在第1天出生的 利用0,1,1作为左集合与右集合的元素,我们可以构造出17个合法的 surreal number,我们称这17个 surreal number是在第2大出生的。其中利用定义2, 我们可以证明1<{1|}和-1>{|-1},因此我们令{1}=2,{-1}--2。 另外,我们发现0<{0|1}<1,由于在稍后介绍的加法运算中会有{01}+ 011}=1,因此我们令{01}=12。同理我们可以得出{-110}=2 因此现在我们有7个 surreal number: 0,2,1,2。虽然在第2天出 生的合法的 surreal number还有13个,但是可以证明它们的值是上面这7个数的 其中一个。例如利用定义2,我们可以证明{-11}=0。 如此类推,在第3天我们可以构造出4={0|2},34={1211},32={1 12},3-{2|}以及对应的负数的情况。直这样下去,我们可以构造出所有形 如j2的有埋数。具体而言,我们可以定义如下函数来立部分有理数与 surreal number的对应关系,我们称这个函数为达利函数: {|} 0 d(x-1)|,x>0∧x∈z (x) {d(x+1)} 0 1 Rocn ∧j,k∈Z入k>0 实际上我们还可以构造出所有的实数、无穷大数和无穷小数,但是这与本文 的主题关系不大,因此这里就不给出具体的构造方法了,有兴趣的读者可以参看 参考文献[1] IO2009冬令营论文方展鹏 212 Surreal| Number的一些基本定理 定理1对于一个 surreal number x={L|R},x人于L中的任意一个元素且 小于R中的任意一个元素。 定理2对于一个 surreal number x={LR},若集合L中有最大元素lmax 那么{1max|R}=x;类似地,若集合R屮有最小元素rm,那么{L|rmn}=x。 举个简单的例子:{1,2,34,5}={34,5}={1,2,34}={3|4}。 看到这里,或许会有读者提出能否将 surreal number的定义改为“左集合与 右集合最多只能含有个元素”,实际上这是不行的。注意到定理2要求集合L 中有最大元素,集合R中有最小元素,然而当集合L与集合R的大小为无穷大 时,就可能出现不存在最大元素与最小元素的情况,因此 surreal number的定义 不能修改。 定理3设a到b之间最早出生的 surreal number是在第i天出生,那么在a 到b之间且在第i天出生的 surreal number只有一个。 定理4如果a<x<b,且x是a到b之间最早出生的 surreal number,那么{a 213 Surrey| Number的运算法则 下面我们将给出 surreal number的加法运算法则与减法运算法则,这两个法 则也是基于递归的形式给出的。 定义3对于 surreal number x={XLXR}和y={YLYR},它们的加法运算 被定义为: x+y={k1|X2}+{y4|}={X2+y,x+Y2|A+y,x+Y2}, 其中对于集合X与 surreal number y,X+y={x+y:x∈H} 注意到上面关于加法的定义是基于递归给出的,因此我们还要增加一个结束 的条件:①+n= 定义4对于 surreal number x={XLXR},x的相反数为 x=-{X|Xk}={-X|-X},其中对于集合X,-X={-x:x∈H}。 由于关于相反数的定义乜是基于递归给出的,因此我们还要增加一个结束的 IO2009冬令营论文方展鹏 条件:-0=-{}={}=0。 定义5对于 surreal number x和y,x-y=x+(-y) 通过上面的三个定义,我们可以得出如下定理: 定理5对于 surreal number x={XLXR}和y={Yu|YR},x+y={XL+y, +YL|XR+y,x+YR}也是一个合法的 surreal number 定理6 surreal number的加法满足交换率,即x+y=y+x 定理7 surreal number的加法满足结合率,即(x+y)+z=x+(y+z)。 225 ureal Number与组合游戏 221组合游戏的定义与表示 在介绍 surreal number在组合游戏中的应用之前,我们先来看看这里所讲的 组合游戏的定义 ■游戏有2名参与者,通常称为玩家L和玩家R。 游戏过程中的任意时刻有确定的状态。 参与者操作吋将游戏从当前状态转移到另状态,规则规定了在任意 个状态时,参与者可以到达的状态集合。 参与者轮流进行操作 在游戏处于某状态,当前参与者不能进行操作时,游戏结束。本节只讨 论最先不能进行操作者输的情况。 尢论参与者做出怎样的操作,游戏总会在有限步数之内结束(没有半局) ■参与者拥有游戏本身,和游戏过程的所有信息,比如规则、自己和对于 之前的操作。 由上面的定义可以看出,我们这里所讲的游戏是由状态组成的。对于一个游 戏,如果它当前处于状态P,玩家L可以转移到的状态的集合为P,玩家R可 以转移到的状念的集合为P,那么我们把这个游戏写作P={P|PR} 举个例子,例如当前处于状态P,玩家L可以到达的状态为A、B、C,玩家 R可以到达的状态为D,那么我们可以这样描述当前的游戏:P={A,B,C|D} 看到这里,读者可能会觉得这甲的游戏与 surreal number非常相似。事实上 IO2009冬令营论文方展鹏 也的确如此,因为所有的 surreal number都是游戏,但是并非所有的游戏都是 surreal number,因为对于游戏P={PP},并没有要求集合P中的仁意元素 都要小于集合P中的任意元素。因此我们下面讨论的游戏,都是可以表示为 surreal number的游戏。 222 Surreal| Number在组合游戏中的应用 对于一个游戏G,如果玩家L和玩家R都采用最优策略进行游戏,且游戏G 等价于 surreal number X,那么有如下结论: 如果ⅹ>0,那么无论先手还是后手,玩家L都会获胜。 如果x<0,那么无论先手还是后手,玩家R都会获胜。 如果x=0,那么谁后手谁获胜。 上面的结论可以用类似于数学归纳法的思想来证明: 当x>0时,如果是玩家L先于,从ⅹ是 surreal number可知,玩家L总可以 将ⅹ转移到一个大于等于0的状态;如果是玩家R先于,那么玩家R只能将x 转移到一个大于0的状态,因此任意时刻玩家L的可选决策集合都不为空集, 所以这种情况无论先手还是后手,玩家L都会获胜 当ⅹ<0时,玩家L只能将ⅹ转移到一个小于0的状态,而玩家R总可以将 x转移到一个小于等于0的状态,因此任意时刻玩家R的可选决策集合都不为空 集,所以无论先手还是后手,玩家R都会获胜。 当ⅹ=0时,如果是玩家L先手,那么他只能将ⅹ转移到一个小于0的状态, 这样玩家R会获胜:如果是玩家R先手,那么他只能将x转移到一个大于0的 状态,这样玩家L会获胜。所以,对于ⅹ=0的情况,谁后手谁获胜。 很多时候,一个游戏G会被分解成n个个相交的子游戏G1,Gi2,…Gn,对G 的每次操作等价于从n个子游戏中选取一个来进行操作。这种情况,我们称游戏 G是游戏G1,G2,.Gn的和,写作G=G1+G2+.+Gn。有n堆石子的Nim游戏 就是一个经典的例子。 对于这类可分解的游戏, surreal number能够对其较好地进行分析,因为有如 下定理 IO2009冬令营论文方展 定理8如果游戏G等价于 surreal number x,游戏H等价于 surreal number y, 那么游戏G+∏等价于 surreal number x+y 上述定理通过 surreal number加法运算的定义来证明。通过上面的定理我们 可以解决很多 The sprague-Grundy Theoren无法解决的不平等博弈问题,下面我 们通过道例题来介绍如何利用 surreal number以及上述定理来解决类不平等 的组合游戏 23例一: Procrastination3 题目描述 有一个叫 Procrastination的游戏,规则如下 游戏一开始有四座由正方休叠成的塔,且所有的正方休要么是黑色,要 么白色。 ■有两个玩家L和R,游戏开始后,两个玩家轮流进行操作。 ■每次操作,玩家要选定一个忙方体,然后拿走该忙方体以及位于该方 体上面的所有正方体,并且规定玩家L只能选定白色的正方体,玩家R 只能选定黑色的正方体。 ■最先个能进行操作的人输。 B B」 Choose this B B B B W B BLW B B WBw 对于一个初始局面,如果玩家L无论先手还是后手都能获胜,那么我们称这 是一个W- configuration。另外我们定义子局面C表示一个由三座塔组成的局面。 一个完整的游戏局面可以由一个子局面C以及一座塔T构成,写作(C,T)。对于 两个子局面C1和C2,我们称C1不差于C2当且仅当对于任意的一座塔T,在(C2, 1)为W- configuration时(C1,T)也为W- configuration MIT Programming Contest 2005, pku2931 IO2009冬令营论文方展鹏 给出两个子局面C1和C2,问是否C1不差于C2。 数据规模:对于钶座给出的塔,它的高度n满足0≤n≤50。 分析 我们不妨先从简单的情况出发,考虑只包含一座塔T的局面G: 如果塔T一个正方休也没有,那么无论玩家L还是玩家R都没有任何可选 决策,因此G={}。由2.1节的定义可知,G=0。 如果塔T由个白色正方体叠成,那么玩家L有个转移到状态0的决策(选 这个白色方体进行操作),因此G={0|}=1。 如果塔T由两个白色正方体叠成,那么玩家L有一个转移到状态1的决策(选 定上面的正方体)以及一个转移到状态0的决策(选定卜面的正方体),因此G {01|}-2 通过数学归纳法,我们可以得出如果塔T由n个白色正方体叠成,那么G 。同理我们可以得出如果塔T由n个黑色正方体叠成,有G=-n。 下面我们考虑图(1)的情况,即塔T由n(n>O)个白色正方体加 个黑色正方体叠成。容易得出此时G={0,1, 1|n}=n (1) 如果塔T由n(n>0)个白色正方体加上两个黑色正方体叠成, 如图(2)所示,则有G={n-11n-2}=n-12-44。如果在图(2)的基B 上在塔T的顶端放上一个黑色止方体,可得G=n-12-14- 若在图(②2)的基{上在塔T的顶端放上一个白色止方体,可得G=n /4+ 如此类推,对于任意一个只包含一座塔T的局面G,我们可以用如下算法计 算与G对应的 surreal number x(为了方便叙述,用伪代码来表示)

...展开详情
试读 26P 浅谈如何解决不平等博弈问题
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    浅谈如何解决不平等博弈问题 50积分/C币 立即下载
    1/26
    浅谈如何解决不平等博弈问题第1页
    浅谈如何解决不平等博弈问题第2页
    浅谈如何解决不平等博弈问题第3页
    浅谈如何解决不平等博弈问题第4页
    浅谈如何解决不平等博弈问题第5页
    浅谈如何解决不平等博弈问题第6页
    浅谈如何解决不平等博弈问题第7页
    浅谈如何解决不平等博弈问题第8页

    试读已结束,剩余18页未读...

    50积分/C币 立即下载 >