《游戏策略讲义.ppt》由会员分享，可在线阅读，更多相关《游戏策略讲义.ppt（40页珍藏版）》请在金锄头文库上搜索。
1、游戏策略,朱全民,Nim问题,取石子问题 有N堆石子，其中第i堆有Pi颗石子，每次从某一堆里选出若干石子去掉（但不能不去石子），两人轮流取石，谁不能继续取谁就输了。 什么情况下先手必胜，什么情况下后手必胜?,分析,从上述博弈树可以看出3,3,1是必胜点，那么我们可以这么想，如果某个点是必胜点，则取完棋子后，必须使得对方落在必败点。 若只有一堆石子，先收走必胜 若有m堆石子，每堆只有一颗石子， m堆为奇数时，先手必胜。 若有m堆石子，每堆有k颗石子， m堆为奇数时，先手必胜。 第1次，先手取k棵，轮到对手走时，若对手取k棵，则先手也取k棵，若对手取xk棵，则先手也取另外一堆的x棵，因为剩下的是偶
2、数堆，总能将剩下的堆变成若干个两两相等的堆。只要始终保持这种取法，先手总能取到最后的石子。,一般情况？,假设某个初始局面为先手必胜,那么先手每走一步都必须使得对手落在必败节点。 因此，对于每一个局面，要么为胜局面，要么为负局面，如果我们将胜局面非0表示，那么负局面就可以用0表示。 因此，对于某一个局面，若为非0局面，它的任务就是要寻找某一种取法，使得局面变为0局面。那么他的对手无论怎么取，都会使得局面又变成0局面。 有什么规律呢？,结论,定理： 如果一个局面先手必胜，就称之为N局面，反之称之为P局面。对于一个局面，令S=P1 XOR P2 XOR P3 XOR XOR Pn。若S=0则为P局面
3、，否则为N局面。 证明： 当P1=P2=.=Pn=0时，S=0，满足终状态是P局面。 若S=0，即P1 XOR XOR Pn=0，若取堆i中的石子，PiPi，S -S，PiPi，则Pi XOR Pi0。所以S XOR Pi XOR Pi=S=0，即S=Pi XOR Pi0。满足P局面的所有子局面都是N局面。 若S0，设S的二进制位是A1An，考虑第一位是1的。在P中取出该位同是1的，不妨设为P1。可知P1 XOR SP1，令P1=P1 XOR S。可知P1 XOR P2 XOR XOR Pn=0。即N局面存在至少一个子局面是P局面。,示例,Nim问题的扩展,取石子问题 有N堆石子，其中第i堆有
4、Pi颗石子，每次去掉某一堆里最多m棵石子（m0），两人轮流取石，谁不能继续取谁就输了。 什么情况下先手必胜，什么情况下后手必胜? 示例m=2,将P1P2P3 Pn 对m+1求余得到P1 P2 P3 Pn ，然后符合定理一的结果，记S=P1 XOR P2 XOR P3 XOR XOR Pn 。若S=0则为P局面，否则为N局面。 证明： 将P1P2P3 Pn分解成为两部分P1 P2 P3 Pn 和 R1R2R3 Rn，其中R1R2R3 Rn 都是m+1的倍数。 若对P1 P2 P3 Pn 部分取子，则按NIM方法走步，若对R1R2R3 Rn部分取子，则后手取k颗，先手方取m-k+1颗，先手始终保持
5、不对R1R2R3 Rn部分先取子。 若初始局面为胜局面，P1 P2 P3 Pn 部分NIM方法取子必胜，由于R1R2R3 Rn都为m+1的倍数，因此，按m+1互补的取法，先手一定能取到最后K=m颗石子。,结论,Nimk问题,取石子问题 有N堆石子，其中第i堆有Pi颗石子，每次可以从最多K堆中选出若干石子去掉（但不能不去石子），两人轮流取石，谁不能继续取谁就输了。 什么情况下先手必胜，什么情况下后手必胜?,结论,K=1，为Nim问题。 对于K1的情况，我们令把P1Pn这n个数，转成二进制，然后每位分别相加，每位最后结果mod (K+1)即可。如果每一位结果都是0，则为P局面，否则是N局面 示例
6、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局面。 证明与NIM证明类似。下面我们看看具体的取法。,Nimk问题的取石子方法,设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(D1j)。 3. 若更
7、新后的S某一位非0（即Si0），且Si+D0iK，或Si-D1i1，可以通过修改以前已标记的石子堆将Si修正为0。 4. 如果加法结果已经全部为0，则确认所有已经做的更改，并结束；否则转到1。,MisreNim问题,取石子问题 有N堆石子，每次从某一堆里选出若干石子去掉（但不能不去石子），两人轮流取石，谁不能继续取谁就赢了。 什么情况下先手必胜，什么情况下后手必胜?,结论,所有石子堆的数目都为1：显然，若有偶数堆石子堆，则必胜，否则必败。 如果恰好只有一堆石子数目大于1。我们可以把这堆石子取完或者取得只剩下1，使得只剩下奇数堆数目为1的石子留给对方，由1)，必胜。 如果有至少2堆石子的数目大于
8、1。 考虑异或值：若异或值不为0，则按照Nim走法取石。这样，当对手某次取完石子后，肯定会出现情况2，必胜。 证明：按照Nim走法则取完石子后，必定会给对手留下异或值为0的局面。因此不可能给对手留下情况2 的局面（容易证明，情况2 局面的异或值肯定不为0），而对手一次最多将一堆石子数大于1的石子堆处理掉。因此情况2 的情况肯定会出现。 相反，若异或值为0，则无论如何走都会给对方留下情况2 或情况3的情况，必败。,SG函数简介,如果我们把游戏中的某一个局面看作一个顶点，把局面之间的转换用边来表示，那么很多游戏都可以转化成图游戏模型。 图游戏模型 给定有向无环图G=(V,E)和一个起始点，双方轮流
9、行动。每个人每次可以从当前点出发沿着一条有向边走到另外一个点。谁无法走了谁就输。 一些图游戏可以通过Sprague-Grundy函数来判定先手的胜负情况（简称SG函数）。 SG函数 一个图G=(V,E)的SG函数g，是定义在v上的一个非负整数函数： g(x)=minn=0 | ng(y) for E 如果x的出度为0，那么g(x)=0。（边界条件）,SG函数的内涵,g(x)就是x的后继点的SG值中没有出现过的最小值。 这样定义有什么好处呢？我们把一个图的当前状态值定义为游戏者处在的这个点的SG值。 如果游戏者处在一个点x，g(x)0。那么0, 1, , g(x)-1这些数必然都出现在x的后继节
10、点的SG值中，而游戏者可以走到这些点中的任意一个。也就是说：游戏者可以通过一步走棋把图的当前状态值任意的减小（当然必须保证状态值始终=0）。 如果游戏者处在一个点x，g(x)=0。那么游戏者无论如何移动，下一个点的SG值都不等于0。,SG函数性质,对于一个图游戏，如果图的当前状态等于0，那么先手必败，否则必胜。 证明： 如果当前点SG=0，先手无论怎么走，都会到达一个SG0的点；接着后手就能设法到达一个SG=0的点。也就是说后手总是能移动，而先手总是处在SG=0的点。游戏不能无限的进行下去，一旦先手到达一个出度等于0的点，游戏结束，先手败。 如果当前点SG0，先手可以走到一个SG=0的点，这样
11、后手面对一个必败状态，所以先手必胜。,SG函数在多图游戏中的应用,多图游戏 有多个图，每个图都有一个当前节点。两个游戏者轮流行动。每个人每次可以把某一个图中的当前节点沿着该点连出的有向边移动到另一个点。无法移动的那个人输。 结论: 设这些图的当前状态值分别是a1, a2, , ak，如果：a1 a2 ak = 0，那么先手必败，否则必胜。 证明： 请回忆SG函数的性质：如果当前某图的状态值0，那么游戏者可以通过一步走棋把图的当前状态值任意的减小。因此一个状态值为x的图等价于Nim Game中规模为x的一堆石子！ 如果a1 a2 ak = 0，先手无论怎么走都会令a1 a2 ak 0。（ai是a
12、i变化后的值） 如果a1 a2 ak 0，那么就完全等价于Nim Game，先手可以按照Nim Game的走法行动，使得a1 a2 ak = 0。 证毕。 SG的妙处就是把多图游戏转化成了Nim Game。,保龄球问题,在一行中有n个木瓶，你和你的朋友轮流用保龄球去打这些木瓶，由于你们都是高手，每一次都可以准确的击倒一个或相邻的两个木瓶，谁击倒最后一个剩余的木瓶谁将获得胜利。如果由你先打，请你分析，你应该采取什么策略来确保赢得胜利。,分析,为了更方便的看清楚问题的本质，我们用另一种方式来描述这个游戏。 最开始有一堆石子（n个），每一次你可以进行以下四种操作中的一种： 从中取出一颗石子 从中取出
13、两颗石子 从一堆中取出一颗石子，并且将这一堆中余下的石子任意分成两堆（每堆至少一颗） 从一堆中取出两颗石子，并且将这一堆中余下的石子任意分成两堆（每堆至少一颗） 这四种操作，实际上就依次对应于原来游戏中的以下四种击倒法： 击倒一段连续的木瓶中最靠边的一个 击倒一段连续的木瓶中最靠边的连续两个 击倒一段连续的木瓶中不靠边的一个 击倒一段连续的木瓶中不靠边的连续两个,求解,把局面看作顶点,游戏规则看作边,这是一个典型的图游戏。 如果当前局面被分成了M堆，(A1，A2，Am)，则 SG(A1,A2,Am)=SG(A1)SG(A2)SG(Am) 显然, SG(0)=0 剩余一个时，只能取到0个，而SG
14、(0)=0，所以SG(1)=1。 剩余两个时，可以取到0或1，其中SG(0)=0，SG(1)=1， 所以SG(2)=2 剩余三个时，我们可以把局面变成1或2或两堆均为1。 其中SG(1)=1，SG(2)=2，SG(1，1)=SG(1) SG(1)=0，所以SG(3)=3 SG(4)可分解为SG(2), SG(3),SG(2)SG(1), SG(1)SG(1) =2,3,3,0,所以SG(4)=1 对于任意一种局面P，的SG值为SG(P)，为了赢得胜利，我们只需将他的局面变成Q,使得SG(Q)=0即可。,优化,对于每一个N值，我们为了求出他的SG值, 时间复杂度为O(N) ，如果只要求你求出你第
15、一步应该如何行动，那么这种普通的方法需要O(N2)的复杂度，显然不能令我们满意。 这个问题看似已经解决，但我们可以进行优化。 事实上，我们通过观察较小的数的SG值，可以发现： 0 11的SG值为：0 1 2 3 1 4 3 2 1 4 2 6 1223的SG值为：4 1 2 7 1 4 3 2 1 4 6 7 2435的SG值为：4 1 2 8 5 4 7 2 1 8 6 7 3647的SG值为：4 1 2 3 1 4 7 2 1 8 2 7 4859的SG值为：4 1 2 8 1 4 7 2 1 4 2 7 6071的SG值为：4 1 2 8 1 4 7 2 1 8 6 7 7283的SG值为：4 1 2 8 1 4 7 2 1 8 2 7 并且从72开始，SG值以12为循环节，不断的重复出现，这样我们求出所有SG值的复杂度就降到了常数，这样判断第一步的如何选择的复杂度就降为了O(N)。,Strips(poi2000),Stripes is a two player game. Necessary requisites are a board and rectangular stripes in three colours: red, green and blue. All the red stripes ha
