2014.1.26开坑

听蔡大神讲了好多。

//不定时不定期填坑

=======================================================================================

无聊的定义

｛//用括号注释（无视）掉

P位置和N位置(先手必败状态和先手必胜状态)
我们会发现对于N位置和P位置有一些性质，这些性质的前提是，这是公平游戏，且有终点。
(1) 终点是P位置。
(2) 所有P位置能转移到的都是N位置
(3) N位置至少能转移到一个P位置
（也就是轮到你走时无论怎么走都输，那你就输定了，那么你就是p位置。如果轮到你走时你可以走一步让别人接下来无论怎么走都输，那你就是N位置。）

3.Nim和
首先，我们定义nim和为两个数或多个数在二进制下的异或和(异或和部分不作展开介绍，请不懂的读者自行找资料)。我们定义“⊕”为Nim和的运算符号。例如，如果x与y的Nim和是z，那么我们表示为 x⊕y=z。

波顿定理。
波顿定理：对n堆火柴(x1,x2,x3,...,xn)，若x1⊕x2⊕...⊕xn = 0，则这个状态为P位置，否则为N位置。

sg函数
定义：g(x) = min{n ≥ 0 : n ≠ g(y) | y ∈ F(x)}（F(x)表示x的后继）
不存在于x的所有后继的SG值中的最小值。
比如F(x)=｛1，2，3｝且g(1)=1,g(2)=2,g(3)=3那么g(4)=0
再比如F(x)=｛1，2，3｝且g(1)=0,g(2)=2,g(3)=3那么g(4)=1
如果g(x)=0，显然这是个P位置，如果g(x)≠0，显然这是个N位置。

SG定理
SG定理：母游戏的SG值等于其各个子游戏的SG值的Nim和。

｝

 =================================================================================

http://blog.csdn.net/kk303/article/details/6692506

题目合集

博弈论