由感性认识到理性认识.DOC

1、- 1 -由感性认识到理性认识透析一类搏弈游戏的解答过程一、 游戏 .2二、 从简单入手 .2三、 类比与联想 .6四、 证明 .8五、 推广 .11六、 精华 .12七、 结论 .16八、 总结 .17- 2 -一、 游戏 游戏 A： 甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。例如图1 所示的初始局面：共 n=3 堆，其中第一堆的石子数 a1=3，第二堆石子数a2=3，第三堆石子数 a3=1。两人轮流按下列规则取走一些石子，游戏的规则如下： 每一步应取走至少一枚石子； 每一步只能从某一堆中取走部分或全部石子； 如果谁无法按规则取子，谁就是输家。第一堆：a 1=3 第二堆：a

2、2=3 第三堆：a 3=1图 1 游戏的一个初始局面 游戏 B： 甲乙双方事先约定一个数 m，并且每次取石子的数目不能超过 m 个； 其余规则同游戏 A。我们关心的是，对于一个初始局面，究竟是先行者（甲）有必胜策略，还是后行者（乙）有必胜策略。下面，我们从简单入手，先来研究研究这个游戏的一些性质。二、 从简单入手 用一个 n 元组(a 1, a2, , an)，来描述游戏过程中的一个局面。 可以用 3 元组(3, 3, 1)来描述图 1 所示的局面。 改变这个 n 元组中数的顺序，仍然代表同一个局面。 (3, 3, 1)和 (1, 3, 3)，可以看作是同一个局面。- 3 - 如果初始局面只有

3、一堆石子，则甲有必胜策略。 甲可以一次把这一堆石子全部取完，这样乙就无石子可取了。 如果初始局面有两堆石子，而且这两堆石子的数目相等，则乙有必胜策略。 因为有两堆石子，所以甲无法一次取完； 如果甲在一堆中取若干石子，乙便在另一堆中取同样数目的石子； 根据对称性，在甲取了石子之后，乙总有石子可取； 石子总数一直在减少，最后必定是甲无石子可取。 对于初始局面(1)，甲有必胜策略，而初始局面(3, 3)，乙有必胜策略。 局面的加法：(a 1, a2, , an) + (b1, b2, , bm) = (a1, a2, , an, b1, b2, , bm)。 (3) + (3) + (1) = (3

4、, 3) + (1) = (3, 3, 1)。 对于局面 A, B, S，若 S=A+B，则称局面 S 可以分解为“子局面”A 和 B。 局面(3, 3, 1)可以分解为(3, 3) 和(1)。 如果初始局面可以分成两个相同的“子局面” ，则乙有必胜策略。 设初始局面 S=A+A，想象有两个桌子，每个桌子上放一个 A 局面； 若甲在一个桌子中取石子，则乙在另一个桌子中对称的取石子； 根据对称性，在甲取了石子之后，乙总有石子可取； 石子总数一直在减少，最后必定是甲无石子可取。 初始局面(2, 2, 5, 5, 5, 5, 7, 7)，可以分成两个(2, 5, 5, 7)，故乙有必胜策略。 对于局

5、面 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 ，有 T 胜。 设初始局面 S 可以分解成两个子局面 A 和 B（分解理论） 。 若 A 和 B 一胜一负，则 S 胜。 不妨设 A 胜 B 负； 想象有两个桌子 A 和 B，桌子上分别放着 A 局面和 B 局面； 因为

6、A 胜，所以甲可以保证取桌子 A 上的最后一个石子； 与此同时，甲还可以保证在桌子 B 中走第一步的是乙； 因为 B 负，所以甲还可以保证取桌子 B 中的最后一个石子； 综上所述，甲可以保证两个桌子上的最后一个石子都由自己取得。 若 A 负 B 负，则 S 负。 无论甲先从 A 中取，还是先从 B 中取，都会变成一胜一负的局面； 因此，乙面临的局面总是“胜”局面，故甲面临的 S 是“负”局面。 若 B 负，则 S 的胜负情况与 A 的胜负情况相同。 若 A 胜 B 胜，则有时 S 胜，有时 S 负。 如果 S=A+C+C，则 S 的胜负情况与 A 相同。 令 B=C+C，则 S=A+B 且 B

7、 负，故 S 的胜负情况与 A 相同。 图 1 所示的初始局面(3, 3, 1) = (3) + (3) + (1)，与局面(1)的胜负情况相同。 图 1 中所示的初始局面(3, 3, 1)是“胜”局面，甲有必胜策略。 称一个石子也没有的局面为“空局面” 。 空局面是“负”局面。 如果局面 S 中，存在两堆石子，它们的数目相等。用 T 表示从 S 中把这两堆石子拿掉之后的局面，则称“S 可以简化为 T”。 局面(2, 2, 2, 7, 9, 9)可以简化为(2, 2, 2, 7) ，还可以进一步简化为(2, 7)。- 5 - 一个局面的胜负情况，与其简化后的局面相同。 三个局面(2, 2, 2

8、, 7, 9, 9)、(2, 2, 2, 7) 和(2, 7)，胜负情况都相同。 不能简化的局面称为“最简局面” 。 局面 (2, 7)是最简局面。 最简局面中不会有两堆相同的石子，故可以用一个集合来表示最简局面。 最简局面(2, 7) 可以用集合2, 7来表示。 如果只关心局面的胜负，则一个局面可以用一个集合来描述。 图 1 所示的局面(3, 3, 1)，可以用集合1 来描述。如果用搜索（搏弈树）的方法来解这个游戏，则采用集合来表示一个局面，比采用多元组来表示一个局面，搜索量将有所减少，但时间复杂度仍然很高。能不能进一步简化一个局面的表示呢？三、 类比与联想 二进制加法 1 1 + 0 =

