常见的几个博弈
常见的几个博弈
第一种：巴什博弈
游戏玩法: 有一堆物品共n个,两人轮流取物，一次最少取一个最多取m个。取走最后一个的胜。
思路：当n<=m时 显然先手胜。
n=m+1时 无论先手怎么取 后手都能取完,所以此时的状态为平衡态。谁面临这个状态必输。
已知n%(m+1)!=0时 先手显然可以取走n%(m+1)的余数让对手变为平衡态。
至此，规律已经出来了：
N%(m+1)==0 后手胜,否则先手胜。
试题传送门：
HDU-Brave_Game
第二种：威佐夫博弈
两堆物品,两人轮流取,一次可从一堆取至少 1个至多全部，或从两堆取相同数，取最后一个的人获胜。
思路：第i个必败态的bi=ai+i。
且第i个必败态的ai为前面为出现的最小自然数。
根据beatty序列可证明：
试题传送门：Matches Game
第三种：尼姆博弈
给任意堆物品,每堆物品数任意个,双方轮流取，一次只能从一堆中最少取一个，最多取全部,取走最后一个物品人获胜。
用括号(k1,k2,k3……kn)表示每堆的数目
当为一堆是(k) 可知k=0为必败态，
K>0为必胜态。
两堆：(k1,k2) k1=k2=0为必败态
K1,k2其中一个为0,另一个非0为必胜态。
K1,k2都非0，1.(1,1) 可知为必败态。
2.(1,2)可以通过先手拿一个转化为（1，1）必败态，所以(1,2)为必胜态。
同理可知(2,2)必败态,(k,k)为必败态。
只要后手拿先手之前拿的另一堆相同的数目始终保持两堆相同,直到先手方拿光一堆,此时状态为(K,0)所以后手必胜。
所以(k,k)为必败态。
三堆(k1,k2,k3)如果存在两堆相同，
则先手可以通过拿令一堆使后手处于必败态,所以此时(k,k,k3)为必胜态。
K3=k也是必胜态。
2：当k1,k2,k3都不相同。可以猜想谁先把状态变为必败态，谁就赢。
---------------------------------------------------------------------------------------至此可以猜想规律与异或和有关。
因为两个数相同异或和为0
而两个数相同正好为必败态。
三个相同异或和为该数本身不是0.
可以知道将所有堆物品数进行异或和
若结果为0则为必败态，后手胜。
否则先手胜。
试题传送门：取石子游戏