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

《浅谈如何解决不平等博弈问题》由会员分享，可在线阅读，更多相关《浅谈如何解决不平等博弈问题（43页珍藏版）》请在装配图网上搜索。

1、浅谈如何解决不平等博弈问题浅谈如何解决不平等博弈问题 引言n给出n棵竹子，高度分别为a1, a2 an，玩家L和R在这些竹子上面进行游戏，规则如下：两人轮流操作，玩家L先手；对于每次操作，先选定一棵高度不为0的竹子，然后砍掉该竹子的某一段，并且将与竹子底部不相连的部分也去掉； 最先无法进行操作的人输。假设玩家L和R都采取最优策略，问对于给出的局面谁会获胜。Hack This引言n对于上述问题，根据The Sprague-Grundy Theorem，我们可以轻松地设计出一个时间复杂度为O(n)的算法。n详见2007年王晓柯前辈的论文)().()(),.,(2121nnxgxgxgxxxg引言n

2、The Sprague-Grundy Theorem能在本题使用的前提条件q对于任意局面，玩家对于任意局面，玩家L和玩家和玩家R的可选决策都相同的可选决策都相同 n如果两者的可选决策不相同会怎样?n我们不妨在游戏规则处再多加一条：竹子的每一段都被标上了L或者R，玩家L只能砍被标上L的段，玩家R只能砍被标上R的段。 加上上述规则后，玩家加上上述规则后，玩家L和玩家和玩家R的可选决策就不相同了。的可选决策就不相同了。 同时我们还发现同时我们还发现The Sprague-Grundy Theorem在上述问在上述问 题上也不再成立。题上也不再成立。 引言n本文所要探讨的正是如何解决这类两个玩家的本文

3、所要探讨的正是如何解决这类两个玩家的可选决策集合不相同的博弈问题，也称之为不可选决策集合不相同的博弈问题，也称之为不平等博弈问题（平等博弈问题（Partizan Games） 概览n第一部分：介绍如何利用第一部分：介绍如何利用Surreal Number分析一类不平分析一类不平等组合游戏等组合游戏n第二部分：介绍如何通过动态规划、迭代等方法解决不平第二部分：介绍如何通过动态规划、迭代等方法解决不平等博弈问题等博弈问题n第三部分：总结全文第三部分：总结全文Surreal Number的定义n一个surreal number由两个集合组成。我们称这两个集合为“左集合”与“右集合”。 n通常情况下，

4、我们会将surreal number写作 L | R ，其中L表示左集合，R表示右集合。n左集合和右集合中的元素也为surreal number，且右集合中不存在元素x使得左集合中存在元素y满足x y。 的定义n 对于surreal number x = XL | XR 和y = YL | YR ，我们称 当且仅当不存在 使得 以及不存在 使得 。n得出 的定义后，我们还可以定义、=n我们称x y表示 n我们称x = y表示yx LLXx Lxy RRYy xyR)(xyyxxyyxSurreal Number的构造n第一个surreal number： n构造出0后，尝试利用0构造新的sur

5、real number，可得：q 0 | ， | 0 以及0 | 0 n因为0 0，所以 0 | 0 不是一个合法的surreal number。n因为 | 0 0 1， | -1 -1，所以令 1 | = 2， | -1 = -2。n因为0 0 | 1 0，那么无论先手还是后手，玩家L都会获胜。n如果G 1时：m个C1C1C2n个umuG21m个C1C1C2n个umuG21设u为由最下面的n+m-1个正方体叠成的塔对应的surreal numberProcrastinationSurrealNumber(T) /Ti表示塔T从下往上数第i个正方体的颜色1.x 02.i 13.n 塔T的大小4

6、.while i n and Ti = T15.if Ti = 白色 then x x + 1 else x x - 16.i i + 17.k 28.while i n9.if Ti = 白色 then x x + 1/k else x x - 1/k10.i i + 111.k k * 212.return xBBB1112141161321Procrastinationn考虑局面G由n座塔T1, T2, Tn组成nT1, T2, Tn对应的surreal number为x1, x2, xn nxxxG.21ProcrastinationG为L局面G 0C1不差于C2当C2 + H 0时，

7、C1 + H 0判断是否C1 C2 !总结n从上面的例子可以看出，利用surreal number分析不平等博弈问题，不仅思路清晰，而且程序的实现也相当简洁，但不同的不平等博弈问题分析思路也不尽相同，在我的论文中提供了多种分析思路。希望本文能为大家打开一扇窗，在遇到博弈问题的时候多一些解决问题的手段。The Easy Chasen玩家L与玩家R很喜欢玩一个双人的棋类游戏，游戏规则如下：n在一个大小为n*n的棋盘上，有一个白色的棋子，初始位置为(wx, wy)，与一个黑色的棋子，初始位置为(bx, by)。玩家L执白先行，玩家R执黑后行，两人交替行棋。n如果当前是玩家L行棋，玩家L可以在上下左右

8、四个方向中选一个并让他的棋子在该方向前进一格；如果当前是玩家R行棋，玩家R可以在上下左右四个方向中选一个并让他的棋子在该方向前进一格或两格（均不能走出棋盘）。一个人取得胜利当且仅当他的棋子走到了对方的棋子当前所在的位置。The Easy Chasen玩家L与玩家R都采取同样的策略行棋：如果一方能赢，一定会用尽量少的步数去赢；如果一方会输，一定会拖尽量多的步数才输。n假设玩家L与玩家R都绝顶聪明，行棋中途均不犯错误，你能提前预测最终的胜者以及棋局持续的步数吗？n数据规模：2 n 20The Easy Chasen用一个五元组(x1, y1, x2, y2, cur)来刻画一个局面 n对于一个局面

9、G，我们用函数f(G)来描述G的胜负情况。定义infinite为一个很大的正整数，不妨设为108。如果局面G的胜者为玩家L且棋局持续x步，则f(G) = infinite x；如果局面G的胜者为玩家R且棋局持续x步，则f(G) = -infinite + x。 The Easy Chasen边界：f(x, y, x, y, L) = -infinite，f(x, y, x, y, R) = infinite。n转移：qf(x1, y1, x2, y2, L) = max f(x1, y1, x2, y2, R) sign(f(x1, y1, x2, y2, R) qf(x1, y1, x2,

10、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。The Easy Chasen用类似于SPFA的迭代算法来解决局面的计算顺序问题 Count(G)初始化f，对于所有的局面G，令f(G) = 0枚举所有的终止局面Ge，确定f(Ge)的值，并将Ge放入队列q中while q不为空 取出队首元素，并令其为Y fo

11、r 每个可以一步到达局面Y的局面Xtmp f(X)根据状态转移方程重新计算f(X)if tmp f(X) and X不在队列q中 then 将X放入队列q中return f(G)证明0 0 | n证明：0 0 | & ( 0 | 0)n先证明：0 0定理证明na A : a A|Bna A : a A|B; a A : (A|B a)n通过归纳法证明。首先当A为空集时命题正确n等价于n上述命题的右半部分显然正确，从surreal number定义可知；其左半部分等价于 也就是：n在上面命题的左边令a=a，则有 由归纳法的性质可以知道该命题是正确的，所以上面命题是正确的。所以是正确的。类似地可以

12、得出也是正确的。定理2证明n不妨设存在x = x1, x2, | XR 且x1 x2n证明： x1, x2, | XR x2, | XR x2, | XR x1, x2, | XR n通过定义证明定理3证明n先证明：如果surreal number x大于集合A中的任意元素且小于集合B中的任意元素，则x = A, XL| XR, B n利用定义证明n设x为a、b之间最早出生的surreal number，且x的父母为xL和xR，则有：nxL | xR = a, xL | b, xR = xn a | b = a, xL | b, xR = xProcrastinationn我们先将在塔T最上面

13、的m + 1个正方体从上往下编号为m, m 1, m 2, 0，然后分两种情况进行讨论：m个C1C2kn个uvProcrastinationSurreal Number的一些基本定理 n定理定理1对于一个surreal number x = L | R ，x大于L中的任意一个元素且小于R中的任意一个元素。 n定理定理2 对于一个surreal number x = L | R ，若集合L中有最大元素lmax，那么 lmax | R = x；类似地，若集合R中有最小元素rmin，那么 L | rmin = x。n定理定理3 如果a x b，且x是a到b之间最早出生的surreal number，

14、那么 a | b = x。 Surreal Number加法运算的基本性质n对于surreal number x = XL | XR 和y = YL | YR ，x + y = XL + y, x + YL | XR + y, x + YR 也是一个合法的surreal number。nsurreal number的加法满足交换率。nsurreal number的加法满足结合率。游戏的定义n游戏有2名参与者，两人轮流操作。n游戏过程中的任意时刻有确定的状态。 n参与者操作时将游戏从当前状态转移到另一状态，规则规定了在任意一个状态时，参与者可以到达的状态集合。n游戏总会在有限步数之内结束(没有平局)。n参与者拥有完全的信息。n本文只讨论最先不能进行操作者输的情况。