博弈 总结和思考 更新中

一、状态分析

在做某些博弈题的时候，最重要的就是P/N局面的分析了。

所谓的P局面及必败点，N局面及必胜点，我所理解的P/N局面是谁走到P点或者N点就必须承受这点所带来的状态，必败或者必胜。所以我摒弃了那种P点即是前一个选手将取胜的位置，N点即是下一个选手将取胜的位置的理解模式，很烦，事实上是一样的，但是一开始我们不用管这个概念，不然绕弯弯也能把自己绕晕。

所以必败点和必胜点满足三个性质：

第一个性质：所有的终结点都是必败点，都必须标记为P点。

解释：很明显，谁最后站在了终结点无法移动的时候，就必须承受这点输的状态，所以终结点一定是必败点。

第二个性质：从任何必胜点（N点）操作，一定有一种策略可以进入必败点（P点）。

解释：初次接触这个的时候，觉得貌似不好理解，我想很多人也是模棱两可，甚至当公式一样背下来，其实很简单，这点之所以被称作必胜点，就是因为处在这点的人一定能采取某种状态将对手置于必败状态，那么当轮到对手操作的时候就必须承受这个必败的状态，从而这点就是必胜点。所以必胜点是一定有方法走到一个必败点的。

第三个性质：无论怎么操作，从必败点（P点）都只能进入必胜点（N点）。

解释：和第二个性质的思考方式一样，试想为什么这点被称作必败点，那是因为走到这点的人，无论怎么操作，就是无论怎么走，都只能走到一个必胜点，那么当下一个人操作的时候承受的是这个必胜点的必胜状态，所以走到这点的人是一定会输的。

在理解第三条性质的时候，我常常想到证明一个公式的合理性，如果能举一个反例把这个公式推翻，那这个公式就肯定不成立，所以要证明一个点是必败点，那么你就想想有没有方法可以走到一个必败点，让对方处于必败状态，如果没有，那么这点当然就必败了。反之，你要有方法走到这么一给点，让对方处于必败状态，那么处在这点的人不一定会输，所以这点当然不能成为必败点了。所以从必败点只能走到必胜点。

实战演练：杭电2147 kiki's gamehttp://acm.hdu.edu.cn/showproblem.php?pid=2147

这个题就是简单的分析必败点和必胜点的。

题意：给你一个n*m的棋盘，首先硬币是放在右上角的，每次只能往左或者往下，或者往左下方走，如果谁走到某个点不能再动谁就输了。

很明显，终点是左下角这个点，因为无论谁走到这一点，都没法动了，所以走到这点的人就输了。

所以根据这三条性质我们可以试着描述下PN点得状态。

假设棋盘是5*3的，那么这个PN分析状态就是如下：

PNP
NNN
PNP
NNN
PNP

终点左下角标记为P，从这个点开始，我们看和它相近的点（4,1）（4,2）（5，2），显然这三点是都可以一步走到终点的，也就是说这三点能走到一个必败点，使对方置于必败状态，所以这三点都标记为N点，必胜点，再看（5,3）这点，此时无论走到这点的人采取什么策略，都只能往（5,2）这点走，而（5,2）已经标记为N点，所以它只能走到必胜点，因此它被标记为P点，即是必败点。依次类推，就能把这个图画出来。

我们已经学会了分析必败点和必胜点，那么也就能把这题做出来了。我们不妨从n,m的奇偶性去思考，上面我们分析的是n,m都是奇数的，此时右上角是P点，及必败点，所以先手必输。那么我们不妨再考虑下n为偶数m为奇数，n为奇数m为偶数，n,m都为偶数的P/N图，我们会发现只有n,m都为奇数的时候，先手必输，所以这题得到完美解答。

二、NIM问题

经典的取石子问题，有N堆石子，其中第i堆有Pi颗石子，从某一堆里取出若干石子去掉，两人轮流操作，谁不能继续取石子，谁就输了。

