游戏策略讲义

《游戏策略讲义》由会员分享，可在线阅读，更多相关《游戏策略讲义（40页珍藏版）》请在装配图网上搜索。

1、游戏策略游戏策略朱全民Nim问题问题 l取石子问题有N堆石子，其中第i堆有Pi颗石子，每次从某一堆里选出若干石子去掉（但不能不去石子），两人轮流取石，谁不能继续取谁就输了。l什么情况下先手必胜，什么情况下后手必胜?第一堆：a1=3第二堆：a2=3第三堆：a3=1分析分析l从上述博弈树可以看出3,3,1是必胜点，那么我们可以这么想，如果某个点是必胜点，则取完棋子后，必须使得对方落在必败点。l若只有一堆石子，先收走必胜l若有m堆石子，每堆只有一颗石子，m堆为奇数时，先手必胜。l若有m堆石子，每堆有k颗石子，m堆为奇数时，先手必胜。第1次，先手取k棵，轮到对手走时，若对手取k棵，则先手也取k棵，若对

2、手取xPi，S-S，PiPi，则Pi XOR Pi0。所以S XOR Pi XOR Pi=S=0，即S=Pi XOR Pi0。满足P局面的所有子局面都是N局面。3.若S0，设S的二进制位是A1An，考虑第一位是1的。在P中取出该位同是1的，不妨设为P1。可知P1 XOR S0），两人轮流取石，谁不能继续取谁就输了。l什么情况下先手必胜，什么情况下后手必胜?l示例m=2a1=7a2=3a3=51 2 3 4 5 6 7l将P1P2P3 Pn 对m+1求余得到P1 P2 P3 Pn ，然后符合定理一的结果，记S=P1 XOR P2 XOR P3 XOR XOR Pn 。若S=0则为P局面，否则为N

3、局面。证明：l将P1P2P3 Pn分解成为两部分P1 P2 P3 Pn 和 R1R2R3 Rn，其中R1R2R3 Rn 都是m+1的倍数。l若对P1 P2 P3 Pn 部分取子，则按NIM方法走步，若对R1R2R3 Rn部分取子，则后手取k颗，先手方取m-k+1颗，先手始终保持不对R1R2R3 Rn部分先取子。l若初始局面为胜局面，P1 P2 P3 Pn 部分NIM方法取子必胜，由于R1R2R3 Rn都为m+1的倍数，因此，按m+1互补的取法，先手一定能取到最后K1的情况，我们令把P1Pn这n个数，转成二进制，然后每位分别相加，每位最后结果mod(K+1)即可。如果每一位结果都是0，则为P局面

4、，否则是N局面l示例 P1P2P3P4=3,5,10,15 ，K=2 3 1 1 5 1 0 1 10 1 0 1 0 15 1 1 1 1 2 2 0 0所以这是N局面。l证明与NIM证明类似。下面我们看看具体的取法。Nimk问题的取石子方法问题的取石子方法l设P1P2P3 Pn 为n堆石子数目。Pi已标记的石子堆，D0i和 D1i分别表示所有已标记的石子堆中第i位为0和1的总数。1.找出加法结果非0的最高位，设为W。2.找出一个二进制第W位为1、而且未标记的石子堆Pi，将Pi标记，并把它的第W位由1改为0。对于Pi的第1到(W-1)位，逐个判断，第j位如果为0则Inc(D0j)，否则Inc

5、(D1j)。3.若更新后的S某一位非0（即Si0），且Si+D0iK，或Si-D1i=0|ng(y)for E如果x的出度为0，那么g(x)=0。（边界条件）SG函数的内涵函数的内涵lg(x)就是x的后继点的SG值中没有出现过的最小值。l这样定义有什么好处呢？我们把一个图的当前状态值图的当前状态值定义为游戏者处在的这个点的SG值。l如果游戏者处在一个点x，g(x)0。那么0,1,g(x)-1这些数必然都出现在x的后继节点的SG值中，而游戏者可以走到这些点中的任意一个。也就是说：游戏者可以通过一步走棋把图的当前状态值图的当前状态值任意的减小（当然必须保证状态值始终=0）。l如果游戏者处在一个点x

