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

《由感性认识到理性认识-透析一类搏弈游戏的解答过程》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、由感性认识到理性认识——透析一类搏弈游戏的解答过程认识事物的过程事物的现象认识的感性阶段?事物的本质认识的理性阶段人们认识事物，总是从简单入手。究竟如何才能由浅入深呢？并不是人人都能从简单的事物中得到一般性的规律。游戏甲乙两人面对若干排石子。每一排石子的数目可以任意确定。两人轮流按下列规则取走一些石子：每一步必须从某一排中取走两枚石子；这两枚石子必须是紧紧挨着的；如果谁无法按规则取子，谁就是输家。a1=7a2=3a3=51234567规则分析a1=7如果一排有7枚石子而你取了3、4这两枚石子，可以看作是将这一排分成了两排，其中一排有2枚石子

2、，另一排有3枚石子。局面的排数可能会随着游戏的进行而增加。a1=2a2=3从简单入手用一个无序多元组(a1,a2,…,an)，来描述游戏过程中的一个局面。(3,3,1)若初始局面可以分成两个相同的“子局面”，则乙有必胜策略。(3,3,3,3,1,1)+负(3,3,1)(3)+(3)+(1)加法分解加法++若先行者有必胜策略，则称为“胜局面”。若后行者有必胜策略，则称为“负局面”。局面的分解胜负胜+=负负负+=胜胜?+=XC+CX+=XX负+=X负X+=局面与集合我们只关心局面的胜负。XC+CX+=(2,2,2,7,9,9)(2,2,2,7)

3、+(9)+(9)=(2,2,2,7)(2,7)用集合{2,7}来表示这实质上是简化了局面的表示。能不能进一步简化一个局面的表示呢？一个局面可以用一个集合来描述。类比局面的加法胜+负=胜；负+胜=胜；负+负=负；胜+胜=不定。二进制数的不进位加法：对二进制数的每一位，采用01加法。二进制的01加法VS局面的加法1+0=1；胜+负=胜；0+1=1；负+胜=胜；0+0=0；负+负=负；1+1=0；胜+胜=不定。二进制数的加法VS局面的加法胜负胜+=负负负+=胜胜?+=!00!0+=000+=!0!0?+=0011+101010011010+101

4、00000胜!0，负0局面的加法，与二进制数的加法，性质完全相同。联想能否用一个二进制数，来表示一个局面呢？#S=#(a1,…,an)=f(a1)+…+f(an)。关键就在于函数f(x)的构造。S#S(3)#(3)#(3,3)=#(3)+#(3)(3)(3)(3,3)+=+=#(3,3,1)=#(3)+#(3)+#(1)(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)，下一步可

5、能局面的值的集合。(5)(1,4)(2,3)(7)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)}，满足要求。取两枚相邻石子例子(5)(1,4)(2,3)(7)g(7)={0,2}，G(7)={1,3,4,5,…}#(5)=f(5)=0#(1,4)=f(1)+f(4)=0+2=2#(2,3)=f(2)+f(3)=1+1=0f(7)=min

6、{G(7)}=min{1,3,4,5,…}=1x01234567f(x)0011203?a1=7a2=3a3=5#(7,3,5)=f(7)+f(3)+f(5)=1+1+0=0局面(7,3,5)是负局面后走者（乙）有必胜策略推广把游戏规则改变一下一次取紧紧相邻的两枚石子；一次取紧紧相邻的三枚石子；一次取紧紧相邻的任意多枚石子；一次取某一排中的任意两枚石子，不要求紧紧相邻；一次取某一排中的任意多枚石子，不要求紧紧相邻；……此类博弈游戏的特点甲乙两人取石子；每一步只能对某一排石子进行操作；每一步操作的约束，只与这排石子的数目或一些常数有关；操作在

7、有限步内终止，并不会出现循环；谁无法继续操作，谁就是输家。此类博弈游戏的一般性解法判断一个局面，究竟谁有必胜策略设局面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)}。小结（一）优点&缺点优点适用范围广，可以直接用于大多数此类游戏与穷举相比，速度快，时空复杂度低缺点另一个游戏有若干堆

8、石子，两人互取。无法取子者输。一次只能在一堆中取，至少一枚，至多不限。对于这个游戏，可以证明令f(x)=x，就满足要求。有些游戏可以直接推导出函数f(x)的表达式小结（二）如何优