这个问题有个结论：S=p1^p2……p^n ，当S=0的时候是必败点。

那么怎么理解？首先看终点，肯定是0,0……0，所以S=0，满足这个结论。

然后看其他点，当S=0的时候，及S=p1^p2……^pi……^pn=0,那么S=p1^p2……^pn（不异或pi)肯定是等于pi的，不然S=p1^p2……^pi……^pn也不可能等于0，那么我们从pi取出一些石子后，pi'也就不再等于pi了，所以S=p1^p2……^pi'……^pn肯定就不等于0了。由此可知从S=0这个点，无论怎么走，都只能走到S<>0（S不等于0）的点，所以S=0的点称为必败点。

再看S!=0的时候，设S的二进制位是A1…An，考虑第一位是1的。在P中取出该位同是1的，不妨设为P1。可知P1 ^S<P1，令P1’=P1 XOR S。可知P1’ XOR P2 XOR … XOR Pn=0。即满足N局面存在至少一个子局面是P局面。所以这点就是N点，必胜点。

三、NIM问题的扩展问题。

还是取石子问题。有N堆石子，第i堆有Pi个石子，每次去掉某一堆里最多m颗石子，（m>0)，两人轮流操作，谁不能继续取石子，谁就输了。

这个问题的结论是：将每堆石子对m+1取模后异或，若异或等于0，就是必败点。

怎么理解？其实有了上面的基础，这个问题真的很好理解了。我们把所有的石子分成两部分，一部分是m+1的倍数r1r2……rn,一部分为p1',p2'……pn'.那么p1',p2'……pn'这部分就直接按nim的方法取石子就行了，而对于r1,r2……rn这部分，由于他们是m+1的倍数，所以我们可以在对手取K颗石子的时候，我们取m-1+K颗。

若初始局面为胜局面，P1 ’ P2 ’ P3 ’ … Pn ’部分NIM方法取子必胜，由于r1r2r3 …rn都为m+1的倍数，因此，按m+1互补的取法，先手一定能取到最后K<=m颗石子。

四、NIMk问题

还是取石子问题。
有N堆石子，其中第i堆有Pi颗石子，每次可以从最多K堆中选出若干石子去掉（但不能不去石子），两人轮流取石，谁不能继续取谁就输了。什么情况下先手必胜，什么情况下后手必胜?

K=1，为Nim问题。
对于K>1的情况，我们令把P1~Pn这n个数，转成二进制，然后每位分别相加，每位最后结果mod (K+1)即可。如果每一位结果都是0，则为P局面，否则是N局面。
示例
P1P2P3P4=3,5,10,15 ，K=2

3—————— 1 1
5—————— 1 0 1
10—————— 1 0 1 0
15 —————— 1 1 1 1
2 2 0 0
所以这是N局面。
证明与NIM证明类似。

五、MisèreNim问题

有N堆石子，每次从某一堆里选出若干石子去掉（但不能不去石子），两人轮流取石，谁不能继续取谁就赢了。

所有石子堆的数目都为1：显然，若有偶数堆石子堆，则必胜，否则必败。
如果恰好只有一堆石子数目大于1。
我们可以把这堆石子取完或者取得只剩下1，使得只剩下奇数堆数目为1的石子留给对方，由1)，必胜。

如果有至少2堆石子的数目大于1。
考虑异或值：若异或值不为0，则按照Nim走法取石。
这样，当对手某次取完石子后，肯定会出现情况2，必胜。

证明：按照Nim走法则取完石子后，必定会给对手留下异或值为0的局面。
因此不可能给对手留下情况2 的局面（容易证明，情况2 局面的异或值肯定不为0），
而对手一次最多将一堆石子数大于1的石子堆处理掉。因此情况2 的情况肯定会出现。

相反，若异或值为0，则无论如何走都会给对方留下情况2 或情况3的情况，必败。