算法合集之《由感性認识到理性认识透析一类搏弈游戏的解答过程》.docVIP

由感性认识到理性认识——透析一类搏弈游戏的解答过程 一、 游戏 2 二、 从简单入手 2 三、 类比与联想 6 四、 证明 8 五、 推广 11 六、 精华 12 七、 结论 16 八、 总结 17 游戏 游戏A： 甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。例如图1所示的初始局面：共n=3堆，其中第一堆的石子数a1=3，第二堆石子数a2=3，第三堆石子数a3=1。两人轮流按下列规则取走一些石子，游戏的规则如下： 每一步应取走至少一枚石子； 每一步只能从某一堆中取走部分或全部石子； 如果谁无法按规则取子，谁就是输家。 图 1 游戏的一个初始局面 游戏B： 甲乙双方事先约定一个数m，并且每次取石子的数目不能超过m个； 其余规则同游戏A。 我们关心的是，对于一个初始局面，究竟是先行者（甲）有必胜策略，还是后行者（乙）有必胜策略。 下面，我们从简单入手，先来研究研究这个游戏的一些性质。 从简单入手 用一个n元组(a1, a2, …, an)，来描述游戏过程中的一个局面。 可以用3元组(3, 3, 1)来描述图1所示的局面。 改变这个n元组中数的顺序，仍然代表同一个局面。 (3, 3, 1)和(1, 3, 3)，可以看作是同一个局面。 如果初始局面只有一堆石子，则甲有必胜策略。 甲可以一次把这一堆石子全部取完，这样乙就无石子可取了。 如果初始局面有两堆石子，而且这两堆石子的数目相等，则乙有必胜策略。 因为有两堆石子，所以甲无法一次取完； 如果甲在一堆中取若干石子，乙便在另一堆中取同样数目的石子； 根据对称性，在甲取了石子之后，乙总有石子可取； 石子总数一直在减少，最后必定是甲无石子可取。 对于初始局面(1)，甲有必胜策略，而初始局面(3, 3)，乙有必胜策略。 局面的加法：(a1, 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局面； 若甲在一个桌子中取石子，则乙在另一个桌子中对称的取石子； 根据对称性，在甲取了石子之后，乙总有石子可取； 石子总数一直在减少，最后必定是甲无石子可取。 初始局面(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胜，则必存在取子的方法S→T，且T负。 如果局面S负，则对于任意取子方法S→T，有T胜。 设初始局面S可以分解成两个子局面A和B（分解理论）。 若A和B一胜一负，则S胜。 不妨设A胜B负； 想象有两个桌子A和B，桌子上分别放着A局面和B局面； 因为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负，故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)。 一个局面的胜负情况，与其简化后的局面相同。 三个局面(2, 2, 2, 7, 9, 9)、(2, 2, 2, 7)和(2, 7)，胜负情况都相同。 不能简化的局面称为“最简局面”。