《ACM课件lecture12组合博弈入门》由会员分享，可在线阅读，更多相关《ACM课件lecture12组合博弈入门（38页珍藏版）》请在金锄头文库上搜索。
1、ACM程序设计,杭州电子科技大学 刘春英 ,2019/6/12,2,今天，,你 了吗？,AC,2019/6/12,3,每周一星（10）：,Lin2144,2019/6/12,4,第十一讲,组合博弈入门 （Simple Game Theory）,2019/6/12,5,导引游戏,(1) 玩家：2人； (2) 道具：23张扑克牌； (3) 规则： 游戏双方轮流取牌； 每人每次仅限于取1张、2张或3张牌； 扑克牌取光，则游戏结束； 最后取牌的一方为胜者。,2019/6/12,6,基本思路？,请陈述自己的观点,2019/6/12,7,第一部分,简单取子游戏,（组合游戏的一种）,2019/6/12,8,
2、什么是组合游戏,有两个玩家； 游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）； 游戏双方轮流操作； 双方的每次操作必须符合游戏规定； 当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方； 无论如何操作，游戏总能在有限次操作后结束；,2019/6/12,9,概念:必败点和必胜点(P点 & N点),必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。 必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。,2019/6/12,10,必败(必胜)点属性,(1) 所有终结点是必败点（P点）； (2) 从任何必胜点（N点）操作，
3、至少有一种方法可以进入必败点（P点）； (3)无论如何操作， 从必败点（P点）都只能进入必胜点（N点）.,2019/6/12,11,取子游戏算法实现,步骤1:将所有终结位置标记为必败点（P点）； 步骤2: 将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点） 步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） ； 步骤4: 如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。,2019/6/12,12,课内练习:,Subtraction Games: subtraction set S = 1, 3, 4,2019/6/12
4、,13,实战练习,kikis game,2019/6/12,14,第二部分,Nim游戏,2019/6/12,15,Nim游戏简介,有两个玩家； 有三堆扑克牌（比如：可以分别是 5，7，9张）； 游戏双方轮流操作； 玩家的每次操作是选择其中某一堆牌，然后从中取走任意张； 最后一次取牌的一方为获胜方；,2019/6/12,16,2019/6/12,17,初步分析,(0, 0, 0),(0, 0, x),(0, 1, 1),(0, k, k),P-position,P-position,P-position,N-position,(14, 35, 46),?,2019/6/12,18,引入概念：Ni
5、m-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=0m）.,2019/6/12,19,定理一：,对于nim游戏的某个位置(x1,x2,x3),当且仅当它各部分的nim-sum等于0时（即x1x2x3=0），则当前位于必败点。,定理一也适用于更多堆的情况,2019/6/12,20,定理一的证明,2019/6/12,21,思考（1）：,有了定理一，如果判断某个游戏的先手是输还是赢？,2019/6/12,22,思考（2）：,对
6、于必胜点，如何判断有几种可行的操作方案？,2019/6/12,23,实例分析(HDOJ_1850),Being a Good Boy in Spring Festival,2019/6/12,24,第三部分,Graph Games & Sprague-Grundy Function,2019/6/12,25,What is the graph game ?,(1) Player I moves first, starting at x0. (2) Players alternate moves. (3) At position x, the player whose turn it is to
7、 move chooses a position y F(x). (4) The player who is confronted with a terminal position at his turn, and thus cannot move, loses.,2019/6/12,26,Example about graph game:,2019/6/12,27,The Sprague-Grundy Function.,Definition: The Sprague-Grundy function of a graph, (X,F), is a function, g, defined o
8、n X and taking non-negative integer values, such that g(x) =minn 0 : ng(y) for y F(x). (1) In words, g(x) the smallest non-negative integer not found among the Sprague-Grundy values of the followers of x. g(x) =mexg(y) : y F(x). (2),2019/6/12,28,Use of the Sprague-Grundy Function:,P-positions: Posit
9、ions x for which g(x) = 0 N-positions: Positions x for which g(x) 0,2019/6/12,29,Exercise:,What is the SG-value of the subtraction game with subtraction set S = 1, 2, 3?,2019/6/12,30,Question:,What can the S-G value describe?,2019/6/12,31,Part 4:,Sums of Combinatorial Games,2019/6/12,32,What is so-c
10、alled “Sums of Combinatorial Games”?,2019/6/12,33,Theorem 2.,If gi is the Sprague-Grundy function of Gi , i = 1, . . . , n, then G = G1 + + Gn has Sprague-Grundy function g(x1, . . . , xn) = g1(x1) gn(xn).,2019/6/12,34,Applications:,Sums of three Subtraction Games. In the first game: m = 3 and the p
11、ile has 9 chips. In the second: m = 5 and the pile has 10 chips. In the third: m = 7 and the pile has 14c hips. g(9, 10, 14) =?,2019/6/12,35,附:参考源码(HDOJ-1536),#include #include #include using namespace std; int k,a100,f10001; int mex(int p) int i,t; bool g101=0; for(i=0;ik;i+) t=p-ai; if(t0) break;
12、if(ft=-1) ft=mex(t); gft=1; for(i=0;i+) if(!gi) return i; ,int main() int n,i,m,t,s; while(scanf(“%d“, ,2019/6/12,36,课后练习,2008ACM ProgrammingExercise(12)_博弈入门,1517 A Multiplication Game 1079 Calendar Game 2147 kikis game 1404 Digital Deletions 1536 S-Nim 1729 Stone Game 1730 Northcott Game 1760 A New Tetris Game 1809 A New Tetris Game(2) 1524 A Chess Game,2019/6/12,37,记住:,学习是快乐的,2019/6/12,38,Welcome to HDOJ,Thank You ,
