有没人研究过这样一个游戏？
kuaidi.ping-jia.net 作者：佚名 更新日期：2024-07-04
有没有人玩过这样一个游戏：游戏是在一个岛上，首先要采集资源（香蕉还有其他的），玩到一定程度可以去开
由感性认识到理性认识
——透析一类搏弈游戏的解答过程
一、 游戏.................................................................................................2
二、 从简单入手....................................................................................2
三、 类比与联想....................................................................................6
四、 证明.................................................................................................8
五、 推广...............................................................................................11
六、 精华...............................................................................................12
七、 结论...............................................................................................16
八、 总结...............................................................................................17
- 1 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
一、 游戏 !
!
#
#
#
!
#
#
$
%
游戏A：
甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。例如图1所示的初始局面：共n=3堆，其中第一堆的石子数a1=3，第二堆石子数a2=3，第三堆石子数a3=1。两人轮流按下列规则取走一些石子，游戏的规则如下：
每一步应取走至少一枚石子；
每一步只能从某一堆中取走部分或全部石子；
如果谁无法按规则取子，谁就是输家。
第一堆：a1=3
第二堆：a2=3
第三堆：a3=1
图 1 游戏的一个初始局面
游戏B：
甲乙双方事先约定一个数m，并且每次取石子的数目不能超过m个；
其余规则同游戏A。
我们关心的是，对于一个初始局面，究竟是先行者（甲）有必胜策略，还是后行者（乙）有必胜策略。
下面，我们从简单入手，先来研究研究这个游戏的一些性质。
二、 从简单入手
用一个n元组(a1, a2, …, an)，来描述游戏过程中的一个局面。
可以用3元组(3, 3, 1)来描述图1所示的局面。 - 2 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
&
%
%
$
%
$
%
%
改变这个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)，故乙有必胜策略。 - 3 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
$
$
%
%
'
'
'
'
'
'
'
'
对于局面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负。
- 4 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
& 如果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)，胜负情况都相同。
$ 不能简化的局面称为“最简局面”。
局面 (2, 7)是最简局面。
& 最简局面中不会有两堆相同的石子，故可以用一个集合来表示最简局面。
最简局面(2, 7)可以用集合{2, 7}来表示。
( 如果只关心局面的胜负，则一个局面可以用一个集合来描述。
图1所示的局面(3, 3, 1)，可以用集合{1}来描述。
- 5 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
如果用搜索（搏弈树）的方法来解这个游戏，则采用集合来表示一个局面，比采用多元组来表示一个局面，搜索量将有所减少，但时间复杂度仍然很高。
能不能进一步简化一个局面的表示呢？
三、 类比与联想
! 二进制加法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负，则A+B胜；若b=1且a=0，则a+b=1
若A负B负，则A+B负；若a=0且b=0，则a+b=0
……
) 如果用二进制1和0，分别表示一个局面的胜或负
& 局面的加法，与二进制的加法有很多类似之处。
* 若A胜B胜，则A+B有时胜，有时负；若a=1且b=1，则a+b=0。
1 本文的“二进制加法”，是指不进位的二进制加法，也可以理解为逻辑里的“异或”操作。 - 6 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
$ 二进制数的加法：对二进制数的每一位，都采用二进制的加法。
，。 0011 + 1010
1010
+ 1010
0000
1001
%
#
#
#
#
#
#
#
#
$
%
! 二进制数的加法 VS 局面的加法
大写字母AB表示局面，小写字母ab表示二进制数
若A和B相同，则A+B负；若a和b相等，则a+b为0
若A胜B负，则A+B胜；若a≠0且b=0，则a+b≠0
若B胜A负，则A+B胜；若b≠0且a=0，则a+b≠0
若A负B负，则A+B负；若a=0且b=0，则a+b=0
若A胜B胜，则A+B有时胜，有时负
若a≠0且b≠0，则有时a+b≠0，有时a+b=0
……
) 如果用二进制数s来表示一个局面S的胜或负，S胜则s≠0，S负则s=0
& 局面的加法，与二进制数的加法，性质完全相同。
) 能否用一个二进制数，来表示一个局面呢？
用符号#S，表示局面S所对应的二进制数。
) 如果局面S只有一堆石子，则用这一堆石子数目所对应的二进制数来表示S。
#(5)=5=101。
- 7 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
) 若局面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)=#(a1)。
对于游戏A来说，#(5)=101，所以f(5)=101。
对于游戏A来说，f(x)就是x所对应的二进制数。换句话说，f(x)=x。
& 设局面S=(a1, a2, …, an)，即S=(a1)+(a2)+…+(an)，则#S=f(a1)+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负；若#S≠0，则S胜。
四、 证明
& 二进制数a, b，若a + b = 0，当且仅当a = b。
1011
+ 1001
0010
1011
+ 1011
0000
& 二进制数a, b, s，若a + b = s，则a = b + s。
0011
+ 1010
1001
1001
+ 1010
0011
- 8 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
& 二进制数a1+a2+…+an=p≠0，则必存在k，使得ak+p<ak。
' 因为p≠0，所以p的最高位是1；
' 设p的最高位是第q位；
' 至少存在一个k，使得ak的第q位也是1；
' ak+p的第q位为0，所以ak+p<ak。
00110 p q 01101 ak + 00110 p 01011 ak+p
11001 a1
01101 ak
+ 10010 a3
q %
%
& 若#S=0，则无论先行者如何取子S→T，都有#T≠0。
' 先行者只能从某一堆中取若干石子，不妨设他选择的就是第1堆；
' 设先行者从第1堆中取了x个石子，用T表示取完之后的局面；
' 设S=(a1, a2, …, an)，则T=(a1–x, a2, …, an)；
' #S=f(a1)+#(a2, …, an)=0，故f(a1)=#(a2, …, an)；
' #T=f(a1–x)+#(a2, …, an)=f(a1–x)+f(a1)；
' x>0→f(a1)≠f(a1–x)→f(a1)+f(a1–x)≠0→#T≠0。
00101 a1
10011 a2
10111 a3
+ 00001 a4
00000 p=0
00101 a1
00101 a2+a3+a4=a1
+
00000 p=0
x≠a1
a1
+
p≠0
- 9 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
& 若#S≠0，则先行者必然存在一种取子方法S→T，且#T=0。
' 设S=(a1, a2, …, an)，p=#S=f(a1)+f(a2)+…+f(an)；
' 因为p≠0，所以必然存在k，使得f(ak)+p<f(ak)，不妨设k=1，f(a1)+p=x；
' 先行者将第1堆的石子的数目从a1变成x，用T表示这个局面；
' p=#S=f(a1)+#(a2, …, an)，故#(a2, …, an)=f(a1)+p=x；
' #T=f(x)+#(a2, …, an)=f(x)+x=0。 %
%
%
00101 a1
10011 a2
00111 a3
+ 10111 a4
00110 p≠0
00101 a1
00011 x=a2+a3+a4=a1+p<a1
+
00110 p
x
x
+
p=0
$ 若S是空局面，则#S=0。
( 若#S=0，则S负；若#S≠0，则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=a1+a2+…+an。若#S≠0，则先行者（甲）有必胜策略；否则#S=0，这时后行者（乙）有必胜策略。
下面把这个结论推广到游戏B。
- 10 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
$
$
&
'
!
!
#
#
#
%
函数f：f(x)=x mod (m+1)；把函数f的值看作是二进制数。
对于任意初始局面S=(a1, a2, …, an)，令#S=f(a1)+f(a2)+…+f(an)。
若#S≠0，则先行者（甲）有必胜策略；否则后行者（乙）有必胜策略。
类似游戏A的证明。
! 游戏B的解法与游戏A十分类似。这是因为两个游戏的规则相当类似。
五、 推广
游戏C：
甲乙两人面对若干排石子，其中每一排石子的数目可以任意确定。例如图2所示的初始局面：共n=3排，其中第一排的石子数a1=7，第二排石子数a2=3，第三排石子数a3=3。两人轮流按下列规则取走一些石子，游戏的规则如下：
每一步必须从某一排中取走两枚石子；
这两枚石子必须是紧紧挨着的；
如果谁无法按规则取子，谁就是输家。
1 2 3 4 5 6 7
第一排，a1=7
第二排，a2=3
第三排，a3=3
图 2 游戏的一个初始局面
如果甲第一步选择取第一排34这两枚石子，之后无论是甲还是乙，都不能一次取走25这两枚石子。换句话说，如果取了34这两枚石子，等价于将第一排分成了两排，这两排分别有2个和3个石子。 - 11 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
我们只关心，对于一个初始局面，究竟是先行者（甲）有必胜策略，还是后行者（乙）有必胜策略。
游戏C的规则和游戏A并不那么相似。但是，前面所列出的，游戏A的关键性质，游戏C却都具有。比如说，图2所示的初始局面可以用三元组(7, 3, 3)来表示，它的胜负情况与初始局面(7)相同。
游戏A的解答是由它的性质得出来的。因此，我们猜想游戏C是否也能用类似的方法来解。
六、 精华
! 回忆游戏A的结论，以及它在游戏B上的推广，对于游戏C，我们的想法是
) 设计一个函数f，把函数f的值看作是二进制数。对于任意一个初始局面S，设S=(a1, a2, …, an)，令#S=f(a1)+f(a2)+…+f(an)。若#S≠0，则先行者（甲）有必胜策略；否则#S=0，这时后行者（乙）有必胜策略。 %
%
%
!
&
#
#
游戏A中，f(x) = x。
游戏B中，f(x) = x mod (m + 1)。
游戏C中，f(x) = ?。
关键就在于如何构造一个满足要求的函数f。
! 回忆关于游戏A、B的结论的证明过程
函数f是否满足要求，关键在于#S是否满足下面的条件。
若#S=0，则无论先行者如何取子S→T，都有#T≠0。
若#S≠0，则先行者必然存在一种取子方法S→T，且#T=0。
- 12 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
$
%
%
%
$
%
%
%
%
用符号$(x)，表示局面(x)的下一步所有可能出现的局面的集合。
在游戏A中，$(3)={(2), (1), (0)}。
在游戏B中，若m=4，则$(9)={(8), (7), (6), (5)}，$(2)={(1), (0)}。
在游戏C中，$(7)={(5), (1, 4), (2, 3)}。
定义集合g(x)：设$(x)={S1, S2, …, Sk}，则g(x)={#S1, #S2, …, #Sk}。
在游戏A中，$(3)={(2), (1), (0)}，故g(3)={#(2), #(1), #(0)}={10, 01, 00}。
在游戏B中，若m=4，则g(9)={#(8), #(7), #(6), #(5)}，g(2)={#(1), #(0)}。
在游戏C中，g(7)={#(5), #(1, 4), #(2, 3)}。
(5)
(1, 4)
(7)
(2, 3)
$(7)={(5), (1, 4), (2, 3)}
g(7)={#(5), #(1, 4), #(2, 3)}
# 若#S=0，则无论先行者如何取子S→T，都有#T≠0。
' 设S=(a1, a2, …, an)，由于先行者只能选择一堆石子，不妨设选择了a1；
' 因为#S=f(a1)+#(a2, …, an)=0，所以f(a1)=#(a2, …, an)；
' 先行者可能将局面(a1)变为局面(b1, …, bm)，#(b1, …, bm)属于集合g(a1)；
' 设这时的局面为T，我们有T=(b1, …, bm)+(a2, …, an)；
' #T=#(b1, …, bm)+#(a2, …, an)=#(b1, …, bm)+f(a1)；
' 如果要求#T≠0，则必然有#(b1, …, bm)≠f(a1)；
' 因此，函数f(a1)的值，不属于集合g(a1)。（充要） - 13 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
00101 f(a1)
10011 f(a2)
10111 f(a3)
+ 00001 f(a4)
00000 p=0
#(b1, b2, …, bm)∈g(a1)
f(a1)
+
p≠0
00101 f(a1)
00101 f(a1)
+
00000 p=0
%
%
# 若#S≠0，则先行者必然存在一种取子方法S→T，且#T=0。
' 设S=(a1, a2, …, an)，p=#S=f(a1)+f(a2)+…+f(an)；
' 因为p≠0，所以必然存在k，使得f(ak)+p<f(ak)，不妨设k=1，f(a1)+p=x；
' 因为p=#S=f(a1)+#(a2, …, an)，故(a2, …, an)=p+f(a1)=x；
' 如果先行者把局面(a1)变为局面(b1, …, bm)，#(b1, …, bm)属于集合g(a1)；
' 设这时的局面为T，我们有T=(b1, …, bm)+(a2, …, an)；
' #T=#(b1, …, bm)+#(a2, …, an)=#(b1, …, bm)+x；
' 如果要使#T=0，相当于要找到(b1, …, bm)，使得#(b1, …, bm)等于x；
' 如果可以保证x属于集合g(a1)，则肯定可以找到相应的的(b1, …, bm)；
' 因为x<f(a1)，所以，x属于集合{0, 1, …, f(a1)–1}；
' 如果集合g(a1)包含集合{0, 1, …, f(a1)–1}，则x一定属于g(a1)。（充分）
00101 f(a1)
10011 f(a2)
00111 f(a3)
+ 10111 f(a4)
00110 p≠0
#(b1, b2, …, bm)=x
x 如果x∈g(a1)
+
p=0
00101 f(a1)
00011 x=f(a1)+p<f(a1)
+
00110 p
- 14 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
!
#
#
%
$
$
$
$
%
#
#
#
#
#
#
#
#
函数f满足要求的一个充分条件
f(a1)不属于集合g(a1)。
集合g(a1)包含集合{0, 1, …, f(a1)–1}。
如果g(a1)={0, 1, 2, 5, 7, 8, 9}，则f(a1)=3，满足要求。
用大写字母N表示非负整数集，即N={0, 1, 2, …}。
令N为全集，集合G(x)表示集合g(x)的补集。
定义函数f(n)：f(n)=min{G(n)}，即f(n)等于集合G(n)中的最小数。
设局面S=(a1, a2, …, an)，#S=f(a1)+f(a2)+…+f(an)，采用二进制数的加法。
( 若#S=0，则S负；若#S≠0，则S胜。
游戏C的f值：
g(0)={}，G(0)={0, 1, …}，f(0)=0；
g(1)={}，G(1)={0, 1, …}，f(1)=0；
g(2)={#(0)}={f(0)}={0}，G(2)={1, 2, …}，f(2)=1；
g(3)={#(1)}={f(1)}={0}，G(2)={1, 2, …}，f(3)=1；
g(4)={#(2), #(1, 1)}={f(2), f(1)+f(1)}={1, 0}，G(4)={2, 3, …}，f(4)=2；
g(5)={#(3), #(1, 2)}={f(3), f(1)+f(2)}={1, 1}，G(5)={0, 2, 3, …}，f(5)=0；
g(6)={#(4), #(1, 4), #(2, 2)}={2, 1, 0}，G(6)={3, 4, …}，f(6)=3；
g(7)={#(4), #(1, 4), #(2, 3)}={2, 2, 0}，G(7)={1, 3, 4, …}，f(7)=1； - 15 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
%
%
!
$
$
$
$
$
$
$
图2所示的局面S=(7, 3, 3)，有#S=f(7)+f(3)+f(3)=1+1+1=1，故S胜。
游戏C的初始局面S=(3, 4, 6)，有#S=1+2+3=01+10+11=0，故S负。
七、 结论
此类搏弈游戏的一般性解法：
用一个n元组(a1, a2, …, an)，来描述游戏过程中的一个局面。
用符号#S，表示局面S所对应的二进制数。
用符号$(x)，表示局面(x)的下一步所有可能出现的局面的集合。
定义集合g(x)：设$(x)={S1, S2, …, Sk}，则g(x)={#S1, #S2, …, #Sk}。
令非负整数集为全集，集合G(x)表示集合g(x)的补集。
定义函数f(n)：f(n)=min{G(n)}，即f(n)等于集合G(n)中的最小数。
设局面S=(a1, a2, …, an)，#S=f(a1)+f(a2)+…+f(an)，采用二进制数的加法。
( 若#S≠0，则先行者有必胜策略；若#S=0，则后行者有必胜策略。
!
#
#
#
#
#
!
适用范围和限制条件：
甲乙两人取石子游戏及其类似的游戏；
每一步只能对某一堆石子进行操作；
每一步操作的限制，只与这堆石子的数目或一些常数有关；
操作在有限步内终止，并不会出现循环；
谁无法继续操作，谁就是输家。
游戏D（POI’2000，Stripes）： - 16 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
!
☺
一排石子有L个，甲乙两人轮流从中取“紧紧挨着的”A或B或C枚石子。谁不能取了，谁就是输家。已知A, B, C, L，问甲乙二人谁有必胜策略。
有了前面的结论，这个游戏就难不倒我们了。
八、 总结
1. 从算法优化的角度
取石子游戏属于一类典型的搏弈游戏。穷举所有的局面，理论上可以求得最优策略。但穷举的时空复杂度太高，本文所提出的解法，有效的控制了算法的时空复杂度，可以看作是对穷举法的一个优化。
优化算法的过程，可以看作是在优化局面的表示。首先，我们用一个n元组表示一个局面，这是很直观很容易想到的。因为我们只关心局面的胜负，于是得到了第一个性质：这个n元组是无序的。进一步分析发现，n元组中如果出现两个相同的数字，则把它们消去，不影响局面的胜负。于是，我们改用集合来表示一个局面。最后，通过与二进制数的对比，又简化到用一个数来表示一个局面。
优化局面的表示，使得搜索量大大减少。那么，减少的搜索量都到哪里去了呢？举个例子，对于游戏A中的5个局面：(3, 3, 1), (1, 3, 3), (5, 5, 1), (2, 3)：
a. 采用n元组：这5个局面互不相同；
b. 采用无序n元组：局面(3, 3, 1)和(1, 3, 3)相同；
c. 采用集合：局面(3, 3, 1), (1, 3, 3), (5, 5, 1)都相同，可以用集合{1}表示；
d. 采用二进制数：4个局面所对应的二进制数都是1，故都相同。
算法的优化，本质上是避免穷举相同的局面，即避免重复搜索。而优化的关键，就在于“相同局面”的定义。
“相同局面”的定义，必须能够反映游戏的性质。我们没有简单的按照局面的胜负，来对局面归类，就是这个原因。
2. 从算法构造的角度
人们认识事物的过程中，开始只是看到了各个事物的现象。这就是认识的感
- 17 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
性阶段。在这个阶段中，还不能作出合乎逻辑的结论。 随着研究的深入，这些感觉和印象的东西反复了多次，于是在人们的脑子里生起了一个认识过程中的突变，最后产生出合乎逻辑的结论。这就是认识的理性阶段。
人们认识事物的过程，就是由感性认识上升到理性认识的过程。具体到解这类游戏，就是要从简单入手。当我们遇到了一个复杂的问题，或许人人都知道从简单入手，但却并不是每个人都能从中得到一般性的规律。那么，我们究竟是如何由浅入深的呢？
两堆数目相等的石子——这是个很简单的局面。我们就由此入手，将一堆石子与一个子局面相类比，并得出了两个子局面相等时的结论。在此基础上，我们研究了局面的胜负和其子局面的关系，并得出结论：可以用集合来描述一个局面。但我们并没有停留在这一步，而是将局面的分解与二进制数的加法相类比，从而发现了局面与二进制数之间的关系。我们称这个过程为“由此及彼”。
通过分析“用集合来表示一个局面”的结论，我发现这实质上是简化了局面的表示，从而联想到能否进一步化简，比如说用一个数来表示。在解游戏C时，我们并不在意它与游戏A的规则有多大的区别，而是注意到它与游戏A有着相似的性质，从而想到用类似的方法解游戏C。我们称这个过程为“由表及里”。
在解游戏A和B的过程中，我们积累了很多经验。但在解游戏C时，我们却仅仅提到了解游戏A和B的精华：构造一个函数f。这就是“去粗取精”。
将局面与二进制数相类比，我们先试着把局面的胜负直接与二进制的1和0相类比。发现不妥后，再将其改为与二进制数来类比。这一步叫“去伪存真”。
“由此及彼、由表及里、去粗取精、去伪存真” ，这就是由感性认识上升到理性认识的关键。
- 18 -
一天甲 乙丙 丁四位同学打乒乓球,回来时把钱凑在一起买了7块饼干,平均...
答：大量的事实也表明,个人的观察、分析、判断、理解、思考、决策、创意、策划、想像、洞察和战略规划等思维技能是否成熟,是否接受过系统的训练,将决定个人未来的职业发展前途。因此,一个人要想在激烈的脑力竞争中生存,就要学会更新自己僵化的头脑、简单的思维模式,让自己成为一个思维技能训练有素的人。 知识固然重要,但...
找一个游戏
答：找一个游戏 10 首先有一个大公司,有许多顾客来,你需要给他们拿行李,还要做饭,每一关完了都可以买东西,比如买一个拿行李的人,买一个做饭的人,游泳池,羽毛球场………是中文的... 首先有一个大公司,有许多顾客来,你需要给他们拿行李,还要做饭,每一关完了都可以买东西,比如买一个拿行李的人,买一个做饭...
寻找一个2002年的类似于17世纪时的回合制策略游戏.
答：开始是选个国家,自己起名字,回合制,每个单位动一次,然后休整一年进入下一回合.在此期间科技在不断提升.背景就是大殖民时期,可以选择很多地图来开始游戏,有虚拟的,也有一个真实的欧洲... 开始是选个国家,自己起名字,回合制,每个单位动一次,然后休整一年进入下一回合.在此期间科技在不断提升.背景就是大殖民时期,...
《猫鼠游戏》有原型吗?为什么评价那么高?
答：《猫鼠游戏》是有原型的，是根据小弗兰克·阿巴格诺的自传《有本事来抓我吧——一个诈骗犯令人惊异的真实故事》改编，评价之所以高，是因为剧情设定十分优秀。导演斯皮尔伯格颇有意味地设置了明暗两条既平行又交织的叙事线索。弗兰克招摇撞骗取的离奇经历构成了主线，而他甘冒风险四处行骗以挽回破碎的家庭的...
你在生活中发现过什么有趣的现象?有没有推测或探索其中的道理?
答：2.我以前对"石头,剪刀,布"的游戏做过初步的研究,即双方出同样的手形(如石头或剪刀或布)时,如果那两个人智力没有缺陷的话,他们在第二次应该都会出布(假设他们第一次出的都是石头).可是据我观察和粗略统计很多人(当然大多数是小孩在玩这游戏)并不会出石头,他们有近1/2出的还是石头,改成剪刀和布的都只占...
学习如何能集中注意力,当没有一个安静的环境的时候
答：这里给大家介绍一种在心理学中用来锻炼注意力的小游戏。在一张有25个小方格的表中,将1-25的数字打乱顺序,填写在里面,然后以最快的速度从1数到25,要边读边指出,同时计时。 研究表明:7-8岁儿童按顺序导找每张图表上的数字的时间是30-50秒,平均40-42秒;正常成年人看一张图表的时间大约是25-30秒,有些人...
怎样开发右脑
答：在Windows操作系统中，控制面板的鼠标选项可变换左右键，这样就变成了一个左手鼠标。锻炼左手使用鼠标的好处至少还有两个：A，减少由于长期使用鼠标而引起的腕管综合症；B，使鼠标的使用寿命至少延长50％。5．左手用餐。中国人与西方人不同的用餐习惯就是使用筷子，也曾有人自豪地把它归为中国人能够在...
缺氧游戏有没有一种可循环的氧气来源
答：办法：利用空调冷凝，可以把被污染的氧气凝结成液态，甚至把低温氧直接变成固态。液态氧通过水泵抽走，就可以直接提供氧气和低温了。拓展游戏：《缺氧》是由开发过《饥荒》的Klei Entertainment所制作并发行的一款模拟游戏。其美术风格也与《饥荒》一脉相承，并同样采用了横版2D布局。这是一个太空殖民地模拟...
做个几万人一起玩的荒野大镖客有可能吗?
答：多人游戏的规模,一直是个让人捉摸不透的问题。从MUD发展而来的MMORPG,同时在线人数超过五位数的并不少见,但到了《方舟:生存进化》《ATLAS》和"吃鸡类"的作品中,服务器、或者说一个房间容纳的人数一般在70到200之间徘徊。估计有不少玩家曾经幻想过,将《荒野大镖客:救赎2》这样细致入微的单人体验塑造成大型MMO,上...
求星际争霸1人族战役攻略
答：然后造好机场和重工,用运输机送一个SCV到前哨站那里开分矿,这时突然虫族基地传来声音,没一会一个强大的猛犸就会来进攻,速度研究秃鹫车的蜘蛛雷并且建造秃鹫车,一般6枚蜘蛛雷就能把这只猛犸炸残,此后敌人会不断派来这种猛犸,架起坦克布起蜘蛛雷来预防,后期造一堆大和战舰,杀死脑虫,这样主宰附近的防御就瘫痪了,再...
孤岛余生？
（1）A、牛顿从石头落回地面的距离不同，分析预测用相同的力去改变同一物体运动方向时，运动速度越大，物体的运动方向越不易改变，即物体的运动方向改变较小，会落回离掷出点更远的地方．所以牛顿设想：在地球的一座高山上架起一只水平大炮，以不同的速度将炮弹平射出去，射出速度越大，炮弹落地点就离山脚越远．B、于是牛顿通过科学的推理得出了一个重要的结论：抛出物体的速度足够大时，物体将离开地球，绕地球旋转，做圆周运动；C、现在随着现代科技的发展，人们应用他的推论，制成了人造地球卫星．（2）在伽利略以前，关于自由下落的物体人们一直认为：重的物体会比轻的物体下落得快；①取相同体积的木球和铁球，根据公式m=ρV可知，木球的密度小于铁球的密度，所以木球的质量小于铁球的质量，所以V木＜V铁；②根据物体下落时的牵拉效应可以得出：V木＜V＜V铁；③将木球和铁球用质量可以忽略的细绳捆绑在一起，捆绑在一起的球可以理解为一个更重的球，如果按照A假设来推理，得出的结论应该是：V木＜V铁＜V．故答案为：（1）将炮弹水平发射出去，射出的速度越大，炮弹落地点就离山脚越远；如果物体的初速度足够大，则物体将会环绕地球不掉下来；人造地球卫星；（2）重的物体会比轻的物体下落得快；＜；V木＜V＜V铁；假设；V木＜V铁＜V．
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞由感性认识到理性认识
——透析一类搏弈游戏的解答过程
一、 游戏.................................................................................................2
二、 从简单入手....................................................................................2
三、 类比与联想....................................................................................6
四、 证明.................................................................................................8
五、 推广...............................................................................................11
六、 精华...............................................................................................12
七、 结论...............................................................................................16
八、 总结...............................................................................................17
- 1 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
一、 游戏 !
!
#
#
#
!
#
#
$
%
游戏A：
甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。例如图1所示的初始局面：共n=3堆，其中第一堆的石子数a1=3，第二堆石子数a2=3，第三堆石子数a3=1。两人轮流按下列规则取走一些石子，游戏的规则如下：
每一步应取走至少一枚石子；
每一步只能从某一堆中取走部分或全部石子；
如果谁无法按规则取子，谁就是输家。
第一堆：a1=3
第二堆：a2=3
第三堆：a3=1
图 1 游戏的一个初始局面
游戏B：
甲乙双方事先约定一个数m，并且每次取石子的数目不能超过m个；
其余规则同游戏A。
我们关心的是，对于一个初始局面，究竟是先行者（甲）有必胜策略，还是后行者（乙）有必胜策略。
下面，我们从简单入手，先来研究研究这个游戏的一些性质。
二、 从简单入手
用一个n元组(a1, a2, …, an)，来描述游戏过程中的一个局面。
可以用3元组(3, 3, 1)来描述图1所示的局面。 - 2 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
&
%
%
$
%
$
%
%
改变这个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)，故乙有必胜策略。 - 3 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
$
$
%
%
'
'
'
'
'
'
'
'
对于局面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负。
- 4 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
& 如果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)，胜负情况都相同。
$ 不能简化的局面称为“最简局面”。
局面 (2, 7)是最简局面。
& 最简局面中不会有两堆相同的石子，故可以用一个集合来表示最简局面。
最简局面(2, 7)可以用集合{2, 7}来表示。
( 如果只关心局面的胜负，则一个局面可以用一个集合来描述。
图1所示的局面(3, 3, 1)，可以用集合{1}来描述。
- 5 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
如果用搜索（搏弈树）的方法来解这个游戏，则采用集合来表示一个局面，比采用多元组来表示一个局面，搜索量将有所减少，但时间复杂度仍然很高。
能不能进一步简化一个局面的表示呢？
三、 类比与联想
! 二进制加法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负，则A+B胜；若b=1且a=0，则a+b=1
若A负B负，则A+B负；若a=0且b=0，则a+b=0
……
) 如果用二进制1和0，分别表示一个局面的胜或负
& 局面的加法，与二进制的加法有很多类似之处。
* 若A胜B胜，则A+B有时胜，有时负；若a=1且b=1，则a+b=0。
1 本文的“二进制加法”，是指不进位的二进制加法，也可以理解为逻辑里的“异或”操作。 - 6 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
$ 二进制数的加法：对二进制数的每一位，都采用二进制的加法。
，。 0011 + 1010
1010
+ 1010
0000
1001
%
#
#
#
#
#
#
#
#
$
%
! 二进制数的加法 VS 局面的加法
大写字母AB表示局面，小写字母ab表示二进制数
若A和B相同，则A+B负；若a和b相等，则a+b为0
若A胜B负，则A+B胜；若a≠0且b=0，则a+b≠0
若B胜A负，则A+B胜；若b≠0且a=0，则a+b≠0
若A负B负，则A+B负；若a=0且b=0，则a+b=0
若A胜B胜，则A+B有时胜，有时负
若a≠0且b≠0，则有时a+b≠0，有时a+b=0
……
) 如果用二进制数s来表示一个局面S的胜或负，S胜则s≠0，S负则s=0
& 局面的加法，与二进制数的加法，性质完全相同。
) 能否用一个二进制数，来表示一个局面呢？
用符号#S，表示局面S所对应的二进制数。
) 如果局面S只有一堆石子，则用这一堆石子数目所对应的二进制数来表示S。
#(5)=5=101。
- 7 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
) 若局面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)=#(a1)。
对于游戏A来说，#(5)=101，所以f(5)=101。
对于游戏A来说，f(x)就是x所对应的二进制数。换句话说，f(x)=x。
& 设局面S=(a1, a2, …, an)，即S=(a1)+(a2)+…+(an)，则#S=f(a1)+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负；若#S≠0，则S胜。
四、 证明
& 二进制数a, b，若a + b = 0，当且仅当a = b。
1011
+ 1001
0010
1011
+ 1011
0000
& 二进制数a, b, s，若a + b = s，则a = b + s。
0011
+ 1010
1001
1001
+ 1010
0011
- 8 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
& 二进制数a1+a2+…+an=p≠0，则必存在k，使得ak+p<ak。
' 因为p≠0，所以p的最高位是1；
' 设p的最高位是第q位；
' 至少存在一个k，使得ak的第q位也是1；
' ak+p的第q位为0，所以ak+p<ak。
00110 p q 01101 ak + 00110 p 01011 ak+p
11001 a1
01101 ak
+ 10010 a3
q %
%
& 若#S=0，则无论先行者如何取子S→T，都有#T≠0。
' 先行者只能从某一堆中取若干石子，不妨设他选择的就是第1堆；
' 设先行者从第1堆中取了x个石子，用T表示取完之后的局面；
' 设S=(a1, a2, …, an)，则T=(a1–x, a2, …, an)；
' #S=f(a1)+#(a2, …, an)=0，故f(a1)=#(a2, …, an)；
' #T=f(a1–x)+#(a2, …, an)=f(a1–x)+f(a1)；
' x>0→f(a1)≠f(a1–x)→f(a1)+f(a1–x)≠0→#T≠0。
00101 a1
10011 a2
10111 a3
+ 00001 a4
00000 p=0
00101 a1
00101 a2+a3+a4=a1
+
00000 p=0
x≠a1
a1
+
p≠0
- 9 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
& 若#S≠0，则先行者必然存在一种取子方法S→T，且#T=0。
' 设S=(a1, a2, …, an)，p=#S=f(a1)+f(a2)+…+f(an)；
' 因为p≠0，所以必然存在k，使得f(ak)+p<f(ak)，不妨设k=1，f(a1)+p=x；
' 先行者将第1堆的石子的数目从a1变成x，用T表示这个局面；
' p=#S=f(a1)+#(a2, …, an)，故#(a2, …, an)=f(a1)+p=x；
' #T=f(x)+#(a2, …, an)=f(x)+x=0。 %
%
%
00101 a1
10011 a2
00111 a3
+ 10111 a4
00110 p≠0
00101 a1
00011 x=a2+a3+a4=a1+p<a1
+
00110 p
x
x
+
p=0
$ 若S是空局面，则#S=0。
( 若#S=0，则S负；若#S≠0，则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=a1+a2+…+an。若#S≠0，则先行者（甲）有必胜策略；否则#S=0，这时后行者（乙）有必胜策略。
下面把这个结论推广到游戏B。
- 10 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
$
$
&
'
!
!
#
#
#
%
函数f：f(x)=x mod (m+1)；把函数f的值看作是二进制数。
对于任意初始局面S=(a1, a2, …, an)，令#S=f(a1)+f(a2)+…+f(an)。
若#S≠0，则先行者（甲）有必胜策略；否则后行者（乙）有必胜策略。
类似游戏A的证明。
! 游戏B的解法与游戏A十分类似。这是因为两个游戏的规则相当类似。
五、 推广
游戏C：
甲乙两人面对若干排石子，其中每一排石子的数目可以任意确定。例如图2所示的初始局面：共n=3排，其中第一排的石子数a1=7，第二排石子数a2=3，第三排石子数a3=3。两人轮流按下列规则取走一些石子，游戏的规则如下：
每一步必须从某一排中取走两枚石子；
这两枚石子必须是紧紧挨着的；
如果谁无法按规则取子，谁就是输家。
1 2 3 4 5 6 7
第一排，a1=7
第二排，a2=3
第三排，a3=3
图 2 游戏的一个初始局面
如果甲第一步选择取第一排34这两枚石子，之后无论是甲还是乙，都不能一次取走25这两枚石子。换句话说，如果取了34这两枚石子，等价于将第一排分成了两排，这两排分别有2个和3个石子。 - 11 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
我们只关心，对于一个初始局面，究竟是先行者（甲）有必胜策略，还是后行者（乙）有必胜策略。
游戏C的规则和游戏A并不那么相似。但是，前面所列出的，游戏A的关键性质，游戏C却都具有。比如说，图2所示的初始局面可以用三元组(7, 3, 3)来表示，它的胜负情况与初始局面(7)相同。
游戏A的解答是由它的性质得出来的。因此，我们猜想游戏C是否也能用类似的方法来解。
六、 精华
! 回忆游戏A的结论，以及它在游戏B上的推广，对于游戏C，我们的想法是
) 设计一个函数f，把函数f的值看作是二进制数。对于任意一个初始局面S，设S=(a1, a2, …, an)，令#S=f(a1)+f(a2)+…+f(an)。若#S≠0，则先行者（甲）有必胜策略；否则#S=0，这时后行者（乙）有必胜策略。 %
%
%
!
&
#
#
游戏A中，f(x) = x。
游戏B中，f(x) = x mod (m + 1)。
游戏C中，f(x) = ?。
关键就在于如何构造一个满足要求的函数f。
! 回忆关于游戏A、B的结论的证明过程
函数f是否满足要求，关键在于#S是否满足下面的条件。
若#S=0，则无论先行者如何取子S→T，都有#T≠0。
若#S≠0，则先行者必然存在一种取子方法S→T，且#T=0。
- 12 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
$
%
%
%
$
%
%
%
%
用符号$(x)，表示局面(x)的下一步所有可能出现的局面的集合。
在游戏A中，$(3)={(2), (1), (0)}。
在游戏B中，若m=4，则$(9)={(8), (7), (6), (5)}，$(2)={(1), (0)}。
在游戏C中，$(7)={(5), (1, 4), (2, 3)}。
定义集合g(x)：设$(x)={S1, S2, …, Sk}，则g(x)={#S1, #S2, …, #Sk}。
在游戏A中，$(3)={(2), (1), (0)}，故g(3)={#(2), #(1), #(0)}={10, 01, 00}。
在游戏B中，若m=4，则g(9)={#(8), #(7), #(6), #(5)}，g(2)={#(1), #(0)}。
在游戏C中，g(7)={#(5), #(1, 4), #(2, 3)}。
(5)
(1, 4)
(7)
(2, 3)
$(7)={(5), (1, 4), (2, 3)}
g(7)={#(5), #(1, 4), #(2, 3)}
# 若#S=0，则无论先行者如何取子S→T，都有#T≠0。
' 设S=(a1, a2, …, an)，由于先行者只能选择一堆石子，不妨设选择了a1；
' 因为#S=f(a1)+#(a2, …, an)=0，所以f(a1)=#(a2, …, an)；
' 先行者可能将局面(a1)变为局面(b1, …, bm)，#(b1, …, bm)属于集合g(a1)；
' 设这时的局面为T，我们有T=(b1, …, bm)+(a2, …, an)；
' #T=#(b1, …, bm)+#(a2, …, an)=#(b1, …, bm)+f(a1)；
' 如果要求#T≠0，则必然有#(b1, …, bm)≠f(a1)；
' 因此，函数f(a1)的值，不属于集合g(a1)。（充要） - 13 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
00101 f(a1)
10011 f(a2)
10111 f(a3)
+ 00001 f(a4)
00000 p=0
#(b1, b2, …, bm)∈g(a1)
f(a1)
+
p≠0
00101 f(a1)
00101 f(a1)
+
00000 p=0
%
%
# 若#S≠0，则先行者必然存在一种取子方法S→T，且#T=0。
' 设S=(a1, a2, …, an)，p=#S=f(a1)+f(a2)+…+f(an)；
' 因为p≠0，所以必然存在k，使得f(ak)+p<f(ak)，不妨设k=1，f(a1)+p=x；
' 因为p=#S=f(a1)+#(a2, …, an)，故(a2, …, an)=p+f(a1)=x；
' 如果先行者把局面(a1)变为局面(b1, …, bm)，#(b1, …, bm)属于集合g(a1)；
' 设这时的局面为T，我们有T=(b1, …, bm)+(a2, …, an)；
' #T=#(b1, …, bm)+#(a2, …, an)=#(b1, …, bm)+x；
' 如果要使#T=0，相当于要找到(b1, …, bm)，使得#(b1, …, bm)等于x；
' 如果可以保证x属于集合g(a1)，则肯定可以找到相应的的(b1, …, bm)；
' 因为x<f(a1)，所以，x属于集合{0, 1, …, f(a1)–1}；
' 如果集合g(a1)包含集合{0, 1, …, f(a1)–1}，则x一定属于g(a1)。（充分）
00101 f(a1)
10011 f(a2)
00111 f(a3)
+ 10111 f(a4)
00110 p≠0
#(b1, b2, …, bm)=x
x 如果x∈g(a1)
+
p=0
00101 f(a1)
00011 x=f(a1)+p<f(a1)
+
00110 p
- 14 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
!
#
#
%
$
$
$
$
%
#
#
#
#
#
#
#
#
函数f满足要求的一个充分条件
f(a1)不属于集合g(a1)。
集合g(a1)包含集合{0, 1, …, f(a1)–1}。
如果g(a1)={0, 1, 2, 5, 7, 8, 9}，则f(a1)=3，满足要求。
用大写字母N表示非负整数集，即N={0, 1, 2, …}。
令N为全集，集合G(x)表示集合g(x)的补集。
定义函数f(n)：f(n)=min{G(n)}，即f(n)等于集合G(n)中的最小数。
设局面S=(a1, a2, …, an)，#S=f(a1)+f(a2)+…+f(an)，采用二进制数的加法。
( 若#S=0，则S负；若#S≠0，则S胜。
游戏C的f值：
g(0)={}，G(0)={0, 1, …}，f(0)=0；
g(1)={}，G(1)={0, 1, …}，f(1)=0；
g(2)={#(0)}={f(0)}={0}，G(2)={1, 2, …}，f(2)=1；
g(3)={#(1)}={f(1)}={0}，G(2)={1, 2, …}，f(3)=1；
g(4)={#(2), #(1, 1)}={f(2), f(1)+f(1)}={1, 0}，G(4)={2, 3, …}，f(4)=2；
g(5)={#(3), #(1, 2)}={f(3), f(1)+f(2)}={1, 1}，G(5)={0, 2, 3, …}，f(5)=0；
g(6)={#(4), #(1, 4), #(2, 2)}={2, 1, 0}，G(6)={3, 4, …}，f(6)=3；
g(7)={#(4), #(1, 4), #(2, 3)}={2, 2, 0}，G(7)={1, 3, 4, …}，f(7)=1； - 15 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
%
%
!
$
$
$
$
$
$
$
图2所示的局面S=(7, 3, 3)，有#S=f(7)+f(3)+f(3)=1+1+1=1，故S胜。
游戏C的初始局面S=(3, 4, 6)，有#S=1+2+3=01+10+11=0，故S负。
七、 结论
此类搏弈游戏的一般性解法：
用一个n元组(a1, a2, …, an)，来描述游戏过程中的一个局面。
用符号#S，表示局面S所对应的二进制数。
用符号$(x)，表示局面(x)的下一步所有可能出现的局面的集合。
定义集合g(x)：设$(x)={S1, S2, …, Sk}，则g(x)={#S1, #S2, …, #Sk}。
令非负整数集为全集，集合G(x)表示集合g(x)的补集。
定义函数f(n)：f(n)=min{G(n)}，即f(n)等于集合G(n)中的最小数。
设局面S=(a1, a2, …, an)，#S=f(a1)+f(a2)+…+f(an)，采用二进制数的加法。
( 若#S≠0，则先行者有必胜策略；若#S=0，则后行者有必胜策略。
!
#
#
#
#
#
!
适用范围和限制条件：
甲乙两人取石子游戏及其类似的游戏；
每一步只能对某一堆石子进行操作；
每一步操作的限制，只与这堆石子的数目或一些常数有关；
操作在有限步内终止，并不会出现循环；
谁无法继续操作，谁就是输家。
游戏D（POI’2000，Stripes）： - 16 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
!
☺
一排石子有L个，甲乙两人轮流从中取“紧紧挨着的”A或B或C枚石子。谁不能取了，谁就是输家。已知A, B, C, L，问甲乙二人谁有必胜策略。
有了前面的结论，这个游戏就难不倒我们了。
八、 总结
1. 从算法优化的角度
取石子游戏属于一类典型的搏弈游戏。穷举所有的局面，理论上可以求得最优策略。但穷举的时空复杂度太高，本文所提出的解法，有效的控制了算法的时空复杂度，可以看作是对穷举法的一个优化。
优化算法的过程，可以看作是在优化局面的表示。首先，我们用一个n元组表示一个局面，这是很直观很容易想到的。因为我们只关心局面的胜负，于是得到了第一个性质：这个n元组是无序的。进一步分析发现，n元组中如果出现两个相同的数字，则把它们消去，不影响局面的胜负。于是，我们改用集合来表示一个局面。最后，通过与二进制数的对比，又简化到用一个数来表示一个局面。
优化局面的表示，使得搜索量大大减少。那么，减少的搜索量都到哪里去了呢？举个例子，对于游戏A中的5个局面：(3, 3, 1), (1, 3, 3), (5, 5, 1), (2, 3)：
a. 采用n元组：这5个局面互不相同；
b. 采用无序n元组：局面(3, 3, 1)和(1, 3, 3)相同；
c. 采用集合：局面(3, 3, 1), (1, 3, 3), (5, 5, 1)都相同，可以用集合{1}表示；
d. 采用二进制数：4个局面所对应的二进制数都是1，故都相同。
算法的优化，本质上是避免穷举相同的局面，即避免重复搜索。而优化的关键，就在于“相同局面”的定义。
“相同局面”的定义，必须能够反映游戏的性质。我们没有简单的按照局面的胜负，来对局面归类，就是这个原因。
2. 从算法构造的角度
人们认识事物的过程中，开始只是看到了各个事物的现象。这就是认识的感
- 17 -
由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞
性阶段。在这个阶段中，还不能作出合乎逻辑的结论。 随着研究的深入，这些感觉和印象的东西反复了多次，于是在人们的脑子里生起了一个认识过程中的突变，最后产生出合乎逻辑的结论。这就是认识的理性阶段。
人们认识事物的过程，就是由感性认识上升到理性认识的过程。具体到解这类游戏，就是要从简单入手。当我们遇到了一个复杂的问题，或许人人都知道从简单入手，但却并不是每个人都能从中得到一般性的规律。那么，我们究竟是如何由浅入深的呢？
两堆数目相等的石子——这是个很简单的局面。我们就由此入手，将一堆石子与一个子局面相类比，并得出了两个子局面相等时的结论。在此基础上，我们研究了局面的胜负和其子局面的关系，并得出结论：可以用集合来描述一个局面。但我们并没有停留在这一步，而是将局面的分解与二进制数的加法相类比，从而发现了局面与二进制数之间的关系。我们称这个过程为“由此及彼”。
通过分析“用集合来表示一个局面”的结论，我发现这实质上是简化了局面的表示，从而联想到能否进一步化简，比如说用一个数来表示。在解游戏C时，我们并不在意它与游戏A的规则有多大的区别，而是注意到它与游戏A有着相似的性质，从而想到用类似的方法解游戏C。我们称这个过程为“由表及里”。
在解游戏A和B的过程中，我们积累了很多经验。但在解游戏C时，我们却仅仅提到了解游戏A和B的精华：构造一个函数f。这就是“去粗取精”。
将局面与二进制数相类比，我们先试着把局面的胜负直接与二进制的1和0相类比。发现不妥后，再将其改为与二进制数来类比。这一步叫“去伪存真”。
“由此及彼、由表及里、去粗取精、去伪存真” ，这就是由感性认识上升到理性认识的关键。
- 18 -
答：大量的事实也表明,个人的观察、分析、判断、理解、思考、决策、创意、策划、想像、洞察和战略规划等思维技能是否成熟,是否接受过系统的训练,将决定个人未来的职业发展前途。因此,一个人要想在激烈的脑力竞争中生存,就要学会更新自己僵化的头脑、简单的思维模式,让自己成为一个思维技能训练有素的人。 知识固然重要,但...
答：找一个游戏 10 首先有一个大公司,有许多顾客来,你需要给他们拿行李,还要做饭,每一关完了都可以买东西,比如买一个拿行李的人,买一个做饭的人,游泳池,羽毛球场………是中文的... 首先有一个大公司,有许多顾客来,你需要给他们拿行李,还要做饭,每一关完了都可以买东西,比如买一个拿行李的人,买一个做饭...
答：开始是选个国家,自己起名字,回合制,每个单位动一次,然后休整一年进入下一回合.在此期间科技在不断提升.背景就是大殖民时期,可以选择很多地图来开始游戏,有虚拟的,也有一个真实的欧洲... 开始是选个国家,自己起名字,回合制,每个单位动一次,然后休整一年进入下一回合.在此期间科技在不断提升.背景就是大殖民时期,...
答：《猫鼠游戏》是有原型的，是根据小弗兰克·阿巴格诺的自传《有本事来抓我吧——一个诈骗犯令人惊异的真实故事》改编，评价之所以高，是因为剧情设定十分优秀。导演斯皮尔伯格颇有意味地设置了明暗两条既平行又交织的叙事线索。弗兰克招摇撞骗取的离奇经历构成了主线，而他甘冒风险四处行骗以挽回破碎的家庭的...
答：2.我以前对"石头,剪刀,布"的游戏做过初步的研究,即双方出同样的手形(如石头或剪刀或布)时,如果那两个人智力没有缺陷的话,他们在第二次应该都会出布(假设他们第一次出的都是石头).可是据我观察和粗略统计很多人(当然大多数是小孩在玩这游戏)并不会出石头,他们有近1/2出的还是石头,改成剪刀和布的都只占...
答：这里给大家介绍一种在心理学中用来锻炼注意力的小游戏。在一张有25个小方格的表中,将1-25的数字打乱顺序,填写在里面,然后以最快的速度从1数到25,要边读边指出,同时计时。 研究表明:7-8岁儿童按顺序导找每张图表上的数字的时间是30-50秒,平均40-42秒;正常成年人看一张图表的时间大约是25-30秒,有些人...
答：在Windows操作系统中，控制面板的鼠标选项可变换左右键，这样就变成了一个左手鼠标。锻炼左手使用鼠标的好处至少还有两个：A，减少由于长期使用鼠标而引起的腕管综合症；B，使鼠标的使用寿命至少延长50％。5．左手用餐。中国人与西方人不同的用餐习惯就是使用筷子，也曾有人自豪地把它归为中国人能够在...
答：办法：利用空调冷凝，可以把被污染的氧气凝结成液态，甚至把低温氧直接变成固态。液态氧通过水泵抽走，就可以直接提供氧气和低温了。拓展游戏：《缺氧》是由开发过《饥荒》的Klei Entertainment所制作并发行的一款模拟游戏。其美术风格也与《饥荒》一脉相承，并同样采用了横版2D布局。这是一个太空殖民地模拟...
答：多人游戏的规模,一直是个让人捉摸不透的问题。从MUD发展而来的MMORPG,同时在线人数超过五位数的并不少见,但到了《方舟:生存进化》《ATLAS》和"吃鸡类"的作品中,服务器、或者说一个房间容纳的人数一般在70到200之间徘徊。估计有不少玩家曾经幻想过,将《荒野大镖客:救赎2》这样细致入微的单人体验塑造成大型MMO,上...
答：然后造好机场和重工,用运输机送一个SCV到前哨站那里开分矿,这时突然虫族基地传来声音,没一会一个强大的猛犸就会来进攻,速度研究秃鹫车的蜘蛛雷并且建造秃鹫车,一般6枚蜘蛛雷就能把这只猛犸炸残,此后敌人会不断派来这种猛犸,架起坦克布起蜘蛛雷来预防,后期造一堆大和战舰,杀死脑虫,这样主宰附近的防御就瘫痪了,再...
