尼姆博弈:一种在博弈论中有基石作用的策略
提醒:接下的分析有点烧脑
描述:尼姆博弈是一个两人博弈,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,则先手方有必胜策略;
否则后手方有必胜策略。