《算法合集之《浅谈如何解决不平等博弈问题》》由会员分享，可在线阅读，更多相关《算法合集之《浅谈如何解决不平等博弈问题》（43页珍藏版）》请在金锄头文库上搜索。
1、浅谈如何解决不平等博弈问题,广东省中山市第一中学 方展鹏,引言,给出n棵竹子，高度分别为a1, a2 an，玩家L和R在这些竹子上面进行游戏，规则如下： 两人轮流操作，玩家L先手； 对于每次操作，先选定一棵高度不为0的竹子，然后砍掉该竹子的某一段，并且将与竹子底部不相连的部分也去掉； 最先无法进行操作的人输。假设玩家L和R都采取最优策略，问对于给出的局面谁 会获胜。,Hack This,引言,对于上述问题，根据The Sprague-Grundy Theorem，我们可以轻松地设计出一个时间复杂度为O(n)的算法。 详见2007年王晓柯前辈的论文,引言,The Sprague-Grundy T
2、heorem能在本题使用的前提条件 对于任意局面，玩家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 ，我们称 当且仅当不存在 使得 以及不存在 使得 。 得出 的定义后，我们还可以定义、=
4、我们称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个,C1,C1,C2,n个,u,m个,C1,C1,C2,n个,u,设u为由最下面的n+m-1个正方体叠成的塔对应的surreal numbe
5、r,Procrastination,SurrealNumber(T) /Ti表示塔T从下往上数第i个正方体的颜色 x 0 i 1 n 塔T的大小 while i n and Ti = T1if Ti = 白色 then x x + 1 else x x - 1i i + 1 k 2 while i nif Ti = 白色 then x x + 1/k else x x - 1/ki i + 1k k * 2 return x,B,B,B,时间复杂度：O(N),Procrastination,考虑局面G由n座塔T1, T2, Tn组成T1, T2, Tn对应的surreal number为x1,
6、 x2, xn,Procrastination,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)，与一个黑色的棋子
7、，初始位置为(bx, by)。玩家L执白先行，玩家R执黑后行，两人交替行棋。 如果当前是玩家L行棋，玩家L可以在上下左右四个方向中选一个并让他的棋子在该方向前进一格；如果当前是玩家R行棋，玩家R可以在上下左右四个方向中选一个并让他的棋子在该方向前进一格或两格（均不能走出棋盘）。一个人取得胜利当且仅当他的棋子走到了对方的棋子当前所在的位置。,The Easy Chase,玩家L与玩家R都采取同样的策略行棋：如果一方能赢，一定会用尽量少的步数去赢；如果一方会输，一定会拖尽量多的步数才输。 假设玩家L与玩家R都绝顶聪明，行棋中途均不犯错误，你能提前预测最终的胜者以及棋局持续的步数吗？ 数据规模：2
8、n 20,The Easy Chase,用一个五元组(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
9、(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)时走一步可以到达的位置。,。,The Easy Chase,用类似于SPFA的迭代算法来解决局面的计算顺序问题,Count(G) 初始化f，对于所有的局面G，令f(G) = 0 枚举所有的终止局面Ge，确定f(Ge)的值，并将Ge放入队列q中 while q不为空取出队首元素，并令其为Yfor 每个可以一步到达局面Y的局面Xtmp f(X)根据状态转移方程重新计算f(X)if tmp f(X) and X不在队列q中 then 将X放入队列q中 return f(G),
