算法合集之浅谈如何解决不平等博弈问题

引言给出n棵竹子，高度分别为a1,a2…an，玩家L和R在这些竹子上面进行游戏，规则如下：①两人轮流操作，玩家L先手；②对于每次操作，先选定一棵高度不为0的竹子，然后砍掉该竹子的某一段，并且将与竹子底部不相连的部分也去掉；③最先无法进行操作的人输。假设玩家L和R都采取最优策略，问对于给出的局面谁会获胜。HackThis引言对于上述问题，根据TheSprague-GrundyTheorem，我们可以轻松地设计出一个时间复杂度为O(n)的算法。详见2007年王晓柯前辈的论文)()...()(),...,(2121nnxgxgxgxxxg引言TheSprague-GrundyTheorem能在本题使用的前提条件对于任意局面，玩家L和玩家R的可选决策都相同如果两者的可选决策不相同会怎样?我们不妨在游戏规则处再多加一条：竹子的每一段都被标上了L或者R，玩家L只能砍被标上L的段，玩家R只能砍被标上R的段。加上上述规则后，玩家L和玩家R的可选决策就不相同了。同时我们还发现TheSprague-GrundyTheorem在上述问题上也不再成立。引言本文所要探讨的正是如何解决这类两个玩家的可选决策集合不相同的博弈问题，也称之为不平等博弈问题（PartizanGames）概览第一部分：介绍如何利用SurrealNumber分析一类不平等组合游戏第二部分：介绍如何通过动态规划、迭代等方法解决不平等博弈问题第三部分：总结全文SurrealNumber的定义一个surrealnumber由两个集合组成。我们称这两个集合为“左集合”与“右集合”。通常情况下，我们会将surrealnumber写作{L|R}，其中L表示左集合，R表示右集合。左集合和右集合中的元素也为surrealnumber，且右集合中不存在元素x使得左集合中存在元素y满足xy。的定义对于surrealnumberx={XL|XR}和y={YL|YR}，我们称当且仅当不存在使得以及不存在使得。得出的定义后，我们还可以定义、=我们称xy表示我们称x=y表示yxLLXxLxyRRYyxyR)(xyyxxyyxSurrealNumber的构造第一个surrealnumber：构造出0后，尝试利用0构造新的surrealnumber，可得：{0|}，{|0}以及{0|0}因为00，所以{0|0}不是一个合法的surrealnumber。因为{|0}0{0|}，所以令{|0}=-1，{0|}=1。}|{{|}0SurrealNumber的构造利用0,1,-1作为左集合与右集合的元素，我们可以构造出17个合法的surrealnumber因为{1|}1，{|-1}-1，所以令{1|}=2，{|-1}=-2。因为0{0|1}1，且{0|1}+{0|1}=1，因此我们令{0|1}=1/2。同理我们可以得出{-1|0}=-1/2。SurrealNumber的构造如此类推，我们可以构造出所有形如j/2k的有理数。具体而言，我们可以定义如下函数来建立部分有理数与surrealnumber的对应关系，我们称这个函数为达利函数：0,2)},21(|)21({0)},1({|0|},)1({0{|},)(kZkjjxjjZxxxZxxxxxkkkSurrealNumber的基本定理定理对于一个surrealnumberx={L|R}，若集合L中有最大元素lmax，那么{lmax|R}=x；类似地，若集合R中有最小元素rmin，那么{L|rmin}=x。例子：{2,3|4,5}={3|4,5}={2,3|4}={3|4}。SurrealNumber的加法运算对于surrealnumberx={XL|XR}和y={YL|YR}，它们的加法运算被定义为：其中对于集合X与surrealnumbery，边界情况：},|,{}|{}|{RRLLRLRLYxyXYxyXYYXXyx}:{XxyxyXn①②游戏的定义游戏有2名参与者，两人轮流操作。游戏过程中的任意时刻有确定的状态。参与者操作时将游戏从当前状态转移到另一状态，规则规定了在任意一个状态时，参与者可以到达的状态集合。游戏总会在有限步数之内结束(没有平局)。参与者拥有完全的信息。本文只讨论最先不能进行操作者输的情况。游戏的表示对于一个游戏，如果它当前处于状态P，玩家L可以转移到的状态的集合为PL，玩家R可以转移到的状态的集合为PR，那么我们把这个游戏写作P={PL|PR}。例子：当前所处的状态：P玩家L可以到达的状态：ABC玩家R可以到达的状态：D则：P={ABC|D}SurrealNumber与游戏如果G0，那么无论先手还是后手，玩家L都会获胜。如果G0，那么无论先手还是后手，玩家R都会获胜。如果G=0，那么谁后手谁获胜。SurrealNumber与游戏游戏的和如果一个游戏G可以被分解成n个不相交的子游戏G1,G2,…Gn，使得对G的每次操作等价于从n个子游戏中选取一个来进行操作，那么我们称游戏G是游戏G1,G2,…Gn的和，写作G=G1+G2+…+Gn。定理如果游戏G等于surrealnumberx，游戏H等于surrealnumbery，那么游戏G+H等于surrealnumberx+y。Procrastination有一个叫Procrastination的游戏，规则如下：游戏一开始有四座由正方体叠成的塔，且所有的正方体要么黑色，要么白色。有两个玩家L和R，两个人轮流进行操作。每次操作，玩家要选定一个正方体，然后拿走该正方体以及位于该正方体上面的所有正方体，并且规定玩家L只能选定白色的正方体，玩家R只能选定黑色的正方体。最先不能进行操作的人输。BBBBBBChoosethisProcrastination对于一个局面，如果玩家L无论先手还是后手都能获胜，那么我们称这是一个L局面。定义子局面C表示一个由三座塔组成的局面。一个完整的游戏局面可以由一个子局面C以及一座塔T构成，写作(C,T)。对于两个子局面C1和C2，我们称C1不差于C2当且仅当对于任意的一座塔T，当(C2,T)为L局面时(C1,T)也为L局面。给出两个子局面C1和C2，问是否C1不差于C2。Procrastination考虑只有一座塔的情况：0{|}G1|}0{G2|}1,0{GProcrastination不难得出：n个…nGn个…nGProcrastination考察：当m=1时：m个C1C1C2……n个n个…21}|1{}|1,...1,0{nnnnnGProcrastination考察：当m=1时：m个C1C1C2……n个n个21}|1,...1,0{nnnG…Procrastination当m1时：m个C1C1C2……n个umuG21m个C1C1C2……n个umuG21设u为由最下面的n+m-1个正方体叠成的塔对应的surrealnumberProcrastinationSurrealNumber(T)//T[i]表示塔T从下往上数第i个正方体的颜色1.x←02.i←13.n←塔T的大小4.whileinandT[i]=T[1]5.ifT[i]=白色thenx←x+1elsex←x-16.i←i+17.k←28.whilein9.ifT[i]=白色thenx←x+1/kelsex←x-1/k10.i←i+111.k←k*212.returnxBBB1112141161321Procrastination考虑局面G由n座塔T1,T2,…Tn组成T1,T2,…Tn对应的surrealnumber为x1,x2,…xnnxxxG...21ProcrastinationG为L局面G0C1不差于C2当C2+H0时，C1+H0判断是否C1C2!总结从上面的例子可以看出，利用surrealnumber分析不平等博弈问题，不仅思路清晰，而且程序的实现也相当简洁，但不同的不平等博弈问题分析思路也不尽相同，在我的论文中提供了多种分析思路。希望本文能为大家打开一扇窗，在遇到博弈问题的时候多一些解决问题的手段。TheEasyChase玩家L与玩家R很喜欢玩一个双人的棋类游戏，游戏规则如下：在一个大小为n*n的棋盘上，有一个白色的棋子，初始位置为(wx,wy)，与一个黑色的棋子，初始位置为(bx,by)。玩家L执白先行，玩家R执黑后行，两人交替行棋。如果当前是玩家L行棋，玩家L可以在上下左右四个方向中选一个并让他的棋子在该方向前进一格；如果当前是玩家R行棋，玩家R可以在上下左右四个方向中选一个并让他的棋子在该方向前进一格或两格（均不能走出棋盘）。一个人取得胜利当且仅当他的棋子走到了对方的棋子当前所在的位置。TheEasyChase玩家L与玩家R都采取同样的策略行棋：如果一方能赢，一定会用尽量少的步数去赢；如果一方会输，一定会拖尽量多的步数才输。假设玩家L与玩家R都绝顶聪明，行棋中途均不犯错误，你能提前预测最终的胜者以及棋局持续的步数吗？数据规模：2n20TheEasyChase用一个五元组(x1,y1,x2,y2,cur)来刻画一个局面对于一个局面G，我们用函数f(G)来描述G的胜负情况。定义infinite为一个很大的正整数，不妨设为108。如果局面G的胜者为玩家L且棋局持续x步，则f(G)=infinite–x；如果局面G的胜者为玩家R且棋局持续x步，则f(G)=-infinite+x。TheEasyChase边界：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))}其中(x1,y1)(x2,y2)，(x1’,y1’)为白色棋子在(x1,y1)时走一步可以到达的位置，(x2’,y2’)为黑色棋子在(x2,y2)时走一步可以到达的位置。0,10,00,1)(xxxxsign。TheEasyChase用类似于SPFA的迭代算法来解决局面的计算顺序问题Count(G’)初始化f，对于所有的局面G，令f(G)=0枚举所有的终止局面Ge，确定f(Ge)的值，并将Ge放入队列q中whileq不为空取出队首元素，并令其为Yfor每个可以一步到达局面Y的局面Xtmp←f(X)根据状态转移方程重新计算f(X)iftmpf(X)andX不在队列q中then将X放入队列q中returnf(G’)证明0{0|}证明：0{0|}&({0|}0)先证明：00定理１证明aA:a{A|B}bB:b{A|B}aA:a{A|B}①;aA:({A|B}a)②通过归纳法证明。首先当A为空集时命题正确①等价于上述命题的右半部分显然正确，从surrealnumber定义可知；其左半部分等价于也就是：在上面命题的左边令a’=a，则有由归纳法的性质可以知道该命题是正确的，所以上面命题是正确的。所以①是正确的。类似地可以得出②也是正确的。定理2证明不妨设存在x={x1,x2,…|XR}且x1x2证明：{x1,x2,…|XR}{x2,…|XR}{x2,…|XR}{x1,x2,…|XR}通过定义证明定理3证明先证明：如果surrealnumberx大于集合A中的任意元素且小于集合B中的任意元素，则x={A,XL|XR,B}利用定义证明设x为a、b之间最早出生