nbhkdz.com冰点文库

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


Error! No bookmark name given.

张一飞

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

一、 二、 三、 四、 五、 六、 七、 八、

游戏...........................................................

..................................... 2 从简单入手.................................................................................... 2 类比与联想.................................................................................... 6 证明................................................................................................ 8 推广.............................................................................................. 11 精华.............................................................................................. 12 结论.............................................................................................. 16 总结.............................................................................................. 17

-1-

Error! No bookmark name given.

张一飞

一、 游戏 2? ? 游戏 A: 2? ? 甲乙两人面对若干堆石子,其中每一堆石子的数目可以任意确定。例如图 1
所示的初始局面: 共 n=3 堆, 其中第一堆的石子数 a1=3, 第二堆石子数 a2=3, 第三堆石子数 a3=1。两人轮流按下列规则取走一些石子,游戏的规则如下:

?? ? 每一步应取走至少一枚石子; ?? ? 每一步只能从某一堆中取走部分或全部石子; ?? ? 如果谁无法按规则取子,谁就是输家。
第一堆:a1=3 第二堆:a2=3 第三堆:a3=1

图 ? 1 ? 游戏的一个初始局面 ?

2? ? 游戏 B: ?? ? 甲乙双方事先约定一个数 m,并且每次取石子的数目不能超过 m 个; ?? ? 其余规则同游戏 A。

我们关心的是,对于一个初始局面,究竟是先行者(甲)有必胜策略,还是 后行者(乙)有必胜策略。 下面,我们从简单入手,先来研究研究这个游戏的一些性质。

二、 从简单入手 F? ? 用一个 n 元组(a1, a2, …, an),来描述游戏过程中的一个局面。 G? ? 可以用 3 元组(3, 3, 1)来描述图 1 所示的局面。
-2-

Error! No bookmark name given.

张一飞

@? ? 改变这个 n 元组中数的顺序,仍然代表同一个局面。 G? ? (3, 3, 1)和(1, 3, 3),可以看作是同一个局面。

@? ? 如果初始局面只有一堆石子,则甲有必胜策略。 &? ?甲可以一次把这一堆石子全部取完,这样乙就无石子可取了。 @? ? 如果初始局面有两堆石子,而且这两堆石子的数目相等,则乙有必胜策略。 &? ?因为有两堆石子,所以甲无法一次取完; &? ?如果甲在一堆中取若干石子,乙便在另一堆中取同样数目的石子; &? ?根据对称性,在甲取了石子之后,乙总有石子可取; &? ?石子总数一直在减少,最后必定是甲无石子可取。 G? ? 对于初始局面(1),甲有必胜策略,而初始局面(3, 3),乙有必胜策略。

F? ? 局面的加法:(a1, a2, …, an) + (b1, b2, …, bm) = (a1, a2, …, an, b1, b2, …, bm)。 G? ? (3) + (3) + (1) = (3, 3) + (1) = (3, 3, 1)。 F? ? 对于局面 A, B, S,若 S=A+B,则称局面 S 可以分解为“子局面”A 和 B。 G? ? 局面(3, 3, 1)可以分解为(3, 3)和(1)。

@? ? 如果初始局面可以分成两个相同的“子局面” ,则乙有必胜策略。 &? ?设初始局面 S=A+A,想象有两个桌子,每个桌子上放一个 A 局面; &? ?若甲在一个桌子中取石子,则乙在另一个桌子中对称的取石子; &? ?根据对称性,在甲取了石子之后,乙总有石子可取; &? ?石子总数一直在减少,最后必定是甲无石子可取。 G? ? 初始局面(2, 2, 5, 5, 5, 5, 7, 7),可以分成两个(2, 5, 5, 7),故乙有必胜策略。
-3-

Error! No bookmark name given.

张一飞

。 F? ? 对于局面 S,若先行者有必胜策略,则称“S 胜” 。 F? ? 对于局面 S,若后行者有必胜策略,则称“S 负”

G? ? 若 A=(1),B=(3, 3),C=(2, 2, 5, 5, 5, 5, 7, 7),则 A 胜,B 负,C 负。 G? ? 我们所关心的,就是如何判断局面的胜负。

@? ? 如果局面 S 胜,则必存在取子的方法 S→T,且 T 负。 @? ? 如果局面 S 负,则对于任意取子方法 S→T,有 T 胜。