6、，g(x)=0。那么游戏者无论如何游戏者无论如何移动，下一个点的移动，下一个点的SG值都不等于值都不等于0。SG函数性质函数性质l对于一个图游戏，如果图的当前状态图的当前状态等于0，那么先手必败，否则必胜。l证明：l如果当前点SG=0，先手无论怎么走，都会到达一个SG0的点；接着后手就能设法到达一个SG=0的点。也就是说后手总是能移动，而先手总是处在SG=0的点。游戏不能无限的进行下去，一旦先手到达一个出度等于0的点，游戏结束，先手败。l如果当前点SG0，先手可以走到一个SG=0的点，这样后手面对一个必败状态，所以先手必胜。SG函数在多图游戏中的应用函数在多图游戏中的应用l多图游戏多图游戏 有

7、多个图，每个图都有一个当前节点。两个游戏者轮流行动。每个人每次可以把某一个某一个图中的当前节点沿着该点连出的有向边移动到另一个点。无法移动的那个人输。结论:设这些图的当前状态值分别是a1,a2,ak，如果：a1 a2 ak=0，那么先手必败，否则必胜。证明：请回忆SG函数的性质：如果当前某图的状态值0，那么游戏者可以通过一步走棋把图的当前状态值图的当前状态值任意的减小。因此一个状态值为x的图等价于Nim Game中规模为x的一堆石子！l如果a1 a2 ak=0，先手无论怎么走都会令a1 a2 ak 0。（ai是ai变化后的值）l如果a1 a2 ak 0，那么就完全等价于Nim Game，先手可

8、以按照Nim Game的走法行动，使得a1 a2 ak=0。l证毕。lSG的妙处就是把多图游戏转化成了的妙处就是把多图游戏转化成了Nim Game。保龄球问题保龄球问题l在一行中有n个木瓶，你和你的朋友轮流用保龄球去打这些木瓶，由于你们都是高手，每一次都可以准确的击倒一个或相邻的两个木瓶，谁击倒最后一个剩余的木瓶谁将获得胜利。如果由你先打，请你分析，你应该采取什么策略来确保赢得胜利。分析分析为了更方便的看清楚问题的本质，我们用另一种方式来描述这个游戏。l最开始有一堆石子（n个），每一次你可以进行以下四种操作中的一种：l从中取出一颗石子l从中取出两颗石子l从一堆中取出一颗石子，并且将这一堆中余下

9、的石子任意分成两堆（每堆至少一颗）l从一堆中取出两颗石子，并且将这一堆中余下的石子任意分成两堆（每堆至少一颗）这四种操作，实际上就依次对应于原来游戏中的以下四种击倒法：l击倒一段连续的木瓶中最靠边的一个l击倒一段连续的木瓶中最靠边的连续两个l击倒一段连续的木瓶中不靠边的一个l击倒一段连续的木瓶中不靠边的连续两个求解求解l把局面看作顶点,游戏规则看作边,这是一个典型的图游戏。l如果当前局面被分成了M堆，(A1，A2，Am)，则SG(A1,A2,Am)=SG(A1)SG(A2)SG(Am)显然,SG(0)=0l剩余一个时，只能取到0个，而SG(0)=0，所以SG(1)=1。l剩余两个时，可以取到0

10、或1，其中SG(0)=0，SG(1)=1，所以SG(2)=2l剩余三个时，我们可以把局面变成1或2或两堆均为1。l其中SG(1)=1，SG(2)=2，SG(1，1)=SG(1)SG(1)=0，所以SG(3)=3lSG(4)可分解为SG(2),SG(3),SG(2)SG(1),SG(1)SG(1)=2,3,3,0,所以SG(4)=1l对于任意一种局面P，的SG值为SG(P)，为了赢得胜利，我们只需将他的局面变成Q,使得SG(Q)=0即可。优化优化l对于每一个N值，我们为了求出他的SG值,时间复杂度为O(N)，如果只要求你求出你第一步应该如何行动，那么这种普通的方法需要O(N2)的复杂度，显然不能

11、令我们满意。l这个问题看似已经解决，但我们可以进行优化。l事实上，我们通过观察较小的数的SG值，可以发现：0 11的SG值为：0 1 2 3 1 4 3 2 1 4 2 61223的SG值为：4 1 2 7 1 4 3 2 1 4 6 72435的SG值为：4 1 2 8 5 4 7 2 1 8 6 73647的SG值为：4 1 2 3 1 4 7 2 1 8 2 74859的SG值为：4 1 2 8 1 4 7 2 1 4 2 76071的SG值为：4 1 2 8 1 4 7 2 1 8 6 77283的SG值为：4 1 2 8 1 4 7 2 1 8 2 7并且从72开始，SG值以12为循

