BashGame 巴什博弈

问题

$A$和$B$两人轮流从$n$个物品中取出物品，每次取的物品数限定为$(1 - p)$（至少取$1$个，至多取$p$个。$n, p$都是正整数且$p \lt n$，显然若$p \ge n$则第一个取的人一次就可以把所有物品取走从而获胜）个，最后一个把物品取光的人获胜。

给定$n$和$p$，当我方先手，我方和对方都是高手（在能赢的情况下一定能赢），求我方是否能赢。

巴什博弈还可以描述为：$A$和$B$两人轮流向一个篮子中放入物品，篮子最多能放$n$个物品。每次放的物品数量限定为$(1 - p)$，最后一个把篮子填满的人获胜。

上面两个问题其实是相同的，只是放和取的过程相反。本章中其他的博弈问题都可以像这样用相反的过程进行颠倒。

解法

若$n = p + 1$，$A$取$(1 - p)$个物品，剩下$(1 - p)$个物品。下一次$B$总能一次取光，$B$获胜。

介绍博弈论中的概念“局势”，当一方做选择时，剩余的物品数量为$x$时，称这一方面对的局势为$(x)$。对于$n = 50, p = 4$的情况：

$(1)$ 当我方面临$(1 - 4)$局势时，我方必赢，因为我方可以将剩余物品都拿光；

$(2)$ 当我方面临$(5)$局势时，我方必输，因为我方取物品后，必然留给对方$(0 - 4)$局势，对方必赢；

$(3)$ 当我方面临$(6 - 9)$局势时，我方必赢，因为我方可以留给对方$(5)$局势，对方必输；

$$\cdots$$

可以看出，当留给对方$p + 1$个物品时，下一轮对方必然会输，因为对方必然取$(1 - p)$个物品，留给我方$(1 - p)$个物品。称这样的物品数量为必赢数量$w = p + 1$。

当我方取物品时面对$w$的倍数个物品时，我方必输，即$n \mod (p + 1) = 0$。否则对方必输。

该算法的时间复杂度为$O(1)$。

源码

BashGame.h

BashGame.cpp

测试

BashGameTest.cpp