ACM程序设计杭州电子科技大学 刘春英 acm@
今天,
你
了吗?
2014-10-18
每周一星(10):
Lin2144
2014-10-18
第十一讲
组合博弈入门(Simple Game Theory)
2014-10-18
导引游戏(1) 玩家:2人; (2) 道具:23张扑克牌; (3) 规则:游戏双方轮流取牌; 每人每次仅限于取1张、2张或3张牌; 扑克牌取光,则游戏结束; 最后取牌的一方为胜者。
2014-10-18
基本思路?
请陈述自己的观点
2014-10-18
第一部分简单取子游戏 (组合游戏的一种)
2014-10-18
什么是组合游戏——(1) 有两个玩家; (2) 游戏的操作状态是一个有限的集合(比如: 限定大小的棋盘); (3) 游戏双方轮流操作; (4) 双方的每次操作必须符合游戏规定; (5) 当一方不能将游戏继续进行的时候,游戏 结束,同时,对方为获胜方; (6) 无论如何操作,游戏总能在有限次操作后 结束;2014-10-18 8
概念:必败点和必胜点(P点 & N点)
必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。 必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。
2014-10-18
必败(必胜)点属性(1) 所有终结点是必败点(P点); (2) 从任何必胜点(N点)操作,至少有 一种方法可以进入必败点(P点); (3)无论如何操作, 从必败点(P点)都 只能进入必胜点(N点).
2014-10-18
取子游戏算法实现——步骤1:将所有终结位置标记为必败点(P点);步骤2: 将所有一步操作能进入必败点(P点)的 位置标记为必胜点(N点) 步骤3:如果从某个点开始的所有一步操作都只能 进入必胜点(N点) ,则将该点标记为必败点 (P点) ; 步骤4: 如果在步骤3未能找到新的必败(P点), 则算法终止;否则,返回到步骤2。2014-10-18 11
课内练习:
Subtraction Games: subtraction set S = {1, 3, 4}
x : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14… Pos: P N P N N N N P N P N N N N P…
2014-10-18
实战练习…
kiki's game
2014-10-18
第二部分
Nim游戏
2014-10-18
Nim游戏简介(1) 有两个玩家; (2) 有三堆扑克牌(比如:可以分别是 5,7,9张); (3) 游戏双方轮流操作; (4) 玩家的每次操作是选择其中某一堆牌, 然后从中取走任意张; (5) 最后一次取牌的一方为获胜方;2014-10-18 15
2014-10-18
初步分析
(0, 0, 0)
P-position
(0, 0, x)(0, 1, 1) (0, k, k) (14, 35, 46)
N-positionP-position P-position ???17
2014-10-18
引入概念: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).
2014-10-18
定理一:对于nim游戏的某个位置(x1,x2,x3),当 且仅当它各部分的nim-sum等于0时(即 x1⊕x2⊕x3=0),则当前位于必败点。
…… 此处隐藏0字 ……
定理一也适用于更多堆的情况~
2014-10-18
定理一的证明……
2014-10-18
思考(1):
有了定理一,如果判断某个游戏 的先手是输还是赢?
2014-10-18