博弈论

博弈论和$SG$函数

发现原来学的东西都忘了,一方面是第一遍不是很懂,还有就是做题不多,于是重新回顾了一下

博弈,其实差不多明白本质是状态与状态之间的转化就好了

常见博弈

$1.$巴什博弈

一堆石子$n$个,取$1-m$个,$n=m+1$先手必败,$n=k(m+1)+r$先手必胜,因为我们总能到另一个$n=k_1(m+1)+r_1$状态,最后我们是$(m+1),$必胜

$2.$尼姆博弈

偶状态必败,奇状态必胜,异或判断即可

$3.$威佐夫博弈

奇异状态必败,否则必胜

$(a_k,b_k)$为奇异状态当且仅当$a_k=k\times\lfloor\frac{\sqrt 5+1}{2}\rfloor,b_k=a_k+k$

$SG$函数

结论$:$游戏和的$SG$函数等于各个游戏的$Nim$和

大概就是我们这个和游戏当前状态的$SG$等于构成这个游戏的所有游戏的状态的$Nim$和

$SG$函数可以形式化定义为

$SG(x)=mex(SG(a),SG(b),SG(c)...)$

其中$a,b,c$为$SG$的后继状态

其实$SG$函数可以看做我们之前$Nim$游戏的每个状态,然后异或起来得到的结果判定胜负