12、环节，不断的重复出现，这样我们求出所有SG值的复杂度就降到了常数，这样判断第一步的如何选择的复杂度就降为了O(N)。Strips(poi2000)lStripes is a two player game.Necessary requisites are a board and rectangular stripes in three colours:red,green and blue.All the red stripes have dimensions c x 1,green-z x 1,and blue-n x 1,where c,z and n are integers.Player

13、s have at their disposal an unlimited pool of stripes of each colour.lA game board is a rectangle of dimensions p x 1 and consists of p fields of size 1 x 1.Players make their moves by turns.Move consists of laying a stripe of any colour on the board.There are the following rules in force:lA stripe

14、cannot stick out of the board,lThe covering(even partially)the earlier laid stripes is forbidden.lThe ends of a stripe have to adhere to the edges of the fields on the board.The player,who is not able to perform his move in accordance to the game rules first,loses.lThe first player is this one,who m

15、akes the first move in the game.It is said,that the first player has a winning strategy,if independently of the moves of the second player he can always win.lTasklWrite a program,which:lreads sizes of stripes and of at least one board from the text file PAS.IN for each board determines,whether the f

16、irst player has a winning strategy,writes the results to the text file PAS.OUT.InputThe first line of the input file PAS.IN consists of three integers c,z and n,1=c,z,n=1000,equal to the lengths of stripes,adequately:red,green and blue ones.Numbers in the line are separated by single spaces.The seco

17、nd line of the file PAS.IN consists of one number m,1=m=1000,which is equal to the number of different boards to consider.Lines from the 3-rd to the(m+2)-th consists of one number p,1=p=0）和一个任意的数 y,x y=x*yx x=3*x/2 原问题分析原问题分析l对于判断翻硬币游戏的胜负情况，关键就是计算给定状态的g函数值。l对于每一个翻硬币游戏状态，我们都可以分解成若干个子状态的加和，例如：（T表示反面朝上

18、，H表示正面朝上）g(HTTHH)=g(H)g(TTTH)g(TTTTH)l我们先来考虑原问题的一维情况：n个硬币排成一行，每次可以取一个正面朝上的硬币，和它左边的任一枚硬币，将它们翻转。两个人轮流操作，不能操作者输。由于每一个状态可以分解成只有一个反面朝上的子状态，则我们只要考虑这种情况的g()函数。则我们设H左边有n个T的状态 g(TTH)=g(n)n个根据g(x)的定义，我们可以得出：g(n)=nl回到二维情况:根据游戏论理论，对于g(x,y)表示在(x,y)格中有唯一H的状态的g()函数值（坐标从0开始）则 g(x,y)=g(x)g(y)这样，我们只需要计算每一个二维状态的正面朝上的所

19、有位置的g(x,y)的值，再用异或操作加和起来，就得到了给定状态的g函数值。原问题得到解决。棋盘游戏棋盘游戏 l一个n*m的棋盘，两个人轮流走。每次可以选一个格子，把这个格子及其右下方的所有格子全部拿走。l比如右图5*5的棋盘，某一个人选X，就可以把红色的格子全部拿走。l左上角的格子(1,1)是不能选的。l如果某个游戏者不能走了就输。l问：对于一个n*m的棋盘先手有没有必胜策略？分析分析l首先明确一点：如果把一个状态看作一个点，给可以到达的状态之间连有向边，那么问题就转成了：一个有向图，从指定的点开始，游戏参与双方轮流沿着边走，不能走的输。这是个有向无环图，所以每个状态不是先手必胜就是先手必败

20、。l先手可以这么走：(下面这个状态称为A状态)分析分析l如果A是一个先手必败状态，那么原棋盘就是一个先手必胜状态。l否则如果A是一个先手必胜状态，那么必然可以通过拿掉某个格子变成先手必败状态。不妨设这个状态是B：l我们发现，在一开始游戏的时候，先手可以直接达到B状态；而B是必败状态，所以原棋盘还是必胜状态。l也就是说无论如何，n*m的棋盘都是先手必胜状态。特别之处是，我们无法给出最优策略是什么。Green game(POI2001)lGreen game is a game for two players,say Ann and Billy.Their task is to shift a p

