尼姆博弈：一种在博弈论中有基石作用的策略
提醒：接下的分析有点烧脑
描述：尼姆博弈是一个两人博弈，2名玩家轮流从数堆物品中拿取一定数量的物品，每次拿取时先选择某一堆，再从中拿取任意数量个物品，至少拿1个，至多将这一堆物品全部拿走，不能不拿。拿到最后一个物品的玩家获胜。
策略：min-sum(以下称s) s等于0 ，后手必胜，s != 0 先手必胜；
两堆的情形
我们从最简单的两堆物品的情形开始分析，并使用二元组（n，m）来表示这两堆物品当前的数量。当（n，m）情形下先手方\后手方有必胜策略时，我们称（n，m）为制胜位置。
我们将说明：当n=m时，后手有必胜策略，否则先手有必胜策略。
当n=m=1时，先手方仅能够将其中一堆完全取走，故后手方只需要将另一堆的1个物品取走即可获胜。即（1，1）是后手方的制胜位置。
当n=m=k>1时，无论先手方选择哪一堆，取走多少数量的物品，后手方只需要选择另一堆，并取走相同数量的物品，就可以将物品堆的状态从（k，k）转换到（j，j），其中j<k。如此操作下去，由于两堆物品的数量保持相等且严格递减，故后手方玩家总能将物品堆的数量转换为（1，1）或（0，0）。由上面的讨论与游戏规则知，后手方必胜。即（n，m），n=m是后手方的制胜位置。
当时，先手方只需要从较多的一堆物品中拿取适量的物品，使得两物品堆物品数量一致，就将情形转换为了上述两种情况之一，且自身处于后手方。由上面的讨论知，先手方必胜。即（n，m），是先手方的制胜位置。
- 两个数的尼姆和(nim-sum)若相同，则两个数一定相同，反之也成立，再者若两个数不等，尼姆和也不相等;但是三个数就不成立；
- 两个数的nim-sum 是两个数转化成二进制后每个位取异或的二进制数；
两个数相等等价于nim-sum = 0
接下来可以将k个数的s为零的情况转化成两个数的情况
定理1：在尼姆和为0时，无论如何拿取物品，拿取之后物品堆的尼姆和一定不为0；
定理2：在尼姆和不为0时，总存在一种拿取物品的方式，使得拿取之后物品堆的尼姆和为0；
用定理该如何推出上面的转化
若物品堆的尼姆和为0，则无论先手方如何拿取，操作之后物品堆的尼姆和一定不为0，先手方总是不能将物品拿完。后手方总是可以选择拿取方式使得物品堆的尼姆和再次为0，同时物品的数量严格减小，这样操作下去，有限多轮之后即可使得后手方拿取物品后所有物品均被拿取，即后手方有必胜策略。
若物品堆的尼姆和不为0，则先手方总可以选择拿取方式使得拿取之后物品堆的尼姆和为0，且处于后手方的位置。由上述讨论可知，先手方有必胜策略。
定理证明
自行点链接
变体
策略：
若尼姆和为0且所有堆中仅有1个物品，则先手方有必胜策略；
若尼姆和不为0且至少有一堆物品数量大于1，则先手方有必胜策略；
否则后手方有必胜策略。
原文地址：http://www.cnblogs.com/zzxs-blog/p/16829813.html
