- 由两名玩家交替行动
- 游戏进程的任意时刻,可以执行的合法行动与轮到的玩家无关
- 若当前玩家无法行动,则判负
则称该组合游戏为公平组合游戏。如NIM游戏等即是经典的公平组合游戏。而许多游戏虽然形式上与公平组合游戏相差较大,但可以等价转为公平组合游戏。而如围棋等不是公平组合游戏。如交战中一方仅可以落白子,而另一方仅可以落黑子,操作与所在身份有关;同时胜负的判定也比较复杂,不满足条件3。因此围棋不是公平组合游戏。
进一步理解对于第三条,我们有更进一步的定义Position,我们将Position分为两类:
-
P-position:在当前的局面下,先手必败
-
N-position:在当前的局面下,先手必胜
它们有如下性质:
-
合法操作集合为空的局面是P-position
-
可以移动到P-position的局面是N-position
-
所有移动都只能到N-position的局面是P-position
按照这个定义,如果局面不能重现,或者说不同局面之间存在着拓扑排序的关系,那么对游戏中的所有局面,要么为P局面,要么为N局面,同时可以使用定义依据拓扑顺序进行计算。
NIM游戏 定义NIM游戏的经典定义是:给定n个石堆,每一个石堆的数目为 A i A_i Ai,游戏双方轮流行动,每一个人只能选定一个非空石堆取走一定数目的石子,当某一个人没有石子可取时判定为负。问给定所有石堆数目,是否存在先手必胜局面。
一般思路由NIM游戏的性质可以发现其满足ICG游戏的要求,因此存在着P局面与N局面。例如存在着三堆石子,则数目为 ( 0 , 0 , 0 ) (0,0,0) (0,0,0)时是必败局面,则当数目为 ( 1 , 0 , 0 ) / ( 0 , 1 , 0 ) / ( 0 , 0 , 1 ) (1,0,0)/(0,1,0)/(0,0,1) (1,0,0)/(0,1,0)/(0,0,1)时,由于可以转移到 ( 0 , 0 , 0 ) (0,0,0) (0,0,0)这个必败局面,因此三者均是必胜局面。
由上述分析可知,对于每一个局面,我们都可以通过枚举其可以转移的局面进行搜索,从而根据每一个局面的后继局面状态得到当前局面是必胜还是必败。
实现代码如下:
bool calc(int a[], int n)
{
bool flag = false;
for( int i = 1; i <= n; i++ )
{
if(a[i] > 0)
{
for( int j = 1; j <= a[i]; j++ )
{
a[i] = a[i] - j;
flag |= !calc(a, n);//当后继局面有必败,则当前局面必胜
a[i] = a[i] + j;
}
}
}
return flag;
}
上述搜索使用记忆化搜索时,时间复杂度为 O ( ∏ A i ) O(prod A_i) O(∏Ai)。
进一步优化NIM游戏先手必胜,当且仅当 A 1 x o r A 2 x o r A 3 x o r . . . A n ≠ 0 A_1 space xor space A_2 space xor space A_3 space xor...A_nne0 A1 xor A2 xor A3 xor...An=0。
证明:使用数学归纳法进行证明。
当所有石堆为空,则当前是必败局面,则 A 1 x o r A 2 x o r A 3 x o r . . . A n = 0 A_1 space xor space A_2 space xor space A_3 space xor...A_n=0 A1 xor A2 xor A3 xor...An=0。
当
A
1
x
o
r
A
2
.
.
.
A
n
≠
0
A_1 space xor space A_2 ...A_nne0
A1 xor A2...An=0,设
v
a
l
=
A
1
x
o
r
A
2
x
o
r
A
3
.
.
.
A
n
val = A_1 space xor space A_2 space xor space A_3...A_n
val=A1 xor A2 xor A3...An,则设
v
a
l
val
val不为0的最高位为第
k
k
k位,则在
A
1
A_1
A1到
A
n
A_n
An中必定存在
A
i
A_i
Ai的第
k
k
k位为1,且
A
i
x
o
r
v
a
l
<
A
i
A_ispace xorspace val < A_i
Ai xor val 当
A
1
x
o
r
A
2
x
o
r
A
3
x
o
r
.
.
.
A
n
=
0
A_1space xorspace A_2space xorspace A_3space xor...A_n=0
A1 xor A2 xor A3 xor...An=0,则无论如何取石子,都不可能使得所有石子异或和为0。不妨使用反证法证明上述观点,若取了第
i
i
i堆石子之后由
A
i
A_i
Ai变为
a
i
a_i
ai且
A
1
x
o
r
A
2
x
o
r
.
.
.
a
i
x
o
r
.
.
A
n
=
0
A_1space xorspace A_2space xor...a_ispace xor..A_n=0
A1 xor A2 xor...ai xor..An=0,则由异或的消去律可以得到
A
i
x
o
r
a
i
=
0
A_ispace xorspace a_i=0
Ai xor ai=0。又因为
a
i
<
=
A
i
a_i<=A_i
ai<=Ai,所以仅可能
a
i
=
A
i
a_i = A_i
ai=Ai成立。而这与每一次必须取非0石子数矛盾。 我们不妨把异或和为0视为P局面,异或和不为0视为N局面,则上述关系与NP局面之间的判定关系等价,因此可以认定对于任何一个局面,当异或和不为0,则先手必胜。 根据上述性质,我们不仅可以在
O
(
n
)
O(n)
O(n)时间内判定当前局面是否先手必胜,还可以根据上述转移关系在
O
(
n
)
O(n)
O(n)时间内找到所有先手必胜策略。 上述NIM游戏仅是较为简单的一类游戏形式,而接下来介绍的有向图游戏形式更为一般。 给定一张有向图,其上有一个唯一起点,在起点上有唯一的一个棋子。交战双方轮流将这个棋子沿着有向边进行移动,每一次移动一步,直到无法移动时判负。 不妨将有向图中的有向边视为不同局面之间存在的合法转移关系。一次沿一条有向边进行移动,相当于把游戏从一个局面转移到另一个局面,当最后无法移动时,即是对应的玩家无法行动。 由上述分析可以看出,有向图游戏其实就是
I
C
G
ICG
ICG游戏的图形化,二者完全等价。 设
S
S
S是一个非空整数集合(可为空),定义
m
e
x
mex
mex运算如下: 我们在有向图游戏的每一个节点定义
S
G
SG
SG函数。在有向图游戏中,称
y
y
y是
x
x
x的后继,当且仅当存在一条有向边由
x
x
x指向
y
y
y。则有 当
x
x
x不存在后继,则
S
G
(
x
)
=
0
SG(x)=0
SG(x)=0,此时
x
x
x无法行动,对应P局面。 当
x
x
x的后继中存在着
y
y
y使得
S
G
(
y
)
=
0
SG(y)=0
SG(y)=0,则
S
G
(
x
)
≠
0
SG(x)ne 0
SG(x)=0,对应N局面。 当
x
x
x的后继中不存在
y
y
y使得
S
G
(
y
)
=
0
SG(y)=0
SG(y)=0,则
S
G
(
x
)
=
0
SG(x)=0
SG(x)=0,对应P局面。 我们将NIM游戏抽象为一张有向图游戏,则双方轮流行动,每一次只能操作一堆石子,对应有向图游戏上只有一个棋子。那有向图中所有点的
S
G
SG
SG函数值恰好对应了当前局面是否必胜。 当有向图游戏中不是仅有一个棋子,而是存在着
n
n
n个棋子,此时我们考虑
S
G
SG
SG函数的意义。当
S
G
(
x
)
=
k
SG(x)=k
SG(x)=k时,则对于任意
i
i
i且
0
<
=
i
<
k
0<=i 对比NIM游戏,对于每一个石堆,设当前石子的数目为
k
k
k,我们可以把数目变为小于
k
k
k的任意非负整数,但不能保持为
k
k
k。 如果我们把节点的
S
G
SG
SG函数值看为石堆的石子数,可以发现两者之间存在某种相似。但不同的是,石堆的石子数只能减少不能增加,而有向图中从一个点到其后继,节点的
S
G
SG
SG函数值可能会增加。但利用上述分析NIM游戏先手必胜对应异或和不为0的方法,我们可以完全等价地证明:当所有棋子对应的节点的
S
G
SG
SG函数异或值不为0时,一定存在某种策略,移动其中某一个棋子让所有节点
S
G
SG
SG值异或和为0;当所有棋子对应节点的
S
G
SG
SG函数异或值为0时,移动任一个棋子一定会使
S
G
SG
SG值异或和不为0。因此将n个棋子视为n个石堆,便转化为了一个NIM游戏,NIM游戏的必胜策略即对应着移动棋子的必胜策略。 **注意:**我们对NIM游戏进行分析时,是将NIM游戏转化为了仅有一个棋子的有向图游戏。而对有n个棋子时,我们把n个棋子对应的
S
G
SG
SG函数值抽象为石堆,便可以利用NIM游戏的思想来寻求最优策略。 可以发现,无论n个棋子是否在同一张有向图上,不影响最优策略的选定。因此我们可以定义有向图游戏的和。 设
G
1
、
G
2
.
.
.
G
m
G_1、G_2...G_m
G1、G2...Gm是
m
m
m个有向图游戏。定义有向图游戏
G
G
G,它的行动规则是任取一个有向图游戏
G
i
G_i
Gi,并在
G
i
G_i
Gi上行动一步。
G
G
G被称为有向图游戏
G
1
、
G
2
.
.
.
G
m
G_1、G_2...G_m
G1、G2...Gm的和。 有向图游戏的和的
S
G
SG
SG函数值定义如下: 上述定义给我们指明了一个重要思想:若当前游戏可以分为多个子游戏,我们只需要分别分析并求取子游戏对应的有向图游戏的
S
G
SG
SG函数值,便可以将这些
S
G
SG
SG函数值视为NIM游戏中的石堆,从而得到全局游戏的最优策略。即是**“分而治之“**的思想。 例如:有n个石堆,每一次只能从第
i
i
i个石堆取
i
i
i的倍数个(第一个石堆即是任意数目),问是否有必胜策略。 我们可以把游戏分为n个子游戏,第一个游戏仅有一个石堆,可以任意取,第二个游戏也仅有一个石堆,只能取偶数个石子,以此类推。则对于第一个游戏即是最简单的"任取石子游戏",若当前有x个石子,则可以转移到0到x-1的任一个局面,因此当前局面的
S
G
SG
SG函数值为x。对于第二个游戏,可以发现石子数目只能从奇数转移到奇数,从偶数转移到偶数,因此当节点对应石子数为偶数个时,则
S
G
SG
SG函数值为1,反之为0。其他石子同理。于是我们便可以得到每一个子游戏的
S
G
SG
SG函数值,进而得到全局的
S
G
SG
SG函数值。 又如NIM游戏其实就是n个“任取石子游戏”的和。很多ICG游戏都可以按照这种方法进行划分,从而简化计算,方便理解。 简洁起见,我们只讨论一堆石子的情形。若当前仅有一堆石子,可选的石子数组成一个序列,则分情况如下: 对于有n堆石子时,我们可以直接分为n个子游戏,每一个子游戏都仅有一个石堆,便可沿用上述结论。 给定一个ICG游戏,我们都可以将其抽象为一个有向图游戏,并且通过合理的划分,分为多个容易计算
S
G
SG
SG函数值的子游戏,利用分而治之的思想解决问题。
m
e
x
(
S
)
=
min
x
∈
N
,
x
∉
S
{
x
}
mex(S)=min_{xin N,x notin S}{x}
mex(S)=x∈N,x∈/Smin{x}
即
m
e
x
mex
mex运算是取出不属于S的最小非负整数。
S
G
(
x
)
=
m
e
x
(
{
S
G
(
y
)
∣
y
是
x
的
后
继
}
)
SG(x)=mex({SG(y)|y是x的后继})
SG(x)=mex({SG(y)∣y是x的后继})
即
x
x
x的
S
G
SG
SG函数值是对其所有后继点的
S
G
SG
SG函数值所组成的集合进行
m
e
x
mex
mex运算得到的结果。
S
G
(
G
)
=
S
G
(
G
1
)
x
o
r
S
G
(
G
2
)
.
.
x
o
r
S
G
(
G
m
)
SG(G)=SG(G_1)space xorspace SG(G_2)..xorspace SG(G_m)
SG(G)=SG(G1) xor SG(G2)..xor SG(Gm)
将m个有向图抽象为m个石堆,
G
G
G的
S
G
SG
SG函数值便指明了m个有向图游戏的先手必胜策略。



