计算机课件博弈基础

・・

•♦♦

♦♦••

•••

•••

博弈基础

卓越

2010年7月13日

ACMInternationalCollegiate

ProgrammingContest

主要内容•••

一例子

二组合游戏

三Nim取石子游戏

四Sprague-Grundy函数

五常见模型

ACMInternationalCollegiate

ProgrammingContest

主要内容•••

一例子

二组合游戏

三Nim取石子游戏

四Sprague-Grundy函数

五常见模型

ACMInternationalCollegiate

ProgrammingContest

取石子游戏•・

••

N个石子，两个人轮流取，每次可以取1个,

2个或3个，谁取到最后一个石子就算谁赢,

当N=23时，如果你先取，你有必胜策略

吗？

找平衡态!

ACMInternationalCollegiate

ProgrammingContest

主要内容•••

一例子

二组合游戏

三Nim取石子游戏

四Sprague-Grundy函数

五常见模型

ACMInternationalCollegiate

ProgrammingContest

主要内容•••

一例子

二组合游戏

三Nim取石子游戏

四Sprague-Grundy函数

五常见模型

ACMInternationalCollegiate

ProgrammingContest

组合游戏

•概念：

1.两个玩家r、

2.存在一个状态的集合

3.规则确定了每个选手在每个状态转向的其他状态

（对等与不平等）/

4.选手轮流进行操相',

5,不能进行操作时，游戏结束，其中一方胜，另一

4输£

6.游戏在雅艮步内结束

ACMInternationalCollegiate

ProgrammingContest

必胜与必败态•■•

不失一般性，考虑终止状态算输。

P-position：必败态

定义：|

1.所有的终止状态是必败态

2.若当前的状态所能到达的状态都是必胜态,

则当前状态是必败态。

N-positw：如何定义？

儡某扁状态是必败态

ACMInternationalCollegiate

ProgrammingContest

练一练••

•N个石子，两个人轮流取，每次可以取1个,

2个或3个，谁取到最后一个石子就算谁输。

算一算23以内的N/P-position

•初始时有2个盒子，分有有m和n颗石子

（m>0且n>0）,每次把一个盒子清空，然后

把另一个盒子里的石子分成两部分（非0）,

放入崎盒子中。

ACMInternationalCollegiate

ProgrammingContest

主要内容•••

一例子

二组合游戏

三Nim取石子游戏

四Sprague-Grundy函数

五常见模型

ACMInternationalCollegiate

ProgrammingContest

主要内容•••

一例子

二组合游戏

三Nim取石子游戏

四Sprague-Grundy函数

五常见模型

ACMInternationalCollegiate

ProgrammingContest

•♦・

取石子游戏•■•

Nim••

•有n堆石子，每次可以从任意一堆中取任意

多个石子，至少得取一个，谁取走最后一

个石子就算谁赢。（5,7,9）

•引入一种位运算

ACMInternationalCollegiate

ProgrammingContest

异或

••

•1A1=0

0A0=0

0A1=1

1A0=1

满足性质：

交换律aAb=bAa

结合律(aAb)Ac=aA(bAc)

消去律aAc=bAc=>a=b

ACMInternationalCollegiate

ProgrammingContest

Nim-sum

•设Nim游戏中每堆石子的规模分别是

x1,x2,...,xn,贝Unim-sum=x1Ax2A...Axn,

当nim-sum=0时，该状态是P-position,

否则是N-position

•(5,7,9)=5A7A9=11

ACMInternationalCollegiate

ProgrammingContest

证明

••

•1•终止状态nim・sum=0

,2.若当前状态的nim-sum=0,则所能到达

的所有状态nim-sum!=0

•3.若当前状态的nim-sum!=0,则存在一个

后继状态的nim-sum=0

ACMInternationalCollegiate

ProgrammingContest

•♦♦

♦♦*

扩展••

•如果有必胜策略，如何求第一步的策略?

第一步有几种方法可以保证取胜？

ACMInternationalCollegiate

ProgrammingContest

思考题•■•

•Nimk游戏，n堆石子，每次可以从任意k堆

（k已给定）中取石子，至少取1个，谁取

到最后1个石子就算赢，如果判断局面？

•结论：P-position当且仅当把每堆石子用2

进制表示时，每一位的和都能被k+1整除。

ACMInternationalCollegiate

ProgrammingContest

主要内容•••

一例子

二组合游戏

三Nim取石子游戏

四Sprague-Grundy函数

五常见模型

ACMInternationalCollegiate

ProgrammingContest

主要内容•••

一例子

二组合游戏

三Nim取石子游戏

四Sprague-Grundy函数

五常见模型

ACMInternationalCollegiate

ProgrammingContest

Sprague-Grundy函数

•游戏图

有向无环图G=(X,F)

结点：状态集合X

拓扑关系：状态转移F

1.状态x所能到达的状态是F(x)

2,终止状态x的F(x)=①

ACMInternationalCollegiate

ProgrammingContest

Sprague-Grundy函数.；

•定义：在图G=(X,F)中，g的定义域是X

,值域为非负整数。

g(x)=min{n>=0:n#g(y)foryeF(x)}

•g(x)的定义同样满足N/P・position的关系且

包含更多的信息。

ACMInternationalCollegiate

ProgrammingContest

求SG值

•1.subtraction

•2.nim中的一堆

•3,每次取当前堆数的因子数个石子

ACMInternationalCollegiate

ProgrammingContest

有向图游戏的和•■•

•设G1、G2、.・・...、Gn是n个游戏图，定义

游戏G是G1、G2、.・・・・.、Gn的和(Sum),

游戏G的移动规则是：任选一个子游戏Gi

并对该游戏进行操作。

ACMInternationalCollegiate

ProgrammingContest

•♦・

♦♦••

Sprague-GrundyTheorem••::

=

•对于GG[+G2+........Gn

AA

g(”x-…，xn)=g/x/g?(x2)...gn(xn)

•证明：

•1,对任意一个局面X=(x1,X2,・・.，Xn),设b=

AA

=g1(Xi)Ag2(X2)...gn(Xn)，则对任意a<b

,都存在X的后继局面，它的SG值是a

•2,不存在x的后继，它的SG值是b

■通函

ACMInternationalCollegiate

ProgrammingContest

应用•••

••

•考虑3个游戏的组合，第一个游戏的nim,

第二个游戏是subtraction,第三个游戏是每

次取当前堆数的因子数个石子。

•从一堆中取1个或2个，如果愿意，可以把

石子分成两堆。

ACMInternationalCollegiate

ProgrammingContest

主要内容•••

一例子

二组合游戏

三Nim取石子游戏

四Sprague-Grundy函数

五常见模型

ACMInternationalCollegiate

ProgrammingContest

主要内容•••

一例子

二组合游戏

三Nim取石子游戏

四Sprague-Grundy函数

五常见模型

ACMInternationalCollegiate

ProgrammingContest

■

推荐阅读••

1.《GameTheory》ThomasS.Ferguson

2.《由感性认识到理性认识——透析一类搏

弈游戏的解答过程》张一飞

3.《浅析解”对策问题”的两种思路》骆

骥

4：《组合游戏略述——浅谈SG游戏的若干

拓展及变形》贾志豪

ACMInternationalCollegiate

ProgrammingContest

推荐题目

HDU184