2020年杭州 Ninth题号 1003 Slime and Stones 扩展威佐夫博弈 Betty's theorem

阅读量：

2020 杭电第九场 1003 Slime and Stones 扩展威佐夫博弈 betty定理

分为两堆石子，并存在两种取法可供选择：第一种方法允许从单一一堆中取出任意数量的石子；第二种方法规定从两堆中取的数量差不超过k个。

其中威佐夫博弈的核心在于找到所谓的P-position即处于必输状态的位置这些位置具有特定的数学规律可以通过公式 $P_k = (k \cdot (1+\sqrt{2}), k \cdot (2+\sqrt{2}))$ 来表示其中 $k$ 为自然数

威佐夫博弈就是题目中k==0的特殊情况，那我们先讨论这种特殊情况吧。

我们深入探讨这个游戏的局面特性时会发现一些特定局势具有先手必败的特点。例如，在状态 $(0, 0)$ 时先手无法采取有效行动，在状态 $(1, 2)$ 时先手同样面临困境。

在状态 $(1, 2)$ 时我们具体分析先手可能采取的策略：

第一种策略是先手选择移除第一堆的所有石子此时后手将采取行动移除第二堆的所有石子从而实现胜利。

第二种策略是先手选择仅从第二堆中取出一枚石子此时局势变为 $(1, 1)$ 后手将采取同步行动最终导致胜利。

第三种策略同样是先手移除第二堆的所有石子随后后手将移除第一

还没有任何评论哟~