21、awn on the board.Some fields of the board are green,the rest is white.All of them are numbered by integers from the interval 1.(a+b).The fields with integers from the interval 1.a belong to Ann,the fields with numbers(a+1).(a+b)to Billy.lFor each field there is given a set of successors,containing t

22、he fields one can get to from this field in one move.These sets were chosen in such a way that from the field belonging to Ann one can get in one move to the Billys fields only,and vice versa.All the fields have non-empty sets of successors,thus one can always make a move.lAt the beginning of the ga

23、me we put a pawn on the arbitrarily chosen start field P,then players shift the pawn by turns from their field to any successor of this field(we know it belongs to the opponent).The game is started by an owner of the start field P.The game is finished when the pawn stays for the second time on the s

24、ame field,say the field Q.If in the sequence of moves from the field Q to the field Q taken for the second time,the pawn was put at least once on the green field,Ann wins the game,otherwise Billy wins.We say that Ann has a winning strategy for the given start field P in case when there is such a met

25、hod,which guarantees that she wins the game beginning from this field,no matter what moves Billy makes.lWrite a program which:lreads from the text file GRA.IN the description of the board,computes the set of fields for which Ann has a winning strategy,writes the result in the text file GRA.OUT.lInpu

26、tlIn the first line of the text file GRA.IN there are written two positive integers a,b,separated by a single space,meaning respectively:the number of fields belonging to Ann,the number of fields belonging to Billy.Integers a,b satisfy the condition:1=a+b=3000.In the following a+b lines there are de

27、scriptions of the fields of the board:first,descriptions of fields belonging to Ann,and then,of ones belonging to Billy.The(i+1)-st line,for 1=i=a+b,begins with integers z,k meaning respectively the colour of the field i(0 means white,1-green)and the number of successors of this field.Then k integer

28、s(1=k a+b)are written(still in the same line).They are the numbers denoting the successors of the i-th field.The integers in each line are separated by single spaces.The number of green fields on the board is not greater than 100.The total number of successors of all the fields on the board is not g

29、rater than 30000.lOutputlThe first line of the text file GRA.OUT should contain exactly one integer l,which indicates the number of fields for which Ann has a winning strategy.The following l lines should contain numbers of these fields written in ascending order-each integer should be written in a

30、separate line.分析分析l在整个的游戏过程当中，Ann和Billy都会设法让自己赢得游戏。首先我们必须明确一点：从某一区域出发，如果Ann没有必胜策略，那么Billy显然存在着必胜策略，反之亦然。根据这一特点，设置一个布尔函数y=f(i)，当f(i)=true时表示从编号为的区域开始游戏Ann存在着赢得游戏的必胜策略，当f(i)=false时则表示Billy存在着赢得游戏的必胜策略。l当士兵处于属于Ann的区域的时候，如果这个区域的某一个后继区域能够是Ann必胜的话，Ann肯定会让士兵走向那一个区域，同样当士兵处于属于Billy的区域的时候Billy也会采用相同的策略。那么，可以得

