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