组合游戏与博弈论基础

发布于 2022年 01月 24日 00:46

1|0基本定义

1|1策梅洛定理(Zermelo's theorem)

在二人的有限游戏中,如果双方皆拥有完全的资讯,并且运气因素并不牵涉在游戏中,那先行或后行者当一必有一方有必胜/必不败的策略。

即对于游戏局面𝑋X,存在确定的游戏结果𝑃(𝑋)=0 𝑜𝑟 1P(X)=0 or 1𝑠𝑢𝑐𝑐(𝑋)succ(X)𝑋X的后继局面。

1|0推论

  1. 一个状态是必败状态,当且仅当,它的所有后继状态都是必胜状态
    𝑃(𝑋)=0𝑖,𝑃(𝑠𝑢𝑐𝑐(𝑋𝑖))=1P(X)=0i,P(succ(Xi))=1

  2. 一个状态是必胜状态,当且仅当,它的至少一个后继状态是必败状态
    𝑃(𝑋)=1𝑖,𝑃(𝑠𝑢𝑐𝑐(𝑋𝑖))=0P(X)=1i,P(succ(Xi))=0

2|0SG游戏

  • SG游戏定义:没有后继状态为必败状态
    𝑠𝑢𝑐𝑐(𝑋)=𝑃(𝑋)=0succ(X)=P(X)=0

2|1NIM游戏

桌上n堆石子,游戏者轮流在某一堆取若干(>0)个,取走最后一个石子人胜。
最后局面为
𝑋𝑒𝑛𝑑={𝑋1=0,𝑋2=0,,𝑋𝑛=0}Xend={X1=0,X2=0,,Xn=0}
可知NIM游戏是SG游戏。

1|0Bouton定理

在NIM游戏中的必胜状态为:当前局面下所有单堆石子数目的异或和不为0
𝑃(𝑋)=((𝑥1𝑥2𝑥𝑛)0)P(X)=((x1x2xn)0)

1|0单堆NIM游戏

  • SG函数(定义见下)
    𝑆𝐺(𝑥)=𝑥SG(x)=x
  • 游戏结果
    𝑃(𝑥)={01𝑥=0𝑜𝑡𝑒𝑟𝑤𝑖𝑠𝑒P(x)={0x=01otherwise

2|2SG函数

一个游戏局面的SG函数为该局面的后继局面的SG函数集合的mex值
𝑆𝐺(𝑋)=𝑚𝑒𝑥(𝑆)SG(X)=mex(S)
其中
𝑆={𝑆𝐺(𝑠𝑢𝑐𝑐(𝑋1)),𝑆𝐺(𝑠𝑢𝑐𝑐(𝑋2)),𝑆𝐺(𝑠𝑢𝑐𝑐(𝑋𝑛))}S={SG(succ(X1)),SG(succ(X2)),SG(succ(Xn))}
mex表示不在集合内的最小非负整数
𝑚𝑒𝑥(𝑆)=𝑚𝑖𝑛(𝑥|(𝑥)&(𝑥𝑆))mex(S)=min(x|(xR)&(xS))

1|0Sprague-Grundy 定理

游戏和的SG函数等于各子游戏SG函数的NIM和
𝑆𝐺(𝑋)=𝑆𝐺(𝑋1)𝑆𝐺(𝑋2)𝑆𝐺(𝑋𝑛)SG(X)=SG(X1)SG(X2)SG(Xn)
其中
SG游戏局面为若干SG子游戏之和
𝑋=𝑋1+𝑋2++𝑋𝑛X=X1+X2++Xn

1|0SG函数性质

𝑆𝐺(𝑋)=0𝑖,𝑆𝐺(𝑠𝑢𝑐𝑐(𝑋𝑖))0SG(X)=0i,SG(succ(Xi))0
2.
𝑆𝐺(𝑋)0𝑖,𝑆𝐺(𝑠𝑢𝑐𝑐(𝑋𝑖))=0SG(X)0i,SG(succ(Xi))=0
3.
𝑠𝑢𝑐𝑐(𝑋)=𝑆𝐺(𝑋)=0succ(X)=SG(X)=0

  • 在SG游戏(𝑠𝑢𝑐𝑐(𝑋)=𝑃(𝑋)=0succ(X)=P(X)=0)条件下的等价结论

𝑃(𝑋)=0𝑆𝐺(𝑋)=0P(X)=0SG(X)=0
𝑃(𝑋)=1𝑆𝐺(𝑋)0P(X)=1SG(X)0

3|0反SG(Anti-SG)游戏

  • Anti-SG游戏定义:决策集合为空的为必胜状态
    𝑠𝑢𝑐𝑐(𝑋)=𝑃(𝑋)=1succ(X)=P(X)=1

3|1反NIM (Anti-NIM)游戏

桌上n堆石子,游戏者轮流在某一堆取若干(>0)个,取走最后一个石子人

1|0单堆反NIM游戏

  • SG函数:不变
    𝑆𝐺(𝑥)=𝑥SG(x)=x
  • 游戏结果:判断标准改变
    𝑃(𝑥)={01𝑥=1𝑜𝑡𝑒𝑟𝑤𝑖𝑠𝑒P(x)={0x=11otherwise
    解释:
  1. 若堆中有1个石子,根据定义,为必败状态。
  2. 若堆中有0个石子,根据定义,为必胜状态。
  3. 若堆中石子数目大于1,存在导致必败状态的取法:取剩下1个石子,因此为必胜状态。

1|0反NIM游戏的游戏结果

𝑃(𝑋)={𝑆𝐺(𝑋)=0𝑆𝐺(𝑋)0𝑖,𝑥𝑖=1𝑜𝑡𝑒𝑟𝑤𝑖𝑠𝑒P(X)={SG(X)=0i,xi=1SG(X)0otherwise

3|2Sprague Grundy——Jia Zhihao 定理

对于任意一个 Anti-SG 游戏,如果我们规定当局面中所有的单一游戏的 SG 值为 0 时,游戏结束,则先手必胜当且仅当:

  1. 游戏的 SG 函数不为 0 且游戏中某个单一游戏的 SG 函数大于 1;
  2. 游戏的 SG 函数为 0 且游戏中没有单一游戏的 SG 函数大于 1。
    即,在Anti-SG游戏(𝑠𝑢𝑐𝑐(𝑋)=𝑃(𝑋)=1succ(X)=P(X)=1)条件下的等价结论
    𝑃(𝑋)={𝑆𝐺(𝑋)=0𝑆𝐺(𝑋)0𝑖,𝑆𝐺(𝑋𝑖)1𝑖,𝑆𝐺(𝑋𝑖)>1P(X)={SG(X)=0i,SG(Xi)1SG(X)0i,SG(Xi)>1

1|0引论

“规定当局面中所有的单一游戏的 SG 值为 0 时,游戏结束”过于严格, 完全可以替换成“当局面中所有的单一游戏的 SG 值为 0 时,存在一个单一游戏它的 SG 函数能通过一次操作变为 1”。
(𝑖,𝑆𝐺(𝑋𝑖)=0)&(𝑖,𝑆𝐺(𝑠𝑢𝑐𝑐(𝑋𝑖))=1)𝑃(𝑋)=1(i,SG(Xi)=0)&(i,SG(succ(Xi))=1)P(X)=1

4|0SG游戏和反SG游戏模型

除了上述提到的NIM游戏和反NIM游戏,还存在几类博弈论组合游戏中的经典变体。

4|1巴什博弈(Bash game)

有一堆总数为n的物品,2名玩家轮流从中拿取物品。每次至少拿1件,至多拿m件,不能不拿,最终将物品拿完者获胜。
(单堆NIM游戏变式-有上限的单堆NIM游戏)

1|0巴什博弈游戏结果

在先取完者胜的巴什博弈中,若n可被m+1整除,则先手必败,否则先手必胜。
𝑃(𝑛)=((𝑛%(𝑚+1))0)P(n)=((n%(m+1))0)

1|0反巴什博弈(Anti-Bash game)游戏结果

在先取完者败的反巴什博弈中,若n整除m+1的余数为1则先手必败,否则先手必胜。
𝑃(𝑛)=((𝑛%(𝑚+1))1)P(n)=((n%(m+1))1)

4|2威佐夫博弈(Wythoff's game)

有两堆各若干个物品,两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

1|0奇异局势

𝑋=(𝑎[𝑘]𝑏[𝑘]),𝑘,𝑃(𝑋)=0X=(a[k]b[k]),kR,P(X)=0
𝑎[0]=𝑏[0]=0a[0]=b[0]=0,𝑎[𝑘]a[k]是未在前面出现过的最小自然数,即𝑚𝑒𝑥({𝑎[0],𝑎[1],,𝑎[𝑘1],𝑏[0],𝑏[1],,𝑏[𝑘1]})mex({a[0],a[1],,a[k1],b[0],b[1],,b[k1]}),而 𝑏[𝑘]=𝑎[𝑘]+𝑘b[k]=a[k]+k

1|0Betty 定理 (Betti theorem)

𝑎a𝑏b是正无理数且 1𝑎+1𝑏=11a+1b=1。记𝑃={𝑛𝑎𝑛+}P={na|nN+}𝑄={𝑛𝑏𝑛+}Q={nb|nN+},(𝑥x指的是取𝑥x的整数部分𝑓𝑙𝑜𝑜𝑟(𝑥)floor(x)),则𝑃P𝑄Q+N+的一个划分,即𝑃𝑄=ØPQ=Ø𝑃𝑄=+PQ=N+

1|0Betty序列

𝑎[𝑛]a[n]𝑏[𝑛]b[n]是Betty序列,可以通过Betty定理求解。

𝑎𝑛=[α𝑛],𝑏𝑛=[β𝑛]an=[αn],bn=[βn],有 𝑎𝑛+𝑛=[(α+1)𝑛]=[β𝑛]an+n=[(α+1)n]=[βn],解方程 1α+1+1𝛼=11α+1+1α=1

α=5+12,β=α+1α=5+12,β=α+1

𝑎𝑛=[5+12𝑛]an=[5+12n]𝑏𝑛=𝑎𝑛+𝑛bn=an+n (方括号[𝑥][x]表示四舍五入取整函数𝑟𝑜𝑢𝑛𝑑(𝑥)round(x))

5|0参考资料

  1. 百度百科
  2. 维基百科
  3. 《算法竞赛入门提高》刘汝佳
  4. 国家集训队论文集2009-贾志豪

__EOF__

本文作者炯炯目光
本文链接https://www.cnblogs.com/jjmg/p/15645777.html
关于博主:正在努力的ACM狗
版权声明:欢迎分享或转载
声援博主:To be or not to be, is a question.

推荐文章