博弈论（nim游戏，SG函数）

说到自己，就是个笑话。思考问题从不清晰，sg函数的问题证明方法就在眼前可却要弃掉。不过自己理解的也并不透彻，做题也不太行。耳边时不时会想起alf的：“行不行！”，“遇到问题，三个字“下一道”！”我真的乐了！

基本的小概念

• 这里我们讨论的是公平游戏（ICG游戏：Impartial Combinatorial Games），满足：
  1.双方每步的限制相同（轮流）
  2.游戏有尽头
• 对于当前局面的玩家如果能有必胜策略，那就是N局面（反之，P局面）

SG函数

• 每一种决策以及后面的所有可能可以抽象成有向无环图，而sg函数的计算就类似图上dp的过程。
• 若当前的局面是now,下一步的局面为to
  \(SG[now]=Mex(SG[to])\)
  \(Mex(S)\)表示，最小的没有在\(S\)集合里的非负整数
  这就是SG的定义了，这很迷糊，因为它就是一个当前局面的估价，很难说它具体是什么意义（甚至后面还会用它来运算就离谱）
• 显然的性质
  1.SG[now]后面存在了sg为0的局面，now就为N局面，你接下来你的操作也会move到\(sg[to]=0\)这种局面。
  2.1的反之。
  3.SG为0表示当前局面P，否则为N。（ps.三个点就是一个结论，3总结1，2）
• Muiti-SG的性质（见nim游戏后）

nim游戏

• 这是最基本最重要的游戏，理解它后，你将入门博弈。
• 规则：两个人玩nim游戏，有n堆石子，每堆有\(a_i\)个，每次可从一堆中取走任意多个石子。如果一个人无石子可取就输。
• 结论：\(xorsum\ =\ a_1\ xor\ a_2\ xor\ a_3\ xor\ ...\ xor\ a_n\)是0就为P局面，否则N局面。
• 证明：如果xorsum=0，取后xorsum!=0; 如果xorsum!=0,一定存在从一堆（堆i)取走\(a_i-xorsum\ xor\ a_i\)个石子，使取后\(xorsum=0\)
  然后最终输的状态为全0，这是xorsum=0的。而如果一开始为xorsum=0一定被拿捏，一直xorsum=0直到输掉（对面就一直使你xorsum=0)
• 这时，你肯定会想：用sg暴力做呢？状态存不下啊。当然就引出了后面有关sg的重要推论……
  不过对于只有一堆（或者想成n堆每堆独立）\(sg[i]=i\)的。（i为还剩的石子个数）

重要推论

• 从上面，或许我们能猜想：
  S局面被拆分成\(n\)个相互独立的小局面，（我们这里叫S为\(s_1->s_n\)的游戏和，满足：
  \(SG[S]\ =\ SG[s_1]\ xor\ SG[s_2]\ ....\ xor\ SG[s_n]\)
  这个对于公平游戏来讲，居然是正确的。证明?->
• 证明：
  我们通常遇到博弈想最终态（P态为多，因为sg=0)
  当然是所有sg值全为0的时候。
  你每次只能转移一个小局面(一堆石子），它能转移到0~sg[i]-1以及sg[i]+k,k是不确定的。
  你发现如果没有sg[i]+k我们可以用nim游戏来证明。
  如果有，相当于加石子，实质上还是符合nim游戏证明中的异或和总是=0和!=0相交替。
  加和减因此也没有实质区别，就得证。
• ps.老板告诉我们可以把任何ICG问题转化为相同sg值（=石子个数）的nim游戏。

小结：

nim类，或者ICG类都感觉核心就用到以上几个结论。不过我太菜了，还是做不来题。博弈论还有很多值得探索，不过现实中人也没有那么理性，很多时候也用不到。
后面会补一些题目，我退了，拜拜……