《算法合集之《由感性认识到理性认识——透析一类搏弈游戏的解答过程》》由会员分享，可在线阅读，更多相关《算法合集之《由感性认识到理性认识——透析一类搏弈游戏的解答过程》（16页珍藏版）》请在金锄头文库上搜索。
1、由感性认识到理性认识透析一类搏弈游戏的解答过程 张一飞- 1 -由感性认识到理性认识 透析一类搏弈游戏的解答过程一、 游戏 .2二、 从简单入手 .2三、 类比与联想 .6四、 证明 .8五、 推广 .11六、 精华 .12七、 结论 .16八、 总结 .17由感性认识到理性认识透析一类搏弈游戏的解答过程 张一飞- 2 -一、 游戏 游戏 A： 甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。例如图1 所示的初始局面：共 n=3 堆，其中第一堆的石子数 a1=3，第二堆石子数a2=3，第三堆石子数 a3=1。两人轮流按下列规则取走一些石子，游戏的规则如下： 每一步应取走至少一枚石子；
2、 每一步只能从某一堆中取走部分或全部石子； 如果谁无法按规则取子，谁就是输家。第一堆：a 1=3 第二堆：a 2=3 第三堆：a 3=1图 1 游戏的一个初始局面 游戏 B： 甲乙双方事先约定一个数 m，并且每次取石子的数目不能超过 m 个； 其余规则同游戏 A。我们关心的是，对于一个初始局面，究竟是先行者（甲）有必胜策略，还是后行者（乙）有必胜策略。下面，我们从简单入手，先来研究研究这个游戏的一些性质。二、 从简单入手 用一个 n 元组(a 1, a2, , an)，来描述游戏过程中的一个局面。 可以用 3 元组(3, 3, 1)来描述图 1 所示的局面。 改变这个 n 元组中数的顺序，仍然
3、代表同一个局面。 (3, 3, 1)和 (1, 3, 3)，可以看作是同一个局面。由感性认识到理性认识透析一类搏弈游戏的解答过程 张一飞- 3 - 如果初始局面只有一堆石子，则甲有必胜策略。 甲可以一次把这一堆石子全部取完，这样乙就无石子可取了。 如果初始局面有两堆石子，而且这两堆石子的数目相等，则乙有必胜策略。 因为有两堆石子，所以甲无法一次取完； 如果甲在一堆中取若干石子，乙便在另一堆中取同样数目的石子； 根据对称性，在甲取了石子之后，乙总有石子可取； 石子总数一直在减少，最后必定是甲无石子可取。 对于初始局面(1)，甲有必胜策略，而初始局面(3, 3)，乙有必胜策略。 局面的加法：(a
4、1, a2, , an) + (b1, b2, , bm) = (a1, a2, , an, b1, b2, , bm)。 (3) + (3) + (1) = (3, 3) + (1) = (3, 3, 1)。 对于局面 A, B, S，若 S=A+B，则称局面 S 可以分解为“子局面”A 和 B。 局面(3, 3, 1)可以分解为(3, 3) 和(1)。 如果初始局面可以分成两个相同的“子局面” ，则乙有必胜策略。 设初始局面 S=A+A，想象有两个桌子，每个桌子上放一个 A 局面； 若甲在一个桌子中取石子，则乙在另一个桌子中对称的取石子； 根据对称性，在甲取了石子之后，乙总有石子可取； 石
5、子总数一直在减少，最后必定是甲无石子可取。 初始局面(2, 2, 5, 5, 5, 5, 7, 7)，可以分成两个(2, 5, 5, 7)，故乙有必胜策略。 对于局面 S，若先行者有必胜策略，则称 “S 胜” 。 对于局面 S，若后行者有必胜策略，则称 “S 负” 。 若 A=(1)，B=(3, 3)，C=(2, 2, 5, 5, 5, 5, 7, 7)，则 A 胜，B 负，C 负。 我们所关心的，就是如何判断局面的胜负。 如果局面 S 胜，则必存在取子的方法 ST ，且 T 负。由感性认识到理性认识透析一类搏弈游戏的解答过程 张一飞- 4 - 如果局面 S 负，则对于任意取子方法 ST ，有
6、 T 胜。 设初始局面 S 可以分解成两个子局面 A 和 B（分解理论） 。 若 A 和 B 一胜一负，则 S 胜。 不妨设 A 胜 B 负； 想象有两个桌子 A 和 B，桌子上分别放着 A 局面和 B 局面； 因为 A 胜，所以甲可以保证取桌子 A 上的最后一个石子； 与此同时，甲还可以保证在桌子 B 中走第一步的是乙； 因为 B 负，所以甲还可以保证取桌子 B 中的最后一个石子； 综上所述，甲可以保证两个桌子上的最后一个石子都由自己取得。 若 A 负 B 负，则 S 负。 无论甲先从 A 中取，还是先从 B 中取，都会变成一胜一负的局面； 因此，乙面临的局面总是“胜”局面，故甲面临的 S
7、是“负”局面。 若 B 负，则 S 的胜负情况与 A 的胜负情况相同。 若 A 胜 B 胜，则有时 S 胜，有时 S 负。 如果 S=A+C+C，则 S 的胜负情况与 A 相同。 令 B=C+C，则 S=A+B 且 B 负，故 S 的胜负情况与 A 相同。 图 1 所示的初始局面(3, 3, 1) = (3) + (3) + (1)，与局面(1)的胜负情况相同。 图 1 中所示的初始局面(3, 3, 1)是“胜”局面，甲有必胜策略。 称一个石子也没有的局面为“空局面” 。 空局面是“负”局面。 如果局面 S 中，存在两堆石子，它们的数目相等。用 T 表示从 S 中把这两堆石子拿掉之后的局面，则
8、称“S 可以简化为 T”。 局面(2, 2, 2, 7, 9, 9)可以简化为(2, 2, 2, 7) ，还可以进一步简化为(2, 7)。由感性认识到理性认识透析一类搏弈游戏的解答过程 张一飞- 5 - 一个局面的胜负情况，与其简化后的局面相同。 三个局面(2, 2, 2, 7, 9, 9)、(2, 2, 2, 7) 和(2, 7)，胜负情况都相同。 不能简化的局面称为“最简局面” 。 局面 (2, 7)是最简局面。 最简局面中不会有两堆相同的石子，故可以用一个集合来表示最简局面。 最简局面(2, 7) 可以用集合2, 7来表示。 如果只关心局面的胜负，则一个局面可以用一个集合来描述。 图 1
9、 所示的局面(3, 3, 1)，可以用集合1 来描述。如果用搜索（搏弈树）的方法来解这个游戏，则采用集合来表示一个局面，比采用多元组来表示一个局面，搜索量将有所减少，但时间复杂度仍然很高。能不能进一步简化一个局面的表示呢？三、 类比与联想 二进制加法 1 1 + 0 = 1； 0 + 1 = 1； 0 + 0 = 0； 1 + 1 = 0。 二进制的加法 VS 局面的加法 大写字母 AB 表示局面，小写字母 ab 表示二进制 若 A 和 B 相同，则 A+B 负；若 a 和 b 相等，则 a+b=0 若 A 胜 B 负，则 A+B 胜；若 a=1 且 b=0，则 a+b=1 若 B 胜 A 负
10、，则 A+B 胜；若 b=1 且 a=0，则 a+b=11 本文的“二进制加法” ，是指不进位的二进制加法，也可以理解为逻辑里的“异或”操作。由感性认识到理性认识透析一类搏弈游戏的解答过程 张一飞- 6 - 若 A 负 B 负，则 A+B 负；若 a=0 且 b=0，则 a+b=0 如果用二进制 1 和 0，分别表示一个局面的胜或负 局面的加法，与二进制的加法有很多类似之处。 若 A 胜 B 胜，则 A+B 有时胜，有时负；若 a=1 且 b=1，则 a+b=0。 二进制数的加法：对二进制数的每一位，都采用二进制的加法。 ， 。0011+ 101010011010+ 10100000 二进制数
11、的加法 VS 局面的加法 大写字母 AB 表示局面，小写字母 ab 表示二进制数 若 A 和 B 相同，则 A+B 负；若 a 和 b 相等，则 a+b 为 0 若 A 胜 B 负，则 A+B 胜；若 a0 且 b=0，则 a+b0 若 B 胜 A 负，则 A+B 胜；若 b0 且 a=0，则 a+b0 若 A 负 B 负，则 A+B 负；若 a=0 且 b=0，则 a+b=0 若 A 胜 B 胜，则 A+B 有时胜，有时负 若 a0 且 b0，则有时 a+b0，有时 a+b=0 如果用二进制数 s 来表示一个局面 S 的胜或负，S 胜则 s0，S 负则 s=0 局面的加法，与二进制数的加法，
12、性质完全相同。 能否用一个二进制数，来表示一个局面呢？ 用符号#S ，表示局面 S 所对应的二进制数。 如果局面 S 只有一堆石子，则用这一堆石子数目所对应的二进制数来表示由感性认识到理性认识透析一类搏弈游戏的解答过程 张一飞- 7 -S。 #(5)=5=101。 若局面 S=A+B，则#S=#A+#B。 局面(3, 3)=(3)+(3)，所以#(3, 3)=#(3)+#(3)=11+11=0。 局面(3, 3, 1)=(3, 3)+(1)，所以#(3, 3, 1)=#(3, 3)+#(1)=0+1=1。 函数 f：若局面 S 只有一堆石子，设 S=a1，则 f(a1)=#S，即 f(a1)=
13、#(a1)。 对于游戏 A 来说，#(5)=101，所以 f(5)=101。 对于游戏 A 来说，f(x)就是 x 所对应的二进制数。换句话说，f(x)=x。 设局面 S=(a1, a2, , an)，即 S=(a1)+(a2)+(an)，则#S=f(a 1)+f(a2)+f(an)。 #(3, 3, 1)=#(3)+(3)+(1)=#(3)+#(3)+#(1)=f(3)+f(3)+f(1)=11+11+1=1。 对于局面 S，若#S=0，则 S 负；若#S0，则 S 胜。四、 证明 二进制数 a, b，若 a + b = 0，当且仅当 a = b。1011+ 101100001011+ 10010010 二进制数 a, b, s，若 a + b = s，则 a = b + s。0011+ 101010011001+ 10100011由感性认识到理性认识透析一类搏弈游戏的解答过程 张一飞- 8 - 二进制数 a1+a2+an=p0，则必存在 k，使得 ak+p0f(a 1)f(a 1x)f(a 1)