2? ? 设初始局面 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-

Error! No bookmark name given.

张一飞

@? ? 如果 S=A+C+C,则 S 的胜负情况与 A 相同。 &? ?令 B=C+C,则 S=A+B 且 B 负,故 S 的胜负情况与 A 相同。 G? ? 图 1 所示的初始局面(3, 3, 1) = (3) + (3) + (1),与局面(1)的胜负情况相同。 G? ? 图 1 中所示的初始局面(3, 3, 1)是“胜”局面,甲有必胜策略。

F? ? 称一个石子也没有的局面为“空局面” 。 @? ? 空局面是“负”局面。

F? ? 如果局面 S 中,存在两堆石子,它们的数目相等。用 T 表示从 S 中把这两堆
石子拿掉之后的局面,则称“S 可以简化为 T” 。

G? ? 局面(2, 2, 2, 7, 9, 9)可以简化为(2, 2, 2, 7),还可以进一步简化为(2, 7)。

@? ? 一个局面的胜负情况,与其简化后的局面相同。 G? ? 三个局面(2, 2, 2, 7, 9, 9)、(2, 2, 2, 7)和(2, 7),胜负情况都相同。

F? ? 不能简化的局面称为“最简局面” 。 G? ? 局面 (2, 7)是最简局面。

@? ? 最简局面中不会有两堆相同的石子,故可以用一个集合来表示最简局面。 G? ? 最简局面(2, 7)可以用集合{2, 7}来表示。

*? ? 如果只关心局面的胜负,则一个局面可以用一个集合来描述。 G? ? 图 1 所示的局面(3, 3, 1),可以用集合{1}来描述。

-5-

Error! No bookmark name given.

张一飞

如果用搜索(搏弈树)的方法来解这个游戏,则采用集合来表示一个局面, 比采用多元组来表示一个局面,搜索量将有所减少,但时间复杂度仍然很高。 能不能进一步简化一个局面的表示呢?

三、 类比与联想 2? ? 二进制加法1 ?? ? 1 + 0 = 1; ?? ? 0 + 1 = 1; ?? ? 0 + 0 = 0; ?? ? 1 + 1 = 0。

2? ? 二进制的加法 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 ?? ? ……

Z? ? 如果用二进制 1 和 0,分别表示一个局面的胜或负 @? ? 局面的加法,与二进制的加法有很多类似之处。 ?? ? 若 A 胜 B 胜,则 A+B 有时胜,有时负;若 a=1 且 b=1,则 a+b=0。

1

本文的“二进制加法” ,是指不进位的二进制加法,也可以理解为逻辑里的“异或”操作。 -6-

Error! No bookmark name given.

张一飞

F? ? 二进制数的加法:对二进制数的每一位,都采用二进制的加法。
0011 + 1010 1001 , + 1010 1010 0000 。

G? ?

2? ? 二进制数的加法 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 ?? ? ……

Z? ? 如果用二进制数 s 来表示一个局面 S 的胜或负,S 胜则 s≠0,S 负则 s=0 @? ? 局面的加法,与二进制数的加法,性质完全相同。 Z? ? 能否用一个二进制数,来表示一个局面呢? F? ? 用符号#S,表示局面 S 所对应的二进制数。

Z? ? 如果局面 S 只有一堆石子, 则用这一堆石子数目所对应的二进制数来表示 S。

G? ? #(5)=5=101。

-7-

Error! No bookmark name given.

张一飞

Z? ? 若局面 S=A+B,则#S=#A+#B。

G? ? 局面(3, 3)=(3)+(3),所以#(3, 3)=#(3)+#(3)=11+11=0。 G? ? 局面(3, 3, 1)=(3, 3)+(1),所以#(3, 3, 1)=#(3, 3)+#(1)=0+1=1。

F? ? 函数 f:若局面 S 只有一堆石子,设 S={a1},则 f(a1)=#S,即 f(a1)=#(a1)。 G? ? 对于游戏 A 来说,#(5)=101,所以 f(5)=101。 G? ? 对于游戏 A 来说,f(x)就是 x 所对应的二进制数。换句话说,f(x)=x。

@? ? 设局面 S=(a1, a2, …, an),即 S=(a1)+(a2)+…+(an),则#S=f(a1)+f(a2)+…+f(an)。 G? ? #(3, 3, 1)=#((3)+(3)+(1))=#(3)+#(3)+#(1)=f(3)+f(3)+f(1)=11+11+1=1。

