专题总结（博弈论）

总结 博弈论

双人平等博弈（理论应用前提）

• 信息完全公开
• 双方轮流行动
• 面对同一局面,双方的决策集合相同
• 一般来说,规定不能操作者输
• 游戏局面不会成环,有限步之后游戏必定结束

$N$态与$P$态

• 首先把结束的局面置为$P$态
• 对于一个$P$态,找到所有能转移到它的状态,它们全部是$N$态
• 搜到一个状态时,它还没有被筛掉,就是$P$态

很多题目中, P 态之间不可直接转移。

一些性质

• $SG$值异或和为$0$即后者胜，对应$P$态。
  证明：每当前者把异或和改变，使其不为$0$，后者总能把异或和重新变为$0$（拿掉相同数量的石子。并且这一定可行，否则异或和怎么为$0$？）。则最后一定是前者面对石子取完的情况。
  而若不为$0$，前者一开始把异或和变为$0$，之后与后者对着干（使异或和为$0$）即可。

• $SG(A+B)=SG(A)\bigoplus SG(B)$

• 如果交换胜负条件，先手胜利：
  1、存在$SG(x)>1$，且异或和不为$0$
  2、$SG(x)=1$，且有偶数堆石子

如何计算$SG$值

总的来说，常规计算$SG$值是一个递推的过程。
一般计算(推导）过程，就是对 所有后继状态（操作后状态）的$SG$值 的异或和取$mex$。

手推一遍$SG$值，发现一些后继状态实际上可由一些单独状态（在翻硬币游戏中）异或而成。根据上面提到的性质二，可以得到一个递推式：
($mex$表示取括号内不包含的 最小非负整数）

应用场景

阶梯博弈

有$N$堆石子放在$N$层阶梯上，每次选择一层的若干石子,放入下一层。(特别地,$1$层的石子就被扔掉)

结论:计算所有奇数层石子数的异或和,得到整个游戏的$SG$

其实这玩意儿讲不完的，还得自己去看课件。

有趣的题目

模板题

• nim游戏 戳

裸板子。

• Bash游戏 戳

只有一堆，限制一次最多只能取$k$个石子。

则$SG[n]=n\%(k+1)$（不信可以递推试试）

中等题

• CF 731E 戳

• CF 794E 戳

• [HEOI2014]人人尽说江南好 戳

• CF 768E 戳

• [ZJOI2009]取石子游戏 戳

$SG$函数相关

• [ZJOI2009]染色游戏 戳

我在题解中写了一份SG计算教程？？？

• [HNOI2014]江南乐 戳

• Alice和Bob又在玩游戏 戳

• CF 494E 戳

• CF 138D 戳

• A tree game 戳
  题解

• [HNOI2007]分裂游戏 戳
  题解
• 小奇的博弈 戳
  题解（这个好像是DP）

分块相关

• [HAOI2015]数组游戏 戳
  题解