31、到这样一个递推公式：)()(.)()()()(.)()()(2121aixforxforxfaixfandxfandxfifmm构图构图l为了便于思考，将问题简化一下：把a+b个区域看成a+b个节点，节点编号与区域编号对应，如果编号为i的区域是编号为j的区域的后继区域，就从编号为i的节点向编号为j的节点连一条有相弧ij，这样便构成了一个由a+b个节点构成的有向图。l然而在这个有向图中存在着许许多多的环，上面的这一递推式显然存在后效性，是不能够求解的。但是如果某一些区域的f值能够直接求得的话，其它区域的f值就有可能求出来。求求f值值l定义 B集合是一个点集，该集集合是一个点集，该集合当中不存在绿

32、色节点，所有合当中不存在绿色节点，所有的节点构成一个强连通分量，的节点构成一个强连通分量，若编号为若编号为i的节点属于该集合，的节点属于该集合，当时，该节点的所有后继节点当时，该节点的所有后继节点都属于该集合，当时，该节点都属于该集合，当时，该节点至少有一个后继节点属于该集至少有一个后继节点属于该集合。合。表示 Billy 拥有的区域 表示 Ann 拥有的区域 B 集集 合合 lB集合有一个非常重要的性质：一旦士兵走入了某一个集合有一个非常重要的性质：一旦士兵走入了某一个B集合，集合，Billy总总能够使士兵始终处于该集合当中，而能够使士兵始终处于该集合当中，而Ann无法使士兵走出该集合。由于

33、无法使士兵走出该集合。由于B集合当中节点个数是有限的，所以士兵经过的路线上必定会出现一个集合当中节点个数是有限的，所以士兵经过的路线上必定会出现一个没有绿色节点的环。因此只要士兵走进某一个没有绿色节点的环。因此只要士兵走进某一个B集合当中，那么集合当中，那么Billy必必然会赢得比赛的胜利，故所有然会赢得比赛的胜利，故所有B集合当中的节点的集合当中的节点的f值都为值都为False。l接下来，根据上面的递推式能够确定另外一些节点（当且仅当该节点的接下来，根据上面的递推式能够确定另外一些节点（当且仅当该节点的所有后继节点的所有后继节点的f值已经确定了）的值已经确定了）的f值，这些节点的值，这些节点

34、的f值都只可能为值都只可能为False。例如上图那一个例子，图中标有星号的那些节点可以在确定。例如上图那一个例子，图中标有星号的那些节点可以在确定B集合之后确定它们的集合之后确定它们的f值。值。进一步分析进一步分析 表示 Billy 拥有的节点 表示 Ann 拥有的节点 B 集合 l实际上从上图涂有红色的那些节点出发仍然是实际上从上图涂有红色的那些节点出发仍然是Billy获得比赛的胜利，因获得比赛的胜利，因此这些节点的此这些节点的f值也应当为值也应当为False。可按照上面的步骤。可按照上面的步骤f值是不能够确定的，值是不能够确定的，怎样处理这种情况呢？怎样处理这种情况呢？l确定确定B集合的目

35、的是为了使士兵走入这个点集后集合的目的是为了使士兵走入这个点集后Ann不能让他走不出来，不能让他走不出来，从而使从而使Billy获得游戏的胜利，如果获得游戏的胜利，如果Ann可以使士兵走出来，但不过是使士可以使士兵走出来，但不过是使士兵走到了一个使兵走到了一个使Billy必胜的节点，这样在本质上与士兵仍处于必胜的节点，这样在本质上与士兵仍处于B集合是一集合是一样的。样的。l因此可以把所有已经确定了因此可以把所有已经确定了f值的节点删除，那么被涂成红色的节点就成值的节点删除，那么被涂成红色的节点就成为了一个新的为了一个新的B集合。集合。算法框架算法框架while 能够从图中找到B集合 do 寻找

36、所有的B集合并将所有B集合当中的节点的f值置为False；寻找所有可以确定f值的节点，并将它们的置值为False；将已确定f值的节点从图中删除；将剩余的节点的f置值为True.l下面简单的论证一下该算法的正确性。l因为剩余节点当中已经不存在B集合，那么Billy完全无法控制士兵能够到达的节点的范围，那么Ann是一定能够在游戏结束之前使士兵到达一个特定的强连通分量中的某一节点，这个连通分量中任何一个节点的后继节点都处于该连通分量中，因为不存在B集合，那么这一连通分量中必然存在绿色节点，因此Ann可以使士兵在这一个连通分量中走出一个含有绿色节点的环。性能分析l时间复杂度：该算法中寻找B集合和寻找可以确定f值的节点的过程的时间复杂度为，m表示图中有向弧的条数。因此算法的时间复杂度为，k相当于算法框架当中while循环的次数，k的取值与有向图的构型有关，k的上限为(a+b)/2。l空间需求：KBBytesmba300)8)(5(参考资料参考资料博弈论博弈论 中国人民大学出版社 朱弗登博格（法）让梯若尔 博弈与信息：博弈博弈与信息：博弈论概论（第二版）论概论（第二版）Games and Information:An Introduction to Game Theory北京大学出版社美艾里克.拉斯缪森王晖 白金辉 吴任昊人工智能导论人工智能导论 清华大学出版社 林尧瑞 马少平