由感性认识到理性认识——透析一类搏弈游戏的解答过程.pptVIP

由感性认识到理性认识 —— 透析一类搏弈游戏的解答过程 认识事物的过程 人们认识事物，总是从简单入手。 究竟如何才能由浅入深呢？ 并不是人人都能从简单的事物中得到一般性的规律。 游戏 甲乙两人面对若干排石子。 每一排石子的数目可以任意确定。 两人轮流按下列规则取走一些石子： 每一步必须从某一排中取走两枚石子； 这两枚石子必须是紧紧挨着的； 如果谁无法按规则取子，谁就是输家。 规则分析 如果一排有7枚石子 而你取了3、4这两枚石子， 可以看作是将这一排分成了两排， 其中一排有2枚石子，另一排有3枚石子。 局面的排数可能会随着游戏的进行而增加。 从简单入手 用一个无序多元组(a1, a2, …, an)，来描述游戏过程中的一个局面。 若初始局面可以分成两个相同的“子局面”，则乙有必胜策略。 若先行者有必胜策略，则称为“胜局面”。 若后行者有必胜策略，则称为“负局面”。 局面的分解 局面与集合 我们只关心局面的胜负。 (2, 2, 2, 7, 9, 9) 这实质上是简化了局面的表示。 能不能进一步简化一个局面的表示呢？ 一个局面可以用一个集合来描述。 类比 局面的加法 胜+负=胜； 负+胜=胜； 负+负=负； 胜+胜=不定。 二进制数的不进位加法：对二进制数的每一位，采用01加法。 二进制的01加法 VS 局面的加法 1 + 0 = 1；胜+负=胜； 0 + 1 = 1；负+胜=胜； 0 + 0 = 0；负+负=负； 1 + 1 = 0；胜+胜=不定。 二进制数的加法 VS 局面的加法 局面的加法，与二进制数的加法，性质完全相同。 联想 能否用一个二进制数，来表示一个局面呢？ #S=#(a1, …, an)=f(a1)+…+f(an)。 关键就在于函数f(x)的构造。 #(3, 3)=#(3)+#(3) #(3, 3, 1)=#(3)+#(3)+#(1) #(3, 3, 1)=f(3)+f(3)+f(1) 用符号#S，表示局面S所对应的二进制数，简称局面S的值。 #S=0S负， #S≠0S胜。 构造 集合 g(x)：表示局面(x)，下一步可能局面的值的集合。 g(7)={#(5), #(1, 4), #(2, 3)} 可以证明，令函数f(x)为g(x)中没有出现的最小非负整数，满足要求。 如果g(x)={0, 1, 2, 5, 7, 8, 9}，则f(x)=3。 令G(x)为g(x)在非负整数集下的补集。 令f(x)=min{G(x)}，满足要求。 例子 g(7)={0, 2}，G(7)={1, 3, 4, 5, …} f(7)=min{G(7)}=min{1, 3, 4, 5, …}=1 x 0 1 2 3 4 5 6 7 f(x) 0 0 1 1 2 0 3 ? #(7, 3, 5)=f(7)+f(3)+f(5)=1+1+0=0 局面(7, 3, 5)是负局面 后走者（乙）有必胜策略 推广 把游戏规则改变一下 一次取紧紧相邻的两枚石子； 一次取紧紧相邻的三枚石子； 一次取紧紧相邻的任意多枚石子； 一次取某一排中的任意两枚石子，不要求紧紧相邻； 一次取某一排中的任意多枚石子，不要求紧紧相邻； …… 此类博弈游戏的特点 甲乙两人取石子； 每一步只能对某一排石子进行操作； 每一步操作的约束，只与这排石子的数目或一些常数有关； 操作在有限步内终止，并不会出现循环； 谁无法继续操作，谁就是输家。 此类博弈游戏的一般性解法 判断一个局面，究竟谁有必胜策略 设局面S=(a1, a2, …, an)； S的值#S=f(a1)+…+f(an)（二进制数的加法）； 如果#S≠0，则先行者有必胜策略； 如果#S=0，则后行者有必胜策略。 函数f(x)的求法 f(0)=0； g(x)表示局面(x)，下一步可能局面的值的集合； 令G(x)为g(x)在非负整数集下的补集； 则f(x)=min{G(x)}。 小结（一）优点 缺点 优点 适用范围广，可以直接用于大多数此类游戏 与穷举相比，速度快，时空复杂度低 缺点 另一个游戏 有若干堆石子，两人互取。无法取子者输。 一次只能在一堆中取，至少一枚，至多不限。 对于这个游戏，可以证明令f(x)=x，就满足要求。 有些游戏可以直接推导出函数f(x)的表达式 小结（二）如何优化算法 可以看作是对有哪些信誉好的足球投注网站算法的优化。 无序组：(2, 5, 5) (5, 2, 5) (2, 3, 3) (2, 3, 4, 6) (3, 4) 集合： {2} {2} {2} {2, 3, 4, 6} {3, 4} 二进制数： 01 01 01