Z? ? 对于局面 S,若#S=0,则 S 负;若#S≠0,则 S 胜。

四、 证明 @? ? 二进制数 a, b,若 a + b = 0,当且仅当 a = b。
1011 + 1011 0000 + 1011 1001 0010

G? ?

@? ? 二进制数 a, b, s,若 a + b = s,则 a = b + s。
0011 + 1010 1001 + 1001 1010 0011

G? ?

-8-

Error! No bookmark name given.

张一飞

@? ? 二进制数 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。
11001 01101 + 10010 00110 a1 ak a3 p + 01101 00110 01011 q ak p ak+p

G? ?

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 10011 10111 + 00001 00000 a1 a2 a3 a4 p=0 + 00000 p=0 00101 a2+a3+a4=a1 + p≠0 a1 00101 a1 x≠a1

G? ?
-9-

Error! No bookmark name given.

张一飞

@? ? 若#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 10011 00111 + 10111 00110 a1 a2 a3 a4 p≠0 + 00110 p 00011 x=a2+a3+a4=a1+p<a1 + p=0 x 00101 a1 x

G? ? F? ? 若 S 是空局面,则#S=0。

*? ? 若#S=0,则 S 负;若#S≠0,则 S 胜。 G? ? #(1, 2, 3)=01+10+11=0,故局面(1, 2, 3)负。 G? ? #(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 -

Error! No bookmark name given.

张一飞

F? ? 函数 f:f(x)=x mod (m+1);把函数 f 的值看作是二进制数。 F? ? 对于任意初始局面 S=(a1, a2, …, an),令#S=f(a1)+f(a2)+…+f(an)。 @? ? 若#S≠0,则先行者(甲)有必胜策略;否则后行者(乙)有必胜策略。 &? ?类似游戏 A 的证明。 2? ? 游戏 B 的解法与游戏 A 十分类似。这是因为两个游戏的规则相当类似。

五、 推广 2? ? 游戏 C: 2? ? 甲乙两人面对若干排石子,其中每一排石子的数目可以任意确定。例如图 2
所示的初始局面: 共 n=3 排, 其中第一排的石子数 a1=7, 第二排石子数 a2=3, 第三排石子数 a3=3。两人轮流按下列规则取走一些石子,游戏的规则如下:

?? ? 每一步必须从某一排中取走两枚石子; ?? ? 这两枚石子必须是紧紧挨着的; ?? ? 如果谁无法按规则取子,谁就是输家。
1 第一排, a1=7 2 3 4 5 6 7

第二排, a2=3

第三排, a3=3
图 ? 2 ? 游戏的一个初始局面 ?

G? ? 如果甲第一步选择取第一排 34 这两枚石子,之后无论是甲还是乙,都不能
一次取走 25 这两枚石子。换句话说,如果取了 34 这两枚石子,等价于将第 一排分成了两排,这两排分别有 2 个和 3 个石子。
- 11 -

Error! No bookmark name given.

张一飞

我们只关心,对于一个初始局面,究竟是先行者(甲)有必胜策略,还是后 行者(乙)有必胜策略。 游戏 C 的规则和游戏 A 并不那么相似。但是,前面所列出的,游戏 A 的关 键性质,游戏 C 却都具有。比如说,图 2 所示的初始局面可以用三元组(7, 3, 3) 来表示,它的胜负情况与初始局面(7)相同。 游戏 A 的解答是由它的性质得出来的。因此,我们猜想游戏 C 是否也能用 类似的方法来解。

六、 精华 2? ? 回忆游戏 A 的结论,以及它在游戏 B 上的推广,对于游戏 C,我们的想法是 Z? ? 设计一个函数 f,把函数 f 的值看作是二进制数。对于任意一个初始局面 S,
设 S=(a1, a2, …, an),令#S=f(a1)+f(a2)+…+f(an)。若#S≠0,则先行者(甲)有 必胜策略;否则#S=0,这时后行者(乙)有必胜策略。

G? ? 游戏 A 中,f(x) = x。 G? ? 游戏 B 中,f(x) = x mod (m + 1)。 G? ? 游戏 C 中,f(x) = ?。

2? ? 关键就在于如何构造一个满足要求的函数 f。

