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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,浅谈如何解决不平等博弈问题,广东省中山市第一中学 方展鹏,引言,给出,n,棵竹子，高度分别为,a,1,a,2,a,n,，玩家,L,和,R,在这些竹子上面进行游戏，规则如下：,两人轮流操作，玩家,L,先手；,对于每次操作，先选定一棵高度不为,0,的竹子，然后砍掉该竹子的某一段，并且将与竹子底部不相连的部分也去掉；,最先无法进行操作的人输。,假设玩家,L,和,R,都采取最优策略，问对于给出的局面谁,会获胜。,Hack This,引言,对于上述问题，根据,The Sprague-Grundy Theorem,，我们可以轻松地设计出一个时间复杂度为,O(n),的算法。,详见,2007,年王晓柯前辈的论文,引言,The Sprague-Grundy Theorem,能在本题使用的前提条件,对于任意局面，玩家,L,和玩家,R,的可选决策都相同,如果两者的可选决策不相同会怎样,?,我们不妨在游戏规则处再多加一条：竹子的每一段都被标上了,L,或者,R,，玩家,L,只能砍被标上,L,的段，玩家,R,只能砍被标上,R,的段。,加上上述规则后，玩家,L,和玩家,R,的可选决策就不相同了。,同时我们还发现,The Sprague-Grundy Theorem,在上述问,题上也不再成立。,引言,本文所要探讨的正是如何解决这类两个玩家的可选决策集合不相同的博弈问题，也称之为不平等博弈问题（,Partizan Games,）,概览,第一部分：介绍如何利用,Surreal Number,分析一类不平等组合游戏,第二部分：介绍如何通过动态规划、迭代等方法解决不平等博弈问题,第三部分：总结全文,Surreal Number,的定义,一个,surreal number,由两个集合组成。我们称这两个集合为“左集合”与“右集合”。,通常情况下，我们会将,surreal number,写作,L|R,，其中,L,表示左集合，,R,表示右集合。,左集合和右集合中的元素也为,surreal number,，且右集合中不存在元素,x,使得左集合中存在元素,y,满足,x,y,。,的定义,对于,surreal number x=X,L,|X,R,和,y=Y,L,|Y,R,，我们称 当且仅当不存在 使得,以及不存在 使得 。,得出,的定义后，我们还可以定义,、,=,我们称,x y,表示,我们称,x=y,表示,Surreal Number,的构造,第一个,surreal number,：,构造出,0,后，尝试利用,0,构造新的,surreal number,，可得：,0|,，,|0,以及,0|0,因为,0,0,，所以,0|0,不是一个合法的,surreal number,。,因为,|0 0 1,，,|-1 -1,，所以令,1|=2,，,|-1=-2,。,因为,0 0|1 0,，那么无论先手还是后手，玩家,L,都会获胜。,如果,G 1,时：,m,个,C,1,C,1,C,2,n,个,u,m,个,C,1,C,1,C,2,n,个,u,设,u,为由最下面的,n+m-1,个正方体叠成的塔对应的,surreal number,Procrastination,SurrealNumber(T)/Ti,表示塔,T,从下往上数第,i,个正方体的颜色,x 0,i 1,n,塔,T,的大小,while,i,n,and,Ti=T1,if,Ti=,白色,then,x x+1,else,x x-1,i,i+1,k 2,while,i,n,if,Ti=,白色,then,x x+1/k,else,x x-1/k,i i+1,k k*2,return,x,B,B,B,时间复杂度：,O(N),Procrastination,考虑局面,G,由,n,座塔,T,1,T,2,T,n,组成,T,1,T,2,T,n,对应的,surreal number,为,x,1,x,2,x,n,Procrastination,G,为,L,局面,G 0,C,1,不差于,C,2,当,C,2,+H 0,时，,C,1,+H 0,判断是否,C,1,C,2,!,总结,从上面的例子可以看出，利用,surreal number,分析不平等博弈问题，不仅思路清晰，而且程序的实现也相当简洁，但不同的不平等博弈问题分析思路也不尽相同，在我的论文中提供了多种分析思路。希望本文能为大家打开一扇窗，在遇到博弈问题的时候多一些解决问题的手段。,谢谢！,The Easy Chase,玩家,L,与玩家,R,很喜欢玩一个双人的棋类游戏，游戏规则如下：,在一个大小为,n*n,的棋盘上，有一个白色的棋子，初始位置为,(wx,wy),，与一个黑色的棋子，初始位置为,(bx,by),。玩家,L,执白先行，玩家,R,执黑后行，两人交替行棋。,如果当前是玩家,L,行棋，玩家,L,可以在上下左右四个方向中选一个并让他的棋子在该方向前进一格；如果当前是玩家,R,行棋，玩家,R,可以在上下左右四个方向中选一个并让他的棋子在该方向前进一格或两格（均不能走出棋盘）。一个人取得胜利当且仅当他的棋子走到了对方的棋子当前所在的位置。,The Easy Chase,玩家,L,与玩家,R,都采取同样的策略行棋：如果一方能赢，一定会用尽量少的步数去赢；如果一方会输，一定会拖尽量多的步数才输。,假设玩家,L,与玩家,R,都绝顶聪明，行棋中途均不犯错误，你能提前预测最终的胜者以及棋局持续的步数吗？,数据规模：,2,n,20,The Easy Chase,用一个五元组,(x1,y1,x2,y2,cur),来刻画一个局面,对于一个局面,G,，我们用函数,f(G),来描述,G,的胜负情况。定义,infinite,为一个很大的正整数，不妨设为,10,8,。如果局面,G,的胜者为玩家,L,且棋局持续,x,步，则,f(G)=infinite x,；如果局面,G,的胜者为玩家,R,且棋局持续,x,步，则,f(G)=-infinite+x,。,The Easy Chase,边界：,f(x,y,x,y,L)=-infinite,，,f(x,y,x,y,R)=infinite,。,转移：,f(x1,y1,x2,y2,L)=max f(x1,y1,x2,y2,R)sign(f(x1,y1,x2,y2,R),f(x1,y1,x2,y2,R)=min f(x1,y1,x2,y2,L)sign(f(x1,y1,x2,y2,L),其中,(x,1,y,1,),(x,2,y,2,),，,(x,1,y,1,),为白色棋子在,(x,1,y,1,),时走一步可以到达的位置，,(x,2,y,2,),为黑色棋子在,(x,2,y,2,),时走一步可以到达的位置。,。,The Easy Chase,用类似于,SPFA,的迭代算法来解决局面的计算顺序问题,Count(G),初始化,f,，对于所有的局面,G,，令,f(G)=0,枚举所有的终止局面,G,e,，确定,f(G,e,),的值，并将,G,e,放入队列,q,中,while,q,不为空,取出队首元素，并令其为,Y,for,每个可以一步到达局面,Y,的局面,X,tmp f(X),根据状态转移方程重新计算,f(X),if,tmp,f(X),and,X,不在队列,q,中,then,将,X,放入队列,q,中,return,f(G),证明,0 0|,证明：,0,0|&(0|0),先证明：,0 0,定理证明,a,A:a A|B,a,A:a,A|B,;,a,A:,(A|B,a),通过归纳法证明。首先当,A,为空集时命题正确,等价于,上述命题的右半部分显然正确，从,surreal number,定义可知；其左半部分等价于 也就是：,在上面命题的左边令,a=a,，则有 由归纳法的性质可以知道该命题是正确的，所以上面命题是正确的。所以,是正确的。类似地可以得出,也是正确的。,定理,2,证明,不妨设存在,x=x,1,x,2,|X,R,且,x,1,x,2,证明：,x,1,x,2,|X,R,x,2,|X,R,x,2,|X,R,x,1,x,2,|X,R,通过定义证明,定理,3,证明,先证明：如果,surreal number x,大于集合,A,中的任意元素且小于集合,B,中的任意元素，则,x=A,X,L,|X,R,B,利用定义证明,设,x,为,a,、,b,之间最早出生的,surreal number,，且,x,的父母为,x,L,和,x,R,，则有：,x,L,|,x,R,=a,x,L,|,b,x,R,=x,a|b =a,x,L,|,b,x,R,=x,Procrastination,我们先将在塔,T,最上面的,m+1,个正方体从上往下编号为,m,m 1,m 2,0,，然后分两种情况进行讨论：,m,个,C,1,C,2,k,n,个,u,v,Procrastination,Surreal Number,的一些基本定理,定理,1,对于一个,surreal number x=L|R,，,x,大于,L,中的任意一个元素且小于,R,中的任意一个元素。,定理,2,对于一个,surreal number x=L|R,，若集合,L,中有最大元素,l,max,，那么,l,max,|R =x,；类似地，若集合,R,中有最小元素,r,min,，那么,L|r,min,=x,。,定理,3,如果,a x b,，且,x,是,a,到,b,之间最早出生的,surreal number,，那么,a|b =x,。,Surreal Number,加法运算的基本性质,对于,surreal number x=X,L,|X,R,和,y=Y,L,|Y,R,，,x+y=X,L,+y,x+Y,L,|X,R,+y,x+Y,R,也是一个合法的,surreal number,。,surreal number,的加法满足交换率。,surreal number,的加法满足结合率。,游戏的定义,游戏有,2,名参与者，两人轮流操作。,游戏过程中的任意时刻有确定的状态。,参与者操作时将游戏从当前状态转移到另一状态，规则规定了在任意一个状态时，参与者可以到达的状态集合。,游戏总会在有限步数之内结束,(,没有平局,),。,参与者拥有完全的信息。,本文只讨论最先不能进行操作者输的情况。,