ACM组合博弈几何学.pptVIP

ACM程序设计 湖州师范学院 陈宁宇 nychen@hutc.zj.cn 今天， 你 了吗？ 组合博弈入门 （Simple Game Theory） 导引游戏 (1) 玩家：2人； (2) 道具：23张扑克牌； (3) 规则： 游戏双方轮流取牌； 每人每次仅限于取1张、2张或3张牌； 扑克牌取光，则游戏结束； 最后取牌的一方为胜者。 基本思路？ 请陈述自己的观点 第一部分 简单取子游戏 什么是组合游戏—— 有两个玩家； 游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）； 游戏双方轮流操作； 双方的每次操作必须符合游戏规定； 当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方； 无论如何操作，游戏总能在有限次操作后结束； 概念:必败点和必胜点(P点 N点) 必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。 必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。 必败(必胜)点属性 (1) 所有终结点是必败点（P点）； (2) 从任何必胜点（N点）操作，至少有一种方法可以进入必败点（P点）； (3)无论如何操作， 从必败点（P点）都只能进入必胜点（N点）. 取子游戏算法实现—— 步骤1:将所有终结位置标记为必败点（P点）； 步骤2: 将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点） 步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） ； 步骤4: 如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。 第二部分 Nim游戏 Nim游戏简介 有两个玩家； 有三堆扑克牌（比如：可以分别是 5，7，9张）； 游戏双方轮流操作； 玩家的每次操作是选择其中某一堆牌，然后从中取走任意张； 最后一次取牌的一方为获胜方； 初步分析 (0, 0, 0) 引入概念：Nim-Sum 定义: 假设 (xm · · · x0)2 和(ym · · · y0)2 的nim-sum是(zm · · · z0)2,则我们表示成 (xm · · · x0)2 ⊕ (ym · · · y0)2 = (zm · · · z0)2, 这里，zk = xk + yk (mod 2)（k=0…m）. 定理一： 对于nim游戏的某个位置(x1,x2,x3),当且仅当它各部分的nim-sum等于0时（即x1⊕x2⊕x3=0），则当前位于必败点。 定理一的证明…… 思考（1）： 有了定理一，如果判断某个游戏的先手是输还是赢？ 思考（2）： 对于必胜点，如何判断有几种可行的操作方案？ 计算几何初步 (Computational Geometry Basic) 第一单元 线段属性 思考： 1、传统的计算线段相交的方法是什么？ 2、传统方法和本方法的区别是什么？ 特别提醒： 以上介绍的线段的三个属性，是计算几何的基础，在很多方面都有应用，比如求凸包等等，请务必掌握！ 第二单元 多边形面积和重心 基本问题（1）： 给定一个简单多边形，求其面积。 输入：多边形（顶点按逆时针顺序排列） 输出：面积S 思考如下图形： Any good idea? 先看最简单的多边形——三角形 三角形的面积： 在解析几何里， △ABC的面积可以通过如下方法求得： 点坐标 = 边长 = 海伦公式 = 面积 思考：此方法的缺点： 计算量大 计算几何的方法： 在计算几何里，我们知道，△ABC的面积就是“向量AB”和“向量AC”两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。 大功告成： Area(A,B,C)= 1/2 * (↑AB) × (↑AC) =∣ ∣/2 特别注意： 以上得到是有向面积（有正负）！ 凸多边形的三角形剖分 很自然地，我们会想到以 P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积： A=sigma(Ai) (i=1…N-2) 凹多边形的面积？ 依然成立！！！ 多边形面积公式：A=sigma(Ai) (i=1…N-2) 任意点为扇心的三角形剖分： 我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？ 比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。 前面的三角剖分显然对于多边形内部任意一点都是合适的！ 我们可以得到： A=sigma(Ai) （ i=1…N ） 即：A=sigma∣ ∣/2 （