• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

由来(doge)

从前,有两个聪明的人,名叫爱丽丝和鲍勃。故事是这样开始的.

基础

\(N\)是一手赢的情况,\(P\)是一手输的情况。

手牌被认为先输的情况,我们可以称之为怪局。

巴什博弈

小学奥数:甲乙轮流报最多77个数,最少11个数。从11开始,谁先报5050谁就赢。先报告,有没有制胜策略?

威佐夫(Wythoff)博弈

两堆里有几样物品,两个人轮流从一堆或者两堆里拿等量的物品。规定一次至少带一件物品,物品数量不限。最后一个拿到光的人赢了。

设两堆还剩\(x,y\)的情况是\((x,y)\)。

小规模暴力导致一个奇怪的情况(两人中最年轻的先来):

\[(0,0),(1,2),(3,5),(4,7),(6,10),(8,13),(9,15),(11,18),(12,20),\dots

\]

我们用\((a_k,b_k)\)。可以看出\ (b _ k=a _ k k,a _ k=\ text {MEX} \ {a _ 1,b _ 1,\ dots,a _ {k-1},b _ {k-1} \})

然后,通过“找规律”得到(如果不相信有人在考场上严谨证明,小范围打表得到):

\[a _ k=\ l地板k \ phi \地板

,

b _ k=\地板k\phi^2\rfloor

,

\ phi=1.618 \点

\]

Nim 博弈

结论:如果异或和为(0),则为(P),否则为(N)。

猜想:可以用来证明一组数在某个二进制中是异或\(0\),在其他二进制中也是异或\(0\)。

Anti-Nim

第一手牌赢:

XOR是\(0\),每堆只有\(1\)颗石子。

异或和不是\(0\),至少有一堆超过\(1\)的石头。

SG(人名 Sprague-Grundy)函数

车道分隔:\(sg(x)=\text{mex}\{sg(son)\}\)

情况:\(sg(x)=\text{xor}\{sg(son)\}\)

树上删边博弈

这是SG的例子。

在树上,我们可以玩这样一个游戏:

给定一个有\(n\)个点的树,其中一个点作为树的根节点。只有两个玩家。

玩家轮流从树上删除边。删除边后,未连接到根节点的部分将被删除。

谁无处可去,谁就输了。

简单的树手推一下各个 SG 值,然后找到规则。

\(SG(RT)=\ text { XOR } \ {(SG(Son)1)\ } \)找到。

不难概括出证明树的大小。

当然,类似的树游戏都差不多,就是SG扩展性好。

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now