博弈结论小记

博弈结论小记

Nim： 亦或，0必败

阶梯Nim：奇数位置Nim

Moore’s Nimk：

n堆石子从k堆取，取不限量个。 有点像巴士博弈和Nim的合并。

结论：每个二进制位上所有堆的和，整除k+1，则必输，否则必胜。

反nim：

取走最后一个的输。

先手必胜当

1. 每堆石子数均=1，有偶数堆。
2. 至少一堆石子数>1，异或和( ot=0)

反Moore’s Nimk

也是取走最后一个输

先手必胜当

1. 石子规模均为1，堆数mod(k+1) = 1
2. 石子规模不全为1，存在二进制位其和其不整除(k+1)

威佐夫博弈

两堆石子，每次可以取一堆或两堆，从两堆中取得时候个数必须相同，先取完的获胜。

奇异局势先手必输，奇异局势有下性质：

1. 任何自然数只在一个奇异局势里。

2. 任意操作将奇异局势改变为非奇异局势

3. 奇异局势((a_k,b_k),a_k=lfloor k frac{1+sqrt5}{2} floor,b_k=a_k+k)

谢谢Claris：
lasker's game:
若干堆石子，每次可以把一堆分成两堆非空石子 或者 从其中一堆拿走任意石子，不能操作的输
对于k>1 SG(4k)=4k-1 SG(4k+1)=4k+1 SG(4k+2)=4k+2 SG(4k+3)=4k+4

Take&Break Game

把一堆分成k堆，sg(i)=从小到大第i个2进制位里1的位置模k=1的数。//存疑，不过k=2是对的。