博弈的意思就是下棋，这个没什么好解释的-------来自@月桂醛聚醚硫酸酯钠 dalao

博弈论

NIM博弈

1

平面上有两堆石子，现在Alice和Bob轮流取石子。

每次每个人只能取其中一堆石子，不能不取。

取不了石子的输。求先手必胜的状况。

 

当两堆石子不同的时候是先手必胜。

这时候只需要先手把两堆石子取到相同。

然后后手拿多少先手拿多少就行。

2

还是上题，只是平面上有N堆石子，每堆有$a_i$个。

 

当a的异或和等于0时后手必胜，否则先手必胜。

证明：首先当所有的棋子数目都0时候是一个必败局面，此时异或和为0。

我们假设所有异或和为0的局面为必败局面，否则为必胜局面。除了最终局面之外，所有必败局面都一定不可以转化为必败局面。

而所有的必胜局面都一定有可能转化为必败局面。怎么转化呢？

对于必胜局面，我们求一下a数组的异或和x，其中一定存在一个$a_k \ge x$，让$a_k\oplus= x$，这样转化为了必败局面。

有向图游戏

当前你和Alice有一个DAG，DAG的一个入度为0的节点上有一个棋子，你们俩轮流把棋子移动一步，不能移动算输。

我们把它抽象成一个模型，为有向图游戏。

显然，一个节点表示一个局面。一条边则表示局面的转移。

 SG函数

我们现在有一个非负整数集合的子集A，定义mex(A)运算代表A集合没有出现的最小非负整数。

mex的参数是一个集合，结果是一个函数值。例如：mex({0,1,4,2,5}) =3

在有向图游戏中，当一个节点是必败局面的时候，

他的SG函数值为0，否则为他所有能够转移到的局面的SG函数值组成的集合的mex值。

SG函数值是一个局面的估价。

SG函数在某年初赛中有考过。

有向图游戏的和

当NIM游戏只有一堆石子的时候（如果石子不为0，先手必胜），

有SG(0)=0,SG(1)=1,SG(2)=2...SG(N)=N。

对于N个有向图游戏，定义他们的和为：每一次移动可以将一个有向图游戏的一个棋子向前移动一步，移动不了的算输。

显然对于一个局面，当前N个棋子所在位置的SG函数值为$\{a_1,a_2,...,a_n\}$，这个局面的SG函数值为这n个a的异或和。

思考题

现在有一块n*m的矩形，矩形有一个格子是黑色的。现在Alice和Bob轮流把这个矩形劈成两半(沿着任意一条格子之间的直线劈开)，保留有黑色格子的那个。

最后无法劈的人输。求先手必胜。

 

固定黑色格子的那个棋子，变为4堆棋子的nim博弈。

平局

例题：A Game With Numbers

Alice和Bob又在玩游戏，他们每个人手里有8个[0,4]之间的数字。每次一个人选自己的一个数字和对方的一个数字，自己的数字+=对方的数字，自己的数字%=5。不能选择0。不能操作者输。现在给一个局面，问胜负还是平局。

读到这里你肯定会很懵逼，这之后只会出现输赢哪里来平局呢？你没有想到过这个有环。

我们先枚举状态。状态数有$(5^8)^2$种（152587890625种），但实际上没有这么多，因为数字的位置和状态无关。

用组合数则$(C_{5+8-1}^8)^2$种。（245025种）。另外我们注意到有些位置胜负已经确定了（当前有一方全是0，那么先手必败，因为无法走了），

我们从这个状态递推（记忆化搜索？）到其它全部状态，推出所有能够确定胜负的状态，

剩下的就是不能够确定胜负的状态辣。时间复杂度$O(5^2*245025)$。

概率论

OI中期望是当前你处于某一个确定的局面，你有若干种可供选择的后继，

选择某种后继具有某个概率，对所有方案出现概率乘以他的最后局面权值的和是这个局面的期望。

通常在OI中，为了方便你做题，一个局面的期望只和当前所处位置有关，和之前的决策无关。

OI中概率的考察通常与递推啊高斯消元什么的相结合。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　-------源自rqj大佬的markdown