2? ? 回忆关于游戏 A、B 的结论的证明过程 @? ? 函数 f 是否满足要求,关键在于#S 是否满足下面的条件。 ?? ? 若#S=0,则无论先行者如何取子 S→T,都有#T≠0。 ?? ? 若#S≠0,则先行者必然存在一种取子方法 S→T,且#T=0。

- 12 -

Error! No bookmark name given.

张一飞

F? ? 用符号$(x),表示局面(x)的下一步所有可能出现的局面的集合。 G? ? 在游戏 A 中,$(3)={(2), (1), (0)}。 G? ? 在游戏 B 中,若 m=4,则$(9)={(8), (7), (6), (5)},$(2)={(1), (0)}。 G? ? 在游戏 C 中,$(7)={(5), (1, 4), (2, 3)}。 F? ? 定义集合 g(x):设$(x)={S1, S2, …, Sk},则 g(x)={#S1, #S2, …, #Sk}。 G? ? 在游戏 A 中,$(3)={(2), (1), (0)},故 g(3)={#(2), #(1), #(0)}={10, 01, 00}。 G? ? 在游戏 B 中,若 m=4,则 g(9)={#(8), #(7), #(6), #(5)},g(2)={#(1), #(0)}。 G? ? 在游戏 C 中,g(7)={#(5), #(1, 4), #(2, 3)}。
(5) (1, 4) (7) (2, 3)

$(7)={(5), (1, 4), (2, 3)}

G? ?

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 -

Error! No bookmark name given.

张一飞

00101 10011 10111 + 00001 00000

f(a1) f(a2) f(a3) f(a4) p=0 +

00101

f(a1)

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

00101 f(a1) + 00000 p=0

f(a1)

p≠0

G? ? ?? ? 若#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 10011 00111 + 10111 00110

f(a1) f(a2) f(a3) f(a4) p≠0 +

00101

f(a1)

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

00011

x=f(a1)+p<f(a1) +

x

如果 x∈g(a1)

00110

p

p=0

G? ?

- 14 -

Error! No bookmark name given.

张一飞

2? ? 函数 f 满足要求的一个充分条件 ?? ? f(a1)不属于集合 g(a1)。 ?? ? 集合 g(a1)包含集合{0, 1, …, f(a1)–1}。 G? ? 如果 g(a1)={0, 1, 2, 5, 7, 8, 9},则 f(a1)=3,满足要求。

F? ? 用大写字母 N 表示非负整数集,即 N={0, 1, 2, …}。 F? ? 令 N 为全集,集合 G(x)表示集合 g(x)的补集。

F? ? 定义函数 f(n):f(n)=min{G(n)},即 f(n)等于集合 G(n)中的最小数。 F? ? 设局面 S=(a1, a2, …, an),#S=f(a1)+f(a2)+…+f(an),采用二进制数的加法。 *? ? 若#S=0,则 S 负;若#S≠0,则 S 胜。

G? ? 游戏 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; G? ? 图 2 所示的局面 S=(7, 3, 3),有#S=f(7)+f(3)+f(3)=1+1+1=1,故 S 胜。 G? ? 游戏 C 的初始局面 S=(3, 4, 6),有#S=1+2+3=01+10+11=0,故 S 负。
- 15 -

Error! No bookmark name given.

张一飞

七、 结论 2? ? 此类搏弈游戏的一般性解法: F? ? 用一个 n 元组(a1, a2, …, an),来描述游戏过程中的一个局面。 F? ? 用符号#S,表示局面 S 所对应的二进制数。 F? ? 用符号$(x),表示局面(x)的下一步所有可能出现的局面的集合。 F? ? 定义集合 g(x):设$(x)={S1, S2, …, Sk},则 g(x)={#S1, #S2, …, #Sk}。 F? ? 令非负整数集为全集,集合 G(x)表示集合 g(x)的补集。 F? ? 定义函数 f(n):f(n)=min{G(n)},即 f(n)等于集合 G(n)中的最小数。 F? ? 设局面 S=(a1, a2, …, an),#S=f(a1)+f(a2)+…+f(an),采用二进制数的加法。 *? ? 若#S≠0,则先行者有必胜策略;若#S=0,则后行者有必胜策略。

2? ? 适用范围和限制条件: ?? ? 甲乙两人取石子游戏及其类似的游戏; ?? ? 每一步只能对某一堆石子进行操作; ?? ? 每一步操作的限制,只与这堆石子的数目或一些常数有关; ?? ? 操作在有限步内终止,并不会出现循环; ?? ? 谁无法继续操作,谁就是输家。

2? ? 游戏 D(POI’2000,Stripes) : 2? ? 一排石子有 L 个,甲乙两人轮流从中取“紧紧挨着的”A 或 B 或 C 枚石子。
谁不能取了,谁就是输家。已知 A, B, C, L,问甲乙二人谁有必胜策略。

J? ? 有了前面的结论,这个游戏就难不倒我们了。
- 16 -

Error! No bookmark name given.

张一飞

八、 总结

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 -

Error! No bookmark name given.

张一飞

人们认识事物的过程,就是由感性认识上升到理性认识的过程。具体到解这 类游戏,就是要从简单入手。当我们遇到了一个复杂的问题,或许人人都知道从 简单入手,但却并不是每个人都能从中得到一般性的规律。那么,我们究竟是如 何由浅入深的呢? 两堆数目相等的石子——这是个很简单的局面。我们就由此入手,将一堆石 子与一个子局面相类比,并得出了两个子局面相等时的结论。在此基础上,我们 研究了局面的胜负和其子局面的关系, 并得出结论: 可以用集合来描述一个局面。 但我们并没有停留在这一步,而是将局面的分解与二进制数的加法相类比,从而 发现了局面与二进制数之间的关系。我们称这个过程为“由此及彼” 。 通过分析“用集合来表示一个局面”的结论,我发现这实质上是简化了局面 的表示,从而联想到能否进一步化简,比如说用一个数来表示。在解游戏 C 时, 我们并不在意它与游戏 A 的规则有多大的区别,而是注意到它与游戏 A 有着相 似的性质,从而想到用类似的方法解游戏 C。我们称这个过程为“由表及里” 。 在解游戏 A 和 B 的过程中,我们积累了很多经验。但在解游戏 C 时,我们 却仅仅提到了解游戏 A 和 B 的精华:构造一个函数 f。这就是“去粗取精” 。 将局面与二进制数相类比,我们先试着把局面的胜负直接与二进制的 1 和 0 相类比。发现不妥后,再将其改为与二进制数来类比。这一步叫“去伪存真” 。
“由此及彼、由表及里、去粗取精、去伪存真” ,这就是由感性认识上升 到理性认识的关键。

- 18 -


算法合集之《解析一类组合游戏》

算法合集之《解析一类组合游戏》_IT/计算机_专业资料。【关键字】 组合游戏 游戏的和 nim和 Sprague-Grundy函数 【摘要】 本文的主要内容是分析组合游戏的方法。 ...

一类博弈问题的解决思路(经典)

解析一类组合游戏 16页 免费 算法合集之《由感性认识到... 18页 免费 张一飞...-2- 由感性认识到理性认识——透析一类搏弈游戏的解答过程 张一飞 ? 改变这个 ...

算法合集之《一类猜数问题的研究》

算法合集之《一类猜数问题的研究》_IT/计算机_专业资料。【摘要】 猜数问题是信息学竞赛中一种常见的类似博弈的问题。其中部分的问题是给出猜的数与被猜数之间的...

算法合集之《结果提交类问题》

算法合集之《结果提交类问题》_IT/计算机_专业资料。【关键词】 结果提交 数据分析 随机化 策略 【摘要】 结果提交类问题的历史非常短,但其崭新的模式、效率观、...

算法合集之《浅谈类比思想》

11页 免费 算法合集之《多串匹配算法... 37页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

算法合集之《正难则反–浅谈逆向思维在解题中的应用》

算法合集之《正难则反–浅谈逆向思维在解题中的应用》_高三数学_数学_高中教育...我们应用逆向思维, 在原集合的模 S i 不可解的情况下,通过可解的 S i ...

算法合集之《一类称球问题的解法》

4页 免费 算法合集之《由感性认识到... 18页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

算法合集之《探索构造法解题模式》

​之​《​探​索​构​造​法​解​题​模​式​》...但认识问 题的最终目的是解决问题, 模型的固有性质可帮我们建立算法,其优劣可以...

算法合集之《非完美算法初探》

21页 免费 算法合集之《pálya计数法... 40页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

算法合集之《数据关系的简化》

17页 免费 算法合集之《转化目标在解... 15页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...