【专题】Bash博弈

Bash博奕

基本的巴什博弈(Bash Game)描述如下:

有一堆n个物品,两人轮流取走物品,每次至少取一个,最多取m个,最后取光者获胜。

博弈过程如下:

  • 如果n<m,那么先手可以一次取完。先手必胜。

  • 如果n=m+1,那么由于一次最多取走m个,无论先手取走多少个,后手都能一次性取完。此时先手必败。
    可以假设,游戏局面与m+1有关。

  • 如果n%(m+1)=0,那么无论先手取走多少个,假设此时为i个(操作合法时1 $ \le $ i $ \le $ m),后手都能取走m+1-i个,使得局面重新回到n%(m+1)=0。直至最后局面变成n=m+1。此时先手必败。

  • 如果n%(m+1)=k $ \neq $ 0,显然1 $ \le $ k $ \le $ m,那么先手取走k个,则将n%(m+1)=0的必输态(先手必败局面、奇异局面、P-position)留给对面了。此时先手必胜。


修改一下获胜条件:

有一堆n个物品,两人轮流取走物品,每次至少取一个,最多取m个,最后取光者失败。

可以转化为基本的巴什博弈,只不过此时需要给对手留下最后1个,考虑的 $ n’ $ 实际为n-1,即(n-1)%(m+1) ? 先手胜 : 后手胜


另一类的巴什博弈:

有一堆n个物品,两人轮流取走物品,每次至少取p个,最多取q个,剩余不足p个时一次取完,最后取光者失败。

可得 $ n = (p + q) \times r + s $ 时,(s!=0 && s<=p) ? 后手胜 : 先手胜

_/_/_/_/_/ EOF _/_/_/_/_/