Alice与Bob一维数轴博弈的最优策略推导及结论证明

先把游戏规则捋明白 #

咱们先把这个博弈的核心规则说清楚：

• Alice和Bob一开始在数轴上的整数点a和b（保证a < b），两人的初始距离记为d = b - a
• Alice先手，每回合玩家可以选择向对手移动0、2或3个单位，但自己当前的移动必须和上一次自己的移动不同（第一次移动无限制）
• 游戏结束判定：
  • 若玩家直接落在对手当前位置，该玩家获胜
  • 若玩家越过对手落到另一侧，则对手获胜
• 俩人都是玩博弈的老油条，会采取最优策略，咱们要判断最终谁能赢

从小距离试起，摸规律 #

咱们先从最小的几个d值一个个拆解，先搞懂小局面的胜负逻辑，再归纳通用结论：

d=1：Bob稳赢 #

Alice不管选啥移动都没好结果：

• 选移动0：距离还是1，Bob也跟着选0。接下来Alice只能选2或3，不管选哪个都会越过Bob，直接输
• 选移动2或3：直接越过Bob，当场落败
  所以d=1时，Bob躺赢

d=2：Alice直接拿捏 #

Alice直接选移动2，精准落到Bob的位置，秒赢，没啥好纠结的

d=3：Alice同样直接获胜 #

Alice选移动3，刚好落在Bob所在的位置，直接结束游戏拿胜局

d=4：Alice有必胜套路 #

Alice可以先选移动3，把距离缩到1。这时候Bob只能选0（选2或3都会越过Alice），接下来Alice因为上一次选了3，这次不能再选3，但可以选2，刚好落到Bob位置获胜。总之Alice有明确的必胜路径

d=5：Bob的必胜局 #

不管Alice选啥操作，Bob都能精准应对：

• Alice动0：Bob也动0，接下来Alice只能选2或3：Alice动2，Bob就动3（和自己上一次的0不同），刚好落到Alice位置；Alice动3，Bob就动2，同样获胜
• Alice动2：距离变3，Bob直接动3，落到Alice位置赢
• Alice动3：距离变2，Bob直接动2，落到Alice位置赢
  所以d=5时Bob稳赢

d=6：Bob还是稳赢 #

Alice不管选啥，Bob都能把局面拉到d=1的Bob必胜局：

• Alice动0：Bob动0，Alice选2的话距离变4，Bob动3把距离缩到1；Alice选3的话距离变3，Bob动2把距离缩到1
• Alice动2：距离变4，Bob动3缩到1；Alice动3：距离变3，Bob动2缩到1
  最后都会落到d=1的局面，Bob获胜

归纳到模5的通用结论 #

试完小值后规律已经很明显了，接下来用归纳法证明这个结论的通用性：

归纳假设 #

假设对于所有小于d的距离k，以下结论都成立：

• k=1时Bob赢，k=2时Alice赢
• k≥3时，若k mod5是3或4，Alice赢；其他情况Bob赢

分情况讨论d的模5结果 #

情况1：d ≡0 mod5（比如5、10、15...）

不管Alice选啥移动，Bob都能把距离拉回5的倍数：

• Alice动0：Bob也动0，Alice下一次只能选2或3，Alice动2的话Bob动3，把距离缩到5(k-1)；Alice动3的话Bob动2，同样缩到5(k-1)
• Alice动2：距离变5k-2，Bob动3，直接缩到5(k-1)
• Alice动3：距离变5k-3，Bob动2，直接缩到5(k-1)
  最后会落到d=5的局面，Bob获胜

情况2：d≡1 mod5（比如1、6、11...）

Alice不管怎么动，Bob都能把距离拉回5k+1的局面：

• Alice动0：Bob动0，Alice动2的话Bob动3，距离变5(k-1)+1；Alice动3的话Bob动2，距离也变5(k-1)+1
• Alice动2：距离变5k-1=5(k-1)+4，Bob动3，距离变5(k-1)+1
• Alice动3：距离变5k-2=5(k-1)+3，Bob动2，距离变5(k-1)+1
  最后落到d=1的局面，Bob获胜

情况3：d≡2 mod5（比如2、7、12...）

这里注意只有d=2时Alice赢，d≥7时Bob赢：

• Alice动0：Bob动0，Alice动2的话距离变5k，Bob赢；Alice动3的话距离变5(k-1)+4，Bob动3把距离变5(k-1)+1，Bob赢
• Alice动2：距离变5k，Bob赢
• Alice动3：距离变5(k-1)+4，Bob动3把距离变5(k-1)+1，Bob赢
  所以d≥7且≡2 mod5时，Bob获胜

情况4：d≡3 mod5（比如3、8、13...）

Alice可以选移动2，把距离变5k+1（Bob必败的局面）；或者选移动3，把距离变5k（Bob必败的局面）。比如d=8，Alice动2，距离变6（≡1 mod5），Bob不管怎么动，Alice都能跟着把局面拉到自己赢的情况。总之Alice有办法把局面推给Bob的必败局，所以Alice获胜

情况5：d≡4 mod5（比如4、9、14...）

Alice可以选移动2，把距离变5k+2（d≥7时Bob必败）；或者选移动3，把距离变5k+1（Bob必败）。比如d=9，Alice动3，距离变6（≡1 mod5），Bob只能被动应对，最后Alice获胜

最终结论汇总 #

把所有情况整理成清晰的判定规则：

• 当d=1：Bob获胜
• 当d=2：Alice获胜
• 当d≥3：
  • 如果d mod5等于3或4，Alice获胜
  • 其他情况（d mod5为0、1、2），Bob获胜

备注：内容来源于stack exchange，提问作者coder1229