9、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 负，则 A+B 胜；若 b=1 且 a=0，则 a+b=11 本文的“二进制加法” ，是指不进位的二进制加法，也可以理解为逻辑里的“异或”操作。- 6 - 若 A 负 B 负，则 A+B 负；若 a=0 且 b=0，则 a+b=0 如果用二进制 1 和 0，分别表示一个局面

10、的胜或负 局面的加法，与二进制的加法有很多类似之处。 若 A 胜 B 胜，则 A+B 有时胜，有时负；若 a=1 且 b=1，则 a+b=0。 二进制数的加法：对二进制数的每一位，都采用二进制的加法。 ， 。0011+ 101010011010+ 10100000 二进制数的加法 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 负，

11、则 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 局面的加法，与二进制数的加法，性质完全相同。 能否用一个二进制数，来表示一个局面呢？ 用符号#S ，表示局面 S 所对应的二进制数。 如果局面 S 只有一堆石子，则用这一堆石子数目所对应的二进制数来表示- 7 -S。 #(5)=5=101。 若局面 S=A+B，则#S=#A+#B。 局面(3, 3)=(3)+(3)，所以#(3, 3)=#(3)+#(3)

12、=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)=#(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(

13、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)+f(a1x)0#T 0。00101 a110011 a210111 a3+ 00001 a400000 p=000101

14、 a100101 a2+a3+a4=a1+00000 p=0xa 1a1+p0 若#S0，则先行者必然存在一种取子方法 ST，且#T=0。 设 S=(a1, a2, , an)，p=#S=f(a 1)+f(a2)+f(an)；- 9 - 因为 p0，所以必然存在 k，使得 f(ak)+pf(ak)，不妨设 k=1，f(a 1)+p=x； 先行者将第 1 堆的石子的数目从 a1 变成 x，用 T 表示这个局面； p=#S=f(a1)+#(a2, , an)，故#(a 2, , an)=f(a1)+p=x； #T=f(x)+#(a2, , an)=f(x)+x=0。00101 a110011 a2

15、00111 a3+ 10111 a400110 p000101 a100011 x=a2+a3+a4=a1+pa1+00110 pxx+p=0 若 S 是空局面，则 #S=0。 若#S=0，则 S 负；若#S0，则 S 胜。 #(1, 2, 3)=01+10+11=0，故局面(1, 2, 3)负。 #(1, 2, 3, 4)=001+010+011+100=100，故局面(1, 2, 3, 4)胜。对于游戏 A 来说，任意的一个初始局面 S=(a1, a2, , an)，我们把这里的 ai都看成是二进制数。令#S=a 1+a2+an。若#S0，则先行者（甲）有必胜策略；否则#S=0 ，这时后行

16、者（乙）有必胜策略。下面把这个结论推广到游戏 B。 函数 f：f(x)=x mod (m+1)；把函数 f 的值看作是二进制数。 对于任意初始局面 S=(a1, a2, , an)，令#S=f(a 1)+f(a2)+f(an)。 若#S0，则先行者（甲）有必胜策略；否则后行者（乙）有必胜策略。 类似游戏 A 的证明。 游戏 B 的解法与游戏 A 十分类似。这是因为两个游戏的规则相当类似。- 10 -五、 推广 游戏 C： 甲乙两人面对若干排石子，其中每一排石子的数目可以任意确定。例如图2 所示的初始局面：共 n=3 排，其中第一排的石子数 a1=7，第二排石子数a2=3，第三排石子数 a3=3

17、。两人轮流按下列规则取走一些石子，游戏的规则如下： 每一步必须从某一排中取走两枚石子； 这两枚石子必须是紧紧挨着的； 如果谁无法按规则取子，谁就是输家。第一排，a1=7第二排，a2=3第三排，a3=31 2 3 4 5 6 7图 2 游戏的一个初始局面 如果甲第一步选择取第一排 34 这两枚石子，之后无论是甲还是乙，都不能一次取走 25 这两枚石子。换句话说，如果取了 34 这两枚石子，等价于将第一排分成了两排，这两排分别有 2 个和 3 个石子。我们只关心，对于一个初始局面，究竟是先行者（甲）有必胜策略，还是后行者（乙）有必胜策略。游戏 C 的规则和游戏 A 并不那么相似。但是，前面所列出的，游戏 A 的关键性质，游戏 C 却都具有。比如说，图 2 所示的初始局面可以用三元组(7, 3, 3)来表示，它的胜负情况与初始局面(7)相同。游戏 A 的解答是由它的性质得出来的。因此，我们猜想游戏 C 是否也能用类似的方法来解。