博弈-由感性认识到理性认识

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

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

一、 游戏 ................................................................................................. 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

1011

+ 1011 + 1001

0010

?

0000

? 二进制数a, b, s，若a + b = s，则a = b + s。

0011 1001 + 1010 + 1010 0011

?

1001 - 8 -

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

? 二进制数a1+a2+…+an=p≠0，则必存在k，使得ak+p

? 因为p≠0，所以p的最高位是1； ? 设p的最高位是第q位；

? 至少存在一个k，使得ak的第q位也是1； ? ak+p的第q位为0，所以ak+p

11001 a1 01101 ak

01101 ak

+ 10010 a3

00110 p q

+ 00110 p

01011 ak+p q

?

快速推导ak+p

? 若#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

x≠a1 a1 +

p≠0

- 9 -

00101 a2+a3+a4=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

00101 a1 10011 a2 00111 a3 + 10111 a4

00110 p≠0

00101 a1

00011 x=a2+a3+a4=a1+p

00110 p

x x +

p=0

?

? 若S是空局面，则#S=0。

个人推导过程：p+f(ak)

? 若#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)

00101 f(a1)

00101 f(a1)

#(b1, b2, …, bm)∈g(a1)

f(a1) +

p≠0

+ 00001 f(a4) +

00000 p=0

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

? 如果先行者把局面(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

? 如果集合g(a1)包含集合{0, 1, …, f(a1)–1}，则x一定属于g(a1)。（充分）

00101 f(a1) 10011 f(a2) 00111 f(a3)

00101 f(a1)

#(b1, b2, …, bm)=x x +

p=0

如果x∈g(a1)

00011 x=f(a1)+p

+ 10111 f(a4) +

00110 p≠0

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； ? 图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负。

- 15 -

本文来源：https://www.bwwdw.com/article/qz0f.html